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