Bug 1403444 - Replace rbp_move_red_left and rbp_move_red_right with private methods. r?njn
--- a/memory/build/rb.h
+++ b/memory/build/rb.h
@@ -129,80 +129,16 @@ public:
void SetColor(NodeColor aColor)
{
mRightAndColor = reinterpret_cast<T*>(
(reinterpret_cast<uintptr_t>(mRightAndColor) & uintptr_t(~1)) | aColor);
}
};
-#define rbp_move_red_left(a_type, a_field, a_node, r_node) \
- do { \
- a_type *rbp_mrl_t, *rbp_mrl_u; \
- rbp_mrl_t = a_field(a_node).Left(); \
- a_field(rbp_mrl_t).SetColor(NodeColor::Red); \
- rbp_mrl_t = a_field(a_node).Right(); \
- rbp_mrl_u = a_field(rbp_mrl_t).Left(); \
- if (a_field(rbp_mrl_u).IsRed()) { \
- rbp_mrl_u = RotateRight(rbp_mrl_t); \
- a_field(a_node).SetRight(rbp_mrl_u); \
- r_node = RotateLeft(a_node); \
- rbp_mrl_t = a_field(a_node).Right(); \
- if (a_field(rbp_mrl_t).IsRed()) { \
- a_field(rbp_mrl_t).SetColor(NodeColor::Black); \
- a_field(a_node).SetColor(NodeColor::Red); \
- rbp_mrl_t = RotateLeft(a_node); \
- a_field(r_node).SetLeft(rbp_mrl_t); \
- } else { \
- a_field(a_node).SetColor(NodeColor::Black); \
- } \
- } else { \
- a_field(a_node).SetColor(NodeColor::Red); \
- r_node = RotateLeft(a_node); \
- } \
- } while (0)
-
-#define rbp_move_red_right(a_type, a_field, a_node, r_node) \
- do { \
- a_type* rbp_mrr_t; \
- rbp_mrr_t = a_field(a_node).Left(); \
- if (a_field(rbp_mrr_t).IsRed()) { \
- a_type *rbp_mrr_u, *rbp_mrr_v; \
- rbp_mrr_u = a_field(rbp_mrr_t).Right(); \
- rbp_mrr_v = a_field(rbp_mrr_u).Left(); \
- if (a_field(rbp_mrr_v).IsRed()) { \
- a_field(rbp_mrr_u).SetColor(a_field(a_node).Color()); \
- a_field(rbp_mrr_v).SetColor(NodeColor::Black); \
- rbp_mrr_u = RotateLeft(rbp_mrr_t); \
- a_field(a_node).SetLeft(rbp_mrr_u); \
- r_node = RotateRight(a_node); \
- rbp_mrr_t = RotateLeft(a_node); \
- a_field(r_node).SetRight(rbp_mrr_t); \
- } else { \
- a_field(rbp_mrr_t).SetColor(a_field(a_node).Color()); \
- a_field(rbp_mrr_u).SetColor(NodeColor::Red); \
- r_node = RotateRight(a_node); \
- rbp_mrr_t = RotateLeft(a_node); \
- a_field(r_node).SetRight(rbp_mrr_t); \
- } \
- a_field(a_node).SetColor(NodeColor::Red); \
- } else { \
- a_field(rbp_mrr_t).SetColor(NodeColor::Red); \
- rbp_mrr_t = a_field(rbp_mrr_t).Left(); \
- if (a_field(rbp_mrr_t).IsRed()) { \
- a_field(rbp_mrr_t).SetColor(NodeColor::Black); \
- r_node = RotateRight(a_node); \
- rbp_mrr_t = RotateLeft(a_node); \
- a_field(r_node).SetRight(rbp_mrr_t); \
- } else { \
- r_node = RotateLeft(a_node); \
- } \
- } \
- } while (0)
-
/* Tree structure. */
template<typename T, typename Trait>
struct RedBlackTree
{
T* rbt_root;
T rbt_nil;
void Init()
@@ -421,17 +357,17 @@ struct RedBlackTree
* be no way to convert it from a 2-node to a 3-node. */
rbp_r_cmp = Trait::Compare(aNode, rbp_r_c);
if (rbp_r_cmp < 0) {
rbp_r_t = Trait::GetTreeNode(rbp_r_c).Left();
rbp_r_u = Trait::GetTreeNode(rbp_r_t).Left();
if (Trait::GetTreeNode(rbp_r_t).IsBlack() &&
Trait::GetTreeNode(rbp_r_u).IsBlack()) {
/* Apply standard transform to prepare for left move. */
- rbp_move_red_left(T, Trait::GetTreeNode, rbp_r_c, rbp_r_t);
+ rbp_r_t = MoveRedLeft(rbp_r_c);
Trait::GetTreeNode(rbp_r_t).SetColor(NodeColor::Black);
Trait::GetTreeNode(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 = Trait::GetTreeNode(rbp_r_c).Left();
}
@@ -458,17 +394,17 @@ struct RedBlackTree
}
if (rbp_r_cmp == 1) {
if (Trait::GetTreeNode(
Trait::GetTreeNode(Trait::GetTreeNode(rbp_r_c).Right()).Left())
.IsBlack()) {
rbp_r_t = Trait::GetTreeNode(rbp_r_c).Left();
if (Trait::GetTreeNode(rbp_r_t).IsRed()) {
/* Standard transform. */
- rbp_move_red_right(T, Trait::GetTreeNode, rbp_r_c, rbp_r_t);
+ rbp_r_t = MoveRedRight(rbp_r_c);
} else {
/* Root-specific transform. */
Trait::GetTreeNode(rbp_r_c).SetColor(NodeColor::Red);
rbp_r_u = Trait::GetTreeNode(rbp_r_t).Left();
if (Trait::GetTreeNode(rbp_r_u).IsRed()) {
Trait::GetTreeNode(rbp_r_u).SetColor(NodeColor::Black);
rbp_r_t = RotateRight(rbp_r_c);
rbp_r_u = RotateLeft(rbp_r_c);
@@ -515,17 +451,17 @@ struct RedBlackTree
MOZ_ASSERT(Trait::GetTreeNode(rbp_r_p).Right() == rbp_r_c);
Trait::GetTreeNode(rbp_r_p).SetRight(&rbt_nil);
}
break;
}
rbp_r_u = Trait::GetTreeNode(rbp_r_t).Left();
if (Trait::GetTreeNode(rbp_r_t).IsBlack() &&
Trait::GetTreeNode(rbp_r_u).IsBlack()) {
- rbp_move_red_left(T, Trait::GetTreeNode, rbp_r_c, rbp_r_t);
+ rbp_r_t = MoveRedLeft(rbp_r_c);
if (Trait::GetTreeNode(rbp_r_p).Left() == rbp_r_c) {
Trait::GetTreeNode(rbp_r_p).SetLeft(rbp_r_t);
} else {
Trait::GetTreeNode(rbp_r_p).SetRight(rbp_r_t);
}
rbp_r_c = rbp_r_t;
} else {
rbp_r_p = rbp_r_c;
@@ -557,17 +493,17 @@ struct RedBlackTree
* information to do the swap later.
* rbp_r_xp is aNode's parent. */
rbp_r_xp = rbp_r_p;
}
}
rbp_r_t = Trait::GetTreeNode(rbp_r_c).Right();
rbp_r_u = Trait::GetTreeNode(rbp_r_t).Left();
if (Trait::GetTreeNode(rbp_r_u).IsBlack()) {
- rbp_move_red_right(T, Trait::GetTreeNode, rbp_r_c, rbp_r_t);
+ rbp_r_t = MoveRedRight(rbp_r_c);
if (Trait::GetTreeNode(rbp_r_p).Left() == rbp_r_c) {
Trait::GetTreeNode(rbp_r_p).SetLeft(rbp_r_t);
} else {
Trait::GetTreeNode(rbp_r_p).SetRight(rbp_r_t);
}
rbp_r_c = rbp_r_t;
} else {
rbp_r_p = rbp_r_c;
@@ -609,16 +545,86 @@ private:
T* LeanRight(T* aNode)
{
T* node = RotateRight(aNode);
NodeColor color = Trait::GetTreeNode(aNode).Color();
Trait::GetTreeNode(node).SetColor(color);
Trait::GetTreeNode(aNode).SetColor(NodeColor::Red);
return node;
}
+
+ T* MoveRedLeft(T* aNode)
+ {
+ T* node;
+ T *rbp_mrl_t, *rbp_mrl_u;
+ rbp_mrl_t = Trait::GetTreeNode(aNode).Left();
+ Trait::GetTreeNode(rbp_mrl_t).SetColor(NodeColor::Red);
+ rbp_mrl_t = Trait::GetTreeNode(aNode).Right();
+ rbp_mrl_u = Trait::GetTreeNode(rbp_mrl_t).Left();
+ if (Trait::GetTreeNode(rbp_mrl_u).IsRed()) {
+ rbp_mrl_u = RotateRight(rbp_mrl_t);
+ Trait::GetTreeNode(aNode).SetRight(rbp_mrl_u);
+ node = RotateLeft(aNode);
+ rbp_mrl_t = Trait::GetTreeNode(aNode).Right();
+ if (Trait::GetTreeNode(rbp_mrl_t).IsRed()) {
+ Trait::GetTreeNode(rbp_mrl_t).SetColor(NodeColor::Black);
+ Trait::GetTreeNode(aNode).SetColor(NodeColor::Red);
+ rbp_mrl_t = RotateLeft(aNode);
+ Trait::GetTreeNode(node).SetLeft(rbp_mrl_t);
+ } else {
+ Trait::GetTreeNode(aNode).SetColor(NodeColor::Black);
+ }
+ } else {
+ Trait::GetTreeNode(aNode).SetColor(NodeColor::Red);
+ node = RotateLeft(aNode);
+ }
+ return node;
+ }
+
+ T* MoveRedRight(T* aNode)
+ {
+ T* node;
+ T* rbp_mrr_t;
+ rbp_mrr_t = Trait::GetTreeNode(aNode).Left();
+ if (Trait::GetTreeNode(rbp_mrr_t).IsRed()) {
+ T *rbp_mrr_u, *rbp_mrr_v;
+ rbp_mrr_u = Trait::GetTreeNode(rbp_mrr_t).Right();
+ rbp_mrr_v = Trait::GetTreeNode(rbp_mrr_u).Left();
+ if (Trait::GetTreeNode(rbp_mrr_v).IsRed()) {
+ Trait::GetTreeNode(rbp_mrr_u).SetColor(
+ Trait::GetTreeNode(aNode).Color());
+ Trait::GetTreeNode(rbp_mrr_v).SetColor(NodeColor::Black);
+ rbp_mrr_u = RotateLeft(rbp_mrr_t);
+ Trait::GetTreeNode(aNode).SetLeft(rbp_mrr_u);
+ node = RotateRight(aNode);
+ rbp_mrr_t = RotateLeft(aNode);
+ Trait::GetTreeNode(node).SetRight(rbp_mrr_t);
+ } else {
+ Trait::GetTreeNode(rbp_mrr_t).SetColor(
+ Trait::GetTreeNode(aNode).Color());
+ Trait::GetTreeNode(rbp_mrr_u).SetColor(NodeColor::Red);
+ node = RotateRight(aNode);
+ rbp_mrr_t = RotateLeft(aNode);
+ Trait::GetTreeNode(node).SetRight(rbp_mrr_t);
+ }
+ Trait::GetTreeNode(aNode).SetColor(NodeColor::Red);
+ } else {
+ Trait::GetTreeNode(rbp_mrr_t).SetColor(NodeColor::Red);
+ rbp_mrr_t = Trait::GetTreeNode(rbp_mrr_t).Left();
+ if (Trait::GetTreeNode(rbp_mrr_t).IsRed()) {
+ Trait::GetTreeNode(rbp_mrr_t).SetColor(NodeColor::Black);
+ node = RotateRight(aNode);
+ rbp_mrr_t = RotateLeft(aNode);
+ Trait::GetTreeNode(node).SetRight(rbp_mrr_t);
+ } else {
+ node = RotateLeft(aNode);
+ }
+ }
+ return node;
+ }
};
/*
* The iterators simulate 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).
*