Re: [Xen-devel] [PATCH v2 08/20] rbtree: break out of rb_insert_color loop after tree rotation

[Dario Faggioli <dario.faggioli@xxxxxxxxxx>]

On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote:
> 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>
>
Now the patch has all the hunks. There's again some difference in '{'
placement, though, between this patch and the Linux commit.

More specifically, in the Linux commit, this:
> --- a/xen/common/rbtree.c
> +++ b/xen/common/rbtree.c
> @@ -110,16 +110,14 @@ void rb_insert_color(struct rb_node *node,
> struct rb_root *root)
>  
>              if (parent->rb_right == node)
>              {
>
Becomes:

  if (parent->rb_right == node) {

I appreciate that you may not be applying this specific modification
because the Xen style is different. But I actually think you should, as
this file is going to end up being mixed style anyway, so I'd
prioritize staying identical to Linux's commit.

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

Attachment: signature.asc
Description: This is a digitally signed message part

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
https://lists.xen.org/xen-devel