js/src/ds/SplayTree.h
author Nika Layzell <nika@thelayzells.com>
Wed, 16 Sep 2020 20:47:55 +0000
changeset 549331 ab7d302fd3186b10ada9264528c80f6840e44571
parent 449035 66eb1f485c1a3ea81372758bc92292c9428b17cd
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_SplayTree_h
#define ds_SplayTree_h

#include "ds/LifoAlloc.h"

namespace js {

/*
 * Class which represents a splay tree with nodes allocated from a LifoAlloc.
 * Splay trees are balanced binary search trees for which search, insert and
 * remove are all amortized O(log n).
 *
 * T indicates the type of tree elements, C must have a static
 * compare(const T&, const T&) method ordering the elements. As for LifoAlloc
 * objects, T objects stored in the tree will not be explicitly destroyed.
 */
template <class T, class C>
class SplayTree {
  struct Node {
    T item;
    Node* left;
    Node* right;
    Node* parent;

    explicit Node(const T& item)
        : item(item), left(nullptr), right(nullptr), parent(nullptr) {}
  };

  LifoAlloc* alloc;
  Node* root;
  Node* freeList;

#ifdef DEBUG
  bool enableCheckCoherency;
#endif

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

 public:
  explicit SplayTree(LifoAlloc* alloc = nullptr)
      : alloc(alloc),
        root(nullptr),
        freeList(nullptr)
#ifdef DEBUG
        ,
        enableCheckCoherency(true)
#endif
  {
  }

  void setAllocator(LifoAlloc* alloc) { this->alloc = alloc; }

  void disableCheckCoherency() {
#ifdef DEBUG
    enableCheckCoherency = false;
#endif
  }

  bool empty() const { return !root; }

  T* maybeLookup(const T& v) {
    if (!root) {
      return nullptr;
    }
    Node* last = lookup(v);
    return (C::compare(v, last->item) == 0) ? &(last->item) : nullptr;
  }

  bool contains(const T& v, T* res) {
    if (!root) {
      return false;
    }
    Node* last = lookup(v);
    splay(last);
    checkCoherency();
    if (C::compare(v, last->item) == 0) {
      *res = last->item;
      return true;
    }
    return false;
  }

  MOZ_MUST_USE bool insert(const T& v) {
    Node* element = allocateNode(v);
    if (!element) {
      return false;
    }

    if (!root) {
      root = element;
      return true;
    }
    Node* last = lookup(v);
    int cmp = C::compare(v, last->item);

    // Don't tolerate duplicate elements.
    MOZ_DIAGNOSTIC_ASSERT(cmp);

    Node*& parentPointer = (cmp < 0) ? last->left : last->right;
    MOZ_ASSERT(!parentPointer);
    parentPointer = element;
    element->parent = last;

    splay(element);
    checkCoherency();
    return true;
  }

  void remove(const T& v) {
    Node* last = lookup(v);
    MOZ_ASSERT(last && C::compare(v, last->item) == 0);

    splay(last);
    MOZ_ASSERT(last == root);

    // Find another node which can be swapped in for the root: either the
    // rightmost child of the root's left, or the leftmost child of the
    // root's right.
    Node* swap;
    Node* swapChild;
    if (root->left) {
      swap = root->left;
      while (swap->right) {
        swap = swap->right;
      }
      swapChild = swap->left;
    } else if (root->right) {
      swap = root->right;
      while (swap->left) {
        swap = swap->left;
      }
      swapChild = swap->right;
    } else {
      freeNode(root);
      root = nullptr;
      return;
    }

    // The selected node has at most one child, in swapChild. Detach it
    // from the subtree by replacing it with that child.
    if (swap == swap->parent->left) {
      swap->parent->left = swapChild;
    } else {
      swap->parent->right = swapChild;
    }
    if (swapChild) {
      swapChild->parent = swap->parent;
    }

    root->item = swap->item;
    freeNode(swap);

    checkCoherency();
  }

  template <class Op>
  void forEach(Op op) {
    forEachInner<Op>(op, root);
  }

 private:
  Node* lookup(const T& v) {
    MOZ_ASSERT(root);
    Node* node = root;
    Node* parent;
    do {
      parent = node;
      int c = C::compare(v, node->item);
      if (c == 0) {
        return node;
      } else if (c < 0) {
        node = node->left;
      } else {
        node = node->right;
      }
    } while (node);
    return parent;
  }

