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/non_thread_safe.h" |
17 #include "net/base/net_export.h" | 17 #include "net/base/net_export.h" |
18 | 18 |
19 #if !defined(NDEBUG) | 19 #if !defined(NDEBUG) |
20 #include <unordered_set> | 20 #include "base/containers/hash_tables.h" |
21 #endif | 21 #endif |
22 | 22 |
23 namespace net { | 23 namespace net { |
24 | 24 |
25 // A simple priority queue. The order of values is by priority and then FIFO. | 25 // A simple priority queue. The order of values is by priority and then FIFO. |
26 // Unlike the std::priority_queue, this implementation allows erasing elements | 26 // Unlike the std::priority_queue, this implementation allows erasing elements |
27 // from the queue, and all operations are O(p) time for p priority levels. | 27 // from the queue, and all operations are O(p) time for p priority levels. |
28 // The queue is agnostic to priority ordering (whether 0 precedes 1). | 28 // The queue is agnostic to priority ordering (whether 0 precedes 1). |
29 // If the highest priority is 0, FirstMin() returns the first in order. | 29 // If the highest priority is 0, FirstMin() returns the first in order. |
30 // | 30 // |
(...skipping 262 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
293 size_t size() const { | 293 size_t size() const { |
294 DCHECK(CalledOnValidThread()); | 294 DCHECK(CalledOnValidThread()); |
295 return size_; | 295 return size_; |
296 } | 296 } |
297 | 297 |
298 private: | 298 private: |
299 typedef std::vector<List> ListVector; | 299 typedef std::vector<List> ListVector; |
300 | 300 |
301 #if !defined(NDEBUG) | 301 #if !defined(NDEBUG) |
302 unsigned next_id_; | 302 unsigned next_id_; |
303 std::unordered_set<unsigned> valid_ids_; | 303 base::hash_set<unsigned> valid_ids_; |
304 #endif | 304 #endif |
305 | 305 |
306 ListVector lists_; | 306 ListVector lists_; |
307 size_t size_; | 307 size_t size_; |
308 | 308 |
309 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); | 309 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); |
310 }; | 310 }; |
311 | 311 |
312 } // namespace net | 312 } // namespace net |
313 | 313 |
314 #endif // NET_BASE_PRIORITY_QUEUE_H_ | 314 #endif // NET_BASE_PRIORITY_QUEUE_H_ |
OLD | NEW |