From 9bb922c85c4030edd1ec367980bd1bdd4b39674a Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Fri, 28 Sep 2012 10:19:26 +1000 Subject: [PATCH] rbtree: adjust root color in rb_insert_color() only when necessary The root node of an rbtree must always be black. However, rb_insert_color() only needs to maintain this invariant when it has been broken - that is, when it exits the loop due to the current (red) node being the root. In all other cases (exiting after tree rotations, or exiting due to an existing black parent) the invariant is already satisfied, so there is no need to adjust the root node color. Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: Andrew Morton --- lib/rbtree.c | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index 12abb8abf442..d0be5fcaafe8 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -91,8 +91,21 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) { struct rb_node *parent, *gparent; - while ((parent = rb_parent(node)) && rb_is_red(parent)) - { + while (true) { + /* + * Loop invariant: node is red + * + * If there is a black parent, we are done. + * Otherwise, take some corrective action as we don't + * want a red root or two consecutive red nodes. + */ + parent = rb_parent(node); + if (!parent) { + rb_set_black(node); + break; + } else if (rb_is_black(parent)) + break; + gparent = rb_parent(parent); if (parent == gparent->rb_left) @@ -142,8 +155,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) break; } } - - rb_set_black(root->rb_node); } EXPORT_SYMBOL(rb_insert_color); -- 2.39.5