From 4dbdc42d9e7c3968ff7f690d00680419c9b8cb0f Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Tue, 9 Apr 2024 15:34:27 +0200 Subject: Adding upstream version 1:2.43.0. Signed-off-by: Daniel Baumann --- hash-lookup.h | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100644 hash-lookup.h (limited to 'hash-lookup.h') diff --git a/hash-lookup.h b/hash-lookup.h new file mode 100644 index 0000000..dbd71eb --- /dev/null +++ b/hash-lookup.h @@ -0,0 +1,32 @@ +#ifndef HASH_LOOKUP_H +#define HASH_LOOKUP_H + +typedef const struct object_id *oid_access_fn(size_t index, const void *table); + +int oid_pos(const struct object_id *oid, + const void *table, + size_t nr, + oid_access_fn fn); + +/* + * Searches for hash 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: + * + * - hash: 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 hash (if the search is not successful) + * + * This function does not verify the validity of the fanout table. + */ +int bsearch_hash(const unsigned char *hash, const uint32_t *fanout_nbo, + const unsigned char *table, size_t stride, uint32_t *result); +#endif -- cgit v1.2.3