Adding upstream version 110.0.1.upstream/110.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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_