From owner-freebsd-hackers@freebsd.org Fri May 19 08:31:14 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 76F6FD7317E for ; Fri, 19 May 2017 08:31:14 +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 29C84CC3 for ; Fri, 19 May 2017 08:31:13 +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 1dBcuk-000145-0l; Fri, 19 May 2017 10:05:34 +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 1dBcuj-0004Eo-PU; Fri, 19 May 2017 10:05:33 +0200 Received: from localhost (localhost.localhost [127.0.0.1]) by mail.embedded-brains.de (Postfix) with ESMTP id 0BBA52A003F; Fri, 19 May 2017 10:06:10 +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 L1BCbzYUPCjM; Fri, 19 May 2017 10:06:07 +0200 (CEST) Received: from localhost (localhost.localhost [127.0.0.1]) by mail.embedded-brains.de (Postfix) with ESMTP id ADF922A0047; Fri, 19 May 2017 10:06:07 +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 KfWJrQ2BjVbv; Fri, 19 May 2017 10:06:07 +0200 (CEST) Received: from [192.168.96.129] (unknown [192.168.96.129]) by mail.embedded-brains.de (Postfix) with ESMTPSA id 983592A003F; Fri, 19 May 2017 10:06:07 +0200 (CEST) Subject: Re: Improved Red-black tree implementation To: Jens Stimpfle , freebsd-hackers@freebsd.org References: <20170514050220.GA768@jstimpfle.de> From: Sebastian Huber Message-ID: <591EA74A.3080500@embedded-brains.de> Date: Fri, 19 May 2017 10:05:30 +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: <20170514050220.GA768@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/23397/Fri May 19 02:58:09 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: Fri, 19 May 2017 08:31:14 -0000 Hello, I use the BSD for RTEMS with a shared extract and insert=20 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 implementation which=20 encodes the color in one of the pointers to save some memory. --=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.