--- a/memory/build/rb.h
+++ b/memory/build/rb.h
@@ -125,108 +125,94 @@ public:
}
void SetColor(NodeColor aColor)
{
mRightAndColor = (mRightAndColor & uintptr_t(~1)) | aColor;
}
};
-#define rbp_rotate_left(a_type, a_field, a_node, r_node) \
- do { \
- (r_node) = a_field(a_node).Right(); \
- a_field(a_node).SetRight(a_field(r_node).Left()); \
- a_field(r_node).SetLeft((a_node)); \
- } while (0)
-
-#define rbp_rotate_right(a_type, a_field, a_node, r_node) \
- do { \
- (r_node) = a_field(a_node).Left(); \
- a_field(a_node).SetLeft(a_field(r_node).Right()); \
- a_field(r_node).SetRight((a_node)); \
- } while (0)
-
#define rbp_lean_left(a_type, a_field, a_node, r_node) \
do { \
NodeColor rbp_ll_color; \
- rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
+ 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; \
- rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \
+ 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()) { \
- rbp_rotate_right(a_type, a_field, rbp_mrl_t, rbp_mrl_u); \
+ rbp_mrl_u = RotateRight(rbp_mrl_t); \
a_field(a_node).SetRight(rbp_mrl_u); \
- rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
+ 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_rotate_left(a_type, a_field, (a_node), rbp_mrl_t); \
+ 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); \
- rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
+ 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_rotate_left(a_type, a_field, rbp_mrr_t, rbp_mrr_u); \
+ rbp_mrr_u = RotateLeft(rbp_mrr_t); \
a_field(a_node).SetLeft(rbp_mrr_u); \
- rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \
- rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t); \
+ 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); \
- rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \
- rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t); \
+ 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); \
- rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \
- rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t); \
+ r_node = RotateRight(a_node); \
+ rbp_mrr_t = RotateLeft(a_node); \
a_field(r_node).SetRight(rbp_mrr_t); \
} else { \
- rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
+ r_node = RotateLeft(a_node); \
} \
} \
} while (0)
/* Tree structure. */
template<typename T, typename Trait>
struct RedBlackTree
{
@@ -366,17 +352,17 @@ struct RedBlackTree
rbp_i_u = Trait::GetTreeNode(rbp_i_t).Left();
if (Trait::GetTreeNode(rbp_i_t).IsRed() &&
Trait::GetTreeNode(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_rotate_right(T, Trait::GetTreeNode, rbp_i_c, rbp_i_t);
+ rbp_i_t = RotateRight(rbp_i_c);
/* Pass red links up one level. */
rbp_i_u = Trait::GetTreeNode(rbp_i_t).Left();
Trait::GetTreeNode(rbp_i_u).SetColor(NodeColor::Black);
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
@@ -493,22 +479,22 @@ struct RedBlackTree
/* Standard transform. */
rbp_move_red_right(T, Trait::GetTreeNode, rbp_r_c, rbp_r_t);
} 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_rotate_right(T, Trait::GetTreeNode, rbp_r_c, rbp_r_t);
- rbp_rotate_left(T, Trait::GetTreeNode, rbp_r_c, rbp_r_u);
+ rbp_r_t = RotateRight(rbp_r_c);
+ rbp_r_u = RotateLeft(rbp_r_c);
Trait::GetTreeNode(rbp_r_t).SetRight(rbp_r_u);
} else {
Trait::GetTreeNode(rbp_r_t).SetColor(NodeColor::Red);
- rbp_rotate_left(T, Trait::GetTreeNode, rbp_r_c, rbp_r_t);
+ rbp_r_t = RotateLeft(rbp_r_c);
}
}
Trait::GetTreeNode(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 = Trait::GetTreeNode(rbp_r_c).Right();
@@ -602,16 +588,33 @@ struct RedBlackTree
rbp_r_c = Trait::GetTreeNode(rbp_r_c).Right();
}
}
}
}
/* Update root. */
rbt_root = Trait::GetTreeNode(&rbp_r_s).Left();
}
+
+private:
+ T* RotateLeft(T* aNode)
+ {
+ T* node = Trait::GetTreeNode(aNode).Right();
+ Trait::GetTreeNode(aNode).SetRight(Trait::GetTreeNode(node).Left());
+ Trait::GetTreeNode(node).SetLeft(aNode);
+ return node;
+ }
+
+ 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;
+ }
};
/*
* 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).
*