The Tor Browser: js/src/ds/SplayTree.h@6474c204b198 (annotated)

js/src/ds/SplayTree.h@6474c204b198 (annotated)

js/src/ds/SplayTree.h

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

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

The Tor Browser / annotate

js/src/ds/SplayTree.h@6474c204b198 (annotated)

js/src/ds/SplayTree.h