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     : mLeft(nullptr)
  32     , mRight(nullptr)
  33     , mParent(nullptr)
  34   {}
  35
  36 private:
  37   T* mLeft;
  38   T* mRight;
  39   T* mParent;
  40 };
  41
  42
  43 /**
  44  * Class which represents a splay tree.
  45  * Splay trees are balanced binary search trees for which search, insert and
  46  * remove are all amortized O(log n), but where accessing a node makes it
  47  * faster to access that node in the future.
  48  *
  49  * T indicates the type of tree elements, Comparator must have a static
  50  * compare(const T&, const T&) method ordering the elements. The compare
  51  * method must be free from side effects.
  52  */
  53 template<typename T, class Comparator>
  54 class SplayTree
  55 {
  56   T* mRoot;
  57
  58 public:
  59   SplayTree()
  60     : mRoot(nullptr)
  61   {}
  62
  63   bool empty() const
  64   {
  65     return !mRoot;
  66   }
  67
  68   T* find(const T& aValue)
  69   {
  70     if (empty()) {
  71       return nullptr;
  72     }
  73
  74     T* last = lookup(aValue);
  75     splay(last);
  76     return Comparator::compare(aValue, *last) == 0 ? last : nullptr;
  77   }
  78
  79   bool insert(T* aValue)
  80   {
  81     MOZ_ASSERT(!find(*aValue), "Duplicate elements are not allowed.");
  82
  83     if (!mRoot) {
  84       mRoot = aValue;
  85       return true;
  86     }
  87     T* last = lookup(*aValue);
  88     int cmp = Comparator::compare(*aValue, *last);
  89
  90     T** parentPointer = (cmp < 0) ? &last->mLeft : &last->mRight;
  91     MOZ_ASSERT(!*parentPointer);
  92     *parentPointer = aValue;
  93     aValue->mParent = last;
  94
  95     splay(aValue);
  96     return true;
  97   }
  98
  99   T* remove(const T& aValue)
 100   {
 101     T* last = lookup(aValue);
 102     MOZ_ASSERT(last, "This tree must contain the element being removed.");
 103     MOZ_ASSERT(Comparator::compare(aValue, *last) == 0);
 104
 105     // Splay the tree so that the item to remove is the root.
 106     splay(last);
 107     MOZ_ASSERT(last == mRoot);
 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 (mRoot->mLeft) {
 115       swap = mRoot->mLeft;
 116       while (swap->mRight) {
 117         swap = swap->mRight;
 118       }
 119       swapChild = swap->mLeft;
 120     } else if (mRoot->mRight) {
 121       swap = mRoot->mRight;
 122       while (swap->mLeft) {
 123         swap = swap->mLeft;
 124       }
 125       swapChild = swap->mRight;
 126     } else {
 127       T* result = mRoot;
 128       mRoot = nullptr;
 129       return result;
 130     }
 131
 132     // The selected node has at most one child, in swapChild. Detach it
 133     // from the subtree by replacing it with that child.
 134     if (swap == swap->mParent->mLeft) {
 135       swap->mParent->mLeft = swapChild;
 136     } else {
 137       swap->mParent->mRight = swapChild;
 138     }
 139     if (swapChild) {
 140       swapChild->mParent = swap->mParent;
 141     }
 142
 143     // Make the selected node the new root.
 144     mRoot = swap;
 145     mRoot->mParent = nullptr;
 146     mRoot->mLeft = last->mLeft;
 147     mRoot->mRight = last->mRight;
 148     if (mRoot->mLeft) {
 149       mRoot->mLeft->mParent = mRoot;
 150     }
 151     if (mRoot->mRight) {
 152       mRoot->mRight->mParent = mRoot;
 153     }
 154
 155     return last;
 156   }
 157
 158   T* removeMin()
 159   {
 160     MOZ_ASSERT(mRoot, "No min to remove!");
 161
 162     T* min = mRoot;
 163     while (min->mLeft) {
 164       min = min->mLeft;
 165     }
 166     return remove(*min);
 167   }
 168
 169   // For testing purposes only.
 170   void checkCoherency()
 171   {
 172     checkCoherency(mRoot, nullptr);
 173   }
 174
 175 private:
 176   /**
 177    * Returns the node in this comparing equal to |aValue|, or a node just
 178    * greater or just less than |aValue| if there is no such node.
 179    */
 180   T* lookup(const T& aValue)
 181   {
 182     MOZ_ASSERT(!empty());
 183
 184     T* node = mRoot;
 185     T* parent;
 186     do {
 187       parent = node;
 188       int c = Comparator::compare(aValue, *node);
 189       if (c == 0) {
 190         return node;
 191       } else if (c < 0) {
 192         node = node->mLeft;
 193       } else {
 194         node = node->mRight;
 195       }
 196     } while (node);
 197     return parent;
 198   }
 199
 200   /**
 201    * Rotate the tree until |node| is at the root of the tree. Performing
 202    * the rotations in this fashion preserves the amortized balancing of
 203    * the tree.
 204    */
 205   void splay(T* aNode)
 206   {
 207     MOZ_ASSERT(aNode);
 208
 209     while (aNode != mRoot) {
 210       T* parent = aNode->mParent;
 211       if (parent == mRoot) {
 212         // Zig rotation.
 213         rotate(aNode);
 214         MOZ_ASSERT(aNode == mRoot);
 215         return;
 216       }
 217       T* grandparent = parent->mParent;
 218       if ((parent->mLeft == aNode) == (grandparent->mLeft == parent)) {
 219         // Zig-zig rotation.
 220         rotate(parent);
 221         rotate(aNode);
 222       } else {
 223         // Zig-zag rotation.
 224         rotate(aNode);
 225         rotate(aNode);
 226       }
 227     }
 228   }
 229
 230   void rotate(T* aNode)
 231   {
 232     // Rearrange nodes so that aNode becomes the parent of its current
 233     // parent, while preserving the sortedness of the tree.
 234     T* parent = aNode->mParent;
 235     if (parent->mLeft == aNode) {
 236       //     x          y
 237       //   y  c  ==>  a  x
 238       //  a b           b c
 239       parent->mLeft = aNode->mRight;
 240       if (aNode->mRight) {
 241         aNode->mRight->mParent = parent;
 242       }
 243       aNode->mRight = parent;
 244     } else {
 245       MOZ_ASSERT(parent->mRight == aNode);
 246       //   x             y
 247       //  a  y   ==>   x  c
 248       //    b c       a b
 249       parent->mRight = aNode->mLeft;
 250       if (aNode->mLeft) {
 251         aNode->mLeft->mParent = parent;
 252       }
 253       aNode->mLeft = parent;
 254     }
 255     aNode->mParent = parent->mParent;
 256     parent->mParent = aNode;
 257     if (T* grandparent = aNode->mParent) {
 258       if (grandparent->mLeft == parent) {
 259         grandparent->mLeft = aNode;
 260       } else {
 261         grandparent->mRight = aNode;
 262       }
 263     } else {
 264       mRoot = aNode;
 265     }
 266   }
 267
 268   T* checkCoherency(T* aNode, T* aMinimum)
 269   {
 270     if (mRoot) {
 271       MOZ_RELEASE_ASSERT(!mRoot->mParent);
 272     }
 273     if (!aNode) {
 274       MOZ_RELEASE_ASSERT(!mRoot);
 275       return nullptr;
 276     }
 277     if (!aNode->mParent) {
 278       MOZ_RELEASE_ASSERT(aNode == mRoot);
 279     }
 280     if (aMinimum) {
 281       MOZ_RELEASE_ASSERT(Comparator::compare(*aMinimum, *aNode) < 0);
 282     }
 283     if (aNode->mLeft) {
 284       MOZ_RELEASE_ASSERT(aNode->mLeft->mParent == aNode);
 285       T* leftMaximum = checkCoherency(aNode->mLeft, aMinimum);
 286       MOZ_RELEASE_ASSERT(Comparator::compare(*leftMaximum, *aNode) < 0);
 287     }
 288     if (aNode->mRight) {
 289       MOZ_RELEASE_ASSERT(aNode->mRight->mParent == aNode);
 290       return checkCoherency(aNode->mRight, aNode);
 291     }
 292     return aNode;
 293   }
 294
 295   SplayTree(const SplayTree&) MOZ_DELETE;
 296   void operator=(const SplayTree&) MOZ_DELETE;
 297 };
 298
 299 }  /* namespace mozilla */
 300
 301 #endif /* mozilla_SplayTree_h */