[Resend,13/17] rbtree: add __rb_change_child() helper function

Commit Message

Praveen Kumar May 31, 2017, 9:20 p.m. UTC

Add __rb_change_child() as an inline helper function to replace code that
would otherwise be duplicated 4 times in the source.

No changes to binary size or speed.

commit 7abc704ae399fcb9c51ca200b0456f8a975a8011 from Linux tree

Signed-off-by: Praveen Kumar <[e-mail]>
---
 xen/common/rbtree.c | 54 ++++++++++++++++++++++-------------------------------
 1 file changed, 22 insertions(+), 32 deletions(-)

Comments

Dario Faggioli June 12, 2017, 4:14 p.m. UTC | #1

On Thu, 2017-06-01 at 02:50 +0530, Praveen Kumar wrote:
> @@ -65,6 +65,22 @@ static inline struct rb_node *rb_red_parent(struct
> rb_node *red)
>      return (struct rb_node *)red->__rb_parent_color;
>  }
>  
> +static inline void
> +__rb_change_child(struct rb_node *old, struct rb_node *new,
> +                 struct rb_node *parent, struct rb_root *root)
> +{
> +    if (parent)
> +    {
> +        if (parent->rb_left == old)
> +            parent->rb_left = new;
> +        else
> +            parent->rb_right = new;
> +    } else
> +        root->rb_node = new;
> +}
> +
> +
> +
>
why all these blank lines? They're not there in the original Linux
commit, AFAICT.

>  /*
>   * Helper function for rotations:
>   * - old's parent and color get assigned to ne
> 
> @@ -418,15 +421,8 @@ void rb_erase(struct rb_node *node, struct
> rb_root *root)
>  
>      if (child)
>          rb_set_parent(child, parent);
> -    if (parent)
> -    {
> -        if (parent->rb_left == node)
> -            parent->rb_left = child;
> -        else
> -            parent->rb_right = child;
> -    }
> -    else
> -        root->rb_node = child;
> +
>
Same for this one here.

> +    __rb_change_child(node, child, parent, root);
>  
>   color:
>      if (color == RB_BLACK)
> @@ -523,14 +519,8 @@ void rb_replace_node(struct rb_node *victim,
> struct rb_node *new,
>      struct rb_node *parent = rb_parent(victim);
>  
>      /* Set the surrounding nodes to point to the replacement */
> -    if (parent) {
> -        if (victim == parent->rb_left)
> -            parent->rb_left = new;
> -        else
> -            parent->rb_right = new;
> -    } else {
> -        root->rb_node = new;
> -    }
> +    __rb_change_child(victim, new, parent, root);
> +
>
And here too.

Regards,
Dario

Patch

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index b65f00ca1f..3b54c04bea 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -65,6 +65,22 @@  static inline struct rb_node *rb_red_parent(struct rb_node *red)
     return (struct rb_node *)red->__rb_parent_color;
 }
 
+static inline void
+__rb_change_child(struct rb_node *old, struct rb_node *new,
+                 struct rb_node *parent, struct rb_root *root)
+{
+    if (parent)
+    {
+        if (parent->rb_left == old)
+            parent->rb_left = new;
+        else
+            parent->rb_right = new;
+    } else
+        root->rb_node = new;
+}
+
+
+
 /*
  * Helper function for rotations:
  * - old's parent and color get assigned to new
@@ -77,13 +93,7 @@  __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
     struct rb_node *parent = rb_parent(old);
     new->__rb_parent_color = old->__rb_parent_color;
     rb_set_parent_color(old, new, color);
-    if (parent) {
-        if (parent->rb_left == old)
-            parent->rb_left = new;
-        else
-            parent->rb_right = new;
-    } else
-        root->rb_node = new;
+    __rb_change_child(old, new, parent, root);
 }
 
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
@@ -381,14 +391,7 @@  void rb_erase(struct rb_node *node, struct rb_root *root)
         while ((left = node->rb_left) != NULL)
             node = left;
 
-        if (rb_parent(old))
-        {
-            if (rb_parent(old)->rb_left == old)
-                rb_parent(old)->rb_left = node;
-            else
-                rb_parent(old)->rb_right = node;
-        } else
-            root->rb_node = node;
+        __rb_change_child(old, node, rb_parent(old), root);
 
         child = node->rb_right;
         parent = rb_parent(node);
@@ -418,15 +421,8 @@  void rb_erase(struct rb_node *node, struct rb_root *root)
 
     if (child)
         rb_set_parent(child, parent);
-    if (parent)
-    {
-        if (parent->rb_left == node)
-            parent->rb_left = child;
-        else
-            parent->rb_right = child;
-    }
-    else
-        root->rb_node = child;
+
+    __rb_change_child(node, child, parent, root);
 
  color:
     if (color == RB_BLACK)
@@ -523,14 +519,8 @@  void rb_replace_node(struct rb_node *victim, struct rb_node *new,
     struct rb_node *parent = rb_parent(victim);
 
     /* Set the surrounding nodes to point to the replacement */
-    if (parent) {
-        if (victim == parent->rb_left)
-            parent->rb_left = new;
-        else
-            parent->rb_right = new;
-    } else {
-        root->rb_node = new;
-    }
+    __rb_change_child(victim, new, parent, root);
+
     if (victim->rb_left)
         rb_set_parent(victim->rb_left, new);
     if (victim->rb_right)