summaryrefslogtreecommitdiffstats
path: root/js/src/ds/AvlTree.h
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/ds/AvlTree.h')
-rw-r--r--js/src/ds/AvlTree.h1041
1 files changed, 1041 insertions, 0 deletions
diff --git a/js/src/ds/AvlTree.h b/js/src/ds/AvlTree.h
new file mode 100644
index 0000000000..eb31041c5c
--- /dev/null
+++ b/js/src/ds/AvlTree.h
@@ -0,0 +1,1041 @@
+/* -*- 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/. */
+
+// The methods 'AvlTreeImpl::insert_worker' and 'AvlTreeImpl::delete_worker',
+// and all supporting methods reachable from them, are derived from a public
+// domain implementation by Georg Kraml. The public domain implementation in
+// C was translated into Rust and the Rust translation was later translated
+// into this C++ implementation.
+//
+// Unfortunately the relevant web site for the original C version is long
+// gone, and can only be found on the Wayback Machine:
+//
+// https://web.archive.org/web/20010419134337/
+// http://www.kraml.at/georg/avltree/index.html
+//
+// https://web.archive.org/web/20030926063347/
+// http://www.kraml.at/georg/avltree/avlmonolithic.c
+//
+// https://web.archive.org/web/20030401124003/http://www.kraml.at/src/howto/
+//
+// The intermediate Rust translation can be found at
+//
+// https://github.com/bytecodealliance/regalloc.rs/blob/main/lib/src/avl_tree.rs
+//
+// For relicensing clearances, see Mozilla bugs 1620332 and 1769261:
+//
+// https://bugzilla.mozilla.org/show_bug.cgi?id=1620332
+// https://bugzilla.mozilla.org/show_bug.cgi?id=1769261
+//
+// All other code in this file originates from Mozilla.
+
+#ifndef ds_AvlTree_h
+#define ds_AvlTree_h
+
+#include "mozilla/Attributes.h"
+#include "mozilla/Likely.h"
+#include "mozilla/MathAlgorithms.h"
+#include "mozilla/Maybe.h"
+#include "ds/LifoAlloc.h"
+
+namespace js {
+
+////////////////////////////////////////////////////////////////////////
+// //
+// AvlTree implementation. For interface see `class AvlTree` below. //
+// //
+////////////////////////////////////////////////////////////////////////
+
+// An AVL tree class, with private allocator and node-recycling. `T` is the
+// class of elements in the tree. `C` must provide a method
+//
+// static int compare(const T&, const T&)
+//
+// to provide a total ordering on values `T` that are put into the tree,
+// returning -1 for less-than, 0 for equal, and 1 for greater-than.
+//
+// `C::compare` does not have to be a total ordering for *all* values of `T`,
+// but it must be so for the `T` values in the tree. Requests to insert
+// duplicate `T` values, as determined equal by `C::compare`, are valid but
+// will be ignored in this implementation class: the stored data is unchanged.
+// The interface class `AvlTree` however will MOZ_CRASH() on such requests.
+//
+// `T` values stored in the tree will not be explicitly freed or destroyed.
+//
+// For best cache-friendlyness, try to put the fields of `T` that are read by
+// your compare function at the end of `T`. See comment on `struct Node`
+// below.
+//
+// Some operations require (internally) building a stack of tree nodes from
+// the root to some leaf. The maximum stack size, and hence the maximum tree
+// depth, is currently bounded at 48. The max depth of an AVL tree is roughly
+// 1.44 * log2(# nodes), so providing the tree-balancing machinery works
+// correctly, the max number of nodes is at least 2^(48 / 1.44), somewhat over
+// 2^33 (= 8 G). On a 32-bit target we'll run out of address space long
+// before reaching that. On a 64-bit target, the minimum imaginable
+// sizeof(Node) is 16 (for the two pointers), so a tree with 2^33 nodes would
+// occupy at least 2^37 bytes, viz, around 137GB. So this seems unlikely to
+// be a limitation.
+//
+// All stack-pushing operations are release-asserted to not overflow the stack.
+
+template <class T, class C>
+class AvlTreeImpl {
+ // This is the implementation of AVL trees. If you want to know how to use
+ // them in your code, don't read this; instead look below at the public
+ // interface, that is, `class AvlTree`.
+ //
+ // All of `AvlTreeImpl`, apart from the iterator code at the bottom, is
+ // protected. Public facilities are provided by child class `AvlTree`.
+ protected:
+ // Tree node tags.
+ enum class Tag {
+ Free, // Node not in use -- is on the freelist.
+ None, // Node in use. Neither subtree is deeper.
+ Left, // Node in use. The left subtree is deeper.
+ Right, // Node in use. The right subtree is deeper.
+
+ Count, // Not used as an actual tag - should remain last in this list
+ };
+
+ // Tree nodes. The tag is stored in the lower bits of the right Node pointer
+ // rather than as a separate field. For types T with alignment no more than
+ // twice the size of a pointer (ie, most types), this reduces the size of Node
+ // and enables them to pack more tightly, reducing memory requirements and
+ // improving cache behavior. (See bug 1847616.)
+ struct Node {
+ T item;
+ Node* left;
+
+ // This is the mask to use to extract the tag from `rightAndTag`.
+ static constexpr uintptr_t kTagMask = 3;
+ static_assert(mozilla::IsPowerOfTwo(kTagMask + 1),
+ "kTagMask must only have a consecutive sequence of its "
+ "lowest bits set");
+ static_assert(
+ kTagMask >= static_cast<uintptr_t>(Tag::Count) - 1,
+ "kTagMask must be sufficient to cover largest value in 'Tag'");
+
+ private:
+ uintptr_t rightAndTag;
+
+ public:
+ explicit Node(const T& item)
+ : item(item),
+ left(nullptr),
+ rightAndTag(static_cast<uintptr_t>(Tag::None)) {}
+
+ [[nodiscard]] Node* getRight() const {
+ return reinterpret_cast<Node*>(rightAndTag & ~kTagMask);
+ }
+ [[nodiscard]] Tag getTag() const {
+ return static_cast<Tag>(rightAndTag & kTagMask);
+ }
+
+ void setRight(Node* right) {
+ rightAndTag =
+ reinterpret_cast<uintptr_t>(right) | static_cast<uintptr_t>(getTag());
+ }
+ void setTag(const Tag tag) {
+ rightAndTag = (rightAndTag & ~kTagMask) | static_cast<uintptr_t>(tag);
+ }
+ void setRightAndTag(Node* right, const Tag tag) {
+ const uintptr_t rightAsUint = reinterpret_cast<uintptr_t>(right);
+ rightAndTag = rightAsUint | static_cast<uintptr_t>(tag);
+ }
+ };
+
+ // Ensure that we can use the needed lower bits of a Node pointer to store the
+ // tag.
+ static_assert(alignof(Node) >= Node::kTagMask + 1);
+
+ // Once-per-tree components.
+ Node* root_;
+ Node* freeList_;
+ LifoAlloc* alloc_;
+
+ // As a modest but easy optimisation, ::allocateNode will allocate one node
+ // at the first call that sees an empty `freeList_`, two on the next such
+ // call and four on subsequent such calls. This has the effect of reducing
+ // the number of calls to the underlying allocator `alloc_` by a factor of 4
+ // for all but the smallest trees. It also helps pack more nodes into each
+ // cache line. The limit of 4 exists for three reasons:
+ //
+ // (1) It gains the majority (75%) of the available benefit from reducing
+ // the number of calls to `alloc_`, as the allocation size tends to
+ // infinity.
+ //
+ // (2) Similarly, 4 `struct Node`s will surely be greater than 128 bytes,
+ // hence there is minimal chance to use even fewer cache lines by increasing
+ // the group size further. In any case most machines have cache lines of
+ // size 64 bytes, not 128.
+ //
+ // (3) Most importantly, it limits the maximum potentially wasted space,
+ // which is the case where a request causes an allocation of N nodes, of
+ // which one is used immediately and the N-1 are put on the freelist, but
+ // then -- because the tree never grows larger -- are never used. Given
+ // that N=4 here, the worst case lossage is 3 nodes, which seems tolerable.
+ uint32_t nextAllocSize_; // 1, 2 or 4 only
+
+ // The expected maximum tree depth. See comments above.
+ static const size_t MAX_TREE_DEPTH = 48;
+
+ AvlTreeImpl(const AvlTreeImpl&) = delete;
+ AvlTreeImpl& operator=(const AvlTreeImpl&) = delete;
+
+ // ---- Preliminaries --------------------------------------- //
+
+ explicit AvlTreeImpl(LifoAlloc* alloc = nullptr)
+ : root_(nullptr), freeList_(nullptr), alloc_(alloc), nextAllocSize_(1) {}
+
+ void setAllocator(LifoAlloc* alloc) { alloc_ = alloc; }
+
+ // Put `node` onto the free list, for possible later reuse.
+ inline void addToFreeList(Node* node) {
+ node->left = freeList_;
+ node->setRightAndTag(nullptr, Tag::Free); // for safety
+ freeList_ = node;
+ }
+
+ // A safer version of `addToFreeList`.
+ inline void freeNode(Node* node) {
+ MOZ_ASSERT(node->getTag() != Tag::Free);
+ addToFreeList(node);
+ }
+
+ // This is the slow path for ::allocateNode below. Allocate 1, 2 or 4 nodes
+ // as a block, return the first one properly initialised, and put the rest
+ // on the freelist, in increasing order of address.
+ MOZ_NEVER_INLINE Node* allocateNodeOOL(const T& v) {
+ switch (nextAllocSize_) {
+ case 1: {
+ nextAllocSize_ = 2;
+ Node* node = alloc_->new_<Node>(v);
+ // `node` is either fully initialized, or nullptr on OOM.
+ return node;
+ }
+ case 2: {
+ nextAllocSize_ = 4;
+ Node* nodes = alloc_->newArrayUninitialized<Node>(2);
+ if (!nodes) {
+ return nullptr;
+ }
+ Node* node0 = &nodes[0];
+ addToFreeList(&nodes[1]);
+ new (node0) Node(v);
+ return node0;
+ }
+ case 4: {
+ Node* nodes = alloc_->newArrayUninitialized<Node>(4);
+ if (!nodes) {
+ return nullptr;
+ }
+ Node* node0 = &nodes[0];
+ addToFreeList(&nodes[3]);
+ addToFreeList(&nodes[2]);
+ addToFreeList(&nodes[1]);
+ new (node0) Node(v);
+ return node0;
+ }
+ default: {
+ MOZ_CRASH();
+ }
+ }
+ }
+
+ // Allocate a Node holding `v`, or return nullptr on OOM. All of the fields
+ // are initialized.
+ inline Node* allocateNode(const T& v) {
+ Node* node = freeList_;
+ if (MOZ_LIKELY(node)) {
+ MOZ_ASSERT(node->getTag() == Tag::Free);
+ freeList_ = node->left;
+ new (node) Node(v);
+ return node;
+ }
+ return allocateNodeOOL(v);
+ }
+
+ // These exist only transiently, to aid rebalancing. They indicate whether
+ // an insertion/deletion succeeded, whether subsequent rebalancing is
+ // needed.
+ enum class Result { Error, OK, Balance };
+
+ using NodeAndResult = std::pair<Node*, Result>;
+
+ // Standard AVL single-rotate-left
+ Node* rotate_left(Node* old_root) {
+ Node* new_root = old_root->getRight();
+ old_root->setRight(new_root->left);
+ new_root->left = old_root;
+ return new_root;
+ }
+
+ // Standard AVL single-rotate-right
+ Node* rotate_right(Node* old_root) {
+ Node* new_root = old_root->left;
+ old_root->left = new_root->getRight();
+ new_root->setRight(old_root);
+ return new_root;
+ }
+
+ // ---- Helpers for insertion ------------------------------- //
+
+ // `leftgrown`: a helper function for `insert_worker`
+ //
+ // Parameters:
+ //
+ // root Root of a tree. This node's left subtree has just grown due to
+ // item insertion; its "tag" flag needs adjustment, and the local
+ // tree (the subtree of which this node is the root node) may have
+ // become unbalanced.
+ //
+ // Return values:
+ //
+ // The new root of the subtree, plus either:
+ //
+ // OK The local tree could be rebalanced or was balanced from the
+ // start. The caller, insert_worker, may assume the entire tree
+ // is valid.
+ // or
+ // Balance The local tree was balanced, but has grown in height.
+ // Do not assume the entire tree is valid.
+ //
+ // This function has been split into two pieces: `leftgrown`, which is small
+ // and hot, and is marked always-inline, and `leftgrown_left`, which handles
+ // a more complex and less frequent case, and is marked never-inline. The
+ // intent is to have the common case always inlined without having to deal
+ // with the extra register pressure from inlining the less frequent code.
+ // The dual function `rightgrown` is split similarly.
+
+ MOZ_NEVER_INLINE Node* leftgrown_left(Node* root) {
+ if (root->left->getTag() == Tag::Left) {
+ root->setTag(Tag::None);
+ root->left->setTag(Tag::None);
+ root = rotate_right(root);
+ } else {
+ switch (root->left->getRight()->getTag()) {
+ case Tag::Left:
+ root->setTag(Tag::Right);
+ root->left->setTag(Tag::None);
+ break;
+ case Tag::Right:
+ root->setTag(Tag::None);
+ root->left->setTag(Tag::Left);
+ break;
+ case Tag::None:
+ root->setTag(Tag::None);
+ root->left->setTag(Tag::None);
+ break;
+ case Tag::Free:
+ default:
+ MOZ_CRASH();
+ }
+ root->left->getRight()->setTag(Tag::None);
+ root->left = rotate_left(root->left);
+ root = rotate_right(root);
+ }
+ return root;
+ }
+
+ inline NodeAndResult leftgrown(Node* root) {
+ switch (root->getTag()) {
+ case Tag::Left:
+ return NodeAndResult(leftgrown_left(root), Result::OK);
+ case Tag::Right:
+ root->setTag(Tag::None);
+ return NodeAndResult(root, Result::OK);
+ case Tag::None:
+ root->setTag(Tag::Left);
+ return NodeAndResult(root, Result::Balance);
+ case Tag::Free:
+ default:
+ break;
+ }
+ MOZ_CRASH();
+ }
+
+ // `rightgrown`: a helper function for `insert_worker`. See `leftgrown` for
+ // details.
+
+ MOZ_NEVER_INLINE Node* rightgrown_right(Node* root) {
+ if (root->getRight()->getTag() == Tag::Right) {
+ root->setTag(Tag::None);
+ root->getRight()->setTag(Tag::None);
+ root = rotate_left(root);
+ } else {
+ switch (root->getRight()->left->getTag()) {
+ case Tag::Right:
+ root->setTag(Tag::Left);
+ root->getRight()->setTag(Tag::None);
+ break;
+ case Tag::Left:
+ root->setTag(Tag::None);
+ root->getRight()->setTag(Tag::Right);
+ break;
+ case Tag::None:
+ root->setTag(Tag::None);
+ root->getRight()->setTag(Tag::None);
+ break;
+ case Tag::Free:
+ default:
+ MOZ_CRASH();
+ }
+ root->getRight()->left->setTag(Tag::None);
+ root->setRight(rotate_right(root->getRight()));
+ root = rotate_left(root);
+ }
+ return root;
+ }
+
+ inline NodeAndResult rightgrown(Node* root) {
+ switch (root->getTag()) {
+ case Tag::Left:
+ root->setTag(Tag::None);
+ return NodeAndResult(root, Result::OK);
+ case Tag::Right:
+ return NodeAndResult(rightgrown_right(root), Result::OK);
+ case Tag::None:
+ root->setTag(Tag::Right);
+ return NodeAndResult(root, Result::Balance);
+ case Tag::Free:
+ default:
+ break;
+ }
+ MOZ_CRASH();
+ }
+
+ // ---- Insertion ------------------------------------------- //
+
+ // Worker for insertion. Allocates a node for `v` and inserts it into the
+ // tree. Returns: nullptr for OOM; (Node*)1 if `v` is a duplicate (per
+ // `C::compare`), in which case the tree is unchanged; otherwise (successful
+ // insertion) the new root. In the latter case, the new `item` field is
+ // initialised from `v`.
+ Node* insert_worker(const T& v) {
+ // Insertion is a two pass process. In the first pass, we descend from
+ // the root, looking for the place in the tree where the new node will go,
+ // and at the same time storing the sequence of visited nodes in a stack.
+ // In the second phase we re-ascend the tree, as guided by the stack,
+ // rebalancing as we go.
+ //
+ // Note, we start from `root_`, but that isn't updated at the end. Instead
+ // the new value is returned to the caller, which has to do the update.
+
+ Node* stack[MAX_TREE_DEPTH];
+ size_t stackPtr = 0; // points to next available slot
+
+#define STACK_ENTRY_SET_IS_LEFT(_nodePtr) \
+ ((Node*)(uintptr_t(_nodePtr) | uintptr_t(1)))
+#define STACK_ENTRY_GET_IS_LEFT(_ent) ((bool)(uintptr_t(_ent) & uintptr_t(1)))
+#define STACK_ENTRY_GET_NODE(_ent) ((Node*)(uintptr_t(_ent) & ~uintptr_t(1)))
+
+ // In the first phase, walk down the tree to find the place where the new
+ // node should be inserted, recording our path in `stack`. This loop has
+ // a factor-of-2 unrolling (the loop body contains two logical iterations)
+ // in order to reduce the overall cost of the stack-overflow check at the
+ // bottom.
+ Node* node = root_;
+ while (true) {
+ // First logical iteration
+ if (!node) {
+ break;
+ }
+ int cmpRes1 = C::compare(v, node->item);
+ if (cmpRes1 < 0) {
+ stack[stackPtr++] = STACK_ENTRY_SET_IS_LEFT(node);
+ node = node->left;
+ } else if (cmpRes1 > 0) {
+ stack[stackPtr++] = node;
+ node = node->getRight();
+ } else {
+ // `v` is already in the tree. Inform the caller, and don't change
+ // the tree.
+ return (Node*)(uintptr_t(1));
+ }
+ // Second logical iteration
+ if (!node) {
+ break;
+ }
+ int cmpRes2 = C::compare(v, node->item);
+ if (cmpRes2 < 0) {
+ stack[stackPtr++] = STACK_ENTRY_SET_IS_LEFT(node);
+ node = node->left;
+ } else if (cmpRes2 > 0) {
+ stack[stackPtr++] = node;
+ node = node->getRight();
+ } else {
+ return (Node*)(uintptr_t(1));
+ }
+ // We're going around again. Ensure there are at least two available
+ // stack slots.
+ MOZ_RELEASE_ASSERT(stackPtr < MAX_TREE_DEPTH - 2);
+ }
+ MOZ_ASSERT(!node);
+
+ // Now allocate the new node.
+ Node* new_node = allocateNode(v);
+ if (!new_node) {
+ return nullptr; // OOM
+ }
+
+ // And unwind the stack, back to the root, rebalancing as we go. Once get
+ // to a place where the new subtree doesn't need to be rebalanced, we can
+ // stop this upward scan, because no nodes above it will need to be
+ // rebalanced either.
+ Node* curr_node = new_node;
+ Result curr_node_action = Result::Balance;
+
+ while (stackPtr > 0) {
+ Node* parent_node_tagged = stack[--stackPtr];
+ Node* parent_node = STACK_ENTRY_GET_NODE(parent_node_tagged);
+ if (STACK_ENTRY_GET_IS_LEFT(parent_node_tagged)) {
+ parent_node->left = curr_node;
+ if (curr_node_action == Result::Balance) {
+ auto pair = leftgrown(parent_node);
+ curr_node = pair.first;
+ curr_node_action = pair.second;
+ } else {
+ curr_node = parent_node;
+ break;
+ }
+ } else {
+ parent_node->setRight(curr_node);
+ if (curr_node_action == Result::Balance) {
+ auto pair = rightgrown(parent_node);
+ curr_node = pair.first;
+ curr_node_action = pair.second;
+ } else {
+ curr_node = parent_node;
+ break;
+ }
+ }
+ }
+
+ if (stackPtr > 0) {
+ curr_node = STACK_ENTRY_GET_NODE(stack[0]);
+ }
+ MOZ_ASSERT(curr_node);
+
+#undef STACK_ENTRY_SET_IS_LEFT
+#undef STACK_ENTRY_GET_IS_LEFT
+#undef STACK_ENTRY_GET_NODE
+ return curr_node;
+ }
+
+ // ---- Helpers for deletion -------------------------------- //
+
+ // `leftshrunk`: a helper function for `delete_worker` and `findlowest`
+ //
+ // Parameters:
+ //
+ // n Pointer to a node. The node's left subtree has just shrunk due to
+ // item removal; its "skew" flag needs adjustment, and the local tree
+ // (the subtree of which this node is the root node) may have become
+ // unbalanced.
+ //
+ // Return values:
+ //
+ // (jseward: apparently some node, but what is it?), plus either:
+ //
+ // OK The parent activation of the delete activation that called
+ // this function may assume the entire tree is valid.
+ //
+ // Balance Do not assume the entire tree is valid.
+
+ NodeAndResult leftshrunk(Node* n) {
+ switch (n->getTag()) {
+ case Tag::Left: {
+ n->setTag(Tag::None);
+ return NodeAndResult(n, Result::Balance);
+ }
+ case Tag::Right: {
+ if (n->getRight()->getTag() == Tag::Right) {
+ n->setTag(Tag::None);
+ n->getRight()->setTag(Tag::None);
+ n = rotate_left(n);
+ return NodeAndResult(n, Result::Balance);
+ } else if (n->getRight()->getTag() == Tag::None) {
+ n->setTag(Tag::Right);
+ n->getRight()->setTag(Tag::Left);
+ n = rotate_left(n);
+ return NodeAndResult(n, Result::OK);
+ } else {
+ switch (n->getRight()->left->getTag()) {
+ case Tag::Left:
+ n->setTag(Tag::None);
+ n->getRight()->setTag(Tag::Right);
+ break;
+ case Tag::Right:
+ n->setTag(Tag::Left);
+ n->getRight()->setTag(Tag::None);
+ break;
+ case Tag::None:
+ n->setTag(Tag::None);
+ n->getRight()->setTag(Tag::None);
+ break;
+ case Tag::Free:
+ default:
+ MOZ_CRASH();
+ }
+ n->getRight()->left->setTag(Tag::None);
+ n->setRight(rotate_right(n->getRight()));
+ ;
+ n = rotate_left(n);
+ return NodeAndResult(n, Result::Balance);
+ }
+ /*NOTREACHED*/ MOZ_CRASH();
+ }
+ case Tag::None: {
+ n->setTag(Tag::Right);
+ return NodeAndResult(n, Result::OK);
+ }
+ case Tag::Free:
+ default: {
+ MOZ_CRASH();
+ }
+ }
+ MOZ_CRASH();
+ }
+
+ // rightshrunk: a helper function for `delete` and `findhighest`. See
+ // `leftshrunk` for details.
+
+ NodeAndResult rightshrunk(Node* n) {
+ switch (n->getTag()) {
+ case Tag::Right: {
+ n->setTag(Tag::None);
+ return NodeAndResult(n, Result::Balance);
+ }
+ case Tag::Left: {
+ if (n->left->getTag() == Tag::Left) {
+ n->setTag(Tag::None);
+ n->left->setTag(Tag::None);
+ n = rotate_right(n);
+ return NodeAndResult(n, Result::Balance);
+ } else if (n->left->getTag() == Tag::None) {
+ n->setTag(Tag::Left);
+ n->left->setTag(Tag::Right);
+ n = rotate_right(n);
+ return NodeAndResult(n, Result::OK);
+ } else {
+ switch (n->left->getRight()->getTag()) {
+ case Tag::Left:
+ n->setTag(Tag::Right);
+ n->left->setTag(Tag::None);
+ break;
+ case Tag::Right:
+ n->setTag(Tag::None);
+ n->left->setTag(Tag::Left);
+ break;
+ case Tag::None:
+ n->setTag(Tag::None);
+ n->left->setTag(Tag::None);
+ break;
+ case Tag::Free:
+ default:
+ MOZ_CRASH();
+ }
+ n->left->getRight()->setTag(Tag::None);
+ n->left = rotate_left(n->left);
+ n = rotate_right(n);
+ return NodeAndResult(n, Result::Balance);
+ }
+ /*NOTREACHED*/ MOZ_CRASH();
+ }
+ case Tag::None: {
+ n->setTag(Tag::Left);
+ return NodeAndResult(n, Result::OK);
+ }
+ case Tag::Free:
+ default: {
+ MOZ_CRASH();
+ }
+ }
+ MOZ_CRASH();
+ }
+
+ // `findhighest`: helper function for `delete_worker`. It replaces a node
+ // with a subtree's greatest (per C::compare) item.
+ //
+ // Parameters:
+ //
+ // target Pointer to node to be replaced.
+ //
+ // n Address of pointer to subtree.
+ //
+ // Return value:
+ //
+ // Nothing The target node could not be replaced because the subtree
+ // provided was empty.
+ //
+ // Some(Node*,Result) jseward: it's pretty unclear, but I *think* it
+ // is a pair that has the same meaning as the
+ // pair returned by `leftgrown`, as described above.
+
+ mozilla::Maybe<NodeAndResult> findhighest(Node* target, Node* n) {
+ if (n == nullptr) {
+ return mozilla::Nothing();
+ }
+ auto res = Result::Balance;
+ if (n->getRight() != nullptr) {
+ auto fhi = findhighest(target, n->getRight());
+ if (fhi.isSome()) {
+ n->setRight(fhi.value().first);
+ res = fhi.value().second;
+ if (res == Result::Balance) {
+ auto pair = rightshrunk(n);
+ n = pair.first;
+ res = pair.second;
+ }
+ return mozilla::Some(NodeAndResult(n, res));
+ } else {
+ return mozilla::Nothing();
+ }
+ }
+ target->item = n->item;
+ Node* tmp = n;
+ n = n->left;
+ freeNode(tmp);
+ return mozilla::Some(NodeAndResult(n, res));
+ }
+
+ // `findhighest`: helper function for `delete_worker`. It replaces a node
+ // with a subtree's greatest (per C::compare) item. See `findhighest` for
+ // details.
+
+ mozilla::Maybe<NodeAndResult> findlowest(Node* target, Node* n) {
+ if (n == nullptr) {
+ return mozilla::Nothing();
+ }
+ Result res = Result::Balance;
+ if (n->left != nullptr) {
+ auto flo = findlowest(target, n->left);
+ if (flo.isSome()) {
+ n->left = flo.value().first;
+ res = flo.value().second;
+ if (res == Result::Balance) {
+ auto pair = leftshrunk(n);
+ n = pair.first;
+ res = pair.second;
+ }
+ return mozilla::Some(NodeAndResult(n, res));
+ } else {
+ return mozilla::Nothing();
+ }
+ }
+ target->item = n->item;
+ Node* tmp = n;
+ n = n->getRight();
+ freeNode(tmp);
+ return mozilla::Some(NodeAndResult(n, res));
+ }
+
+ // ---- Deletion -------------------------------------------- //
+
+ // Deletes the node matching `item` from an arbitrary subtree rooted at
+ // `node`. Returns the root of the new subtree (if any), a `Result` that
+ // indicates that either, the tree containing `node` does or does not need
+ // rebalancing (::Balance, ::OK) or that the item was not found (::Error).
+
+ NodeAndResult delete_worker(Node* node, const T& item) {
+ Result tmp = Result::Balance;
+ if (node == nullptr) {
+ return NodeAndResult(node, Result::Error);
+ }
+
+ int cmp_res = C::compare(item, node->item);
+ if (cmp_res < 0) {
+ auto pair1 = delete_worker(node->left, item);
+ node->left = pair1.first;
+ tmp = pair1.second;
+ if (tmp == Result::Balance) {
+ auto pair2 = leftshrunk(node);
+ node = pair2.first;
+ tmp = pair2.second;
+ }
+ return NodeAndResult(node, tmp);
+ } else if (cmp_res > 0) {
+ auto pair1 = delete_worker(node->getRight(), item);
+ node->setRight(pair1.first);
+ tmp = pair1.second;
+ if (tmp == Result::Balance) {
+ auto pair2 = rightshrunk(node);
+ node = pair2.first;
+ tmp = pair2.second;
+ }
+ return NodeAndResult(node, tmp);
+ } else {
+ if (node->left != nullptr) {
+ auto fhi = findhighest(node, node->left);
+ if (fhi.isSome()) {
+ node->left = fhi.value().first;
+ tmp = fhi.value().second;
+ if (tmp == Result::Balance) {
+ auto pair = leftshrunk(node);
+ node = pair.first;
+ tmp = pair.second;
+ }
+ }
+ return NodeAndResult(node, tmp);
+ }
+ if (node->getRight() != nullptr) {
+ auto flo = findlowest(node, node->getRight());
+ if (flo.isSome()) {
+ node->setRight(flo.value().first);
+ tmp = flo.value().second;
+ if (tmp == Result::Balance) {
+ auto pair = rightshrunk(node);
+ node = pair.first;
+ tmp = pair.second;
+ }
+ }
+ return NodeAndResult(node, tmp);
+ }
+ freeNode(node);
+ return NodeAndResult(nullptr, Result::Balance);
+ }
+ }
+
+ // ---- Lookup ---------------------------------------------- //
+
+ // Find the node matching `v`, or return nullptr if not found.
+ Node* find_worker(const T& v) const {
+ Node* node = root_;
+ while (node) {
+ int cmpRes = C::compare(v, node->item);
+ if (cmpRes < 0) {
+ node = node->left;
+ } else if (cmpRes > 0) {
+ node = node->getRight();
+ } else {
+ return node;
+ }
+ }
+ return nullptr;
+ }
+
+ // ---- Iteration ------------------------------------------- //
+
+ public:
+ // This provides iteration forwards over the tree. You can either iterate
+ // over the whole tree or specify a start point. To iterate over the whole
+ // tree:
+ //
+ // AvlTree<MyT,MyC> tree;
+ // .. put stuff into `tree` ..
+ //
+ // AvlTree<MyT,MyC>::Iter iter(&tree);
+ // while (iter.hasMore) {
+ // MyT item = iter.next();
+ // }
+ //
+ // Alternatively you can initialize the iterator with some value `startAt`,
+ // so that the first value you get is greater than or equal to `startAt`,
+ // per `MyC::compare`:
+ //
+ // AvlTree<MyT,MyC>::Iter iter(&tree, startAt);
+ //
+ // Starting the iterator at a particular value requires finding the value in
+ // the tree and recording the path to it. So it's nearly as cheap as a call
+ // to `AvlTree::contains` and you can use it as a plausible substitute for
+ // `::contains` if you want.
+ //
+ // Note that `class Iter` is quite large -- around 50 machine words -- so
+ // you might want to think twice before allocating instances on the heap.
+ class Iter {
+ const AvlTreeImpl<T, C>* tree_;
+ Node* stack_[MAX_TREE_DEPTH];
+ size_t stackPtr_;
+
+ // This sets up the iterator stack so that the first value it produces
+ // will be the smallest value that is greater than or equal to `v`. Note
+ // the structural similarity to ::find_worker above.
+ //
+ // The logic for pushing nodes on the stack looks strange at first. Once
+ // set up, the stack contains a root-to-some-node path, and the
+ // top-of-stack value is the next value the iterator will emit. If the
+ // stack becomes empty then the iteration is complete.
+ //
+ // It's not quite accurate to say that the stack contains a complete
+ // root-to-some-node path. Rather, the stack contains such a path, except
+ // it omits nodes at which the path goes to the right child. Eg:
+ //
+ // 5
+ // 3 8
+ // 1 4 7 9
+ //
+ // If the next item to be emitted is 4, then the stack will be [5, 4] and
+ // not [5, 3, 4], because at 3 we go right. This explains why the
+ // `cmpRes > 0` case in `setupIteratorStack` doesn't push an item on the
+ // stack. It also explains why the single-argument `Iter::Iter` below,
+ // which sets up for iteration starting at the lowest element, simply
+ // calls `visitLeftChildren` to do its work.
+ void setupIteratorStack(Node* node, const T& v) {
+ // Ensure stackPtr_ is cached in a register, since this function can be
+ // hot.
+ MOZ_ASSERT(stackPtr_ == 0);
+ size_t stackPtr = 0;
+ while (node) {
+ int cmpRes = C::compare(v, node->item);
+ if (cmpRes < 0) {
+ stack_[stackPtr++] = node;
+ MOZ_RELEASE_ASSERT(stackPtr < MAX_TREE_DEPTH);
+ node = node->left;
+ } else if (cmpRes > 0) {
+ node = node->getRight();
+ } else {
+ stack_[stackPtr++] = node;
+ MOZ_RELEASE_ASSERT(stackPtr < MAX_TREE_DEPTH);
+ break;
+ }
+ }
+ stackPtr_ = stackPtr;
+ }
+
+ void visitLeftChildren(Node* node) {
+ while (true) {
+ Node* left = node->left;
+ if (left == nullptr) {
+ break;
+ }
+ stack_[stackPtr_++] = left;
+ MOZ_RELEASE_ASSERT(stackPtr_ < MAX_TREE_DEPTH);
+ node = left;
+ }
+ }
+
+ public:
+ explicit Iter(const AvlTreeImpl<T, C>* tree) {
+ tree_ = tree;
+ stackPtr_ = 0;
+ if (tree->root_ != nullptr) {
+ stack_[stackPtr_++] = tree->root_;
+ MOZ_RELEASE_ASSERT(stackPtr_ < MAX_TREE_DEPTH);
+ visitLeftChildren(tree->root_);
+ }
+ }
+ Iter(const AvlTreeImpl<T, C>* tree, const T& startAt) {
+ tree_ = tree;
+ stackPtr_ = 0;
+ setupIteratorStack(tree_->root_, startAt);
+ }
+ bool hasMore() const { return stackPtr_ > 0; }
+ T next() {
+ MOZ_RELEASE_ASSERT(stackPtr_ > 0);
+ Node* ret = stack_[--stackPtr_];
+ Node* right = ret->getRight();
+ if (right != nullptr) {
+ stack_[stackPtr_++] = right;
+ MOZ_RELEASE_ASSERT(stackPtr_ < MAX_TREE_DEPTH);
+ visitLeftChildren(right);
+ }
+ return ret->item;
+ }
+ };
+};
+
+////////////////////////////////////////////////////////////////////////
+// //
+// AvlTree public interface, for SpiderMonkey. //
+// //
+////////////////////////////////////////////////////////////////////////
+
+// This public interface is fairly limited and restrictive. If you need to
+// add more functionality, consider copying code from `class AvlTreeTestIF` in
+// js/src/jsapi-tests/testAvlTree.cpp rather than rolling your own. See
+// comments there.
+
+template <class T, class C>
+class AvlTree : public AvlTreeImpl<T, C> {
+ // Shorthands for names in the implementation (parent) class.
+ using Impl = AvlTreeImpl<T, C>;
+ using ImplNode = typename AvlTreeImpl<T, C>::Node;
+ using ImplResult = typename AvlTreeImpl<T, C>::Result;
+ using ImplNodeAndResult = typename AvlTreeImpl<T, C>::NodeAndResult;
+
+ public:
+ explicit AvlTree(LifoAlloc* alloc = nullptr) : Impl(alloc) {}
+
+ // You'll need to tell the tree how to allocate nodes, either here or in
+ // `AvlTree::AvlTree`.
+ void setAllocator(LifoAlloc* alloc) { Impl::setAllocator(alloc); }
+
+ // Is the tree empty?
+ bool empty() const { return Impl::root_ == nullptr; }
+
+ // Insert `v` in the tree. Returns false to indicate OOM. `v` may not be
+ // equal to any existing value in the tree, per `C::compare`; if it is, this
+ // routine will MOZ_CRASH(). It would be trivial to change this to replace
+ // an existing value instead, if needed.
+ [[nodiscard]] bool insert(const T& v) {
+ ImplNode* new_root = Impl::insert_worker(v);
+ // Take out both unlikely cases with a single comparison.
+ if (MOZ_UNLIKELY(uintptr_t(new_root) <= uintptr_t(1))) {
+ // OOM (new_root == 0) or duplicate (new_root == 1)
+ if (!new_root) {
+ // OOM
+ return false;
+ }
+ // Duplicate; tree is unchanged.
+ MOZ_CRASH();
+ }
+ Impl::root_ = new_root;
+ return true;
+ }
+
+ // Remove `v` from the tree. `v` must actually be in the tree, per
+ // `C::compare`. If it is not, this routine will MOZ_CRASH().
+ // Superficially it looks like we could change it to return without doing
+ // anything in that case, if needed, except we'd need to first verify that
+ // `delete_worker` doesn't change the tree in that case.
+ void remove(const T& v) {
+ ImplNodeAndResult pair = Impl::delete_worker(Impl::root_, v);
+ ImplNode* new_root = pair.first;
+ ImplResult res = pair.second;
+ if (MOZ_UNLIKELY(res == ImplResult::Error)) {
+ // `v` isn't in the tree.
+ MOZ_CRASH();
+ } else {
+ Impl::root_ = new_root;
+ }
+ }
+
+ // Determine whether the tree contains `v` and if so return, in `res`, a
+ // copy of the stored version. Note that the determination is done using
+ // `C::compare` and you should consider carefully the consequences of
+ // passing in `v` for which `C::compare` indicates "equal" for more than one
+ // value in the tree. This is not invalid, but it does mean that you may be
+ // returned, via `res`, *any* of the values in the tree that `compare` deems
+ // equal to `v`, and which you get is arbitrary -- it depends on which is
+ // closest to the root.
+ bool contains(const T& v, T* res) const {
+ ImplNode* node = Impl::find_worker(v);
+ if (node) {
+ *res = node->item;
+ return true;
+ }
+ return false;
+ }
+
+ // Determine whether the tree contains `v` and if so return the address of
+ // the stored version. The comments on `::contains` about the meaning of
+ // `C::compare` apply here too.
+ T* maybeLookup(const T& v) {
+ ImplNode* node = Impl::find_worker(v);
+ if (node) {
+ return &(node->item);
+ }
+ return nullptr;
+ }
+
+ // AvlTree::Iter is also public; it's just pass-through from AvlTreeImpl.
+ // See documentation above on AvlTree::Iter on how to use it.
+};
+
+} /* namespace js */
+
+#endif /* ds_AvlTree_h */
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-05 08:05:40 +0000