From: Chuck Lever Date: Thu, 15 Sep 2005 14:01:16 GMT Subject: Re: [PATCH 21/22] teach the merge algorithm about cache iterators Message-ID: <43297EAC.6020205@citi.umich.edu> In-Reply-To: Daniel Barkalow wrote: > On Wed, 14 Sep 2005, Linus Torvalds wrote: > > >>On Wed, 14 Sep 2005, Chuck Lever wrote: >> >>>oh, i see. the hash table won't help cache_find_name find an insertion >>>point quickly if the name isn't already in the cache. >> >>Note that almost all insertion tends to happen linearly. >> >>In particular, read-tree always inserts things in order. > > read-tree (with Chuck's latest work) should actually only append entries > to an initially-empty list, which is even easier. Dunno about the other > stuff, but I'd guess inserting into a cursor would handle a lot of it. i'm implementing the splay tree now. part of the insertion process is to splay the insertion point up to the root of the tree. if what you and linus says is true, then the search for the next insertion point will be very fast most of the time. begin:vcard fn:Chuck Lever n:Lever;Charles org:Network Appliance, Incorporated;Linux NFS Client Development adr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA email;internet:cel@citi.umich.edu title:Member of Technical Staff tel;work:+1 734 763-4415 tel;fax:+1 734 763 4434 tel;home:+1 734 668-1089 x-mozilla-html:FALSE url:http://www.monkey.org/~cel/ version:2.1 end:vcard