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

[Dario Faggioli <dario.faggioli@citrix.com>]

[-- Attachment #1.1: Type: text/plain, Size: 2459 bytes --]

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@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>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> [Linux commit 1f0528653e41ec230c60f5738820e8a544731399]
> 
> Ported to Xen.
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
>
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 #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

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