cvs commit: src/lib/libc/stdlib malloc.c rb.h

Jason Evans jasone at
Wed Apr 23 17:28:24 UTC 2008

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.


More information about the cvs-src mailing list