  Node* allocateNode(const T& v) {
    Node* node = freeList;
    if (node) {
      freeList = node->left;
      new (node) Node(v);
      return node;
    }
    return alloc->new_<Node>(v);
  }

  void freeNode(Node* node) {
    node->left = freeList;
    freeList = node;
  }

  void splay(Node* node) {
    // Rotate the element until it is at the root of the tree. Performing
    // the rotations in this fashion preserves the amortized balancing of
    // the tree.
    MOZ_ASSERT(node);
    while (node != root) {
      Node* parent = node->parent;
      if (parent == root) {
        // Zig rotation.
        rotate(node);
        MOZ_ASSERT(node == root);
        return;
      }
      Node* grandparent = parent->parent;
      if ((parent->left == node) == (grandparent->left == parent)) {
        // Zig-zig rotation.
        rotate(parent);
        rotate(node);
      } else {
        // Zig-zag rotation.
        rotate(node);
        rotate(node);
      }
    }
  }

  void rotate(Node* node) {
    // Rearrange nodes so that node becomes the parent of its current
    // parent, while preserving the sortedness of the tree.
    Node* parent = node->parent;
    if (parent->left == node) {
      //     x          y
      //   y  c  ==>  a  x
      //  a b           b c
      parent->left = node->right;
      if (node->right) {
        node->right->parent = parent;
      }
      node->right = parent;
    } else {
      MOZ_ASSERT(parent->right == node);
      //   x             y
      //  a  y   ==>   x  c
      //    b c       a b
      parent->right = node->left;
      if (node->left) {
        node->left->parent = parent;
      }
      node->left = parent;
    }
    node->parent = parent->parent;
    parent->parent = node;
    if (Node* grandparent = node->parent) {
      if (grandparent->left == parent) {
        grandparent->left = node;
      } else {
        grandparent->right = node;
      }
    } else {
      root = node;
    }
  }

  template <class Op>
  void forEachInner(Op op, Node* node) {
    if (!node) {
      return;
    }

    forEachInner<Op>(op, node->left);
    op(node->item);
    forEachInner<Op>(op, node->right);
  }

  void checkCoherency() const {
#ifdef DEBUG
    if (!enableCheckCoherency) {
      return;
    }
    if (!root) {
      return;
    }
    MOZ_ASSERT(root->parent == nullptr);
    const Node* node = root;
    const Node* minimum = nullptr;
    MOZ_ASSERT_IF(node->left, node->left->parent == node);
    MOZ_ASSERT_IF(node->right, node->right->parent == node);

    // This is doing a depth-first search and check that the values are
    // ordered properly.
    while (true) {
      // Go to the left-most child.
      while (node->left) {
        MOZ_ASSERT_IF(node->left, node->left->parent == node);
        MOZ_ASSERT_IF(node->right, node->right->parent == node);
        node = node->left;
      }

      MOZ_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0);
      minimum = node;

      if (node->right) {
        // Go once to the right and try again.
        MOZ_ASSERT_IF(node->left, node->left->parent == node);
        MOZ_ASSERT_IF(node->right, node->right->parent == node);
        node = node->right;
      } else {
        // We reached a leaf node, move to the first branch to the right of
        // our current left-most sub-tree.
        MOZ_ASSERT(!node->left && !node->right);
        const Node* prev = nullptr;

        // Visit the parent node, to find the right branch which we have
        // not visited yet. Either we are coming back from the right
        // branch, or we are coming back from the left branch with no
        // right branch to visit.
        while (node->parent) {
          prev = node;
          node = node->parent;

          // If we came back from the left branch, visit the value.
          if (node->left == prev) {
            MOZ_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0);
            minimum = node;
          }

          if (node->right != prev && node->right != nullptr) {
            break;
          }
        }

        if (!node->parent) {
          MOZ_ASSERT(node == root);
          // We reached the root node either because we came back from
          // the right hand side, or because the root node had a
          // single child.
          if (node->right == prev || node->right == nullptr) {
            return;
          }
        }

        // Go to the right node which we have not visited yet.
        MOZ_ASSERT(node->right != prev && node->right != nullptr);
        node = node->right;
      }
    }
#endif
  }
};

} /* namespace js */

#endif /* ds_SplayTree_h */