[PATCH v2] xen: common: rbtree: ported updates from linux tree

[PATCH v2] xen: common: rbtree: ported updates from linux tree

[Praveen Kumar]

Hi All,

The patch imports the changes and updates of the rbtree implementaiton
from Linux tree. But since, the only current implementation is with tmem.c,
which am not much aware off much and therefore, was unable to test the changes
thoroughly. Having said that, I do have plans of adding futher code changes
which will be using rb-tree more in credit2 scheduler and that will help in
further testing the same.

I have not imported augmented and rcu rbtree functionality to the xen tree,
as there was no specific requirement for current planned implementation.

Please share your inputs. Thanks in advance.

From Praveen Kumar <kpraveen.lkml@gmail.com> # This line is ignored.
From: Praveen Kumar <kpraveen.lkml@gmail.com>
Subject: 
In-Reply-To: 


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

[PATCH 01/17] rb_tree: reorganize code in rb_erase() for additional changes

[Praveen Kumar]

First, move some code around in order to make the next change more obvious.

commit 16c047add3ceaf0ab882e3e094d1ec904d02312d from linux tree

[akpm@linux-foundation.org: coding-style fixes]
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 19 ++++++++++---------
 1 file changed, 10 insertions(+), 9 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 3328960d56..9826909a2a 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -236,6 +236,16 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         node = node->rb_right;
         while ((left = node->rb_left) != NULL)
             node = left;
+
+        if (rb_parent(old))
+        {
+            if (rb_parent(old)->rb_left == old)
+                rb_parent(old)->rb_left = node;
+            else
+                rb_parent(old)->rb_right = node;
+        } else
+            root->rb_node = node;
+
         child = node->rb_right;
         parent = rb_parent(node);
         color = rb_color(node);
@@ -252,15 +262,6 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         node->rb_right = old->rb_right;
         node->rb_left = old->rb_left;
 
-        if (rb_parent(old))
-        {
-            if (rb_parent(old)->rb_left == old)
-                rb_parent(old)->rb_left = node;
-            else
-                rb_parent(old)->rb_right = node;
-        } else
-            root->rb_node = node;
-
         rb_set_parent(old->rb_left, node);
         if (old->rb_right)
             rb_set_parent(old->rb_right, node);
-- 
2.12.0


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

[PATCH 02/17] rb_tree: make clear distinction between two different cases in rb_erase()

[Praveen Kumar]

There are two cases when a node, having 2 childs, is erased:
'normal case': the successor is not the right-hand-child of the node to be
erased
'special case': the successor is the right-hand child of the node to be
erased

Here some ascii-art, with following symbols (referring to the code):
O: node to be deleted
N: the successor of O
P: parent of N
C: child of N
L: some other node

normal case:

                   O                         N
                  / \                       / \
                 /   \                     /   \
                L     \                   L     \
               / \     P      ---->      / \     P
                      / \                       / \
                     /                         /
                    N                         C
                     \                       / \
                      \
                       C
                      / \

special case:
                  O|P                        N
                  / \                       / \
                 /   \                     /   \
                L     \                   L     \
               / \     N      ---->      /       C
                        \                       / \
                         \
                          C
                         / \

Notice that for the special case we don't have to reconnect C to N.

commit 4c60117811171d867d4f27f17ea07d7419d45dae from linux tree

Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 9826909a2a..3df599c3cb 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -250,13 +250,13 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         parent = rb_parent(node);
         color = rb_color(node);
 
-        if (child)
-            rb_set_parent(child, parent);
         if (parent == old) {
-            parent->rb_right = child;
             parent = node;
-        } else
+        } else {
+            if (child)
+                rb_set_parent(child, parent);
             parent->rb_left = child;
+        }
 
         node->rb_parent_color = old->rb_parent_color;
         node->rb_right = old->rb_right;
-- 
2.12.0


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

[PATCH 03/17] rb_tree: remove redundant if()-condition in rb_erase()

[Praveen Kumar]

Furthermore, notice that the initial checks:

            if (!node->rb_left)
                    child = node->rb_right;
            else if (!node->rb_right)
                    child = node->rb_left;
            else
            {
                    ...
            }
guarantee that old->rb_right is set in the final else branch, therefore
we can omit checking that again.

commit 4b324126e0c6c3a5080ca3ec0981e8766ed6f1ee from linux tree

Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 3df599c3cb..0695edd9f9 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -256,15 +256,16 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
             if (child)
                 rb_set_parent(child, parent);
             parent->rb_left = child;
+
+            node->rb_right = old->rb_right;
+            rb_set_parent(old->rb_right, node);
         }
 
         node->rb_parent_color = old->rb_parent_color;
-        node->rb_right = old->rb_right;
         node->rb_left = old->rb_left;
 
         rb_set_parent(old->rb_left, node);
-        if (old->rb_right)
-            rb_set_parent(old->rb_right, node);
+
         goto color;
     }
 
-- 
2.12.0


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

[PATCH 04/17] rbtree: empty nodes have no color

[Praveen Kumar]

Empty nodes have no color.  We can make use of this property to simplify the
code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE macros.

commit 4c199a93a2d36b277a9fd209a0f2793f8460a215 from linux tree.

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Cc: John Stultz <john.stultz@linaro.org>
Signed-off-by: Stephen Rothwell <sfr@canb.auug.org.au>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c      | 4 ++--
 xen/include/xen/rbtree.h | 9 ++++++---
 2 files changed, 8 insertions(+), 5 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 0695edd9f9..81fb746b35 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -323,7 +323,7 @@ struct rb_node *rb_next(struct rb_node *node)
 {
     struct rb_node *parent;
 
-    if (rb_parent(node) == node)
+    if (RB_EMPTY_NODE(node))
         return NULL;
 
     /* If we have a right-hand child, go down and then left as far
@@ -352,7 +352,7 @@ struct rb_node *rb_prev(struct rb_node *node)
 {
     struct rb_node *parent;
 
-    if (rb_parent(node) == node)
+    if (RB_EMPTY_NODE(node))
         return NULL;
 
     /* If we have a left-hand child, go down and then right as far
diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h
index f93c4d5823..29071a7e4a 100644
--- a/xen/include/xen/rbtree.h
+++ b/xen/include/xen/rbtree.h
@@ -52,9 +52,12 @@ static inline void rb_set_color(struct rb_node *rb, int color)
 #define RB_ROOT (struct rb_root) { NULL, }
 #define rb_entry(ptr, type, member) container_of(ptr, type, member)
 
-#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
-#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
-#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
+#define RB_EMPTY_ROOT(root)  ((root)->rb_node == NULL)
+
+/* 'empty' nodes are nodes that are known not to be inserted in an rbree */
+#define RB_EMPTY_NODE(node)  ((node)->rb_parent_color == (unsigned long)(node))
+#define RB_CLEAR_NODE(node)  ((node)->rb_parent_color = (unsigned long)(node))
+
 
 extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
-- 
2.12.0


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

[PATCH 05/17] rbtree: move some implementation details from rbtree.h to rbtree.c

[Praveen Kumar]

rbtree users must use the documented APIs to manipulate the tree
structure.  Low-level helpers to manipulate node colors and parenthood are
not part of that API, so move them to lib/rbtree.c

commit bf7ad8eeab995710c766df49c9c69a8592ca0216 from linux tree

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c      | 20 +++++++++++++++++++-
 xen/include/xen/rbtree.h | 29 +++++++----------------------
 2 files changed, 26 insertions(+), 23 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 81fb746b35..1d48ac7c78 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -22,6 +22,24 @@
 #include <xen/types.h>
 #include <xen/rbtree.h>
 
+#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_set_red(r)   do { (r)->__rb_parent_color &= ~1; } while (0)
+#define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+    rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
+}
+static inline void rb_set_color(struct rb_node *rb, int color)
+{
+    rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color;
+}
+
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
     struct rb_node *right = node->rb_right;
