summaryrefslogtreecommitdiff
path: root/lib/fdt_rw.c
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 16:31:11 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 16:22:37 +0900
commit46b6135a7402ac23c5b25f2bd79b03bab8f98278 (patch)
tree8430c191a455b1ff48c62229731ded4cbc71a9a1 /lib/fdt_rw.c
parent60670b8034d6e2ba860af79c9379b7788d09db73 (diff)
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>
Diffstat (limited to 'lib/fdt_rw.c')
0 files changed, 0 insertions, 0 deletions