aboutsummaryrefslogtreecommitdiffstats
path: root/lib/rbtree.c
diff options
context:
space:
mode:
authorDavid Woodhouse <dwmw2@infradead.org>2006-04-21 08:30:36 -0400
committerDavid Woodhouse <dwmw2@infradead.org>2006-04-21 08:30:36 -0400
commit1975e59375756da4ff4e6e7d12f67485e813ace0 (patch)
tree2370244862fa47b4ad8d4156d1a4ed32c326d628 /lib/rbtree.c
parent21f1d5fc592e145574dede8debe9603334d08fde (diff)
[RBTREE] Remove dead code in rb_erase()
Observe rb_erase(), when the victim node 'old' has two children so neither of the simple cases at the beginning are taken. Observe that it effectively does an 'rb_next()' operation to find the next (by value) node in the tree. That is; we go to the victim's right-hand child and then follow left-hand pointers all the way down the tree as far as we can until we find the next node 'node'. We end up with 'node' being either the same immediate right-hand child of 'old', or one of its descendants on the far left-hand side. For a start, we _know_ that 'node' has a parent. We can drop that check. We also know that if 'node's parent is 'old', then 'node' is the right-hand child of its parent. And that if 'node's parent is _not_ 'old', then 'node' is the left-hand child of its parent. So instead of checking for 'node->rb_parent == old' in one place and also checking 'node's heritage separately when we're trying to change its link from its parent, we can shuffle things around a bit and do it like this... Signed-off-by: David Woodhouse <dwmw2@infradead.org>
Diffstat (limited to 'lib/rbtree.c')
-rw-r--r--lib/rbtree.c15
1 files changed, 5 insertions, 10 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 14b791ac5089..63473e04f18a 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -243,18 +243,13 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
243 243
244 if (child) 244 if (child)
245 child->rb_parent = parent; 245 child->rb_parent = parent;
246 if (parent)
247 {
248 if (parent->rb_left == node)
249 parent->rb_left = child;
250 else
251 parent->rb_right = child;
252 }
253 else
254 root->rb_node = child;
255 246
256 if (node->rb_parent == old) 247 if (node->rb_parent == old) {
248 parent->rb_right = child;
257 parent = node; 249 parent = node;
250 } else
251 parent->rb_left = child;
252
258 node->rb_parent = old->rb_parent; 253 node->rb_parent = old->rb_parent;
259 node->rb_color = old->rb_color; 254 node->rb_color = old->rb_color;
260 node->rb_right = old->rb_right; 255 node->rb_right = old->rb_right;