[Xen-changelog] [xen master] rbtree: place easiest case first in rb_erase()

[patchbot@xxxxxxx]

commit a6b1da2915b195cda66026e1024dc54375da08b4
Author:     Michel Lespinasse <walken@xxxxxxxxxx>
AuthorDate: Wed Jan 3 12:41:29 2018 +0100
Commit:     Jan Beulich <jbeulich@xxxxxxxx>
CommitDate: Wed Jan 3 12:41:29 2018 +0100

    rbtree: place easiest case first in rb_erase()
    
    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.
    
    Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
    Reviewed-by: Rik van Riel <riel@xxxxxxxxxx>
    Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
    Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
    [Linux commit 60670b8034d6e2ba860af79c9379b7788d09db73]
    
    Ported to Xen.
    
    Signed-off-by: Praveen Kumar <kpraveen.lkml@xxxxxxxxx>
    Acked-by: Jan Beulich <jbeulich@xxxxxxxx>
---
 xen/common/rbtree.c | 35 ++++++++++++++++++-----------------
 1 file changed, 18 insertions(+), 17 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 0bba524..e569704 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -368,17 +368,28 @@ 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;
 
@@ -402,18 +413,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
                node->__rb_parent_color = old->__rb_parent_color;
                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);
 }
--
generated by git-patchbot for /home/xen/git/xen.git#master

_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/xen-changelog