diff options
author | Jonathan Tan <jonathantanmy@google.com> | 2018-02-13 21:39:39 +0300 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2018-02-16 00:08:55 +0300 |
commit | b4e00f7306a160639f047b3421985e8f3d0c6fb1 (patch) | |
tree | f5c1c3ffba403ad4bb1e25bac7e4f2a943a313cf /sha1-lookup.c | |
parent | 4669e7d68ec8fb6ff3572a1193ae75ae2094b8e6 (diff) |
packfile: refactor hash search with fanout table
Subsequent patches will introduce file formats that make use of a fanout
array and a sorted table containing hashes, just like packfiles.
Refactor the hash search in packfile.c into its own function, so that
those patches can make use of it as well.
Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'sha1-lookup.c')
-rw-r--r-- | sha1-lookup.c | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/sha1-lookup.c b/sha1-lookup.c index 4cf3ebd9212..8d0b1db3e27 100644 --- a/sha1-lookup.c +++ b/sha1-lookup.c @@ -99,3 +99,31 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr, } while (lo < hi); return -lo-1; } + +int bsearch_hash(const unsigned char *sha1, const uint32_t *fanout_nbo, + const unsigned char *table, size_t stride, uint32_t *result) +{ + uint32_t hi, lo; + + hi = ntohl(fanout_nbo[*sha1]); + lo = ((*sha1 == 0x0) ? 0 : ntohl(fanout_nbo[*sha1 - 1])); + + while (lo < hi) { + unsigned mi = lo + (hi - lo) / 2; + int cmp = hashcmp(table + mi * stride, sha1); + + if (!cmp) { + if (result) + *result = mi; + return 1; + } + if (cmp > 0) + hi = mi; + else + lo = mi + 1; + } + + if (result) + *result = lo; + return 0; +} |