[PATCH v2 17/20] rbtree: place easiest case first in rb_erase()

[Praveen Kumar <kpraveen.lkml@gmail.com>]

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@google.com>
Reviewed-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 60670b8034d6e2ba860af79c9379b7788d09db73]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
 xen/common/rbtree.c | 34 ++++++++++++++++++----------------
 1 file changed, 18 insertions(+), 16 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 2063536548..149c861ac6 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -370,17 +370,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;
         __rb_change_child(old, node, rb_parent(old), root);
@@ -403,17 +414,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);
 }
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel