Date: Fri, 24 May 2002 21:22:49 -0400 (EDT) From: Robert Watson <rwatson@FreeBSD.org> To: Mike Silbersack <silby@silby.com> Cc: Alan Cox <alc@cs.rice.edu>, cvs-committers@FreeBSD.org, cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/vm vm_map.c vm_map.h Message-ID: <Pine.NEB.3.96L.1020524212137.70658G-100000@fledge.watson.org> In-Reply-To: <20020523221001.X18281-100000@patrocles.silby.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, 23 May 2002, Mike Silbersack wrote: > > On Thu, 23 May 2002, Alan Cox wrote: > > > P.S. I hope this motivates others on this list to look at splay trees. > > They are extemely easy to work with and to implement. (Notice that vm_map.c > > only grew by 24 lines.) > > Hm, they look pretty neat from what I've been able to gather. It looks > like they would be a great replacement for hash tables in many cases. > What are the practical downsides? I'm surprised that I haven't heard of > them before. I believe they were invented by Danny Sleator at CMU a fair while ago as part of his work on amortized analysis. Other related and interesting structures are skip lists, and so on. Any decent algorithms text should discuss these in detail, and the pertinent details of amortized analysis. Robert N M Watson FreeBSD Core Team, TrustedBSD Project robert@fledge.watson.org NAI Labs, Safeport Network Services To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe cvs-all" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.NEB.3.96L.1020524212137.70658G-100000>