Signed-off-by: Jonathan Tan
---
bloom-filter.c | 31 ++-
bloom-filter.h | 12
commit-graph.c | 26 --
revision.c | 9 +++--
4 files changed, 37 insertions(+), 41 deletions(-)
diff --git a/bloom-filter.c b/bloom-filter.c
index 7dce0e35fa..39b453908f 100644
--- a/bloom-filter.c
+++ b/bloom-filter.c
@@ -1,14 +1,17 @@
#include "cache.h"
#include "bloom-filter.h"
-void bloom_filter_init(struct bloom_filter *bf, uint32_t bit_size)
+void bloom_filter_init(struct bloom_filter *bf, uint32_t commit_nr, uint32_t
bit_size)
{
if (bit_size % CHAR_BIT)
BUG("invalid size for bloom filter");
+ if (bit_size > 1024)
+ BUG("aborting: the bit size is per commit, not for the whole
filter");
bf->nr_entries = 0;
+ bf->commit_nr = commit_nr;
bf->bit_size = bit_size;
- bf->bits = xmalloc(bit_size / CHAR_BIT);
+ bf->bits = xcalloc(1, commit_nr * bit_size / CHAR_BIT);
}
void bloom_filter_free(struct bloom_filter *bf)
@@ -19,24 +22,24 @@ void bloom_filter_free(struct bloom_filter *bf)
}
-void bloom_filter_set_bits(struct bloom_filter *bf, const uint32_t *offsets,
+static void bloom_filter_set_bits(struct bloom_filter *bf, uint32_t graph_pos,
const uint32_t *offsets,
int nr_offsets, int nr_entries)
{
int i;
for (i = 0; i < nr_offsets; i++) {
- uint32_t byte_offset = (offsets[i] % bf->bit_size) / CHAR_BIT;
+ uint32_t byte_offset = (offsets[i] % bf->bit_size + graph_pos *
bf->bit_size) / CHAR_BIT;
unsigned char mask = 1 << offsets[i] % CHAR_BIT;
bf->bits[byte_offset] |= mask;
}
bf->nr_entries += nr_entries;
}
-int bloom_filter_check_bits(struct bloom_filter *bf, const uint32_t *offsets,
+static int bloom_filter_check_bits(struct bloom_filter *bf, uint32_t
graph_pos, const uint32_t *offsets,
int nr)
{
int i;
for (i = 0; i < nr; i++) {
- uint32_t byte_offset = (offsets[i] % bf->bit_size) / CHAR_BIT;
+ uint32_t byte_offset = (offsets[i] % bf->bit_size + graph_pos *
bf->bit_size) / CHAR_BIT;
unsigned char mask = 1 << offsets[i] % CHAR_BIT;
if (!(bf->bits[byte_offset] & mask))
return 0;
@@ -45,19 +48,19 @@ int bloom_filter_check_bits(struct bloom_filter *bf, const
uint32_t *offsets,
}
-void bloom_filter_add_hash(struct bloom_filter *bf, const unsigned char *hash)
+void bloom_filter_add_hash(struct bloom_filter *bf, uint32_t graph_pos, const
unsigned char *hash)
{
uint32_t offsets[GIT_MAX_RAWSZ / sizeof(uint32_t)];
hashcpy((unsigned char*)offsets, hash);
- bloom_filter_set_bits(bf, offsets,
+ bloom_filter_set_bits(bf, graph_pos, offsets,
the_hash_algo->rawsz / sizeof(*offsets), 1);
}
-int bloom_filter_check_hash(struct bloom_filter *bf, const unsigned char *hash)
+int bloom_filter_check_hash(struct bloom_filter *bf, uint32_t graph_pos, const
unsigned char *hash)
{
uint32_t offsets[GIT_MAX_RAWSZ / sizeof(uint32_t)];
hashcpy((unsigned char*)offsets, hash);
- return bloom_filter_check_bits(bf, offsets,
+ return bloom_filter_check_bits(bf, graph_pos, offsets,
the_hash_algo->rawsz / sizeof(*offsets));
}
@@ -80,11 +83,12 @@ int bloom_filter_load(struct bloom_filter *bf)
return -1;
read_in_full(fd, >nr_entries, sizeof(bf->nr_entries));
+ read_in_full(fd, >commit_nr, sizeof(bf->commit_nr));
read_in_full(fd, >bit_size, sizeof(bf->bit_size));
if (bf->bit_size % CHAR_BIT)
BUG("invalid size for bloom filter");
- bf->bits = xmalloc(bf->bit_size / CHAR_BIT);
- read_in_full(fd, bf->bits, bf->bit_size / CHAR_BIT);
+ bf->bits = xmalloc(bf->commit_nr * bf->bit_size / CHAR_BIT);
+ read_in_full(fd, bf->bits, bf->commit_nr * bf->bit_size / CHAR_BIT);
close(fd);
@@ -96,8 +100,9 @@ void bloom_filter_write(struct bloom_filter *bf)
int fd = xopen(git_path_bloom(), O_WRONLY | O_CREAT | O_TRUNC, 0666);
write_in_full(fd, >nr_entries, sizeof(bf->nr_entries));
+ write_in_full(fd, >commit_nr, sizeof(bf->commit_nr));
write_in_full(fd, >bit_size, sizeof(bf->bit_size));
- write_in_full(fd, bf->bits, bf->bit_size / CHAR_BIT);
+ write_in_full(fd, bf->bits, bf->commit_nr * bf->bit_size / CHAR_BIT);
close(fd);
}
diff --git a/bloom-filter.h b/bloom-filter.h
index 94d0af1708..607649b8db 100644
--- a/bloom-filter.h
+++ b/bloom-filter.h
@@ -5,30 +5,26 @@
struct bloom_filter {
uint32_t nr_entries;
+ uint32_t commit_nr;
uint32_t bit_size;
unsigned char *bits;
};
-void bloom_filter_init(struct bloom_filter *bf, uint32_t bit_size);
+void