From owner-cvs-all@FreeBSD.ORG  Wed Apr 23 17:28:24 2008
Return-Path: <owner-cvs-all@FreeBSD.ORG>
Delivered-To: cvs-all@FreeBSD.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id 4BAFD106566B;
	Wed, 23 Apr 2008 17:28:24 +0000 (UTC)
	(envelope-from jasone@FreeBSD.org)
Received: from canonware.com (canonware.com [64.183.146.166])
	by mx1.freebsd.org (Postfix) with ESMTP id 1569C8FC1B;
	Wed, 23 Apr 2008 17:28:24 +0000 (UTC)
	(envelope-from jasone@FreeBSD.org)
Received: from [192.168.168.201] (unknown [192.168.168.201])
	by canonware.com (Postfix) with ESMTP id 658EE1298C0;
	Wed, 23 Apr 2008 10:07:04 -0700 (PDT)
Message-ID: <480F6C9B.5050702@FreeBSD.org>
Date: Wed, 23 Apr 2008 10:06:35 -0700
From: Jason Evans <jasone@FreeBSD.org>
User-Agent: Thunderbird 2.0.0.12 (X11/20080227)
MIME-Version: 1.0
To: "Bruce M. Simpson" <bms@FreeBSD.org>
References: <200804231609.m3NG9IIP025153@repoman.freebsd.org>
	<480F64B4.9020001@FreeBSD.org>
In-Reply-To: <480F64B4.9020001@FreeBSD.org>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Cc: cvs-src@FreeBSD.org, src-committers@FreeBSD.org,
	Jason Evans <jasone@FreeBSD.org>, cvs-all@FreeBSD.org
Subject: Re: cvs commit: src/lib/libc/stdlib malloc.c rb.h
X-BeenThere: cvs-all@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: CVS commit messages for the entire tree <cvs-all.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/cvs-all>,
	<mailto:cvs-all-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/cvs-all>
List-Post: <mailto:cvs-all@freebsd.org>
List-Help: <mailto:cvs-all-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/cvs-all>,
	<mailto:cvs-all-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Wed, 23 Apr 2008 17:28:24 -0000

Bruce M. Simpson wrote:
> Jason Evans wrote:
>>   Log:
>>   Implement red-black trees without using parent pointers, and store the
>>   color bit in the least significant bit of the right child pointer, in
>>   order to reduce red-black tree linkage overhead by ~2X as compared to
>>   sys/tree.h.
> 
> Interesting. Will this work in the kernel? I have a bunch of code to 
> introduce which uses sys/tree.h there.

Yes, it will work in the kernel just fine.  The main reason I didn't 
make it sys/rb.h is that sys/tree.h already exists (and I haven't 
bothered to write a manual page either).  There is nothing fundamentally 
wrong with the sys/tree.h implementation, except that it takes more data 
structure space, which was hurting malloc quite a bit.

Jason