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
23 #include <linux/rbtree.h>
24 #include <linux/export.h>
29 #define rb_color(r) ((r)->__rb_parent_color & 1)
30 #define rb_is_red(r) (!rb_color(r))
31 #define rb_is_black(r) rb_color(r)
32 #define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0)
33 #define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0)
35 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
37 rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
39 static inline void rb_set_color(struct rb_node *rb, int color)
41 rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color;
44 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
46 struct rb_node *right = node->rb_right;
47 struct rb_node *parent = rb_parent(node);
49 if ((node->rb_right = right->rb_left))
50 rb_set_parent(right->rb_left, node);
51 right->rb_left = node;
53 rb_set_parent(right, parent);
57 if (node == parent->rb_left)
58 parent->rb_left = right;
60 parent->rb_right = right;
63 root->rb_node = right;
64 rb_set_parent(node, right);
67 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
69 struct rb_node *left = node->rb_left;
70 struct rb_node *parent = rb_parent(node);
72 if ((node->rb_left = left->rb_right))
73 rb_set_parent(left->rb_right, node);
74 left->rb_right = node;
76 rb_set_parent(left, parent);
80 if (node == parent->rb_right)
81 parent->rb_right = left;
83 parent->rb_left = left;
87 rb_set_parent(node, left);
90 void rb_insert_color(struct rb_node *node, struct rb_root *root)
92 struct rb_node *parent, *gparent;
96 * Loop invariant: node is red
98 * If there is a black parent, we are done.
99 * Otherwise, take some corrective action as we don't
100 * want a red root or two consecutive red nodes.
102 parent = rb_parent(node);
106 } else if (rb_is_black(parent))
109 gparent = rb_parent(parent);
111 if (parent == gparent->rb_left)
114 register struct rb_node *uncle = gparent->rb_right;
115 if (uncle && rb_is_red(uncle))
118 rb_set_black(parent);
125 if (parent->rb_right == node) {
126 __rb_rotate_left(parent, root);
130 rb_set_black(parent);
132 __rb_rotate_right(gparent, root);
136 register struct rb_node *uncle = gparent->rb_left;
137 if (uncle && rb_is_red(uncle))
140 rb_set_black(parent);
147 if (parent->rb_left == node) {
148 __rb_rotate_right(parent, root);
152 rb_set_black(parent);
154 __rb_rotate_left(gparent, root);
159 EXPORT_SYMBOL(rb_insert_color);
161 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
162 struct rb_root *root)
164 struct rb_node *other;
166 while ((!node || rb_is_black(node)) && node != root->rb_node)
168 if (parent->rb_left == node)
170 other = parent->rb_right;
171 if (rb_is_red(other))
175 __rb_rotate_left(parent, root);
176 other = parent->rb_right;
178 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
179 (!other->rb_right || rb_is_black(other->rb_right)))
183 parent = rb_parent(node);
187 if (!other->rb_right || rb_is_black(other->rb_right))
189 rb_set_black(other->rb_left);
191 __rb_rotate_right(other, root);
192 other = parent->rb_right;
194 rb_set_color(other, rb_color(parent));
195 rb_set_black(parent);
196 rb_set_black(other->rb_right);
197 __rb_rotate_left(parent, root);
198 node = root->rb_node;
204 other = parent->rb_left;
205 if (rb_is_red(other))
209 __rb_rotate_right(parent, root);
210 other = parent->rb_left;
212 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
213 (!other->rb_right || rb_is_black(other->rb_right)))
217 parent = rb_parent(node);
221 if (!other->rb_left || rb_is_black(other->rb_left))
223 rb_set_black(other->rb_right);
225 __rb_rotate_left(other, root);
226 other = parent->rb_left;
228 rb_set_color(other, rb_color(parent));
229 rb_set_black(parent);
230 rb_set_black(other->rb_left);
231 __rb_rotate_right(parent, root);
232 node = root->rb_node;
241 void rb_erase(struct rb_node *node, struct rb_root *root)
243 struct rb_node *child, *parent;
247 child = node->rb_right;
248 else if (!node->rb_right)
249 child = node->rb_left;
252 struct rb_node *old = node, *left;
254 node = node->rb_right;
255 while ((left = node->rb_left) != NULL)
258 if (rb_parent(old)) {
259 if (rb_parent(old)->rb_left == old)
260 rb_parent(old)->rb_left = node;
262 rb_parent(old)->rb_right = node;
264 root->rb_node = node;
266 child = node->rb_right;
267 parent = rb_parent(node);
268 color = rb_color(node);
274 rb_set_parent(child, parent);
275 parent->rb_left = child;
277 node->rb_right = old->rb_right;
278 rb_set_parent(old->rb_right, node);
281 node->__rb_parent_color = old->__rb_parent_color;
282 node->rb_left = old->rb_left;
283 rb_set_parent(old->rb_left, node);
288 parent = rb_parent(node);
289 color = rb_color(node);
292 rb_set_parent(child, parent);
295 if (parent->rb_left == node)
296 parent->rb_left = child;
298 parent->rb_right = child;
301 root->rb_node = child;
304 if (color == RB_BLACK)
305 __rb_erase_color(child, parent, root);
307 EXPORT_SYMBOL(rb_erase);
309 static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
311 struct rb_node *parent;
315 parent = rb_parent(node);
319 if (node == parent->rb_left && parent->rb_right)
320 func(parent->rb_right, data);
321 else if (parent->rb_left)
322 func(parent->rb_left, data);
329 * after inserting @node into the tree, update the tree to account for
330 * both the new entry and any damage done by rebalance
332 void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
335 node = node->rb_left;
336 else if (node->rb_right)
337 node = node->rb_right;
339 rb_augment_path(node, func, data);
341 EXPORT_SYMBOL(rb_augment_insert);
344 * before removing the node, find the deepest node on the rebalance path
345 * that will still be there after @node gets removed
347 struct rb_node *rb_augment_erase_begin(struct rb_node *node)
349 struct rb_node *deepest;
351 if (!node->rb_right && !node->rb_left)
352 deepest = rb_parent(node);
353 else if (!node->rb_right)
354 deepest = node->rb_left;
355 else if (!node->rb_left)
356 deepest = node->rb_right;
358 deepest = rb_next(node);
359 if (deepest->rb_right)
360 deepest = deepest->rb_right;
361 else if (rb_parent(deepest) != node)
362 deepest = rb_parent(deepest);
367 EXPORT_SYMBOL(rb_augment_erase_begin);
370 * after removal, update the tree to account for the removed entry
371 * and any rebalance damage.
373 void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
376 rb_augment_path(node, func, data);
378 EXPORT_SYMBOL(rb_augment_erase_end);
381 * This function returns the first node (in sort order) of the tree.
383 struct rb_node *rb_first(const struct rb_root *root)
394 EXPORT_SYMBOL(rb_first);
396 struct rb_node *rb_last(const struct rb_root *root)
407 EXPORT_SYMBOL(rb_last);
409 struct rb_node *rb_next(const struct rb_node *node)
411 struct rb_node *parent;
413 if (RB_EMPTY_NODE(node))
416 /* If we have a right-hand child, go down and then left as far
418 if (node->rb_right) {
419 node = node->rb_right;
420 while (node->rb_left)
422 return (struct rb_node *)node;
425 /* No right-hand children. Everything down and left is
426 smaller than us, so any 'next' node must be in the general
427 direction of our parent. Go up the tree; any time the
428 ancestor is a right-hand child of its parent, keep going
429 up. First time it's a left-hand child of its parent, said
430 parent is our 'next' node. */
431 while ((parent = rb_parent(node)) && node == parent->rb_right)
436 EXPORT_SYMBOL(rb_next);
438 struct rb_node *rb_prev(const struct rb_node *node)
440 struct rb_node *parent;
442 if (RB_EMPTY_NODE(node))
445 /* If we have a left-hand child, go down and then right as far
448 node = node->rb_left;
449 while (node->rb_right)
451 return (struct rb_node *)node;
454 /* No left-hand children. Go up till we find an ancestor which
455 is a right-hand child of its parent */
456 while ((parent = rb_parent(node)) && node == parent->rb_left)
461 EXPORT_SYMBOL(rb_prev);
463 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
464 struct rb_root *root)
466 struct rb_node *parent = rb_parent(victim);
468 /* Set the surrounding nodes to point to the replacement */
470 if (victim == parent->rb_left)
471 parent->rb_left = new;
473 parent->rb_right = new;
478 rb_set_parent(victim->rb_left, new);
479 if (victim->rb_right)
480 rb_set_parent(victim->rb_right, new);
482 /* Copy the pointers/colour from the victim to the replacement */
485 EXPORT_SYMBOL(rb_replace_node);