Searched hist:"46 b6135a7402ac23c5b25f2bd79b03bab8f98278" (Results 1 – 1 of 1) sorted by relevance
| /openbmc/linux/lib/ |
| H A D | rbtree.c | diff 46b6135a7402ac23c5b25f2bd79b03bab8f98278 Mon Oct 08 18:31:11 CDT 2012 Michel Lespinasse <walken@google.com> rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()
An interesting observation for rb_erase() is that when a node has
exactly one child, the node must be black and the child must be red.
An interesting consequence is that removing such a node can be done by
simply replacing it with its child and making the child black,
which we can do efficiently in rb_erase(). __rb_erase_color() then
only needs to handle the no-childs case and can be modified accordingly.
Signed-off-by: Michel Lespinasse <walken@google.com>
Acked-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
|