@@ -261,7 +279,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
             rb_set_parent(old->rb_right, node);
         }
 
-        node->rb_parent_color = old->rb_parent_color;
+        node->__rb_parent_color = old->__rb_parent_color;
         node->rb_left = old->rb_left;
 
         rb_set_parent(old->rb_left, node);
diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h
index 29071a7e4a..107f1b12f2 100644
--- a/xen/include/xen/rbtree.h
+++ b/xen/include/xen/rbtree.h
@@ -21,9 +21,7 @@
 
 struct rb_node
 {
-    unsigned long  rb_parent_color;
-#define RB_RED  0
-#define RB_BLACK 1
+    unsigned long  __rb_parent_color;
     struct rb_node *rb_right;
     struct rb_node *rb_left;
 };
@@ -33,21 +31,7 @@ struct rb_root
     struct rb_node *rb_node;
 };
 
-#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
-#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_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
-#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
-
-static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
-{
-    rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
-}
-static inline void rb_set_color(struct rb_node *rb, int color)
-{
-    rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
-}
+#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
 
 #define RB_ROOT (struct rb_root) { NULL, }
 #define rb_entry(ptr, type, member) container_of(ptr, type, member)
@@ -55,9 +39,10 @@ static inline void rb_set_color(struct rb_node *rb, int color)
 #define RB_EMPTY_ROOT(root)  ((root)->rb_node == NULL)
 
 /* 'empty' nodes are nodes that are known not to be inserted in an rbree */
-#define RB_EMPTY_NODE(node)  ((node)->rb_parent_color == (unsigned long)(node))
-#define RB_CLEAR_NODE(node)  ((node)->rb_parent_color = (unsigned long)(node))
-
+#define RB_EMPTY_NODE(node)  \
+    ((node)->__rb_parent_color == (unsigned long)(node))
+#define RB_CLEAR_NODE(node)  \
+    ((node)->__rb_parent_color = (unsigned long)(node))
 
 extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
@@ -75,7 +60,7 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                                 struct rb_node ** rb_link)
 {
-    node->rb_parent_color = (unsigned long )parent;
+    node->__rb_parent_color = (unsigned long )parent;
     node->rb_left = node->rb_right = NULL;
 
     *rb_link = node;
-- 
2.12.0


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

[PATCH 06/17] rbtree: break out of rb_insert_color loop after tree rotation

[Praveen Kumar]

It is a well known property of rbtrees that insertion never requires more
than two tree rotations.  In our implementation, after one loop iteration
identified one or two necessary tree rotations, we would iterate and look
for more.  However at that point the node's parent would always be black,
which would cause us to exit the loop.

We can make the code flow more obvious by just adding a break statement
after the tree rotations, where we know we are done.  Additionally, in the
cases where two tree rotations are necessary, we don't have to update the
'node' pointer as it wouldn't be used until the next loop iteration, which
we now avoid due to this break statement.

commit 1f0528653e41ec230c60f5738820e8a544731399 from linux tree

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 6 ------
 1 file changed, 6 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 1d48ac7c78..bead370436 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -110,11 +110,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 
             if (parent->rb_right == node)
             {
-                register struct rb_node *tmp;
                 __rb_rotate_left(parent, root);
-                tmp = parent;
                 parent = node;
-                node = tmp;
             }
 
             rb_set_black(parent);
@@ -135,11 +132,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 
             if (parent->rb_left == node)
             {
-                register struct rb_node *tmp;
                 __rb_rotate_right(parent, root);
-                tmp = parent;
                 parent = node;
-                node = tmp;
             }
 
             rb_set_black(parent);
-- 
2.12.0


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

[PATCH 07/17] rbtree: adjust root color in rb_insert_color() only when necessary

[Praveen Kumar]

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@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 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 *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 *root)
             __rb_rotate_left(gparent, root);
         }
     }
-
-    rb_set_black(root->rb_node);
 }
 EXPORT_SYMBOL(rb_insert_color);
 
-- 
2.12.0


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

[PATCH 08/17] rbtree: low level optimizations in rb_insert_color()

[Praveen Kumar]

- Use the newly introduced rb_set_parent_color() function to flip the color
  of nodes whose parent is already known.
- Optimize rb_parent() when the node is known to be red - there is no need
  to mask out the color in that case.
- Flipping gparent's color to red requires us to fetch its rb_parent_color
  field, so we can reuse it as the parent value for the next loop iteration.
- Do not use __rb_rotate_left() and __rb_rotate_right() to handle tree
  rotations: we already have pointers to all relevant nodes, and know their
  colors (either because we want to adjust it, or because we've tested it,
  or we can deduce it as black due to the node proximity to a known red node).
  So we can generate more efficient code by making use of the node pointers
  we already have, and setting both the parent and color attributes for
  nodes all at once. Also in Case 2, some node attributes don't have to
  be set because we know another tree rotation (Case 3) will always follow
  and override them.

commit 5bc9188aa207dafd47eab57df7c4fe5b3d3f636a from linux tree

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 160 ++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 129 insertions(+), 31 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index ccf905e35c..8db7a5b4ca 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -22,6 +22,25 @@
 #include <xen/types.h>
 #include <xen/rbtree.h>
 
