[PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD

[Corinna Vinschen]

On Oct 19 18:05, Sebastian Huber wrote:
> This patch set adds some changes after the last synchronization point with
> FreeBSD to Newlib.  In a simple benchmark, the node insert/extract performance
> improved.
> 
> In an intermediate step of this patch set the node color member is removed.
> Later it is restored.  I propose to keep the patch series as is to have the
> same change history as FreeBSD.
> 
> FreeBSD also changed the implementation to so that the node color is stored in
> the parent pointer in follow up patches.  In addition, they changed the
> algorithm from red-black to weak AVL.  These changes are NOT INCLUDED, since
> they break the ABI/API.  I did some rough benchmarking and was not immediately
> convinced that the new implementation in FreeBSD is better.
> 
> dougm (10):
>   Correct the use of RB_AUGMENT in the RB_TREE
>   For the case when RB_REMOVE requires a nontrivial
>   RB_REMOVE invokes RB_REMOVE_COLOR either when
>   Remove from RB_REMOVE_COLOR some null checks
>   To reduce the size of an rb_node, drop the color
>   Restore an RB_COLOR macro, for the benefit of
>   Fixup r361997 by balancing parens. Duh.
>   Linuxkpi uses the rb-tree structures
>   In concluding RB_REMOVE_COLOR, in the case when
>   Define RB_SET_PARENT to do all assignments
> 
> trasz (1):
>   Add RB_REINSERT(3), a low overhead alternative to
> 
>  newlib/libc/include/sys/tree.h | 273 ++++++++++++++++-----------------
>  1 file changed, 130 insertions(+), 143 deletions(-)
> 
> -- 
> 2.26.2

Please go ahead.


Thanks,
Corinna