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>
27 * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
29 * 1) A node is either red or black
30 * 2) The root is black
31 * 3) All leaves (NULL) are black
32 * 4) Both children of every red node are black
33 * 5) Every simple path from root to leaves contains the same number
36 * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
37 * consecutive red nodes in a path and every red node is therefore followed by
38 * a black. So if B is the number of black nodes on every simple path (as per
39 * 5), then the longest possible path due to 4 is 2B.
41 * We shall indicate color with case, where black nodes are uppercase and red
42 * nodes will be lowercase. Unknown color nodes shall be drawn as red within
43 * parentheses and have some accompanying text comment.
49 #define rb_color(r) ((r)->__rb_parent_color & 1)
50 #define rb_is_red(r) (!rb_color(r))
51 #define rb_is_black(r) rb_color(r)
53 static inline void rb_set_parent(struct rb_node
*rb
, struct rb_node
*p
)
55 rb
->__rb_parent_color
= rb_color(rb
) | (unsigned long)p
;
58 static inline void rb_set_parent_color(struct rb_node
*rb
,
59 struct rb_node
*p
, int color
)
61 rb
->__rb_parent_color
= (unsigned long)p
| color
;
64 static inline struct rb_node
*rb_red_parent(struct rb_node
*red
)
66 return (struct rb_node
*)red
->__rb_parent_color
;
70 * Helper function for rotations:
71 * - old's parent and color get assigned to new
72 * - old gets assigned new as a parent and 'color' as a color.
75 __rb_rotate_set_parents(struct rb_node
*old
, struct rb_node
*new,
76 struct rb_root
*root
, int color
)
78 struct rb_node
*parent
= rb_parent(old
);
79 new->__rb_parent_color
= old
->__rb_parent_color
;
80 rb_set_parent_color(old
, new, color
);
82 if (parent
->rb_left
== old
)
83 parent
->rb_left
= new;
85 parent
->rb_right
= new;
90 void rb_insert_color(struct rb_node
*node
, struct rb_root
*root
)
92 struct rb_node
*parent
= rb_red_parent(node
), *gparent
, *tmp
;
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.
103 rb_set_parent_color(node
, NULL
, RB_BLACK
);
105 } else if (rb_is_black(parent
))
108 gparent
= rb_red_parent(parent
);
110 tmp
= gparent
->rb_right
;
111 if (parent
!= tmp
) { /* parent == gparent->rb_left */
112 if (tmp
&& rb_is_red(tmp
)) {
114 * Case 1 - color flips
122 * However, since g's parent might be red, and
123 * 4) does not allow this, we need to recurse
126 rb_set_parent_color(tmp
, gparent
, RB_BLACK
);
127 rb_set_parent_color(parent
, gparent
, RB_BLACK
);
129 parent
= rb_parent(node
);
130 rb_set_parent_color(node
, parent
, RB_RED
);
134 tmp
= parent
->rb_right
;
137 * Case 2 - left rotate at parent
145 * This still leaves us in violation of 4), the
146 * continuation into Case 3 will fix that.
148 parent
->rb_right
= tmp
= node
->rb_left
;
149 node
->rb_left
= parent
;
151 rb_set_parent_color(tmp
, parent
,
153 rb_set_parent_color(parent
, node
, RB_RED
);
155 tmp
= node
->rb_right
;
159 * Case 3 - right rotate at gparent
167 gparent
->rb_left
= tmp
; /* == parent->rb_right */
168 parent
->rb_right
= gparent
;
170 rb_set_parent_color(tmp
, gparent
, RB_BLACK
);
171 __rb_rotate_set_parents(gparent
, parent
, root
, RB_RED
);
174 tmp
= gparent
->rb_left
;
175 if (tmp
&& rb_is_red(tmp
)) {
176 /* Case 1 - color flips */
177 rb_set_parent_color(tmp
, gparent
, RB_BLACK
);
178 rb_set_parent_color(parent
, gparent
, RB_BLACK
);
180 parent
= rb_parent(node
);
181 rb_set_parent_color(node
, parent
, RB_RED
);
185 tmp
= parent
->rb_left
;
187 /* Case 2 - right rotate at parent */
188 parent
->rb_left
= tmp
= node
->rb_right
;
189 node
->rb_right
= parent
;
191 rb_set_parent_color(tmp
, parent
,
193 rb_set_parent_color(parent
, node
, RB_RED
);
198 /* Case 3 - left rotate at gparent */
199 gparent
->rb_right
= tmp
; /* == parent->rb_left */
200 parent
->rb_left
= gparent
;
202 rb_set_parent_color(tmp
, gparent
, RB_BLACK
);
203 __rb_rotate_set_parents(gparent
, parent
, root
, RB_RED
);
208 EXPORT_SYMBOL(rb_insert_color
);
210 static void __rb_erase_color(struct rb_node
*node
, struct rb_node
*parent
,
211 struct rb_root
*root
)
213 struct rb_node
*sibling
, *tmp1
, *tmp2
;
217 * Loop invariant: all leaf paths going through node have a
218 * black node count that is 1 lower than other leaf paths.
220 * If node is red, we can flip it to black to adjust.
221 * If node is the root, all leaf paths go through it.
222 * Otherwise, we need to adjust the tree through color flips
223 * and tree rotations as per one of the 4 cases below.
225 if (node
&& rb_is_red(node
)) {
226 rb_set_parent_color(node
, parent
, RB_BLACK
);
228 } else if (!parent
) {
231 sibling
= parent
->rb_right
;
232 if (node
!= sibling
) { /* node == parent->rb_left */
233 if (rb_is_red(sibling
)) {
235 * Case 1 - left rotate at parent
243 parent
->rb_right
= tmp1
= sibling
->rb_left
;
244 sibling
->rb_left
= parent
;
245 rb_set_parent_color(tmp1
, parent
, RB_BLACK
);
246 __rb_rotate_set_parents(parent
, sibling
, root
,
250 tmp1
= sibling
->rb_right
;
251 if (!tmp1
|| rb_is_black(tmp1
)) {
252 tmp2
= sibling
->rb_left
;
253 if (!tmp2
|| rb_is_black(tmp2
)) {
255 * Case 2 - sibling color flip
256 * (p could be either color here)
264 * This leaves us violating 5), so
265 * recurse at p. If p is red, the
266 * recursion will just flip it to black
267 * and exit. If coming from Case 1,
268 * p is known to be red.
270 rb_set_parent_color(sibling
, parent
,
273 parent
= rb_parent(node
);
277 * Case 3 - right rotate at sibling
278 * (p could be either color here)
288 sibling
->rb_left
= tmp1
= tmp2
->rb_right
;
289 tmp2
->rb_right
= sibling
;
290 parent
->rb_right
= tmp2
;
292 rb_set_parent_color(tmp1
, sibling
,
298 * Case 4 - left rotate at parent + color flips
299 * (p and sl could be either color here.
300 * After rotation, p becomes black, s acquires
301 * p's color, and sl keeps its color)
309 parent
->rb_right
= tmp2
= sibling
->rb_left
;
310 sibling
->rb_left
= parent
;
311 rb_set_parent_color(tmp1
, sibling
, RB_BLACK
);
313 rb_set_parent(tmp2
, parent
);
314 __rb_rotate_set_parents(parent
, sibling
, root
,
318 sibling
= parent
->rb_left
;
319 if (rb_is_red(sibling
)) {
320 /* Case 1 - right rotate at parent */
321 parent
->rb_left
= tmp1
= sibling
->rb_right
;
322 sibling
->rb_right
= parent
;
323 rb_set_parent_color(tmp1
, parent
, RB_BLACK
);
324 __rb_rotate_set_parents(parent
, sibling
, root
,
328 tmp1
= sibling
->rb_left
;
329 if (!tmp1
|| rb_is_black(tmp1
)) {
330 tmp2
= sibling
->rb_right
;
331 if (!tmp2
|| rb_is_black(tmp2
)) {
332 /* Case 2 - sibling color flip */
333 rb_set_parent_color(sibling
, parent
,
336 parent
= rb_parent(node
);
339 /* Case 3 - right rotate at sibling */
340 sibling
->rb_right
= tmp1
= tmp2
->rb_left
;
341 tmp2
->rb_left
= sibling
;
342 parent
->rb_left
= tmp2
;
344 rb_set_parent_color(tmp1
, sibling
,
349 /* Case 4 - left rotate at parent + color flips */
350 parent
->rb_left
= tmp2
= sibling
->rb_right
;
351 sibling
->rb_right
= parent
;
352 rb_set_parent_color(tmp1
, sibling
, RB_BLACK
);
354 rb_set_parent(tmp2
, parent
);
355 __rb_rotate_set_parents(parent
, sibling
, root
,
362 void rb_erase(struct rb_node
*node
, struct rb_root
*root
)
364 struct rb_node
*child
, *parent
;
368 child
= node
->rb_right
;
369 else if (!node
->rb_right
)
370 child
= node
->rb_left
;
372 struct rb_node
*old
= node
, *left
;
374 node
= node
->rb_right
;
375 while ((left
= node
->rb_left
) != NULL
)
378 if (rb_parent(old
)) {
379 if (rb_parent(old
)->rb_left
== old
)
380 rb_parent(old
)->rb_left
= node
;
382 rb_parent(old
)->rb_right
= node
;
384 root
->rb_node
= node
;
386 child
= node
->rb_right
;
387 parent
= rb_parent(node
);
388 color
= rb_color(node
);
394 rb_set_parent(child
, parent
);
395 parent
->rb_left
= child
;
397 node
->rb_right
= old
->rb_right
;
398 rb_set_parent(old
->rb_right
, node
);
401 node
->__rb_parent_color
= old
->__rb_parent_color
;
402 node
->rb_left
= old
->rb_left
;
403 rb_set_parent(old
->rb_left
, node
);
408 parent
= rb_parent(node
);
409 color
= rb_color(node
);
412 rb_set_parent(child
, parent
);
414 if (parent
->rb_left
== node
)
415 parent
->rb_left
= child
;
417 parent
->rb_right
= child
;
419 root
->rb_node
= child
;
422 if (color
== RB_BLACK
)
423 __rb_erase_color(child
, parent
, root
);
425 EXPORT_SYMBOL(rb_erase
);
427 static void rb_augment_path(struct rb_node
*node
, rb_augment_f func
, void *data
)
429 struct rb_node
*parent
;
433 parent
= rb_parent(node
);
437 if (node
== parent
->rb_left
&& parent
->rb_right
)
438 func(parent
->rb_right
, data
);
439 else if (parent
->rb_left
)
440 func(parent
->rb_left
, data
);
447 * after inserting @node into the tree, update the tree to account for
448 * both the new entry and any damage done by rebalance
450 void rb_augment_insert(struct rb_node
*node
, rb_augment_f func
, void *data
)
453 node
= node
->rb_left
;
454 else if (node
->rb_right
)
455 node
= node
->rb_right
;
457 rb_augment_path(node
, func
, data
);
459 EXPORT_SYMBOL(rb_augment_insert
);
462 * before removing the node, find the deepest node on the rebalance path
463 * that will still be there after @node gets removed
465 struct rb_node
*rb_augment_erase_begin(struct rb_node
*node
)
467 struct rb_node
*deepest
;
469 if (!node
->rb_right
&& !node
->rb_left
)
470 deepest
= rb_parent(node
);
471 else if (!node
->rb_right
)
472 deepest
= node
->rb_left
;
473 else if (!node
->rb_left
)
474 deepest
= node
->rb_right
;
476 deepest
= rb_next(node
);
477 if (deepest
->rb_right
)
478 deepest
= deepest
->rb_right
;
479 else if (rb_parent(deepest
) != node
)
480 deepest
= rb_parent(deepest
);
485 EXPORT_SYMBOL(rb_augment_erase_begin
);
488 * after removal, update the tree to account for the removed entry
489 * and any rebalance damage.
491 void rb_augment_erase_end(struct rb_node
*node
, rb_augment_f func
, void *data
)
494 rb_augment_path(node
, func
, data
);
496 EXPORT_SYMBOL(rb_augment_erase_end
);
499 * This function returns the first node (in sort order) of the tree.
501 struct rb_node
*rb_first(const struct rb_root
*root
)
512 EXPORT_SYMBOL(rb_first
);
514 struct rb_node
*rb_last(const struct rb_root
*root
)
525 EXPORT_SYMBOL(rb_last
);
527 struct rb_node
*rb_next(const struct rb_node
*node
)
529 struct rb_node
*parent
;
531 if (RB_EMPTY_NODE(node
))
535 * If we have a right-hand child, go down and then left as far
538 if (node
->rb_right
) {
539 node
= node
->rb_right
;
540 while (node
->rb_left
)
542 return (struct rb_node
*)node
;
546 * No right-hand children. Everything down and left is smaller than us,
547 * so any 'next' node must be in the general direction of our parent.
548 * Go up the tree; any time the ancestor is a right-hand child of its
549 * parent, keep going up. First time it's a left-hand child of its
550 * parent, said parent is our 'next' node.
552 while ((parent
= rb_parent(node
)) && node
== parent
->rb_right
)
557 EXPORT_SYMBOL(rb_next
);
559 struct rb_node
*rb_prev(const struct rb_node
*node
)
561 struct rb_node
*parent
;
563 if (RB_EMPTY_NODE(node
))
567 * If we have a left-hand child, go down and then right as far
571 node
= node
->rb_left
;
572 while (node
->rb_right
)
574 return (struct rb_node
*)node
;
578 * No left-hand children. Go up till we find an ancestor which
579 * is a right-hand child of its parent.
581 while ((parent
= rb_parent(node
)) && node
== parent
->rb_left
)
586 EXPORT_SYMBOL(rb_prev
);
588 void rb_replace_node(struct rb_node
*victim
, struct rb_node
*new,
589 struct rb_root
*root
)
591 struct rb_node
*parent
= rb_parent(victim
);
593 /* Set the surrounding nodes to point to the replacement */
595 if (victim
== parent
->rb_left
)
596 parent
->rb_left
= new;
598 parent
->rb_right
= new;
603 rb_set_parent(victim
->rb_left
, new);
604 if (victim
->rb_right
)
605 rb_set_parent(victim
->rb_right
, new);
607 /* Copy the pointers/colour from the victim to the replacement */
610 EXPORT_SYMBOL(rb_replace_node
);