[PATCH v3 3/6] bloom: add helper to check if any key in a vector is present
- From
Toon Claes <toon@iotcl.com>
- Date
- Aug 31, 2026, 15:18 UTC
- Message-ID
- <20260831-toon-speed-up-last-modified-v3-3-2bbb864acf93@iotcl.com>
- In-Reply-To
- <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com>
The changed-path Bloom filter of a commit stores a key for every changed path together with each of its leading directories. To query if a path was changed, bloom_keyvec_new() fills a key vector the same way: a key for the given path and one for each of its leading directories. For example, for "a/b/c" the vector holds keys for "a/b/c", "a/b" and "a".
A Bloom filter can only ever prove absence. When a key is not in the filter, the path it was made for definitely did not change. When it is in the filter, the path may have changed, as the key can be a false positive.
bloom_filter_contains_vec() looks up all keys of a vector and reports whether all of them are present. That answers: Is this path maybe changed by this commit?
A caller that also cares about the directories containing the path asks a different question: Is this path, or any directory leading up to it, maybe changed by this commit?
Consider the Bloom filter of a commit that changed "a/b/d". It holds keys for "a/b/d", "a/b" and "a", so looking up the vector of "a/b/c" with bloom_filter_contains_vec() reports that nothing changed, even though "a/b" and "a" did.
Add bloom_filter_contains_any_vec(), which reports whether any key in the vector is present. It returns 0 only when none of the keys are in the filter, which means the path and all directories leading up to it definitely did not change.
There are no callers yet, one is added in a subsequent commit.
Signed-off-by: Toon Claes <toon@iotcl.com> --- bloom.c | 12 ++++++++++++ bloom.h | 11 +++++++++++ 2 files changed, 23 insertions(+)
diff --git a/bloom.c b/bloom.c index caf22f9831..b96534e6e3 100644 --- a/bloom.c +++ b/bloom.c @@ -607,6 +607,18 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter, return ret; } +int bloom_filter_contains_any_vec(const struct bloom_filter *filter, + const struct bloom_keyvec *vec, + const struct bloom_filter_settings *settings) +{ + int ret = 0; + + for (size_t nr = 0; !ret && nr < vec->count; nr++) + ret = bloom_filter_contains(filter, &vec->key[nr], settings); + + return ret; +} + uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len, int version) { diff --git a/bloom.h b/bloom.h index 92ab2100d3..f508db23ad 100644 --- a/bloom.h +++ b/bloom.h @@ -164,6 +164,17 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter, const struct bloom_keyvec *v, const struct bloom_filter_settings *settings); +/* + * bloom_filter_contains_any_vec - Check if any key in a key vector is in the + * Bloom filter. + * + * Returns 1 if **any** key in the vector is present in the filter, 0 if none + * of them are. + */ +int bloom_filter_contains_any_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);
-- 2.55.0.679.g6767b8d81c