subtree: t7900: rename last_commit_message to last_commit_subject
[git] / 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