Improved Red-black tree implementation

[Sebastian Huber]

Hello,

I use the BSD <sys/tree.h> for RTEMS with a shared extract and insert 
color implementation (this is similar to Linux):

https://git.rtems.org/rtems/tree/cpukit/score/include/rtems/score/rbtree.h#n206
https://git.rtems.org/rtems/tree/cpukit/score/src/rbtreeextract.c
https://git.rtems.org/rtems/tree/cpukit/score/src/rbtreeinsert.c

I did also some primitive benchmarking:

https://github.com/sebhub/rb-bench

It would be quite nice to have a <sys/tree.h> implementation which 
encodes the color in one of the pointers to save some memory.

-- 
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone   : +49 89 189 47 41-16
Fax     : +49 89 189 47 41-09
E-Mail  : sebastian.huber at embedded-brains.de
PGP     : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.