Re: splay tree and red-black tree for vm_map entry lookups.

[Eirik Nygaard <eirikn@xxxxxxxxxxxx>]

On Wed, Jan 19, 2005 at 09:39:38AM -0800, Matthew Dillon wrote:
> :I have ported the splay tree used in FreeBSD to look up vm_map entries. [1]
> :And written a reb-black tree that does the same (part of the vm_map_lookup_entry
> :taken from NetBSD) [2].
> :
> :I havn't done any benchmarks on the two patches yet, but this should be done to
> :see which one is the best to use, and I hope you have some feedback for me.
> :
> :1: http://leaf.dragonflybsd.org/~eirikn/splay-tree-freebsd-1.patch
> :2: http://leaf.dragonflybsd.org/~eirikn/vm_map-rb-tree-netbsd-eirikn.patch
> :
> :-- 
> :Eirik Nygaard
> 
>     Lets go with the red-black approach.   I will patch it in and start
>     testing it myself.  It looks like NetBSD has done their homework though
>     and I expect we will be able to commit it by the end of the week.

I did add some code that used the hint, but for some reason it made my computer
go crazy at boot, and the login just went dead, could enter a login name but
'login:' just poped back out. I am having some trouble seeing why this could go
so bad. The hint code is in this patch:
http://leaf.dragonflybsd.org/~eirikn/vm_map-rb-tree-netbsd-eirikn-hint.patch

-- 
Eirik Nygaard