Subject: Re: [PATCH 17/32] read-cache: split-index mode

From: Junio C Hamano <[email-masked]>
Date: Tue, 29 Apr 2014 10:23:47 -0700

Duy Nguyen <[email-masked]> writes:

>> I do think it is sensible to keep two arrays of "struct cache_entry"
>> around (one for base and one for incremental changes) inside
>> index_state, and the patch seems to do so via "struct split_index"
>> that does have a copy of saved_cache.  If the write-out codepath
>> walks these two sorted arrays in parallel, shouldn't it be able to
>> figure out which entry is added, deleted and modified without
>> fattening this structure?
>
> So far without that "index" field I would have to resort to hasing
> entries in both arrays to find the shared paths. But ideas are
> welcome.

Hmm, why do you need to hash, when both arrays are sorted?  Wouldn't
it be just the matter of walking these two arrays in parallel,
with one scanning index for each array initialized to the beginning,
comparing the elements pointed by these indices, noting the side
that comes earlier in the sort order and advancing the index on that
side (or if they compare equal then advance both), ...?