linux-kernel - [PATCH] rbtree: increase readability of __rb_erase

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Date:	Sun, 23 Aug 2015 20:14:56 +0800
From:	Wei Yang <weiyang@...ux.vnet.ibm.com>
To:	walken@...gle.com
Cc:	linux-kernel@...r.kernel.org, Wei Yang <weiyang@...ux.vnet.ibm.com>
Subject: [PATCH] rbtree: increase readability of __rb_erase_augmented()

__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@...ux.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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/