[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Xen-devel] [PATCH 07/17] 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.

commit 6d58452dc066db61acdff7b84671db1b11a3de1c from linux tree

Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
Cc: Andrea Arcangeli <aarcange@xxxxxxxxxx>
Acked-by: David Woodhouse <David.Woodhouse@xxxxxxxxx>
Cc: Rik van Riel <riel@xxxxxxxxxx>
Cc: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
Cc: Daniel Santos <daniel.santos@xxxxxxxxx>
Cc: Jens Axboe <axboe@xxxxxxxxx>
Cc: "Eric W. Biederman" <ebiederm@xxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
 xen/common/rbtree.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index bead370436..ccf905e35c 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -90,8 +90,23 @@ void rb_insert_color(struct rb_node *node, struct rb_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)
@@ -141,8 +156,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root 
             __rb_rotate_left(gparent, root);
-    rb_set_black(root->rb_node);

Xen-devel mailing list



Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.