From owner-cvs-all Fri May 24 18:23:15 2002 Delivered-To: cvs-all@freebsd.org Received: from fledge.watson.org (fledge.watson.org [204.156.12.50]) by hub.freebsd.org (Postfix) with ESMTP id 41F0737B407; Fri, 24 May 2002 18:23:11 -0700 (PDT) Received: from fledge.watson.org (fledge.pr.watson.org [192.0.2.3]) by fledge.watson.org (8.12.3/8.12.3) with SMTP id g4P1Mnb5071215; Fri, 24 May 2002 21:22:49 -0400 (EDT) (envelope-from robert@fledge.watson.org) Date: Fri, 24 May 2002 21:22:49 -0400 (EDT) From: Robert Watson X-Sender: robert@fledge.watson.org To: Mike Silbersack Cc: Alan Cox , cvs-committers@FreeBSD.org, cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/vm vm_map.c vm_map.h In-Reply-To: <20020523221001.X18281-100000@patrocles.silby.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-cvs-all@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG 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