diff options
| author | Wolfram Strepp <wstrepp@gmx.de> | 2009-06-16 15:34:12 -0700 |
|---|---|---|
| committer | Linus Torvalds <torvalds@linux-foundation.org> | 2009-06-16 19:47:56 -0700 |
| commit | 4c60117811171d867d4f27f17ea07d7419d45dae (patch) | |
| tree | 9148532285b9276573f000b3125aee885afce411 /lib | |
| parent | 16c047add3ceaf0ab882e3e094d1ec904d02312d (diff) | |
| download | op-kernel-dev-4c60117811171d867d4f27f17ea07d7419d45dae.zip op-kernel-dev-4c60117811171d867d4f27f17ea07d7419d45dae.tar.gz | |
rb_tree: make clear distinction between two different cases in rb_erase()
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>
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/rbtree.c | 8 |
1 files changed, 4 insertions, 4 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c index 0455685..4b4b29b 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -244,13 +244,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; |
