@leroysheep / MovieWebApp
Code Commits Pulls CI/CD 82,128
seen
bisect jch maint master next seen test todo
h 170 lines 4.92 KB
Raw
1 #ifndef BLOOM_H
2 #define BLOOM_H
3
4 struct commit;
5 struct repository;
6 struct commit_graph;
7
8 struct bloom_filter_settings {
9 /*
10 * The version of the hashing technique being used.
11 * The newest version is 2, which is
12 * the seeded murmur3 hashing technique implemented
13 * in bloom.c. Bloom filters of version 1 were created
14 * with prior versions of Git, which had a bug in the
15 * implementation of the hash function.
16 */
17 uint32_t hash_version;
18
19 /*
20 * The number of times a path is hashed, i.e. the
21 * number of bit positions that cumulatively
22 * determine whether a path is present in the
23 * Bloom filter.
24 */
25 uint32_t num_hashes;
26
27 /*
28 * The minimum number of bits per entry in the Bloom
29 * filter. If the filter contains 'n' entries, then
30 * filter size is the minimum number of 8-bit words
31 * that contain n*b bits.
32 */
33 uint32_t bits_per_entry;
34
35 /*
36 * The maximum number of changed paths per commit
37 * before declaring a Bloom filter to be too-large.
38 *
39 * Not written to the commit-graph file.
40 */
41 uint32_t max_changed_paths;
42 };
43
44 #define DEFAULT_BLOOM_MAX_CHANGES 512
45 #define DEFAULT_BLOOM_FILTER_SETTINGS { 1, 7, 10, DEFAULT_BLOOM_MAX_CHANGES }
46 #define BITS_PER_WORD 8
47 #define BLOOMDATA_CHUNK_HEADER_SIZE 3 * sizeof(uint32_t)
48
49 /*
50 * A bloom_filter struct represents a data segment to
51 * use when testing hash values. The 'len' member
52 * dictates how many entries are stored in
53 * 'data'.
54 */
55 struct bloom_filter {
56 unsigned char *data;
57 size_t len;
58 int version;
59
60 void *to_free;
61 };
62
63 /*
64 * A bloom_key represents the k hash values for a
65 * given string. These can be precomputed and
66 * stored in a bloom_key for re-use when testing
67 * against a bloom_filter. The number of hashes is
68 * given by the Bloom filter settings and is the same
69 * for all Bloom filters and keys interacting with
70 * the loaded version of the commit graph file and
71 * the Bloom data chunks.
72 */
73 struct bloom_key {
74 uint32_t *hashes;
75 };
76
77 /*
78 * A bloom_keyvec is a vector of bloom_keys, which
79 * can be used to store multiple keys for a single
80 * pathspec item.
81 */
82 struct bloom_keyvec {
83 size_t count;
84 struct bloom_key key[FLEX_ARRAY];
85 };
86
87 int load_bloom_filter_from_graph(struct commit_graph *g,
88 struct bloom_filter *filter,
89 uint32_t graph_pos);
90
91 void bloom_key_fill(struct bloom_key *key, const char *data, size_t len,
92 const struct bloom_filter_settings *settings);
93 void bloom_key_clear(struct bloom_key *key);
94
95 /*
96 * bloom_keyvec_new - Allocate and populate a bloom_keyvec with keys for the
97 * given path.
98 *
99 * This function splits the input path by '/' and generates a bloom key for each
100 * prefix, in reverse order of specificity. For example, given the input
101 * "a/b/c", it will generate bloom keys for:
102 * - "a/b/c"
103 * - "a/b"
104 * - "a"
105 *
106 * The resulting keys are stored in a newly allocated bloom_keyvec.
107 */
108 struct bloom_keyvec *bloom_keyvec_new(const char *path, size_t len,
109 const struct bloom_filter_settings *settings);
110 void bloom_keyvec_free(struct bloom_keyvec *vec);
111
112 void add_key_to_filter(const struct bloom_key *key,
113 struct bloom_filter *filter,
114 const struct bloom_filter_settings *settings);
115
116 void init_bloom_filters(void);
117 void deinit_bloom_filters(void);
118
119 enum bloom_filter_computed {
120 BLOOM_NOT_COMPUTED = (1 << 0),
121 BLOOM_COMPUTED = (1 << 1),
122 BLOOM_TRUNC_LARGE = (1 << 2),
123 BLOOM_TRUNC_EMPTY = (1 << 3),
124 BLOOM_UPGRADED = (1 << 4),
125 };
126
127 struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
128 struct commit *c,
129 int compute_if_not_present,
130 const struct bloom_filter_settings *settings,
131 enum bloom_filter_computed *computed);
132
133 /*
134 * Find the Bloom filter associated with the given commit "c".
135 *
136 * If any of the following are true
137 *
138 * - the repository does not have a commit-graph, or
139 * - the repository disables reading from the commit-graph, or
140 * - the given commit does not have a Bloom filter computed, or
141 * - there is a Bloom filter for commit "c", but it cannot be read
142 * because the filter uses an incompatible version of murmur3
143 *
144 * , then `get_bloom_filter()` will return NULL. Otherwise, the corresponding
145 * Bloom filter will be returned.
146 *
147 * For callers who wish to inspect Bloom filters with incompatible hash
148 * versions, use get_or_compute_bloom_filter().
149 */
150 struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c);
151
152 int bloom_filter_contains(const struct bloom_filter *filter,
153 const struct bloom_key *key,
154 const struct bloom_filter_settings *settings);
155
156 /*
157 * bloom_filter_contains_vec - Check if all keys in a key vector are in the
158 * Bloom filter.
159 *
160 * Returns 1 if **all** keys in the vector are present in the filter,
161 * 0 if **any** key is not present.
162 */
163 int bloom_filter_contains_vec(const struct bloom_filter *filter,
164 const struct bloom_keyvec *v,
165 const struct bloom_filter_settings *settings);
166
167 uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len,
168 int version);
169
170 #endif