diff -r 000000000000 -r 6474c204b198 js/src/ds/SplayTree.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/ds/SplayTree.h Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,280 @@ +/* -*- 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 SplayTree +{ + struct Node { + T item; + Node *left, *right, *parent; + + Node(const T &item) + : item(item), left(nullptr), right(nullptr), parent(nullptr) + {} + }; + + LifoAlloc *alloc; + Node *root, *freeList; + + SplayTree(const SplayTree &) MOZ_DELETE; + SplayTree &operator=(const SplayTree &) MOZ_DELETE; + + public: + + SplayTree(LifoAlloc *alloc = nullptr) + : alloc(alloc), root(nullptr), freeList(nullptr) + {} + + void setAllocator(LifoAlloc *alloc) { + this->alloc = alloc; + } + + bool empty() const { + return !root; + } + + 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; + } + + 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. + JS_ASSERT(cmp); + + Node *&parentPointer = (cmp < 0) ? last->left : last->right; + JS_ASSERT(!parentPointer); + parentPointer = element; + element->parent = last; + + splay(element); + checkCoherency(root, nullptr); + return true; + } + + void remove(const T &v) + { + Node *last = lookup(v); + JS_ASSERT(last && C::compare(v, last->item) == 0); + + splay(last); + JS_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, *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 + void forEach(Op op) + { + forEachInner(op, root); + } + + private: + + Node *lookup(const T &v) + { + JS_ASSERT(root); + Node *node = root, *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_(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. + JS_ASSERT(node); + while (node != root) { + Node *parent = node->parent; + if (parent == root) { + // Zig rotation. + rotate(node); + JS_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 { + JS_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 + void forEachInner(Op op, Node *node) + { + if (!node) + return; + + forEachInner(op, node->left); + op(node->item); + forEachInner(op, node->right); + } + + Node *checkCoherency(Node *node, Node *minimum) + { +#ifdef DEBUG + if (!node) { + JS_ASSERT(!root); + return nullptr; + } + JS_ASSERT_IF(!node->parent, node == root); + JS_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0); + if (node->left) { + JS_ASSERT(node->left->parent == node); + Node *leftMaximum = checkCoherency(node->left, minimum); + JS_ASSERT(C::compare(leftMaximum->item, node->item) < 0); + } + if (node->right) { + JS_ASSERT(node->right->parent == node); + return checkCoherency(node->right, node); + } + return node; +#else + return nullptr; +#endif + } +}; + +} /* namespace js */ + +#endif /* ds_SplayTree_h */