| 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 "base/containers/hash_tables.h" | 20 #include <unordered_set> |
| 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 base::hash_set<unsigned> valid_ids_; | 303 std::unordered_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 |