git/hashmap.c

/*
 * Generic implementation of hash-based key value mappings.
 */
#include "git-compat-util.h"
#include "hashmap.h"

#define FNV32_BASE …
#define FNV32_PRIME …

unsigned int strhash(const char *str)
{ … }

unsigned int strihash(const char *str)
{ … }

unsigned int memhash(const void *buf, size_t len)
{ … }

unsigned int memihash(const void *buf, size_t len)
{ … }

/*
 * Incorporate another chunk of data into a memihash
 * computation.
 */
unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)
{ … }

#define HASHMAP_INITIAL_SIZE …
/* grow / shrink by 2^2 */
#define HASHMAP_RESIZE_BITS …
/* load factor in percent */
#define HASHMAP_LOAD_FACTOR …

static void alloc_table(struct hashmap *map, unsigned int size)
{ … }

static inline int entry_equals(const struct hashmap *map,
			       const struct hashmap_entry *e1,
			       const struct hashmap_entry *e2,
			       const void *keydata)
{ … }

static inline unsigned int bucket(const struct hashmap *map,
				  const struct hashmap_entry *key)
{ … }

int hashmap_bucket(const struct hashmap *map, unsigned int hash)
{ … }

static void rehash(struct hashmap *map, unsigned int newsize)
{ … }

static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map,
		const struct hashmap_entry *key, const void *keydata)
{ … }

static int always_equal(const void *cmp_data UNUSED,
			const struct hashmap_entry *entry1 UNUSED,
			const struct hashmap_entry *entry2 UNUSED,
			const void *keydata UNUSED)
{ … }

void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,
		  const void *cmpfn_data, size_t initial_size)
{ … }

static void free_individual_entries(struct hashmap *map, ssize_t entry_offset)
{ … }

void hashmap_partial_clear_(struct hashmap *map, ssize_t entry_offset)
{ … }

void hashmap_clear_(struct hashmap *map, ssize_t entry_offset)
{ … }

struct hashmap_entry *hashmap_get(const struct hashmap *map,
				const struct hashmap_entry *key,
				const void *keydata)
{ … }

struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
				       const struct hashmap_entry *entry)
{ … }

void hashmap_add(struct hashmap *map, struct hashmap_entry *entry)
{ … }

struct hashmap_entry *hashmap_remove(struct hashmap *map,
				     const struct hashmap_entry *key,
				     const void *keydata)
{ … }

struct hashmap_entry *hashmap_put(struct hashmap *map,
				  struct hashmap_entry *entry)
{ … }

void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)
{ … }

struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter)
{ … }

struct pool_entry { … };

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

const void *memintern(const void *data, size_t len)
{ … }