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

1 files changed, 18 insertions, 17 deletions

diff --git a/lib/rbtree.c b/lib/rbtree.c
index de89a614b1ba..bde1b5c5fb33 100644
--- a/lib/rbtree.c
+++ b/lib/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);
 }