mfbt/SplayTree.h

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