Quelle  AvlTree.h   Sprache: C

/* -*- 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 */