diff options
| author | Sylvain Munaut <tnt@246tNt.com> | 2011-11-11 15:25:25 +0100 |
|---|---|---|
| committer | Harald Welte <laforge@gnumonks.org> | 2011-11-12 23:23:35 +0100 |
| commit | 0395c6e7c4baceae4539e4a7ede9a4473c57a350 (patch) | |
| tree | 89921ffbfcb772100d358c2b7bc570c9894c7f0d | |
| parent | 2179f402e062f40a357759ad28717a79df062697 (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>
| -rw-r--r-- | src/rbtree.c | 14 |
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; |