[PATCH v2 3/6] bloom: add helper to check if any key in a vector is present

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 <[email protected]>
---
 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