bloom.h

   1 #ifndef BLOOM_H
   2 #define BLOOM_H
   3
   4 struct commit;
   5 struct repository;
   6
   7 struct bloom_filter_settings {
   8         /*
   9          * The version of the hashing technique being used.
  10          * We currently only support version = 1 which is
  11          * the seeded murmur3 hashing technique implemented
  12          * in bloom.c.
  13          */
  14         uint32_t hash_version;
  15
  16         /*
  17          * The number of times a path is hashed, i.e. the
  18          * number of bit positions tht cumulatively
  19          * determine whether a path is present in the
  20          * Bloom filter.
  21          */
  22         uint32_t num_hashes;
  23
  24         /*
  25          * The minimum number of bits per entry in the Bloom
  26          * filter. If the filter contains 'n' entries, then
  27          * filter size is the minimum number of 8-bit words
  28          * that contain n*b bits.
  29          */
  30         uint32_t bits_per_entry;
  31
  32         /*
  33          * The maximum number of changed paths per commit
  34          * before declaring a Bloom filter to be too-large.
  35          *
  36          * Not written to the commit-graph file.
  37          */
  38         uint32_t max_changed_paths;
  39 };
  40
  41 #define DEFAULT_BLOOM_MAX_CHANGES 512
  42 #define DEFAULT_BLOOM_FILTER_SETTINGS { 1, 7, 10, DEFAULT_BLOOM_MAX_CHANGES }
  43 #define BITS_PER_WORD 8
  44 #define BLOOMDATA_CHUNK_HEADER_SIZE 3 * sizeof(uint32_t)
  45
  46 /*
  47  * A bloom_filter struct represents a data segment to
  48  * use when testing hash values. The 'len' member
  49  * dictates how many entries are stored in
  50  * 'data'.
  51  */
  52 struct bloom_filter {
  53         unsigned char *data;
  54         size_t len;
  55 };
  56
  57 /*
  58  * A bloom_key represents the k hash values for a
  59  * given string. These can be precomputed and
  60  * stored in a bloom_key for re-use when testing
  61  * against a bloom_filter. The number of hashes is
  62  * given by the Bloom filter settings and is the same
  63  * for all Bloom filters and keys interacting with
  64  * the loaded version of the commit graph file and
  65  * the Bloom data chunks.
  66  */
  67 struct bloom_key {
  68         uint32_t *hashes;
  69 };
  70
  71 /*
  72  * Calculate the murmur3 32-bit hash value for the given data
  73  * using the given seed.
  74  * Produces a uniformly distributed hash value.
  75  * Not considered to be cryptographically secure.
  76  * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
  77  */
  78 uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len);
  79
  80 void fill_bloom_key(const char *data,
  81                     size_t len,
  82                     struct bloom_key *key,
  83                     const struct bloom_filter_settings *settings);
  84 void clear_bloom_key(struct bloom_key *key);
  85
  86 void add_key_to_filter(const struct bloom_key *key,
  87                        struct bloom_filter *filter,
  88                        const struct bloom_filter_settings *settings);
  89
  90 void init_bloom_filters(void);
  91
  92 enum bloom_filter_computed {
  93         BLOOM_NOT_COMPUTED = (1 << 0),
  94         BLOOM_COMPUTED     = (1 << 1),
  95         BLOOM_TRUNC_LARGE  = (1 << 2),
  96         BLOOM_TRUNC_EMPTY  = (1 << 3),
  97 };
  98
  99 struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
 100                                                  struct commit *c,
 101                                                  int compute_if_not_present,
 102                                                  const struct bloom_filter_settings *settings,
 103                                                  enum bloom_filter_computed *computed);
 104
 105 #define get_bloom_filter(r, c) get_or_compute_bloom_filter( \
 106         (r), (c), 0, NULL, NULL)
 107
 108 int bloom_filter_contains(const struct bloom_filter *filter,
 109                           const struct bloom_key *key,
 110                           const struct bloom_filter_settings *settings);
 111
 112 #endif