Improved Red-black tree implementation

[Jens Stimpfle]

On Fri, May 19, 2017 at 10:05:30AM +0200, Sebastian Huber wrote:
> 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

Thanks Sebastian, I had actually found you bench already and tested an
earlier version of my code. It did quite well on my machine, although I
would expect it to be faster than BSD ("SIL RB3"):

https://raw.githubusercontent.com/jstimpfle/rb-bench/31f111f9c7664d72d5f103bb46adcb28a1cea61a/reports/test-amdx2250.png

The second plot is broken maybe because my machine is too fast for the
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.

I have looked at your project and will send you email off-list. Just a
few points here:

Considering memory savings, have you considered 2-pointer trees (no
parent pointer)? They need a temporary search stack for insertion and
deletion, but not for iteration ("threaded trees").

The RTEMS red-black tree API seems to be implemented by removing
convenience / type-safety from the BSD API to save memory (no multiple
instances compiled). While relatively straightforward, replacing tree.h
with rb3ptr's BSD shim here would be a lot of layers on top of rb3ptr's
core just to expose something like that core again, in the end.

And as advertised in another mail, with minimal use of macros
convenience and type-safety can be increased without requiring multiple
compilation, probably even saving code size. But that would mean
changing all client code to use the wrapper API / BSD shim...

Jens