[RBTREE] Merge colour and parent fields of struct rb_node.

We only used a single bit for colour information, so having a whole machine word of space allocated for it was a bit wasteful. Instead, store it in the lowest bit of the 'parent' pointer, since that was always going to be aligned anyway. Signed-off-by: David Woodhouse <dwmw2@infradead.org>
author: David Woodhouse <dwmw2@infradead.org> 2006-04-21 08:35:51 -0400
committer: David Woodhouse <dwmw2@infradead.org> 2006-04-21 08:35:51 -0400
commit: 55a981027fc393c86de2c4e7836c9515088a9a58 (patch)
tree: dd950b79d9f57ce48b2b2a91262b88eecb5296da /lib/rbtree.c
parent: 1975e59375756da4ff4e6e7d12f67485e813ace0 (diff)
1 files changed, 90 insertions, 88 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 63473e04f18a..4a7173cad149 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -26,60 +26,66 @@
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
        struct rb_node *right = node->rb_right;
+        struct rb_node *parent = rb_parent(node);
        if ((node->rb_right = right->rb_left))
-                right->rb_left->rb_parent = node;
+                rb_set_parent(right->rb_left, node);
        right->rb_left = node;
-        if ((right->rb_parent = node->rb_parent))
+        rb_set_parent(right, parent);
+        if (parent)
        {
-                if (node == node->rb_parent->rb_left)
+                if (node == parent->rb_left)
-                        node->rb_parent->rb_left = right;
+                        parent->rb_left = right;
                else
-                        node->rb_parent->rb_right = right;
+                        parent->rb_right = right;
        }
        else
                root->rb_node = right;
-        node->rb_parent = right;
+        rb_set_parent(node, right);
 }
 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
 {
        struct rb_node *left = node->rb_left;
+        struct rb_node *parent = rb_parent(node);
        if ((node->rb_left = left->rb_right))
-                left->rb_right->rb_parent = node;
+                rb_set_parent(left->rb_right, node);
        left->rb_right = node;
-        if ((left->rb_parent = node->rb_parent))
+        rb_set_parent(left, parent);
+        if (parent)
        {
-                if (node == node->rb_parent->rb_right)
+                if (node == parent->rb_right)
-                        node->rb_parent->rb_right = left;
+                        parent->rb_right = left;
                else
-                        node->rb_parent->rb_left = left;
+                        parent->rb_left = left;
        }
        else
                root->rb_node = left;
-        node->rb_parent = left;
+        rb_set_parent(node, left);
 }
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
        struct rb_node *parent, *gparent;
-        while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
+        while ((parent = rb_parent(node)) && rb_is_red(parent))
        {
-                gparent = parent->rb_parent;
+                gparent = rb_parent(parent);
                if (parent == gparent->rb_left)
                {
                        {
                                register struct rb_node *uncle = gparent->rb_right;
-                                if (uncle && uncle->rb_color == RB_RED)
+                                if (uncle && rb_is_red(uncle))
                                {
-                                        uncle->rb_color = RB_BLACK;
+                                        rb_set_black(uncle);
-                                        parent->rb_color = RB_BLACK;
+                                        rb_set_black(parent);
-                                        gparent->rb_color = RB_RED;
+                                        rb_set_red(gparent);
                                        node = gparent;
                                        continue;
                                }
@@ -94,17 +100,17 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
                                node = tmp;
                        }
-                        parent->rb_color = RB_BLACK;
+                        rb_set_black(parent);
-                        gparent->rb_color = RB_RED;
+                        rb_set_red(gparent);
                        __rb_rotate_right(gparent, root);
                } else {
                        {
                                register struct rb_node *uncle = gparent->rb_left;
-                                if (uncle && uncle->rb_color == RB_RED)
+                                if (uncle && rb_is_red(uncle))
                                {
-                                        uncle->rb_color = RB_BLACK;
+                                        rb_set_black(uncle);
-                                        parent->rb_color = RB_BLACK;
+                                        rb_set_black(parent);
-                                        gparent->rb_color = RB_RED;
+                                        rb_set_red(gparent);
                                        node = gparent;
                                        continue;
                                }
@@ -119,13 +125,13 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
                                node = tmp;
                        }
-                        parent->rb_color = RB_BLACK;
+                        rb_set_black(parent);
-                        gparent->rb_color = RB_RED;
+                        rb_set_red(gparent);
                        __rb_rotate_left(gparent, root);
                }
        }
