From 0395c6e7c4baceae4539e4a7ede9a4473c57a350 Mon Sep 17 00:00:00 2001 From: Sylvain Munaut Date: Fri, 11 Nov 2011 15:25:25 +0100 Subject: core/rbtree: optimize rb_erase() See kernel commit 55a63998b8967615a15e2211ba0ff3a84a565824 ---- 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 Acked-by: Peter Zijlstra Cc: Andrea Arcangeli Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds ---- Signed-off-by: Sylvain Munaut --- src/rbtree.c | 14 ++++---------- 1 file changed, 4 insertions(+), 10 deletions(-) (limited to 'src/rbtree.c') diff --git a/src/rbtree.c b/src/rbtree.c index 9b7fe83c..d1c2f6b1 100644 --- a/src/rbtree.c +++ b/src/rbtree.c @@ -161,17 +161,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; @@ -198,17 +195,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; -- cgit v1.2.3