--- a/memory/build/rb.h
+++ b/memory/build/rb.h
@@ -127,34 +127,30 @@ template <typename T>
struct RedBlackTree
{
T* rbt_root;
T rbt_nil;
};
#define rb_node_field(a_node, a_field) (a_node)->a_field
-/* Right accessors. */
-#define rbp_right_set(a_type, a_field, a_node, a_right) \
- rb_node_field(a_node, a_field).SetRight(a_right)
-
/* Color accessors. */
#define rbp_color_set(a_type, a_field, a_node, a_red) \
rb_node_field(a_node, a_field) \
.SetColor(a_red ? NodeColor::Red : NodeColor::Black)
#define rbp_red_set(a_type, a_field, a_node) \
rb_node_field(a_node, a_field).SetColor(NodeColor::Red)
#define rbp_black_set(a_type, a_field, a_node) \
rb_node_field(a_node, a_field).SetColor(NodeColor::Black)
/* Node initializer. */
#define rbp_node_new(a_type, a_field, a_tree, a_node) \
do { \
rb_node_field((a_node), a_field).SetLeft(&(a_tree)->rbt_nil); \
- rbp_right_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil); \
+ rb_node_field((a_node), a_field).SetRight(&(a_tree)->rbt_nil); \
rbp_red_set(a_type, a_field, (a_node)); \
} while (0)
/* Tree initializer. */
#define rb_new(a_type, a_field, a_tree) \
do { \
(a_tree)->rbt_root = &(a_tree)->rbt_nil; \
rbp_node_new(a_type, a_field, a_tree, &(a_tree)->rbt_nil); \
@@ -305,27 +301,27 @@ struct RedBlackTree
/*
* Find a match if it exists. Otherwise, find the previous lesser node, if one
* exists.
*/
#define rbp_rotate_left(a_type, a_field, a_node, r_node) \
do { \
(r_node) = rb_node_field((a_node), a_field).Right(); \
- rbp_right_set( \
- a_type, a_field, (a_node), rb_node_field((r_node), a_field).Left()); \
+ rb_node_field((a_node), a_field) \
+ .SetRight(rb_node_field((r_node), a_field).Left()); \
rb_node_field((r_node), a_field).SetLeft((a_node)); \
} while (0)
#define rbp_rotate_right(a_type, a_field, a_node, r_node) \
do { \
(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()); \
- rbp_right_set(a_type, a_field, (r_node), (a_node)); \
+ 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; \
rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
rbp_ll_red = rb_node_field((a_node), a_field).IsRed(); \
rbp_color_set(a_type, a_field, (r_node), rbp_ll_red); \
@@ -345,17 +341,17 @@ struct RedBlackTree
do { \
a_type *rbp_mrl_t, *rbp_mrl_u; \
rbp_mrl_t = rb_node_field((a_node), a_field).Left(); \
rbp_red_set(a_type, a_field, rbp_mrl_t); \
rbp_mrl_t = rb_node_field((a_node), a_field).Right(); \
rbp_mrl_u = rb_node_field(rbp_mrl_t, a_field).Left(); \
if (rb_node_field(rbp_mrl_u, a_field).IsRed()) { \
rbp_rotate_right(a_type, a_field, rbp_mrl_t, rbp_mrl_u); \
- rbp_right_set(a_type, a_field, (a_node), rbp_mrl_u); \
+ rb_node_field((a_node), a_field).SetRight(rbp_mrl_u); \
rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
rbp_mrl_t = rb_node_field((a_node), a_field).Right(); \
if (rb_node_field(rbp_mrl_t, a_field).IsRed()) { \
rbp_black_set(a_type, a_field, rbp_mrl_t); \
rbp_red_set(a_type, a_field, (a_node)); \
rbp_rotate_left(a_type, a_field, (a_node), rbp_mrl_t); \
rb_node_field((r_node), a_field).SetLeft(rbp_mrl_t); \
} else { \
@@ -380,50 +376,50 @@ struct RedBlackTree
a_field, \
rbp_mrr_u, \
rb_node_field((a_node), a_field).IsRed()); \
rbp_black_set(a_type, a_field, rbp_mrr_v); \
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); \
- rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t); \
+ rb_node_field((r_node), a_field).SetRight(rbp_mrr_t); \
} else { \
rbp_color_set(a_type, \
a_field, \
rbp_mrr_t, \
rb_node_field((a_node), a_field).IsRed()); \
rbp_red_set(a_type, a_field, 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); \
- rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t); \
+ rb_node_field((r_node), a_field).SetRight(rbp_mrr_t); \
} \
rbp_red_set(a_type, a_field, (a_node)); \
} else { \
rbp_red_set(a_type, a_field, rbp_mrr_t); \
rbp_mrr_t = rb_node_field(rbp_mrr_t, a_field).Left(); \
if (rb_node_field(rbp_mrr_t, a_field).IsRed()) { \
rbp_black_set(a_type, a_field, rbp_mrr_t); \
rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \
rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t); \
- rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t); \
+ rb_node_field((r_node), a_field).SetRight(rbp_mrr_t); \
} else { \
rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
} \
} \
} while (0)
#define rb_insert(a_type, a_field, a_cmp, a_tree, a_node) \
do { \
a_type rbp_i_s; \
a_type *rbp_i_g, *rbp_i_p, *rbp_i_c, *rbp_i_t, *rbp_i_u; \
int rbp_i_cmp = 0; \
rbp_i_g = &(a_tree)->rbt_nil; \
rb_node_field(&rbp_i_s, a_field).SetLeft((a_tree)->rbt_root); \
- rbp_right_set(a_type, a_field, &rbp_i_s, &(a_tree)->rbt_nil); \
+ rb_node_field(&rbp_i_s, a_field).SetRight(&(a_tree)->rbt_nil); \
rbp_black_set(a_type, a_field, &rbp_i_s); \
rbp_i_p = &rbp_i_s; \
rbp_i_c = (a_tree)->rbt_root; \
/* 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 != &(a_tree)->rbt_nil) { \
@@ -443,23 +439,23 @@ struct RedBlackTree
if (rb_node_field(rbp_i_p, a_field).Left() == rbp_i_c) { \
rb_node_field(rbp_i_p, a_field).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(rb_node_field(rbp_i_p, a_field).Right() == rbp_i_c); \
- rbp_right_set(a_type, a_field, rbp_i_p, rbp_i_t); \
+ rb_node_field(rbp_i_p, a_field).SetRight(rbp_i_t); \
rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_u); \
if (rb_node_field(rbp_i_g, a_field).Left() == rbp_i_p) { \
rb_node_field(rbp_i_g, a_field).SetLeft(rbp_i_u); \
} else { \
MOZ_ASSERT(rb_node_field(rbp_i_g, a_field).Right() == rbp_i_p); \
- rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_u); \
+ rb_node_field(rbp_i_g, a_field).SetRight(rbp_i_u); \
} \
rbp_i_p = rbp_i_u; \
rbp_i_cmp = (a_cmp)((a_node), rbp_i_p); \
if (rbp_i_cmp < 0) { \
rbp_i_c = rb_node_field(rbp_i_p, a_field).Left(); \
} else { \
MOZ_ASSERT(rbp_i_cmp > 0); \
rbp_i_c = rb_node_field(rbp_i_p, a_field).Right(); \
@@ -475,38 +471,38 @@ struct RedBlackTree
} else { \
MOZ_ASSERT(rbp_i_cmp > 0); \
rbp_i_c = rb_node_field(rbp_i_c, a_field).Right(); \
} \
} \
/* rbp_i_p now refers to the node under which to insert. */ \
rbp_node_new(a_type, a_field, a_tree, (a_node)); \
if (rbp_i_cmp > 0) { \
- rbp_right_set(a_type, a_field, rbp_i_p, (a_node)); \
+ rb_node_field(rbp_i_p, a_field).SetRight((a_node)); \
rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_t); \
if (rb_node_field(rbp_i_g, a_field).Left() == rbp_i_p) { \
rb_node_field(rbp_i_g, a_field).SetLeft(rbp_i_t); \
} else if (rb_node_field(rbp_i_g, a_field).Right() == rbp_i_p) { \
- rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_t); \
+ rb_node_field(rbp_i_g, a_field).SetRight(rbp_i_t); \
} \
} else { \
rb_node_field(rbp_i_p, a_field).SetLeft((a_node)); \
} \
/* Update the root and make sure that it is black. */ \
(a_tree)->rbt_root = rb_node_field(&rbp_i_s, a_field).Left(); \
rbp_black_set(a_type, a_field, (a_tree)->rbt_root); \
} while (0)
#define rb_remove(a_type, a_field, a_cmp, a_tree, a_node) \
do { \
a_type rbp_r_s; \
a_type *rbp_r_p, *rbp_r_c, *rbp_r_xp, *rbp_r_t, *rbp_r_u; \
int rbp_r_cmp; \
rb_node_field(&rbp_r_s, a_field).SetLeft((a_tree)->rbt_root); \
- rbp_right_set(a_type, a_field, &rbp_r_s, &(a_tree)->rbt_nil); \
+ rb_node_field(&rbp_r_s, a_field).SetRight(&(a_tree)->rbt_nil); \
rbp_black_set(a_type, a_field, &rbp_r_s); \
rbp_r_p = &rbp_r_s; \
rbp_r_c = (a_tree)->rbt_root; \
rbp_r_xp = &(a_tree)->rbt_nil; \
/* 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 */ \
@@ -529,17 +525,17 @@ struct RedBlackTree
} \
} else { \
if (rbp_r_cmp == 0) { \
MOZ_ASSERT((a_node) == rbp_r_c); \
if (rb_node_field(rbp_r_c, a_field).Right() == &(a_tree)->rbt_nil) { \
/* Delete root node (which is also a leaf node). */ \
if (rb_node_field(rbp_r_c, a_field).Left() != &(a_tree)->rbt_nil) { \
rbp_lean_right(a_type, a_field, rbp_r_c, rbp_r_t); \
- rbp_right_set(a_type, a_field, rbp_r_t, &(a_tree)->rbt_nil); \
+ rb_node_field(rbp_r_t, a_field).SetRight(&(a_tree)->rbt_nil); \
} else { \
rbp_r_t = &(a_tree)->rbt_nil; \
} \
rb_node_field(rbp_r_p, a_field).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 */ \
@@ -561,17 +557,17 @@ struct RedBlackTree
} else { \
/* Root-specific transform. */ \
rbp_red_set(a_type, a_field, rbp_r_c); \
rbp_r_u = rb_node_field(rbp_r_t, a_field).Left(); \
if (rb_node_field(rbp_r_u, a_field).IsRed()) { \
rbp_black_set(a_type, a_field, rbp_r_u); \
rbp_rotate_right(a_type, a_field, rbp_r_c, rbp_r_t); \
rbp_rotate_left(a_type, a_field, rbp_r_c, rbp_r_u); \
- rbp_right_set(a_type, a_field, rbp_r_t, rbp_r_u); \
+ rb_node_field(rbp_r_t, a_field).SetRight(rbp_r_u); \
} else { \
rbp_red_set(a_type, a_field, rbp_r_t); \
rbp_rotate_left(a_type, a_field, rbp_r_c, rbp_r_t); \
} \
} \
rb_node_field(rbp_r_p, a_field).SetLeft(rbp_r_t); \
rbp_r_c = rbp_r_t; \
} else { \
@@ -591,44 +587,42 @@ struct RedBlackTree
/* rbp_r_c now refers to the successor node to */ \
/* relocate, and rbp_r_xp/a_node refer to the */ \
/* context for the relocation. */ \
if (rb_node_field(rbp_r_xp, a_field).Left() == (a_node)) { \
rb_node_field(rbp_r_xp, a_field).SetLeft(rbp_r_c); \
} else { \
MOZ_ASSERT(rb_node_field(rbp_r_xp, a_field).Right() == \
(a_node)); \
- rbp_right_set(a_type, a_field, rbp_r_xp, rbp_r_c); \
+ 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()); \
- rbp_right_set(a_type, \
- a_field, \
- rbp_r_c, \
- rb_node_field((a_node), a_field).Right()); \
+ rb_node_field(rbp_r_c, a_field) \
+ .SetRight(rb_node_field((a_node), a_field).Right()); \
rbp_color_set(a_type, \
a_field, \
rbp_r_c, \
rb_node_field((a_node), a_field).IsRed()); \
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); \
- rbp_right_set(a_type, a_field, rbp_r_p, &(a_tree)->rbt_nil); \
+ 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) { \
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 { \
- rbp_right_set(a_type, a_field, rbp_r_p, rbp_r_t); \
+ rb_node_field(rbp_r_p, a_field).SetRight(rbp_r_t); \
} \
rbp_r_c = rbp_r_t; \
} else { \
rbp_r_p = rbp_r_c; \
rbp_r_c = rb_node_field(rbp_r_c, a_field).Left(); \
} \
} else { \
/* Check whether to delete this node (it has to be */ \
@@ -636,24 +630,24 @@ struct RedBlackTree
if (rbp_r_cmp == 0) { \
MOZ_ASSERT((a_node) == rbp_r_c); \
if (rb_node_field(rbp_r_c, a_field).Right() == \
&(a_tree)->rbt_nil) { \
/* Delete leaf node. */ \
if (rb_node_field(rbp_r_c, a_field).Left() != \
&(a_tree)->rbt_nil) { \
rbp_lean_right(a_type, a_field, rbp_r_c, rbp_r_t); \
- rbp_right_set(a_type, a_field, rbp_r_t, &(a_tree)->rbt_nil); \
+ rb_node_field(rbp_r_t, a_field).SetRight(&(a_tree)->rbt_nil); \
} else { \
rbp_r_t = &(a_tree)->rbt_nil; \
} \
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 { \
- rbp_right_set(a_type, a_field, rbp_r_p, rbp_r_t); \
+ rb_node_field(rbp_r_p, a_field).SetRight(rbp_r_t); \
} \
break; \
} 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 a_node's parent. */ \
@@ -662,17 +656,17 @@ struct RedBlackTree
} \
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) { \
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 { \
- rbp_right_set(a_type, a_field, rbp_r_p, rbp_r_t); \
+ rb_node_field(rbp_r_p, a_field).SetRight(rbp_r_t); \
} \
rbp_r_c = rbp_r_t; \
} else { \
rbp_r_p = rbp_r_c; \
rbp_r_c = rb_node_field(rbp_r_c, a_field).Right(); \
} \
} \
} \