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 |