rbtree.c (9d9e6f9703bbd642f3f2f807e6aaa642a4cbcec9) rbtree.c (9c079add0d0f45220f4bb37febf0621137ec2d38)
1/*
2 Red Black Trees
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
5 (C) 2012 Michel Lespinasse <walken@google.com>
6
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

--- 7 unchanged lines hidden (view full) ---

16
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
20
21 linux/lib/rbtree.c
22*/
23
1/*
2 Red Black Trees
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
5 (C) 2012 Michel Lespinasse <walken@google.com>
6
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

--- 7 unchanged lines hidden (view full) ---

16
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
20
21 linux/lib/rbtree.c
22*/
23
24#include <linux/rbtree.h>
24#include <linux/rbtree_augmented.h>
25#include <linux/export.h>
26
27/*
28 * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
29 *
30 * 1) A node is either red or black
31 * 2) The root is black
32 * 3) All leaves (NULL) are black

--- 6 unchanged lines hidden (view full) ---

39 * a black. So if B is the number of black nodes on every simple path (as per
40 * 5), then the longest possible path due to 4 is 2B.
41 *
42 * We shall indicate color with case, where black nodes are uppercase and red
43 * nodes will be lowercase. Unknown color nodes shall be drawn as red within
44 * parentheses and have some accompanying text comment.
45 */
46
25#include <linux/export.h>
26
27/*
28 * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
29 *
30 * 1) A node is either red or black
31 * 2) The root is black
32 * 3) All leaves (NULL) are black

--- 6 unchanged lines hidden (view full) ---

39 * a black. So if B is the number of black nodes on every simple path (as per
40 * 5), then the longest possible path due to 4 is 2B.
41 *
42 * We shall indicate color with case, where black nodes are uppercase and red
43 * nodes will be lowercase. Unknown color nodes shall be drawn as red within
44 * parentheses and have some accompanying text comment.
45 */
46
47#define RB_RED 0
48#define RB_BLACK 1
49
50#define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
51
52#define __rb_color(pc) ((pc) & 1)
53#define __rb_is_black(pc) __rb_color(pc)
54#define __rb_is_red(pc) (!__rb_color(pc))
55#define rb_color(rb) __rb_color((rb)->__rb_parent_color)
56#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
57#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
58
59static inline void rb_set_black(struct rb_node *rb)
60{
61 rb->__rb_parent_color |= RB_BLACK;
62}
63
47static inline void rb_set_black(struct rb_node *rb)
48{
49 rb->__rb_parent_color |= RB_BLACK;
50}
51
64static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
65{
66 rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
67}
68
69static inline void rb_set_parent_color(struct rb_node *rb,
70 struct rb_node *p, int color)
71{
72 rb->__rb_parent_color = (unsigned long)p | color;
73}
74
75static inline struct rb_node *rb_red_parent(struct rb_node *red)
76{
77 return (struct rb_node *)red->__rb_parent_color;
78}
79
52static inline struct rb_node *rb_red_parent(struct rb_node *red)
53{
54 return (struct rb_node *)red->__rb_parent_color;
55}
56
80static inline void
81__rb_change_child(struct rb_node *old, struct rb_node *new,
82 struct rb_node *parent, struct rb_root *root)
83{
84 if (parent) {
85 if (parent->rb_left == old)
86 parent->rb_left = new;
87 else
88 parent->rb_right = new;
89 } else
90 root->rb_node = new;
91}
92
93/*
94 * Helper function for rotations:
95 * - old's parent and color get assigned to new
96 * - old gets assigned new as a parent and 'color' as a color.
97 */
98static inline void
99__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
100 struct rb_root *root, int color)

--- 124 unchanged lines hidden (view full) ---

225 rb_set_parent_color(tmp, gparent, RB_BLACK);
226 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
227 augment_rotate(gparent, parent);
228 break;
229 }
230 }
231}
232
57/*
58 * Helper function for rotations:
59 * - old's parent and color get assigned to new
60 * - old gets assigned new as a parent and 'color' as a color.
61 */
62static inline void
63__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
64 struct rb_root *root, int color)

--- 124 unchanged lines hidden (view full) ---