+/*
+ * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree
+ *
+ *  1) A node is either red or black
+ *  2) The root is black
+ *  3) All leaves (NULL) are black
+ *  4) Both children of every red node are black
+ *  5) Every simple path from root to leaves contains the same number
+ *     of black nodes.
+ *
+ *  4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
+ *  consecutive red nodes in a path and every red node is therefore followed by
+ *  a black. So if B is the number of black nodes on every simple path (as per
+ *  5), then the longest possible path due to 4 is 2B.
+ *
+ *  We shall indicate color with case, where black nodes are uppercase and red
+ *  nodes will be lowercase.
+ */
+
 #define    RB_RED    0
 #define    RB_BLACK  1
 
@@ -40,6 +59,17 @@ static inline void rb_set_color(struct rb_node *rb, int color)
     rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color;
 }
 
+static inline void rb_set_parent_color(struct rb_node *rb,
+                                      struct rb_node *p, int color)
+{
+    rb->__rb_parent_color = (unsigned long)p | color;
+}
+
+static inline struct rb_node *rb_red_parent(struct rb_node *red)
+{
+    return (struct rb_node *)red->__rb_parent_color;
+}
+
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
     struct rb_node *right = node->rb_right;
@@ -86,9 +116,30 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
     rb_set_parent(node, left);
 }
 
+/*
+ * Helper function for rotations:
+ * - old's parent and color get assigned to new
+ * - old gets assigned new as a parent and 'color' as a color.
+ */
+static inline void
+__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
+                        struct rb_root *root, int color)
+{
+    struct rb_node *parent = rb_parent(old);
+    new->__rb_parent_color = old->__rb_parent_color;
+    rb_set_parent_color(old, new, color);
+    if (parent) {
+        if (parent->rb_left == old)
+            parent->rb_left = new;
+        else
+            parent->rb_right = new;
+    } else
+        root->rb_node = new;
+}
+
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
-    struct rb_node *parent, *gparent;
+    struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
 
     while (true)
     {
@@ -99,61 +150,108 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
          * 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);
+            rb_set_parent_color(node, NULL, RB_BLACK);
             break;
         } else if (rb_is_black(parent))
             break;
 
-        gparent = rb_parent(parent);
+        gparent = rb_red_parent(parent);
 
         if (parent == gparent->rb_left)
         {
+            tmp = gparent->rb_right;
+            if (tmp && rb_is_red(tmp))
             {
-                register struct rb_node *uncle = gparent->rb_right;
-                if (uncle && rb_is_red(uncle))
-                {
-                    rb_set_black(uncle);
-                    rb_set_black(parent);
-                    rb_set_red(gparent);
-                    node = gparent;
-                    continue;
-                }
+                /*
+                 * Case 1 - color flips
+                 *
+                 *       G            g
+                 *      / \          / \
+                 *     p   u  -->   P   U
+                 *    /            /
+                 *   n            N
+                 *
+                 * However, since g's parent might be red, and
+                 * 4) does not allow this, we need to recurse
+                 * at g.
+                 */
+                rb_set_parent_color(tmp, gparent, RB_BLACK);
+                rb_set_parent_color(parent, gparent, RB_BLACK);
+                node = gparent;
+                parent = rb_parent(node);
+                rb_set_parent_color(node, parent, RB_RED);
+                continue;
             }
 
             if (parent->rb_right == node)
             {
-                __rb_rotate_left(parent, root);
+                /*
+                 * Case 2 - left rotate at parent
+                 *
+                 *      G             G
+                 *     / \           / \
+                 *    p   U  -->    n   U
+                 *     \           /
+                 *      n         p
+                 *
+                 * This still leaves us in violation of 4), the
+                 * continuation into Case 3 will fix that.
+                 */
+                parent->rb_right = tmp = node->rb_left;
+                node->rb_left = parent;
+                if (tmp)
+                    rb_set_parent_color(tmp, parent, RB_BLACK);
+                rb_set_parent_color(parent, node, RB_RED);
                 parent = node;
             }
-
-            rb_set_black(parent);
-            rb_set_red(gparent);
-            __rb_rotate_right(gparent, root);
+            /*
+             * Case 3 - right rotate at gparent
+             *
+             *        G           P
+             *       / \         / \
+             *      p   U  -->  n   g
+             *     /                 \
+             *    n                   U
+             */
+            gparent->rb_left = tmp = parent->rb_right;
+            parent->rb_right = gparent;
+            if (tmp)
+                rb_set_parent_color(tmp, gparent, RB_BLACK);
+            __rb_rotate_set_parents(gparent, parent, root, RB_RED);
+            break;
         } else {
+            tmp = gparent->rb_left;
+            if (tmp && rb_is_red(tmp))
             {
-                register struct rb_node *uncle = gparent->rb_left;
-                if (uncle && rb_is_red(uncle))
-                {
-                    rb_set_black(uncle);
-                    rb_set_black(parent);
-                    rb_set_red(gparent);
-                    node = gparent;
-                    continue;
-                }
+                /* Case 1 - color flips */
+                rb_set_parent_color(tmp, gparent, RB_BLACK);
+                rb_set_parent_color(parent, gparent, RB_BLACK);
+                node = gparent;
+                parent = rb_parent(node);
+                rb_set_parent_color(node, parent, RB_RED);
+                continue;
             }
 
             if (parent->rb_left == node)
             {
-                __rb_rotate_right(parent, root);
+                /* Case 2 - right rotate at parent */
+                parent->rb_left = tmp = node->rb_right;
+                node->rb_right = parent;
+                if (tmp)
+                    rb_set_parent_color(tmp, parent, RB_BLACK);
+                rb_set_parent_color(parent, node, RB_RED);
                 parent = node;
             }
 
-            rb_set_black(parent);
-            rb_set_red(gparent);
-            __rb_rotate_left(gparent, root);
+            /* Case 3 - left rotate at gparent */
+            gparent->rb_right = tmp = parent->rb_left;
+            parent->rb_left = gparent;
+            if (tmp)
+                rb_set_parent_color(tmp, gparent, RB_BLACK);
+            __rb_rotate_set_parents(gparent, parent, root, RB_RED);
+            break;
         }
     }
 }
-- 
2.12.0


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

[PATCH 09/17] rbtree: adjust node color in __rb_erase_color() only when necessary

[Praveen Kumar]

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.

commit d6ff1273928ebf15466a85b7e1810cd00e72998b from linux tree

