Chromium Code Reviews| 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 priority_ = p.priority_; | |
|
stevez
2012/05/30 17:12:45
You may want to check for self-assignment.
szym
2012/05/30 23:53:24
Self-assignment is benign. Added comment.
| |
| 64 iterator_ = p.iterator_; | |
| 65 #if !defined(NDEBUG) | |
| 66 id_ = p.id_; | |
| 67 #endif | |
| 68 return *this; | |
| 69 } | |
| 70 | |
| 56 bool is_null() const { return priority_ == kNullPriority; } | 71 bool is_null() const { return priority_ == kNullPriority; } |
| 57 | 72 |
| 58 Priority priority() const { return priority_; } | 73 Priority priority() const { return priority_; } |
| 59 | 74 |
| 60 #if !defined(NDEBUG) | 75 #if !defined(NDEBUG) |
| 61 const T& value() const { return iterator_->second; } | 76 const T& value() const { return iterator_->second; } |
| 62 #else | 77 #else |
| 63 const T& value() const { return *iterator_; } | 78 const T& value() const { return *iterator_; } |
| 64 #endif | 79 #endif |
| 65 | 80 |
| (...skipping 21 matching lines...) Expand all Loading... | |
| 87 #if !defined(NDEBUG) | 102 #if !defined(NDEBUG) |
| 88 id_ = iterator_->first; | 103 id_ = iterator_->first; |
| 89 #endif | 104 #endif |
| 90 } | 105 } |
| 91 | 106 |
| 92 Priority priority_; | 107 Priority priority_; |
| 93 ListIterator iterator_; | 108 ListIterator iterator_; |
| 94 | 109 |
| 95 #if !defined(NDEBUG) | 110 #if !defined(NDEBUG) |
| 96 // Used by the queue to check if a Pointer is valid. | 111 // Used by the queue to check if a Pointer is valid. |
| 97 size_t id_; | 112 unsigned id_; |
| 98 #endif | 113 #endif |
| 99 }; | 114 }; |
| 100 | 115 |
| 101 // Creates a new queue for |num_priorities|. | 116 // Creates a new queue for |num_priorities|. |
| 102 explicit PriorityQueue(Priority num_priorities) | 117 explicit PriorityQueue(Priority num_priorities) |
| 103 : lists_(num_priorities), size_(0) { | 118 : lists_(num_priorities), size_(0) { |
| 104 #if !defined(NDEBUG) | 119 #if !defined(NDEBUG) |
| 105 next_id_ = 0; | 120 next_id_ = 0; |
| 106 #endif | 121 #endif |
| 107 } | 122 } |
| 108 | 123 |
| 109 // Adds |value| with |priority| to the queue. Returns a pointer to the | 124 // Adds |value| with |priority| to the queue. Returns a pointer to the |
| 110 // created element. | 125 // created element. |
| 111 Pointer Insert(const T& value, Priority priority) { | 126 Pointer Insert(const T& value, Priority priority) { |
| 112 DCHECK(CalledOnValidThread()); | 127 DCHECK(CalledOnValidThread()); |
| 113 DCHECK_LT(priority, lists_.size()); | 128 DCHECK_LT(priority, lists_.size()); |
| 114 ++size_; | 129 ++size_; |
| 115 List& list = lists_[priority]; | 130 List& list = lists_[priority]; |
| 116 #if !defined(NDEBUG) | 131 #if !defined(NDEBUG) |
| 117 size_t id = next_id_; | 132 unsigned id = next_id_; |
| 118 valid_ids_.insert(id); | 133 valid_ids_.insert(id); |
| 119 ++next_id_; | 134 ++next_id_; |
| 120 return Pointer(priority, list.insert(list.end(), | 135 return Pointer(priority, list.insert(list.end(), |
| 121 std::make_pair(id, value))); | 136 std::make_pair(id, value))); |
| 122 #else | 137 #else |
| 123 return Pointer(priority, list.insert(list.end(), value)); | 138 return Pointer(priority, list.insert(list.end(), value)); |
| 124 #endif | 139 #endif |
| 125 } | 140 } |
| 126 | 141 |
| 127 // 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 |
| (...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 201 // Returns number of queued values. | 216 // Returns number of queued values. |
| 202 size_t size() const { | 217 size_t size() const { |
| 203 DCHECK(CalledOnValidThread()); | 218 DCHECK(CalledOnValidThread()); |
| 204 return size_; | 219 return size_; |
| 205 } | 220 } |
| 206 | 221 |
| 207 private: | 222 private: |
| 208 typedef std::vector<List> ListVector; | 223 typedef std::vector<List> ListVector; |
| 209 | 224 |
| 210 #if !defined(NDEBUG) | 225 #if !defined(NDEBUG) |
| 211 size_t next_id_; | 226 unsigned next_id_; |
| 212 base::hash_set<size_t> valid_ids_; | 227 base::hash_set<unsigned> valid_ids_; |
| 213 #endif | 228 #endif |
| 214 | 229 |
| 215 ListVector lists_; | 230 ListVector lists_; |
| 216 size_t size_; | 231 size_t size_; |
| 232 | |
| 233 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); | |
| 217 }; | 234 }; |
| 218 | 235 |
| 219 } // namespace net | 236 } // namespace net |
| 220 | 237 |
| 221 #endif // NET_BASE_PRIORITY_QUEUE_H_ | 238 #endif // NET_BASE_PRIORITY_QUEUE_H_ |
| 222 | 239 |
| 240 | |
| OLD | NEW |