cpusets: randomize node rotor used in cpuset_mem_spread_node()
[linux-2.6/linux-acpi-2.6/ibm-acpi-2.6.git] / lib / rbtree.c
blob15e10b1afdd279aad26ebbf869a5fd824831fe5f
1 /*
2 Red Black Trees
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 linux/lib/rbtree.c
23 #include <linux/rbtree.h>
24 #include <linux/module.h>
26 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
28 struct rb_node *right = node->rb_right;
29 struct rb_node *parent = rb_parent(node);
31 if ((node->rb_right = right->rb_left))
32 rb_set_parent(right->rb_left, node);
33 right->rb_left = node;
35 rb_set_parent(right, parent);
37 if (parent)
39 if (node == parent->rb_left)
40 parent->rb_left = right;
41 else
42 parent->rb_right = right;
44 else
45 root->rb_node = right;
46 rb_set_parent(node, right);
48 if (root->augment_cb) {
49 root->augment_cb(node);
50 root->augment_cb(right);
54 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
56 struct rb_node *left = node->rb_left;
57 struct rb_node *parent = rb_parent(node);
59 if ((node->rb_left = left->rb_right))
60 rb_set_parent(left->rb_right, node);
61 left->rb_right = node;
63 rb_set_parent(left, parent);
65 if (parent)
67 if (node == parent->rb_right)
68 parent->rb_right = left;
69 else
70 parent->rb_left = left;
72 else
73 root->rb_node = left;
74 rb_set_parent(node, left);
76 if (root->augment_cb) {
77 root->augment_cb(node);
78 root->augment_cb(left);
82 void rb_insert_color(struct rb_node *node, struct rb_root *root)
84 struct rb_node *parent, *gparent;
86 if (root->augment_cb)
87 root->augment_cb(node);
89 while ((parent = rb_parent(node)) && rb_is_red(parent))
91 gparent = rb_parent(parent);
93 if (parent == gparent->rb_left)
96 register struct rb_node *uncle = gparent->rb_right;
97 if (uncle && rb_is_red(uncle))
99 rb_set_black(uncle);
100 rb_set_black(parent);
101 rb_set_red(gparent);
102 node = gparent;
103 continue;
107 if (parent->rb_right == node)
109 register struct rb_node *tmp;
110 __rb_rotate_left(parent, root);
111 tmp = parent;
112 parent = node;
113 node = tmp;
116 rb_set_black(parent);
117 rb_set_red(gparent);
118 __rb_rotate_right(gparent, root);
119 } else {
121 register struct rb_node *uncle = gparent->rb_left;
122 if (uncle && rb_is_red(uncle))
124 rb_set_black(uncle);
125 rb_set_black(parent);
126 rb_set_red(gparent);
127 node = gparent;
128 continue;
132 if (parent->rb_left == node)
134 register struct rb_node *tmp;
135 __rb_rotate_right(parent, root);
136 tmp = parent;
137 parent = node;
138 node = tmp;
141 rb_set_black(parent);
142 rb_set_red(gparent);
143 __rb_rotate_left(gparent, root);
147 rb_set_black(root->rb_node);
149 EXPORT_SYMBOL(rb_insert_color);
151 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
152 struct rb_root *root)
154 struct rb_node *other;
156 while ((!node || rb_is_black(node)) && node != root->rb_node)
158 if (parent->rb_left == node)
160 other = parent->rb_right;
161 if (rb_is_red(other))
163 rb_set_black(other);
164 rb_set_red(parent);
165 __rb_rotate_left(parent, root);
166 other = parent->rb_right;
168 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
169 (!other->rb_right || rb_is_black(other->rb_right)))
171 rb_set_red(other);
172 node = parent;
173 parent = rb_parent(node);
175 else
177 if (!other->rb_right || rb_is_black(other->rb_right))
179 rb_set_black(other->rb_left);
180 rb_set_red(other);
181 __rb_rotate_right(other, root);
182 other = parent->rb_right;
184 rb_set_color(other, rb_color(parent));
185 rb_set_black(parent);
186 rb_set_black(other->rb_right);
187 __rb_rotate_left(parent, root);
188 node = root->rb_node;
189 break;
192 else
194 other = parent->rb_left;
195 if (rb_is_red(other))
197 rb_set_black(other);
198 rb_set_red(parent);
199 __rb_rotate_right(parent, root);
200 other = parent->rb_left;
202 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
203 (!other->rb_right || rb_is_black(other->rb_right)))
205 rb_set_red(other);
206 node = parent;
207 parent = rb_parent(node);
209 else
211 if (!other->rb_left || rb_is_black(other->rb_left))
213 rb_set_black(other->rb_right);
214 rb_set_red(other);
215 __rb_rotate_left(other, root);
216 other = parent->rb_left;
218 rb_set_color(other, rb_color(parent));
219 rb_set_black(parent);
220 rb_set_black(other->rb_left);
221 __rb_rotate_right(parent, root);
222 node = root->rb_node;
223 break;
227 if (node)
228 rb_set_black(node);
231 void rb_erase(struct rb_node *node, struct rb_root *root)
233 struct rb_node *child, *parent;
234 int color;
236 if (!node->rb_left)
237 child = node->rb_right;
238 else if (!node->rb_right)
239 child = node->rb_left;
240 else
242 struct rb_node *old = node, *left;
243 int old_parent_cb = 0;
244 int successor_parent_cb = 0;
246 node = node->rb_right;
247 while ((left = node->rb_left) != NULL)
248 node = left;
250 if (rb_parent(old)) {
251 old_parent_cb = 1;
252 if (rb_parent(old)->rb_left == old)
253 rb_parent(old)->rb_left = node;
254 else
255 rb_parent(old)->rb_right = node;
256 } else
257 root->rb_node = node;
259 child = node->rb_right;
260 parent = rb_parent(node);
261 color = rb_color(node);
263 if (parent == old) {
264 parent = node;
265 } else {
266 successor_parent_cb = 1;
267 if (child)
268 rb_set_parent(child, parent);
270 parent->rb_left = child;
272 node->rb_right = old->rb_right;
273 rb_set_parent(old->rb_right, node);
276 node->rb_parent_color = old->rb_parent_color;
277 node->rb_left = old->rb_left;
278 rb_set_parent(old->rb_left, node);
280 if (root->augment_cb) {
282 * Here, three different nodes can have new children.
283 * The parent of the successor node that was selected
284 * to replace the node to be erased.
285 * The node that is getting erased and is now replaced
286 * by its successor.
287 * The parent of the node getting erased-replaced.
289 if (successor_parent_cb)
290 root->augment_cb(parent);
292 root->augment_cb(node);
294 if (old_parent_cb)
295 root->augment_cb(rb_parent(old));
298 goto color;
301 parent = rb_parent(node);
302 color = rb_color(node);
304 if (child)
305 rb_set_parent(child, parent);
307 if (parent) {
308 if (parent->rb_left == node)
309 parent->rb_left = child;
310 else
311 parent->rb_right = child;
313 if (root->augment_cb)
314 root->augment_cb(parent);
316 } else {
317 root->rb_node = child;
320 color:
321 if (color == RB_BLACK)
322 __rb_erase_color(child, parent, root);
324 EXPORT_SYMBOL(rb_erase);
327 * This function returns the first node (in sort order) of the tree.
329 struct rb_node *rb_first(const struct rb_root *root)
331 struct rb_node *n;
333 n = root->rb_node;
334 if (!n)
335 return NULL;
336 while (n->rb_left)
337 n = n->rb_left;
338 return n;
340 EXPORT_SYMBOL(rb_first);
342 struct rb_node *rb_last(const struct rb_root *root)
344 struct rb_node *n;
346 n = root->rb_node;
347 if (!n)
348 return NULL;
349 while (n->rb_right)
350 n = n->rb_right;
351 return n;
353 EXPORT_SYMBOL(rb_last);
355 struct rb_node *rb_next(const struct rb_node *node)
357 struct rb_node *parent;
359 if (rb_parent(node) == node)
360 return NULL;
362 /* If we have a right-hand child, go down and then left as far
363 as we can. */
364 if (node->rb_right) {
365 node = node->rb_right;
366 while (node->rb_left)
367 node=node->rb_left;
368 return (struct rb_node *)node;
371 /* No right-hand children. Everything down and left is
372 smaller than us, so any 'next' node must be in the general
373 direction of our parent. Go up the tree; any time the
374 ancestor is a right-hand child of its parent, keep going
375 up. First time it's a left-hand child of its parent, said
376 parent is our 'next' node. */
377 while ((parent = rb_parent(node)) && node == parent->rb_right)
378 node = parent;
380 return parent;
382 EXPORT_SYMBOL(rb_next);
384 struct rb_node *rb_prev(const struct rb_node *node)
386 struct rb_node *parent;
388 if (rb_parent(node) == node)
389 return NULL;
391 /* If we have a left-hand child, go down and then right as far
392 as we can. */
393 if (node->rb_left) {
394 node = node->rb_left;
395 while (node->rb_right)
396 node=node->rb_right;
397 return (struct rb_node *)node;
400 /* No left-hand children. Go up till we find an ancestor which
401 is a right-hand child of its parent */
402 while ((parent = rb_parent(node)) && node == parent->rb_left)
403 node = parent;
405 return parent;
407 EXPORT_SYMBOL(rb_prev);
409 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
410 struct rb_root *root)
412 struct rb_node *parent = rb_parent(victim);
414 /* Set the surrounding nodes to point to the replacement */
415 if (parent) {
416 if (victim == parent->rb_left)
417 parent->rb_left = new;
418 else
419 parent->rb_right = new;
420 } else {
421 root->rb_node = new;
423 if (victim->rb_left)
424 rb_set_parent(victim->rb_left, new);
425 if (victim->rb_right)
426 rb_set_parent(victim->rb_right, new);
428 /* Copy the pointers/colour from the victim to the replacement */
429 *new = *victim;
431 EXPORT_SYMBOL(rb_replace_node);