[adrian.hunter@intel.com: perf tools: fix build for another rbtree.c change]
Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Adrian Hunter <adrian.hunter@intel.com>
Cc: Alexander Shishkin <alexander.shishkin@intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 22 ++++++++++++++++------
 1 file changed, 16 insertions(+), 6 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 8db7a5b4ca..736e2a55aa 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -262,10 +262,24 @@ 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)
+    while (true)
     {
-        if (parent->rb_left == node)
+        /*
+         * 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))
             {
@@ -297,7 +311,6 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                 if (other->rb_right)
                     rb_set_black(other->rb_right);
                 __rb_rotate_left(parent, root);
-                node = root->rb_node;
                 break;
             }
         }
@@ -334,13 +347,10 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                 if (other->rb_left)
                     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)
-- 
2.12.0


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

[PATCH 10/17] rbtree: optimize case selection logic in __rb_erase_color()

[Praveen Kumar]

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.

commit e125d1471a4f8f1bf7ea9a83deb8d23cb40bd712 from linux tree

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 69 ++++++++++++++++++++++-------------------------------
 1 file changed, 29 insertions(+), 40 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 736e2a55aa..1e4cb1ed2c 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -288,31 +288,26 @@ 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)))
+            if (!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))
+                if (!other->rb_left || rb_is_black(other->rb_left))
                 {
-                    struct rb_node *o_left;
-                    if ((o_left = other->rb_left))
-                        rb_set_black(o_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);
-                if (other->rb_right)
-                    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
         {
@@ -324,31 +319,25 @@ 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)))
+            if (!other->rb_left || rb_is_black(other->rb_left))
             {
-                rb_set_red(other);
-                node = parent;
-                parent = rb_parent(node);
-            }
-            else
-            {
-                if (!other->rb_left || rb_is_black(other->rb_left))
+                if (!other->rb_right || rb_is_black(other->rb_right))
                 {
-                    register struct rb_node *o_right;
-                    if ((o_right = other->rb_right))
-                        rb_set_black(o_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);
-                if (other->rb_left)
-                    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;
         }
     }
 }
-- 
2.12.0


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

[PATCH 11/17] rbtree: low level optimizations in __rb_erase_color()

[Praveen Kumar]

In __rb_erase_color(), we often already have pointers to the nodes being
rotated and/or know what their colors must be, so we can generate more
efficient code than the generic __rb_rotate_left() and __rb_rotate_right()
functions.

Also when the current node is red or when flipping the sibling's color,
the parent is already known so we can use the more efficient
rb_set_parent_color() function to set the desired color.

commit 6280d2356fd8ad0936a63c10dc1e6accf48d0c61 from linux tree

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 197 ++++++++++++++++++++++++++++------------------------
 1 file changed, 107 insertions(+), 90 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 1e4cb1ed2c..253861d889 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -38,7 +38,8 @@
  *  5), then the longest possible path due to 4 is 2B.
  *
  *  We shall indicate color with case, where black nodes are uppercase and red
- *  nodes will be lowercase.
+ *  nodes will be lowercase. Unknown color nodes shall be drawn as red within
+ *  parentheses and have some accompanying text comment.
  */
 
 #define    RB_RED    0
@@ -47,17 +48,11 @@
 #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_set_red(r)   do { (r)->__rb_parent_color &= ~1; } while (0)
-#define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0)
 
 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
 {
     rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
 }
-static inline void rb_set_color(struct rb_node *rb, int color)
-{
-    rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color;
-}
 
 static inline void rb_set_parent_color(struct rb_node *rb,
                                       struct rb_node *p, int color)
@@ -70,52 +65,6 @@ static inline struct rb_node *rb_red_parent(struct rb_node *red)
     return (struct rb_node *)red->__rb_parent_color;
 }
 
