OLD | NEW |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef NET_BASE_PRIORITY_QUEUE_H_ | 5 #ifndef NET_BASE_PRIORITY_QUEUE_H_ |
6 #define NET_BASE_PRIORITY_QUEUE_H_ | 6 #define NET_BASE_PRIORITY_QUEUE_H_ |
7 | 7 |
8 #include <stddef.h> | 8 #include <stddef.h> |
9 #include <stdint.h> | 9 #include <stdint.h> |
10 | 10 |
11 #include <list> | 11 #include <list> |
12 #include <vector> | 12 #include <vector> |
13 | 13 |
14 #include "base/logging.h" | 14 #include "base/logging.h" |
15 #include "base/macros.h" | 15 #include "base/macros.h" |
16 #include "base/threading/non_thread_safe.h" | 16 #include "base/threading/thread_checker.h" |
17 | 17 |
18 #if !defined(NDEBUG) | 18 #if !defined(NDEBUG) |
19 #include <unordered_set> | 19 #include <unordered_set> |
20 #endif | 20 #endif |
21 | 21 |
22 namespace net { | 22 namespace net { |
23 | 23 |
24 // A simple priority queue. The order of values is by priority and then FIFO. | 24 // A simple priority queue. The order of values is by priority and then FIFO. |
25 // Unlike the std::priority_queue, this implementation allows erasing elements | 25 // Unlike the std::priority_queue, this implementation allows erasing elements |
26 // from the queue, and all operations are O(p) time for p priority levels. | 26 // from the queue, and all operations are O(p) time for p priority levels. |
27 // The queue is agnostic to priority ordering (whether 0 precedes 1). | 27 // The queue is agnostic to priority ordering (whether 0 precedes 1). |
28 // If the highest priority is 0, FirstMin() returns the first in order. | 28 // If the highest priority is 0, FirstMin() returns the first in order. |
29 // | 29 // |
30 // In debug-mode, the internal queues store (id, value) pairs where id is used | 30 // In debug-mode, the internal queues store (id, value) pairs where id is used |
31 // to validate Pointers. | 31 // to validate Pointers. |
32 // | 32 // |
33 template<typename T> | 33 template <typename T> |
34 class PriorityQueue : public base::NonThreadSafe { | 34 class PriorityQueue { |
35 private: | 35 private: |
36 // This section is up-front for Pointer only. | 36 // This section is up-front for Pointer only. |
37 #if !defined(NDEBUG) | 37 #if !defined(NDEBUG) |
38 typedef std::list<std::pair<unsigned, T> > List; | 38 typedef std::list<std::pair<unsigned, T> > List; |
39 #else | 39 #else |
40 typedef std::list<T> List; | 40 typedef std::list<T> List; |
41 #endif | 41 #endif |
42 | 42 |
43 public: | 43 public: |
44 typedef uint32_t Priority; | 44 typedef uint32_t Priority; |
(...skipping 85 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
130 }; | 130 }; |
131 | 131 |
132 // Creates a new queue for |num_priorities|. | 132 // Creates a new queue for |num_priorities|. |
133 explicit PriorityQueue(Priority num_priorities) | 133 explicit PriorityQueue(Priority num_priorities) |
134 : lists_(num_priorities), size_(0) { | 134 : lists_(num_priorities), size_(0) { |
135 #if !defined(NDEBUG) | 135 #if !defined(NDEBUG) |
136 next_id_ = 0; | 136 next_id_ = 0; |
137 #endif | 137 #endif |
138 } | 138 } |
139 | 139 |
| 140 ~PriorityQueue() { DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); } |
| 141 |
140 // Adds |value| with |priority| to the queue. Returns a pointer to the | 142 // Adds |value| with |priority| to the queue. Returns a pointer to the |
141 // created element. | 143 // created element. |
142 Pointer Insert(const T& value, Priority priority) { | 144 Pointer Insert(const T& value, Priority priority) { |
143 DCHECK(CalledOnValidThread()); | 145 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
144 DCHECK_LT(priority, lists_.size()); | 146 DCHECK_LT(priority, lists_.size()); |
145 ++size_; | 147 ++size_; |
146 List& list = lists_[priority]; | 148 List& list = lists_[priority]; |
147 #if !defined(NDEBUG) | 149 #if !defined(NDEBUG) |
148 unsigned id = next_id_; | 150 unsigned id = next_id_; |
149 valid_ids_.insert(id); | 151 valid_ids_.insert(id); |
150 ++next_id_; | 152 ++next_id_; |
151 return Pointer(priority, list.insert(list.end(), | 153 return Pointer(priority, list.insert(list.end(), |
152 std::make_pair(id, value))); | 154 std::make_pair(id, value))); |
153 #else | 155 #else |
154 return Pointer(priority, list.insert(list.end(), value)); | 156 return Pointer(priority, list.insert(list.end(), value)); |
155 #endif | 157 #endif |
156 } | 158 } |
157 | 159 |
158 // Adds |value| with |priority| to the queue. Returns a pointer to the | 160 // Adds |value| with |priority| to the queue. Returns a pointer to the |
159 // created element. | 161 // created element. |
160 Pointer InsertAtFront(const T& value, Priority priority) { | 162 Pointer InsertAtFront(const T& value, Priority priority) { |
161 DCHECK(CalledOnValidThread()); | 163 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
162 DCHECK_LT(priority, lists_.size()); | 164 DCHECK_LT(priority, lists_.size()); |
163 ++size_; | 165 ++size_; |
164 List& list = lists_[priority]; | 166 List& list = lists_[priority]; |
165 #if !defined(NDEBUG) | 167 #if !defined(NDEBUG) |
166 unsigned id = next_id_; | 168 unsigned id = next_id_; |
167 valid_ids_.insert(id); | 169 valid_ids_.insert(id); |
168 ++next_id_; | 170 ++next_id_; |
169 return Pointer(priority, list.insert(list.begin(), | 171 return Pointer(priority, list.insert(list.begin(), |
170 std::make_pair(id, value))); | 172 std::make_pair(id, value))); |
171 #else | 173 #else |
172 return Pointer(priority, list.insert(list.begin(), value)); | 174 return Pointer(priority, list.insert(list.begin(), value)); |
173 #endif | 175 #endif |
174 } | 176 } |
175 | 177 |
176 // Removes the value pointed by |pointer| from the queue. All pointers to this | 178 // Removes the value pointed by |pointer| from the queue. All pointers to this |
177 // value including |pointer| become invalid. | 179 // value including |pointer| become invalid. |
178 void Erase(const Pointer& pointer) { | 180 void Erase(const Pointer& pointer) { |
179 DCHECK(CalledOnValidThread()); | 181 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
180 DCHECK_LT(pointer.priority_, lists_.size()); | 182 DCHECK_LT(pointer.priority_, lists_.size()); |
181 DCHECK_GT(size_, 0u); | 183 DCHECK_GT(size_, 0u); |
182 | 184 |
183 #if !defined(NDEBUG) | 185 #if !defined(NDEBUG) |
184 DCHECK_EQ(1u, valid_ids_.erase(pointer.id_)); | 186 DCHECK_EQ(1u, valid_ids_.erase(pointer.id_)); |
185 DCHECK_EQ(pointer.iterator_->first, pointer.id_); | 187 DCHECK_EQ(pointer.iterator_->first, pointer.id_); |
186 #endif | 188 #endif |
187 | 189 |
188 --size_; | 190 --size_; |
189 lists_[pointer.priority_].erase(pointer.iterator_); | 191 lists_[pointer.priority_].erase(pointer.iterator_); |
190 } | 192 } |
191 | 193 |
192 // Returns a pointer to the first value of minimum priority or a null-pointer | 194 // Returns a pointer to the first value of minimum priority or a null-pointer |
193 // if empty. | 195 // if empty. |
194 Pointer FirstMin() const { | 196 Pointer FirstMin() const { |
195 DCHECK(CalledOnValidThread()); | 197 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
196 for (size_t i = 0; i < lists_.size(); ++i) { | 198 for (size_t i = 0; i < lists_.size(); ++i) { |
197 List* list = const_cast<List*>(&lists_[i]); | 199 List* list = const_cast<List*>(&lists_[i]); |
198 if (!list->empty()) | 200 if (!list->empty()) |
199 return Pointer(i, list->begin()); | 201 return Pointer(i, list->begin()); |
200 } | 202 } |
201 return Pointer(); | 203 return Pointer(); |
202 } | 204 } |
203 | 205 |
204 // Returns a pointer to the last value of minimum priority or a null-pointer | 206 // Returns a pointer to the last value of minimum priority or a null-pointer |
205 // if empty. | 207 // if empty. |
206 Pointer LastMin() const { | 208 Pointer LastMin() const { |
207 DCHECK(CalledOnValidThread()); | 209 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
208 for (size_t i = 0; i < lists_.size(); ++i) { | 210 for (size_t i = 0; i < lists_.size(); ++i) { |
209 List* list = const_cast<List*>(&lists_[i]); | 211 List* list = const_cast<List*>(&lists_[i]); |
210 if (!list->empty()) | 212 if (!list->empty()) |
211 return Pointer(i, --list->end()); | 213 return Pointer(i, --list->end()); |
212 } | 214 } |
213 return Pointer(); | 215 return Pointer(); |
214 } | 216 } |
215 | 217 |
216 // Returns a pointer to the first value of maximum priority or a null-pointer | 218 // Returns a pointer to the first value of maximum priority or a null-pointer |
217 // if empty. | 219 // if empty. |
218 Pointer FirstMax() const { | 220 Pointer FirstMax() const { |
219 DCHECK(CalledOnValidThread()); | 221 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
220 for (size_t i = lists_.size(); i > 0; --i) { | 222 for (size_t i = lists_.size(); i > 0; --i) { |
221 size_t index = i - 1; | 223 size_t index = i - 1; |
222 List* list = const_cast<List*>(&lists_[index]); | 224 List* list = const_cast<List*>(&lists_[index]); |
223 if (!list->empty()) | 225 if (!list->empty()) |
224 return Pointer(index, list->begin()); | 226 return Pointer(index, list->begin()); |
225 } | 227 } |
226 return Pointer(); | 228 return Pointer(); |
227 } | 229 } |
228 | 230 |
229 // Returns a pointer to the last value of maximum priority or a null-pointer | 231 // Returns a pointer to the last value of maximum priority or a null-pointer |
230 // if empty. | 232 // if empty. |
231 Pointer LastMax() const { | 233 Pointer LastMax() const { |
232 DCHECK(CalledOnValidThread()); | 234 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
233 for (size_t i = lists_.size(); i > 0; --i) { | 235 for (size_t i = lists_.size(); i > 0; --i) { |
234 size_t index = i - 1; | 236 size_t index = i - 1; |
235 List* list = const_cast<List*>(&lists_[index]); | 237 List* list = const_cast<List*>(&lists_[index]); |
236 if (!list->empty()) | 238 if (!list->empty()) |
237 return Pointer(index, --list->end()); | 239 return Pointer(index, --list->end()); |
238 } | 240 } |
239 return Pointer(); | 241 return Pointer(); |
240 } | 242 } |
241 | 243 |
242 // Given an ordering of the values in this queue by decreasing | 244 // Given an ordering of the values in this queue by decreasing |
243 // priority and then FIFO, returns a pointer to the value following | 245 // priority and then FIFO, returns a pointer to the value following |
244 // the value of the given pointer (which must be non-NULL). | 246 // the value of the given pointer (which must be non-NULL). |
245 // | 247 // |
246 // (One could also implement GetNextTowardsFirstMin() [decreasing | 248 // (One could also implement GetNextTowardsFirstMin() [decreasing |
247 // priority, then reverse FIFO] as well as | 249 // priority, then reverse FIFO] as well as |
248 // GetNextTowards{First,Last}Max() [increasing priority, then | 250 // GetNextTowards{First,Last}Max() [increasing priority, then |
249 // {,reverse} FIFO].) | 251 // {,reverse} FIFO].) |
250 Pointer GetNextTowardsLastMin(const Pointer& pointer) const { | 252 Pointer GetNextTowardsLastMin(const Pointer& pointer) const { |
251 DCHECK(CalledOnValidThread()); | 253 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
252 DCHECK(!pointer.is_null()); | 254 DCHECK(!pointer.is_null()); |
253 DCHECK_LT(pointer.priority_, lists_.size()); | 255 DCHECK_LT(pointer.priority_, lists_.size()); |
254 | 256 |
255 typename Pointer::ListIterator it = pointer.iterator_; | 257 typename Pointer::ListIterator it = pointer.iterator_; |
256 Priority priority = pointer.priority_; | 258 Priority priority = pointer.priority_; |
257 DCHECK(it != lists_[priority].end()); | 259 DCHECK(it != lists_[priority].end()); |
258 ++it; | 260 ++it; |
259 while (it == lists_[priority].end()) { | 261 while (it == lists_[priority].end()) { |
260 if (priority == 0u) | 262 if (priority == 0u) |
261 return Pointer(); | 263 return Pointer(); |
262 --priority; | 264 --priority; |
263 it = const_cast<List*>(&lists_[priority])->begin(); | 265 it = const_cast<List*>(&lists_[priority])->begin(); |
264 } | 266 } |
265 return Pointer(priority, it); | 267 return Pointer(priority, it); |
266 } | 268 } |
267 | 269 |
268 // Empties the queue. All pointers become invalid. | 270 // Empties the queue. All pointers become invalid. |
269 void Clear() { | 271 void Clear() { |
270 DCHECK(CalledOnValidThread()); | 272 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
271 for (size_t i = 0; i < lists_.size(); ++i) { | 273 for (size_t i = 0; i < lists_.size(); ++i) { |
272 lists_[i].clear(); | 274 lists_[i].clear(); |
273 } | 275 } |
274 #if !defined(NDEBUG) | 276 #if !defined(NDEBUG) |
275 valid_ids_.clear(); | 277 valid_ids_.clear(); |
276 #endif | 278 #endif |
277 size_ = 0u; | 279 size_ = 0u; |
278 } | 280 } |
279 | 281 |
280 // Returns the number of priorities the queue supports. | 282 // Returns the number of priorities the queue supports. |
281 size_t num_priorities() const { | 283 size_t num_priorities() const { |
282 DCHECK(CalledOnValidThread()); | 284 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
283 return lists_.size(); | 285 return lists_.size(); |
284 } | 286 } |
285 | 287 |
286 bool empty() const { | 288 bool empty() const { |
287 DCHECK(CalledOnValidThread()); | 289 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
288 return size_ == 0; | 290 return size_ == 0; |
289 } | 291 } |
290 | 292 |
291 // Returns number of queued values. | 293 // Returns number of queued values. |
292 size_t size() const { | 294 size_t size() const { |
293 DCHECK(CalledOnValidThread()); | 295 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); |
294 return size_; | 296 return size_; |
295 } | 297 } |
296 | 298 |
297 private: | 299 private: |
298 typedef std::vector<List> ListVector; | 300 typedef std::vector<List> ListVector; |
299 | 301 |
300 #if !defined(NDEBUG) | 302 #if !defined(NDEBUG) |
301 unsigned next_id_; | 303 unsigned next_id_; |
302 std::unordered_set<unsigned> valid_ids_; | 304 std::unordered_set<unsigned> valid_ids_; |
303 #endif | 305 #endif |
304 | 306 |
305 ListVector lists_; | 307 ListVector lists_; |
306 size_t size_; | 308 size_t size_; |
307 | 309 |
| 310 THREAD_CHECKER(thread_checker_); |
| 311 |
308 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); | 312 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); |
309 }; | 313 }; |
310 | 314 |
311 } // namespace net | 315 } // namespace net |
312 | 316 |
313 #endif // NET_BASE_PRIORITY_QUEUE_H_ | 317 #endif // NET_BASE_PRIORITY_QUEUE_H_ |
OLD | NEW |