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      // 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_
312