-static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
-{
-    struct rb_node *right = node->rb_right;
-    struct rb_node *parent = rb_parent(node);
-
-    if ((node->rb_right = right->rb_left))
-        rb_set_parent(right->rb_left, node);
-    right->rb_left = node;
-
-    rb_set_parent(right, parent);
-
-    if (parent)
-    {
-        if (node == parent->rb_left)
-            parent->rb_left = right;
-        else
-            parent->rb_right = right;
-    }
-    else
-        root->rb_node = right;
-    rb_set_parent(node, right);
-}
-
-static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
-{
-    struct rb_node *left = node->rb_left;
-    struct rb_node *parent = rb_parent(node);
-
-    if ((node->rb_left = left->rb_right))
-        rb_set_parent(left->rb_right, node);
-    left->rb_right = node;
-
-    rb_set_parent(left, parent);
-
-    if (parent)
-    {
-        if (node == parent->rb_right)
-            parent->rb_right = left;
-        else
-            parent->rb_left = left;
-    }
-    else
-        root->rb_node = left;
-    rb_set_parent(node, left);
-}
-
 /*
  * Helper function for rotations:
  * - old's parent and color get assigned to new
@@ -260,7 +209,7 @@ EXPORT_SYMBOL(rb_insert_color);
 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                              struct rb_root *root)
 {
-    struct rb_node *other;
+    struct rb_node *sibling, *tmp1, *tmp2;
 
     while (true)
     {
@@ -275,68 +224,136 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
          */
         if (node && rb_is_red(node))
         {
-            rb_set_black(node);
+            rb_set_parent_color(node, parent, RB_BLACK);
             break;
         } else if (!parent) {
             break;
         } else if (parent->rb_left == node) {
-            other = parent->rb_right;
-            if (rb_is_red(other))
-            {
-                rb_set_black(other);
-                rb_set_red(parent);
-                __rb_rotate_left(parent, root);
-                other = parent->rb_right;
+            sibling = parent->rb_right;
+            if (rb_is_red(sibling)) {
+                /*
+                 * Case 1 - left rotate at parent
+                 *
+                 *     P               S
+                 *    / \             / \
+                 *   N   s    -->    p   Sr
+                 *      / \         / \
+                 *     Sl  Sr      N   Sl
+                 */
+                parent->rb_right = tmp1 = sibling->rb_left;
+                sibling->rb_left = parent;
+                rb_set_parent_color(tmp1, parent, RB_BLACK);
+                __rb_rotate_set_parents(parent, sibling, root, RB_RED);
+                sibling = tmp1;
             }
-            if (!other->rb_right || rb_is_black(other->rb_right))
+            tmp1 = sibling->rb_right;
+            if (!tmp1 || rb_is_black(tmp1))
             {
-                if (!other->rb_left || rb_is_black(other->rb_left))
+                tmp2 = sibling->rb_left;
+                if (!tmp2 || rb_is_black(tmp2))
                 {
-                    rb_set_red(other);
+                    /*
+                     * Case 2 - sibling color flip
+                     * (p could be either color here)
+                     *
+                     *    (p)           (p)
+                     *    / \           / \
+                     *   N   S    -->  N   s
+                     *      / \           / \
+                     *     Sl  Sr        Sl  Sr
+                     *
+                     * This leaves us violating 5), so
+                     * recurse at p. If p is red, the
+                     * recursion will just flip it to black
+                     * and exit. If coming from Case 1,
+                     * p is known to be red.
+                     */
+                    rb_set_parent_color(sibling, parent, RB_RED);
                     node = parent;
                     parent = rb_parent(node);
                     continue;
 
                 }
-                rb_set_black(other->rb_left);
-                rb_set_red(other);
-                __rb_rotate_right(other, root);
-                other = parent->rb_right;
+                /*
+                 * Case 3 - right rotate at sibling
+                 * (p could be either color here)
+                 *
+                 *   (p)           (p)
+                 *   / \           / \
+                 *  N   S    -->  N   Sl
+                 *     / \             \
+                 *    sl  Sr            s
+                 *                       \
+                 *                        Sr
+                 */
+                sibling->rb_left = tmp1 = tmp2->rb_right;
+                tmp2->rb_right = sibling;
+                parent->rb_right = tmp2;
+                if (tmp1)
+                    rb_set_parent_color(tmp1, sibling, RB_BLACK);
+                tmp1 = sibling;
+                sibling = tmp2;
             }
-            rb_set_color(other, rb_color(parent));
-            rb_set_black(parent);
-            rb_set_black(other->rb_right);
-            __rb_rotate_left(parent, root);
+            /*
+             * Case 4 - left rotate at parent + color flips
+             * (p and sl could be either color here.
+             *  After rotation, p becomes black, s acquires
+             *  p's color, and sl keeps its color)
+             *
+             *      (p)             (s)
+             *      / \             / \
+             *     N   S     -->   P   Sr
+             *        / \         / \
+             *      (sl) sr      N  (sl)
+             */
+            parent->rb_right = tmp2 = sibling->rb_left;
+            sibling->rb_left = parent;
+            rb_set_parent_color(tmp1, sibling, RB_BLACK);
+            if (tmp2)
+                rb_set_parent(tmp2, parent);
+            __rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
             break;
         }
         else
         {
-            other = parent->rb_left;
-            if (rb_is_red(other))
+            sibling = parent->rb_left;
+            if (rb_is_red(sibling))
             {
-                rb_set_black(other);
-                rb_set_red(parent);
-                __rb_rotate_right(parent, root);
-                other = parent->rb_left;
+                /* Case 1 - right rotate at parent */
+                parent->rb_left = tmp1 = sibling->rb_right;
+                sibling->rb_right = parent;
+                rb_set_parent_color(tmp1, parent, RB_BLACK);
+                __rb_rotate_set_parents(parent, sibling, root, RB_RED);
+                sibling = tmp1;
             }
-            if (!other->rb_left || rb_is_black(other->rb_left))
+            tmp1 = sibling->rb_left;
+            if (!tmp1 || rb_is_black(tmp1))
             {
-                if (!other->rb_right || rb_is_black(other->rb_right))
+                tmp2 = sibling->rb_right;
+                if (!tmp2 || rb_is_black(tmp2))
                 {
-                    rb_set_red(other);
+                    /* Case 2 - sibling color flip */
+                    rb_set_parent_color(sibling, parent, RB_RED);
                     node = parent;
                     parent = rb_parent(node);
                     continue;
                 }
-                rb_set_black(other->rb_right);
-                rb_set_red(other);
-                __rb_rotate_left(other, root);
-                other = parent->rb_left;
+                /* Case 3 - right rotate at sibling */
+                sibling->rb_right = tmp1 = tmp2->rb_left;
+                tmp2->rb_left = sibling;
+                parent->rb_left = tmp2;
+                if (tmp1)
+                    rb_set_parent_color(tmp1, sibling, RB_BLACK);
+                tmp1 = sibling;
+                sibling = tmp2;
             }
-            rb_set_color(other, rb_color(parent));
-            rb_set_black(parent);
-            rb_set_black(other->rb_left);
-            __rb_rotate_right(parent, root);
+            /* Case 4 - left rotate at parent + color flips */
+            parent->rb_left = tmp2 = sibling->rb_right;
+            sibling->rb_right = parent;
+            rb_set_parent_color(tmp1, sibling, RB_BLACK);
+            if (tmp2)
+                rb_set_parent(tmp2, parent);
+            __rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
             break;
         }
     }
-- 
2.12.0


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

[PATCH 12/17] rbtree: optimize fetching of sibling node

[Praveen Kumar]

When looking to fetch a node's sibling, we went through a sequence of:
- check if node is the parent's left child
- if it is, then fetch the parent's right child

This can be replaced with:
- fetch the parent's right child as an assumed sibling
- check that node is NOT the fetched child

This avoids fetching the parent's left child when node is actually
that child. Saves a bit on code size, though it doesn't seem to make
a large difference in speed.

commit 59633abf34e2f44b8e772a2c12a92132aa7c2220 from Linux tree

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <David.Woodhouse@intel.com>
Acked-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 21 +++++++++++++--------
 1 file changed, 13 insertions(+), 8 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 253861d889..b65f00ca1f 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -108,9 +108,9 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 
         gparent = rb_red_parent(parent);
 
