summaryrefslogtreecommitdiffstats
path: root/js/src/ds/SplayTree.h
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/ds/SplayTree.h')
-rw-r--r--js/src/ds/SplayTree.h308
1 files changed, 308 insertions, 0 deletions
diff --git a/js/src/ds/SplayTree.h b/js/src/ds/SplayTree.h
new file mode 100644
index 000000000..f130706e5
--- /dev/null
+++ b/js/src/ds/SplayTree.h
@@ -0,0 +1,308 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * 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(root, nullptr);
+ 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_ASSERT(cmp);
+
+ Node*& parentPointer = (cmp < 0) ? last->left : last->right;
+ MOZ_ASSERT(!parentPointer);
+ parentPointer = element;
+ element->parent = last;
+
+ splay(element);
+ checkCoherency(root, nullptr);
+ 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(root, nullptr);
+ }
+
+ 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);
+ }
+
+ Node* checkCoherency(Node* node, Node* minimum)
+ {
+#ifdef DEBUG
+ if (!enableCheckCoherency)
+ return nullptr;
+ if (!node) {
+ MOZ_ASSERT(!root);
+ return nullptr;
+ }
+ MOZ_ASSERT_IF(!node->parent, node == root);
+ MOZ_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0);
+ if (node->left) {
+ MOZ_ASSERT(node->left->parent == node);
+ Node* leftMaximum = checkCoherency(node->left, minimum);
+ MOZ_ASSERT(C::compare(leftMaximum->item, node->item) < 0);
+ }
+ if (node->right) {
+ MOZ_ASSERT(node->right->parent == node);
+ return checkCoherency(node->right, node);
+ }
+ return node;
+#else
+ return nullptr;
+#endif
+ }
+};
+
+} /* namespace js */
+
+#endif /* ds_SplayTree_h */
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-14 21:42:07 +0000