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

[Dario Faggioli <dario.faggioli@xxxxxxxxxx>]

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@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>
>
Reviewed-by: Dario Faggioli <dario.faggioli@xxxxxxxxxx>

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

Attachment: signature.asc
Description: This is a digitally signed message part

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