-        if (parent == gparent->rb_left)
+        tmp = gparent->rb_right;
+        if (parent != tmp)    /* parent == gparent->rb_left */
         {
-            tmp = gparent->rb_right;
             if (tmp && rb_is_red(tmp))
             {
                 /*
@@ -134,7 +134,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
                 continue;
             }
 
-            if (parent->rb_right == node)
+            tmp = parent->rb_right;
+            if (node == tmp)
             {
                 /*
                  * Case 2 - left rotate at parent
@@ -164,7 +165,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
              *     /                 \
              *    n                   U
              */
-            gparent->rb_left = tmp = parent->rb_right;
+            gparent->rb_left = tmp;    /* == parent->rb_right */
             parent->rb_right = gparent;
             if (tmp)
                 rb_set_parent_color(tmp, gparent, RB_BLACK);
@@ -183,7 +184,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
                 continue;
             }
 
-            if (parent->rb_left == node)
+            tmp = parent->rb_left;
+            if (node == tmp)
             {
                 /* Case 2 - right rotate at parent */
                 parent->rb_left = tmp = node->rb_right;
@@ -192,10 +194,11 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
                     rb_set_parent_color(tmp, parent, RB_BLACK);
                 rb_set_parent_color(parent, node, RB_RED);
                 parent = node;
+                tmp = node->rb_left;
             }
 
             /* Case 3 - left rotate at gparent */
-            gparent->rb_right = tmp = parent->rb_left;
+            gparent->rb_right = tmp;    /* == parent->rb_left */
             parent->rb_left = gparent;
             if (tmp)
                 rb_set_parent_color(tmp, gparent, RB_BLACK);
@@ -228,8 +231,10 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
             break;
         } else if (!parent) {
             break;
-        } else if (parent->rb_left == node) {
-            sibling = parent->rb_right;
+        }
+        sibling = parent->rb_right;
+        if ( node != sibling)    /* node == parent->rb_left */
+        {
             if (rb_is_red(sibling)) {
                 /*
                  * Case 1 - left rotate at parent
-- 
2.12.0


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

[PATCH 13/17] rbtree: add __rb_change_child() helper function

[Praveen Kumar]

Add __rb_change_child() as an inline helper function to replace code that
would otherwise be duplicated 4 times in the source.

No changes to binary size or speed.

commit 7abc704ae399fcb9c51ca200b0456f8a975a8011 from Linux tree

Signed-off-by: Michel Lespinasse <walken@google.com>
Reviewed-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 54 ++++++++++++++++++++++-------------------------------
 1 file changed, 22 insertions(+), 32 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index b65f00ca1f..3b54c04bea 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -65,6 +65,22 @@ static inline struct rb_node *rb_red_parent(struct rb_node *red)
     return (struct rb_node *)red->__rb_parent_color;
 }
 
+static inline void
+__rb_change_child(struct rb_node *old, struct rb_node *new,
+                 struct rb_node *parent, struct rb_root *root)
+{
+    if (parent)
+    {
+        if (parent->rb_left == old)
+            parent->rb_left = new;
+        else
+            parent->rb_right = new;
+    } else
+        root->rb_node = new;
+}
+
+
+
 /*
  * Helper function for rotations:
  * - old's parent and color get assigned to new
@@ -77,13 +93,7 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
     struct rb_node *parent = rb_parent(old);
     new->__rb_parent_color = old->__rb_parent_color;
     rb_set_parent_color(old, new, color);
-    if (parent) {
-        if (parent->rb_left == old)
-            parent->rb_left = new;
-        else
-            parent->rb_right = new;
-    } else
-        root->rb_node = new;
+    __rb_change_child(old, new, parent, root);
 }
 
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
@@ -381,14 +391,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         while ((left = node->rb_left) != NULL)
             node = left;
 
-        if (rb_parent(old))
-        {
-            if (rb_parent(old)->rb_left == old)
-                rb_parent(old)->rb_left = node;
-            else
-                rb_parent(old)->rb_right = node;
-        } else
-            root->rb_node = node;
+        __rb_change_child(old, node, rb_parent(old), root);
 
         child = node->rb_right;
         parent = rb_parent(node);
@@ -418,15 +421,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 
     if (child)
         rb_set_parent(child, parent);
-    if (parent)
-    {
-        if (parent->rb_left == node)
-            parent->rb_left = child;
-        else
-            parent->rb_right = child;
-    }
-    else
-        root->rb_node = child;
+
+    __rb_change_child(node, child, parent, root);
 
  color:
     if (color == RB_BLACK)
@@ -523,14 +519,8 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
     struct rb_node *parent = rb_parent(victim);
 
     /* Set the surrounding nodes to point to the replacement */
-    if (parent) {
-        if (victim == parent->rb_left)
-            parent->rb_left = new;
-        else
-            parent->rb_right = new;
-    } else {
-        root->rb_node = new;
-    }
+    __rb_change_child(victim, new, parent, root);
+
     if (victim->rb_left)
         rb_set_parent(victim->rb_left, new);
     if (victim->rb_right)
-- 
2.12.0


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

[PATCH 14/17] rbtree: place easiest case first in rb_erase()

[Praveen Kumar]

In rb_erase, move the easy case (node to erase has no more than
1 child) first. I feel the code reads easier that way.

commit 60670b8034d6e2ba860af79c9379b7788d09db73 from Linux tree

Signed-off-by: Michel Lespinasse <walken@google.com>
Reviewed-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 36 ++++++++++++++++++------------------
 1 file changed, 18 insertions(+), 18 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 3b54c04bea..69c7496c65 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -376,18 +376,29 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 
 void rb_erase(struct rb_node *node, struct rb_root *root)
 {
-    struct rb_node *child, *parent;
+    struct rb_node *child = node->rb_right, *tmp = node->rb_left;
+    struct rb_node *parent;
     int color;
 
-    if (!node->rb_left)
-        child = node->rb_right;
-    else if (!node->rb_right)
-        child = node->rb_left;
-    else
+    if (!tmp)
     {
+    case1:
+        /* Case 1: node to erase has no more than 1 child (easy!) */
+
+        parent = rb_parent(node);
+        color = rb_color(node);
+
+        if (child)
+            rb_set_parent(child, parent);
+        __rb_change_child(node, child, parent, root);
+    } else if (!child) {
+        /* Still case 1, but this time the child is node->rb_left */
+        child = tmp;
+        goto case1;
+    } else {
         struct rb_node *old = node, *left;
 
-        node = node->rb_right;
+        node = child;
         while ((left = node->rb_left) != NULL)
             node = left;
 
@@ -412,19 +423,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         node->rb_left = old->rb_left;
 
         rb_set_parent(old->rb_left, node);
-
-        goto color;
     }
 
-    parent = rb_parent(node);
-    color = rb_color(node);
-
-    if (child)
-        rb_set_parent(child, parent);
-
-    __rb_change_child(node, child, parent, root);
-
- color:
     if (color == RB_BLACK)
         __rb_erase_color(child, parent, root);
 }
-- 
2.12.0


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

[PATCH 15/17] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()

[Praveen Kumar]

An interesting observation for rb_erase() is that when a node has
exactly one child, the node must be black and the child must be red.
An interesting consequence is that removing such a node can be done by
simply replacing it with its child and making the child black,
which we can do efficiently in rb_erase(). __rb_erase_color() then
only needs to handle the no-childs case and can be modified accordingly.

commit 46b6135a7402ac23c5b25f2bd79b03bab8f98278 from Linux tree

Signed-off-by: Michel Lespinasse <walken@google.com>
Acked-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 xen/common/rbtree.c | 110 +++++++++++++++++++++++++++++++---------------------
 1 file changed, 66 insertions(+), 44 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 69c7496c65..6e37e960ab 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -2,6 +2,7 @@
   Red Black Trees
   (C) 1999  Andrea Arcangeli <andrea@suse.de>
   (C) 2002  David Woodhouse <dwmw2@infradead.org>
+  (C) 2012  Michel Lespinasse <walken@google.com>
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
@@ -49,6 +50,12 @@
 #define rb_is_red(r)    (!rb_color(r))
 #define rb_is_black(r)  rb_color(r)
 
+static inline void rb_set_black(struct rb_node *rb)
+{
+    rb->__rb_parent_color |= RB_BLACK;
+}
+
+
 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
 {
     rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
@@ -219,29 +226,19 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 }
 EXPORT_SYMBOL(rb_insert_color);
 
-static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
-                             struct rb_root *root)
+static void __rb_erase_color(struct rb_node *parent, struct rb_root *root)
 {
-    struct rb_node *sibling, *tmp1, *tmp2;
+    struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
 
     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.
+         * Loop invariants:
+         * - node is black (or NULL on first iteration)
+         * - node is not the root (parent is not NULL)
+         * - All leaf paths going through parent and node have a
+         *   black node count that is 1 lower than other leaf paths.
          */
-        if (node && rb_is_red(node))
-        {
-            rb_set_parent_color(node, parent, RB_BLACK);
-            break;
-        } else if (!parent) {
-            break;
-        }
         sibling = parent->rb_right;
         if ( node != sibling)    /* node == parent->rb_left */
         {
@@ -277,17 +274,22 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                      *      / \           / \
                      *     Sl  Sr        Sl  Sr
                      *
-                     * This leaves us violating 5), so
-                     * recurse at p. If p is red, the
-                     * recursion will just flip it to black
-                     * and exit. If coming from Case 1,
-                     * p is known to be red.
+                     * This leaves us violating 5) which
+                     * can be fixed by flipping p to black
+                     * if it was red, or by recursing at p.
+                     * p is red when coming from Case 1.
                      */
                     rb_set_parent_color(sibling, parent, RB_RED);
-                    node = parent;
-                    parent = rb_parent(node);
-                    continue;
-
+                    if (rb_is_red(parent))
+                        rb_set_black(parent);
+                    else
+                    {
+                        node = parent;
+                        parent = rb_parent(node);
+                        if (parent)
+                            continue;
+                    }
+                    break;
                 }
                 /*
                  * Case 3 - right rotate at sibling
@@ -349,9 +351,16 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                 {
                     /* Case 2 - sibling color flip */
                     rb_set_parent_color(sibling, parent, RB_RED);
