git.oblomov.eu Git - git/blob - sha1-lookup.h

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