git/bloom.c

#include "git-compat-util.h"
#include "bloom.h"
#include "diff.h"
#include "diffcore.h"
#include "hashmap.h"
#include "commit-graph.h"
#include "commit.h"
#include "commit-slab.h"
#include "tree.h"
#include "tree-walk.h"
#include "config.h"
#include "repository.h"

define_commit_slab(bloom_filter_slab, struct bloom_filter);

static struct bloom_filter_slab bloom_filters;

struct pathmap_hash_entry { … };

static uint32_t rotate_left(uint32_t value, int32_t count)
{ … }

static inline unsigned char get_bitmask(uint32_t pos)
{ … }

static int check_bloom_offset(struct commit_graph *g, uint32_t pos,
			      uint32_t offset)
{ … }

int load_bloom_filter_from_graph(struct commit_graph *g,
				 struct bloom_filter *filter,
				 uint32_t graph_pos)
{ … }

/*
 * Calculate the murmur3 32-bit hash value for the given data
 * using the given seed.
 * Produces a uniformly distributed hash value.
 * Not considered to be cryptographically secure.
 * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
 */
uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len)
{ … }

static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len)
{ … }

void fill_bloom_key(const char *data,
		    size_t len,
		    struct bloom_key *key,
		    const struct bloom_filter_settings *settings)
{ … }

void clear_bloom_key(struct bloom_key *key)
{ … }

void add_key_to_filter(const struct bloom_key *key,
		       struct bloom_filter *filter,
		       const struct bloom_filter_settings *settings)
{ … }

void init_bloom_filters(void)
{ … }

static void free_one_bloom_filter(struct bloom_filter *filter)
{ … }

void deinit_bloom_filters(void)
{ … }

static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,
		       const struct hashmap_entry *eptr,
		       const struct hashmap_entry *entry_or_key,
		       const void *keydata UNUSED)
{ … }

static void init_truncated_large_filter(struct bloom_filter *filter,
					int version)
{ … }

#define VISITED …
#define HIGH_BITS …

static int has_entries_with_high_bit(struct repository *r, struct tree *t)
{ … }

static int commit_tree_has_high_bit_paths(struct repository *r,
					  struct commit *c)
{ … }

static struct bloom_filter *upgrade_filter(struct repository *r, struct commit *c,
					   struct bloom_filter *filter,
					   int hash_version)
{ … }

struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)
{ … }

struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
						 struct commit *c,
						 int compute_if_not_present,
						 const struct bloom_filter_settings *settings,
						 enum bloom_filter_computed *computed)
{ … }

int bloom_filter_contains(const struct bloom_filter *filter,
			  const struct bloom_key *key,
			  const struct bloom_filter_settings *settings)
{ … }