summaryrefslogtreecommitdiffstats
path: root/js/src/ds/SplayTree.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--js/src/ds/SplayTree.h354
1 files changed, 354 insertions, 0 deletions
diff --git a/js/src/ds/SplayTree.h b/js/src/ds/SplayTree.h
new file mode 100644
index 0000000000..ae4c1ca3d3
--- /dev/null
+++ b/js/src/ds/SplayTree.h
@@ -0,0 +1,354 @@
+/* -*- 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 */
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-24 09:32:00 +0000