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/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);
39 if (node == parent->rb_left)
40 parent->rb_left = right;
42 parent->rb_right = right;
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);
67 if (node == parent->rb_right)
68 parent->rb_right = left;
70 parent->rb_left = 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;
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))
100 rb_set_black(parent);
107 if (parent->rb_right == node)
109 register struct rb_node *tmp;
110 __rb_rotate_left(parent, root);
116 rb_set_black(parent);
118 __rb_rotate_right(gparent, root);
121 register struct rb_node *uncle = gparent->rb_left;
122 if (uncle && rb_is_red(uncle))
125 rb_set_black(parent);
132 if (parent->rb_left == node)
134 register struct rb_node *tmp;
135 __rb_rotate_right(parent, root);
141 rb_set_black(parent);
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))
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)))
173 parent = rb_parent(node);
177 if (!other->rb_right || rb_is_black(other->rb_right))
179 rb_set_black(other->rb_left);
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;
194 other = parent->rb_left;
195 if (rb_is_red(other))
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)))
207 parent = rb_parent(node);
211 if (!other->rb_left || rb_is_black(other->rb_left))
213 rb_set_black(other->rb_right);
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;
231 void rb_erase(struct rb_node *node, struct rb_root *root)
233 struct rb_node *child, *parent;
237 child = node->rb_right;
238 else if (!node->rb_right)
239 child = node->rb_left;
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)
250 if (rb_parent(old)) {
252 if (rb_parent(old)->rb_left == old)
253 rb_parent(old)->rb_left = node;
255 rb_parent(old)->rb_right = node;
257 root->rb_node = node;
259 child = node->rb_right;
260 parent = rb_parent(node);
261 color = rb_color(node);
266 successor_parent_cb = 1;
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
287 * The parent of the node getting erased-replaced.
289 if (successor_parent_cb)
290 root->augment_cb(parent);
292 root->augment_cb(node);
295 root->augment_cb(rb_parent(old));
301 parent = rb_parent(node);
302 color = rb_color(node);
305 rb_set_parent(child, parent);
308 if (parent->rb_left == node)
309 parent->rb_left = child;
311 parent->rb_right = child;
313 if (root->augment_cb)
314 root->augment_cb(parent);
317 root->rb_node = child;
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)
340 EXPORT_SYMBOL(rb_first);
342 struct rb_node *rb_last(const struct rb_root *root)
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)
362 /* If we have a right-hand child, go down and then left as far
364 if (node->rb_right) {
365 node = node->rb_right;
366 while (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)
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)
391 /* If we have a left-hand child, go down and then right as far
394 node = node->rb_left;
395 while (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)
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 */
416 if (victim == parent->rb_left)
417 parent->rb_left = new;
419 parent->rb_right = new;
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 */
431 EXPORT_SYMBOL(rb_replace_node);