hash-lookup.h

   1 #ifndef HASH_LOOKUP_H
   2 #define HASH_LOOKUP_H
   3
   4 typedef const struct object_id *oid_access_fn(size_t index, const void *table);
   5
   6 int oid_pos(const struct object_id *oid,
   7             const void *table,
   8             size_t nr,
   9             oid_access_fn fn);
  10
  11 /*
  12  * Searches for hash in table, using the given fanout table to determine the
  13  * interval to search, then using binary search. Returns 1 if found, 0 if not.
  14  *
  15  * Takes the following parameters:
  16  *
  17  *  - hash: the hash to search for
  18  *  - fanout_nbo: a 256-element array of NETWORK-order 32-bit integers; the
  19  *    integer at position i represents the number of elements in table whose
  20  *    first byte is less than or equal to i
  21  *  - table: a sorted list of hashes with optional extra information in between
  22  *  - stride: distance between two consecutive elements in table (should be
  23  *    GIT_MAX_RAWSZ or greater)
  24  *  - result: if not NULL, this function stores the element index of the
  25  *    position found (if the search is successful) or the index of the least
  26  *    element that is greater than hash (if the search is not successful)
  27  *
  28  * This function does not verify the validity of the fanout table.
  29  */
  30 int bsearch_hash(const unsigned char *hash, const uint32_t *fanout_nbo,
  31                  const unsigned char *table, size_t stride, uint32_t *result);
  32 #endif