Re: [PATCH 21/22] teach the merge algorithm about cache iterators

[Chuck Lever <cel@citi.umich.edu>]

[-- Attachment #1: Type: text/plain, Size: 924 bytes --]

Daniel Barkalow wrote:
> On Wed, 14 Sep 2005, Chuck Lever wrote:
>>[ i'm not sure why you think insert would be O(n). ]
> 
> 
> You need to find the correct location to insert in the sorted list, and 
> the hash table won't help you, because it doesn't have the new name. 
> Remember that the cursors need to go through the index in order, so the 
> list has to stay sorted.

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.

in fact, this will impact the other places that need an insertion point, 
such as ls-files and merge-index, as well as your new merge algorithm 
(which inserts all merged entries into the active cache one at a time 
via add_cache_entry).

considering that add_cache_entry can do a cache lookup several times, i 
think we need the "not found, returning insertion point" case to be fast 
too.

back to the drawring board.

[-- Attachment #2: cel.vcf --]
[-- Type: text/x-vcard, Size: 439 bytes --]

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