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

[Sebastian Huber]

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