summaryrefslogtreecommitdiffstats
path: root/src/rbtree.c
diff options
context:
space:
mode:
authorSylvain Munaut <tnt@246tNt.com>2011-11-11 15:25:25 +0100
committerHarald Welte <laforge@gnumonks.org>2011-11-12 23:23:35 +0100
commit0395c6e7c4baceae4539e4a7ede9a4473c57a350 (patch)
tree89921ffbfcb772100d358c2b7bc570c9894c7f0d /src/rbtree.c
parent2179f402e062f40a357759ad28717a79df062697 (diff)
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 <wstrepp@gmx.de> Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Andrea Arcangeli <andrea@qumranet.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> ---- Signed-off-by: Sylvain Munaut <tnt@246tNt.com>
Diffstat (limited to 'src/rbtree.c')
-rw-r--r--src/rbtree.c14
1 files changed, 4 insertions, 10 deletions
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;