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
27 #define EXPORT_SYMBOL(foo)
29 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
31 struct rb_node *right = node->rb_right;
32 struct rb_node *parent = rb_parent(node);
34 if ((node->rb_right = right->rb_left))
35 rb_set_parent(right->rb_left, node);
36 right->rb_left = node;
38 rb_set_parent(right, parent);
42 if (node == parent->rb_left)
43 parent->rb_left = right;
45 parent->rb_right = right;
48 root->rb_node = right;
49 rb_set_parent(node, right);
52 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
54 struct rb_node *left = node->rb_left;
55 struct rb_node *parent = rb_parent(node);
57 if ((node->rb_left = left->rb_right))
58 rb_set_parent(left->rb_right, node);
59 left->rb_right = node;
61 rb_set_parent(left, parent);
65 if (node == parent->rb_right)
66 parent->rb_right = left;
68 parent->rb_left = left;
72 rb_set_parent(node, left);
75 void rb_insert_color(struct rb_node *node, struct rb_root *root)
77 struct rb_node *parent, *gparent;
79 while ((parent = rb_parent(node)) && rb_is_red(parent))
81 gparent = rb_parent(parent);
83 if (parent == gparent->rb_left)
86 register struct rb_node *uncle = gparent->rb_right;
87 if (uncle && rb_is_red(uncle))
97 if (parent->rb_right == node)
99 register struct rb_node *tmp;
100 __rb_rotate_left(parent, root);
106 rb_set_black(parent);
108 __rb_rotate_right(gparent, root);
111 register struct rb_node *uncle = gparent->rb_left;
112 if (uncle && rb_is_red(uncle))
115 rb_set_black(parent);
122 if (parent->rb_left == node)
124 register struct rb_node *tmp;
125 __rb_rotate_right(parent, root);
131 rb_set_black(parent);
133 __rb_rotate_left(gparent, root);
137 rb_set_black(root->rb_node);
139 EXPORT_SYMBOL(rb_insert_color);
141 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
142 struct rb_root *root)
144 struct rb_node *other;
146 while ((!node || rb_is_black(node)) && node != root->rb_node)
148 if (parent->rb_left == node)
150 other = parent->rb_right;
151 if (rb_is_red(other))
155 __rb_rotate_left(parent, root);
156 other = parent->rb_right;
158 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
159 (!other->rb_right || rb_is_black(other->rb_right)))
163 parent = rb_parent(node);
167 if (!other->rb_right || rb_is_black(other->rb_right))
169 rb_set_black(other->rb_left);
171 __rb_rotate_right(other, root);
172 other = parent->rb_right;
174 rb_set_color(other, rb_color(parent));
175 rb_set_black(parent);
176 rb_set_black(other->rb_right);
177 __rb_rotate_left(parent, root);
178 node = root->rb_node;
184 other = parent->rb_left;
185 if (rb_is_red(other))
189 __rb_rotate_right(parent, root);
190 other = parent->rb_left;
192 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
193 (!other->rb_right || rb_is_black(other->rb_right)))
197 parent = rb_parent(node);
201 if (!other->rb_left || rb_is_black(other->rb_left))
203 rb_set_black(other->rb_right);
205 __rb_rotate_left(other, root);
206 other = parent->rb_left;
208 rb_set_color(other, rb_color(parent));
209 rb_set_black(parent);
210 rb_set_black(other->rb_left);
211 __rb_rotate_right(parent, root);
212 node = root->rb_node;
221 void rb_erase(struct rb_node *node, struct rb_root *root)
223 struct rb_node *child, *parent;
227 child = node->rb_right;
228 else if (!node->rb_right)
229 child = node->rb_left;
232 struct rb_node *old = node, *left;
234 node = node->rb_right;
235 while ((left = node->rb_left) != NULL)
238 if (rb_parent(old)) {
239 if (rb_parent(old)->rb_left == old)
240 rb_parent(old)->rb_left = node;
242 rb_parent(old)->rb_right = node;
244 root->rb_node = node;
246 child = node->rb_right;
247 parent = rb_parent(node);
248 color = rb_color(node);
254 rb_set_parent(child, parent);
255 parent->rb_left = child;
257 node->rb_right = old->rb_right;
258 rb_set_parent(old->rb_right, node);
261 node->rb_parent_color = old->rb_parent_color;
262 node->rb_left = old->rb_left;
263 rb_set_parent(old->rb_left, node);
268 parent = rb_parent(node);
269 color = rb_color(node);
272 rb_set_parent(child, parent);
275 if (parent->rb_left == node)
276 parent->rb_left = child;
278 parent->rb_right = child;
281 root->rb_node = child;
284 if (color == RB_BLACK)
285 __rb_erase_color(child, parent, root);
287 EXPORT_SYMBOL(rb_erase);
289 static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
291 struct rb_node *parent;
295 parent = rb_parent(node);
299 if (node == parent->rb_left && parent->rb_right)
300 func(parent->rb_right, data);
301 else if (parent->rb_left)
302 func(parent->rb_left, data);
309 * after inserting @node into the tree, update the tree to account for
310 * both the new entry and any damage done by rebalance
312 void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
315 node = node->rb_left;
316 else if (node->rb_right)
317 node = node->rb_right;
319 rb_augment_path(node, func, data);
321 EXPORT_SYMBOL(rb_augment_insert);
324 * before removing the node, find the deepest node on the rebalance path
325 * that will still be there after @node gets removed
327 struct rb_node *rb_augment_erase_begin(struct rb_node *node)
329 struct rb_node *deepest;
331 if (!node->rb_right && !node->rb_left)
332 deepest = rb_parent(node);
333 else if (!node->rb_right)
334 deepest = node->rb_left;
335 else if (!node->rb_left)
336 deepest = node->rb_right;
338 deepest = rb_next(node);
339 if (deepest->rb_right)
340 deepest = deepest->rb_right;
341 else if (rb_parent(deepest) != node)
342 deepest = rb_parent(deepest);
347 EXPORT_SYMBOL(rb_augment_erase_begin);
350 * after removal, update the tree to account for the removed entry
351 * and any rebalance damage.
353 void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
356 rb_augment_path(node, func, data);
358 EXPORT_SYMBOL(rb_augment_erase_end);
361 * This function returns the first node (in sort order) of the tree.
363 struct rb_node *rb_first(const struct rb_root *root)
374 EXPORT_SYMBOL(rb_first);
376 struct rb_node *rb_last(const struct rb_root *root)
387 EXPORT_SYMBOL(rb_last);
389 struct rb_node *rb_next(const struct rb_node *node)
391 struct rb_node *parent;
393 if (rb_parent(node) == node)
396 /* If we have a right-hand child, go down and then left as far
398 if (node->rb_right) {
399 node = node->rb_right;
400 while (node->rb_left)
402 return (struct rb_node *)node;
405 /* No right-hand children. Everything down and left is
406 smaller than us, so any 'next' node must be in the general
407 direction of our parent. Go up the tree; any time the
408 ancestor is a right-hand child of its parent, keep going
409 up. First time it's a left-hand child of its parent, said
410 parent is our 'next' node. */
411 while ((parent = rb_parent(node)) && node == parent->rb_right)
416 EXPORT_SYMBOL(rb_next);
418 struct rb_node *rb_prev(const struct rb_node *node)
420 struct rb_node *parent;
422 if (rb_parent(node) == node)
425 /* If we have a left-hand child, go down and then right as far
428 node = node->rb_left;
429 while (node->rb_right)
431 return (struct rb_node *)node;
434 /* No left-hand children. Go up till we find an ancestor which
435 is a right-hand child of its parent */
436 while ((parent = rb_parent(node)) && node == parent->rb_left)
441 EXPORT_SYMBOL(rb_prev);
443 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
444 struct rb_root *root)
446 struct rb_node *parent = rb_parent(victim);
448 /* Set the surrounding nodes to point to the replacement */
450 if (victim == parent->rb_left)
451 parent->rb_left = new;
453 parent->rb_right = new;
458 rb_set_parent(victim->rb_left, new);
459 if (victim->rb_right)
460 rb_set_parent(victim->rb_right, new);
462 /* Copy the pointers/colour from the victim to the replacement */
465 EXPORT_SYMBOL(rb_replace_node);