path: root/sha1-lookup.h
diff options
authorJonathan Tan <>2018-02-13 18:39:39 (GMT)
committerJunio C Hamano <>2018-02-15 21:08:55 (GMT)
commitb4e00f7306a160639f047b3421985e8f3d0c6fb1 (patch)
treef5c1c3ffba403ad4bb1e25bac7e4f2a943a313cf /sha1-lookup.h
parent4669e7d68ec8fb6ff3572a1193ae75ae2094b8e6 (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 <> Signed-off-by: Junio C Hamano <>
Diffstat (limited to 'sha1-lookup.h')
1 files changed, 22 insertions, 0 deletions
diff --git a/sha1-lookup.h b/sha1-lookup.h
index cf5314f..7678b23 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);