-                    node = parent;
-                    parent = rb_parent(node);
-                    continue;
+                    if (rb_is_red(parent))
+                        rb_set_black(parent);
+                    else
+                    {
+                        node = parent;
+                        parent = rb_parent(node);
+                        if (parent)
+                            continue;
+                    }
+                    break;
                 }
                 /* Case 3 - right rotate at sibling */
                 sibling->rb_right = tmp1 = tmp2->rb_left;
@@ -377,24 +386,33 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 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;
-    int color;
+    struct rb_node *parent, *rebalance;
 
     if (!tmp)
     {
-    case1:
-        /* Case 1: node to erase has no more than 1 child (easy!) */
+        /*
+         * Case 1: node to erase has no more than 1 child (easy!)
+         *
+         * Note that if there is one child it must be red due to 5)
+         * 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);
-        color = rb_color(node);
-
-        if (child)
-            rb_set_parent(child, parent);
         __rb_change_child(node, child, parent, root);
+        if (child)
+        {
+            rb_set_parent_color(child, parent, RB_BLACK);
+            rebalance = NULL;
+        } else {
+            rebalance = rb_is_black(node) ? parent : NULL;
+        }
     } else if (!child) {
         /* Still case 1, but this time the child is node->rb_left */
-        child = tmp;
-        goto case1;
+        parent = rb_parent(node);
+        __rb_change_child(node, tmp, parent, root);
+        rb_set_parent_color(tmp, parent, RB_BLACK);
+        rebalance = NULL;
     } else {
         struct rb_node *old = node, *left;
 
@@ -406,27 +424,31 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 
         child = node->rb_right;
         parent = rb_parent(node);
-        color = rb_color(node);
 
         if (parent == old) {
             parent = node;
         } else {
-            if (child)
-                rb_set_parent(child, parent);
             parent->rb_left = child;
 
             node->rb_right = old->rb_right;
             rb_set_parent(old->rb_right, node);
         }
 
+        if (child) {
+            rb_set_parent_color(child, parent, RB_BLACK);
+            rebalance = NULL;
+        } else {
+            rebalance = rb_is_black(node) ? parent : NULL;
+        }
+
         node->__rb_parent_color = old->__rb_parent_color;
         node->rb_left = old->rb_left;
 
         rb_set_parent(old->rb_left, node);
     }
 
-    if (color == RB_BLACK)
-        __rb_erase_color(child, parent, root);
+    if (rebalance)
+        __rb_erase_color(rebalance, root);
 }
 EXPORT_SYMBOL(rb_erase);
 
-- 
2.12.0


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

Re: [PATCH 15/17] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()

[Praveen Kumar]

