The Tor Browser / file revision

 /* -*- 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 T, class C>

 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 <class Op>

     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_<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.

         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 <class Op>

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