Re: [Xen-devel] [PATCH v6 05/16 RESEND] rbtree: adjust root color in rb_insert_color() only when necessary

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> On 21.11.17 at 16:19, <kpraveen.lkml@xxxxxxxxx> wrote:
> From: Michel Lespinasse <walken@xxxxxxxxxx>
> 
> The root node of an rbtree must always be black.  However,
> rb_insert_color() only needs to maintain this invariant when it has been
> broken - that is, when it exits the loop due to the current (red) node
> being the root.  In all other cases (exiting after tree rotations, or
> exiting due to an existing black parent) the invariant is already
> satisfied, so there is no need to adjust the root node color.
> 
> Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
> Cc: Andrea Arcangeli <aarcange@xxxxxxxxxx>
> Acked-by: David Woodhouse <David.Woodhouse@xxxxxxxxx>
> Cc: Rik van Riel <riel@xxxxxxxxxx>
> Cc: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
> Cc: Daniel Santos <daniel.santos@xxxxxxxxx>
> Cc: Jens Axboe <axboe@xxxxxxxxx>
> Cc: "Eric W. Biederman" <ebiederm@xxxxxxxxxxxx>
> Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
> Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
> [Linux commit 6d58452dc066db61acdff7b84671db1b11a3de1c]
> 
> Ported to Xen.
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@xxxxxxxxx>

Acked-by: Jan Beulich <jbeulich@xxxxxxxx>



_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/xen-devel