Subject: Re: libkern's rb tree
To: Joerg Sonnenberger <>
From: SODA Noriyuki <>
List: tech-kern
Date: 10/19/2007 09:22:06
>>>>> On Thu, 18 Oct 2007 23:31:51 +0200,
      Joerg Sonnenberger <> said:

> The third concern is generality. The only use of sys/tree.h in the
> kernel is uvm right now

arch/x86/x86/pmap.c uses <sys/tree.h> as well.
It does not use redblack tree, but splay tree though.

> 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). 

If you choose splay tree, you don't need even the two bits.
So, I think it's better to measure which tree algorithm is faster.