From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- mfbt/SplayTree.h | 305 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 305 insertions(+) create mode 100644 mfbt/SplayTree.h (limited to 'mfbt/SplayTree.h') diff --git a/mfbt/SplayTree.h b/mfbt/SplayTree.h new file mode 100644 index 0000000000..08765c0b11 --- /dev/null +++ b/mfbt/SplayTree.h @@ -0,0 +1,305 @@ +/* -*- 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 SplayTree; + +template +class SplayTreeNode { + public: + template + 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 +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); + } + + 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; + } + + last->mLeft = nullptr; + last->mRight = nullptr; + 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 +T* SplayTree::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 */ -- cgit v1.2.3