Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(231)

Side by Side Diff: net/base/priority_queue.h

Issue 266243004: Clang format slam. Base URL: svn://svn.chromium.org/chrome/trunk/src
Patch Set: Created 6 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
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
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
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
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
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_
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698