mfbt/SplayTree.h

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  * vim: set ts=8 sw=4 et tw=99 ft=cpp:
   3  *
   4  * This Source Code Form is subject to the terms of the Mozilla Public
   5  * License, v. 2.0. If a copy of the MPL was not distributed with this
   6  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   7
   8 /**
   9  * A sorted tree with optimal access times, where recently-accessed elements
  10  * are faster to access again.
  11  */
  12
  13 #ifndef mozilla_SplayTree_h_
  14 #define mozilla_SplayTree_h_
  15
  16 #include "mozilla/Assertions.h"
  17 #include "mozilla/NullPtr.h"
  18
  19 namespace mozilla {
  20
  21 template<class T, class C>
  22 class SplayTree;
  23
  24 template<typename T>
  25 class SplayTreeNode
  26 {
  27   public:
  28     template<class A, class B>
  29     friend class SplayTree;
  30
  31     SplayTreeNode()
  32       : left(nullptr), right(nullptr), parent(nullptr)
  33     {}
  34
  35   private:
  36     T* left;
  37     T* right;
  38     T* parent;
  39 };
  40
  41
  42 /**
  43  * Class which represents a splay tree.
  44  * Splay trees are balanced binary search trees for which search, insert and
  45  * remove are all amortized O(log n), but where accessing a node makes it
  46  * faster to access that node in the future.
  47  *
  48  * T indicates the type of tree elements, Comparator must have a static
  49  * compare(const T&, const T&) method ordering the elements. The compare
  50  * method must be free from side effects.
  51  */
  52 template<typename T, class Comparator>
  53 class SplayTree
  54 {
  55     T* root;
  56     T* freeList;
  57
  58   public:
  59     SplayTree()
  60       : root(nullptr), freeList(nullptr)
  61     {}
  62
  63     bool empty() const {
  64       return !root;
  65     }
  66
  67     bool contains(const T& v)
  68     {
  69       if (empty())
  70         return false;
  71
  72       T* last = lookup(v);
  73       splay(last);
  74       checkCoherency(root, nullptr);
  75       return Comparator::compare(v, *last) == 0;
  76     }
  77
  78     bool insert(T* v)
  79     {
  80       MOZ_ASSERT(!contains(*v), "Duplicate elements are not allowed.");
  81
  82       if (!root) {
  83         root = v;
  84         return true;
  85       }
  86       T* last = lookup(*v);
  87       int cmp = Comparator::compare(*v, *last);
  88
  89       T** parentPointer = (cmp < 0) ? &last->left : &last->right;
  90       MOZ_ASSERT(!*parentPointer);
  91       *parentPointer = v;
  92       v->parent = last;
  93
  94       splay(v);
  95       checkCoherency(root, nullptr);
  96       return true;
  97     }
  98
  99     T* remove(const T& v)
 100     {
 101       T* last = lookup(v);
 102       MOZ_ASSERT(last, "This tree must contain the element being removed.");
 103       MOZ_ASSERT(Comparator::compare(v, *last) == 0);
 104
 105       // Splay the tree so that the item to remove is the root.
 106       splay(last);
 107       MOZ_ASSERT(last == root);
 108
 109       // Find another node which can be swapped in for the root: either the
 110       // rightmost child of the root's left, or the leftmost child of the
 111       // root's right.
 112       T* swap;
 113       T* swapChild;
 114       if (root->left) {
 115         swap = root->left;
 116         while (swap->right)
 117           swap = swap->right;
 118         swapChild = swap->left;
 119       } else if (root->right) {
 120         swap = root->right;
 121         while (swap->left)
 122           swap = swap->left;
 123         swapChild = swap->right;
 124       } else {
 125         T* result = root;
 126         root = nullptr;
 127         return result;
 128       }
 129
 130       // The selected node has at most one child, in swapChild. Detach it
 131       // from the subtree by replacing it with that child.
 132       if (swap == swap->parent->left)
 133         swap->parent->left = swapChild;
 134       else
 135         swap->parent->right = swapChild;
 136       if (swapChild)
 137         swapChild->parent = swap->parent;
 138
 139       // Make the selected node the new root.
 140       root = swap;
 141       root->parent = nullptr;
 142       root->left = last->left;
 143       root->right = last->right;
 144       if (root->left) {
 145         root->left->parent = root;
 146       }
 147       if (root->right) {
 148         root->right->parent = root;
 149       }
 150
 151       checkCoherency(root, nullptr);
 152       return last;
 153     }
 154
 155     T* removeMin()
 156     {
 157       MOZ_ASSERT(root, "No min to remove!");
 158
 159       T* min = root;
 160       while (min->left)
 161         min = min->left;
 162       return remove(*min);
 163     }
 164
 165   private:
 166     /**
 167      * Returns the node in this comparing equal to |v|, or a node just greater or
 168      * just less than |v| if there is no such node.
 169      */
 170     T* lookup(const T& v)
 171     {
 172       MOZ_ASSERT(!empty());
 173
 174       T* node = root;
 175       T* parent;
 176       do {
 177         parent = node;
 178         int c = Comparator::compare(v, *node);
 179         if (c == 0)
 180           return node;
 181         else if (c < 0)
 182           node = node->left;
 183         else
 184           node = node->right;
 185       } while (node);
 186       return parent;
 187     }
 188
 189     /**
 190      * Rotate the tree until |node| is at the root of the tree. Performing
 191      * the rotations in this fashion preserves the amortized balancing of
 192      * the tree.
 193      */
 194     void splay(T* node)
 195     {
 196       MOZ_ASSERT(node);
 197
 198       while (node != root) {
 199         T* parent = node->parent;
 200         if (parent == root) {
 201           // Zig rotation.
 202           rotate(node);
 203           MOZ_ASSERT(node == root);
 204           return;
 205         }
 206         T* grandparent = parent->parent;
 207         if ((parent->left == node) == (grandparent->left == parent)) {
 208           // Zig-zig rotation.
 209           rotate(parent);
 210           rotate(node);
 211         } else {
 212           // Zig-zag rotation.
 213           rotate(node);
 214           rotate(node);
 215         }
 216       }
 217     }
 218
 219     void rotate(T* node)
 220     {
 221       // Rearrange nodes so that node becomes the parent of its current
 222       // parent, while preserving the sortedness of the tree.
 223       T* parent = node->parent;
 224       if (parent->left == node) {
 225         //     x          y
 226         //   y  c  ==>  a  x
 227         //  a b           b c
 228         parent->left = node->right;
 229         if (node->right)
 230           node->right->parent = parent;
 231         node->right = parent;
 232       } else {
 233         MOZ_ASSERT(parent->right == node);
 234         //   x             y
 235         //  a  y   ==>   x  c
 236         //    b c       a b
 237         parent->right = node->left;
 238         if (node->left)
 239           node->left->parent = parent;
 240         node->left = parent;
 241       }
 242       node->parent = parent->parent;
 243       parent->parent = node;
 244       if (T* grandparent = node->parent) {
 245         if (grandparent->left == parent)
 246           grandparent->left = node;
 247         else
 248           grandparent->right = node;
 249       } else {
 250         root = node;
 251       }
 252     }
 253
 254     T* checkCoherency(T* node, T* minimum)
 255     {
 256 #ifdef DEBUG
 257       MOZ_ASSERT_IF(root, !root->parent);
 258       if (!node) {
 259         MOZ_ASSERT(!root);
 260         return nullptr;
 261       }
 262       MOZ_ASSERT_IF(!node->parent, node == root);
 263       MOZ_ASSERT_IF(minimum, Comparator::compare(*minimum, *node) < 0);
 264       if (node->left) {
 265         MOZ_ASSERT(node->left->parent == node);
 266         T* leftMaximum = checkCoherency(node->left, minimum);
 267         MOZ_ASSERT(Comparator::compare(*leftMaximum, *node) < 0);
 268       }
 269       if (node->right) {
 270         MOZ_ASSERT(node->right->parent == node);
 271         return checkCoherency(node->right, node);
 272       }
 273       return node;
 274 #else
 275       return nullptr;
 276 #endif
 277     }
 278
 279     SplayTree(const SplayTree&) MOZ_DELETE;
 280     void operator=(const SplayTree&) MOZ_DELETE;
 281 };
 282
 283 }  /* namespace mozilla */
 284
 285 #endif /* mozilla_SplayTree_h_ */