splay tree and red-black tree for vm_map entry lookups.
eirikn at kerneled.com
Wed Jan 19 09:47:31 PST 2005
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. 
> :And written a reb-black tree that does the same (part of the vm_map_lookup_entry
> :taken from NetBSD) .
> :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:
More information about the Kernel