[Xen-devel] [PATCH v4 16/17] rbtree: low level optimizations in rb_erase()

[Praveen Kumar <kpraveen.lkml@xxxxxxxxx>]

From: Michel Lespinasse <walken@xxxxxxxxxx>

Various minor optimizations in rb_erase():
- Avoid multiple loading of node->__rb_parent_color when computing parent
  and color information (possibly not in close sequence, as there might
  be further branches in the algorithm)
- In the 1-child subcase of case 1, copy the __rb_parent_color field from
  the erased node to the child instead of recomputing it from the desired
  parent and color
- When searching for the erased node's successor, differentiate between
  cases 2 and 3 based on whether any left links were followed. This avoids
  a condition later down.
- In case 3, keep a pointer to the erased node's right child so we don't
  have to refetch it later to adjust its parent.
- In the no-childs subcase of cases 2 and 3, place the rebalance assigment
  last so that the compiler can remove the following if(rebalance) test.

Also, added some comments to illustrate cases 2 and 3.

Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
Acked-by: Rik van Riel <riel@xxxxxxxxxx>
Cc: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
Cc: Andrea Arcangeli <aarcange@xxxxxxxxxx>
Cc: David Woodhouse <dwmw2@xxxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
[Linux commit 4f035ad67f4633c233cb3642711d49b4efc9c82d]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@xxxxxxxxx>
---
 xen/common/rbtree.c | 100 +++++++++++++++++++++++++++++++++-------------------
 1 file changed, 64 insertions(+), 36 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index e506e0451d..678adf5aa3 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -46,9 +46,14 @@
 #define                RB_RED          0
 #define                RB_BLACK        1
 
-#define rb_color(r)   ((r)->__rb_parent_color & 1)
-#define rb_is_red(r)   (!rb_color(r))
-#define rb_is_black(r) rb_color(r)
+#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
+
+#define __rb_color(pc)     ((pc) & 1)
+#define __rb_is_black(pc)  __rb_color(pc)
+#define __rb_is_red(pc)    (!__rb_color(pc))
+#define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
+#define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
+#define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
 
 static inline void rb_set_black(struct rb_node *rb)
 {
@@ -377,6 +382,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 {
        struct rb_node *child = node->rb_right, *tmp = node->rb_left;
        struct rb_node *parent, *rebalance;
+       unsigned long pc;
 
        if (!tmp) {
                /*
@@ -386,53 +392,75 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
                 * and node must be black due to 4). We adjust colors locally
                 * so as to bypass __rb_erase_color() later on.
                 */
-
-               parent = rb_parent(node);
-
+               pc = node->__rb_parent_color;
+               parent = __rb_parent(pc);
                __rb_change_child(node, child, parent, root);
                if (child) {
-                       rb_set_parent_color(child, parent, RB_BLACK);
+                       child->__rb_parent_color = pc;
                        rebalance = NULL;
-               } else {
-                       rebalance = rb_is_black(node) ? parent : NULL;
-               }
+               } else
+                       rebalance = __rb_is_black(pc) ? parent : NULL;
        } else if (!child) {
                /* Still case 1, but this time the child is node->rb_left */
-               parent = rb_parent(node);
+               tmp->__rb_parent_color = pc = node->__rb_parent_color;
+               parent = __rb_parent(pc);
                __rb_change_child(node, tmp, parent, root);
-               rb_set_parent_color(tmp, parent, RB_BLACK);
                rebalance = NULL;
        } else {
-               struct rb_node *old = node, *left;
-
-               node = child;
-               while ((left = node->rb_left) != NULL)
-                       node = left;
-
-               __rb_change_child(old, node, rb_parent(old), root);
-
-               child = node->rb_right;
-               parent = rb_parent(node);
-
-               if (parent == old) {
-                       parent = node;
+               struct rb_node *successor = child, *child2;
+               tmp = child->rb_left;
+               if (!tmp) {
+                       /*
+                        * Case 2: node's successor is its right child
+                        *
+                        *    (n)          (s)
+                        *    / \          / \
+                        *  (x) (s)  ->  (x) (c)
+                        *        \
+                        *        (c)
+                        */
+                       parent = child;
+                       child2 = child->rb_right;
                } else {
-                       parent->rb_left = child;
-
-                       node->rb_right = old->rb_right;
-                       rb_set_parent(old->rb_right, node);
+                       /*
+                        * Case 3: node's successor is leftmost under
+                        * node's right child subtree
+                        *
+                        *    (n)          (s)
+                        *    / \          / \
+                        *  (x) (y)  ->  (x) (y)
+                        *      /            /
+                        *    (p)          (p)
+                        *    /            /
+                        *  (s)          (c)
+                        *    \
+                        *    (c)
+                        */
+                       do {
+                               parent = successor;
+                               successor = tmp;
+                               tmp = tmp->rb_left;
+                       } while (tmp);
+                       parent->rb_left = child2 = successor->rb_right;
+                       successor->rb_right = child;
+                       rb_set_parent(child, successor);
                }
 
-               if (child) {
-                       rb_set_parent_color(child, parent, RB_BLACK);
+               successor->rb_left = tmp = node->rb_left;
+               rb_set_parent(tmp, successor);
+
+               pc = node->__rb_parent_color;
+               tmp = __rb_parent(pc);
+               __rb_change_child(node, successor, tmp, root);
+               if (child2) {
+                       successor->__rb_parent_color = pc;
+                       rb_set_parent_color(child2, parent, RB_BLACK);
                        rebalance = NULL;
                } else {
-                       rebalance = rb_is_black(node) ? parent : NULL;
+                       unsigned long pc2 = successor->__rb_parent_color;
+                       successor->__rb_parent_color = pc;
+                       rebalance = __rb_is_black(pc2) ? parent : NULL;
                }
-               node->__rb_parent_color = old->__rb_parent_color;
-               node->rb_left = old->rb_left;
-
-               rb_set_parent(old->rb_left, node);
        }
 
        if (rebalance)
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
https://lists.xen.org/xen-devel