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