From a83cbe12f83d81d4b4167193fe85b1e3d745dc94 Mon Sep 17 00:00:00 2001 From: Sylvain Munaut Date: Fri, 11 Nov 2011 15:29:59 +0100 Subject: 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 Signed-off-by: Peter Zijlstra Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds ---- Signed-off-by: Sylvain Munaut --- src/rbtree.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/rbtree.c') diff --git a/src/rbtree.c b/src/rbtree.c index 9db0641c..afbdca64 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; -- cgit v1.2.3