Bug 1403444 - Replace rbp_lean_left and rbp_lean_right with private methods. r?njn
--- a/memory/build/rb.h
+++ b/memory/build/rb.h
@@ -125,34 +125,16 @@ public:
}
void SetColor(NodeColor aColor)
{
mRightAndColor = (mRightAndColor & uintptr_t(~1)) | aColor;
}
};
-#define rbp_lean_left(a_type, a_field, a_node, r_node) \
- do { \
- NodeColor rbp_ll_color; \
- r_node = RotateLeft(a_node); \
- rbp_ll_color = a_field(a_node).Color(); \
- a_field(r_node).SetColor(rbp_ll_color); \
- a_field(a_node).SetColor(NodeColor::Red); \
- } while (0)
-
-#define rbp_lean_right(a_type, a_field, a_node, r_node) \
- do { \
- NodeColor rbp_lr_color; \
- r_node = RotateRight(a_node); \
- rbp_lr_color = a_field(a_node).Color(); \
- a_field(r_node).SetColor(rbp_lr_color); \
- a_field(a_node).SetColor(NodeColor::Red); \
- } while (0)
-
#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()) { \
@@ -364,17 +346,17 @@ struct RedBlackTree
if (Trait::GetTreeNode(rbp_i_p).Left() == rbp_i_c) {
Trait::GetTreeNode(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(Trait::GetTreeNode(rbp_i_p).Right() == rbp_i_c);
Trait::GetTreeNode(rbp_i_p).SetRight(rbp_i_t);
- rbp_lean_left(T, Trait::GetTreeNode, rbp_i_p, rbp_i_u);
+ rbp_i_u = LeanLeft(rbp_i_p);
if (Trait::GetTreeNode(rbp_i_g).Left() == rbp_i_p) {
Trait::GetTreeNode(rbp_i_g).SetLeft(rbp_i_u);
} else {
MOZ_ASSERT(Trait::GetTreeNode(rbp_i_g).Right() == rbp_i_p);
Trait::GetTreeNode(rbp_i_g).SetRight(rbp_i_u);
}
rbp_i_p = rbp_i_u;
rbp_i_cmp = Trait::Compare(aNode, rbp_i_p);
@@ -398,17 +380,17 @@ struct RedBlackTree
}
}
/* rbp_i_p now refers to the node under which to insert. */
Trait::GetTreeNode(aNode).SetLeft(&rbt_nil);
Trait::GetTreeNode(aNode).SetRight(&rbt_nil);
Trait::GetTreeNode(aNode).SetColor(NodeColor::Red);
if (rbp_i_cmp > 0) {
Trait::GetTreeNode(rbp_i_p).SetRight(aNode);
- rbp_lean_left(T, Trait::GetTreeNode, rbp_i_p, rbp_i_t);
+ rbp_i_t = LeanLeft(rbp_i_p);
if (Trait::GetTreeNode(rbp_i_g).Left() == rbp_i_p) {
Trait::GetTreeNode(rbp_i_g).SetLeft(rbp_i_t);
} else if (Trait::GetTreeNode(rbp_i_g).Right() == rbp_i_p) {
Trait::GetTreeNode(rbp_i_g).SetRight(rbp_i_t);
}
} else {
Trait::GetTreeNode(rbp_i_p).SetLeft(aNode);
}
@@ -450,17 +432,17 @@ struct RedBlackTree
rbp_r_c = Trait::GetTreeNode(rbp_r_c).Left();
}
} else {
if (rbp_r_cmp == 0) {
MOZ_ASSERT(aNode == rbp_r_c);
if (Trait::GetTreeNode(rbp_r_c).Right() == &rbt_nil) {
/* Delete root node (which is also a leaf node). */
if (Trait::GetTreeNode(rbp_r_c).Left() != &rbt_nil) {
- rbp_lean_right(T, Trait::GetTreeNode, rbp_r_c, rbp_r_t);
+ rbp_r_t = LeanRight(rbp_r_c);
Trait::GetTreeNode(rbp_r_t).SetRight(&rbt_nil);
} else {
rbp_r_t = &rbt_nil;
}
Trait::GetTreeNode(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
@@ -548,17 +530,17 @@ struct RedBlackTree
} else {
/* Check whether to delete this node (it has to be
* the correct node and a leaf node). */
if (rbp_r_cmp == 0) {
MOZ_ASSERT(aNode == rbp_r_c);
if (Trait::GetTreeNode(rbp_r_c).Right() == &rbt_nil) {
/* Delete leaf node. */
if (Trait::GetTreeNode(rbp_r_c).Left() != &rbt_nil) {
- rbp_lean_right(T, Trait::GetTreeNode, rbp_r_c, rbp_r_t);
+ rbp_r_t = LeanRight(rbp_r_c);
Trait::GetTreeNode(rbp_r_t).SetRight(&rbt_nil);
} else {
rbp_r_t = &rbt_nil;
}
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);
@@ -605,16 +587,34 @@ private:
T* RotateRight(T* aNode)
{
T* node = Trait::GetTreeNode(aNode).Left();
Trait::GetTreeNode(aNode).SetLeft(Trait::GetTreeNode(node).Right());
Trait::GetTreeNode(node).SetRight(aNode);
return node;
}
+
+ T* LeanLeft(T* aNode)
+ {
+ T* node = RotateLeft(aNode);
+ NodeColor color = Trait::GetTreeNode(aNode).Color();
+ Trait::GetTreeNode(node).SetColor(color);
+ Trait::GetTreeNode(aNode).SetColor(NodeColor::Red);
+ return node;
+ }
+
+ 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;
+ }
};
/*
* 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).
*