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