]> git.karo-electronics.de Git - karo-tx-linux.git/commit
rbtree: adjust node color in __rb_erase_color() only when necessary
authorMichel Lespinasse <walken@google.com>
Fri, 28 Sep 2012 00:19:27 +0000 (10:19 +1000)
committerStephen Rothwell <sfr@canb.auug.org.au>
Fri, 5 Oct 2012 04:00:56 +0000 (14:00 +1000)
commit137d2859608b89d268ab456c20d14f80c18ba1a3
treea68bb1e6ccf242b32ff3702b4009d5aac1b20f48
parentadd99639b1e3d6a254f33c8f5c7a733b7be5f4cb
rbtree: adjust node color in __rb_erase_color() only when necessary

In __rb_erase_color(), we were always setting a node to black after
exiting the main loop.  And in one case, after fixing up the tree to
satisfy all rbtree invariants, we were setting the current node to root
just to guarantee a loop exit, at which point the root would be set to
black.  However this is not necessary, as the root of an rbtree is already
known to be black.  The only case where the color flip is required is when
we exit the loop due to the current node being red, and it's easiest to
just do the flip at that point instead of doing it after the loop.

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