3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
5 (C) 2012 Michel Lespinasse <walken@google.com>
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
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.
46 struct rb_augment_callbacks {
47 void (*propagate)(struct rb_node *node, struct rb_node *stop);
48 void (*copy)(struct rb_node *old, struct rb_node *new);
49 void (*rotate)(struct rb_node *old, struct rb_node *new);
55 #define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
57 #define __rb_color(pc) ((pc) & 1)
58 #define __rb_is_black(pc) __rb_color(pc)
59 #define __rb_is_red(pc) (!__rb_color(pc))
60 #define rb_color(rb) __rb_color((rb)->__rb_parent_color)
61 #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
62 #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
64 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
66 rb->__rb_parent_color = rb_color(rb) | (uintptr_t)p;
69 static inline void rb_set_parent_color(struct rb_node *rb,
70 struct rb_node *p, int color)
72 rb->__rb_parent_color = (uintptr_t)p | color;
75 static inline void rb_set_black(struct rb_node *rb)
77 rb->__rb_parent_color |= RB_BLACK;
80 static inline struct rb_node *rb_red_parent(struct rb_node *red)
82 return (struct rb_node *)red->__rb_parent_color;
86 __rb_change_child(struct rb_node *old, struct rb_node *new,
87 struct rb_node *parent, struct rb_root *root)
90 if (parent->rb_left == old)
91 parent->rb_left = new;
93 parent->rb_right = new;
99 * Helper function for rotations:
100 * - old's parent and color get assigned to new
101 * - old gets assigned new as a parent and 'color' as a color.
104 __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
105 struct rb_root *root, int color)
107 struct rb_node *parent = rb_parent(old);
108 new->__rb_parent_color = old->__rb_parent_color;
109 rb_set_parent_color(old, new, color);
110 __rb_change_child(old, new, parent, root);
114 __rb_erase_color(struct rb_node *parent, struct rb_root *root,
115 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
117 struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
122 * - node is black (or NULL on first iteration)
123 * - node is not the root (parent is not NULL)
124 * - All leaf paths going through parent and node have a
125 * black node count that is 1 lower than other leaf paths.
127 sibling = parent->rb_right;
128 if (node != sibling) { /* node == parent->rb_left */
129 if (rb_is_red(sibling)) {
131 * Case 1 - left rotate at parent
139 parent->rb_right = tmp1 = sibling->rb_left;
140 sibling->rb_left = parent;
141 rb_set_parent_color(tmp1, parent, RB_BLACK);
142 __rb_rotate_set_parents(parent, sibling, root,
144 augment_rotate(parent, sibling);
147 tmp1 = sibling->rb_right;
148 if (!tmp1 || rb_is_black(tmp1)) {
149 tmp2 = sibling->rb_left;
150 if (!tmp2 || rb_is_black(tmp2)) {
152 * Case 2 - sibling color flip
153 * (p could be either color here)
161 * This leaves us violating 5) which
162 * can be fixed by flipping p to black
163 * if it was red, or by recursing at p.
164 * p is red when coming from Case 1.
166 rb_set_parent_color(sibling, parent,
168 if (rb_is_red(parent))
169 rb_set_black(parent);
172 parent = rb_parent(node);
179 * Case 3 - right rotate at sibling
180 * (p could be either color here)
190 sibling->rb_left = tmp1 = tmp2->rb_right;
191 tmp2->rb_right = sibling;
192 parent->rb_right = tmp2;
194 rb_set_parent_color(tmp1, sibling,
196 augment_rotate(sibling, tmp2);
201 * Case 4 - left rotate at parent + color flips
202 * (p and sl could be either color here.
203 * After rotation, p becomes black, s acquires
204 * p's color, and sl keeps its color)
212 parent->rb_right = tmp2 = sibling->rb_left;
213 sibling->rb_left = parent;
214 rb_set_parent_color(tmp1, sibling, RB_BLACK);
216 rb_set_parent(tmp2, parent);
217 __rb_rotate_set_parents(parent, sibling, root,
219 augment_rotate(parent, sibling);
222 sibling = parent->rb_left;
223 if (rb_is_red(sibling)) {
224 /* Case 1 - right rotate at parent */
225 parent->rb_left = tmp1 = sibling->rb_right;
226 sibling->rb_right = parent;
227 rb_set_parent_color(tmp1, parent, RB_BLACK);
228 __rb_rotate_set_parents(parent, sibling, root,
230 augment_rotate(parent, sibling);
233 tmp1 = sibling->rb_left;
234 if (!tmp1 || rb_is_black(tmp1)) {
235 tmp2 = sibling->rb_right;
236 if (!tmp2 || rb_is_black(tmp2)) {
237 /* Case 2 - sibling color flip */
238 rb_set_parent_color(sibling, parent,
240 if (rb_is_red(parent))
241 rb_set_black(parent);
244 parent = rb_parent(node);
250 /* Case 3 - right rotate at sibling */
251 sibling->rb_right = tmp1 = tmp2->rb_left;
252 tmp2->rb_left = sibling;
253 parent->rb_left = tmp2;
255 rb_set_parent_color(tmp1, sibling,
257 augment_rotate(sibling, tmp2);
261 /* Case 4 - left rotate at parent + color flips */
262 parent->rb_left = tmp2 = sibling->rb_right;
263 sibling->rb_right = parent;
264 rb_set_parent_color(tmp1, sibling, RB_BLACK);
266 rb_set_parent(tmp2, parent);
267 __rb_rotate_set_parents(parent, sibling, root,
269 augment_rotate(parent, sibling);
276 rb_erase_augmented(struct rb_node *node, struct rb_root *root,
277 const struct rb_augment_callbacks *augment)
279 struct rb_node *child = node->rb_right, *tmp = node->rb_left;
280 struct rb_node *parent, *rebalance;
285 * Case 1: node to erase has no more than 1 child (easy!)
287 * Note that if there is one child it must be red due to 5)
288 * and node must be black due to 4). We adjust colors locally
289 * so as to bypass __rb_erase_color() later on.
291 pc = node->__rb_parent_color;
292 parent = __rb_parent(pc);
293 __rb_change_child(node, child, parent, root);
295 child->__rb_parent_color = pc;
298 rebalance = __rb_is_black(pc) ? parent : NULL;
301 /* Still case 1, but this time the child is node->rb_left */
302 tmp->__rb_parent_color = pc = node->__rb_parent_color;
303 parent = __rb_parent(pc);
304 __rb_change_child(node, tmp, parent, root);
308 struct rb_node *successor = child, *child2;
309 tmp = child->rb_left;
312 * Case 2: node's successor is its right child
321 child2 = successor->rb_right;
322 augment->copy(node, successor);
325 * Case 3: node's successor is leftmost under
326 * node's right child subtree
343 parent->rb_left = child2 = successor->rb_right;
344 successor->rb_right = child;
345 rb_set_parent(child, successor);
346 augment->copy(node, successor);
347 augment->propagate(parent, successor);
350 successor->rb_left = tmp = node->rb_left;
351 rb_set_parent(tmp, successor);
353 pc = node->__rb_parent_color;
354 tmp = __rb_parent(pc);
355 __rb_change_child(node, successor, tmp, root);
357 successor->__rb_parent_color = pc;
358 rb_set_parent_color(child2, parent, RB_BLACK);
361 uintptr_t pc2 = successor->__rb_parent_color;
362 successor->__rb_parent_color = pc;
363 rebalance = __rb_is_black(pc2) ? parent : NULL;
368 augment->propagate(tmp, NULL);
370 __rb_erase_color(rebalance, root, augment->rotate);
375 __rb_insert(struct rb_node *node, struct rb_root *root,
376 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
378 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
382 * Loop invariant: node is red
384 * If there is a black parent, we are done.
385 * Otherwise, take some corrective action as we don't
386 * want a red root or two consecutive red nodes.
389 rb_set_parent_color(node, NULL, RB_BLACK);
391 } else if (rb_is_black(parent))
394 gparent = rb_red_parent(parent);
396 tmp = gparent->rb_right;
397 if (parent != tmp) { /* parent == gparent->rb_left */
398 if (tmp && rb_is_red(tmp)) {
400 * Case 1 - color flips
408 * However, since g's parent might be red, and
409 * 4) does not allow this, we need to recurse
412 rb_set_parent_color(tmp, gparent, RB_BLACK);
413 rb_set_parent_color(parent, gparent, RB_BLACK);
415 parent = rb_parent(node);
416 rb_set_parent_color(node, parent, RB_RED);
420 tmp = parent->rb_right;
423 * Case 2 - left rotate at parent
431 * This still leaves us in violation of 4), the
432 * continuation into Case 3 will fix that.
434 parent->rb_right = tmp = node->rb_left;
435 node->rb_left = parent;
437 rb_set_parent_color(tmp, parent,
439 rb_set_parent_color(parent, node, RB_RED);
440 augment_rotate(parent, node);
442 tmp = node->rb_right;
446 * Case 3 - right rotate at gparent
454 gparent->rb_left = tmp; /* == parent->rb_right */
455 parent->rb_right = gparent;
457 rb_set_parent_color(tmp, gparent, RB_BLACK);
458 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
459 augment_rotate(gparent, parent);
462 tmp = gparent->rb_left;
463 if (tmp && rb_is_red(tmp)) {
464 /* Case 1 - color flips */
465 rb_set_parent_color(tmp, gparent, RB_BLACK);
466 rb_set_parent_color(parent, gparent, RB_BLACK);
468 parent = rb_parent(node);
469 rb_set_parent_color(node, parent, RB_RED);
473 tmp = parent->rb_left;
475 /* Case 2 - right rotate at parent */
476 parent->rb_left = tmp = node->rb_right;
477 node->rb_right = parent;
479 rb_set_parent_color(tmp, parent,
481 rb_set_parent_color(parent, node, RB_RED);
482 augment_rotate(parent, node);
487 /* Case 3 - left rotate at gparent */
488 gparent->rb_right = tmp; /* == parent->rb_left */
489 parent->rb_left = gparent;
491 rb_set_parent_color(tmp, gparent, RB_BLACK);
492 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
493 augment_rotate(gparent, parent);
501 * Non-augmented rbtree manipulation functions.
503 * We use dummy augmented callbacks here, and have the compiler optimize them
504 * out of the rb_insert_color() and rb_erase() function definitions.
507 static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
508 static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
509 static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
511 static const struct rb_augment_callbacks dummy_callbacks = {
512 dummy_propagate, dummy_copy, dummy_rotate
515 void rb_insert_color(struct rb_node *node, struct rb_root *root)
517 __rb_insert(node, root, dummy_rotate);
520 void rb_erase(struct rb_node *node, struct rb_root *root)
522 rb_erase_augmented(node, root, &dummy_callbacks);