Further optimization of function rb_erase() in lib/rbtree.c
PATCH 2/3 Further optimization of function rb_erase() in lib/rbtree.c
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 <[email protected]>
Signed-off-by Peter Zijlstra <[email protected]>
--- lib/rbtree.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
lib/rbtree.c +4 -4
@@ -251,13 +251,13 @@ void rb_erase(struct rb_node *node, stru 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;
Signature · 1 line
Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01