]> git.karo-electronics.de Git - karo-tx-linux.git/commit
rbtree: optimize case selection logic in __rb_erase_color()
authorMichel Lespinasse <walken@google.com>
Fri, 28 Sep 2012 00:19:27 +0000 (10:19 +1000)
committerStephen Rothwell <sfr@canb.auug.org.au>
Fri, 28 Sep 2012 06:07:39 +0000 (16:07 +1000)
commitb4c0fe9dd401b865cf1417e814141531ee012f47
tree6558c555059b5ac905ece5a899e1cb5a27307bd9
parent5ff39f5474f03b7a807c61f8151b97071f94e61d
rbtree: optimize case selection logic in __rb_erase_color()

In __rb_erase_color(), we have to select one of 3 cases depending on the
color on the 'other' node children.  If both children are black, we flip a
few node colors and iterate.  Otherwise, we do either one or two tree
rotations, depending on the color of the 'other' child opposite to 'node',
and then we are done.

The corresponding logic had duplicate checks for the color of the 'other'
child opposite to 'node'.  It was checking it first to determine if both
children are black, and then to determine how many tree rotations are
required.  Rearrange the logic to avoid that extra check.

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
lib/rbtree.c