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 121 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
132 unsigned id = next_id_; | 132 unsigned id = next_id_; |
133 valid_ids_.insert(id); | 133 valid_ids_.insert(id); |
134 ++next_id_; | 134 ++next_id_; |
135 return Pointer(priority, list.insert(list.end(), | 135 return Pointer(priority, list.insert(list.end(), |
136 std::make_pair(id, value))); | 136 std::make_pair(id, value))); |
137 #else | 137 #else |
138 return Pointer(priority, list.insert(list.end(), value)); | 138 return Pointer(priority, list.insert(list.end(), value)); |
139 #endif | 139 #endif |
140 } | 140 } |
141 | 141 |
142 // Adds |value| with |priority| to the queue. Returns a pointer to the | |
143 // created element. | |
144 Pointer InsertAtFront(const T& value, Priority priority) { | |
145 DCHECK(CalledOnValidThread()); | |
146 DCHECK_LT(priority, lists_.size()); | |
147 ++size_; | |
148 List& list = lists_[priority]; | |
149 #if !defined(NDEBUG) | |
150 unsigned id = next_id_; | |
151 valid_ids_.insert(id); | |
152 ++next_id_; | |
153 return Pointer(priority, list.insert(list.begin(), | |
154 std::make_pair(id, value))); | |
155 #else | |
156 return Pointer(priority, list.insert(list.begin(), value)); | |
157 #endif | |
158 } | |
159 | |
160 // Removes the value pointed by |pointer| from the queue. All pointers to this | 142 // Removes the value pointed by |pointer| from the queue. All pointers to this |
161 // value including |pointer| become invalid. | 143 // value including |pointer| become invalid. |
162 void Erase(const Pointer& pointer) { | 144 void Erase(const Pointer& pointer) { |
163 DCHECK(CalledOnValidThread()); | 145 DCHECK(CalledOnValidThread()); |
164 DCHECK_LT(pointer.priority_, lists_.size()); | 146 DCHECK_LT(pointer.priority_, lists_.size()); |
165 DCHECK_GT(size_, 0u); | 147 DCHECK_GT(size_, 0u); |
166 | 148 |
167 #if !defined(NDEBUG) | 149 #if !defined(NDEBUG) |
168 DCHECK_EQ(1u, valid_ids_.erase(pointer.id_)); | 150 DCHECK_EQ(1u, valid_ids_.erase(pointer.id_)); |
169 DCHECK_EQ(pointer.iterator_->first, pointer.id_); | 151 DCHECK_EQ(pointer.iterator_->first, pointer.id_); |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
224 DCHECK(CalledOnValidThread()); | 206 DCHECK(CalledOnValidThread()); |
225 for (size_t i = 0; i < lists_.size(); ++i) { | 207 for (size_t i = 0; i < lists_.size(); ++i) { |
226 lists_[i].clear(); | 208 lists_[i].clear(); |
227 } | 209 } |
228 #if !defined(NDEBUG) | 210 #if !defined(NDEBUG) |
229 valid_ids_.clear(); | 211 valid_ids_.clear(); |
230 #endif | 212 #endif |
231 size_ = 0u; | 213 size_ = 0u; |
232 } | 214 } |
233 | 215 |
234 // Returns the number of priorities the queue supports. | |
235 size_t num_priorities() const { return lists_.size(); } | |
236 | |
237 // Returns number of queued values. | 216 // Returns number of queued values. |
238 size_t size() const { | 217 size_t size() const { |
239 DCHECK(CalledOnValidThread()); | 218 DCHECK(CalledOnValidThread()); |
240 return size_; | 219 return size_; |
241 } | 220 } |
242 | 221 |
243 private: | 222 private: |
244 typedef std::vector<List> ListVector; | 223 typedef std::vector<List> ListVector; |
245 | 224 |
246 #if !defined(NDEBUG) | 225 #if !defined(NDEBUG) |
247 unsigned next_id_; | 226 unsigned next_id_; |
248 base::hash_set<unsigned> valid_ids_; | 227 base::hash_set<unsigned> valid_ids_; |
249 #endif | 228 #endif |
250 | 229 |
251 ListVector lists_; | 230 ListVector lists_; |
252 size_t size_; | 231 size_t size_; |
253 | 232 |
254 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); | 233 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); |
255 }; | 234 }; |
256 | 235 |
257 } // namespace net | 236 } // namespace net |
258 | 237 |
259 #endif // NET_BASE_PRIORITY_QUEUE_H_ | 238 #endif // NET_BASE_PRIORITY_QUEUE_H_ |
OLD | NEW |