> On Thu, Oct 18, 2007 at 01:58:24PM -0700, Jason Thorpe wrote:

>> Can you please adapt this to use the rb tree code in libkern (proplib also 
>> uses a copy of this) and test for any performance differences / code size 
>> differences?

Jason, why do you think libkern version is better?
I think using <sys/tree.h> version is better, instead.
See below.


>>>>> On Thu, 18 Oct 2007 23:31:51 +0200,
      Joerg Sonnenberger <joerg@britannica.bec.de> said:

> The first concern is that the code doesn't allow "type safe" usage. I

<sys/tree.h> version is type safe, because it's using macros.

> The second concern is the use of the sentinel nodes. Having done the rb
> tree myself I'm sure that they save very little actual code and might
> have even increased the size.

I agree.  <sys/tree.h> version is better in this point too.

> The third concern is generality.  The only use of sys/tree.h in the
> kernel is uvm right now and that does some nasty things with
> RB_AUGMENT.  We can't replace that with the current rb_moved. If we
> want to have a single copy in the tree, we need a callback whenever
> a child of a node changes. That adds a conditional to a lot of
> branches though.

If we use <sys/tree.h> version, this is not a problem at all.

> The last concern is about memory usage. If doing all the above, only two
> bits of storage are needed for each node (color and position). I think
> that should be merged into the parent pointer. Based on my own tests,
> this is approximately free on i386 as the bitfield access is as bad as
> modifying the parent pointer and the parent pointer needs to be changed
> in most cases already.

The RB tree implementation in <sys/tree.h> is same with libkern
version in this point.
But if the memory usage is most important, we can use splay tree
instead of redblack tree with <sys/tree.h>, because the splay tree
version uses same interface with only half size of node memory.
The libkern version doesn't have splay tree implementation.
-- 
soda