Bug 822906 - Add SplayTree to mfbt. r=waldo a=akeybl
authorMatt Woodrow <mwoodrow@mozilla.com>
Wed, 16 Jan 2013 12:12:05 +1300
changeset 123376 a3a21c01dab8e715c51b317e7b6834bcc43d8d47
parent 123375 6e334c2290919b369aca1fbd66b52f7a644afd5d
child 123377 7f84bf06751d0b6af1c47d9c7650adf8346e993f
push id273
push userlsblakk@mozilla.com
push dateThu, 14 Feb 2013 23:19:38 +0000
treeherdermozilla-release@c5e807a3f8b8 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswaldo, akeybl
bugs822906
milestone19.0
Bug 822906 - Add SplayTree to mfbt. r=waldo a=akeybl
mfbt/SplayTree.h
mfbt/exported_headers.mk
new file mode 100644
--- /dev/null
+++ b/mfbt/SplayTree.h
@@ -0,0 +1,285 @@
+/* -*- 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/. */
+
+/**
+ * A sorted tree with optimal access times, where recently-accessed elements
+ * are faster to access again.
+ */
+
+#ifndef mozilla_SplayTree_h_
+#define mozilla_SplayTree_h_
+
+#include "mozilla/Assertions.h"
+#include "mozilla/NullPtr.h"
+
+namespace mozilla {
+
+template<class T, class C>
+class SplayTree;
+
+template<typename T>
+class SplayTreeNode
+{
+  public:
+    template<class A, class B>
+    friend class SplayTree;
+
+    SplayTreeNode()
+      : left(nullptr), right(nullptr), parent(nullptr)
+    {}
+
+  private:
+    T* left;
+    T* right;
+    T* parent;
+};
+
+
+/**
+ * Class which represents a splay tree.
+ * Splay trees are balanced binary search trees for which search, insert and
+ * remove are all amortized O(log n), but where accessing a node makes it
+ * faster to access that node in the future.
+ *
+ * T indicates the type of tree elements, Comparator must have a static
+ * compare(const T&, const T&) method ordering the elements. The compare
+ * method must be free from side effects.
+ */
+template<typename T, class Comparator>
+class SplayTree
+{
+    T* root;
+    T* freeList;
+
+  public:
+    SplayTree()
+      : root(nullptr), freeList(nullptr)
+    {}
+
+    bool empty() const {
+      return !root;
+    }
+
+    bool contains(const T& v)
+    {
+      if (empty())
+        return false;
+
+      T* last = lookup(v);
+      splay(last);
+      checkCoherency(root, nullptr);
+      return Comparator::compare(v, *last) == 0;
+    }
+
+    bool insert(T* v)
+    {
+      MOZ_ASSERT(!contains(*v), "Duplicate elements are not allowed.");
+
+      if (!root) {
+        root = v;
+        return true;
+      }
+      T* last = lookup(*v);
+      int cmp = Comparator::compare(*v, *last);
+
+      T** parentPointer = (cmp < 0) ? &last->left : &last->right;
+      MOZ_ASSERT(!*parentPointer);
+      *parentPointer = v;
+      v->parent = last;
+
+      splay(v);
+      checkCoherency(root, nullptr);
+      return true;
+    }
+
+    T* remove(const T& v)
+    {
+      T* last = lookup(v);
+      MOZ_ASSERT(last, "This tree must contain the element being removed.");
+      MOZ_ASSERT(Comparator::compare(v, *last) == 0);
+
+      // Splay the tree so that the item to remove is the root.
+      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.
+      T* swap;
+      T* 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 {
+        T* result = root;
+        root = nullptr;
+        return result;
+      }
+
+      // 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;
+
+      // Make the selected node the new root.
+      root = swap;
+      root->parent = nullptr;
+      root->left = last->left;
+      root->right = last->right;
+      if (root->left) {
+        root->left->parent = root;
+      }
+      if (root->right) {
+        root->right->parent = root;
+      }
+
+      checkCoherency(root, nullptr);
+      return last;
+    }
+
+    T* removeMin()
+    {
+      MOZ_ASSERT(root, "No min to remove!");
+
+      T* min = root;
+      while (min->left)
+        min = min->left;
+      return remove(*min);
+    }
+
+  private:
+    /**
+     * Returns the node in this comparing equal to |v|, or a node just greater or
+     * just less than |v| if there is no such node.
+     */
+    T* lookup(const T& v)
+    {
+      MOZ_ASSERT(!empty());
+
+      T* node = root;
+      T* parent;
+      do {
+        parent = node;
+        int c = Comparator::compare(v, *node);
+        if (c == 0)
+          return node;
+        else if (c < 0)
+          node = node->left;
+        else
+          node = node->right;
+      } while (node);
+      return parent;
+    }
+
+    /**
+     * Rotate the tree until |node| is at the root of the tree. Performing
+     * the rotations in this fashion preserves the amortized balancing of
+     * the tree.
+     */
+    void splay(T* node)
+    {
+      MOZ_ASSERT(node);
+
+      while (node != root) {
+        T* parent = node->parent;
+        if (parent == root) {
+          // Zig rotation.
+          rotate(node);
+          MOZ_ASSERT(node == root);
+          return;
+        }
+        T* 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(T* node)
+    {
+      // Rearrange nodes so that node becomes the parent of its current
+      // parent, while preserving the sortedness of the tree.
+      T* 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 (T* grandparent = node->parent) {
+        if (grandparent->left == parent)
+          grandparent->left = node;
+        else
+          grandparent->right = node;
+      } else {
+        root = node;
+      }
+    }
+
+    T* checkCoherency(T* node, T* minimum)
+    {
+#ifdef DEBUG
+      MOZ_ASSERT_IF(root, !root->parent);
+      if (!node) {
+        MOZ_ASSERT(!root);
+        return nullptr;
+      }
+      MOZ_ASSERT_IF(!node->parent, node == root);
+      MOZ_ASSERT_IF(minimum, Comparator::compare(*minimum, *node) < 0);
+      if (node->left) {
+        MOZ_ASSERT(node->left->parent == node);
+        T* leftMaximum = checkCoherency(node->left, minimum);
+        MOZ_ASSERT(Comparator::compare(*leftMaximum, *node) < 0);
+      }
+      if (node->right) {
+        MOZ_ASSERT(node->right->parent == node);
+        return checkCoherency(node->right, node);
+      }
+      return node;
+#else
+      return nullptr;
+#endif
+    }
+
+    SplayTree(const SplayTree&) MOZ_DELETE;
+    void operator=(const SplayTree&) MOZ_DELETE;
+};
+
+}  /* namespace mozilla */
+
+#endif /* mozilla_SplayTree_h_ */
--- a/mfbt/exported_headers.mk
+++ b/mfbt/exported_headers.mk
@@ -21,16 +21,17 @@ EXPORTS_mozilla += \
   Likely.h \
   LinkedList.h \
   MathAlgorithms.h \
   MSStdInt.h \
   NullPtr.h \
   RangedPtr.h \
   RefPtr.h \
   Scoped.h \
+  SHA1.h \
+  SplayTree.h \
   StandardInteger.h \
-  SHA1.h \
   ThreadLocal.h \
   TypeTraits.h \
   Types.h \
   Util.h \
   WeakPtr.h \
   $(NULL)