Improved Red-black tree implementation

[Sebastian Huber]

On 20/05/17 18:53, Jens Stimpfle wrote:
>> 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 RB and Eternally Confuzzled variants don't use a parent pointer as 
far as I remember.

>
> 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.

Yes, type-safety was no major requirement in my case.

>
> 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...

For BSD inclusion I guess the API and ABI must be compatible. You can 
add new features optionally.

-- 
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.