27 // A simple priority queue. The order of values is by priority and then FIFO.
29 // from the queue, and all operations are O(p) time for p priority levels.
30 // The queue is agnostic to priority ordering (whether 0 precedes 1).
31 // If the highest priority is 0, FirstMin() returns the first in order.
47   typedef uint32_t Priority;  typedef
85     Priority priority() const { return priority_; }  in priority()  function
111     static const Priority kNullPriority = static_cast<Priority>(-1);
115     Pointer(Priority priority, const ListIterator& iterator)  in Pointer()  argument
116         : priority_(priority), iterator_(iterator) {  in Pointer()
122     Priority priority_;
136   explicit PriorityQueue(Priority num_priorities) : lists_(num_priorities) {  in PriorityQueue()
146   // Adds |value| with |priority| to the queue. Returns a pointer to the
148   Pointer Insert(T value, Priority priority) {  in Insert()  argument
150     DCHECK_LT(priority, lists_.size());  in Insert()
152     List& list = lists_[priority];  in Insert()
161     return Pointer(priority, std::prev(list.end()));  in Insert()
164   // Adds |value| with |priority| to the queue. Returns a pointer to the
166   Pointer InsertAtFront(T value, Priority priority) {  in InsertAtFront()  argument
168     DCHECK_LT(priority, lists_.size());  in InsertAtFront()
170     List& list = lists_[priority];  in InsertAtFront()
179     return Pointer(priority, list.begin());  in InsertAtFront()
202   // Returns a pointer to the first value of minimum priority or a null-pointer
214   // Returns a pointer to the last value of minimum priority or a null-pointer
226   // Returns a pointer to the first value of maximum priority or a null-pointer
239   // Returns a pointer to the last value of maximum priority or a null-pointer
252   // Given an ordering of the values in this queue by decreasing priority and
255   // priority, then FIFO order. If the given pointer is already pointing at the
258   // (One could also implement GetNextTowardsFirstMin() [decreasing priority,
260   // priority, then {,reverse} FIFO].)
267     Priority priority = pointer.priority_;  in GetNextTowardsLastMin()  local
268     CHECK(it != lists_[priority].end(), base::NotFatalUntil::M130);  in GetNextTowardsLastMin()
270     while (it == lists_[priority].end()) {  in GetNextTowardsLastMin()
271       if (priority == 0u) {  in GetNextTowardsLastMin()
275       --priority;  in GetNextTowardsLastMin()
276       it = const_cast<List*>(&lists_[priority])->begin();  in GetNextTowardsLastMin()
278     return Pointer(priority, it);  in GetNextTowardsLastMin()
281   // Given an ordering of the values in this queue by decreasing priority and
284   // priority, then reverse FIFO order. If the given pointer is already pointing
292     Priority priority = pointer.priority_;  in GetPreviousTowardsFirstMax()  local
293     CHECK(it != lists_[priority].end(), base::NotFatalUntil::M130);  in GetPreviousTowardsFirstMax()
294     while (it == lists_[priority].begin()) {  in GetPreviousTowardsFirstMax()
295       if (priority == num_priorities() - 1) {  in GetPreviousTowardsFirstMax()
299       ++priority;  in GetPreviousTowardsFirstMax()
300       it = const_cast<List*>(&lists_[priority])->end();  in GetPreviousTowardsFirstMax()
302     return Pointer(priority, std::prev(it));  in GetPreviousTowardsFirstMax()
327   // Finds the first element (with respect to decreasing priority, then FIFO