path: root/t/helper
diff options
authorGarima Singh <>2020-03-30 00:31:26 (GMT)
committerJunio C Hamano <>2020-03-30 16:59:53 (GMT)
commited591febb4a201ce48b34a4e90027414cd0d7966 (patch)
treea928b663ad556a34b2f69ac991eb84663a95e4d5 /t/helper
parentf1294eaf7fbf7673567b698b11e062566b9f1035 (diff)
bloom.c: core Bloom filter implementation for changed paths.
Add the core implementation for computing Bloom filters for the paths changed between a commit and it's first parent. We fill the Bloom filters as (const char *data, int len) pairs as `struct bloom_filters" within a commit slab. Filters for commits with no changes and more than 512 changes, is represented with a filter of length zero. There is no gain in distinguishing between a computed filter of length zero for a commit with no changes, and an uncomputed filter for new commits or for commits with more than 512 changes. The effect on `git log -- path` is the same in both cases. We will fall back to the normal diffing algorithm when we can't benefit from the existence of Bloom filters. Helped-by: Jeff King <> Helped-by: Derrick Stolee <> Reviewed-by: Jakub Narębski <> Signed-off-by: Garima Singh <> Signed-off-by: Junio C Hamano <>
Diffstat (limited to 't/helper')
1 files changed, 20 insertions, 0 deletions
diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c
index 20460cd..f18d1b7 100644
--- a/t/helper/test-bloom.c
+++ b/t/helper/test-bloom.c
@@ -1,6 +1,7 @@
#include "git-compat-util.h"
#include "bloom.h"
#include "test-tool.h"
+#include "commit.h"
struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
@@ -32,6 +33,16 @@ static void print_bloom_filter(struct bloom_filter *filter) {
+static void get_bloom_filter_for_commit(const struct object_id *commit_oid)
+ struct commit *c;
+ struct bloom_filter *filter;
+ setup_git_directory();
+ c = lookup_commit(the_repository, commit_oid);
+ filter = get_bloom_filter(the_repository, c);
+ print_bloom_filter(filter);
int cmd__bloom(int argc, const char **argv)
if (!strcmp(argv[1], "get_murmur3")) {
@@ -57,5 +68,14 @@ int cmd__bloom(int argc, const char **argv)
+ if (!strcmp(argv[1], "get_filter_for_commit")) {
+ struct object_id oid;
+ const char *end;
+ if (parse_oid_hex(argv[2], &oid, &end))
+ die("cannot parse oid '%s'", argv[2]);
+ init_bloom_filters();
+ get_bloom_filter_for_commit(&oid);
+ }
return 0;
} \ No newline at end of file