189 rb_set_parent_color(tmp, gparent, RB_BLACK);
190 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
191 augment_rotate(gparent, parent);
192 break;
193 }
194 }
195}
196
233static __always_inline void
197__always_inline void
234__rb_erase_color(struct rb_node *parent, struct rb_root *root,
198__rb_erase_color(struct rb_node *parent, struct rb_root *root,
235 const struct rb_augment_callbacks *augment)
199 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
236{
237 struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
238
239 while (true) {
240 /*
241 * Loop invariants:
242 * - node is black (or NULL on first iteration)
243 * - node is not the root (parent is not NULL)

--- 12 unchanged lines hidden (view full) ---

256 * / \ / \
257 * Sl Sr N Sl
258 */
259 parent->rb_right = tmp1 = sibling->rb_left;
260 sibling->rb_left = parent;
261 rb_set_parent_color(tmp1, parent, RB_BLACK);
262 __rb_rotate_set_parents(parent, sibling, root,
263 RB_RED);
200{
201 struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
202
203 while (true) {
204 /*
205 * Loop invariants:
206 * - node is black (or NULL on first iteration)
207 * - node is not the root (parent is not NULL)

--- 12 unchanged lines hidden (view full) ---

220 * / \ / \
221 * Sl Sr N Sl
222 */
223 parent->rb_right = tmp1 = sibling->rb_left;
224 sibling->rb_left = parent;
225 rb_set_parent_color(tmp1, parent, RB_BLACK);
226 __rb_rotate_set_parents(parent, sibling, root,
227 RB_RED);
264 augment->rotate(parent, sibling);
228 augment_rotate(parent, sibling);
265 sibling = tmp1;
266 }
267 tmp1 = sibling->rb_right;
268 if (!tmp1 || rb_is_black(tmp1)) {
269 tmp2 = sibling->rb_left;
270 if (!tmp2 || rb_is_black(tmp2)) {
271 /*
272 * Case 2 - sibling color flip

--- 35 unchanged lines hidden (view full) ---

308 * Sr
309 */
310 sibling->rb_left = tmp1 = tmp2->rb_right;
311 tmp2->rb_right = sibling;
312 parent->rb_right = tmp2;
313 if (tmp1)
314 rb_set_parent_color(tmp1, sibling,
315 RB_BLACK);
229 sibling = tmp1;
230 }
231 tmp1 = sibling->rb_right;
232 if (!tmp1 || rb_is_black(tmp1)) {
233 tmp2 = sibling->rb_left;
234 if (!tmp2 || rb_is_black(tmp2)) {
235 /*
236 * Case 2 - sibling color flip

--- 35 unchanged lines hidden (view full) ---

272 * Sr
273 */
274 sibling->rb_left = tmp1 = tmp2->rb_right;
275 tmp2->rb_right = sibling;
276 parent->rb_right = tmp2;
277 if (tmp1)
278 rb_set_parent_color(tmp1, sibling,
279 RB_BLACK);
316 augment->rotate(sibling, tmp2);
280 augment_rotate(sibling, tmp2);
317 tmp1 = sibling;
318 sibling = tmp2;
319 }
320 /*
321 * Case 4 - left rotate at parent + color flips
322 * (p and sl could be either color here.
323 * After rotation, p becomes black, s acquires
324 * p's color, and sl keeps its color)

--- 6 unchanged lines hidden (view full) ---

331 */
332 parent->rb_right = tmp2 = sibling->rb_left;
333 sibling->rb_left = parent;
334 rb_set_parent_color(tmp1, sibling, RB_BLACK);
335 if (tmp2)
336 rb_set_parent(tmp2, parent);
337 __rb_rotate_set_parents(parent, sibling, root,
338 RB_BLACK);
281 tmp1 = sibling;
282 sibling = tmp2;
283 }
284 /*
285 * Case 4 - left rotate at parent + color flips
286 * (p and sl could be either color here.
287 * After rotation, p becomes black, s acquires
288 * p's color, and sl keeps its color)

--- 6 unchanged lines hidden (view full) ---

295 */
296 parent->rb_right = tmp2 = sibling->rb_left;
297 sibling->rb_left = parent;
298 rb_set_parent_color(tmp1, sibling, RB_BLACK);
299 if (tmp2)
300 rb_set_parent(tmp2, parent);
301 __rb_rotate_set_parents(parent, sibling, root,
302 RB_BLACK);
339 augment->rotate(parent, sibling);
303 augment_rotate(parent, sibling);
340 break;
341 } else {
342 sibling = parent->rb_left;
343 if (rb_is_red(sibling)) {
344 /* Case 1 - right rotate at parent */
345 parent->rb_left = tmp1 = sibling->rb_right;
346 sibling->rb_right = parent;
347 rb_set_parent_color(tmp1, parent, RB_BLACK);
348 __rb_rotate_set_parents(parent, sibling, root,
349 RB_RED);
304 break;
305 } else {
306 sibling = parent->rb_left;
307 if (rb_is_red(sibling)) {
308 /* Case 1 - right rotate at parent */
309 parent->rb_left = tmp1 = sibling->rb_right;
310 sibling->rb_right = parent;
311 rb_set_parent_color(tmp1, parent, RB_BLACK);
312 __rb_rotate_set_parents(parent, sibling, root,
313 RB_RED);
350 augment->rotate(parent, sibling);
314 augment_rotate(parent, sibling);
351 sibling = tmp1;
352 }
353 tmp1 = sibling->rb_left;
354 if (!tmp1 || rb_is_black(tmp1)) {
355 tmp2 = sibling->rb_right;
356 if (!tmp2 || rb_is_black(tmp2)) {
357 /* Case 2 - sibling color flip */
358 rb_set_parent_color(sibling, parent,

--- 10 unchanged lines hidden (view full) ---

369 }
370 /* Case 3 - right rotate at sibling */
371 sibling->rb_right = tmp1 = tmp2->rb_left;
372 tmp2->rb_left = sibling;
373 parent->rb_left = tmp2;
374 if (tmp1)
375 rb_set_parent_color(tmp1, sibling,
376 RB_BLACK);
315 sibling = tmp1;
316 }
317 tmp1 = sibling->rb_left;
318 if (!tmp1 || rb_is_black(tmp1)) {
319 tmp2 = sibling->rb_right;
320 if (!tmp2 || rb_is_black(tmp2)) {
321 /* Case 2 - sibling color flip */
322 rb_set_parent_color(sibling, parent,

--- 10 unchanged lines hidden (view full) ---

333 }
334 /* Case 3 - right rotate at sibling */
335 sibling->rb_right = tmp1 = tmp2->rb_left;
336 tmp2->rb_left = sibling;
337 parent->rb_left = tmp2;
338 if (tmp1)
339 rb_set_parent_color(tmp1, sibling,
340 RB_BLACK);
377 augment->rotate(sibling, tmp2);
341 augment_rotate(sibling, tmp2);
378 tmp1 = sibling;
379 sibling = tmp2;
380 }
381 /* Case 4 - left rotate at parent + color flips */
382 parent->rb_left = tmp2 = sibling->rb_right;
383 sibling->rb_right = parent;
384 rb_set_parent_color(tmp1, sibling, RB_BLACK);
385 if (tmp2)
386 rb_set_parent(tmp2, parent);
387 __rb_rotate_set_parents(parent, sibling, root,
388 RB_BLACK);
342 tmp1 = sibling;
343 sibling = tmp2;
344 }
345 /* Case 4 - left rotate at parent + color flips */
346 parent->rb_left = tmp2 = sibling->rb_right;
347 sibling->rb_right = parent;
348 rb_set_parent_color(tmp1, sibling, RB_BLACK);
349 if (tmp2)
350 rb_set_parent(tmp2, parent);
351 __rb_rotate_set_parents(parent, sibling, root,
352 RB_BLACK);
389 augment->rotate(parent, sibling);
353 augment_rotate(parent, sibling);
390 break;
391 }
392 }
393}
354 break;
355 }
356 }
357}
358EXPORT_SYMBOL(__rb_erase_color);
394
359
395static __always_inline void
396__rb_erase(struct rb_node *node, struct rb_root *root,
397 const struct rb_augment_callbacks *augment)
398{
399 struct rb_node *child = node->rb_right, *tmp = node->rb_left;
400 struct rb_node *parent, *rebalance;
401 unsigned long pc;
402
403 if (!tmp) {
404 /*
405 * Case 1: node to erase has no more than 1 child (easy!)
406 *
407 * Note that if there is one child it must be red due to 5)
408 * and node must be black due to 4). We adjust colors locally
409 * so as to bypass __rb_erase_color() later on.
410 */
411 pc = node->__rb_parent_color;
412 parent = __rb_parent(pc);
413 __rb_change_child(node, child, parent, root);
414 if (child) {
415 child->__rb_parent_color = pc;
416 rebalance = NULL;
417 } else
418 rebalance = __rb_is_black(pc) ? parent : NULL;
419 tmp = parent;
420 } else if (!child) {
421 /* Still case 1, but this time the child is node->rb_left */
422 tmp->__rb_parent_color = pc = node->__rb_parent_color;
423 parent = __rb_parent(pc);
424 __rb_change_child(node, tmp, parent, root);
425 rebalance = NULL;
426 tmp = parent;
427 } else {
428 struct rb_node *successor = child, *child2;
429 tmp = child->rb_left;
430 if (!tmp) {
431 /*
432 * Case 2: node's successor is its right child
433 *
434 * (n) (s)
435 * / \ / \
436 * (x) (s) -> (x) (c)
437 * \
438 * (c)
439 */
440 parent = successor;
441 child2 = successor->rb_right;
442 augment->copy(node, successor);
443 } else {
444 /*
445 * Case 3: node's successor is leftmost under
446 * node's right child subtree
447 *
448 * (n) (s)
449 * / \ / \
450 * (x) (y) -> (x) (y)
451 * / /
452 * (p) (p)
453 * / /
454 * (s) (c)
455 * \
456 * (c)
457 */
458 do {
459 parent = successor;
460 successor = tmp;
461 tmp = tmp->rb_left;
462 } while (tmp);
463 parent->rb_left = child2 = successor->rb_right;
464 successor->rb_right = child;
465 rb_set_parent(child, successor);
466 augment->copy(node, successor);
467 augment->propagate(parent, successor);
468 }
469
470 successor->rb_left = tmp = node->rb_left;
471 rb_set_parent(tmp, successor);
472
473 pc = node->__rb_parent_color;
474 tmp = __rb_parent(pc);
475 __rb_change_child(node, successor, tmp, root);
476 if (child2) {
477 successor->__rb_parent_color = pc;
478 rb_set_parent_color(child2, parent, RB_BLACK);
479 rebalance = NULL;
480 } else {
481 unsigned long pc2 = successor->__rb_parent_color;
482 successor->__rb_parent_color = pc;
483 rebalance = __rb_is_black(pc2) ? parent : NULL;
484 }
485 tmp = successor;
486 }
487
488 augment->propagate(tmp, NULL);
489 if (rebalance)
490 __rb_erase_color(rebalance, root, augment);
491}
492
493/*
494 * Non-augmented rbtree manipulation functions.
495 *
496 * We use dummy augmented callbacks here, and have the compiler optimize them
497 * out of the rb_insert_color() and rb_erase() function definitions.
498 */
499
500static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}