-        root->rb_node->rb_color = RB_BLACK;
+        rb_set_black(root->rb_node);
 }
 EXPORT_SYMBOL(rb_insert_color);
@@ -134,43 +140,40 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 {
        struct rb_node *other;
-        while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
+        while ((!node || rb_is_black(node)) && node != root->rb_node)
        {
                if (parent->rb_left == node)
                {
                        other = parent->rb_right;
-                        if (other->rb_color == RB_RED)
+                        if (rb_is_red(other))
                        {
-                                other->rb_color = RB_BLACK;
+                                rb_set_black(other);
-                                parent->rb_color = RB_RED;
+                                rb_set_red(parent);
                                __rb_rotate_left(parent, root);
                                other = parent->rb_right;
                        }
-                        if ((!other->rb_left ||
+                        if ((!other->rb_left || rb_is_black(other->rb_left)) &&
-                             other->rb_left->rb_color == RB_BLACK)
+                            (!other->rb_right || rb_is_black(other->rb_right)))
-                            && (!other->rb_right ||
-                                other->rb_right->rb_color == RB_BLACK))
                        {
-                                other->rb_color = RB_RED;
+                                rb_set_red(other);
                                node = parent;
-                                parent = node->rb_parent;
+                                parent = rb_parent(node);
                        }
                        else
                        {
-                                if (!other->rb_right ||
+                                if (!other->rb_right || rb_is_black(other->rb_right))
-                                    other->rb_right->rb_color == RB_BLACK)
                                {
-                                        register struct rb_node *o_left;
+                                        struct rb_node *o_left;
                                        if ((o_left = other->rb_left))
-                                                o_left->rb_color = RB_BLACK;
+                                                rb_set_black(o_left);
-                                        other->rb_color = RB_RED;
+                                        rb_set_red(other);
                                        __rb_rotate_right(other, root);
                                        other = parent->rb_right;
                                }
-                                other->rb_color = parent->rb_color;
+                                rb_set_colour(other, rb_colour(parent));
-                                parent->rb_color = RB_BLACK;
+                                rb_set_black(parent);
                                if (other->rb_right)
-                                        other->rb_right->rb_color = RB_BLACK;
+                                        rb_set_black(other->rb_right);
                                __rb_rotate_left(parent, root);
                                node = root->rb_node;
                                break;
@@ -179,38 +182,35 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                else
                {
                        other = parent->rb_left;
-                        if (other->rb_color == RB_RED)
+                        if (rb_is_red(other))
                        {
-                                other->rb_color = RB_BLACK;
+                                rb_set_black(other);
-                                parent->rb_color = RB_RED;
+                                rb_set_red(parent);
                                __rb_rotate_right(parent, root);
                                other = parent->rb_left;
                        }
-                        if ((!other->rb_left ||
+                        if ((!other->rb_left || rb_is_black(other->rb_left)) &&
-                             other->rb_left->rb_color == RB_BLACK)
+                            (!other->rb_right || rb_is_black(other->rb_right)))
-                            && (!other->rb_right ||
-                                other->rb_right->rb_color == RB_BLACK))
                        {
-                                other->rb_color = RB_RED;
+                                rb_set_red(other);
                                node = parent;
-                                parent = node->rb_parent;
+                                parent = rb_parent(node);
                        }
                        else
                        {
-                                if (!other->rb_left ||
+                                if (!other->rb_left || rb_is_black(other->rb_left))
-                                    other->rb_left->rb_color == RB_BLACK)
                                {
                                        register struct rb_node *o_right;
                                        if ((o_right = other->rb_right))
-                                                o_right->rb_color = RB_BLACK;
+                                                rb_set_black(o_right);
-                                        other->rb_color = RB_RED;
+                                        rb_set_red(other);
                                        __rb_rotate_left(other, root);
                                        other = parent->rb_left;
                                }
-                                other->rb_color = parent->rb_color;
+                                rb_set_colour(other, rb_colour(parent));
-                                parent->rb_color = RB_BLACK;
+                                rb_set_black(parent);
                                if (other->rb_left)
-                                        other->rb_left->rb_color = RB_BLACK;
+                                        rb_set_black(other->rb_left);
                                __rb_rotate_right(parent, root);
                                node = root->rb_node;
                                break;
@@ -218,7 +218,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                }
        }
        if (node)
-                node->rb_color = RB_BLACK;
+                rb_set_black(node);
 }
 void rb_erase(struct rb_node *node, struct rb_root *root)
@@ -238,43 +238,41 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
                while ((left = node->rb_left) != NULL)
                        node = left;
                child = node->rb_right;
-                parent = node->rb_parent;
+                parent = rb_parent(node);
-                color = node->rb_color;
+                color = rb_colour(node);
                if (child)
-                        child->rb_parent = parent;
+                        rb_set_parent(child, parent);
+                if (parent == old) {
-                if (node->rb_parent == old) {
                        parent->rb_right = child;
                        parent = node;
-                } else                  
+                } else
                        parent->rb_left = child;
-                node->rb_parent = old->rb_parent;
+                node->rb_parent_colour = old->rb_parent_colour;
-                node->rb_color = old->rb_color;
                node->rb_right = old->rb_right;
                node->rb_left = old->rb_left;
-                if (old->rb_parent)
+                if (rb_parent(old))
                {
-                        if (old->rb_parent->rb_left == old)
+                        if (rb_parent(old)->rb_left == old)
-                                old->rb_parent->rb_left = node;
+                                rb_parent(old)->rb_left = node;
                        else
-                                old->rb_parent->rb_right = node;
+                                rb_parent(old)->rb_right = node;
                } else
                        root->rb_node = node;
-                old->rb_left->rb_parent = node;
+                rb_set_parent(old->rb_left, node);
                if (old->rb_right)
-                        old->rb_right->rb_parent = node;
+                        rb_set_parent(old->rb_right, node);
                goto color;
        }
-        parent = node->rb_parent;
+        parent = rb_parent(node);
-        color = node->rb_color;
+        color = rb_colour(node);
        if (child)
-                child->rb_parent = parent;
+                rb_set_parent(child, parent);
        if (parent)
        {
                if (parent->rb_left == node)
@@ -322,6 +320,8 @@ EXPORT_SYMBOL(rb_last);
 struct rb_node *rb_next(struct rb_node *node)
 {
+        struct rb_node *parent;
        /* If we have a right-hand child, go down and then left as far
           as we can. */
        if (node->rb_right) {
@@ -337,15 +337,17 @@ struct rb_node *rb_next(struct rb_node *node)
           ancestor is a right-hand child of its parent, keep going
           up. First time it's a left-hand child of its parent, said
           parent is our 'next' node. */
-        while (node->rb_parent && node == node->rb_parent->rb_right)
+        while ((parent = rb_parent(node)) && node == parent->rb_right)
-                node = node->rb_parent;
+                node = parent;
-        return node->rb_parent;
+        return parent;
 }
 EXPORT_SYMBOL(rb_next);
 struct rb_node *rb_prev(struct rb_node *node)
 {
+        struct rb_node *parent;
        /* If we have a left-hand child, go down and then right as far
           as we can. */
        if (node->rb_left) {
@@ -357,17 +359,17 @@ struct rb_node *rb_prev(struct rb_node *node)
        /* No left-hand children. Go up till we find an ancestor which
           is a right-hand child of its parent */
-        while (node->rb_parent && node == node->rb_parent->rb_left)
+        while ((parent = rb_parent(node)) && node == parent->rb_left)
-                node = node->rb_parent;
+                node = parent;
-        return node->rb_parent;
+        return parent;
 }
 EXPORT_SYMBOL(rb_prev);
 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
                     struct rb_root *root)
 {
-        struct rb_node *parent = victim->rb_parent;
+        struct rb_node *parent = rb_parent(victim);
        /* Set the surrounding nodes to point to the replacement */
        if (parent) {
@@ -379,9 +381,9 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
                root->rb_node = new;
        }
        if (victim->rb_left)
-                victim->rb_left->rb_parent = new;
+                rb_set_parent(victim->rb_left, new);
        if (victim->rb_right)
-                victim->rb_right->rb_parent = new;
+                rb_set_parent(victim->rb_right, new);
        /* Copy the pointers/colour from the victim to the replacement */
        *new = *victim;
author	David Woodhouse <dwmw2@infradead.org>	2006-04-21 08:35:51 -0400
committer	David Woodhouse <dwmw2@infradead.org>	2006-04-21 08:35:51 -0400
commit	55a981027fc393c86de2c4e7836c9515088a9a58 (patch)
tree	dd950b79d9f57ce48b2b2a91262b88eecb5296da /lib/rbtree.c
parent	1975e59375756da4ff4e6e7d12f67485e813ace0 (diff)

diff --git a/lib/rbtree.c b/lib/rbtree.c index 63473e04f18a..4a7173cad149 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c
@@ -26,60 +26,66 @@
26	static void __rb_rotate_left(struct rb_node node, struct rb_root root)	26	static void __rb_rotate_left(struct rb_node node, struct rb_root root)
27	{	27	{
28	struct rb_node *right = node->rb_right;	28	struct rb_node *right = node->rb_right;
		29	struct rb_node *parent = rb_parent(node);
29		30
30	if ((node->rb_right = right->rb_left))	31	if ((node->rb_right = right->rb_left))
31	right->rb_left->rb_parent = node;	32	rb_set_parent(right->rb_left, node);
32	right->rb_left = node;	33	right->rb_left = node;
33		34
34	if ((right->rb_parent = node->rb_parent))	35	rb_set_parent(right, parent);
		36
		37	if (parent)
35	{	38	{
36	if (node == node->rb_parent->rb_left)	39	if (node == parent->rb_left)
37	node->rb_parent->rb_left = right;	40	parent->rb_left = right;
38	else	41	else
39	node->rb_parent->rb_right = right;	42	parent->rb_right = right;
40	}	43	}
41	else	44	else
42	root->rb_node = right;	45	root->rb_node = right;
43	node->rb_parent = right;	46	rb_set_parent(node, right);
44	}	47	}
45		48
46	static void __rb_rotate_right(struct rb_node node, struct rb_root root)	49	static void __rb_rotate_right(struct rb_node node, struct rb_root root)
47	{	50	{
48	struct rb_node *left = node->rb_left;	51	struct rb_node *left = node->rb_left;
		52	struct rb_node *parent = rb_parent(node);
49		53
50	if ((node->rb_left = left->rb_right))	54	if ((node->rb_left = left->rb_right))
51	left->rb_right->rb_parent = node;	55	rb_set_parent(left->rb_right, node);
52	left->rb_right = node;	56	left->rb_right = node;
53		57
54	if ((left->rb_parent = node->rb_parent))	58	rb_set_parent(left, parent);
		59
		60	if (parent)
55	{	61	{
56	if (node == node->rb_parent->rb_right)	62	if (node == parent->rb_right)
57	node->rb_parent->rb_right = left;	63	parent->rb_right = left;
58	else	64	else
59	node->rb_parent->rb_left = left;	65	parent->rb_left = left;
60	}	66	}
61	else	67	else
62	root->rb_node = left;	68	root->rb_node = left;
63	node->rb_parent = left;	69	rb_set_parent(node, left);
64	}	70	}
65		71
66	void rb_insert_color(struct rb_node node, struct rb_root root)	72	void rb_insert_color(struct rb_node node, struct rb_root root)
67	{	73	{
68	struct rb_node parent, gparent;	74	struct rb_node parent, gparent;
69		75
70	while ((parent = node->rb_parent) && parent->rb_color == RB_RED)	76	while ((parent = rb_parent(node)) && rb_is_red(parent))
71	{	77	{
72	gparent = parent->rb_parent;	78	gparent = rb_parent(parent);
73		79
74	if (parent == gparent->rb_left)	80	if (parent == gparent->rb_left)
75	{	81	{
76	{	82	{
77	register struct rb_node *uncle = gparent->rb_right;	83	register struct rb_node *uncle = gparent->rb_right;
78	if (uncle && uncle->rb_color == RB_RED)	84	if (uncle && rb_is_red(uncle))
79	{	85	{
80	uncle->rb_color = RB_BLACK;	86	rb_set_black(uncle);
81	parent->rb_color = RB_BLACK;	87	rb_set_black(parent);
82	gparent->rb_color = RB_RED;	88	rb_set_red(gparent);
83	node = gparent;	89	node = gparent;
84	continue;	90	continue;
85	}	91	}
@@ -94,17 +100,17 @@ void rb_insert_color(struct rb_node node, struct rb_root root)
94	node = tmp;	100	node = tmp;
95	}	101	}
96		102
97	parent->rb_color = RB_BLACK;	103	rb_set_black(parent);
98	gparent->rb_color = RB_RED;	104	rb_set_red(gparent);
99	__rb_rotate_right(gparent, root);	105	__rb_rotate_right(gparent, root);
100	} else {	106	} else {
101	{	107	{
102	register struct rb_node *uncle = gparent->rb_left;	108	register struct rb_node *uncle = gparent->rb_left;
103	if (uncle && uncle->rb_color == RB_RED)	109	if (uncle && rb_is_red(uncle))
104	{	110	{
105	uncle->rb_color = RB_BLACK;	111	rb_set_black(uncle);
106	parent->rb_color = RB_BLACK;	112	rb_set_black(parent);
107	gparent->rb_color = RB_RED;	113	rb_set_red(gparent);
108	node = gparent;	114	node = gparent;
109	continue;	115	continue;
110	}	116	}
@@ -119,13 +125,13 @@ void rb_insert_color(struct rb_node node, struct rb_root root)
119	node = tmp;	125	node = tmp;
120	}	126	}
121		127
122	parent->rb_color = RB_BLACK;	128	rb_set_black(parent);
123	gparent->rb_color = RB_RED;	129	rb_set_red(gparent);
124	__rb_rotate_left(gparent, root);	130	__rb_rotate_left(gparent, root);
125	}	131	}
126	}	132	}
127		133
128	root->rb_node->rb_color = RB_BLACK;	134	rb_set_black(root->rb_node);
129	}	135	}
130	EXPORT_SYMBOL(rb_insert_color);	136	EXPORT_SYMBOL(rb_insert_color);
131		137
@@ -134,43 +140,40 @@ static void __rb_erase_color(struct rb_node node, struct rb_node parent,
134	{	140	{
135	struct rb_node *other;	141	struct rb_node *other;
136		142
137	while ((!node \|\| node->rb_color == RB_BLACK) && node != root->rb_node)	143	while ((!node \|\| rb_is_black(node)) && node != root->rb_node)
138	{	144	{
139	if (parent->rb_left == node)	145	if (parent->rb_left == node)
140	{	146	{
141	other = parent->rb_right;	147	other = parent->rb_right;
142	if (other->rb_color == RB_RED)	148	if (rb_is_red(other))
143	{	149	{
144	other->rb_color = RB_BLACK;	150	rb_set_black(other);
145	parent->rb_color = RB_RED;	151	rb_set_red(parent);
146	__rb_rotate_left(parent, root);	152	__rb_rotate_left(parent, root);
147	other = parent->rb_right;	153	other = parent->rb_right;
148	}	154	}
149	if ((!other->rb_left \|\|	155	if ((!other->rb_left \|\| rb_is_black(other->rb_left)) &&
150	other->rb_left->rb_color == RB_BLACK)	156	(!other->rb_right \|\| rb_is_black(other->rb_right)))
151	&& (!other->rb_right \|\|
152	other->rb_right->rb_color == RB_BLACK))
153	{	157	{
154	other->rb_color = RB_RED;	158	rb_set_red(other);
155	node = parent;	159	node = parent;
156	parent = node->rb_parent;	160	parent = rb_parent(node);
157	}	161	}
158	else	162	else
159	{	163	{
160	if (!other->rb_right \|\|	164	if (!other->rb_right \|\| rb_is_black(other->rb_right))
161	other->rb_right->rb_color == RB_BLACK)
162	{	165	{
163	register struct rb_node *o_left;	166	struct rb_node *o_left;
164	if ((o_left = other->rb_left))	167	if ((o_left = other->rb_left))
165	o_left->rb_color = RB_BLACK;	168	rb_set_black(o_left);
166	other->rb_color = RB_RED;	169	rb_set_red(other);
167	__rb_rotate_right(other, root);	170	__rb_rotate_right(other, root);
168	other = parent->rb_right;	171	other = parent->rb_right;
169	}	172	}
170	other->rb_color = parent->rb_color;	173	rb_set_colour(other, rb_colour(parent));
171	parent->rb_color = RB_BLACK;	174	rb_set_black(parent);
172	if (other->rb_right)	175	if (other->rb_right)
173	other->rb_right->rb_color = RB_BLACK;	176	rb_set_black(other->rb_right);
174	__rb_rotate_left(parent, root);	177	__rb_rotate_left(parent, root);
175	node = root->rb_node;	178	node = root->rb_node;
176	break;	179	break;
@@ -179,38 +182,35 @@ static void __rb_erase_color(struct rb_node node, struct rb_node parent,
179	else	182	else
180	{	183	{
181	other = parent->rb_left;	184	other = parent->rb_left;
182	if (other->rb_color == RB_RED)	185	if (rb_is_red(other))
183	{	186	{
184	other->rb_color = RB_BLACK;	187	rb_set_black(other);
185	parent->rb_color = RB_RED;	188	rb_set_red(parent);
186	__rb_rotate_right(parent, root);	189	__rb_rotate_right(parent, root);
187	other = parent->rb_left;	190	other = parent->rb_left;
188	}	191	}
189	if ((!other->rb_left \|\|	192	if ((!other->rb_left \|\| rb_is_black(other->rb_left)) &&
190	other->rb_left->rb_color == RB_BLACK)	193	(!other->rb_right \|\| rb_is_black(other->rb_right)))
191	&& (!other->rb_right \|\|
192	other->rb_right->rb_color == RB_BLACK))
193	{	194	{
194	other->rb_color = RB_RED;	195	rb_set_red(other);
195	node = parent;	196	node = parent;
196	parent = node->rb_parent;	197	parent = rb_parent(node);
197	}	198	}
198	else	199	else
199	{	200	{
200	if (!other->rb_left \|\|	201	if (!other->rb_left \|\| rb_is_black(other->rb_left))
201	other->rb_left->rb_color == RB_BLACK)
202	{	202	{
203	register struct rb_node *o_right;	203	register struct rb_node *o_right;
204	if ((o_right = other->rb_right))	204	if ((o_right = other->rb_right))
205	o_right->rb_color = RB_BLACK;	205	rb_set_black(o_right);
206	other->rb_color = RB_RED;	206	rb_set_red(other);
207	__rb_rotate_left(other, root);	207	__rb_rotate_left(other, root);
208	other = parent->rb_left;	208	other = parent->rb_left;
209	}	209	}
210	other->rb_color = parent->rb_color;	210	rb_set_colour(other, rb_colour(parent));
211	parent->rb_color = RB_BLACK;	211	rb_set_black(parent);
212	if (other->rb_left)	212	if (other->rb_left)
213	other->rb_left->rb_color = RB_BLACK;	213	rb_set_black(other->rb_left);
214	__rb_rotate_right(parent, root);	214	__rb_rotate_right(parent, root);
215	node = root->rb_node;	215	node = root->rb_node;
216	break;	216	break;
@@ -218,7 +218,7 @@ static void __rb_erase_color(struct rb_node node, struct rb_node parent,
218	}	218	}
219	}	219	}
220	if (node)	220	if (node)
221	node->rb_color = RB_BLACK;	221	rb_set_black(node);
222	}	222	}
223		223
224	void rb_erase(struct rb_node node, struct rb_root root)	224	void rb_erase(struct rb_node node, struct rb_root root)
@@ -238,43 +238,41 @@ void rb_erase(struct rb_node node, struct rb_root root)
238	while ((left = node->rb_left) != NULL)	238	while ((left = node->rb_left) != NULL)
239	node = left;	239	node = left;
240	child = node->rb_right;	240	child = node->rb_right;
241	parent = node->rb_parent;	241	parent = rb_parent(node);
242	color = node->rb_color;	242	color = rb_colour(node);
243		243
244	if (child)	244	if (child)
245	child->rb_parent = parent;	245	rb_set_parent(child, parent);
246		246	if (parent == old) {
247	if (node->rb_parent == old) {
248	parent->rb_right = child;	247	parent->rb_right = child;
249	parent = node;	248	parent = node;
250	} else	249	} else
251	parent->rb_left = child;	250	parent->rb_left = child;
252		251
253	node->rb_parent = old->rb_parent;	252	node->rb_parent_colour = old->rb_parent_colour;
254	node->rb_color = old->rb_color;
255	node->rb_right = old->rb_right;	253	node->rb_right = old->rb_right;
256	node->rb_left = old->rb_left;	254	node->rb_left = old->rb_left;
257		255
258	if (old->rb_parent)	256	if (rb_parent(old))
259	{	257	{
260	if (old->rb_parent->rb_left == old)	258	if (rb_parent(old)->rb_left == old)
261	old->rb_parent->rb_left = node;	259	rb_parent(old)->rb_left = node;
262	else	260	else
263	old->rb_parent->rb_right = node;	261	rb_parent(old)->rb_right = node;
264	} else	262	} else
265	root->rb_node = node;	263	root->rb_node = node;
266		264
267	old->rb_left->rb_parent = node;	265	rb_set_parent(old->rb_left, node);
268	if (old->rb_right)	266	if (old->rb_right)
269	old->rb_right->rb_parent = node;	267	rb_set_parent(old->rb_right, node);
270	goto color;	268	goto color;
271	}	269	}
272		270
273	parent = node->rb_parent;	271	parent = rb_parent(node);
274	color = node->rb_color;	272	color = rb_colour(node);
275		273
276	if (child)	274	if (child)
277	child->rb_parent = parent;	275	rb_set_parent(child, parent);
278	if (parent)	276	if (parent)
279	{	277	{
280	if (parent->rb_left == node)	278	if (parent->rb_left == node)
@@ -322,6 +320,8 @@ EXPORT_SYMBOL(rb_last);
322		320
323	struct rb_node rb_next(struct rb_node node)	321	struct rb_node rb_next(struct rb_node node)
324	{	322	{
		323	struct rb_node *parent;
		324
325	/* If we have a right-hand child, go down and then left as far	325	/* If we have a right-hand child, go down and then left as far
326	as we can. */	326	as we can. */
327	if (node->rb_right) {	327	if (node->rb_right) {
@@ -337,15 +337,17 @@ struct rb_node rb_next(struct rb_node node)
337	ancestor is a right-hand child of its parent, keep going	337	ancestor is a right-hand child of its parent, keep going
338	up. First time it's a left-hand child of its parent, said	338	up. First time it's a left-hand child of its parent, said
339	parent is our 'next' node. */	339	parent is our 'next' node. */
340	while (node->rb_parent && node == node->rb_parent->rb_right)	340	while ((parent = rb_parent(node)) && node == parent->rb_right)
341	node = node->rb_parent;	341	node = parent;
342		342
343	return node->rb_parent;	343	return parent;
344	}	344	}
345	EXPORT_SYMBOL(rb_next);	345	EXPORT_SYMBOL(rb_next);
346		346
347	struct rb_node rb_prev(struct rb_node node)	347	struct rb_node rb_prev(struct rb_node node)
348	{	348	{
		349	struct rb_node *parent;
		350
349	/* If we have a left-hand child, go down and then right as far	351	/* If we have a left-hand child, go down and then right as far
350	as we can. */	352	as we can. */
351	if (node->rb_left) {	353	if (node->rb_left) {
@@ -357,17 +359,17 @@ struct rb_node rb_prev(struct rb_node node)
357		359
358	/* No left-hand children. Go up till we find an ancestor which	360	/* No left-hand children. Go up till we find an ancestor which
359	is a right-hand child of its parent */	361	is a right-hand child of its parent */
360	while (node->rb_parent && node == node->rb_parent->rb_left)	362	while ((parent = rb_parent(node)) && node == parent->rb_left)
361	node = node->rb_parent;	363	node = parent;
362		364
363	return node->rb_parent;	365	return parent;
364	}	366	}
365	EXPORT_SYMBOL(rb_prev);	367	EXPORT_SYMBOL(rb_prev);
366		368
367	void rb_replace_node(struct rb_node victim, struct rb_node new,	369	void rb_replace_node(struct rb_node victim, struct rb_node new,
368	struct rb_root *root)	370	struct rb_root *root)
369	{	371	{
370	struct rb_node *parent = victim->rb_parent;	372	struct rb_node *parent = rb_parent(victim);
371		373
372	/* Set the surrounding nodes to point to the replacement */	374	/* Set the surrounding nodes to point to the replacement */
373	if (parent) {	375	if (parent) {
@@ -379,9 +381,9 @@ void rb_replace_node(struct rb_node victim, struct rb_node new,
379	root->rb_node = new;	381	root->rb_node = new;
380	}	382	}
381	if (victim->rb_left)	383	if (victim->rb_left)
382	victim->rb_left->rb_parent = new;	384	rb_set_parent(victim->rb_left, new);
383	if (victim->rb_right)	385	if (victim->rb_right)
384	victim->rb_right->rb_parent = new;	386	rb_set_parent(victim->rb_right, new);
385		387
386	/* Copy the pointers/colour from the victim to the replacement */	388	/* Copy the pointers/colour from the victim to the replacement */
387	new = victim;	389	new = victim;