| 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 |