[Xen-changelog] [xen master] rbtree: adjust root color in rb_insert_color() only when necessary

[patchbot@xxxxxxx]

commit 74ed07944ad082dc54d5bcead9faae35ee83099f
Author:     Michel Lespinasse <walken@xxxxxxxxxx>
AuthorDate: Wed Dec 20 18:02:31 2017 +0100
Commit:     Jan Beulich <jbeulich@xxxxxxxx>
CommitDate: Wed Dec 20 18:02:31 2017 +0100

    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 <walken@xxxxxxxxxx>
    Acked-by: David Woodhouse <David.Woodhouse@xxxxxxxxx>
    Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
    Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
    [Linux commit 6d58452dc066db61acdff7b84671db1b11a3de1c]
    
    Ported to Xen.
    
    Signed-off-by: Praveen Kumar <kpraveen.lkml@xxxxxxxxx>
    Acked-by: Jan Beulich <jbeulich@xxxxxxxx>
---
 xen/common/rbtree.c | 19 +++++++++++++++----
 1 file changed, 15 insertions(+), 4 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 9dc296e..244f1d8 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/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);
 
--
generated by git-patchbot for /home/xen/git/xen.git#master

_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/xen-changelog