| Message ID | 20170531212056.10583-15-kpraveen.lkml@gmail.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Thu, 2017-06-01 at 02:50 +0530, Praveen Kumar wrote: > --- a/xen/common/rbtree.c > +++ b/xen/common/rbtree.c > @@ -376,18 +376,29 @@ static void __rb_erase_color(struct rb_node > *node, struct rb_node *parent, > > void rb_erase(struct rb_node *node, struct rb_root *root) > { > - struct rb_node *child, *parent; > + struct rb_node *child = node->rb_right, *tmp = node->rb_left; > + struct rb_node *parent; > int color; > > - if (!node->rb_left) > - child = node->rb_right; > - else if (!node->rb_right) > - child = node->rb_left; > - else > + if (!tmp) > { > In the original Linux commit, this is: if (!tmp) { I know that putting the '{' on new line is more Xen-ish, but since the file is going to end up in a mixed style anyway, I think it's better to import the commit as is (as much as possible) rather than make this micro-adjustment (which, in future, may make importing new Linux commits difficult). > + case1: > + /* Case 1: node to erase has no more than 1 child (easy!) */ > + > + parent = rb_parent(node); > + color = rb_color(node); > + > + if (child) > + rb_set_parent(child, parent); > + __rb_change_child(node, child, parent, root); > + } else if (!child) { > + /* Still case 1, but this time the child is node->rb_left */ > + child = tmp; > + goto case1; > + } else { > struct rb_node *old = node, *left; > > - node = node->rb_right; > + node = child; > while ((left = node->rb_left) != NULL) > node = left; > Regards, Dario
diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index 3b54c04bea..69c7496c65 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -376,18 +376,29 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, void rb_erase(struct rb_node *node, struct rb_root *root) { - struct rb_node *child, *parent; + struct rb_node *child = node->rb_right, *tmp = node->rb_left; + struct rb_node *parent; int color; - if (!node->rb_left) - child = node->rb_right; - else if (!node->rb_right) - child = node->rb_left; - else + if (!tmp) { + case1: + /* Case 1: node to erase has no more than 1 child (easy!) */ + + parent = rb_parent(node); + color = rb_color(node); + + if (child) + rb_set_parent(child, parent); + __rb_change_child(node, child, parent, root); + } else if (!child) { + /* Still case 1, but this time the child is node->rb_left */ + child = tmp; + goto case1; + } else { struct rb_node *old = node, *left; - node = node->rb_right; + node = child; while ((left = node->rb_left) != NULL) node = left; @@ -412,19 +423,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root) node->rb_left = old->rb_left; rb_set_parent(old->rb_left, node); - - goto color; } - parent = rb_parent(node); - color = rb_color(node); - - if (child) - rb_set_parent(child, parent); - - __rb_change_child(node, child, parent, root); - - color: if (color == RB_BLACK) __rb_erase_color(child, parent, root); }
In rb_erase, move the easy case (node to erase has no more than 1 child) first. I feel the code reads easier that way. commit 60670b8034d6e2ba860af79c9379b7788d09db73 from Linux tree Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com> --- xen/common/rbtree.c | 36 ++++++++++++++++++------------------ 1 file changed, 18 insertions(+), 18 deletions(-)