diff options
| author | Sylvain Munaut <tnt@246tNt.com> | 2011-11-11 15:29:59 +0100 |
|---|---|---|
| committer | Harald Welte <laforge@gnumonks.org> | 2011-11-12 23:23:35 +0100 |
| commit | a83cbe12f83d81d4b4167193fe85b1e3d745dc94 (patch) | |
| tree | 8d73276b6d27d428a8481fc0fd399360697bfab6 /doc | |
| parent | b8c5bdefcdb91babbc025e2936702ba19d7946a9 (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>
Diffstat (limited to 'doc')
0 files changed, 0 insertions, 0 deletions