net/base/priority_queue.h

   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
  20 namespace 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 //
  31 template<typename T>
  32 class 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       // TODO(syzm)
  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
  56       // with a better approach.
  57       iterator_ = dummy_empty_list_.end();
  58     }
  59
  60     Pointer(const Pointer& p)
  61         : priority_(p.priority_),
  62           iterator_(p.iterator_) {
  63 #if !defined(NDEBUG)
  64       id_ = p.id_;
  65 #endif
  66     }
  67
  68     Pointer& operator=(const Pointer& p) {
  69       // Self-assignment is benign.
  70       priority_ = p.priority_;
  71       iterator_ = p.iterator_;
  72 #if !defined(NDEBUG)
  73       id_ = p.id_;
  74 #endif
  75       return *this;
  76     }
  77
  78     bool is_null() const { return priority_ == kNullPriority; }
  79
  80     Priority priority() const { return priority_; }
  81
  82 #if !defined(NDEBUG)
  83     const T& value() const { return iterator_->second; }
  84 #else
  85     const T& value() const { return *iterator_; }
  86 #endif
  87
  88     // Comparing to Pointer from a different PriorityQueue is undefined.
  89     bool Equals(const Pointer& other) const {
  90       return (priority_ == other.priority_) && (iterator_ == other.iterator_);
  91     }
  92
  93     void Reset() {
  94       *this = Pointer();
  95     }
  96
  97    private:
  98     friend class PriorityQueue;
  99
 100     // 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
 102     // be changed to const_iterator and the const_casts in the rest of
 103     // the file can be removed.
 104     typedef typename PriorityQueue::List::iterator ListIterator;
 105
 106     static const Priority kNullPriority = static_cast<Priority>(-1);
 107
 108     // It is guaranteed that Pointer will treat |iterator| as a
 109     // const_iterator.
 110     Pointer(Priority priority, const ListIterator& iterator)
 111         : priority_(priority), iterator_(iterator) {
 112 #if !defined(NDEBUG)
 113       id_ = iterator_->first;
 114 #endif
 115     }
 116
 117     Priority priority_;
 118     ListIterator iterator_;
 119     // The STL iterators when uninitialized are like uninitialized pointers
 120     // which cause crashes when assigned to other iterators. We need to
 121     // initialize a NULL iterator to the end of a valid list.
 122     List dummy_empty_list_;
 123
 124 #if !defined(NDEBUG)
 125     // Used by the queue to check if a Pointer is valid.
 126     unsigned id_;
 127 #endif
 128   };
 129
 130   // Creates a new queue for |num_priorities|.
 131   explicit PriorityQueue(Priority num_priorities)
 132       : lists_(num_priorities), size_(0) {
 133 #if !defined(NDEBUG)
 134     next_id_ = 0;
 135 #endif
 136   }
 137
 138   // Adds |value| with |priority| to the queue. Returns a pointer to the
 139   // created element.
 140   Pointer Insert(const T& value, Priority priority) {
 141     DCHECK(CalledOnValidThread());
 142     DCHECK_LT(priority, lists_.size());
 143     ++size_;
 144     List& list = lists_[priority];
 145 #if !defined(NDEBUG)
 146     unsigned id = next_id_;
 147     valid_ids_.insert(id);
 148     ++next_id_;
 149     return Pointer(priority, list.insert(list.end(),
 150                                          std::make_pair(id, value)));
 151 #else
 152     return Pointer(priority, list.insert(list.end(), value));
 153 #endif
 154   }
 155
 156   // Adds |value| with |priority| to the queue. Returns a pointer to the
 157   // created element.
 158   Pointer InsertAtFront(const T& value, Priority priority) {
 159     DCHECK(CalledOnValidThread());
 160     DCHECK_LT(priority, lists_.size());
 161     ++size_;
 162     List& list = lists_[priority];
 163 #if !defined(NDEBUG)
 164     unsigned id = next_id_;
 165     valid_ids_.insert(id);
 166     ++next_id_;
 167     return Pointer(priority, list.insert(list.begin(),
 168                                          std::make_pair(id, value)));
 169 #else
 170     return Pointer(priority, list.insert(list.begin(), value));
 171 #endif
 172   }
 173
 174   // Removes the value pointed by |pointer| from the queue. All pointers to this
 175   // value including |pointer| become invalid.
 176   void Erase(const Pointer& pointer) {
 177     DCHECK(CalledOnValidThread());
 178     DCHECK_LT(pointer.priority_, lists_.size());
 179     DCHECK_GT(size_, 0u);
 180
 181 #if !defined(NDEBUG)
 182     DCHECK_EQ(1u, valid_ids_.erase(pointer.id_));
 183     DCHECK_EQ(pointer.iterator_->first, pointer.id_);
 184 #endif
 185
 186     --size_;
 187     lists_[pointer.priority_].erase(pointer.iterator_);
 188   }
 189
 190   // Returns a pointer to the first value of minimum priority or a null-pointer
 191   // if empty.
 192   Pointer FirstMin() const {
 193     DCHECK(CalledOnValidThread());
 194     for (size_t i = 0; i < lists_.size(); ++i) {
 195       List* list = const_cast<List*>(&lists_[i]);
 196       if (!list->empty())
 197         return Pointer(i, list->begin());
 198     }
 199     return Pointer();
 200   }
 201
 202   // Returns a pointer to the last value of minimum priority or a null-pointer
 203   // if empty.
 204   Pointer LastMin() const {
 205     DCHECK(CalledOnValidThread());
 206     for (size_t i = 0; i < lists_.size(); ++i) {
 207       List* list = const_cast<List*>(&lists_[i]);
 208       if (!list->empty())
 209         return Pointer(i, --list->end());
 210     }
 211     return Pointer();
 212   }
 213
 214   // Returns a pointer to the first value of maximum priority or a null-pointer
 215   // if empty.
 216   Pointer FirstMax() const {
 217     DCHECK(CalledOnValidThread());
 218     for (size_t i = lists_.size(); i > 0; --i) {
 219       size_t index = i - 1;
 220       List* list = const_cast<List*>(&lists_[index]);
 221       if (!list->empty())
 222         return Pointer(index, list->begin());
 223     }
 224     return Pointer();
 225   }
 226
 227   // Returns a pointer to the last value of maximum priority or a null-pointer
 228   // if empty.
 229   Pointer LastMax() const {
 230     DCHECK(CalledOnValidThread());
 231     for (size_t i = lists_.size(); i > 0; --i) {
 232       size_t index = i - 1;
 233       List* list = const_cast<List*>(&lists_[index]);
 234       if (!list->empty())
 235         return Pointer(index, --list->end());
 236     }
 237     return Pointer();
 238   }
 239
 240   // Given an ordering of the values in this queue by decreasing
 241   // priority and then FIFO, returns a pointer to the value following
 242   // the value of the given pointer (which must be non-NULL).
 243   //
 244   // (One could also implement GetNextTowardsFirstMin() [decreasing
 245   // priority, then reverse FIFO] as well as
 246   // GetNextTowards{First,Last}Max() [increasing priority, then
 247   // {,reverse} FIFO].)
 248   Pointer GetNextTowardsLastMin(const Pointer& pointer) const {
 249     DCHECK(CalledOnValidThread());
 250     DCHECK(!pointer.is_null());
 251     DCHECK_LT(pointer.priority_, lists_.size());
 252
 253     typename Pointer::ListIterator it = pointer.iterator_;
 254     Priority priority = pointer.priority_;
 255     DCHECK(it != lists_[priority].end());
 256     ++it;
 257     while (it == lists_[priority].end()) {
 258       if (priority == 0u)
 259         return Pointer();
 260       --priority;
 261       it = const_cast<List*>(&lists_[priority])->begin();
 262     }
 263     return Pointer(priority, it);
 264   }
 265
 266   // Empties the queue. All pointers become invalid.
 267   void Clear() {
 268     DCHECK(CalledOnValidThread());
 269     for (size_t i = 0; i < lists_.size(); ++i) {
 270       lists_[i].clear();
 271     }
 272 #if !defined(NDEBUG)
 273     valid_ids_.clear();
 274 #endif
 275     size_ = 0u;
 276   }
 277
 278   // Returns the number of priorities the queue supports.
 279   size_t num_priorities() const {
 280     DCHECK(CalledOnValidThread());
 281     return lists_.size();
 282   }
 283
 284   bool empty() const {
 285     DCHECK(CalledOnValidThread());
 286     return size_ == 0;
 287   }
 288
 289   // Returns number of queued values.
 290   size_t size() const {
 291     DCHECK(CalledOnValidThread());
 292     return size_;
 293   }
 294
 295  private:
 296   typedef std::vector<List> ListVector;
 297
 298 #if !defined(NDEBUG)
 299   unsigned next_id_;
 300   base::hash_set<unsigned> valid_ids_;
 301 #endif
 302
 303   ListVector lists_;
 304   size_t size_;
 305
 306   DISALLOW_COPY_AND_ASSIGN(PriorityQueue);
 307 };
 308
 309 }  // namespace net
 310
 311 #endif  // NET_BASE_PRIORITY_QUEUE_H_