Re: [Xen-devel] [PATCH v6 08/16 RESEND] rbtree: optimize case selection logic in __rb_erase_color()

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> On 21.11.17 at 16:20, <kpraveen.lkml@xxxxxxxxx> wrote:
> From: Michel Lespinasse <walken@xxxxxxxxxx>
> 
> 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@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 e125d1471a4f8f1bf7ea9a83deb8d23cb40bd712]
> 
> 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