diff options
Diffstat (limited to '')
| -rw-r--r-- | memory/build/rb.h | 741 |
1 files changed, 741 insertions, 0 deletions
diff --git a/memory/build/rb.h b/memory/build/rb.h new file mode 100644 index 0000000000..418d206911 --- /dev/null +++ b/memory/build/rb.h @@ -0,0 +1,741 @@ +/* -*- 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/. */ + +// Portions of this file were originally under the following license: +// +// Copyright (C) 2008 Jason Evans <jasone@FreeBSD.org>. +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions +// are met: +// 1. Redistributions of source code must retain the above copyright +// notice(s), this list of conditions and the following disclaimer +// unmodified other than the allowable addition of one or more +// copyright notices. +// 2. Redistributions in binary form must reproduce the above copyright +// notice(s), this list of conditions and the following disclaimer in +// the documentation and/or other materials provided with the +// distribution. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY +// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR +// BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, +// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE +// OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, +// EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +// +// **************************************************************************** +// +// C++ template implementation of left-leaning red-black trees. +// +// All operations are done non-recursively. Parent pointers are not used, and +// color bits are stored in the least significant bit of right-child pointers, +// thus making node linkage as compact as is possible for red-black trees. +// +// The RedBlackTree template expects two type arguments: the type of the nodes, +// containing a RedBlackTreeNode, and a trait providing two methods: +// - a GetTreeNode method that returns a reference to the RedBlackTreeNode +// corresponding to a given node with the following signature: +// static RedBlackTreeNode<T>& GetTreeNode(T*) +// - a Compare function with the following signature: +// static Order Compare(T* aNode, T* aOther) +// ^^^^^ +// or aKey +// +// Interpretation of comparision function return values: +// +// Order::eLess: aNode < aOther +// Order::eEqual: aNode == aOther +// Order::eGreater: aNode > aOther +// +// In all cases, the aNode or aKey argument is the first argument to the +// comparison function, which makes it possible to write comparison functions +// that treat the first argument specially. +// +// *************************************************************************** + +#ifndef RB_H_ +#define RB_H_ + +#include "mozilla/Alignment.h" +#include "mozilla/Assertions.h" +#include "Utils.h" + +enum NodeColor { + Black = 0, + Red = 1, +}; + +// Node structure. +template <typename T> +class RedBlackTreeNode { + T* mLeft; + // The lowest bit is the color + T* mRightAndColor; + + public: + T* Left() { return mLeft; } + + void SetLeft(T* aValue) { mLeft = aValue; } + + T* Right() { + return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(mRightAndColor) & + uintptr_t(~1)); + } + + void SetRight(T* aValue) { + mRightAndColor = reinterpret_cast<T*>( + (reinterpret_cast<uintptr_t>(aValue) & uintptr_t(~1)) | Color()); + } + + NodeColor Color() { + return static_cast<NodeColor>(reinterpret_cast<uintptr_t>(mRightAndColor) & + 1); + } + + bool IsBlack() { return Color() == NodeColor::Black; } + + bool IsRed() { return Color() == NodeColor::Red; } + + void SetColor(NodeColor aColor) { + mRightAndColor = reinterpret_cast<T*>( + (reinterpret_cast<uintptr_t>(mRightAndColor) & uintptr_t(~1)) | aColor); + } +}; + +// Tree structure. +template <typename T, typename Trait> +class RedBlackTree { + public: + void Init() { mRoot = nullptr; } + + T* First(T* aStart = nullptr) { return First(TreeNode(aStart)).Get(); } + + T* Last(T* aStart = nullptr) { return Last(TreeNode(aStart)).Get(); } + + T* Next(T* aNode) { return Next(TreeNode(aNode)).Get(); } + + T* Prev(T* aNode) { return Prev(TreeNode(aNode)).Get(); } + + T* Search(T* aKey) { return Search(TreeNode(aKey)).Get(); } + + // Find a match if it exists. Otherwise, find the next greater node, if one + // exists. + T* SearchOrNext(T* aKey) { return SearchOrNext(TreeNode(aKey)).Get(); } + + void Insert(T* aNode) { Insert(TreeNode(aNode)); } + + void Remove(T* aNode) { Remove(TreeNode(aNode)); } + + // Helper class to avoid having all the tree traversal code further below + // have to use Trait::GetTreeNode and do manual null pointer checks, adding + // visual noise. Practically speaking TreeNode(nullptr) acts as a virtual + // sentinel, that loops back to itself for Left() and Right() and is always + // black. + class TreeNode { + public: + constexpr TreeNode() : mNode(nullptr) {} + + MOZ_IMPLICIT TreeNode(T* aNode) : mNode(aNode) {} + + TreeNode& operator=(TreeNode aOther) { + mNode = aOther.mNode; + return *this; + } + + TreeNode Left() { + return TreeNode(mNode ? Trait::GetTreeNode(mNode).Left() : nullptr); + } + + void SetLeft(TreeNode aNode) { + MOZ_RELEASE_ASSERT(mNode); + Trait::GetTreeNode(mNode).SetLeft(aNode.mNode); + } + + TreeNode Right() { + return TreeNode(mNode ? Trait::GetTreeNode(mNode).Right() : nullptr); + } + + void SetRight(TreeNode aNode) { + MOZ_RELEASE_ASSERT(mNode); + Trait::GetTreeNode(mNode).SetRight(aNode.mNode); + } + + NodeColor Color() { + return mNode ? Trait::GetTreeNode(mNode).Color() : NodeColor::Black; + } + + bool IsRed() { return Color() == NodeColor::Red; } + + bool IsBlack() { return Color() == NodeColor::Black; } + + void SetColor(NodeColor aColor) { + MOZ_RELEASE_ASSERT(mNode); + Trait::GetTreeNode(mNode).SetColor(aColor); + } + + T* Get() { return mNode; } + + MOZ_IMPLICIT operator bool() { return !!mNode; } + + bool operator==(TreeNode& aOther) { return mNode == aOther.mNode; } + + private: + T* mNode; + }; + + private: + // Ideally we'd use a TreeNode for mRoot, but we need RedBlackTree to stay + // a POD type to avoid a static initializer for gArenas. + T* mRoot; + + TreeNode First(TreeNode aStart) { + TreeNode ret; + for (ret = aStart ? aStart : mRoot; ret.Left(); ret = ret.Left()) { + } + return ret; + } + + TreeNode Last(TreeNode aStart) { + TreeNode ret; + for (ret = aStart ? aStart : mRoot; ret.Right(); ret = ret.Right()) { + } + return ret; + } + + TreeNode Next(TreeNode aNode) { + TreeNode ret; + if (aNode.Right()) { + ret = First(aNode.Right()); + } else { + TreeNode rbp_n_t = mRoot; + MOZ_ASSERT(rbp_n_t); + ret = nullptr; + while (true) { + Order rbp_n_cmp = Trait::Compare(aNode.Get(), rbp_n_t.Get()); + if (rbp_n_cmp == Order::eLess) { + ret = rbp_n_t; + rbp_n_t = rbp_n_t.Left(); + } else if (rbp_n_cmp == Order::eGreater) { + rbp_n_t = rbp_n_t.Right(); + } else { + break; + } + MOZ_ASSERT(rbp_n_t); + } + } + return ret; + } + + TreeNode Prev(TreeNode aNode) { + TreeNode ret; + if (aNode.Left()) { + ret = Last(aNode.Left()); + } else { + TreeNode rbp_p_t = mRoot; + MOZ_ASSERT(rbp_p_t); + ret = nullptr; + while (true) { + Order rbp_p_cmp = Trait::Compare(aNode.Get(), rbp_p_t.Get()); + if (rbp_p_cmp == Order::eLess) { + rbp_p_t = rbp_p_t.Left(); + } else if (rbp_p_cmp == Order::eGreater) { + ret = rbp_p_t; + rbp_p_t = rbp_p_t.Right(); + } else { + break; + } + MOZ_ASSERT(rbp_p_t); + } + } + return ret; + } + + TreeNode Search(TreeNode aKey) { + TreeNode ret = mRoot; + Order rbp_se_cmp; + while (ret && (rbp_se_cmp = Trait::Compare(aKey.Get(), ret.Get())) != + Order::eEqual) { + if (rbp_se_cmp == Order::eLess) { + ret = ret.Left(); + } else { + ret = ret.Right(); + } + } + return ret; + } + + TreeNode SearchOrNext(TreeNode aKey) { + TreeNode ret = nullptr; + TreeNode rbp_ns_t = mRoot; + while (rbp_ns_t) { + Order rbp_ns_cmp = Trait::Compare(aKey.Get(), rbp_ns_t.Get()); + if (rbp_ns_cmp == Order::eLess) { + ret = rbp_ns_t; + rbp_ns_t = rbp_ns_t.Left(); + } else if (rbp_ns_cmp == Order::eGreater) { + rbp_ns_t = rbp_ns_t.Right(); + } else { + ret = rbp_ns_t; + break; + } + } + return ret; + } + + void Insert(TreeNode aNode) { + // rbp_i_s is only used as a placeholder for its RedBlackTreeNode. Use + // AlignedStorage2 to avoid running the TreeNode base class constructor. + mozilla::AlignedStorage2<T> rbp_i_s; + TreeNode rbp_i_g, rbp_i_p, rbp_i_c, rbp_i_t, rbp_i_u; + Order rbp_i_cmp = Order::eEqual; + rbp_i_g = nullptr; + rbp_i_p = rbp_i_s.addr(); + rbp_i_p.SetLeft(mRoot); + rbp_i_p.SetRight(nullptr); + rbp_i_p.SetColor(NodeColor::Black); + rbp_i_c = mRoot; + // Iteratively search down the tree for the insertion point, + // splitting 4-nodes as they are encountered. At the end of each + // iteration, rbp_i_g->rbp_i_p->rbp_i_c is a 3-level path down + // the tree, assuming a sufficiently deep tree. + while (rbp_i_c) { + rbp_i_t = rbp_i_c.Left(); + rbp_i_u = rbp_i_t.Left(); + if (rbp_i_t.IsRed() && rbp_i_u.IsRed()) { + // rbp_i_c is the top of a logical 4-node, so split it. + // This iteration does not move down the tree, due to the + // disruptiveness of node splitting. + // + // Rotate right. + rbp_i_t = RotateRight(rbp_i_c); + // Pass red links up one level. + rbp_i_u = rbp_i_t.Left(); + rbp_i_u.SetColor(NodeColor::Black); + if (rbp_i_p.Left() == rbp_i_c) { + rbp_i_p.SetLeft(rbp_i_t); + rbp_i_c = rbp_i_t; + } else { + // rbp_i_c was the right child of rbp_i_p, so rotate + // left in order to maintain the left-leaning invariant. + MOZ_ASSERT(rbp_i_p.Right() == rbp_i_c); + rbp_i_p.SetRight(rbp_i_t); + rbp_i_u = LeanLeft(rbp_i_p); + if (rbp_i_g.Left() == rbp_i_p) { + rbp_i_g.SetLeft(rbp_i_u); + } else { + MOZ_ASSERT(rbp_i_g.Right() == rbp_i_p); + rbp_i_g.SetRight(rbp_i_u); + } + rbp_i_p = rbp_i_u; + rbp_i_cmp = Trait::Compare(aNode.Get(), rbp_i_p.Get()); + if (rbp_i_cmp == Order::eLess) { + rbp_i_c = rbp_i_p.Left(); + } else { + MOZ_ASSERT(rbp_i_cmp == Order::eGreater); + rbp_i_c = rbp_i_p.Right(); + } + continue; + } + } + rbp_i_g = rbp_i_p; + rbp_i_p = rbp_i_c; + rbp_i_cmp = Trait::Compare(aNode.Get(), rbp_i_c.Get()); + if (rbp_i_cmp == Order::eLess) { + rbp_i_c = rbp_i_c.Left(); + } else { + MOZ_ASSERT(rbp_i_cmp == Order::eGreater); + rbp_i_c = rbp_i_c.Right(); + } + } + // rbp_i_p now refers to the node under which to insert. + aNode.SetLeft(nullptr); + aNode.SetRight(nullptr); + aNode.SetColor(NodeColor::Red); + if (rbp_i_cmp == Order::eGreater) { + rbp_i_p.SetRight(aNode); + rbp_i_t = LeanLeft(rbp_i_p); + if (rbp_i_g.Left() == rbp_i_p) { + rbp_i_g.SetLeft(rbp_i_t); + } else if (rbp_i_g.Right() == rbp_i_p) { + rbp_i_g.SetRight(rbp_i_t); + } + } else { + rbp_i_p.SetLeft(aNode); + } + // Update the root and make sure that it is black. + TreeNode root = TreeNode(rbp_i_s.addr()).Left(); + root.SetColor(NodeColor::Black); + mRoot = root.Get(); + } + + void Remove(TreeNode aNode) { + // rbp_r_s is only used as a placeholder for its RedBlackTreeNode. Use + // AlignedStorage2 to avoid running the TreeNode base class constructor. + mozilla::AlignedStorage2<T> rbp_r_s; + TreeNode rbp_r_p, rbp_r_c, rbp_r_xp, rbp_r_t, rbp_r_u; + Order rbp_r_cmp; + rbp_r_p = TreeNode(rbp_r_s.addr()); + rbp_r_p.SetLeft(mRoot); + rbp_r_p.SetRight(nullptr); + rbp_r_p.SetColor(NodeColor::Black); + rbp_r_c = mRoot; + rbp_r_xp = nullptr; + // Iterate down the tree, but always transform 2-nodes to 3- or + // 4-nodes in order to maintain the invariant that the current + // node is not a 2-node. This allows simple deletion once a leaf + // is reached. Handle the root specially though, since there may + // be no way to convert it from a 2-node to a 3-node. + rbp_r_cmp = Trait::Compare(aNode.Get(), rbp_r_c.Get()); + if (rbp_r_cmp == Order::eLess) { + rbp_r_t = rbp_r_c.Left(); + rbp_r_u = rbp_r_t.Left(); + if (rbp_r_t.IsBlack() && rbp_r_u.IsBlack()) { + // Apply standard transform to prepare for left move. + rbp_r_t = MoveRedLeft(rbp_r_c); + rbp_r_t.SetColor(NodeColor::Black); + rbp_r_p.SetLeft(rbp_r_t); + rbp_r_c = rbp_r_t; + } else { + // Move left. + rbp_r_p = rbp_r_c; + rbp_r_c = rbp_r_c.Left(); + } + } else { + if (rbp_r_cmp == Order::eEqual) { + MOZ_ASSERT(aNode == rbp_r_c); + if (!rbp_r_c.Right()) { + // Delete root node (which is also a leaf node). + if (rbp_r_c.Left()) { + rbp_r_t = LeanRight(rbp_r_c); + rbp_r_t.SetRight(nullptr); + } else { + rbp_r_t = nullptr; + } + rbp_r_p.SetLeft(rbp_r_t); + } else { + // This is the node we want to delete, but we will + // instead swap it with its successor and delete the + // successor. Record enough information to do the + // swap later. rbp_r_xp is the aNode's parent. + rbp_r_xp = rbp_r_p; + rbp_r_cmp = Order::eGreater; // Note that deletion is incomplete. + } + } + if (rbp_r_cmp == Order::eGreater) { + if (rbp_r_c.Right().Left().IsBlack()) { + rbp_r_t = rbp_r_c.Left(); + if (rbp_r_t.IsRed()) { + // Standard transform. + rbp_r_t = MoveRedRight(rbp_r_c); + } else { + // Root-specific transform. + rbp_r_c.SetColor(NodeColor::Red); + rbp_r_u = rbp_r_t.Left(); + if (rbp_r_u.IsRed()) { + rbp_r_u.SetColor(NodeColor::Black); + rbp_r_t = RotateRight(rbp_r_c); + rbp_r_u = RotateLeft(rbp_r_c); + rbp_r_t.SetRight(rbp_r_u); + } else { + rbp_r_t.SetColor(NodeColor::Red); + rbp_r_t = RotateLeft(rbp_r_c); + } + } + rbp_r_p.SetLeft(rbp_r_t); + rbp_r_c = rbp_r_t; + } else { + // Move right. + rbp_r_p = rbp_r_c; + rbp_r_c = rbp_r_c.Right(); + } + } + } + if (rbp_r_cmp != Order::eEqual) { + while (true) { + MOZ_ASSERT(rbp_r_p); + rbp_r_cmp = Trait::Compare(aNode.Get(), rbp_r_c.Get()); + if (rbp_r_cmp == Order::eLess) { + rbp_r_t = rbp_r_c.Left(); + if (!rbp_r_t) { + // rbp_r_c now refers to the successor node to + // relocate, and rbp_r_xp/aNode refer to the + // context for the relocation. + if (rbp_r_xp.Left() == aNode) { + rbp_r_xp.SetLeft(rbp_r_c); + } else { + MOZ_ASSERT(rbp_r_xp.Right() == (aNode)); + rbp_r_xp.SetRight(rbp_r_c); + } + rbp_r_c.SetLeft(aNode.Left()); + rbp_r_c.SetRight(aNode.Right()); + rbp_r_c.SetColor(aNode.Color()); + if (rbp_r_p.Left() == rbp_r_c) { + rbp_r_p.SetLeft(nullptr); + } else { + MOZ_ASSERT(rbp_r_p.Right() == rbp_r_c); + rbp_r_p.SetRight(nullptr); + } + break; + } + rbp_r_u = rbp_r_t.Left(); + if (rbp_r_t.IsBlack() && rbp_r_u.IsBlack()) { + rbp_r_t = MoveRedLeft(rbp_r_c); + if (rbp_r_p.Left() == rbp_r_c) { + rbp_r_p.SetLeft(rbp_r_t); + } else { + rbp_r_p.SetRight(rbp_r_t); + } + rbp_r_c = rbp_r_t; + } else { + rbp_r_p = rbp_r_c; + rbp_r_c = rbp_r_c.Left(); + } + } else { + // Check whether to delete this node (it has to be + // the correct node and a leaf node). + if (rbp_r_cmp == Order::eEqual) { + MOZ_ASSERT(aNode == rbp_r_c); + if (!rbp_r_c.Right()) { + // Delete leaf node. + if (rbp_r_c.Left()) { + rbp_r_t = LeanRight(rbp_r_c); + rbp_r_t.SetRight(nullptr); + } else { + rbp_r_t = nullptr; + } + if (rbp_r_p.Left() == rbp_r_c) { + rbp_r_p.SetLeft(rbp_r_t); + } else { + rbp_r_p.SetRight(rbp_r_t); + } + break; + } + // This is the node we want to delete, but we + // will instead swap it with its successor + // and delete the successor. Record enough + // information to do the swap later. + // rbp_r_xp is aNode's parent. + rbp_r_xp = rbp_r_p; + } + rbp_r_t = rbp_r_c.Right(); + rbp_r_u = rbp_r_t.Left(); + if (rbp_r_u.IsBlack()) { + rbp_r_t = MoveRedRight(rbp_r_c); + if (rbp_r_p.Left() == rbp_r_c) { + rbp_r_p.SetLeft(rbp_r_t); + } else { + rbp_r_p.SetRight(rbp_r_t); + } + rbp_r_c = rbp_r_t; + } else { + rbp_r_p = rbp_r_c; + rbp_r_c = rbp_r_c.Right(); + } + } + } + } + // Update root. + mRoot = TreeNode(rbp_r_s.addr()).Left().Get(); + aNode.SetLeft(nullptr); + aNode.SetRight(nullptr); + aNode.SetColor(NodeColor::Black); + } + + TreeNode RotateLeft(TreeNode aNode) { + TreeNode node = aNode.Right(); + aNode.SetRight(node.Left()); + node.SetLeft(aNode); + return node; + } + + TreeNode RotateRight(TreeNode aNode) { + TreeNode node = aNode.Left(); + aNode.SetLeft(node.Right()); + node.SetRight(aNode); + return node; + } + + TreeNode LeanLeft(TreeNode aNode) { + TreeNode node = RotateLeft(aNode); + NodeColor color = aNode.Color(); + node.SetColor(color); + aNode.SetColor(NodeColor::Red); + return node; + } + + TreeNode LeanRight(TreeNode aNode) { + TreeNode node = RotateRight(aNode); + NodeColor color = aNode.Color(); + node.SetColor(color); + aNode.SetColor(NodeColor::Red); + return node; + } + + TreeNode MoveRedLeft(TreeNode aNode) { + TreeNode node; + TreeNode rbp_mrl_t, rbp_mrl_u; + rbp_mrl_t = aNode.Left(); + rbp_mrl_t.SetColor(NodeColor::Red); + rbp_mrl_t = aNode.Right(); + rbp_mrl_u = rbp_mrl_t.Left(); + if (rbp_mrl_u.IsRed()) { + rbp_mrl_u = RotateRight(rbp_mrl_t); + aNode.SetRight(rbp_mrl_u); + node = RotateLeft(aNode); + rbp_mrl_t = aNode.Right(); + if (rbp_mrl_t.IsRed()) { + rbp_mrl_t.SetColor(NodeColor::Black); + aNode.SetColor(NodeColor::Red); + rbp_mrl_t = RotateLeft(aNode); + node.SetLeft(rbp_mrl_t); + } else { + aNode.SetColor(NodeColor::Black); + } + } else { + aNode.SetColor(NodeColor::Red); + node = RotateLeft(aNode); + } + return node; + } + + TreeNode MoveRedRight(TreeNode aNode) { + TreeNode node; + TreeNode rbp_mrr_t; + rbp_mrr_t = aNode.Left(); + if (rbp_mrr_t.IsRed()) { + TreeNode rbp_mrr_u, rbp_mrr_v; + rbp_mrr_u = rbp_mrr_t.Right(); + rbp_mrr_v = rbp_mrr_u.Left(); + if (rbp_mrr_v.IsRed()) { + rbp_mrr_u.SetColor(aNode.Color()); + rbp_mrr_v.SetColor(NodeColor::Black); + rbp_mrr_u = RotateLeft(rbp_mrr_t); + aNode.SetLeft(rbp_mrr_u); + node = RotateRight(aNode); + rbp_mrr_t = RotateLeft(aNode); + node.SetRight(rbp_mrr_t); + } else { + rbp_mrr_t.SetColor(aNode.Color()); + rbp_mrr_u.SetColor(NodeColor::Red); + node = RotateRight(aNode); + rbp_mrr_t = RotateLeft(aNode); + node.SetRight(rbp_mrr_t); + } + aNode.SetColor(NodeColor::Red); + } else { + rbp_mrr_t.SetColor(NodeColor::Red); + rbp_mrr_t = rbp_mrr_t.Left(); + if (rbp_mrr_t.IsRed()) { + rbp_mrr_t.SetColor(NodeColor::Black); + node = RotateRight(aNode); + rbp_mrr_t = RotateLeft(aNode); + node.SetRight(rbp_mrr_t); + } else { + node = RotateLeft(aNode); + } + } + return node; + } + + // The iterator simulates recursion via an array of pointers that store the + // current path. This is critical to performance, since a series of calls to + // rb_{next,prev}() would require time proportional to (n lg n), whereas this + // implementation only requires time proportional to (n). + // + // Since the iterator caches a path down the tree, any tree modification may + // cause the cached path to become invalid. Don't modify the tree during an + // iteration. + + // Size the path arrays such that they are always large enough, even if a + // tree consumes all of memory. Since each node must contain a minimum of + // two pointers, there can never be more nodes than: + // + // 1 << ((sizeof(void*)<<3) - (log2(sizeof(void*))+1)) + // + // Since the depth of a tree is limited to 3*lg(#nodes), the maximum depth + // is: + // + // (3 * ((sizeof(void*)<<3) - (log2(sizeof(void*))+1))) + // + // This works out to a maximum depth of 87 and 180 for 32- and 64-bit + // systems, respectively (approximately 348 and 1440 bytes, respectively). + public: + class Iterator { + TreeNode mPath[3 * ((sizeof(void*) << 3) - (LOG2(sizeof(void*)) + 1))]; + unsigned mDepth; + + public: + explicit Iterator(RedBlackTree<T, Trait>* aTree) : mDepth(0) { + // Initialize the path to contain the left spine. + if (aTree->mRoot) { + TreeNode node; + mPath[mDepth++] = aTree->mRoot; + while ((node = mPath[mDepth - 1].Left())) { + mPath[mDepth++] = node; + } + } + } + + template <typename Iterator> + class Item { + Iterator* mIterator; + T* mItem; + + public: + Item(Iterator* aIterator, T* aItem) + : mIterator(aIterator), mItem(aItem) {} + + bool operator!=(const Item& aOther) const { + return (mIterator != aOther.mIterator) || (mItem != aOther.mItem); + } + + T* operator*() const { return mItem; } + + const Item& operator++() { + mItem = mIterator->Next(); + return *this; + } + }; + + Item<Iterator> begin() { + return Item<Iterator>(this, + mDepth > 0 ? mPath[mDepth - 1].Get() : nullptr); + } + + Item<Iterator> end() { return Item<Iterator>(this, nullptr); } + + T* Next() { + TreeNode node; + if ((node = mPath[mDepth - 1].Right())) { + // The successor is the left-most node in the right subtree. + mPath[mDepth++] = node; + while ((node = mPath[mDepth - 1].Left())) { + mPath[mDepth++] = node; + } + } else { + // The successor is above the current node. Unwind until a + // left-leaning edge is removed from the path, of the path is empty. + for (mDepth--; mDepth > 0; mDepth--) { + if (mPath[mDepth - 1].Left() == mPath[mDepth]) { + break; + } + } + } + return mDepth > 0 ? mPath[mDepth - 1].Get() : nullptr; + } + }; + + Iterator iter() { return Iterator(this); } +}; + +#endif // RB_H_ |