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 3// found in the LICENSE file. 4 5#ifndef NET_BASE_PRIORITY_QUEUE_H_ 6#define NET_BASE_PRIORITY_QUEUE_H_ 7 8#include <list> 9#include <vector> 10 11#include "base/basictypes.h" 12#include "base/logging.h" 13#include "base/threading/non_thread_safe.h" 14#include "net/base/net_export.h" 15 16#if !defined(NDEBUG) 17#include "base/containers/hash_tables.h" 18#endif 19 20namespace net { 21 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 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). 26// If the highest priority is 0, FirstMin() returns the first in order. 27// 28// In debug-mode, the internal queues store (id, value) pairs where id is used 29// to validate Pointers. 30// 31template<typename T> 32class PriorityQueue : public base::NonThreadSafe { 33 private: 34 // This section is up-front for Pointer only. 35#if !defined(NDEBUG) 36 typedef std::list<std::pair<unsigned, T> > List; 37#else 38 typedef std::list<T> List; 39#endif 40 41 public: 42 typedef uint32 Priority; 43 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. 46 class Pointer { 47 public: 48 // Constructs a null pointer. 49 Pointer() : priority_(kNullPriority) { 50#if !defined(NDEBUG) 51 id_ = static_cast<unsigned>(-1); 52#endif 53 } 54 55 Pointer(const Pointer& p) : priority_(p.priority_), iterator_(p.iterator_) { 56#if !defined(NDEBUG) 57 id_ = p.id_; 58#endif 59 } 60 61 Pointer& operator=(const Pointer& p) { 62 // Self-assignment is benign. 63 priority_ = p.priority_; 64 iterator_ = p.iterator_; 65#if !defined(NDEBUG) 66 id_ = p.id_; 67#endif 68 return *this; 69 } 70 71 bool is_null() const { return priority_ == kNullPriority; } 72 73 Priority priority() const { return priority_; } 74 75#if !defined(NDEBUG) 76 const T& value() const { return iterator_->second; } 77#else 78 const T& value() const { return *iterator_; } 79#endif 80 81 // Comparing to Pointer from a different PriorityQueue is undefined. 82 bool Equals(const Pointer& other) const { 83 return (priority_ == other.priority_) && (iterator_ == other.iterator_); 84 } 85 86 void Reset() { 87 *this = Pointer(); 88 } 89 90 private: 91 friend class PriorityQueue; 92 93 // Note that we need iterator not const_iterator to pass to List::erase. 94 // When C++0x comes, this could be changed to const_iterator and const could 95 // be added to First, Last, and OldestLowest. 96 typedef typename PriorityQueue::List::iterator ListIterator; 97 98 static const Priority kNullPriority = static_cast<Priority>(-1); 99 100 Pointer(Priority priority, const ListIterator& iterator) 101 : priority_(priority), iterator_(iterator) { 102#if !defined(NDEBUG) 103 id_ = iterator_->first; 104#endif 105 } 106 107 Priority priority_; 108 ListIterator iterator_; 109 110#if !defined(NDEBUG) 111 // Used by the queue to check if a Pointer is valid. 112 unsigned id_; 113#endif 114 }; 115 116 // Creates a new queue for |num_priorities|. 117 explicit PriorityQueue(Priority num_priorities) 118 : lists_(num_priorities), size_(0) { 119#if !defined(NDEBUG) 120 next_id_ = 0; 121#endif 122 } 123 124 // Adds |value| with |priority| to the queue. Returns a pointer to the 125 // created element. 126 Pointer Insert(const T& value, Priority priority) { 127 DCHECK(CalledOnValidThread()); 128 DCHECK_LT(priority, lists_.size()); 129 ++size_; 130 List& list = lists_[priority]; 131#if !defined(NDEBUG) 132 unsigned id = next_id_; 133 valid_ids_.insert(id); 134 ++next_id_; 135 return Pointer(priority, list.insert(list.end(), 136 std::make_pair(id, value))); 137#else 138 return Pointer(priority, list.insert(list.end(), value)); 139#endif 140 } 141 142 // Removes the value pointed by |pointer| from the queue. All pointers to this 143 // value including |pointer| become invalid. 144 void Erase(const Pointer& pointer) { 145 DCHECK(CalledOnValidThread()); 146 DCHECK_LT(pointer.priority_, lists_.size()); 147 DCHECK_GT(size_, 0u); 148 149#if !defined(NDEBUG) 150 DCHECK_EQ(1u, valid_ids_.erase(pointer.id_)); 151 DCHECK_EQ(pointer.iterator_->first, pointer.id_); 152#endif 153 154 --size_; 155 lists_[pointer.priority_].erase(pointer.iterator_); 156 } 157 158 // Returns a pointer to the first value of minimum priority or a null-pointer 159 // if empty. 160 Pointer FirstMin() { 161 DCHECK(CalledOnValidThread()); 162 for (size_t i = 0; i < lists_.size(); ++i) { 163 if (!lists_[i].empty()) 164 return Pointer(i, lists_[i].begin()); 165 } 166 return Pointer(); 167 } 168 169 // Returns a pointer to the last value of minimum priority or a null-pointer 170 // if empty. 171 Pointer LastMin() { 172 DCHECK(CalledOnValidThread()); 173 for (size_t i = 0; i < lists_.size(); ++i) { 174 if (!lists_[i].empty()) 175 return Pointer(i, --lists_[i].end()); 176 } 177 return Pointer(); 178 } 179 180 // Returns a pointer to the first value of maximum priority or a null-pointer 181 // if empty. 182 Pointer FirstMax() { 183 DCHECK(CalledOnValidThread()); 184 for (size_t i = lists_.size(); i > 0; --i) { 185 size_t index = i - 1; 186 if (!lists_[index].empty()) 187 return Pointer(index, lists_[index].begin()); 188 } 189 return Pointer(); 190 } 191 192 // Returns a pointer to the last value of maximum priority or a null-pointer 193 // if empty. 194 Pointer LastMax() { 195 DCHECK(CalledOnValidThread()); 196 for (size_t i = lists_.size(); i > 0; --i) { 197 size_t index = i - 1; 198 if (!lists_[index].empty()) 199 return Pointer(index, --lists_[index].end()); 200 } 201 return Pointer(); 202 } 203 204 // Empties the queue. All pointers become invalid. 205 void Clear() { 206 DCHECK(CalledOnValidThread()); 207 for (size_t i = 0; i < lists_.size(); ++i) { 208 lists_[i].clear(); 209 } 210#if !defined(NDEBUG) 211 valid_ids_.clear(); 212#endif 213 size_ = 0u; 214 } 215 216 // Returns number of queued values. 217 size_t size() const { 218 DCHECK(CalledOnValidThread()); 219 return size_; 220 } 221 222 private: 223 typedef std::vector<List> ListVector; 224 225#if !defined(NDEBUG) 226 unsigned next_id_; 227 base::hash_set<unsigned> valid_ids_; 228#endif 229 230 ListVector lists_; 231 size_t size_; 232 233 DISALLOW_COPY_AND_ASSIGN(PriorityQueue); 234}; 235 236} // namespace net 237 238#endif // NET_BASE_PRIORITY_QUEUE_H_ 239