diff options
| author | Junio C Hamano <gitster@pobox.com> | 2025-07-23 15:45:15 -0700 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2025-07-23 15:45:15 -0700 |
| commit | f22d4ac4fd50b55c88142dfd15a361680cf3fb40 (patch) | |
| tree | 92a3be8ed47f75e15d2bda0932b6e4ca45d6d064 /bloom.h | |
| parent | 0e8243a355a69035dac269528b49dc8c9bc81f8a (diff) | |
| parent | 2a6ce090f27016d68ee6952809d98fe88ce53522 (diff) | |
| download | git-f22d4ac4fd50b55c88142dfd15a361680cf3fb40.tar.gz | |
Merge branch 'ly/changed-paths-traversal'
Lift the limitation to use changed-path filter in "git log" so that
it can be used for a pathspec with multiple literal paths.
* ly/changed-paths-traversal:
bloom: optimize multiple pathspec items in revision
revision: make helper for pathspec to bloom keyvec
bloom: replace struct bloom_key * with struct bloom_keyvec
bloom: rename function operates on bloom_key
bloom: add test helper to return murmur3 hash
Diffstat (limited to 'bloom.h')
| -rw-r--r-- | bloom.h | 54 |
1 files changed, 42 insertions, 12 deletions
@@ -74,24 +74,40 @@ struct bloom_key { uint32_t *hashes; }; +/* + * A bloom_keyvec is a vector of bloom_keys, which + * can be used to store multiple keys for a single + * pathspec item. + */ +struct bloom_keyvec { + size_t count; + struct bloom_key key[FLEX_ARRAY]; +}; + int load_bloom_filter_from_graph(struct commit_graph *g, struct bloom_filter *filter, uint32_t graph_pos); +void bloom_key_fill(struct bloom_key *key, const char *data, size_t len, + const struct bloom_filter_settings *settings); +void bloom_key_clear(struct bloom_key *key); + /* - * Calculate the murmur3 32-bit hash value for the given data - * using the given seed. - * Produces a uniformly distributed hash value. - * Not considered to be cryptographically secure. - * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm + * bloom_keyvec_new - Allocate and populate a bloom_keyvec with keys for the + * given path. + * + * This function splits the input path by '/' and generates a bloom key for each + * prefix, in reverse order of specificity. For example, given the input + * "a/b/c", it will generate bloom keys for: + * - "a/b/c" + * - "a/b" + * - "a" + * + * The resulting keys are stored in a newly allocated bloom_keyvec. */ -uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len); - -void fill_bloom_key(const char *data, - size_t len, - struct bloom_key *key, - const struct bloom_filter_settings *settings); -void clear_bloom_key(struct bloom_key *key); +struct bloom_keyvec *bloom_keyvec_new(const char *path, size_t len, + const struct bloom_filter_settings *settings); +void bloom_keyvec_free(struct bloom_keyvec *vec); void add_key_to_filter(const struct bloom_key *key, struct bloom_filter *filter, @@ -137,4 +153,18 @@ int bloom_filter_contains(const struct bloom_filter *filter, const struct bloom_key *key, const struct bloom_filter_settings *settings); +/* + * bloom_filter_contains_vec - Check if all keys in a key vector are in the + * Bloom filter. + * + * Returns 1 if **all** keys in the vector are present in the filter, + * 0 if **any** key is not present. + */ +int bloom_filter_contains_vec(const struct bloom_filter *filter, + const struct bloom_keyvec *v, + const struct bloom_filter_settings *settings); + +uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len, + int version); + #endif |