summaryrefslogtreecommitdiffstats
path: root/mfbt/SplayTree.h
diff options
context:
space:
mode:
Diffstat (limited to 'mfbt/SplayTree.h')
-rw-r--r--mfbt/SplayTree.h330
1 files changed, 330 insertions, 0 deletions
diff --git a/mfbt/SplayTree.h b/mfbt/SplayTree.h
new file mode 100644
index 000000000..2b3b838bf
--- /dev/null
+++ b/mfbt/SplayTree.h
@@ -0,0 +1,330 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/**
+ * A sorted tree with optimal access times, where recently-accessed elements
+ * are faster to access again.
+ */
+
+#ifndef mozilla_SplayTree_h
+#define mozilla_SplayTree_h
+
+#include "mozilla/Assertions.h"
+#include "mozilla/Attributes.h"
+
+namespace mozilla {
+
+template<class T, class C>
+class SplayTree;
+
+template<typename T>
+class SplayTreeNode
+{
+public:
+ template<class A, class B>
+ friend class SplayTree;
+
+ SplayTreeNode()
+ : mLeft(nullptr)
+ , mRight(nullptr)
+ , mParent(nullptr)
+ {}
+
+private:
+ T* mLeft;
+ T* mRight;
+ T* mParent;
+};
+
+
+/**
+ * Class which represents a splay tree.
+ * Splay trees are balanced binary search trees for which search, insert and
+ * remove are all amortized O(log n), but where accessing a node makes it
+ * faster to access that node in the future.
+ *
+ * T indicates the type of tree elements, Comparator must have a static
+ * compare(const T&, const T&) method ordering the elements. The compare
+ * method must be free from side effects.
+ */
+template<typename T, class Comparator>
+class SplayTree
+{
+ T* mRoot;
+
+public:
+ constexpr SplayTree()
+ : mRoot(nullptr)
+ {}
+
+ bool empty() const
+ {
+ return !mRoot;
+ }
+
+ T* find(const T& aValue)
+ {
+ if (empty()) {
+ return nullptr;
+ }
+
+ T* last = lookup(aValue);
+ splay(last);
+ return Comparator::compare(aValue, *last) == 0 ? last : nullptr;
+ }
+
+ void insert(T* aValue)
+ {
+ MOZ_ASSERT(!find(*aValue), "Duplicate elements are not allowed.");
+
+ if (!mRoot) {
+ mRoot = aValue;
+ return;
+ }
+ T* last = lookup(*aValue);
+ int cmp = Comparator::compare(*aValue, *last);
+
+ finishInsertion(last, cmp, aValue);
+ return;
+ }
+
+ T* findOrInsert(const T& aValue);
+
+ T* remove(const T& aValue)
+ {
+ T* last = lookup(aValue);
+ MOZ_ASSERT(last, "This tree must contain the element being removed.");
+ MOZ_ASSERT(Comparator::compare(aValue, *last) == 0);
+
+ // Splay the tree so that the item to remove is the root.
+ splay(last);
+ MOZ_ASSERT(last == mRoot);
+
+ // Find another node which can be swapped in for the root: either the
+ // rightmost child of the root's left, or the leftmost child of the
+ // root's right.
+ T* swap;
+ T* swapChild;
+ if (mRoot->mLeft) {
+ swap = mRoot->mLeft;
+ while (swap->mRight) {
+ swap = swap->mRight;
+ }
+ swapChild = swap->mLeft;
+ } else if (mRoot->mRight) {
+ swap = mRoot->mRight;
+ while (swap->mLeft) {
+ swap = swap->mLeft;
+ }
+ swapChild = swap->mRight;
+ } else {
+ T* result = mRoot;
+ mRoot = nullptr;
+ return result;
+ }
+
+ // The selected node has at most one child, in swapChild. Detach it
+ // from the subtree by replacing it with that child.
+ if (swap == swap->mParent->mLeft) {
+ swap->mParent->mLeft = swapChild;
+ } else {
+ swap->mParent->mRight = swapChild;
+ }
+ if (swapChild) {
+ swapChild->mParent = swap->mParent;
+ }
+
+ // Make the selected node the new root.
+ mRoot = swap;
+ mRoot->mParent = nullptr;
+ mRoot->mLeft = last->mLeft;
+ mRoot->mRight = last->mRight;
+ if (mRoot->mLeft) {
+ mRoot->mLeft->mParent = mRoot;
+ }
+ if (mRoot->mRight) {
+ mRoot->mRight->mParent = mRoot;
+ }
+
+ return last;
+ }
+
+ T* removeMin()
+ {
+ MOZ_ASSERT(mRoot, "No min to remove!");
+
+ T* min = mRoot;
+ while (min->mLeft) {
+ min = min->mLeft;
+ }
+ return remove(*min);
+ }
+
+ // For testing purposes only.
+ void checkCoherency()
+ {
+ checkCoherency(mRoot, nullptr);
+ }
+
+private:
+ /**
+ * Returns the node in this comparing equal to |aValue|, or a node just
+ * greater or just less than |aValue| if there is no such node.
+ */
+ T* lookup(const T& aValue)
+ {
+ MOZ_ASSERT(!empty());
+
+ T* node = mRoot;
+ T* parent;
+ do {
+ parent = node;
+ int c = Comparator::compare(aValue, *node);
+ if (c == 0) {
+ return node;
+ } else if (c < 0) {
+ node = node->mLeft;
+ } else {
+ node = node->mRight;
+ }
+ } while (node);
+ return parent;
+ }
+
+ void finishInsertion(T* aLast, int32_t aCmp, T* aNew)
+ {
+ MOZ_ASSERT(aCmp, "Nodes shouldn't be equal!");
+
+ T** parentPointer = (aCmp < 0) ? &aLast->mLeft : &aLast->mRight;
+ MOZ_ASSERT(!*parentPointer);
+ *parentPointer = aNew;
+ aNew->mParent = aLast;
+
+ splay(aNew);
+ }
+
+ /**
+ * Rotate the tree until |node| is at the root of the tree. Performing
+ * the rotations in this fashion preserves the amortized balancing of
+ * the tree.
+ */
+ void splay(T* aNode)
+ {
+ MOZ_ASSERT(aNode);
+
+ while (aNode != mRoot) {
+ T* parent = aNode->mParent;
+ if (parent == mRoot) {
+ // Zig rotation.
+ rotate(aNode);
+ MOZ_ASSERT(aNode == mRoot);
+ return;
+ }
+ T* grandparent = parent->mParent;
+ if ((parent->mLeft == aNode) == (grandparent->mLeft == parent)) {
+ // Zig-zig rotation.
+ rotate(parent);
+ rotate(aNode);
+ } else {
+ // Zig-zag rotation.
+ rotate(aNode);
+ rotate(aNode);
+ }
+ }
+ }
+
+ void rotate(T* aNode)
+ {
+ // Rearrange nodes so that aNode becomes the parent of its current
+ // parent, while preserving the sortedness of the tree.
+ T* parent = aNode->mParent;
+ if (parent->mLeft == aNode) {
+ // x y
+ // y c ==> a x
+ // a b b c
+ parent->mLeft = aNode->mRight;
+ if (aNode->mRight) {
+ aNode->mRight->mParent = parent;
+ }
+ aNode->mRight = parent;
+ } else {
+ MOZ_ASSERT(parent->mRight == aNode);
+ // x y
+ // a y ==> x c
+ // b c a b
+ parent->mRight = aNode->mLeft;
+ if (aNode->mLeft) {
+ aNode->mLeft->mParent = parent;
+ }
+ aNode->mLeft = parent;
+ }
+ aNode->mParent = parent->mParent;
+ parent->mParent = aNode;
+ if (T* grandparent = aNode->mParent) {
+ if (grandparent->mLeft == parent) {
+ grandparent->mLeft = aNode;
+ } else {
+ grandparent->mRight = aNode;
+ }
+ } else {
+ mRoot = aNode;
+ }
+ }
+
+ T* checkCoherency(T* aNode, T* aMinimum)
+ {
+ if (mRoot) {
+ MOZ_RELEASE_ASSERT(!mRoot->mParent);
+ }
+ if (!aNode) {
+ MOZ_RELEASE_ASSERT(!mRoot);
+ return nullptr;
+ }
+ if (!aNode->mParent) {
+ MOZ_RELEASE_ASSERT(aNode == mRoot);
+ }
+ if (aMinimum) {
+ MOZ_RELEASE_ASSERT(Comparator::compare(*aMinimum, *aNode) < 0);
+ }
+ if (aNode->mLeft) {
+ MOZ_RELEASE_ASSERT(aNode->mLeft->mParent == aNode);
+ T* leftMaximum = checkCoherency(aNode->mLeft, aMinimum);
+ MOZ_RELEASE_ASSERT(Comparator::compare(*leftMaximum, *aNode) < 0);
+ }
+ if (aNode->mRight) {
+ MOZ_RELEASE_ASSERT(aNode->mRight->mParent == aNode);
+ return checkCoherency(aNode->mRight, aNode);
+ }
+ return aNode;
+ }
+
+ SplayTree(const SplayTree&) = delete;
+ void operator=(const SplayTree&) = delete;
+};
+
+template<typename T, class Comparator>
+T*
+SplayTree<T, Comparator>::findOrInsert(const T& aValue)
+{
+ if (!mRoot) {
+ mRoot = new T(aValue);
+ return mRoot;
+ }
+
+ T* last = lookup(aValue);
+ int cmp = Comparator::compare(aValue, *last);
+ if (!cmp) {
+ return last;
+ }
+
+ T* t = new T(aValue);
+ finishInsertion(last, cmp, t);
+ return t;
+}
+
+} /* namespace mozilla */
+
+#endif /* mozilla_SplayTree_h */
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-23 09:03:50 +0000