--- 7 unchanged lines hidden (view full) ---

508void rb_insert_color(struct rb_node *node, struct rb_root *root)
509{
510 __rb_insert(node, root, dummy_rotate);
511}
512EXPORT_SYMBOL(rb_insert_color);
513
514void rb_erase(struct rb_node *node, struct rb_root *root)
515{
360/*
361 * Non-augmented rbtree manipulation functions.
362 *
363 * We use dummy augmented callbacks here, and have the compiler optimize them
364 * out of the rb_insert_color() and rb_erase() function definitions.
365 */
366
367static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}

--- 7 unchanged lines hidden (view full) ---

375void rb_insert_color(struct rb_node *node, struct rb_root *root)
376{
377 __rb_insert(node, root, dummy_rotate);
378}
379EXPORT_SYMBOL(rb_insert_color);
380
381void rb_erase(struct rb_node *node, struct rb_root *root)
382{
516 __rb_erase(node, root, &dummy_callbacks);
383 rb_erase_augmented(node, root, &dummy_callbacks);
517}
518EXPORT_SYMBOL(rb_erase);
519
520/*
521 * Augmented rbtree manipulation functions.
522 *
523 * This instantiates the same __always_inline functions as in the non-augmented
524 * case, but this time with user-defined callbacks.
525 */
526
527void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
528 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
529{
530 __rb_insert(node, root, augment_rotate);
531}
532EXPORT_SYMBOL(__rb_insert_augmented);
533
384}
385EXPORT_SYMBOL(rb_erase);
386
387/*
388 * Augmented rbtree manipulation functions.
389 *
390 * This instantiates the same __always_inline functions as in the non-augmented
391 * case, but this time with user-defined callbacks.
392 */
393
394void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
395 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
396{
397 __rb_insert(node, root, augment_rotate);
398}
399EXPORT_SYMBOL(__rb_insert_augmented);
400
534void rb_erase_augmented(struct rb_node *node, struct rb_root *root,
535 const struct rb_augment_callbacks *augment)
536{
537 __rb_erase(node, root, augment);
538}
539EXPORT_SYMBOL(rb_erase_augmented);
540
541/*
542 * This function returns the first node (in sort order) of the tree.
543 */
544struct rb_node *rb_first(const struct rb_root *root)
545{
546 struct rb_node *n;
547
548 n = root->rb_node;

--- 98 unchanged lines hidden --- 		401/*
402 * This function returns the first node (in sort order) of the tree.
403 */
404struct rb_node *rb_first(const struct rb_root *root)
405{
406 struct rb_node *n;
407
408 n = root->rb_node;

--- 98 unchanged lines hidden ---