Bug 821151 - Add splay tree utility class, r=luke.
authorBrian Hackett <bhackett1024@gmail.com>
Fri, 14 Dec 2012 09:53:52 -0700
changeset 125175 e4da3fe4a9da44011eeb29895457f28de4571e80
parent 125174 9d1bb565ab3ad8df0593d1fbbe0d101116da219b
child 125176 15e83fa7017265eadfce80b140385436df5f11e8
push id2151
push userlsblakk@mozilla.com
push dateTue, 19 Feb 2013 18:06:57 +0000
treeherdermozilla-beta@4952e88741ec [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersluke
bugs821151
milestone20.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 821151 - Add splay tree utility class, r=luke.
js/src/ds/SplayTree.h
new file mode 100644
--- /dev/null
+++ b/js/src/ds/SplayTree.h
@@ -0,0 +1,264 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sw=4 et tw=99 ft=cpp:
+ *
+ * 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 jssplaytree_h_
+#define jssplaytree_h_
+
+#include "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.
+ */
+template <class T, class C>
+class SplayTree
+{
+    struct Node {
+        T item;
+        Node *left, *right, *parent;
+
+        Node(const T &item)
+          : item(item), left(NULL), right(NULL), parent(NULL)
+        {}
+    };
+
+    LifoAlloc *alloc;
+    Node *root, *freeList;
+
+    SplayTree(const SplayTree &) MOZ_DELETE;
+    SplayTree &operator=(const SplayTree &) MOZ_DELETE;
+
+  public:
+
+    SplayTree(LifoAlloc *alloc = NULL)
+      : alloc(alloc), root(NULL), freeList(NULL)
+    {}
+
+    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, NULL);
+        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, NULL);
+        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 = NULL;
+            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, NULL);
+    }
+
+  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_<Node>(v);
+    }
+
+    void freeNode(Node *node)
+    {
+        node->item.~T();
+        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;
+        }
+    }
+
+    Node *checkCoherency(Node *node, Node *minimum)
+    {
+#ifdef DEBUG
+        if (!node) {
+            JS_ASSERT(!root);
+            return NULL;
+        }
+        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 NULL;
+#endif
+    }
+};
+
+}  /* namespace js */
+
+#endif /* jssplaytree_h_ */