Web lists-archives.com

Re: [PATCH] sha1_file: avoid comparison if no packed hash matches the first byte




René Scharfe wrote:

> find_pack_entry_one() uses the fan-out table of pack indexes to find out
> which entries match the first byte of the searched hash and does a
> binary search on this subset of the main index table.
>
> If there are no matching entries then lo and hi will have the same
> value.  The binary search still starts and compares the hash of the
> following entry (which has a non-matching first byte, so won't cause any
> trouble), or whatever comes after the sorted list of entries.
>
> The probability of that stray comparison matching by mistake is low, but
> let's not take any chances and check when entering the binary search
> loop if we're actually done already.
>
> Signed-off-by: Rene Scharfe <l.s.r@xxxxxx>
> ---
>  sha1_file.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)

Thanks for a clear explanation.

Sanity checking: is this correct in the sha1[0] == 0 case?  In that
case, we have lo = 0, hi = the 0th offset from the fanout table.  The
offsets in the fanout table are defined as "the number of objects in
the corresponding pack, the first byte of whose object name is less
than or equal to N."  So hi == lo would mean there are no objects with
id starting with 0, as hoped.

Or in other words, the [lo, hi) interval we're trying to search is
indeed a half-open interval.

Reviewed-by: Jonathan Nieder <jrnieder@xxxxxxxxx>