| 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 <list> | 8 #include <list> |
| 9 #include <vector> | 9 #include <vector> |
| 10 | 10 |
| (...skipping 10 matching lines...) Expand all Loading... |
| 21 | 21 |
| 22 // A simple priority queue. The order of values is by priority and then FIFO. | 22 // A simple priority queue. The order of values is by priority and then FIFO. |
| 23 // Unlike the std::priority_queue, this implementation allows erasing elements | 23 // Unlike the std::priority_queue, this implementation allows erasing elements |
| 24 // from the queue, and all operations are O(p) time for p priority levels. | 24 // from the queue, and all operations are O(p) time for p priority levels. |
| 25 // The queue is agnostic to priority ordering (whether 0 precedes 1). | 25 // The queue is agnostic to priority ordering (whether 0 precedes 1). |
| 26 // If the highest priority is 0, FirstMin() returns the first in order. | 26 // If the highest priority is 0, FirstMin() returns the first in order. |
| 27 // | 27 // |
| 28 // In debug-mode, the internal queues store (id, value) pairs where id is used | 28 // In debug-mode, the internal queues store (id, value) pairs where id is used |
| 29 // to validate Pointers. | 29 // to validate Pointers. |
| 30 // | 30 // |
| 31 template<typename T> | 31 template <typename T> |
| 32 class PriorityQueue : public base::NonThreadSafe { | 32 class PriorityQueue : public base::NonThreadSafe { |
| 33 private: | 33 private: |
| 34 // This section is up-front for Pointer only. | 34 // This section is up-front for Pointer only. |
| 35 #if !defined(NDEBUG) | 35 #if !defined(NDEBUG) |
| 36 typedef std::list<std::pair<unsigned, T> > List; | 36 typedef std::list<std::pair<unsigned, T> > List; |
| 37 #else | 37 #else |
| 38 typedef std::list<T> List; | 38 typedef std::list<T> List; |
| 39 #endif | 39 #endif |
| 40 | 40 |
| 41 public: | 41 public: |
| 42 typedef uint32 Priority; | 42 typedef uint32 Priority; |
| 43 | 43 |
| 44 // A pointer to a value stored in the queue. The pointer becomes invalid | 44 // A pointer to a value stored in the queue. The pointer becomes invalid |
| 45 // when the queue is destroyed or cleared, or the value is erased. | 45 // when the queue is destroyed or cleared, or the value is erased. |
| 46 class Pointer { | 46 class Pointer { |
| 47 public: | 47 public: |
| 48 // Constructs a null pointer. | 48 // Constructs a null pointer. |
| 49 Pointer() : priority_(kNullPriority) { | 49 Pointer() : priority_(kNullPriority) { |
| 50 #if !defined(NDEBUG) | 50 #if !defined(NDEBUG) |
| 51 id_ = static_cast<unsigned>(-1); | 51 id_ = static_cast<unsigned>(-1); |
| 52 #endif | 52 #endif |
| 53 // TODO(syzm) | 53 // TODO(syzm) |
| 54 // An uninitialized iterator behaves like an uninitialized pointer as per | 54 // An uninitialized iterator behaves like an uninitialized pointer as per |
| 55 // the STL docs. The fix below is ugly and should possibly be replaced | 55 // the STL docs. The fix below is ugly and should possibly be replaced |
| 56 // with a better approach. | 56 // with a better approach. |
| 57 iterator_ = dummy_empty_list_.end(); | 57 iterator_ = dummy_empty_list_.end(); |
| 58 } | 58 } |
| 59 | 59 |
| 60 Pointer(const Pointer& p) | 60 Pointer(const Pointer& p) : priority_(p.priority_), iterator_(p.iterator_) { |
| 61 : priority_(p.priority_), | |
| 62 iterator_(p.iterator_) { | |
| 63 #if !defined(NDEBUG) | 61 #if !defined(NDEBUG) |
| 64 id_ = p.id_; | 62 id_ = p.id_; |
| 65 #endif | 63 #endif |
| 66 } | 64 } |
| 67 | 65 |
| 68 Pointer& operator=(const Pointer& p) { | 66 Pointer& operator=(const Pointer& p) { |
| 69 // Self-assignment is benign. | 67 // Self-assignment is benign. |
| 70 priority_ = p.priority_; | 68 priority_ = p.priority_; |
| 71 iterator_ = p.iterator_; | 69 iterator_ = p.iterator_; |
| 72 #if !defined(NDEBUG) | 70 #if !defined(NDEBUG) |
| (...skipping 10 matching lines...) Expand all Loading... |
| 83 const T& value() const { return iterator_->second; } | 81 const T& value() const { return iterator_->second; } |
| 84 #else | 82 #else |
| 85 const T& value() const { return *iterator_; } | 83 const T& value() const { return *iterator_; } |
| 86 #endif | 84 #endif |
| 87 | 85 |
| 88 // Comparing to Pointer from a different PriorityQueue is undefined. | 86 // Comparing to Pointer from a different PriorityQueue is undefined. |
| 89 bool Equals(const Pointer& other) const { | 87 bool Equals(const Pointer& other) const { |
| 90 return (priority_ == other.priority_) && (iterator_ == other.iterator_); | 88 return (priority_ == other.priority_) && (iterator_ == other.iterator_); |
| 91 } | 89 } |
| 92 | 90 |
| 93 void Reset() { | 91 void Reset() { *this = Pointer(); } |
| 94 *this = Pointer(); | |
| 95 } | |
| 96 | 92 |
| 97 private: | 93 private: |
| 98 friend class PriorityQueue; | 94 friend class PriorityQueue; |
| 99 | 95 |
| 100 // Note that we need iterator and not const_iterator to pass to | 96 // Note that we need iterator and not const_iterator to pass to |
| 101 // List::erase. When C++11 is turned on for Chromium, this could | 97 // List::erase. When C++11 is turned on for Chromium, this could |
| 102 // be changed to const_iterator and the const_casts in the rest of | 98 // be changed to const_iterator and the const_casts in the rest of |
| 103 // the file can be removed. | 99 // the file can be removed. |
| 104 typedef typename PriorityQueue::List::iterator ListIterator; | 100 typedef typename PriorityQueue::List::iterator ListIterator; |
| 105 | 101 |
| (...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 139 // created element. | 135 // created element. |
| 140 Pointer Insert(const T& value, Priority priority) { | 136 Pointer Insert(const T& value, Priority priority) { |
| 141 DCHECK(CalledOnValidThread()); | 137 DCHECK(CalledOnValidThread()); |
| 142 DCHECK_LT(priority, lists_.size()); | 138 DCHECK_LT(priority, lists_.size()); |
| 143 ++size_; | 139 ++size_; |
| 144 List& list = lists_[priority]; | 140 List& list = lists_[priority]; |
| 145 #if !defined(NDEBUG) | 141 #if !defined(NDEBUG) |
| 146 unsigned id = next_id_; | 142 unsigned id = next_id_; |
| 147 valid_ids_.insert(id); | 143 valid_ids_.insert(id); |
| 148 ++next_id_; | 144 ++next_id_; |
| 149 return Pointer(priority, list.insert(list.end(), | 145 return Pointer(priority, |
| 150 std::make_pair(id, value))); | 146 list.insert(list.end(), std::make_pair(id, value))); |
| 151 #else | 147 #else |
| 152 return Pointer(priority, list.insert(list.end(), value)); | 148 return Pointer(priority, list.insert(list.end(), value)); |
| 153 #endif | 149 #endif |
| 154 } | 150 } |
| 155 | 151 |
| 156 // Adds |value| with |priority| to the queue. Returns a pointer to the | 152 // Adds |value| with |priority| to the queue. Returns a pointer to the |
| 157 // created element. | 153 // created element. |
| 158 Pointer InsertAtFront(const T& value, Priority priority) { | 154 Pointer InsertAtFront(const T& value, Priority priority) { |
| 159 DCHECK(CalledOnValidThread()); | 155 DCHECK(CalledOnValidThread()); |
| 160 DCHECK_LT(priority, lists_.size()); | 156 DCHECK_LT(priority, lists_.size()); |
| 161 ++size_; | 157 ++size_; |
| 162 List& list = lists_[priority]; | 158 List& list = lists_[priority]; |
| 163 #if !defined(NDEBUG) | 159 #if !defined(NDEBUG) |
| 164 unsigned id = next_id_; | 160 unsigned id = next_id_; |
| 165 valid_ids_.insert(id); | 161 valid_ids_.insert(id); |
| 166 ++next_id_; | 162 ++next_id_; |
| 167 return Pointer(priority, list.insert(list.begin(), | 163 return Pointer(priority, |
| 168 std::make_pair(id, value))); | 164 list.insert(list.begin(), std::make_pair(id, value))); |
| 169 #else | 165 #else |
| 170 return Pointer(priority, list.insert(list.begin(), value)); | 166 return Pointer(priority, list.insert(list.begin(), value)); |
| 171 #endif | 167 #endif |
| 172 } | 168 } |
| 173 | 169 |
| 174 // Removes the value pointed by |pointer| from the queue. All pointers to this | 170 // Removes the value pointed by |pointer| from the queue. All pointers to this |
| 175 // value including |pointer| become invalid. | 171 // value including |pointer| become invalid. |
| 176 void Erase(const Pointer& pointer) { | 172 void Erase(const Pointer& pointer) { |
| 177 DCHECK(CalledOnValidThread()); | 173 DCHECK(CalledOnValidThread()); |
| 178 DCHECK_LT(pointer.priority_, lists_.size()); | 174 DCHECK_LT(pointer.priority_, lists_.size()); |
| (...skipping 123 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 302 | 298 |
| 303 ListVector lists_; | 299 ListVector lists_; |
| 304 size_t size_; | 300 size_t size_; |
| 305 | 301 |
| 306 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); | 302 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); |
| 307 }; | 303 }; |
| 308 | 304 |
| 309 } // namespace net | 305 } // namespace net |
| 310 | 306 |
| 311 #endif // NET_BASE_PRIORITY_QUEUE_H_ | 307 #endif // NET_BASE_PRIORITY_QUEUE_H_ |
| OLD | NEW |