Date: Mon, 22 May 2017 07:17:10 +0200 From: Sebastian Huber <sebastian.huber@embedded-brains.de> To: Jens Stimpfle <jfs@jstimpfle.de>, freebsd-hackers@freebsd.org Subject: Re: Improved Red-black tree implementation Message-ID: <59227456.9020805@embedded-brains.de> In-Reply-To: <20170520165303.GA22452@jstimpfle.de> References: <20170514050220.GA768@jstimpfle.de> <591EA74A.3080500@embedded-brains.de> <20170520165303.GA22452@jstimpfle.de>
next in thread | previous in thread | raw e-mail | index | archive | help
On 20/05/17 18:53, Jens Stimpfle wrote:
>> It would be quite nice to have a <sys/tree.h> implementation which enc=
odes
>> >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=20
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=20
add new features optionally.
--=20
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@embedded-brains.de
PGP : Public key available on request.
Diese Nachricht ist keine gesch=E4ftliche Mitteilung im Sinne des EHUG.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?59227456.9020805>