]> git.ipfire.org Git - thirdparty/git.git/commit - bloom.h
bloom.c: core Bloom filter implementation for changed paths.
authorGarima Singh <garima.singh@microsoft.com>
Mon, 30 Mar 2020 00:31:26 +0000 (00:31 +0000)
committerJunio C Hamano <gitster@pobox.com>
Mon, 30 Mar 2020 16:59:53 +0000 (09:59 -0700)
commited591febb4a201ce48b34a4e90027414cd0d7966
treea928b663ad556a34b2f69ac991eb84663a95e4d5
parentf1294eaf7fbf7673567b698b11e062566b9f1035
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 <peff@peff.net>
Helped-by: Derrick Stolee <dstolee@microsoft.com>
Reviewed-by: Jakub Narębski <jnareb@gmail.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
bloom.c
bloom.h
t/helper/test-bloom.c
t/t0095-bloom.sh