| 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 #pragma once | 7 #pragma once |
| 8 | 8 |
| 9 #include <list> | 9 #include <list> |
| 10 #include <vector> | 10 #include <vector> |
| (...skipping 16 matching lines...) Expand all Loading... |
| 27 // If the highest priority is 0, FirstMin() returns the first in order. | 27 // If the highest priority is 0, FirstMin() returns the first in order. |
| 28 // | 28 // |
| 29 // In debug-mode, the internal queues store (id, value) pairs where id is used | 29 // In debug-mode, the internal queues store (id, value) pairs where id is used |
| 30 // to validate Pointers. | 30 // to validate Pointers. |
| 31 // | 31 // |
| 32 template<typename T> | 32 template<typename T> |
| 33 class PriorityQueue : public base::NonThreadSafe { | 33 class PriorityQueue : public base::NonThreadSafe { |
| 34 private: | 34 private: |
| 35 // This section is up-front for Pointer only. | 35 // This section is up-front for Pointer only. |
| 36 #if !defined(NDEBUG) | 36 #if !defined(NDEBUG) |
| 37 typedef std::list<std::pair<size_t, T> > List; | 37 typedef std::list<std::pair<unsigned, T> > List; |
| 38 #else | 38 #else |
| 39 typedef std::list<T> List; | 39 typedef std::list<T> List; |
| 40 #endif | 40 #endif |
| 41 | 41 |
| 42 public: | 42 public: |
| 43 typedef uint32 Priority; | 43 typedef uint32 Priority; |
| 44 | 44 |
| 45 // A pointer to a value stored in the queue. The pointer becomes invalid | 45 // A pointer to a value stored in the queue. The pointer becomes invalid |
| 46 // when the queue is destroyed or cleared, or the value is erased. | 46 // when the queue is destroyed or cleared, or the value is erased. |
| 47 class Pointer { | 47 class Pointer { |
| 48 public: | 48 public: |
| 49 // Constructs a null pointer. | 49 // Constructs a null pointer. |
| 50 Pointer() : priority_(kNullPriority) { | 50 Pointer() : priority_(kNullPriority) { |
| 51 #if !defined(NDEBUG) | 51 #if !defined(NDEBUG) |
| 52 id_ = static_cast<size_t>(-1); | 52 id_ = static_cast<unsigned>(-1); |
| 53 #endif | 53 #endif |
| 54 } | 54 } |
| 55 | 55 |
| 56 Pointer(const Pointer& p) : priority_(p.priority_), iterator_(p.iterator_) { |
| 57 #if !defined(NDEBUG) |
| 58 id_ = p.id_; |
| 59 #endif |
| 60 } |
| 61 |
| 62 Pointer& operator=(const Pointer& p) { |
| 63 // Self-assignment is benign. |
| 64 priority_ = p.priority_; |
| 65 iterator_ = p.iterator_; |
| 66 #if !defined(NDEBUG) |
| 67 id_ = p.id_; |
| 68 #endif |
| 69 return *this; |
| 70 } |
| 71 |
| 56 bool is_null() const { return priority_ == kNullPriority; } | 72 bool is_null() const { return priority_ == kNullPriority; } |
| 57 | 73 |
| 58 Priority priority() const { return priority_; } | 74 Priority priority() const { return priority_; } |
| 59 | 75 |
| 60 #if !defined(NDEBUG) | 76 #if !defined(NDEBUG) |
| 61 const T& value() const { return iterator_->second; } | 77 const T& value() const { return iterator_->second; } |
| 62 #else | 78 #else |
| 63 const T& value() const { return *iterator_; } | 79 const T& value() const { return *iterator_; } |
| 64 #endif | 80 #endif |
| 65 | 81 |
| (...skipping 21 matching lines...) Expand all Loading... |
| 87 #if !defined(NDEBUG) | 103 #if !defined(NDEBUG) |
| 88 id_ = iterator_->first; | 104 id_ = iterator_->first; |
| 89 #endif | 105 #endif |
| 90 } | 106 } |
| 91 | 107 |
| 92 Priority priority_; | 108 Priority priority_; |
| 93 ListIterator iterator_; | 109 ListIterator iterator_; |
| 94 | 110 |
| 95 #if !defined(NDEBUG) | 111 #if !defined(NDEBUG) |
| 96 // Used by the queue to check if a Pointer is valid. | 112 // Used by the queue to check if a Pointer is valid. |
| 97 size_t id_; | 113 unsigned id_; |
| 98 #endif | 114 #endif |
| 99 }; | 115 }; |
| 100 | 116 |
| 101 // Creates a new queue for |num_priorities|. | 117 // Creates a new queue for |num_priorities|. |
| 102 explicit PriorityQueue(Priority num_priorities) | 118 explicit PriorityQueue(Priority num_priorities) |
| 103 : lists_(num_priorities), size_(0) { | 119 : lists_(num_priorities), size_(0) { |
| 104 #if !defined(NDEBUG) | 120 #if !defined(NDEBUG) |
| 105 next_id_ = 0; | 121 next_id_ = 0; |
| 106 #endif | 122 #endif |
| 107 } | 123 } |
| 108 | 124 |
| 109 // Adds |value| with |priority| to the queue. Returns a pointer to the | 125 // Adds |value| with |priority| to the queue. Returns a pointer to the |
| 110 // created element. | 126 // created element. |
| 111 Pointer Insert(const T& value, Priority priority) { | 127 Pointer Insert(const T& value, Priority priority) { |
| 112 DCHECK(CalledOnValidThread()); | 128 DCHECK(CalledOnValidThread()); |
| 113 DCHECK_LT(priority, lists_.size()); | 129 DCHECK_LT(priority, lists_.size()); |
| 114 ++size_; | 130 ++size_; |
| 115 List& list = lists_[priority]; | 131 List& list = lists_[priority]; |
| 116 #if !defined(NDEBUG) | 132 #if !defined(NDEBUG) |
| 117 size_t id = next_id_; | 133 unsigned id = next_id_; |
| 118 valid_ids_.insert(id); | 134 valid_ids_.insert(id); |
| 119 ++next_id_; | 135 ++next_id_; |
| 120 return Pointer(priority, list.insert(list.end(), | 136 return Pointer(priority, list.insert(list.end(), |
| 121 std::make_pair(id, value))); | 137 std::make_pair(id, value))); |
| 122 #else | 138 #else |
| 123 return Pointer(priority, list.insert(list.end(), value)); | 139 return Pointer(priority, list.insert(list.end(), value)); |
| 124 #endif | 140 #endif |
| 125 } | 141 } |
| 126 | 142 |
| 127 // Removes the value pointed by |pointer| from the queue. All pointers to this | 143 // Removes the value pointed by |pointer| from the queue. All pointers to this |
| (...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 201 // Returns number of queued values. | 217 // Returns number of queued values. |
| 202 size_t size() const { | 218 size_t size() const { |
| 203 DCHECK(CalledOnValidThread()); | 219 DCHECK(CalledOnValidThread()); |
| 204 return size_; | 220 return size_; |
| 205 } | 221 } |
| 206 | 222 |
| 207 private: | 223 private: |
| 208 typedef std::vector<List> ListVector; | 224 typedef std::vector<List> ListVector; |
| 209 | 225 |
| 210 #if !defined(NDEBUG) | 226 #if !defined(NDEBUG) |
| 211 size_t next_id_; | 227 unsigned next_id_; |
| 212 base::hash_set<size_t> valid_ids_; | 228 base::hash_set<unsigned> valid_ids_; |
| 213 #endif | 229 #endif |
| 214 | 230 |
| 215 ListVector lists_; | 231 ListVector lists_; |
| 216 size_t size_; | 232 size_t size_; |
| 233 |
| 234 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); |
| 217 }; | 235 }; |
| 218 | 236 |
| 219 } // namespace net | 237 } // namespace net |
| 220 | 238 |
| 221 #endif // NET_BASE_PRIORITY_QUEUE_H_ | 239 #endif // NET_BASE_PRIORITY_QUEUE_H_ |
| 222 | |
| OLD | NEW |