Messages in this thread Patch in this message | | | Date | Fri, 10 Apr 2009 12:23:56 +0200 | From | "Wolfram Strepp" <> | Subject | [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 <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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |