js/src/ds/PriorityQueue.h
author Nika Layzell <nika@thelayzells.com>
Wed, 16 Sep 2020 20:47:55 +0000
changeset 549331 ab7d302fd3186b10ada9264528c80f6840e44571
parent 480654 1621ba12b29232e3eafa61a6c0e1bb0770147554
permissions -rw-r--r--
Bug 1659696 - Check PendingInitialization before targeting in window.open, r=kmag This requires adding the flag as a synced field on the BrowsingContext, and checking it in a few more places. Attempts to open a new window in this racy manner will now raise an exception. This should avoid the issue from bug 1658854 by blocking the buggy attempts to load before the nested event loop has been exited. Differential Revision: https://phabricator.services.mozilla.com/D87927

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef ds_PriorityQueue_h
#define ds_PriorityQueue_h

#include "js/Vector.h"

namespace js {

/*
 * Class which represents a heap based priority queue using a vector.
 * Inserting elements and removing the highest priority one are both O(log n).
 *
 * Template parameters are the same as for Vector, with the addition that P
 * must have a static priority(const T&) method which returns higher numbers
 * for higher priority elements.
 */
template <class T, class P, size_t MinInlineCapacity = 0,
          class AllocPolicy = TempAllocPolicy>
class PriorityQueue {
  Vector<T, MinInlineCapacity, AllocPolicy> heap;

  PriorityQueue(const PriorityQueue&) = delete;
  PriorityQueue& operator=(const PriorityQueue&) = delete;

 public:
  explicit PriorityQueue(AllocPolicy ap = AllocPolicy())
      : heap(std::move(ap)) {}

  MOZ_MUST_USE bool reserve(size_t capacity) { return heap.reserve(capacity); }

  size_t length() const { return heap.length(); }

  bool empty() const { return heap.empty(); }

  T removeHighest() {
    T highest = heap[0];
    T last = heap.popCopy();
    if (!heap.empty()) {
      heap[0] = last;
      siftDown(0);
    }
    return highest;
  }

  MOZ_MUST_USE bool insert(const T& v) {
    if (!heap.append(v)) {
      return false;
    }
    siftUp(heap.length() - 1);
    return true;
  }

  void infallibleInsert(const T& v) {
    heap.infallibleAppend(v);
    siftUp(heap.length() - 1);
  }

 private:
  /*
   * Elements of the vector encode a binary tree:
   *
   *      0
   *    1   2
   *   3 4 5 6
   *
   * The children of element N are (2N + 1) and (2N + 2).
   * The parent of element N is (N - 1) / 2.
   *
   * Each element has higher priority than its children.
   */

  void siftDown(size_t n) {
    while (true) {
      size_t left = n * 2 + 1;
      size_t right = n * 2 + 2;

      if (left < heap.length()) {
        if (right < heap.length()) {
          if (P::priority(heap[n]) < P::priority(heap[right]) &&
              P::priority(heap[left]) < P::priority(heap[right])) {
            swap(n, right);
            n = right;
            continue;
          }
        }

        if (P::priority(heap[n]) < P::priority(heap[left])) {
          swap(n, left);
          n = left;
          continue;
        }
      }

      break;
    }
  }

  void siftUp(size_t n) {
    while (n > 0) {
      size_t parent = (n - 1) / 2;

      if (P::priority(heap[parent]) > P::priority(heap[n])) {
        break;
      }

      swap(n, parent);
      n = parent;
    }
  }

  void swap(size_t a, size_t b) {
    T tmp = heap[a];
    heap[a] = heap[b];
    heap[b] = tmp;
  }
};

} /* namespace js */

#endif /* ds_PriorityQueue_h */