path: root/js/src/ds/SplayTree.h

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