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