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

[patchbot@xxxxxxx]

commit 96bc157a7c71c8e3687e2aeb5b4c3cdef5f4141c
Author:     Michel Lespinasse <walken@xxxxxxxxxx>
AuthorDate: Wed Dec 20 18:03:09 2017 +0100
Commit:     Jan Beulich <jbeulich@xxxxxxxx>
CommitDate: Wed Dec 20 18:03:09 2017 +0100

    rbtree: adjust node color in __rb_erase_color() only when necessary
    
    In __rb_erase_color(), we were always setting a node to black after
    exiting the main loop.  And in one case, after fixing up the tree to
    satisfy all rbtree invariants, we were setting the current node to root
    just to guarantee a loop exit, at which point the root would be set to
    black.  However this is not necessary, as the root of an rbtree is already
    known to be black.  The only case where the color flip is required is when
    we exit the loop due to the current node being red, and it's easiest to
    just do the flip at that point instead of doing it after the loop.
    
    [adrian.hunter@xxxxxxxxx: perf tools: fix build for another rbtree.c change]
    Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
    Acked-by: David Woodhouse <David.Woodhouse@xxxxxxxxx>
    Signed-off-by: Adrian Hunter <adrian.hunter@xxxxxxxxx>
    Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
    Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
    [Linux commit d6ff1273928ebf15466a85b7e1810cd00e72998b]
    
    Ported only rbtree.c to Xen.
    
    Signed-off-by: Praveen Kumar <kpraveen.lkml@xxxxxxxxx>
    Acked-by: Jan Beulich <jbeulich@xxxxxxxx>
---
 xen/common/rbtree.c | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index fb27b0c..99a1305 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -259,10 +259,22 @@ static void __rb_erase_color(struct rb_node *node, struct 
rb_node *parent,
 {
        struct rb_node *other;
 
-       while ((!node || rb_is_black(node)) && node != root->rb_node)
-       {
-               if (parent->rb_left == node)
-               {
+       while (true) {
+               /*
+                * Loop invariant: all leaf paths going through node have a
+                * black node count that is 1 lower than other leaf paths.
+                *
+                * If node is red, we can flip it to black to adjust.
+                * If node is the root, all leaf paths go through it.
+                * Otherwise, we need to adjust the tree through color flips
+                * and tree rotations as per one of the 4 cases below.
+                */
+               if (node && rb_is_red(node)) {
+                       rb_set_black(node);
+                       break;
+               } else if (!parent) {
+                       break;
+               } else if (parent->rb_left == node) {
                        other = parent->rb_right;
                        if (rb_is_red(other))
                        {
@@ -291,12 +303,9 @@ static void __rb_erase_color(struct rb_node *node, struct 
rb_node *parent,
                                rb_set_black(parent);
                                rb_set_black(other->rb_right);
                                __rb_rotate_left(parent, root);
-                               node = root->rb_node;
                                break;
                        }
-               }
-               else
-               {
+               } else {
                        other = parent->rb_left;
                        if (rb_is_red(other))
                        {
@@ -325,13 +334,10 @@ static void __rb_erase_color(struct rb_node *node, struct 
rb_node *parent,
                                rb_set_black(parent);
                                rb_set_black(other->rb_left);
                                __rb_rotate_right(parent, root);
-                               node = root->rb_node;
                                break;
                        }
                }
        }
-       if (node)
-               rb_set_black(node);
 }
 
 void rb_erase(struct rb_node *node, struct rb_root *root)
--
generated by git-patchbot for /home/xen/git/xen.git#master

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