* [merged] rbtree-place-easiest-case-first-in-rb_erase.patch removed from -mm tree
@ 2012-10-09 18:09 akpm
0 siblings, 0 replies; only message in thread
From: akpm @ 2012-10-09 18:09 UTC (permalink / raw)
To: walken, a.p.zijlstra, aarcange, dwmw2, riel, mm-commits
The patch titled
Subject: rbtree: place easiest case first in rb_erase()
has been removed from the -mm tree. Its filename was
rbtree-place-easiest-case-first-in-rb_erase.patch
This patch was dropped because it was merged into mainline or a subsystem tree
------------------------------------------------------
From: Michel Lespinasse <walken@google.com>
Subject: rbtree: place easiest case first in rb_erase()
In rb_erase, move the easy case (node to erase has no more than
1 child) first. I feel the code reads easier that way.
Signed-off-by: Michel Lespinasse <walken@google.com>
Reviewed-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
lib/rbtree.c | 35 ++++++++++++++++++-----------------
1 file changed, 18 insertions(+), 17 deletions(-)
diff -puN lib/rbtree.c~rbtree-place-easiest-case-first-in-rb_erase lib/rbtree.c
--- a/lib/rbtree.c~rbtree-place-easiest-case-first-in-rb_erase
+++ a/lib/rbtree.c
@@ -368,17 +368,28 @@ static void __rb_erase_color(struct rb_n
void rb_erase(struct rb_node *node, struct rb_root *root)
{
- struct rb_node *child, *parent;
+ struct rb_node *child = node->rb_right, *tmp = node->rb_left;
+ struct rb_node *parent;
int color;
- if (!node->rb_left)
- child = node->rb_right;
- else if (!node->rb_right)
- child = node->rb_left;
- else {
+ if (!tmp) {
+ case1:
+ /* Case 1: node to erase has no more than 1 child (easy!) */
+
+ parent = rb_parent(node);
+ color = rb_color(node);
+
+ if (child)
+ rb_set_parent(child, parent);
+ __rb_change_child(node, child, parent, root);
+ } else if (!child) {
+ /* Still case 1, but this time the child is node->rb_left */
+ child = tmp;
+ goto case1;
+ } else {
struct rb_node *old = node, *left;
- node = node->rb_right;
+ node = child;
while ((left = node->rb_left) != NULL)
node = left;
@@ -402,18 +413,8 @@ void rb_erase(struct rb_node *node, stru
node->__rb_parent_color = old->__rb_parent_color;
node->rb_left = old->rb_left;
rb_set_parent(old->rb_left, node);
-
- goto color;
}
- parent = rb_parent(node);
- color = rb_color(node);
-
- if (child)
- rb_set_parent(child, parent);
- __rb_change_child(node, child, parent, root);
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2012-10-09 18:09 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-10-09 18:09 [merged] rbtree-place-easiest-case-first-in-rb_erase.patch removed from -mm tree akpm
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.