From owner-freebsd-hackers@freebsd.org Mon May 22 05:17:21 2017 Return-Path: Delivered-To: freebsd-hackers@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 11350D773AD for ; Mon, 22 May 2017 05:17:21 +0000 (UTC) (envelope-from sebastian.huber@embedded-brains.de) Received: from dedi548.your-server.de (dedi548.your-server.de [85.10.215.148]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id C40131919 for ; Mon, 22 May 2017 05:17:20 +0000 (UTC) (envelope-from sebastian.huber@embedded-brains.de) Received: from [88.198.220.130] (helo=sslproxy01.your-server.de) by dedi548.your-server.de with esmtpsa (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (Exim 4.85_2) (envelope-from ) id 1dCfiS-0007tj-4K; Mon, 22 May 2017 07:17:12 +0200 Received: from [82.135.62.35] (helo=mail.embedded-brains.de) by sslproxy01.your-server.de with esmtpsa (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (Exim 4.84_2) (envelope-from ) id 1dCfiR-0002gM-TN; Mon, 22 May 2017 07:17:12 +0200 Received: from localhost (localhost.localhost [127.0.0.1]) by mail.embedded-brains.de (Postfix) with ESMTP id A7D2F2A0929; Mon, 22 May 2017 07:17:51 +0200 (CEST) Received: from mail.embedded-brains.de ([127.0.0.1]) by localhost (zimbra.eb.localhost [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id dOcjPTo8BYv3; Mon, 22 May 2017 07:17:51 +0200 (CEST) Received: from localhost (localhost.localhost [127.0.0.1]) by mail.embedded-brains.de (Postfix) with ESMTP id 2F85B2A092A; Mon, 22 May 2017 07:17:51 +0200 (CEST) X-Virus-Scanned: amavisd-new at zimbra.eb.localhost Received: from mail.embedded-brains.de ([127.0.0.1]) by localhost (zimbra.eb.localhost [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id Rb3qoEWFJYLX; Mon, 22 May 2017 07:17:51 +0200 (CEST) Received: from [192.168.96.129] (unknown [192.168.96.129]) by mail.embedded-brains.de (Postfix) with ESMTPSA id 1CD192A0929; Mon, 22 May 2017 07:17:51 +0200 (CEST) Subject: Re: Improved Red-black tree implementation To: Jens Stimpfle , freebsd-hackers@freebsd.org References: <20170514050220.GA768@jstimpfle.de> <591EA74A.3080500@embedded-brains.de> <20170520165303.GA22452@jstimpfle.de> From: Sebastian Huber Message-ID: <59227456.9020805@embedded-brains.de> Date: Mon, 22 May 2017 07:17:10 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.0 MIME-Version: 1.0 In-Reply-To: <20170520165303.GA22452@jstimpfle.de> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: quoted-printable X-Authenticated-Sender: smtp-embedded@poldinet.de X-Virus-Scanned: Clear (ClamAV 0.99.2/23406/Mon May 22 02:55:22 2017) X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 22 May 2017 05:17:21 -0000 On 20/05/17 18:53, Jens Stimpfle wrote: >> It would be quite nice to have a 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.