[Xen-devel] [PATCH 02/20] lib/rbtree.c: optimize rb_erase()

[Praveen Kumar <kpraveen.lkml@xxxxxxxxx>]

Tfour 4 redundant if-conditions in function __rb_erase_color() in
lib/rbtree.c are removed.

In pseudo-source-code, the structure of the code is as follows:

if ((!A || B) && (!C || D)) {
.
.
.
} else {
                if (!C || D) {//if this is true, it implies: (A == true) && (B 
== false)
                                if (A) {//hence this always evaluates to 
'true'...
                                                .
                                }
                                .
                                //at this point, C always becomes true, because 
of:
                                __rb_rotate_right/left();
                                //and:
                                other = parent->rb_right/left;
                }
                .
                .
                if (C) {//...and this too !
                                .
                }
}

Signed-off-by: Wolfram Strepp <wstrepp@xxxxxx>
Acked-by: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
Cc: Andrea Arcangeli <andrea@xxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
[Linux commit 55a63998b8967615a15e2211ba0ff3a84a565824]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@xxxxxxxxx>
---
 xen/common/rbtree.c | 14 ++++----------
 1 file changed, 4 insertions(+), 10 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index d86b5f25c0..70cb15f1fe 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -162,17 +162,14 @@ static void __rb_erase_color(struct rb_node *node, struct 
rb_node *parent,
             {
                 if (!other->rb_right || rb_is_black(other->rb_right))
                 {
-                    struct rb_node *o_left;
-                    if ((o_left = other->rb_left))
-                        rb_set_black(o_left);
+                    rb_set_black(other->rb_left);
                     rb_set_red(other);
                     __rb_rotate_right(other, root);
                     other = parent->rb_right;
                 }
                 rb_set_color(other, rb_color(parent));
                 rb_set_black(parent);
-                if (other->rb_right)
-                    rb_set_black(other->rb_right);
+                rb_set_black(other->rb_right);
                 __rb_rotate_left(parent, root);
                 node = root->rb_node;
                 break;
@@ -199,17 +196,14 @@ static void __rb_erase_color(struct rb_node *node, struct 
rb_node *parent,
             {
                 if (!other->rb_left || rb_is_black(other->rb_left))
                 {
-                    register struct rb_node *o_right;
-                    if ((o_right = other->rb_right))
-                        rb_set_black(o_right);
+                    rb_set_black(other->rb_right);
                     rb_set_red(other);
                     __rb_rotate_left(other, root);
                     other = parent->rb_left;
                 }
                 rb_set_color(other, rb_color(parent));
                 rb_set_black(parent);
-                if (other->rb_left)
-                    rb_set_black(other->rb_left);
+                rb_set_black(other->rb_left);
                 __rb_rotate_right(parent, root);
                 node = root->rb_node;
                 break;
-- 
2.12.0


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