| Message ID | 20170617093253.3990-5-kpraveen.lkml@gmail.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote: > 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@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> > [Linux commit 4c60117811171d867d4f27f17ea07d7419d45dae] > > Ported to Xen. > > Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com> > Reviewed-by: Dario Faggioli <dario.faggioli@citrix.com> Regards, Dario
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;
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@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> [Linux commit 4c60117811171d867d4f27f17ea07d7419d45dae] Ported to Xen. Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com> --- xen/common/rbtree.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)