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

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

Issue 2910473005: Deprecate NonThreadSafe in net/ in favor of SequenceChecker/ThreadChecker. (Closed)
Patch Set: rebase on r476634 Created 3 years, 6 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
« no previous file with comments | « net/base/network_delegate.cc ('k') | net/cert/multi_threaded_cert_verifier.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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 <stddef.h> 8 #include <stddef.h>
9 #include <stdint.h> 9 #include <stdint.h>
10 10
11 #include <list> 11 #include <list>
12 #include <vector> 12 #include <vector>
13 13
14 #include "base/logging.h" 14 #include "base/logging.h"
15 #include "base/macros.h" 15 #include "base/macros.h"
16 #include "base/threading/non_thread_safe.h" 16 #include "base/threading/thread_checker.h"
17 17
18 #if !defined(NDEBUG) 18 #if !defined(NDEBUG)
19 #include <unordered_set> 19 #include <unordered_set>
20 #endif 20 #endif
21 21
22 namespace net { 22 namespace net {
23 23
24 // A simple priority queue. The order of values is by priority and then FIFO. 24 // A simple priority queue. The order of values is by priority and then FIFO.
25 // Unlike the std::priority_queue, this implementation allows erasing elements 25 // Unlike the std::priority_queue, this implementation allows erasing elements
26 // from the queue, and all operations are O(p) time for p priority levels. 26 // from the queue, and all operations are O(p) time for p priority levels.
27 // The queue is agnostic to priority ordering (whether 0 precedes 1). 27 // The queue is agnostic to priority ordering (whether 0 precedes 1).
28 // If the highest priority is 0, FirstMin() returns the first in order. 28 // If the highest priority is 0, FirstMin() returns the first in order.
29 // 29 //
30 // In debug-mode, the internal queues store (id, value) pairs where id is used 30 // In debug-mode, the internal queues store (id, value) pairs where id is used
31 // to validate Pointers. 31 // to validate Pointers.
32 // 32 //
33 template<typename T> 33 template <typename T>
34 class PriorityQueue : public base::NonThreadSafe { 34 class PriorityQueue {
35 private: 35 private:
36 // This section is up-front for Pointer only. 36 // This section is up-front for Pointer only.
37 #if !defined(NDEBUG) 37 #if !defined(NDEBUG)
38 typedef std::list<std::pair<unsigned, T> > List; 38 typedef std::list<std::pair<unsigned, T> > List;
39 #else 39 #else
40 typedef std::list<T> List; 40 typedef std::list<T> List;
41 #endif 41 #endif
42 42
43 public: 43 public:
44 typedef uint32_t Priority; 44 typedef uint32_t Priority;
(...skipping 85 matching lines...) Expand 10 before | Expand all | Expand 10 after
130 }; 130 };
131 131
132 // Creates a new queue for |num_priorities|. 132 // Creates a new queue for |num_priorities|.
133 explicit PriorityQueue(Priority num_priorities) 133 explicit PriorityQueue(Priority num_priorities)
134 : lists_(num_priorities), size_(0) { 134 : lists_(num_priorities), size_(0) {
135 #if !defined(NDEBUG) 135 #if !defined(NDEBUG)
136 next_id_ = 0; 136 next_id_ = 0;
137 #endif 137 #endif
138 } 138 }
139 139
140 ~PriorityQueue() { DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); }
141
140 // Adds |value| with |priority| to the queue. Returns a pointer to the 142 // Adds |value| with |priority| to the queue. Returns a pointer to the
141 // created element. 143 // created element.
142 Pointer Insert(const T& value, Priority priority) { 144 Pointer Insert(const T& value, Priority priority) {
143 DCHECK(CalledOnValidThread()); 145 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
144 DCHECK_LT(priority, lists_.size()); 146 DCHECK_LT(priority, lists_.size());
145 ++size_; 147 ++size_;
146 List& list = lists_[priority]; 148 List& list = lists_[priority];
147 #if !defined(NDEBUG) 149 #if !defined(NDEBUG)
148 unsigned id = next_id_; 150 unsigned id = next_id_;
149 valid_ids_.insert(id); 151 valid_ids_.insert(id);
150 ++next_id_; 152 ++next_id_;
151 return Pointer(priority, list.insert(list.end(), 153 return Pointer(priority, list.insert(list.end(),
152 std::make_pair(id, value))); 154 std::make_pair(id, value)));
153 #else 155 #else
154 return Pointer(priority, list.insert(list.end(), value)); 156 return Pointer(priority, list.insert(list.end(), value));
155 #endif 157 #endif
156 } 158 }
157 159
158 // Adds |value| with |priority| to the queue. Returns a pointer to the 160 // Adds |value| with |priority| to the queue. Returns a pointer to the
159 // created element. 161 // created element.
160 Pointer InsertAtFront(const T& value, Priority priority) { 162 Pointer InsertAtFront(const T& value, Priority priority) {
161 DCHECK(CalledOnValidThread()); 163 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
162 DCHECK_LT(priority, lists_.size()); 164 DCHECK_LT(priority, lists_.size());
163 ++size_; 165 ++size_;
164 List& list = lists_[priority]; 166 List& list = lists_[priority];
165 #if !defined(NDEBUG) 167 #if !defined(NDEBUG)
166 unsigned id = next_id_; 168 unsigned id = next_id_;
167 valid_ids_.insert(id); 169 valid_ids_.insert(id);
168 ++next_id_; 170 ++next_id_;
169 return Pointer(priority, list.insert(list.begin(), 171 return Pointer(priority, list.insert(list.begin(),
170 std::make_pair(id, value))); 172 std::make_pair(id, value)));
171 #else 173 #else
172 return Pointer(priority, list.insert(list.begin(), value)); 174 return Pointer(priority, list.insert(list.begin(), value));
173 #endif 175 #endif
174 } 176 }
175 177
176 // Removes the value pointed by |pointer| from the queue. All pointers to this 178 // Removes the value pointed by |pointer| from the queue. All pointers to this
177 // value including |pointer| become invalid. 179 // value including |pointer| become invalid.
178 void Erase(const Pointer& pointer) { 180 void Erase(const Pointer& pointer) {
179 DCHECK(CalledOnValidThread()); 181 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
180 DCHECK_LT(pointer.priority_, lists_.size()); 182 DCHECK_LT(pointer.priority_, lists_.size());
181 DCHECK_GT(size_, 0u); 183 DCHECK_GT(size_, 0u);
182 184
183 #if !defined(NDEBUG) 185 #if !defined(NDEBUG)
184 DCHECK_EQ(1u, valid_ids_.erase(pointer.id_)); 186 DCHECK_EQ(1u, valid_ids_.erase(pointer.id_));
185 DCHECK_EQ(pointer.iterator_->first, pointer.id_); 187 DCHECK_EQ(pointer.iterator_->first, pointer.id_);
186 #endif 188 #endif
187 189
188 --size_; 190 --size_;
189 lists_[pointer.priority_].erase(pointer.iterator_); 191 lists_[pointer.priority_].erase(pointer.iterator_);
190 } 192 }
191 193
192 // Returns a pointer to the first value of minimum priority or a null-pointer 194 // Returns a pointer to the first value of minimum priority or a null-pointer
193 // if empty. 195 // if empty.
194 Pointer FirstMin() const { 196 Pointer FirstMin() const {
195 DCHECK(CalledOnValidThread()); 197 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
196 for (size_t i = 0; i < lists_.size(); ++i) { 198 for (size_t i = 0; i < lists_.size(); ++i) {
197 List* list = const_cast<List*>(&lists_[i]); 199 List* list = const_cast<List*>(&lists_[i]);
198 if (!list->empty()) 200 if (!list->empty())
199 return Pointer(i, list->begin()); 201 return Pointer(i, list->begin());
200 } 202 }
201 return Pointer(); 203 return Pointer();
202 } 204 }
203 205
204 // Returns a pointer to the last value of minimum priority or a null-pointer 206 // Returns a pointer to the last value of minimum priority or a null-pointer
205 // if empty. 207 // if empty.
206 Pointer LastMin() const { 208 Pointer LastMin() const {
207 DCHECK(CalledOnValidThread()); 209 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
208 for (size_t i = 0; i < lists_.size(); ++i) { 210 for (size_t i = 0; i < lists_.size(); ++i) {
209 List* list = const_cast<List*>(&lists_[i]); 211 List* list = const_cast<List*>(&lists_[i]);
210 if (!list->empty()) 212 if (!list->empty())
211 return Pointer(i, --list->end()); 213 return Pointer(i, --list->end());
212 } 214 }
213 return Pointer(); 215 return Pointer();
214 } 216 }
215 217
216 // Returns a pointer to the first value of maximum priority or a null-pointer 218 // Returns a pointer to the first value of maximum priority or a null-pointer
217 // if empty. 219 // if empty.
218 Pointer FirstMax() const { 220 Pointer FirstMax() const {
219 DCHECK(CalledOnValidThread()); 221 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
220 for (size_t i = lists_.size(); i > 0; --i) { 222 for (size_t i = lists_.size(); i > 0; --i) {
221 size_t index = i - 1; 223 size_t index = i - 1;
222 List* list = const_cast<List*>(&lists_[index]); 224 List* list = const_cast<List*>(&lists_[index]);
223 if (!list->empty()) 225 if (!list->empty())
224 return Pointer(index, list->begin()); 226 return Pointer(index, list->begin());
225 } 227 }
226 return Pointer(); 228 return Pointer();
227 } 229 }
228 230
229 // Returns a pointer to the last value of maximum priority or a null-pointer 231 // Returns a pointer to the last value of maximum priority or a null-pointer
230 // if empty. 232 // if empty.
231 Pointer LastMax() const { 233 Pointer LastMax() const {
232 DCHECK(CalledOnValidThread()); 234 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
233 for (size_t i = lists_.size(); i > 0; --i) { 235 for (size_t i = lists_.size(); i > 0; --i) {
234 size_t index = i - 1; 236 size_t index = i - 1;
235 List* list = const_cast<List*>(&lists_[index]); 237 List* list = const_cast<List*>(&lists_[index]);
236 if (!list->empty()) 238 if (!list->empty())
237 return Pointer(index, --list->end()); 239 return Pointer(index, --list->end());
238 } 240 }
239 return Pointer(); 241 return Pointer();
240 } 242 }
241 243
242 // Given an ordering of the values in this queue by decreasing 244 // Given an ordering of the values in this queue by decreasing
243 // priority and then FIFO, returns a pointer to the value following 245 // priority and then FIFO, returns a pointer to the value following
244 // the value of the given pointer (which must be non-NULL). 246 // the value of the given pointer (which must be non-NULL).
245 // 247 //
246 // (One could also implement GetNextTowardsFirstMin() [decreasing 248 // (One could also implement GetNextTowardsFirstMin() [decreasing
247 // priority, then reverse FIFO] as well as 249 // priority, then reverse FIFO] as well as
248 // GetNextTowards{First,Last}Max() [increasing priority, then 250 // GetNextTowards{First,Last}Max() [increasing priority, then
249 // {,reverse} FIFO].) 251 // {,reverse} FIFO].)
250 Pointer GetNextTowardsLastMin(const Pointer& pointer) const { 252 Pointer GetNextTowardsLastMin(const Pointer& pointer) const {
251 DCHECK(CalledOnValidThread()); 253 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
252 DCHECK(!pointer.is_null()); 254 DCHECK(!pointer.is_null());
253 DCHECK_LT(pointer.priority_, lists_.size()); 255 DCHECK_LT(pointer.priority_, lists_.size());
254 256
255 typename Pointer::ListIterator it = pointer.iterator_; 257 typename Pointer::ListIterator it = pointer.iterator_;
256 Priority priority = pointer.priority_; 258 Priority priority = pointer.priority_;
257 DCHECK(it != lists_[priority].end()); 259 DCHECK(it != lists_[priority].end());
258 ++it; 260 ++it;
259 while (it == lists_[priority].end()) { 261 while (it == lists_[priority].end()) {
260 if (priority == 0u) 262 if (priority == 0u)
261 return Pointer(); 263 return Pointer();
262 --priority; 264 --priority;
263 it = const_cast<List*>(&lists_[priority])->begin(); 265 it = const_cast<List*>(&lists_[priority])->begin();
264 } 266 }
265 return Pointer(priority, it); 267 return Pointer(priority, it);
266 } 268 }
267 269
268 // Empties the queue. All pointers become invalid. 270 // Empties the queue. All pointers become invalid.
269 void Clear() { 271 void Clear() {
270 DCHECK(CalledOnValidThread()); 272 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
271 for (size_t i = 0; i < lists_.size(); ++i) { 273 for (size_t i = 0; i < lists_.size(); ++i) {
272 lists_[i].clear(); 274 lists_[i].clear();
273 } 275 }
274 #if !defined(NDEBUG) 276 #if !defined(NDEBUG)
275 valid_ids_.clear(); 277 valid_ids_.clear();
276 #endif 278 #endif
277 size_ = 0u; 279 size_ = 0u;
278 } 280 }
279 281
280 // Returns the number of priorities the queue supports. 282 // Returns the number of priorities the queue supports.
281 size_t num_priorities() const { 283 size_t num_priorities() const {
282 DCHECK(CalledOnValidThread()); 284 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
283 return lists_.size(); 285 return lists_.size();
284 } 286 }
285 287
286 bool empty() const { 288 bool empty() const {
287 DCHECK(CalledOnValidThread()); 289 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
288 return size_ == 0; 290 return size_ == 0;
289 } 291 }
290 292
291 // Returns number of queued values. 293 // Returns number of queued values.
292 size_t size() const { 294 size_t size() const {
293 DCHECK(CalledOnValidThread()); 295 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
294 return size_; 296 return size_;
295 } 297 }
296 298
297 private: 299 private:
298 typedef std::vector<List> ListVector; 300 typedef std::vector<List> ListVector;
299 301
300 #if !defined(NDEBUG) 302 #if !defined(NDEBUG)
301 unsigned next_id_; 303 unsigned next_id_;
302 std::unordered_set<unsigned> valid_ids_; 304 std::unordered_set<unsigned> valid_ids_;
303 #endif 305 #endif
304 306
305 ListVector lists_; 307 ListVector lists_;
306 size_t size_; 308 size_t size_;
307 309
310 THREAD_CHECKER(thread_checker_);
311
308 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); 312 DISALLOW_COPY_AND_ASSIGN(PriorityQueue);
309 }; 313 };
310 314
311 } // namespace net 315 } // namespace net
312 316
313 #endif // NET_BASE_PRIORITY_QUEUE_H_ 317 #endif // NET_BASE_PRIORITY_QUEUE_H_
OLDNEW
« no previous file with comments | « net/base/network_delegate.cc ('k') | net/cert/multi_threaded_cert_verifier.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698