Re: [Resend][PATCH 14/17] rbtree: place easiest case first in rb_erase()

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

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

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
-- 
<<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