Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1211610

[PATCH] rbtree: increase readability of __rb_erase_augmented()

Show all headers | View raw

__rb_erase_augmented() is the fundamental part of erase a node from rbtree,
while to some extend it is hard to understand.

This patch replaces some code with macro to make it more easy to
understand for audience.
1. rb_parent(node) replaces __rb_parent(pc)
2. rb_set_parent_color() replaces direct assignment of __rb_parent_color
3. rb_is_black(node) replaces __rb_is_black(pc)
4. merges the successor's parent/color change together after every thing is
   set down.

Signed-off-by: Wei Yang <weiyang@linux.vnet.ibm.com>
---
 include/linux/rbtree_augmented.h | 24 +++++++++---------------
 1 file changed, 9 insertions(+), 15 deletions(-)

diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index 14d7b83..f25a786 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -140,7 +140,6 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
 	struct rb_node *child = node->rb_right;
 	struct rb_node *tmp = node->rb_left;
 	struct rb_node *parent, *rebalance;
-	unsigned long pc;
 
 	if (!tmp) {
 		/*
@@ -150,20 +149,19 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
 		 * and node must be black due to 4). We adjust colors locally
 		 * so as to bypass __rb_erase_color() later on.
 		 */
-		pc = node->__rb_parent_color;
-		parent = __rb_parent(pc);
+		parent = rb_parent(node);
 		__rb_change_child(node, child, parent, root);
 		if (child) {
-			child->__rb_parent_color = pc;
+			rb_set_parent_color(child, parent, rb_color(node));
 			rebalance = NULL;
 		} else
-			rebalance = __rb_is_black(pc) ? parent : NULL;
+			rebalance = rb_is_black(node) ? parent : NULL;
 		tmp = parent;
 	} else if (!child) {
 		/* Still case 1, but this time the child is node->rb_left */
-		tmp->__rb_parent_color = pc = node->__rb_parent_color;
-		parent = __rb_parent(pc);
+		parent = rb_parent(node);
 		__rb_change_child(node, tmp, parent, root);
+		rb_set_parent_color(tmp, parent, rb_color(node));
 		rebalance = NULL;
 		tmp = parent;
 	} else {
@@ -217,19 +215,15 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
 		WRITE_ONCE(successor->rb_left, tmp);
 		rb_set_parent(tmp, successor);
 
-		pc = node->__rb_parent_color;
-		tmp = __rb_parent(pc);
+		tmp = rb_parent(node);
 		__rb_change_child(node, successor, tmp, root);
 
 		if (child2) {
-			successor->__rb_parent_color = pc;
 			rb_set_parent_color(child2, parent, RB_BLACK);
 			rebalance = NULL;
-		} else {
-			unsigned long pc2 = successor->__rb_parent_color;
-			successor->__rb_parent_color = pc;
-			rebalance = __rb_is_black(pc2) ? parent : NULL;
-		}
+		} else
+			rebalance = rb_is_black(successor) ? parent : NULL;
+		rb_set_parent_color(successor, tmp, rb_color(node));
 		tmp = successor;
 	}
 
-- 
2.5.0

--
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/

Back to linux.kernel | Previous | Next | Find similar | Unroll thread

Thread

[PATCH] rbtree: increase readability of __rb_erase_augmented() Wei Yang <weiyang@linux.vnet.ibm.com> - 2015-08-23 14:20 +0200

csiph-web