aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@g5.osdl.org>2006-06-20 17:51:22 -0400
committerLinus Torvalds <torvalds@g5.osdl.org>2006-06-20 17:51:22 -0400
commit2edc322d420a4cec8dbc184a1220ecd7fa9f8ae6 (patch)
treee7be2cf442626316b6b6fb212960fe1f77ff2725 /lib
parentbe967b7e2f7747a5ebf2a07ee627d9338491e784 (diff)
parent2f3243aebd8df4d9eecaeca04bbff6c7dbfb2142 (diff)
Merge git://git.infradead.org/~dwmw2/rbtree-2.6
* git://git.infradead.org/~dwmw2/rbtree-2.6: [RBTREE] Switch rb_colour() et al to en_US spelling of 'color' for consistency Update UML kernel/physmem.c to use rb_parent() accessor macro [RBTREE] Update hrtimers to use rb_parent() accessor macro. [RBTREE] Add explicit alignment to sizeof(long) for struct rb_node. [RBTREE] Merge colour and parent fields of struct rb_node. [RBTREE] Remove dead code in rb_erase() [RBTREE] Update JFFS2 to use rb_parent() accessor macro. [RBTREE] Update eventpoll.c to use rb_parent() accessor macro. [RBTREE] Update key.c to use rb_parent() accessor macro. [RBTREE] Update ext3 to use rb_parent() accessor macro. [RBTREE] Change rbtree off-tree marking in I/O schedulers. [RBTREE] Add accessor macros for colour and parent fields of rb_node
Diffstat (limited to 'lib')
-rw-r--r--lib/rbtree.c189
1 files changed, 93 insertions, 96 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 14b791ac5089..1e55ba1c2edf 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -26,60 +26,66 @@
26static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) 26static 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
46static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 49static 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
66void rb_insert_color(struct rb_node *node, struct rb_root *root) 72void 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}
130EXPORT_SYMBOL(rb_insert_color); 136EXPORT_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_color(other, rb_color(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_color(other, rb_color(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
224void rb_erase(struct rb_node *node, struct rb_root *root) 224void rb_erase(struct rb_node *node, struct rb_root *root)
@@ -238,48 +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_color(node);
243 243
244 if (child) 244 if (child)
245 child->rb_parent = parent; 245 rb_set_parent(child, parent);
246 if (parent) 246 if (parent == old) {
247 { 247 parent->rb_right = child;
248 if (parent->rb_left == node)
249 parent->rb_left = child;
250 else
251 parent->rb_right = child;
252 }
253 else
254 root->rb_node = child;
255
256 if (node->rb_parent == old)
257 parent = node; 248 parent = node;
258 node->rb_parent = old->rb_parent; 249 } else
259 node->rb_color = old->rb_color; 250 parent->rb_left = child;
251
252 node->rb_parent_color = old->rb_parent_color;
260 node->rb_right = old->rb_right; 253 node->rb_right = old->rb_right;
261 node->rb_left = old->rb_left; 254 node->rb_left = old->rb_left;
262 255
263 if (old->rb_parent) 256 if (rb_parent(old))
264 { 257 {
265 if (old->rb_parent->rb_left == old) 258 if (rb_parent(old)->rb_left == old)
266 old->rb_parent->rb_left = node; 259 rb_parent(old)->rb_left = node;
267 else 260 else
268 old->rb_parent->rb_right = node; 261 rb_parent(old)->rb_right = node;
269 } else 262 } else
270 root->rb_node = node; 263 root->rb_node = node;
271 264
272 old->rb_left->rb_parent = node; 265 rb_set_parent(old->rb_left, node);
273 if (old->rb_right) 266 if (old->rb_right)
274 old->rb_right->rb_parent = node; 267 rb_set_parent(old->rb_right, node);
275 goto color; 268 goto color;
276 } 269 }
277 270
278 parent = node->rb_parent; 271 parent = rb_parent(node);
279 color = node->rb_color; 272 color = rb_color(node);
280 273
281 if (child) 274 if (child)
282 child->rb_parent = parent; 275 rb_set_parent(child, parent);
283 if (parent) 276 if (parent)
284 { 277 {
285 if (parent->rb_left == node) 278 if (parent->rb_left == node)
@@ -327,6 +320,8 @@ EXPORT_SYMBOL(rb_last);
327 320
328struct rb_node *rb_next(struct rb_node *node) 321struct rb_node *rb_next(struct rb_node *node)
329{ 322{
323 struct rb_node *parent;
324
330 /* 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
331 as we can. */ 326 as we can. */
332 if (node->rb_right) { 327 if (node->rb_right) {
@@ -342,15 +337,17 @@ struct rb_node *rb_next(struct rb_node *node)
342 ancestor is a right-hand child of its parent, keep going 337 ancestor is a right-hand child of its parent, keep going
343 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
344 parent is our 'next' node. */ 339 parent is our 'next' node. */
345 while (node->rb_parent && node == node->rb_parent->rb_right) 340 while ((parent = rb_parent(node)) && node == parent->rb_right)
346 node = node->rb_parent; 341 node = parent;
347 342
348 return node->rb_parent; 343 return parent;
349} 344}
350EXPORT_SYMBOL(rb_next); 345EXPORT_SYMBOL(rb_next);
351 346
352struct rb_node *rb_prev(struct rb_node *node) 347struct rb_node *rb_prev(struct rb_node *node)
353{ 348{
349 struct rb_node *parent;
350
354 /* 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
355 as we can. */ 352 as we can. */
356 if (node->rb_left) { 353 if (node->rb_left) {
@@ -362,17 +359,17 @@ struct rb_node *rb_prev(struct rb_node *node)
362 359
363 /* 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
364 is a right-hand child of its parent */ 361 is a right-hand child of its parent */
365 while (node->rb_parent && node == node->rb_parent->rb_left) 362 while ((parent = rb_parent(node)) && node == parent->rb_left)
366 node = node->rb_parent; 363 node = parent;
367 364
368 return node->rb_parent; 365 return parent;
369} 366}
370EXPORT_SYMBOL(rb_prev); 367EXPORT_SYMBOL(rb_prev);
371 368
372void rb_replace_node(struct rb_node *victim, struct rb_node *new, 369void rb_replace_node(struct rb_node *victim, struct rb_node *new,
373 struct rb_root *root) 370 struct rb_root *root)
374{ 371{
375 struct rb_node *parent = victim->rb_parent; 372 struct rb_node *parent = rb_parent(victim);
376 373
377 /* Set the surrounding nodes to point to the replacement */ 374 /* Set the surrounding nodes to point to the replacement */
378 if (parent) { 375 if (parent) {
@@ -384,9 +381,9 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
384 root->rb_node = new; 381 root->rb_node = new;
385 } 382 }
386 if (victim->rb_left) 383 if (victim->rb_left)
387 victim->rb_left->rb_parent = new; 384 rb_set_parent(victim->rb_left, new);
388 if (victim->rb_right) 385 if (victim->rb_right)
389 victim->rb_right->rb_parent = new; 386 rb_set_parent(victim->rb_right, new);
390 387
391 /* Copy the pointers/colour from the victim to the replacement */ 388 /* Copy the pointers/colour from the victim to the replacement */
392 *new = *victim; 389 *new = *victim;
generated by cgit v1.2.2 (git 2.25.0) at 2024-10-01 18:28:50 -0400