[Xen-changelog] [xen master] rbtree: optimize case selection logic in __rb_erase_color()

[patchbot@xxxxxxx]

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

    rbtree: optimize case selection logic in __rb_erase_color()
    
    In __rb_erase_color(), we have to select one of 3 cases depending on the
    color on the 'other' node children.  If both children are black, we flip a
    few node colors and iterate.  Otherwise, we do either one or two tree
    rotations, depending on the color of the 'other' child opposite to 'node',
    and then we are done.
    
    The corresponding logic had duplicate checks for the color of the 'other'
    child opposite to 'node'.  It was checking it first to determine if both
    children are black, and then to determine how many tree rotations are
    required.  Rearrange the logic to avoid that extra check.
    
    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 e125d1471a4f8f1bf7ea9a83deb8d23cb40bd712]
    
    Ported to Xen.
    
    Signed-off-by: Praveen Kumar <kpraveen.lkml@xxxxxxxxx>
    Acked-by: Jan Beulich <jbeulich@xxxxxxxx>
---
 xen/common/rbtree.c | 68 +++++++++++++++++++++++------------------------------
 1 file changed, 30 insertions(+), 38 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 99a1305..61a2f5e 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -283,28 +283,24 @@ static void __rb_erase_color(struct rb_node *node, struct 
rb_node *parent,
                                __rb_rotate_left(parent, root);
                                other = parent->rb_right;
                        }
-                       if ((!other->rb_left || rb_is_black(other->rb_left)) &&
-                           (!other->rb_right || rb_is_black(other->rb_right)))
-                       {
-                               rb_set_red(other);
-                               node = parent;
-                               parent = rb_parent(node);
-                       }
-                       else
-                       {
-                               if (!other->rb_right || 
rb_is_black(other->rb_right))
-                               {
-                                       rb_set_black(other->rb_left);
+                       if (!other->rb_right || rb_is_black(other->rb_right)) {
+                               if (!other->rb_left ||
+                                   rb_is_black(other->rb_left)) {
                                        rb_set_red(other);
-                                       __rb_rotate_right(other, root);
-                                       other = parent->rb_right;
+                                       node = parent;
+                                       parent = rb_parent(node);
+                                       continue;
                                }
-                               rb_set_color(other, rb_color(parent));
-                               rb_set_black(parent);
-                               rb_set_black(other->rb_right);
-                               __rb_rotate_left(parent, root);
-                               break;
+                               rb_set_black(other->rb_left);
+                               rb_set_red(other);
+                               __rb_rotate_right(other, root);
+                               other = parent->rb_right;
                        }
+                       rb_set_color(other, rb_color(parent));
+                       rb_set_black(parent);
+                       rb_set_black(other->rb_right);
+                       __rb_rotate_left(parent, root);
+                       break;
                } else {
                        other = parent->rb_left;
                        if (rb_is_red(other))
@@ -314,28 +310,24 @@ static void __rb_erase_color(struct rb_node *node, struct 
rb_node *parent,
                                __rb_rotate_right(parent, root);
                                other = parent->rb_left;
                        }
-                       if ((!other->rb_left || rb_is_black(other->rb_left)) &&
-                           (!other->rb_right || rb_is_black(other->rb_right)))
-                       {
-                               rb_set_red(other);
-                               node = parent;
-                               parent = rb_parent(node);
-                       }
-                       else
-                       {
-                               if (!other->rb_left || 
rb_is_black(other->rb_left))
-                               {
-                                       rb_set_black(other->rb_right);
+                       if (!other->rb_left || rb_is_black(other->rb_left)) {
+                               if (!other->rb_right ||
+                                   rb_is_black(other->rb_right)) {
                                        rb_set_red(other);
-                                       __rb_rotate_left(other, root);
-                                       other = parent->rb_left;
+                                       node = parent;
+                                       parent = rb_parent(node);
+                                       continue;
                                }
-                               rb_set_color(other, rb_color(parent));
-                               rb_set_black(parent);
-                               rb_set_black(other->rb_left);
-                               __rb_rotate_right(parent, root);
-                               break;
+                               rb_set_black(other->rb_right);
+                               rb_set_red(other);
+                               __rb_rotate_left(other, root);
+                               other = parent->rb_left;
                        }
+                       rb_set_color(other, rb_color(parent));
+                       rb_set_black(parent);
+                       rb_set_black(other->rb_left);
+                       __rb_rotate_right(parent, root);
+                       break;
                }
        }
 }
--
generated by git-patchbot for /home/xen/git/xen.git#master

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