* [PATCH 2/3] Further optimization of function rb_erase() in lib/rbtree.c
@ 2009-04-10 10:23 Wolfram Strepp
0 siblings, 0 replies; only message in thread
From: Wolfram Strepp @ 2009-04-10 10:23 UTC (permalink / raw)
To: linux-kernel; +Cc: akpm, peterz, lowdanie
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>
---
lib/rbtree.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
Index: linux-2.6/lib/rbtree.c
===================================================================
--- linux-2.6.orig/lib/rbtree.c
+++ linux-2.6/lib/rbtree.c
@@ -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;
--
Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2009-04-10 10:24 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-04-10 10:23 [PATCH 2/3] Further optimization of function rb_erase() in lib/rbtree.c Wolfram Strepp
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).