Skip to contentSkip to conversation

Further optimization of function rb_erase() in lib/rbtree.c

PATCH In review Wolfram Strepp 2 participants 2 messages Apr 10, 2009 – Apr 11, 2009 Library code

lore
Share & tools
lore
#0 lore raw

PATCH 1/3 Further optimization of function rb_erase() in lib/rbtree.c

This small patch-series reorganizes some lines in function rb_erase() in lib/rbtree.c, and as a result one if-condition can be omitted. Tested on x86.

First, move some code around in order to make the next change more obvious.

---
 lib/rbtree.c |   19 ++++++++++---------
 1 file changed, 10 insertions(+), 9 deletions(-)
lib/rbtree.c +10 -9
Index: linux-2.6/lib/rbtree.c
===================================================================
@@ -237,6 +237,16 @@ void rb_erase(struct rb_node *node, stru
 		node = node->rb_right;
 		while ((left = node->rb_left) != NULL)
 			node = left;
+
+		if (rb_parent(old))
+		{
+			if (rb_parent(old)->rb_left == old)
+				rb_parent(old)->rb_left = node;
+			else
+				rb_parent(old)->rb_right = node;
+		} else
+			root->rb_node = node;
+
 		child = node->rb_right;
 		parent = rb_parent(node);
 		color = rb_color(node);
@@ -253,15 +263,6 @@ void rb_erase(struct rb_node *node, stru
 		node->rb_right = old->rb_right;
 		node->rb_left = old->rb_left;
 
-		if (rb_parent(old))
-		{
-			if (rb_parent(old)->rb_left == old)
-				rb_parent(old)->rb_left = node;
-			else
-				rb_parent(old)->rb_right = node;
-		} else
-			root->rb_node = node;
-
 		rb_set_parent(old->rb_left, node);
 		if (old->rb_right)
 			rb_set_parent(old->rb_right, node);
Signature · 1 line
Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a
maintainer
#1 lore raw
Quoted 2 lines

Subject: [PATCH 1/3] Further optimization of function rb_erase() in lib/rbtree.c

Three distinct patches, all with the same title.

Please carefully choose a unique title for each patch in the series.

We push thousands and thousands of patches into Linux and it all gets complex and confusing. These little organisational things help us to manage the volume and the complexity.

Quoted 20 lines · On Fri, 10 Apr 2009 12:23:46 +0200 "Wolfram Strepp" <[email protected]> wrote:

This small patch-series reorganizes some lines in function rb_erase() in lib/rbtree.c, and as a result one if-condition can be omitted. Tested on x86.

First, move some code around in order to make the next change more obvious.

---
 lib/rbtree.c |   19 ++++++++++---------
 1 file changed, 10 insertions(+), 9 deletions(-)

Index: linux-2.6/lib/rbtree.c
===================================================================

lib/rbtree.c +0 -0
@@ -237,6 +237,16 @@ void rb_erase(struct rb_node *node, stru
 		node = node->rb_right;
 		while ((left = node->rb_left) != NULL)

lib/rbtree.c void rb_erase(struct rb_node *node, stru · line 248

Quoted 10 lines
lib/rbtree.c +9 -0
 			node = left;
+
+		if (rb_parent(old))
+		{
+			if (rb_parent(old)->rb_left == old)
+				rb_parent(old)->rb_left = node;
+			else
+				rb_parent(old)->rb_right = node;
+		} else
+			root->rb_node = node;

You may as well fix the obvious coding-style error while moving the code. scripts/checkpatch.pl will detect this one.

Quoted 19 lines
lib/rbtree.c +0 -9
 		child = node->rb_right;
 		parent = rb_parent(node);
 		color = rb_color(node);
@@ -253,15 +263,6 @@ void rb_erase(struct rb_node *node, stru
 		node->rb_right = old->rb_right;
 		node->rb_left = old->rb_left;
 
-		if (rb_parent(old))
-		{
-			if (rb_parent(old)->rb_left == old)
-				rb_parent(old)->rb_left = node;
-			else
-				rb_parent(old)->rb_right = node;
-		} else
-			root->rb_node = node;
-
 		rb_set_parent(old->rb_left, node);
 		if (old->rb_right)
 			rb_set_parent(old->rb_right, node);