Page Speed Optimization Libraries  1.13.35.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
priority_queue.h
Go to the documentation of this file.
1 // Copyright 2016 Google Inc.
16 
17 #ifndef PAGESPEED_CONTROLLER_PRIORITY_QUEUE_H_
18 #define PAGESPEED_CONTROLLER_PRIORITY_QUEUE_H_
19 
20 #include <cstddef>
21 #include <functional>
22 #include <utility>
23 #include <unordered_map>
24 #include <vector>
25 
26 #include "base/logging.h"
27 #include "base/macros.h"
29 
31 
32 namespace net_instaweb {
33 
34 template <typename T,
35  typename HashFn = std::hash<T>,
36  typename EqFn = std::equal_to<T>>
38  public:
39  PriorityQueue() { }
40  ~PriorityQueue() { Clear(); }
41 
44  void IncreasePriority(const T& key, int64 amount);
45 
47  void Increment(const T& key);
48 
50  void Remove(const T& key);
51 
53  const std::pair<const T*, int64>& Top() const;
54 
56  void Pop();
57 
58  bool Empty() const { return queue_.empty(); }
59  size_t Size() const { return queue_.size(); }
60 
61  void Clear();
62 
63  private:
67  struct PtrHash {
68  size_t operator()(const T* x) const {
69  return HashFn()(*x);
70  }
71  };
72 
73  struct PtrEq {
74  bool operator()(const T* x, const T* y) const {
75  return (x == y || EqFn()(*x, *y));
76  }
77  };
78 
81  void Rebalance(size_t pos);
82  void PushDown(size_t pos);
83  void PushUp(size_t pos);
84 
86  void SwapElements(size_t a, size_t b);
87 
90  void SanityCheckForTesting() const;
91 
93  typedef std::unordered_map<const T*, size_t, PtrHash, PtrEq>
94  IndexMap;
95  IndexMap index_map_;
96 
99  typedef std::pair<const T*, int64> QueueEntry;
100  std::vector<QueueEntry> queue_;
101 
102  friend class PriorityQueueTest;
103 
104 
105 };
106 
107 template <typename T, typename Hash, typename Equal>
109  index_map_.clear();
110  for (const QueueEntry& qe : queue_) {
111  delete qe.first;
112  }
113  queue_.clear();
114 }
115 
116 template <typename T, typename Hash, typename Equal>
118  IncreasePriority(key, 1);
119 }
120 
121 template <typename T, typename Hash, typename Equal>
123  int64 amount) {
124  typename IndexMap::iterator i = index_map_.find(&key);
126  if (i == index_map_.end()) {
128  size_t queue_pos = queue_.size();
129  queue_.emplace_back(new T(key), 0);
131  const T* created_key = queue_.back().first;
132  std::pair<typename IndexMap::iterator, bool> insert_result =
133  index_map_.emplace(created_key, queue_pos);
134  CHECK(insert_result.second);
135  i = insert_result.first;
136  }
137  size_t queue_pos = i->second;
138  CHECK(queue_pos < queue_.size());
139  queue_[queue_pos].second += amount;
140  Rebalance(queue_pos);
141 }
142 
143 template <typename T, typename Hash, typename Equal>
145  typename IndexMap::iterator i = index_map_.find(&key);
146  if (i == index_map_.end()) {
148  return;
149  }
150 
153  size_t removed_pos = i->second;
154  SwapElements(removed_pos, queue_.size() - 1);
155 
157  const T* removed_key = queue_.back().first;
158  queue_.pop_back();
159  index_map_.erase(i);
160  delete removed_key;
161 
162  if (!Empty() && removed_pos < queue_.size()) {
163  Rebalance(removed_pos);
164  }
165 }
166 
167 template <typename T, typename Hash, typename Equal>
169  CHECK_LT(pos, queue_.size());
170 
171  size_t parent_pos = (pos >> 1);
172 
175  if (pos != 0 && queue_[parent_pos].second < queue_[pos].second) {
176  PushUp(pos);
177  } else {
178  PushDown(pos);
179  }
180 }
181 
182 template <typename T, typename Hash, typename Equal>
183 const std::pair<const T*, int64>& PriorityQueue<T, Hash, Equal>::Top() const {
184  CHECK(!Empty());
185  return queue_.front();
186 }
187 
188 template <typename T, typename Hash, typename Equal>
190  if (!Empty()) {
193  SwapElements(0, queue_.size() - 1);
196  const T* removed_key = queue_.back().first;
197  queue_.pop_back();
199  size_t num_deleted = index_map_.erase(removed_key);
200  CHECK_EQ(num_deleted, 1);
202  delete removed_key;
205  PushDown(0);
206  }
207 }
208 
209 template <typename T, typename Hash, typename Equal>
210 void PriorityQueue<T, Hash, Equal>::SwapElements(size_t a_idx, size_t b_idx) {
211  if (a_idx != b_idx) {
212  const T* a_key = queue_[a_idx].first;
213  const T* b_key = queue_[b_idx].first;
214  std::swap(index_map_[a_key], index_map_[b_key]);
215  std::swap(queue_[a_idx], queue_[b_idx]);
216  }
217 }
218 
219 template <typename T, typename Hash, typename Equal>
220 void PriorityQueue<T, Hash, Equal>::PushDown(size_t pos) {
221  while (pos * 2 < queue_.size()) {
222  size_t child = pos * 2;
224  if (child + 1 < queue_.size() &&
225  queue_[child].second < queue_[child + 1].second) {
226  ++child;
227  }
229  if (queue_[pos].second < queue_[child].second) {
230  SwapElements(pos, child);
231  pos = child;
232  } else {
233  break;
234  }
235  }
236 }
237 
238 template <typename T, typename Hash, typename Equal>
239 void PriorityQueue<T, Hash, Equal>::PushUp(size_t pos) {
240  while (pos != 0 && pos < queue_.size()) {
241  size_t parent = (pos >> 1);
242  if (queue_[parent].second < queue_[pos].second) {
243  SwapElements(pos, parent);
244  pos = parent;
245  } else {
246  break;
247  }
248  }
249 }
250 
251 template <typename T, typename Hash, typename Equal>
252 void PriorityQueue<T, Hash, Equal>::SanityCheckForTesting() const {
253  CHECK_EQ(queue_.size(), index_map_.size());
254 
255  for (size_t queue_pos = 0; queue_pos < queue_.size(); ++queue_pos) {
257  const T* key = queue_[queue_pos].first;
259  typename IndexMap::const_iterator i = index_map_.find(key);
260  CHECK(i != index_map_.end());
261  size_t indexed_pos = i->second;
262  CHECK_EQ(indexed_pos, queue_pos);
263 
265  if (queue_pos > 0) {
266  size_t parent_pos = (queue_pos >> 1);
267  CHECK_LE(queue_[queue_pos].second, queue_[parent_pos].second);
268  }
269  }
270 }
271 
272 }
273 
274 #endif
void Remove(const T &key)
Remove a given element. Silently succeeds if the element isn't present.
Definition: priority_queue.h:144
Definition: priority_queue.h:37
void Pop()
Remove the key with the highest priority from the queue.
Definition: priority_queue.h:189
void IncreasePriority(const T &key, int64 amount)
Definition: priority_queue.h:122
const std::pair< const T *, int64 > & Top() const
Return the key with the highest priority, and its priority.
Definition: priority_queue.h:183
void Increment(const T &key)
Eqivalent to IncreasePriority(key, 1).
Definition: priority_queue.h:117