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 <wal...@google.com>
> Cc: Andrea Arcangeli <aarca...@redhat.com>
> Acked-by: David Woodhouse <david.woodho...@intel.com>
> Cc: Rik van Riel <r...@redhat.com>
> Cc: Peter Zijlstra <a.p.zijls...@chello.nl>
> Cc: Daniel Santos <daniel.san...@pobox.com>
> Cc: Jens Axboe <ax...@kernel.dk>
> Cc: "Eric W. Biederman" <ebied...@xmission.com>
> Signed-off-by: Andrew Morton <a...@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torva...@linux-foundation.org>
> [Linux commit 1f0528653e41ec230c60f5738820e8a544731399]
>
> Ported to Xen.
>
> Signed-off-by: Praveen Kumar <kpraveen.l...@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)
signature.asc
Description: This is a digitally signed message part
_______________________________________________ Xen-devel mailing list Xen-devel@lists.xen.org https://lists.xen.org/xen-devel
