--- a/memory/build/rb.h
+++ b/memory/build/rb.h
@@ -106,16 +106,21 @@ public:
mRightAndColor = (reinterpret_cast<uintptr_t>(aValue) & uintptr_t(~1)) | Color();
}
NodeColor Color()
{
return static_cast<NodeColor>(mRightAndColor & 1);
}
+ bool IsBlack()
+ {
+ return Color() == NodeColor::Black;
+ }
+
bool IsRed()
{
return Color() == NodeColor::Red;
}
void SetColor(NodeColor aColor)
{
mRightAndColor = (mRightAndColor & uintptr_t(~1)) | aColor;
@@ -307,31 +312,29 @@ struct RedBlackTree
(r_node) = rb_node_field((a_node), a_field).Left(); \
rb_node_field((a_node), a_field) \
.SetLeft(rb_node_field((r_node), a_field).Right()); \
rb_node_field((r_node), a_field).SetRight((a_node)); \
} while (0)
#define rbp_lean_left(a_type, a_field, a_node, r_node) \
do { \
- bool rbp_ll_red; \
+ NodeColor rbp_ll_color; \
rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
- rbp_ll_red = rb_node_field((a_node), a_field).IsRed(); \
- rb_node_field((r_node), a_field) \
- .SetColor(rbp_ll_red ? NodeColor::Red : NodeColor::Black); \
+ rbp_ll_color = rb_node_field((a_node), a_field).Color(); \
+ rb_node_field((r_node), a_field).SetColor(rbp_ll_color); \
rb_node_field((a_node), a_field).SetColor(NodeColor::Red); \
} while (0)
#define rbp_lean_right(a_type, a_field, a_node, r_node) \
do { \
- bool rbp_lr_red; \
+ NodeColor rbp_lr_color; \
rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \
- rbp_lr_red = rb_node_field((a_node), a_field).IsRed(); \
- rb_node_field((r_node), a_field) \
- .SetColor(rbp_lr_red ? NodeColor::Red : NodeColor::Black); \
+ rbp_lr_color = rb_node_field((a_node), a_field).Color(); \
+ rb_node_field((r_node), a_field).SetColor(rbp_lr_color); \
rb_node_field((a_node), a_field).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 = rb_node_field((a_node), a_field).Left(); \
rb_node_field(rbp_mrl_t, a_field).SetColor(NodeColor::Red); \
@@ -361,30 +364,26 @@ struct RedBlackTree
a_type* rbp_mrr_t; \
rbp_mrr_t = rb_node_field((a_node), a_field).Left(); \
if (rb_node_field(rbp_mrr_t, a_field).IsRed()) { \
a_type *rbp_mrr_u, *rbp_mrr_v; \
rbp_mrr_u = rb_node_field(rbp_mrr_t, a_field).Right(); \
rbp_mrr_v = rb_node_field(rbp_mrr_u, a_field).Left(); \
if (rb_node_field(rbp_mrr_v, a_field).IsRed()) { \
rb_node_field(rbp_mrr_u, a_field) \
- .SetColor(rb_node_field((a_node), a_field).IsRed() \
- ? NodeColor::Red \
- : NodeColor::Black); \
+ .SetColor(rb_node_field((a_node), a_field).Color()); \
rb_node_field(rbp_mrr_v, a_field).SetColor(NodeColor::Black); \
rbp_rotate_left(a_type, a_field, rbp_mrr_t, rbp_mrr_u); \
rb_node_field((a_node), a_field).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); \
rb_node_field((r_node), a_field).SetRight(rbp_mrr_t); \
} else { \
rb_node_field(rbp_mrr_t, a_field) \
- .SetColor(rb_node_field((a_node), a_field).IsRed() \
- ? NodeColor::Red \
- : NodeColor::Black); \
+ .SetColor(rb_node_field((a_node), a_field).Color()); \
rb_node_field(rbp_mrr_u, a_field).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); \
rb_node_field((r_node), a_field).SetRight(rbp_mrr_t); \
} \
rb_node_field((a_node), a_field).SetColor(NodeColor::Red); \
} else { \
rb_node_field(rbp_mrr_t, a_field).SetColor(NodeColor::Red); \
@@ -499,18 +498,18 @@ struct RedBlackTree
/* 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 = (a_cmp)((a_node), rbp_r_c); \
if (rbp_r_cmp < 0) { \
rbp_r_t = rb_node_field(rbp_r_c, a_field).Left(); \
rbp_r_u = rb_node_field(rbp_r_t, a_field).Left(); \
- if (rb_node_field(rbp_r_t, a_field).IsRed() == false && \
- rb_node_field(rbp_r_u, a_field).IsRed() == false) { \
+ if (rb_node_field(rbp_r_t, a_field).IsBlack() && \
+ rb_node_field(rbp_r_u, a_field).IsBlack()) { \
/* Apply standard transform to prepare for left move. */ \
rbp_move_red_left(a_type, a_field, rbp_r_c, rbp_r_t); \
rb_node_field(rbp_r_t, a_field).SetColor(NodeColor::Black); \
rb_node_field(rbp_r_p, a_field).SetLeft(rbp_r_t); \
rbp_r_c = rbp_r_t; \
} else { \
/* Move left. */ \
rbp_r_p = rbp_r_c; \
@@ -537,17 +536,17 @@ struct RedBlackTree
rbp_r_cmp = 1; /* Note that deletion is incomplete. */ \
} \
} \
if (rbp_r_cmp == 1) { \
if (rb_node_field( \
rb_node_field(rb_node_field(rbp_r_c, a_field).Right(), a_field) \
.Left(), \
a_field) \
- .IsRed() == false) { \
+ .IsBlack()) { \
rbp_r_t = rb_node_field(rbp_r_c, a_field).Left(); \
if (rb_node_field(rbp_r_t, a_field).IsRed()) { \
/* Standard transform. */ \
rbp_move_red_right(a_type, a_field, rbp_r_c, rbp_r_t); \
} else { \
/* Root-specific transform. */ \
rb_node_field(rbp_r_c, a_field).SetColor(NodeColor::Red); \
rbp_r_u = rb_node_field(rbp_r_t, a_field).Left(); \
@@ -587,30 +586,28 @@ struct RedBlackTree
(a_node)); \
rb_node_field(rbp_r_xp, a_field).SetRight(rbp_r_c); \
} \
rb_node_field(rbp_r_c, a_field) \
.SetLeft(rb_node_field((a_node), a_field).Left()); \
rb_node_field(rbp_r_c, a_field) \
.SetRight(rb_node_field((a_node), a_field).Right()); \
rb_node_field(rbp_r_c, a_field) \
- .SetColor(rb_node_field((a_node), a_field).IsRed() \
- ? NodeColor::Red \
- : NodeColor::Black); \
+ .SetColor(rb_node_field((a_node), a_field).Color()); \
if (rb_node_field(rbp_r_p, a_field).Left() == rbp_r_c) { \
rb_node_field(rbp_r_p, a_field).SetLeft(&(a_tree)->rbt_nil); \
} else { \
MOZ_ASSERT(rb_node_field(rbp_r_p, a_field).Right() == rbp_r_c); \
rb_node_field(rbp_r_p, a_field).SetRight(&(a_tree)->rbt_nil); \
} \
break; \
} \
rbp_r_u = rb_node_field(rbp_r_t, a_field).Left(); \
- if (rb_node_field(rbp_r_t, a_field).IsRed() == false && \
- rb_node_field(rbp_r_u, a_field).IsRed() == false) { \
+ if (rb_node_field(rbp_r_t, a_field).IsBlack() && \
+ rb_node_field(rbp_r_u, a_field).IsBlack()) { \
rbp_move_red_left(a_type, a_field, rbp_r_c, rbp_r_t); \
if (rb_node_field(rbp_r_p, a_field).Left() == rbp_r_c) { \
rb_node_field(rbp_r_p, a_field).SetLeft(rbp_r_t); \
} else { \
rb_node_field(rbp_r_p, a_field).SetRight(rbp_r_t); \
} \
rbp_r_c = rbp_r_t; \
} else { \
@@ -644,17 +641,17 @@ struct RedBlackTree
/* and delete the successor. Record enough */ \
/* information to do the swap later. */ \
/* rbp_r_xp is a_node's parent. */ \
rbp_r_xp = rbp_r_p; \
} \
} \
rbp_r_t = rb_node_field(rbp_r_c, a_field).Right(); \
rbp_r_u = rb_node_field(rbp_r_t, a_field).Left(); \
- if (rb_node_field(rbp_r_u, a_field).IsRed() == false) { \
+ if (rb_node_field(rbp_r_u, a_field).IsBlack()) { \
rbp_move_red_right(a_type, a_field, rbp_r_c, rbp_r_t); \
if (rb_node_field(rbp_r_p, a_field).Left() == rbp_r_c) { \
rb_node_field(rbp_r_p, a_field).SetLeft(rbp_r_t); \
} else { \
rb_node_field(rbp_r_p, a_field).SetRight(rbp_r_t); \
} \
rbp_r_c = rbp_r_t; \
} else { \