[-- Attachment #1.1: Type: text/plain, Size: 8722 bytes --]

Hi All,

Sorry, I mistakenly sent the patch to Linux kernel developers. Please
ignore the series of patch sent by me.

Will be re-sending the updated patch to respective maintainers.

Sorry once again for spamming your mailbox.

Regards,

~Praveen.


On Thu, Jun 1, 2017 at 2:17 AM, Praveen Kumar <kpraveen.lkml@gmail.com>
wrote:

> An interesting observation for rb_erase() is that when a node has
> exactly one child, the node must be black and the child must be red.
> An interesting consequence is that removing such a node can be done by
> simply replacing it with its child and making the child black,
> which we can do efficiently in rb_erase(). __rb_erase_color() then
> only needs to handle the no-childs case and can be modified accordingly.
>
> commit 46b6135a7402ac23c5b25f2bd79b03bab8f98278 from Linux tree
>
> Signed-off-by: Michel Lespinasse <walken@google.com>
> Acked-by: Rik van Riel <riel@redhat.com>
> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Cc: Andrea Arcangeli <aarcange@redhat.com>
> Cc: David Woodhouse <dwmw2@infradead.org>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> ---
>  xen/common/rbtree.c | 110 ++++++++++++++++++++++++++++++
> +---------------------
>  1 file changed, 66 insertions(+), 44 deletions(-)
>
> diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
> index 69c7496c65..6e37e960ab 100644
> --- a/xen/common/rbtree.c
> +++ b/xen/common/rbtree.c
> @@ -2,6 +2,7 @@
>    Red Black Trees
>    (C) 1999  Andrea Arcangeli <andrea@suse.de>
>    (C) 2002  David Woodhouse <dwmw2@infradead.org>
> +  (C) 2012  Michel Lespinasse <walken@google.com>
>
>    This program is free software; you can redistribute it and/or modify
>    it under the terms of the GNU General Public License as published by
> @@ -49,6 +50,12 @@
>  #define rb_is_red(r)    (!rb_color(r))
>  #define rb_is_black(r)  rb_color(r)
>
> +static inline void rb_set_black(struct rb_node *rb)
> +{
> +    rb->__rb_parent_color |= RB_BLACK;
> +}
> +
> +
>  static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
>  {
>      rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
> @@ -219,29 +226,19 @@ void rb_insert_color(struct rb_node *node, struct
> rb_root *root)
>  }
>  EXPORT_SYMBOL(rb_insert_color);
>
> -static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
> -                             struct rb_root *root)
> +static void __rb_erase_color(struct rb_node *parent, struct rb_root *root)
>  {
> -    struct rb_node *sibling, *tmp1, *tmp2;
> +    struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
>
>      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.
> +         * Loop invariants:
> +         * - node is black (or NULL on first iteration)
> +         * - node is not the root (parent is not NULL)
> +         * - All leaf paths going through parent and node have a
> +         *   black node count that is 1 lower than other leaf paths.
>           */
> -        if (node && rb_is_red(node))
> -        {
> -            rb_set_parent_color(node, parent, RB_BLACK);
> -            break;
> -        } else if (!parent) {
> -            break;
> -        }
>          sibling = parent->rb_right;
>          if ( node != sibling)    /* node == parent->rb_left */
>          {
> @@ -277,17 +274,22 @@ static void __rb_erase_color(struct rb_node *node,
> struct rb_node *parent,
>                       *      / \           / \
>                       *     Sl  Sr        Sl  Sr
>                       *
> -                     * This leaves us violating 5), so
> -                     * recurse at p. If p is red, the
> -                     * recursion will just flip it to black
> -                     * and exit. If coming from Case 1,
> -                     * p is known to be red.
> +                     * This leaves us violating 5) which
> +                     * can be fixed by flipping p to black
> +                     * if it was red, or by recursing at p.
> +                     * p is red when coming from Case 1.
>                       */
>                      rb_set_parent_color(sibling, parent, RB_RED);
> -                    node = parent;
> -                    parent = rb_parent(node);
> -                    continue;
> -
> +                    if (rb_is_red(parent))
> +                        rb_set_black(parent);
> +                    else
> +                    {
> +                        node = parent;
> +                        parent = rb_parent(node);
> +                        if (parent)
> +                            continue;
> +                    }
> +                    break;
>                  }
>                  /*
>                   * Case 3 - right rotate at sibling
> @@ -349,9 +351,16 @@ static void __rb_erase_color(struct rb_node *node,
> struct rb_node *parent,
>                  {
>                      /* Case 2 - sibling color flip */
>                      rb_set_parent_color(sibling, parent, RB_RED);
> -                    node = parent;
> -                    parent = rb_parent(node);
> -                    continue;
> +                    if (rb_is_red(parent))
> +                        rb_set_black(parent);
> +                    else
> +                    {
> +                        node = parent;
> +                        parent = rb_parent(node);
> +                        if (parent)
> +                            continue;
> +                    }
> +                    break;
>                  }
>                  /* Case 3 - right rotate at sibling */
>                  sibling->rb_right = tmp1 = tmp2->rb_left;
> @@ -377,24 +386,33 @@ static void __rb_erase_color(struct rb_node *node,
> struct rb_node *parent,
>  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;
> -    int color;
> +    struct rb_node *parent, *rebalance;
>
>      if (!tmp)
>      {
> -    case1:
> -        /* Case 1: node to erase has no more than 1 child (easy!) */
> +        /*
> +         * Case 1: node to erase has no more than 1 child (easy!)
> +         *
> +         * Note that if there is one child it must be red due to 5)
> +         * 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);
> -        color = rb_color(node);
> -
> -        if (child)
> -            rb_set_parent(child, parent);
>          __rb_change_child(node, child, parent, root);
> +        if (child)
> +        {
> +            rb_set_parent_color(child, parent, RB_BLACK);
> +            rebalance = NULL;
> +        } else {
> +            rebalance = rb_is_black(node) ? parent : NULL;
> +        }
>      } else if (!child) {
>          /* Still case 1, but this time the child is node->rb_left */
> -        child = tmp;
> -        goto case1;
> +        parent = rb_parent(node);
> +        __rb_change_child(node, tmp, parent, root);
> +        rb_set_parent_color(tmp, parent, RB_BLACK);
> +        rebalance = NULL;
>      } else {
>          struct rb_node *old = node, *left;
>
> @@ -406,27 +424,31 @@ void rb_erase(struct rb_node *node, struct rb_root
> *root)
>
>          child = node->rb_right;
>          parent = rb_parent(node);
> -        color = rb_color(node);
>
>          if (parent == old) {
>              parent = node;
>          } else {
> -            if (child)
> -                rb_set_parent(child, parent);
>              parent->rb_left = child;
>
>              node->rb_right = old->rb_right;
>              rb_set_parent(old->rb_right, node);
>          }
>
> +        if (child) {
> +            rb_set_parent_color(child, parent, RB_BLACK);
> +            rebalance = NULL;
> +        } else {
> +            rebalance = rb_is_black(node) ? parent : NULL;
> +        }
> +
>          node->__rb_parent_color = old->__rb_parent_color;
>          node->rb_left = old->rb_left;
>
>          rb_set_parent(old->rb_left, node);
>      }
>
> -    if (color == RB_BLACK)
> -        __rb_erase_color(child, parent, root);
> +    if (rebalance)
> +        __rb_erase_color(rebalance, root);
>  }
>  EXPORT_SYMBOL(rb_erase);
>
> --
> 2.12.0
>
>

[-- Attachment #1.2: Type: text/html, Size: 11426 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

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