tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

PriorityQueue.h (3765B)

      1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
      2 * vim: set ts=8 sts=2 et sw=2 tw=80:
      3 * This Source Code Form is subject to the terms of the Mozilla Public
      4 * License, v. 2.0. If a copy of the MPL was not distributed with this
      5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      6 
      7 #ifndef ds_PriorityQueue_h
      8 #define ds_PriorityQueue_h
      9 
     10 #include "js/Vector.h"
     11 
     12 namespace js {
     13 
     14 /*
     15 * Class which represents a heap based priority queue using a vector.
     16 * Inserting elements and removing the highest priority one are both O(log n).
     17 *
     18 * Template parameters are the same as for Vector, with the addition that P
     19 * must have a static higherPriority(const T& a, const T& b) method which
     20 * returns true if |a| has a higher priority than |b|.
     21 */
     22 template <class T, class P, size_t MinInlineCapacity = 0,
     23          class AllocPolicy = TempAllocPolicy>
     24 class PriorityQueue {
     25  Vector<T, MinInlineCapacity, AllocPolicy> heap;
     26 
     27  PriorityQueue(const PriorityQueue&) = delete;
     28  PriorityQueue& operator=(const PriorityQueue&) = delete;
     29 
     30 public:
     31  explicit PriorityQueue(AllocPolicy ap = AllocPolicy())
     32      : heap(std::move(ap)) {}
     33 
     34  [[nodiscard]] bool reserve(size_t capacity) { return heap.reserve(capacity); }
     35 
     36  size_t length() const { return heap.length(); }
     37 
     38  bool empty() const { return heap.empty(); }
     39 
     40  // highest and popHighest are used to enforce necessary move semantics for
     41  // working with UniquePtrs in a queue, and should be used together Example:
     42  //   UniquePtr<...> x = std::move(queue.highest());
     43  //   queue.popHighest();
     44  T& highest() {
     45    MOZ_ASSERT(!empty());
     46    return heap[0];
     47  }
     48 
     49  void popHighest() {
     50    if (heap.length() == 1) {
     51      heap.popBack();
     52      return;
     53    }
     54    std::swap(heap[0], heap.back());
     55    heap.popBack();
     56    siftDown(0);
     57  }
     58 
     59  // removeHighest cannot be used with UniquePtrs, and should only be used for
     60  // other datatypes.
     61  T removeHighest() {
     62    T highest = heap[0];
     63    T last = heap.popCopy();
     64    if (!heap.empty()) {
     65      heap[0] = last;
     66      siftDown(0);
     67    }
     68    return highest;
     69  }
     70 
     71  [[nodiscard]] bool insert(T&& v) {
     72    if (!heap.append(std::move(v))) {
     73      return false;
     74    }
     75    siftUp(heap.length() - 1);
     76    return true;
     77  }
     78 
     79  // The combination of reserveOne+infallibleInsert can be used for the case
     80  // where the failure case needs to take the ownership of the value.
     81  [[nodiscard]] bool reserveOne() { return heap.reserve(heap.length() + 1); }
     82 
     83  void infallibleInsert(T&& v) {
     84    heap.infallibleAppend(std::move(v));
     85    siftUp(heap.length() - 1);
     86  }
     87 
     88 private:
     89  /*
     90   * Elements of the vector encode a binary tree:
     91   *
     92   *      0
     93   *    1   2
     94   *   3 4 5 6
     95   *
     96   * The children of element N are (2N + 1) and (2N + 2).
     97   * The parent of element N is (N - 1) / 2.
     98   *
     99   * Each element has higher priority than its children.
    100   */
    101 
    102  void siftDown(size_t n) {
    103    while (true) {
    104      size_t left = n * 2 + 1;
    105      size_t right = n * 2 + 2;
    106 
    107      if (left < heap.length()) {
    108        if (right < heap.length()) {
    109          if (P::higherPriority(heap[right], heap[n]) &&
    110              P::higherPriority(heap[right], heap[left])) {
    111            swap(n, right);
    112            n = right;
    113            continue;
    114          }
    115        }
    116 
    117        if (P::higherPriority(heap[left], heap[n])) {
    118          swap(n, left);
    119          n = left;
    120          continue;
    121        }
    122      }
    123 
    124      break;
    125    }
    126  }
    127 
    128  void siftUp(size_t n) {
    129    while (n > 0) {
    130      size_t parent = (n - 1) / 2;
    131 
    132      if (P::higherPriority(heap[parent], heap[n])) {
    133        break;
    134      }
    135 
    136      swap(n, parent);
    137      n = parent;
    138    }
    139  }
    140 
    141  void swap(size_t a, size_t b) { std::swap(heap[a], heap[b]); }
    142 };
    143 
    144 } /* namespace js */
    145 
    146 #endif /* ds_PriorityQueue_h */