From b4e00f7306a160639f047b3421985e8f3d0c6fb1 Mon Sep 17 00:00:00 2001 From: Jonathan Tan Date: Tue, 13 Feb 2018 10:39:39 -0800 Subject: 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 Signed-off-by: Junio C Hamano --- sha1-lookup.h | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'sha1-lookup.h') diff --git a/sha1-lookup.h b/sha1-lookup.h index cf5314f402..7678b23b36 100644 --- a/sha1-lookup.h +++ b/sha1-lookup.h @@ -7,4 +7,26 @@ extern int sha1_pos(const unsigned char *sha1, void *table, size_t nr, sha1_access_fn fn); + +/* + * Searches for sha1 in table, using the given fanout table to determine the + * interval to search, then using binary search. Returns 1 if found, 0 if not. + * + * Takes the following parameters: + * + * - sha1: the hash to search for + * - fanout_nbo: a 256-element array of NETWORK-order 32-bit integers; the + * integer at position i represents the number of elements in table whose + * first byte is less than or equal to i + * - table: a sorted list of hashes with optional extra information in between + * - stride: distance between two consecutive elements in table (should be + * GIT_MAX_RAWSZ or greater) + * - result: if not NULL, this function stores the element index of the + * position found (if the search is successful) or the index of the least + * element that is greater than sha1 (if the search is not successful) + * + * This function does not verify the validity of the fanout table. + */ +int bsearch_hash(const unsigned char *sha1, const uint32_t *fanout_nbo, + const unsigned char *table, size_t stride, uint32_t *result); #endif -- cgit v1.2.3