[Xen-devel] [PATCH v2 04/20] rb_tree: make clear distinction between two different cases in rb_erase()

[Praveen Kumar <kpraveen.lkml@xxxxxxxxx>]

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.

Signed-off-by: Wolfram Strepp <wstrepp@xxxxxx>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
[Linux commit 4c60117811171d867d4f27f17ea07d7419d45dae]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@xxxxxxxxx>
---
 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 4b85fd492b..90db00a5e8 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -244,13 +244,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@xxxxxxxxxxxxx
https://lists.xen.org/xen-devel