1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mfbt/SplayTree.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,283 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim: set ts=8 sts=2 et sw=2 tw=80: */
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 +/**
1.11 + * A sorted tree with optimal access times, where recently-accessed elements
1.12 + * are faster to access again.
1.13 + */
1.14 +
1.15 +#ifndef mozilla_SplayTree_h
1.16 +#define mozilla_SplayTree_h
1.17 +
1.18 +#include "mozilla/Assertions.h"
1.19 +#include "mozilla/NullPtr.h"
1.20 +
1.21 +namespace mozilla {
1.22 +
1.23 +template<class T, class C>
1.24 +class SplayTree;
1.25 +
1.26 +template<typename T>
1.27 +class SplayTreeNode
1.28 +{
1.29 + public:
1.30 + template<class A, class B>
1.31 + friend class SplayTree;
1.32 +
1.33 + SplayTreeNode()
1.34 + : left(nullptr), right(nullptr), parent(nullptr)
1.35 + {}
1.36 +
1.37 + private:
1.38 + T* left;
1.39 + T* right;
1.40 + T* parent;
1.41 +};
1.42 +
1.43 +
1.44 +/**
1.45 + * Class which represents a splay tree.
1.46 + * Splay trees are balanced binary search trees for which search, insert and
1.47 + * remove are all amortized O(log n), but where accessing a node makes it
1.48 + * faster to access that node in the future.
1.49 + *
1.50 + * T indicates the type of tree elements, Comparator must have a static
1.51 + * compare(const T&, const T&) method ordering the elements. The compare
1.52 + * method must be free from side effects.
1.53 + */
1.54 +template<typename T, class Comparator>
1.55 +class SplayTree
1.56 +{
1.57 + T* root;
1.58 +
1.59 + public:
1.60 + SplayTree()
1.61 + : root(nullptr)
1.62 + {}
1.63 +
1.64 + bool empty() const {
1.65 + return !root;
1.66 + }
1.67 +
1.68 + T* find(const T& v)
1.69 + {
1.70 + if (empty())
1.71 + return nullptr;
1.72 +
1.73 + T* last = lookup(v);
1.74 + splay(last);
1.75 + checkCoherency(root, nullptr);
1.76 + return Comparator::compare(v, *last) == 0 ? last : nullptr;
1.77 + }
1.78 +
1.79 + bool insert(T* v)
1.80 + {
1.81 + MOZ_ASSERT(!find(*v), "Duplicate elements are not allowed.");
1.82 +
1.83 + if (!root) {
1.84 + root = v;
1.85 + return true;
1.86 + }
1.87 + T* last = lookup(*v);
1.88 + int cmp = Comparator::compare(*v, *last);
1.89 +
1.90 + T** parentPointer = (cmp < 0) ? &last->left : &last->right;
1.91 + MOZ_ASSERT(!*parentPointer);
1.92 + *parentPointer = v;
1.93 + v->parent = last;
1.94 +
1.95 + splay(v);
1.96 + checkCoherency(root, nullptr);
1.97 + return true;
1.98 + }
1.99 +
1.100 + T* remove(const T& v)
1.101 + {
1.102 + T* last = lookup(v);
1.103 + MOZ_ASSERT(last, "This tree must contain the element being removed.");
1.104 + MOZ_ASSERT(Comparator::compare(v, *last) == 0);
1.105 +
1.106 + // Splay the tree so that the item to remove is the root.
1.107 + splay(last);
1.108 + MOZ_ASSERT(last == root);
1.109 +
1.110 + // Find another node which can be swapped in for the root: either the
1.111 + // rightmost child of the root's left, or the leftmost child of the
1.112 + // root's right.
1.113 + T* swap;
1.114 + T* swapChild;
1.115 + if (root->left) {
1.116 + swap = root->left;
1.117 + while (swap->right)
1.118 + swap = swap->right;
1.119 + swapChild = swap->left;
1.120 + } else if (root->right) {
1.121 + swap = root->right;
1.122 + while (swap->left)
1.123 + swap = swap->left;
1.124 + swapChild = swap->right;
1.125 + } else {
1.126 + T* result = root;
1.127 + root = nullptr;
1.128 + return result;
1.129 + }
1.130 +
1.131 + // The selected node has at most one child, in swapChild. Detach it
1.132 + // from the subtree by replacing it with that child.
1.133 + if (swap == swap->parent->left)
1.134 + swap->parent->left = swapChild;
1.135 + else
1.136 + swap->parent->right = swapChild;
1.137 + if (swapChild)
1.138 + swapChild->parent = swap->parent;
1.139 +
1.140 + // Make the selected node the new root.
1.141 + root = swap;
1.142 + root->parent = nullptr;
1.143 + root->left = last->left;
1.144 + root->right = last->right;
1.145 + if (root->left) {
1.146 + root->left->parent = root;
1.147 + }
1.148 + if (root->right) {
1.149 + root->right->parent = root;
1.150 + }
1.151 +
1.152 + checkCoherency(root, nullptr);
1.153 + return last;
1.154 + }
1.155 +
1.156 + T* removeMin()
1.157 + {
1.158 + MOZ_ASSERT(root, "No min to remove!");
1.159 +
1.160 + T* min = root;
1.161 + while (min->left)
1.162 + min = min->left;
1.163 + return remove(*min);
1.164 + }
1.165 +
1.166 + private:
1.167 + /**
1.168 + * Returns the node in this comparing equal to |v|, or a node just greater or
1.169 + * just less than |v| if there is no such node.
1.170 + */
1.171 + T* lookup(const T& v)
1.172 + {
1.173 + MOZ_ASSERT(!empty());
1.174 +
1.175 + T* node = root;
1.176 + T* parent;
1.177 + do {
1.178 + parent = node;
1.179 + int c = Comparator::compare(v, *node);
1.180 + if (c == 0)
1.181 + return node;
1.182 + else if (c < 0)
1.183 + node = node->left;
1.184 + else
1.185 + node = node->right;
1.186 + } while (node);
1.187 + return parent;
1.188 + }
1.189 +
1.190 + /**
1.191 + * Rotate the tree until |node| is at the root of the tree. Performing
1.192 + * the rotations in this fashion preserves the amortized balancing of
1.193 + * the tree.
1.194 + */
1.195 + void splay(T* node)
1.196 + {
1.197 + MOZ_ASSERT(node);
1.198 +
1.199 + while (node != root) {
1.200 + T* parent = node->parent;
1.201 + if (parent == root) {
1.202 + // Zig rotation.
1.203 + rotate(node);
1.204 + MOZ_ASSERT(node == root);
1.205 + return;
1.206 + }
1.207 + T* grandparent = parent->parent;
1.208 + if ((parent->left == node) == (grandparent->left == parent)) {
1.209 + // Zig-zig rotation.
1.210 + rotate(parent);
1.211 + rotate(node);
1.212 + } else {
1.213 + // Zig-zag rotation.
1.214 + rotate(node);
1.215 + rotate(node);
1.216 + }
1.217 + }
1.218 + }
1.219 +
1.220 + void rotate(T* node)
1.221 + {
1.222 + // Rearrange nodes so that node becomes the parent of its current
1.223 + // parent, while preserving the sortedness of the tree.
1.224 + T* parent = node->parent;
1.225 + if (parent->left == node) {
1.226 + // x y
1.227 + // y c ==> a x
1.228 + // a b b c
1.229 + parent->left = node->right;
1.230 + if (node->right)
1.231 + node->right->parent = parent;
1.232 + node->right = parent;
1.233 + } else {
1.234 + MOZ_ASSERT(parent->right == node);
1.235 + // x y
1.236 + // a y ==> x c
1.237 + // b c a b
1.238 + parent->right = node->left;
1.239 + if (node->left)
1.240 + node->left->parent = parent;
1.241 + node->left = parent;
1.242 + }
1.243 + node->parent = parent->parent;
1.244 + parent->parent = node;
1.245 + if (T* grandparent = node->parent) {
1.246 + if (grandparent->left == parent)
1.247 + grandparent->left = node;
1.248 + else
1.249 + grandparent->right = node;
1.250 + } else {
1.251 + root = node;
1.252 + }
1.253 + }
1.254 +
1.255 + T* checkCoherency(T* node, T* minimum)
1.256 + {
1.257 +#ifdef DEBUG
1.258 + MOZ_ASSERT_IF(root, !root->parent);
1.259 + if (!node) {
1.260 + MOZ_ASSERT(!root);
1.261 + return nullptr;
1.262 + }
1.263 + MOZ_ASSERT_IF(!node->parent, node == root);
1.264 + MOZ_ASSERT_IF(minimum, Comparator::compare(*minimum, *node) < 0);
1.265 + if (node->left) {
1.266 + MOZ_ASSERT(node->left->parent == node);
1.267 + T* leftMaximum = checkCoherency(node->left, minimum);
1.268 + MOZ_ASSERT(Comparator::compare(*leftMaximum, *node) < 0);
1.269 + }
1.270 + if (node->right) {
1.271 + MOZ_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 + SplayTree(const SplayTree&) MOZ_DELETE;
1.281 + void operator=(const SplayTree&) MOZ_DELETE;
1.282 +};
1.283 +
1.284 +} /* namespace mozilla */
1.285 +
1.286 +#endif /* mozilla_SplayTree_h */
