lkml.org 
[lkml]   [2012]   [Aug]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH v2 5/9] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()
On 08/02/2012 06:34 PM, Michel Lespinasse 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.
>
> Signed-off-by: Michel Lespinasse<walken@google.com>

Acked-by: Rik van Riel <riel@redhat.com>


--
All rights reversed


\
 
 \ /
  Last update: 2012-08-06 04:01    [W:1.425 / U:0.048 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site