Subject: Re: libkern's rb tree
To: Joerg Sonnenberger <firstname.lastname@example.org>
From: SODA Noriyuki <email@example.com>
Date: 10/19/2007 09:22:06
>>>>> On Thu, 18 Oct 2007 23:31:51 +0200,
Joerg Sonnenberger <firstname.lastname@example.org> 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.