1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/ds/SplayTree.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,280 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef ds_SplayTree_h
1.11 +#define ds_SplayTree_h
1.12 +
1.13 +#include "ds/LifoAlloc.h"
1.14 +
1.15 +namespace js {
1.16 +
1.17 +/*
1.18 + * Class which represents a splay tree with nodes allocated from a LifoAlloc.
1.19 + * Splay trees are balanced binary search trees for which search, insert and
1.20 + * remove are all amortized O(log n).
1.21 + *
1.22 + * T indicates the type of tree elements, C must have a static
1.23 + * compare(const T&, const T&) method ordering the elements. As for LifoAlloc
1.24 + * objects, T objects stored in the tree will not be explicitly destroyed.
1.25 + */
1.26 +template <class T, class C>
1.27 +class SplayTree
1.28 +{
1.29 + struct Node {
1.30 + T item;
1.31 + Node *left, *right, *parent;
1.32 +
1.33 + Node(const T &item)
1.34 + : item(item), left(nullptr), right(nullptr), parent(nullptr)
1.35 + {}
1.36 + };
1.37 +
1.38 + LifoAlloc *alloc;
1.39 + Node *root, *freeList;
1.40 +
1.41 + SplayTree(const SplayTree &) MOZ_DELETE;
1.42 + SplayTree &operator=(const SplayTree &) MOZ_DELETE;
1.43 +
1.44 + public:
1.45 +
1.46 + SplayTree(LifoAlloc *alloc = nullptr)
1.47 + : alloc(alloc), root(nullptr), freeList(nullptr)
1.48 + {}
1.49 +
1.50 + void setAllocator(LifoAlloc *alloc) {
1.51 + this->alloc = alloc;
1.52 + }
1.53 +
1.54 + bool empty() const {
1.55 + return !root;
1.56 + }
1.57 +
1.58 + bool contains(const T &v, T *res)
1.59 + {
1.60 + if (!root)
1.61 + return false;
1.62 + Node *last = lookup(v);
1.63 + splay(last);
1.64 + checkCoherency(root, nullptr);
1.65 + if (C::compare(v, last->item) == 0) {
1.66 + *res = last->item;
1.67 + return true;
1.68 + }
1.69 + return false;
1.70 + }
1.71 +
1.72 + bool insert(const T &v)
1.73 + {
1.74 + Node *element = allocateNode(v);
1.75 + if (!element)
1.76 + return false;
1.77 +
1.78 + if (!root) {
1.79 + root = element;
1.80 + return true;
1.81 + }
1.82 + Node *last = lookup(v);
1.83 + int cmp = C::compare(v, last->item);
1.84 +
1.85 + // Don't tolerate duplicate elements.
1.86 + JS_ASSERT(cmp);
1.87 +
1.88 + Node *&parentPointer = (cmp < 0) ? last->left : last->right;
1.89 + JS_ASSERT(!parentPointer);
1.90 + parentPointer = element;
1.91 + element->parent = last;
1.92 +
1.93 + splay(element);
1.94 + checkCoherency(root, nullptr);
1.95 + return true;
1.96 + }
1.97 +
1.98 + void remove(const T &v)
1.99 + {
1.100 + Node *last = lookup(v);
1.101 + JS_ASSERT(last && C::compare(v, last->item) == 0);
1.102 +
1.103 + splay(last);
1.104 + JS_ASSERT(last == root);
1.105 +
1.106 + // Find another node which can be swapped in for the root: either the
1.107 + // rightmost child of the root's left, or the leftmost child of the
1.108 + // root's right.
1.109 + Node *swap, *swapChild;
1.110 + if (root->left) {
1.111 + swap = root->left;
1.112 + while (swap->right)
1.113 + swap = swap->right;
1.114 + swapChild = swap->left;
1.115 + } else if (root->right) {
1.116 + swap = root->right;
1.117 + while (swap->left)
1.118 + swap = swap->left;
1.119 + swapChild = swap->right;
1.120 + } else {
1.121 + freeNode(root);
1.122 + root = nullptr;
1.123 + return;
1.124 + }
1.125 +
1.126 + // The selected node has at most one child, in swapChild. Detach it
1.127 + // from the subtree by replacing it with that child.
1.128 + if (swap == swap->parent->left)
1.129 + swap->parent->left = swapChild;
1.130 + else
1.131 + swap->parent->right = swapChild;
1.132 + if (swapChild)
1.133 + swapChild->parent = swap->parent;
1.134 +
1.135 + root->item = swap->item;
1.136 + freeNode(swap);
1.137 +
1.138 + checkCoherency(root, nullptr);
1.139 + }
1.140 +
1.141 + template <class Op>
1.142 + void forEach(Op op)
1.143 + {
1.144 + forEachInner(op, root);
1.145 + }
1.146 +
1.147 + private:
1.148 +
1.149 + Node *lookup(const T &v)
1.150 + {
1.151 + JS_ASSERT(root);
1.152 + Node *node = root, *parent;
1.153 + do {
1.154 + parent = node;
1.155 + int c = C::compare(v, node->item);
1.156 + if (c == 0)
1.157 + return node;
1.158 + else if (c < 0)
1.159 + node = node->left;
1.160 + else
1.161 + node = node->right;
1.162 + } while (node);
1.163 + return parent;
1.164 + }
1.165 +
1.166 + Node *allocateNode(const T &v)
1.167 + {
1.168 + Node *node = freeList;
1.169 + if (node) {
1.170 + freeList = node->left;
1.171 + new(node) Node(v);
1.172 + return node;
1.173 + }
1.174 + return alloc->new_<Node>(v);
1.175 + }
1.176 +
1.177 + void freeNode(Node *node)
1.178 + {
1.179 + node->left = freeList;
1.180 + freeList = node;
1.181 + }
1.182 +
1.183 + void splay(Node *node)
1.184 + {
1.185 + // Rotate the element until it is at the root of the tree. Performing
1.186 + // the rotations in this fashion preserves the amortized balancing of
1.187 + // the tree.
1.188 + JS_ASSERT(node);
1.189 + while (node != root) {
1.190 + Node *parent = node->parent;
1.191 + if (parent == root) {
1.192 + // Zig rotation.
1.193 + rotate(node);
1.194 + JS_ASSERT(node == root);
1.195 + return;
1.196 + }
1.197 + Node *grandparent = parent->parent;
1.198 + if ((parent->left == node) == (grandparent->left == parent)) {
1.199 + // Zig-zig rotation.
1.200 + rotate(parent);
1.201 + rotate(node);
1.202 + } else {
1.203 + // Zig-zag rotation.
1.204 + rotate(node);
1.205 + rotate(node);
1.206 + }
1.207 + }
1.208 + }
1.209 +
1.210 + void rotate(Node *node)
1.211 + {
1.212 + // Rearrange nodes so that node becomes the parent of its current
1.213 + // parent, while preserving the sortedness of the tree.
1.214 + Node *parent = node->parent;
1.215 + if (parent->left == node) {
1.216 + // x y
1.217 + // y c ==> a x
1.218 + // a b b c
1.219 + parent->left = node->right;
1.220 + if (node->right)
1.221 + node->right->parent = parent;
1.222 + node->right = parent;
1.223 + } else {
1.224 + JS_ASSERT(parent->right == node);
1.225 + // x y
1.226 + // a y ==> x c
1.227 + // b c a b
1.228 + parent->right = node->left;
1.229 + if (node->left)
1.230 + node->left->parent = parent;
1.231 + node->left = parent;
1.232 + }
1.233 + node->parent = parent->parent;
1.234 + parent->parent = node;
1.235 + if (Node *grandparent = node->parent) {
1.236 + if (grandparent->left == parent)
1.237 + grandparent->left = node;
1.238 + else
1.239 + grandparent->right = node;
1.240 + } else {
1.241 + root = node;
1.242 + }
1.243 + }
1.244 +
1.245 + template <class Op>
1.246 + void forEachInner(Op op, Node *node)
1.247 + {
1.248 + if (!node)
1.249 + return;
1.250 +
1.251 + forEachInner(op, node->left);
1.252 + op(node->item);
1.253 + forEachInner(op, node->right);
1.254 + }
1.255 +
1.256 + Node *checkCoherency(Node *node, Node *minimum)
1.257 + {
1.258 +#ifdef DEBUG
1.259 + if (!node) {
1.260 + JS_ASSERT(!root);
1.261 + return nullptr;
1.262 + }
1.263 + JS_ASSERT_IF(!node->parent, node == root);
1.264 + JS_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0);
1.265 + if (node->left) {
1.266 + JS_ASSERT(node->left->parent == node);
1.267 + Node *leftMaximum = checkCoherency(node->left, minimum);
1.268 + JS_ASSERT(C::compare(leftMaximum->item, node->item) < 0);
1.269 + }
1.270 + if (node->right) {
1.271 + JS_ASSERT(node->right->parent == node);
1.272 + return checkCoherency(node->right, node);
1.273 + }
1.274 + return node;
1.275 +#else
1.276 + return nullptr;
1.277 +#endif
1.278 + }
1.279 +};
1.280 +
1.281 +} /* namespace js */
1.282 +
1.283 +#endif /* ds_SplayTree_h */
