summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRené Scharfe <l.s.r@web.de>2017-08-09 00:07:30 +0200
committerJunio C Hamano <gitster@pobox.com>2017-08-09 09:52:25 -0700
commit6355a768023e7c6d0ec11f2e8cdd2b7501daa516 (patch)
tree2379e34649e6d5c59c3a353767beff999f2d9ef4
parent840ed141983718e0c5518a325534a5656797132a (diff)
downloadgit-6355a768023e7c6d0ec11f2e8cdd2b7501daa516.tar.gz
sha1_file: avoid comparison if no packed hash matches the first byters/find-pack-entry-bisection
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@web.de> Reviewed-by: Jonathan Nieder <jrnieder@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
-rw-r--r--sha1_file.c4
1 files changed, 2 insertions, 2 deletions
diff --git a/sha1_file.c b/sha1_file.c
index 727a9769fb..3047ee04f1 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -2526,7 +2526,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,
return nth_packed_object_offset(p, pos);
}
- do {
+ while (lo < hi) {
unsigned mi = (lo + hi) / 2;
int cmp = hashcmp(index + mi * stride, sha1);
@@ -2539,7 +2539,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,
hi = mi;
else
lo = mi+1;
- } while (lo < hi);
+ }
return 0;
}