summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorSylvain Munaut <tnt@246tNt.com>2011-11-11 15:29:59 +0100
committerHarald Welte <laforge@gnumonks.org>2011-11-12 23:23:35 +0100
commita83cbe12f83d81d4b4167193fe85b1e3d745dc94 (patch)
tree8d73276b6d27d428a8481fc0fd399360697bfab6
parentb8c5bdefcdb91babbc025e2936702ba19d7946a9 (diff)
core/rbtree: make clear distinction between two different cases in rb_erase()
See kernel commit 4c60117811171d867d4f27f17ea07d7419d45dae ---- There are two cases when a node, having 2 childs, is erased: 'normal case': the successor is not the right-hand-child of the node to be erased 'special case': the successor is the right-hand child of the node to be erased Here some ascii-art, with following symbols (referring to the code): O: node to be deleted N: the successor of O P: parent of N C: child of N L: some other node normal case: O N / \ / \ / \ / \ L \ L \ / \ P ----> / \ P / \ / \ / / N C \ / \ \ C / \ special case: O|P N / \ / \ / \ / \ L \ L \ / \ N ----> / C \ / \ \ C / \ Notice that for the special case we don't have to reconnect C to N. Signed-off-by: Wolfram Strepp <wstrepp@gmx.de> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl> 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.c8
1 files changed, 4 insertions, 4 deletions
diff --git a/src/rbtree.c b/src/rbtree.c
index 9db0641..afbdca6 100644
--- a/src/rbtree.c
+++ b/src/rbtree.c
@@ -242,13 +242,13 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
parent = rb_parent(node);
color = rb_color(node);
- if (child)
- rb_set_parent(child, parent);
if (parent == old) {
- parent->rb_right = child;
parent = node;
- } else
+ } else {
+ if (child)
+ rb_set_parent(child, parent);
parent->rb_left = child;
+ }
node->rb_parent_color = old->rb_parent_color;
node->rb_right = old->rb_right;