tor-browser

RedBlackTree.h (24239B)

---

/* -*- 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() {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wuninitialized"
   return static_cast<NodeColor>(reinterpret_cast<uintptr_t>(mRightAndColor) &
                                 1);
#pragma GCC diagnostic pop
 }

 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:
 constexpr RedBlackTree() : 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))];

   // Depth always points to the next empty place in mPath.  Therefore
   // mDepth == 0 means there are no items in mPath,
   // mDepth != 0 means that mPath[mDepth-1] is safe to dereference.
   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, Current()); }

   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 Current();
   }

   T* Current() { return mDepth > 0 ? mPath[mDepth - 1].Get() : nullptr; }

   bool NotDone() { return !!mDepth; }
 };

 Iterator iter() { return Iterator(this); }
};

#endif  // RB_H_