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

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

Issue 9924023: Readability review (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src
Patch Set: Add copy constructor and assignment operator to Pointer. Created 8 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 #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
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
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
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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698