Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752497AbbHWMPQ (ORCPT ); Sun, 23 Aug 2015 08:15:16 -0400 Received: from e28smtp01.in.ibm.com ([122.248.162.1]:34624 "EHLO e28smtp01.in.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752310AbbHWMPN (ORCPT ); Sun, 23 Aug 2015 08:15:13 -0400 X-Helo: d28dlp02.in.ibm.com X-MailFrom: weiyang@linux.vnet.ibm.com X-RcptTo: linux-kernel@vger.kernel.org From: Wei Yang To: walken@google.com Cc: linux-kernel@vger.kernel.org, Wei Yang Subject: [PATCH] rbtree: increase readability of __rb_erase_augmented() Date: Sun, 23 Aug 2015 20:14:56 +0800 Message-Id: <1440332096-7850-1-git-send-email-weiyang@linux.vnet.ibm.com> X-Mailer: git-send-email 2.5.0 X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 15082312-4790-0000-0000-000009F07717 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3031 Lines: 86 __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 --- 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/