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