priority_queue.h 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382
  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. #ifndef NET_BASE_PRIORITY_QUEUE_H_
  5. #define NET_BASE_PRIORITY_QUEUE_H_
  6. #include <stddef.h>
  7. #include <stdint.h>
  8. #include <list>
  9. #include <utility>
  10. #include <vector>
  11. #include "base/bind.h"
  12. #include "base/callback.h"
  13. #include "base/check_op.h"
  14. #include "base/threading/thread_checker.h"
  15. #if !defined(NDEBUG)
  16. #include <unordered_set>
  17. #endif
  18. namespace net {
  19. // A simple priority queue. The order of values is by priority and then FIFO.
  20. // Unlike the std::priority_queue, this implementation allows erasing elements
  21. // from the queue, and all operations are O(p) time for p priority levels.
  22. // The queue is agnostic to priority ordering (whether 0 precedes 1).
  23. // If the highest priority is 0, FirstMin() returns the first in order.
  24. //
  25. // In debug-mode, the internal queues store (id, value) pairs where id is used
  26. // to validate Pointers.
  27. //
  28. template <typename T>
  29. class PriorityQueue {
  30. private:
  31. // This section is up-front for Pointer only.
  32. #if !defined(NDEBUG)
  33. typedef std::list<std::pair<unsigned, T> > List;
  34. #else
  35. typedef std::list<T> List;
  36. #endif
  37. public:
  38. typedef uint32_t Priority;
  39. // A pointer to a value stored in the queue. The pointer becomes invalid
  40. // when the queue is destroyed or cleared, or the value is erased.
  41. class Pointer {
  42. public:
  43. // Constructs a null pointer.
  44. Pointer() : priority_(kNullPriority) {
  45. #if !defined(NDEBUG)
  46. id_ = static_cast<unsigned>(-1);
  47. #endif
  48. // TODO(syzm)
  49. // An uninitialized iterator behaves like an uninitialized pointer as per
  50. // the STL docs. The fix below is ugly and should possibly be replaced
  51. // with a better approach.
  52. iterator_ = dummy_empty_list_.end();
  53. }
  54. Pointer(const Pointer& p)
  55. : priority_(p.priority_),
  56. iterator_(p.iterator_) {
  57. #if !defined(NDEBUG)
  58. id_ = p.id_;
  59. #endif
  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. bool is_null() const { return priority_ == kNullPriority; }
  71. Priority priority() const { return priority_; }
  72. #if !defined(NDEBUG)
  73. const T& value() const { return iterator_->second; }
  74. #else
  75. const T& value() const { return *iterator_; }
  76. #endif
  77. // Comparing to Pointer from a different PriorityQueue is undefined.
  78. bool Equals(const Pointer& other) const {
  79. return (priority_ == other.priority_) && (iterator_ == other.iterator_);
  80. }
  81. void Reset() {
  82. *this = Pointer();
  83. }
  84. private:
  85. friend class PriorityQueue;
  86. // Note that we need iterator and not const_iterator to pass to
  87. // List::erase. When C++11 is turned on for Chromium, this could
  88. // be changed to const_iterator and the const_casts in the rest of
  89. // the file can be removed.
  90. typedef typename PriorityQueue::List::iterator ListIterator;
  91. static const Priority kNullPriority = static_cast<Priority>(-1);
  92. // It is guaranteed that Pointer will treat |iterator| as a
  93. // const_iterator.
  94. Pointer(Priority priority, const ListIterator& iterator)
  95. : priority_(priority), iterator_(iterator) {
  96. #if !defined(NDEBUG)
  97. id_ = iterator_->first;
  98. #endif
  99. }
  100. Priority priority_;
  101. ListIterator iterator_;
  102. // The STL iterators when uninitialized are like uninitialized pointers
  103. // which cause crashes when assigned to other iterators. We need to
  104. // initialize a NULL iterator to the end of a valid list.
  105. List dummy_empty_list_;
  106. #if !defined(NDEBUG)
  107. // Used by the queue to check if a Pointer is valid.
  108. unsigned id_;
  109. #endif
  110. };
  111. // Creates a new queue for |num_priorities|.
  112. explicit PriorityQueue(Priority num_priorities) : lists_(num_priorities) {
  113. #if !defined(NDEBUG)
  114. next_id_ = 0;
  115. #endif
  116. }
  117. PriorityQueue(const PriorityQueue&) = delete;
  118. PriorityQueue& operator=(const PriorityQueue&) = delete;
  119. ~PriorityQueue() { DCHECK_CALLED_ON_VALID_THREAD(thread_checker_); }
  120. // Adds |value| with |priority| to the queue. Returns a pointer to the
  121. // created element.
  122. Pointer Insert(T value, Priority priority) {
  123. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  124. DCHECK_LT(priority, lists_.size());
  125. ++size_;
  126. List& list = lists_[priority];
  127. #if !defined(NDEBUG)
  128. unsigned id = next_id_;
  129. valid_ids_.insert(id);
  130. ++next_id_;
  131. list.emplace_back(std::make_pair(id, std::move(value)));
  132. #else
  133. list.emplace_back(std::move(value));
  134. #endif
  135. return Pointer(priority, std::prev(list.end()));
  136. }
  137. // Adds |value| with |priority| to the queue. Returns a pointer to the
  138. // created element.
  139. Pointer InsertAtFront(T value, Priority priority) {
  140. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  141. DCHECK_LT(priority, lists_.size());
  142. ++size_;
  143. List& list = lists_[priority];
  144. #if !defined(NDEBUG)
  145. unsigned id = next_id_;
  146. valid_ids_.insert(id);
  147. ++next_id_;
  148. list.emplace_front(std::make_pair(id, std::move(value)));
  149. #else
  150. list.emplace_front(std::move(value));
  151. #endif
  152. return Pointer(priority, list.begin());
  153. }
  154. // Removes the value pointed by |pointer| from the queue. All pointers to this
  155. // value including |pointer| become invalid. Returns the erased value.
  156. T Erase(const Pointer& pointer) {
  157. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  158. DCHECK_LT(pointer.priority_, lists_.size());
  159. DCHECK_GT(size_, 0u);
  160. #if !defined(NDEBUG)
  161. DCHECK_EQ(1u, valid_ids_.erase(pointer.id_));
  162. DCHECK_EQ(pointer.iterator_->first, pointer.id_);
  163. T erased = std::move(pointer.iterator_->second);
  164. #else
  165. T erased = std::move(*pointer.iterator_);
  166. #endif
  167. --size_;
  168. lists_[pointer.priority_].erase(pointer.iterator_);
  169. return erased;
  170. }
  171. // Returns a pointer to the first value of minimum priority or a null-pointer
  172. // if empty.
  173. Pointer FirstMin() const {
  174. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  175. for (size_t i = 0; i < lists_.size(); ++i) {
  176. List* list = const_cast<List*>(&lists_[i]);
  177. if (!list->empty())
  178. return Pointer(i, list->begin());
  179. }
  180. return Pointer();
  181. }
  182. // Returns a pointer to the last value of minimum priority or a null-pointer
  183. // if empty.
  184. Pointer LastMin() const {
  185. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  186. for (size_t i = 0; i < lists_.size(); ++i) {
  187. List* list = const_cast<List*>(&lists_[i]);
  188. if (!list->empty())
  189. return Pointer(i, --list->end());
  190. }
  191. return Pointer();
  192. }
  193. // Returns a pointer to the first value of maximum priority or a null-pointer
  194. // if empty.
  195. Pointer FirstMax() const {
  196. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  197. for (size_t i = lists_.size(); i > 0; --i) {
  198. size_t index = i - 1;
  199. List* list = const_cast<List*>(&lists_[index]);
  200. if (!list->empty())
  201. return Pointer(index, list->begin());
  202. }
  203. return Pointer();
  204. }
  205. // Returns a pointer to the last value of maximum priority or a null-pointer
  206. // if empty.
  207. Pointer LastMax() const {
  208. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  209. for (size_t i = lists_.size(); i > 0; --i) {
  210. size_t index = i - 1;
  211. List* list = const_cast<List*>(&lists_[index]);
  212. if (!list->empty())
  213. return Pointer(index, --list->end());
  214. }
  215. return Pointer();
  216. }
  217. // Given an ordering of the values in this queue by decreasing priority and
  218. // then FIFO, returns a pointer to the value following the value of the given
  219. // pointer (which must be non-NULL). I.e., gets the next element in decreasing
  220. // priority, then FIFO order. If the given pointer is already pointing at the
  221. // last value, returns a null Pointer.
  222. //
  223. // (One could also implement GetNextTowardsFirstMin() [decreasing priority,
  224. // then reverse FIFO] as well as GetNextTowards{First,Last}Max() [increasing
  225. // priority, then {,reverse} FIFO].)
  226. Pointer GetNextTowardsLastMin(const Pointer& pointer) const {
  227. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  228. DCHECK(!pointer.is_null());
  229. DCHECK_LT(pointer.priority_, lists_.size());
  230. typename Pointer::ListIterator it = pointer.iterator_;
  231. Priority priority = pointer.priority_;
  232. DCHECK(it != lists_[priority].end());
  233. ++it;
  234. while (it == lists_[priority].end()) {
  235. if (priority == 0u) {
  236. DCHECK(pointer.Equals(LastMin()));
  237. return Pointer();
  238. }
  239. --priority;
  240. it = const_cast<List*>(&lists_[priority])->begin();
  241. }
  242. return Pointer(priority, it);
  243. }
  244. // Given an ordering of the values in this queue by decreasing priority and
  245. // then FIFO, returns a pointer to the value preceding the value of the given
  246. // pointer (which must be non-NULL). I.e., gets the next element in increasing
  247. // priority, then reverse FIFO order. If the given pointer is already pointing
  248. // at the first value, returns a null Pointer.
  249. Pointer GetPreviousTowardsFirstMax(const Pointer& pointer) const {
  250. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  251. DCHECK(!pointer.is_null());
  252. DCHECK_LT(pointer.priority_, lists_.size());
  253. typename Pointer::ListIterator it = pointer.iterator_;
  254. Priority priority = pointer.priority_;
  255. DCHECK(it != lists_[priority].end());
  256. while (it == lists_[priority].begin()) {
  257. if (priority == num_priorities() - 1) {
  258. DCHECK(pointer.Equals(FirstMax()));
  259. return Pointer();
  260. }
  261. ++priority;
  262. it = const_cast<List*>(&lists_[priority])->end();
  263. }
  264. return Pointer(priority, std::prev(it));
  265. }
  266. // Checks whether |lhs| is closer in the queue to the first max element than
  267. // |rhs|. Assumes that both Pointers refer to elements in this PriorityQueue.
  268. bool IsCloserToFirstMaxThan(const Pointer& lhs, const Pointer& rhs) {
  269. if (lhs.Equals(rhs))
  270. return false;
  271. if (lhs.priority_ == rhs.priority_) {
  272. // Traverse list starting from lhs and see if we find rhs.
  273. for (auto it = lhs.iterator_; it != lists_[lhs.priority_].end(); ++it) {
  274. if (it == rhs.iterator_)
  275. return true;
  276. }
  277. return false;
  278. }
  279. return lhs.priority_ > rhs.priority_;
  280. }
  281. // Checks whether |lhs| is closer in the queue to the last min element than
  282. // |rhs|. Assumes that both Pointers refer to elements in this PriorityQueue.
  283. bool IsCloserToLastMinThan(const Pointer& lhs, const Pointer& rhs) {
  284. return !lhs.Equals(rhs) && !IsCloserToFirstMaxThan(lhs, rhs);
  285. }
  286. // Finds the first element (with respect to decreasing priority, then FIFO
  287. // order) which matches the given predicate.
  288. Pointer FindIf(const base::RepeatingCallback<bool(T)>& pred) {
  289. for (auto pointer = FirstMax(); !pointer.is_null();
  290. pointer = GetNextTowardsLastMin(pointer)) {
  291. if (pred.Run(pointer.value()))
  292. return pointer;
  293. }
  294. return Pointer();
  295. }
  296. // Empties the queue. All pointers become invalid.
  297. void Clear() {
  298. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  299. for (size_t i = 0; i < lists_.size(); ++i) {
  300. lists_[i].clear();
  301. }
  302. #if !defined(NDEBUG)
  303. valid_ids_.clear();
  304. #endif
  305. size_ = 0u;
  306. }
  307. // Returns the number of priorities the queue supports.
  308. size_t num_priorities() const {
  309. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  310. return lists_.size();
  311. }
  312. bool empty() const {
  313. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  314. return size_ == 0;
  315. }
  316. // Returns number of queued values.
  317. size_t size() const {
  318. DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
  319. return size_;
  320. }
  321. private:
  322. typedef std::vector<List> ListVector;
  323. #if !defined(NDEBUG)
  324. unsigned next_id_;
  325. std::unordered_set<unsigned> valid_ids_;
  326. #endif
  327. ListVector lists_;
  328. size_t size_ = 0;
  329. THREAD_CHECKER(thread_checker_);
  330. };
  331. } // namespace net
  332. #endif // NET_BASE_PRIORITY_QUEUE_H_