Re: [Xen-devel] [PATCH v6 04/16 RESEND] rbtree: break out of rb_insert_color loop after tree rotation

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> On 21.11.17 at 16:19, <kpraveen.lkml@xxxxxxxxx> wrote:
> From: Michel Lespinasse <walken@xxxxxxxxxx>
> 
> It is a well known property of rbtrees that insertion never requires more
> than two tree rotations.  In our implementation, after one loop iteration
> identified one or two necessary tree rotations, we would iterate and look
> for more.  However at that point the node's parent would always be black,
> which would cause us to exit the loop.
> 
> We can make the code flow more obvious by just adding a break statement
> after the tree rotations, where we know we are done.  Additionally, in the
> cases where two tree rotations are necessary, we don't have to update the
> 'node' pointer as it wouldn't be used until the next loop iteration, which
> we now avoid due to this break statement.
> 
> 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 1f0528653e41ec230c60f5738820e8a544731399]
> 
> 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