Date: Wed, 23 Apr 2008 10:06:35 -0700 From: Jason Evans <jasone@FreeBSD.org> To: "Bruce M. Simpson" <bms@FreeBSD.org> 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 Message-ID: <480F6C9B.5050702@FreeBSD.org> In-Reply-To: <480F64B4.9020001@FreeBSD.org> References: <200804231609.m3NG9IIP025153@repoman.freebsd.org> <480F64B4.9020001@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?480F6C9B.5050702>