Message ID | 20170617093253.3990-9-kpraveen.lkml@gmail.com (mailing list archive) |
---|---|
State | New, archived |
Headers | show |
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
diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index 49f73e2461..25902c0659 100644 --- 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) { - register struct rb_node *tmp; __rb_rotate_left(parent, root); - tmp = parent; parent = node; - node = tmp; } rb_set_black(parent); rb_set_red(gparent); __rb_rotate_right(gparent, root); + break; } else { { register struct rb_node *uncle = gparent->rb_left; @@ -135,16 +133,14 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) if (parent->rb_left == node) { - register struct rb_node *tmp; __rb_rotate_right(parent, root); - tmp = parent; parent = node; - node = tmp; } rb_set_black(parent); rb_set_red(gparent); __rb_rotate_left(gparent, root); + break; } }