rbtree.c (bf61c8840efe60fd8f91446860b63338fb424158) rbtree.c (9dee5c51516d2c3fff22633c1272c5652e68075a)
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

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

513 rb_set_parent(victim->rb_left, new);
514 if (victim->rb_right)
515 rb_set_parent(victim->rb_right, new);
516
517 /* Copy the pointers/colour from the victim to the replacement */
518 *new = *victim;
519}
520EXPORT_SYMBOL(rb_replace_node);
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

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

513 rb_set_parent(victim->rb_left, new);
514 if (victim->rb_right)
515 rb_set_parent(victim->rb_right, new);
516
517 /* Copy the pointers/colour from the victim to the replacement */
518 *new = *victim;
519}
520EXPORT_SYMBOL(rb_replace_node);
521
522static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
523{
524 for (;;) {
525 if (node->rb_left)
526 node = node->rb_left;
527 else if (node->rb_right)
528 node = node->rb_right;
529 else
530 return (struct rb_node *)node;
531 }
532}
533
534struct rb_node *rb_next_postorder(const struct rb_node *node)
535{
536 const struct rb_node *parent;
537 if (!node)
538 return NULL;
539 parent = rb_parent(node);
540
541 /* If we're sitting on node, we've already seen our children */
542 if (parent && node == parent->rb_left && parent->rb_right) {
543 /* If we are the parent's left node, go to the parent's right
544 * node then all the way down to the left */
545 return rb_left_deepest_node(parent->rb_right);
546 } else
547 /* Otherwise we are the parent's right node, and the parent
548 * should be next */
549 return (struct rb_node *)parent;
550}
551EXPORT_SYMBOL(rb_next_postorder);
552
553struct rb_node *rb_first_postorder(const struct rb_root *root)
554{
555 if (!root->rb_node)
556 return NULL;
557
558 return rb_left_deepest_node(root->rb_node);
559}
560EXPORT_SYMBOL(rb_first_postorder);