[thirdparty/git.git] / hashmap.c

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

#define FNV32_BASE ((unsigned int) 0x811c9dc5)
#define FNV32_PRIME ((unsigned int) 0x01000193)

unsigned int strhash(const char *str)
{
	unsigned int c, hash = FNV32_BASE;
	while ((c = (unsigned char) *str++))
		hash = (hash * FNV32_PRIME) ^ c;
	return hash;
}

unsigned int strihash(const char *str)
{
	unsigned int c, hash = FNV32_BASE;
	while ((c = (unsigned char) *str++)) {
		if (c >= 'a' && c <= 'z')
			c -= 'a' - 'A';
		hash = (hash * FNV32_PRIME) ^ c;
	}
	return hash;
}

unsigned int memhash(const void *buf, size_t len)
{
	unsigned int hash = FNV32_BASE;
	unsigned char *ucbuf = (unsigned char *) buf;
	while (len--) {
		unsigned int c = *ucbuf++;
		hash = (hash * FNV32_PRIME) ^ c;
	}
	return hash;
}

unsigned int memihash(const void *buf, size_t len)
{
	unsigned int hash = FNV32_BASE;
	unsigned char *ucbuf = (unsigned char *) buf;
	while (len--) {
		unsigned int c = *ucbuf++;
		if (c >= 'a' && c <= 'z')
			c -= 'a' - 'A';
		hash = (hash * FNV32_PRIME) ^ c;
	}
	return hash;
}

/*
 * Incorporate another chunk of data into a memihash
 * computation.
 */
unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)
{
	unsigned int hash = hash_seed;
	unsigned char *ucbuf = (unsigned char *) buf;
	while (len--) {
		unsigned int c = *ucbuf++;
		if (c >= 'a' && c <= 'z')
			c -= 'a' - 'A';
		hash = (hash * FNV32_PRIME) ^ c;
	}
	return hash;
}

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

static void alloc_table(struct hashmap *map, unsigned int size)
{
	map->tablesize = size;
	map->table = xcalloc(size, sizeof(struct hashmap_entry *));

	/* calculate resize thresholds for new size */
	map->grow_at = (unsigned int) ((uint64_t) size * HASHMAP_LOAD_FACTOR / 100);
	if (size <= HASHMAP_INITIAL_SIZE)
		map->shrink_at = 0;
	else
		/*
		 * The shrink-threshold must be slightly smaller than
		 * (grow-threshold / resize-factor) to prevent erratic resizing,
		 * thus we divide by (resize-factor + 1).
		 */
		map->shrink_at = map->grow_at / ((1 << HASHMAP_RESIZE_BITS) + 1);
}

static inline int entry_equals(const struct hashmap *map,
			       const struct hashmap_entry *e1,
			       const struct hashmap_entry *e2,
			       const void *keydata)
{
	return (e1 == e2) ||
	       (e1->hash == e2->hash &&
		!map->cmpfn(map->cmpfn_data, e1, e2, keydata));
}

static inline unsigned int bucket(const struct hashmap *map,
				  const struct hashmap_entry *key)
{
	return key->hash & (map->tablesize - 1);
}

int hashmap_bucket(const struct hashmap *map, unsigned int hash)
{
	return hash & (map->tablesize - 1);
}

static void rehash(struct hashmap *map, unsigned int newsize)
{
	/* map->table MUST NOT be NULL when this function is called */
	unsigned int i, oldsize = map->tablesize;
	struct hashmap_entry **oldtable = map->table;

	alloc_table(map, newsize);
	for (i = 0; i < oldsize; i++) {
		struct hashmap_entry *e = oldtable[i];
		while (e) {
			struct hashmap_entry *next = e->next;
			unsigned int b = bucket(map, e);
			e->next = map->table[b];
			map->table[b] = e;
			e = next;
		}
	}
	free(oldtable);
}

static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map,
		const struct hashmap_entry *key, const void *keydata)
{
	/* map->table MUST NOT be NULL when this function is called */
	struct hashmap_entry **e = &map->table[bucket(map, key)];
	while (*e && !entry_equals(map, *e, key, keydata))
		e = &(*e)->next;
	return e;
}

static int always_equal(const void *unused_cmp_data,
			const struct hashmap_entry *unused1,
			const struct hashmap_entry *unused2,
			const void *unused_keydata)
{
	return 0;
}

void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,
		  const void *cmpfn_data, size_t initial_size)
{
	unsigned int size = HASHMAP_INITIAL_SIZE;

	memset(map, 0, sizeof(*map));

	map->cmpfn = equals_function ? equals_function : always_equal;
	map->cmpfn_data = cmpfn_data;

	/* calculate initial table size and allocate the table */
	initial_size = (unsigned int) ((uint64_t) initial_size * 100
			/ HASHMAP_LOAD_FACTOR);
	while (initial_size > size)
		size <<= HASHMAP_RESIZE_BITS;
	alloc_table(map, size);

	/*
	 * Keep track of the number of items in the map and
	 * allow the map to automatically grow as necessary.
	 */
	map->do_count_items = 1;
}

static void free_individual_entries(struct hashmap *map, ssize_t entry_offset)
{
	struct hashmap_iter iter;
	struct hashmap_entry *e;

	hashmap_iter_init(map, &iter);
	while ((e = hashmap_iter_next(&iter)))
		/*
		 * like container_of, but using caller-calculated
		 * offset (caller being hashmap_clear_and_free)
		 */
		free((char *)e - entry_offset);
}

void hashmap_partial_clear_(struct hashmap *map, ssize_t entry_offset)
{
	if (!map || !map->table)
		return;
	if (entry_offset >= 0)  /* called by hashmap_clear_entries */
		free_individual_entries(map, entry_offset);
	memset(map->table, 0, map->tablesize * sizeof(struct hashmap_entry *));
	map->shrink_at = 0;
	map->private_size = 0;
}

void hashmap_clear_(struct hashmap *map, ssize_t entry_offset)
{
	if (!map || !map->table)
		return;
	if (entry_offset >= 0)  /* called by hashmap_clear_and_free */
		free_individual_entries(map, entry_offset);
	free(map->table);
	memset(map, 0, sizeof(*map));
}

struct hashmap_entry *hashmap_get(const struct hashmap *map,
				const struct hashmap_entry *key,
				const void *keydata)
{
	if (!map->table)
		return NULL;
	return *find_entry_ptr(map, key, keydata);
}

struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
				       const struct hashmap_entry *entry)
{
	struct hashmap_entry *e = entry->next;
	for (; e; e = e->next)
		if (entry_equals(map, entry, e, NULL))
			return e;
	return NULL;
}

void hashmap_add(struct hashmap *map, struct hashmap_entry *entry)
{
	unsigned int b;

	if (!map->table)
		alloc_table(map, HASHMAP_INITIAL_SIZE);

	b = bucket(map, entry);
	/* add entry */
	entry->next = map->table[b];
	map->table[b] = entry;

	/* fix size and rehash if appropriate */
	if (map->do_count_items) {
		map->private_size++;
		if (map->private_size > map->grow_at)
			rehash(map, map->tablesize << HASHMAP_RESIZE_BITS);
	}
}

struct hashmap_entry *hashmap_remove(struct hashmap *map,
				     const struct hashmap_entry *key,
				     const void *keydata)
{
	struct hashmap_entry *old;
	struct hashmap_entry **e;

	if (!map->table)
		return NULL;
	e = find_entry_ptr(map, key, keydata);
	if (!*e)
		return NULL;

	/* remove existing entry */
	old = *e;
	*e = old->next;
	old->next = NULL;

	/* fix size and rehash if appropriate */
	if (map->do_count_items) {
		map->private_size--;
		if (map->private_size < map->shrink_at)
			rehash(map, map->tablesize >> HASHMAP_RESIZE_BITS);
	}

	return old;
}

struct hashmap_entry *hashmap_put(struct hashmap *map,
				  struct hashmap_entry *entry)
{
	struct hashmap_entry *old = hashmap_remove(map, entry, NULL);
	hashmap_add(map, entry);
	return old;
}

void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)
{
	iter->map = map;
	iter->tablepos = 0;
	iter->next = NULL;
}

struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter)
{
	struct hashmap_entry *current = iter->next;
	for (;;) {
		if (current) {
			iter->next = current->next;
			return current;
		}

		if (iter->tablepos >= iter->map->tablesize)
			return NULL;

		current = iter->map->table[iter->tablepos++];
	}
}

struct pool_entry {
	struct hashmap_entry ent;
	size_t len;
	unsigned char data[FLEX_ARRAY];
};

static int pool_entry_cmp(const void *unused_cmp_data,
			  const struct hashmap_entry *eptr,
			  const struct hashmap_entry *entry_or_key,
			  const void *keydata)
{
	const struct pool_entry *e1, *e2;

	e1 = container_of(eptr, const struct pool_entry, ent);
	e2 = container_of(entry_or_key, const struct pool_entry, ent);

	return e1->data != keydata &&
	       (e1->len != e2->len || memcmp(e1->data, keydata, e1->len));
}

const void *memintern(const void *data, size_t len)
{
	static struct hashmap map;
	struct pool_entry key, *e;

	/* initialize string pool hashmap */
	if (!map.tablesize)
		hashmap_init(&map, pool_entry_cmp, NULL, 0);

	/* lookup interned string in pool */
	hashmap_entry_init(&key.ent, memhash(data, len));
	key.len = len;
	e = hashmap_get_entry(&map, &key, ent, data);
	if (!e) {
		/* not found: create it */
		FLEX_ALLOC_MEM(e, data, data, len);
		hashmap_entry_init(&e->ent, key.ent.hash);
		e->len = len;
		hashmap_add(&map, &e->ent);
	}
	return e->data;
}
Commit	Line	Data
6a364ced KB	1	/*
	2	* Generic implementation of hash-based key value mappings.
	3	*/
	4	#include "cache.h"
	5	#include "hashmap.h"
	6
	7	#define FNV32_BASE ((unsigned int) 0x811c9dc5)
	8	#define FNV32_PRIME ((unsigned int) 0x01000193)
	9
	10	unsigned int strhash(const char *str)
	11	{
	12	unsigned int c, hash = FNV32_BASE;
	13	while ((c = (unsigned char) *str++))
	14	hash = (hash * FNV32_PRIME) ^ c;
	15	return hash;
	16	}
	17
	18	unsigned int strihash(const char *str)
	19	{
	20	unsigned int c, hash = FNV32_BASE;
	21	while ((c = (unsigned char) *str++)) {
	22	if (c >= 'a' && c <= 'z')
	23	c -= 'a' - 'A';
	24	hash = (hash * FNV32_PRIME) ^ c;
	25	}
	26	return hash;
	27	}
	28
	29	unsigned int memhash(const void *buf, size_t len)
	30	{
	31	unsigned int hash = FNV32_BASE;
	32	unsigned char ucbuf = (unsigned char ) buf;
	33	while (len--) {
	34	unsigned int c = *ucbuf++;
	35	hash = (hash * FNV32_PRIME) ^ c;
	36	}
	37	return hash;
	38	}
	39
	40	unsigned int memihash(const void *buf, size_t len)
	41	{
	42	unsigned int hash = FNV32_BASE;
	43	unsigned char ucbuf = (unsigned char ) buf;
	44	while (len--) {
	45	unsigned int c = *ucbuf++;
	46	if (c >= 'a' && c <= 'z')
	47	c -= 'a' - 'A';
	48	hash = (hash * FNV32_PRIME) ^ c;
	49	}
	50	return hash;
	51	}
	52
f75619bd	53	/*
15beaaa3	54	* Incorporate another chunk of data into a memihash
f75619bd JH	55	* computation.
	56	*/
	57	unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)
	58	{
	59	unsigned int hash = hash_seed;
	60	unsigned char ucbuf = (unsigned char ) buf;
	61	while (len--) {
	62	unsigned int c = *ucbuf++;
	63	if (c >= 'a' && c <= 'z')
	64	c -= 'a' - 'A';
	65	hash = (hash * FNV32_PRIME) ^ c;
	66	}
	67	return hash;
	68	}
	69
6a364ced KB	70	#define HASHMAP_INITIAL_SIZE 64
	71	/* grow / shrink by 2^2 */
	72	#define HASHMAP_RESIZE_BITS 2
	73	/* load factor in percent */
	74	#define HASHMAP_LOAD_FACTOR 80
	75
	76	static void alloc_table(struct hashmap *map, unsigned int size)
	77	{
	78	map->tablesize = size;
	79	map->table = xcalloc(size, sizeof(struct hashmap_entry *));
	80
	81	/* calculate resize thresholds for new size */
	82	map->grow_at = (unsigned int) ((uint64_t) size * HASHMAP_LOAD_FACTOR / 100);
	83	if (size <= HASHMAP_INITIAL_SIZE)
	84	map->shrink_at = 0;
	85	else
	86	/*
	87	* The shrink-threshold must be slightly smaller than
	88	* (grow-threshold / resize-factor) to prevent erratic resizing,
	89	* thus we divide by (resize-factor + 1).
	90	*/
	91	map->shrink_at = map->grow_at / ((1 << HASHMAP_RESIZE_BITS) + 1);
	92	}
	93
	94	static inline int entry_equals(const struct hashmap *map,
97a39a4a EN	95	const struct hashmap_entry *e1,
	96	const struct hashmap_entry *e2,
	97	const void *keydata)
6a364ced	98	{
7663cdc8 SB	99	return (e1 == e2) \|\|
	100	(e1->hash == e2->hash &&
	101	!map->cmpfn(map->cmpfn_data, e1, e2, keydata));
6a364ced KB	102	}
	103
	104	static inline unsigned int bucket(const struct hashmap *map,
97a39a4a	105	const struct hashmap_entry *key)
6a364ced KB	106	{
	107	return key->hash & (map->tablesize - 1);
	108	}
	109
0607e100 JH	110	int hashmap_bucket(const struct hashmap *map, unsigned int hash)
	111	{
	112	return hash & (map->tablesize - 1);
	113	}
	114
6a364ced KB	115	static void rehash(struct hashmap *map, unsigned int newsize)
6a364ced KB	116	{
b7879b0b	117	/* map->table MUST NOT be NULL when this function is called */
6a364ced KB	118	unsigned int i, oldsize = map->tablesize;
	119	struct hashmap_entry **oldtable = map->table;
	120
	121	alloc_table(map, newsize);
	122	for (i = 0; i < oldsize; i++) {
	123	struct hashmap_entry *e = oldtable[i];
	124	while (e) {
	125	struct hashmap_entry *next = e->next;
	126	unsigned int b = bucket(map, e);
	127	e->next = map->table[b];
	128	map->table[b] = e;
	129	e = next;
	130	}
	131	}
	132	free(oldtable);
	133	}
	134
	135	static inline struct hashmap_entry *find_entry_ptr(const struct hashmap map,
	136	const struct hashmap_entry key, const void keydata)
	137	{
b7879b0b	138	/* map->table MUST NOT be NULL when this function is called */
6a364ced KB	139	struct hashmap_entry **e = &map->table[bucket(map, key)];
	140	while (e && !entry_equals(map, e, key, keydata))
	141	e = &(*e)->next;
	142	return e;
	143	}
	144
7663cdc8	145	static int always_equal(const void *unused_cmp_data,
939af16e EW	146	const struct hashmap_entry *unused1,
939af16e EW	147	const struct hashmap_entry *unused2,
7663cdc8	148	const void *unused_keydata)
6a364ced KB	149	{
	150	return 0;
	151	}
	152
	153	void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,
97a39a4a	154	const void *cmpfn_data, size_t initial_size)
6a364ced KB	155	{
6a364ced KB	156	unsigned int size = HASHMAP_INITIAL_SIZE;
0607e100 JH	157
	158	memset(map, 0, sizeof(*map));
	159
6a364ced	160	map->cmpfn = equals_function ? equals_function : always_equal;
7663cdc8	161	map->cmpfn_data = cmpfn_data;
6a364ced KB	162
	163	/* calculate initial table size and allocate the table */
	164	initial_size = (unsigned int) ((uint64_t) initial_size * 100
	165	/ HASHMAP_LOAD_FACTOR);
	166	while (initial_size > size)
	167	size <<= HASHMAP_RESIZE_BITS;
	168	alloc_table(map, size);
8b604d19 JH	169
	170	/*
	171	* Keep track of the number of items in the map and
	172	* allow the map to automatically grow as necessary.
	173	*/
	174	map->do_count_items = 1;
6a364ced KB	175	}
6a364ced KB	176
33f20d82 EN	177	static void free_individual_entries(struct hashmap *map, ssize_t entry_offset)
	178	{
	179	struct hashmap_iter iter;
	180	struct hashmap_entry *e;
	181
	182	hashmap_iter_init(map, &iter);
	183	while ((e = hashmap_iter_next(&iter)))
	184	/*
	185	* like container_of, but using caller-calculated
6da1a258	186	* offset (caller being hashmap_clear_and_free)
33f20d82 EN	187	*/
	188	free((char *)e - entry_offset);
	189	}
	190
	191	void hashmap_partial_clear_(struct hashmap *map, ssize_t entry_offset)
	192	{
	193	if (!map \|\| !map->table)
	194	return;
	195	if (entry_offset >= 0) /* called by hashmap_clear_entries */
	196	free_individual_entries(map, entry_offset);
	197	memset(map->table, 0, map->tablesize * sizeof(struct hashmap_entry *));
	198	map->shrink_at = 0;
	199	map->private_size = 0;
	200	}
	201
6da1a258	202	void hashmap_clear_(struct hashmap *map, ssize_t entry_offset)
6a364ced KB	203	{
	204	if (!map \|\| !map->table)
	205	return;
6da1a258	206	if (entry_offset >= 0) /* called by hashmap_clear_and_free */
33f20d82	207	free_individual_entries(map, entry_offset);
6a364ced KB	208	free(map->table);
	209	memset(map, 0, sizeof(*map));
	210	}
	211
f23a4651 EW	212	struct hashmap_entry hashmap_get(const struct hashmap map,
	213	const struct hashmap_entry *key,
	214	const void *keydata)
6a364ced	215	{
b7879b0b EN	216	if (!map->table)
b7879b0b EN	217	return NULL;
6a364ced KB	218	return *find_entry_ptr(map, key, keydata);
	219	}
	220
6bcbdfb2	221	struct hashmap_entry hashmap_get_next(const struct hashmap map,
97a39a4a	222	const struct hashmap_entry *entry)
6a364ced	223	{
f6eb6bdc	224	struct hashmap_entry *e = entry->next;
6a364ced KB	225	for (; e; e = e->next)
	226	if (entry_equals(map, entry, e, NULL))
	227	return e;
	228	return NULL;
	229	}
	230
b94e5c1d	231	void hashmap_add(struct hashmap map, struct hashmap_entry entry)
6a364ced	232	{
b7879b0b	233	unsigned int b;
6a364ced	234
b7879b0b EN	235	if (!map->table)
	236	alloc_table(map, HASHMAP_INITIAL_SIZE);
	237
	238	b = bucket(map, entry);
6a364ced	239	/* add entry */
b94e5c1d	240	entry->next = map->table[b];
6a364ced KB	241	map->table[b] = entry;
	242
	243	/* fix size and rehash if appropriate */
8b604d19 JH	244	if (map->do_count_items) {
	245	map->private_size++;
	246	if (map->private_size > map->grow_at)
	247	rehash(map, map->tablesize << HASHMAP_RESIZE_BITS);
	248	}
6a364ced KB	249	}
6a364ced KB	250
8a973d0b	251	struct hashmap_entry hashmap_remove(struct hashmap map,
97a39a4a EN	252	const struct hashmap_entry *key,
97a39a4a EN	253	const void *keydata)
6a364ced KB	254	{
6a364ced KB	255	struct hashmap_entry *old;
b7879b0b EN	256	struct hashmap_entry **e;
	257
	258	if (!map->table)
	259	return NULL;
	260	e = find_entry_ptr(map, key, keydata);
6a364ced KB	261	if (!*e)
	262	return NULL;
	263
	264	/* remove existing entry */
	265	old = *e;
	266	*e = old->next;
	267	old->next = NULL;
	268
	269	/* fix size and rehash if appropriate */
8b604d19 JH	270	if (map->do_count_items) {
	271	map->private_size--;
	272	if (map->private_size < map->shrink_at)
	273	rehash(map, map->tablesize >> HASHMAP_RESIZE_BITS);
	274	}
	275
6a364ced KB	276	return old;
	277	}
	278
8a973d0b	279	struct hashmap_entry hashmap_put(struct hashmap map,
97a39a4a	280	struct hashmap_entry *entry)
6a364ced KB	281	{
	282	struct hashmap_entry *old = hashmap_remove(map, entry, NULL);
	283	hashmap_add(map, entry);
	284	return old;
	285	}
	286
	287	void hashmap_iter_init(struct hashmap map, struct hashmap_iter iter)
	288	{
	289	iter->map = map;
	290	iter->tablepos = 0;
	291	iter->next = NULL;
	292	}
	293
87571c3f	294	struct hashmap_entry hashmap_iter_next(struct hashmap_iter iter)
6a364ced KB	295	{
	296	struct hashmap_entry *current = iter->next;
	297	for (;;) {
	298	if (current) {
	299	iter->next = current->next;
	300	return current;
	301	}
	302
	303	if (iter->tablepos >= iter->map->tablesize)
	304	return NULL;
	305
	306	current = iter->map->table[iter->tablepos++];
	307	}
	308	}
7b64d42d KB	309
	310	struct pool_entry {
	311	struct hashmap_entry ent;
	312	size_t len;
	313	unsigned char data[FLEX_ARRAY];
	314	};
	315
7663cdc8	316	static int pool_entry_cmp(const void *unused_cmp_data,
939af16e EW	317	const struct hashmap_entry *eptr,
	318	const struct hashmap_entry *entry_or_key,
	319	const void *keydata)
7b64d42d	320	{
939af16e EW	321	const struct pool_entry e1, e2;
	322
	323	e1 = container_of(eptr, const struct pool_entry, ent);
	324	e2 = container_of(entry_or_key, const struct pool_entry, ent);
	325
7b64d42d KB	326	return e1->data != keydata &&
	327	(e1->len != e2->len \|\| memcmp(e1->data, keydata, e1->len));
	328	}
	329
	330	const void memintern(const void data, size_t len)
	331	{
	332	static struct hashmap map;
	333	struct pool_entry key, *e;
	334
	335	/* initialize string pool hashmap */
	336	if (!map.tablesize)
939af16e	337	hashmap_init(&map, pool_entry_cmp, NULL, 0);
7b64d42d KB	338
7b64d42d KB	339	/* lookup interned string in pool */
d22245a2	340	hashmap_entry_init(&key.ent, memhash(data, len));
7b64d42d	341	key.len = len;
404ab78e	342	e = hashmap_get_entry(&map, &key, ent, data);
7b64d42d KB	343	if (!e) {
7b64d42d KB	344	/* not found: create it */
96ffc06f	345	FLEX_ALLOC_MEM(e, data, data, len);
d22245a2	346	hashmap_entry_init(&e->ent, key.ent.hash);
7b64d42d	347	e->len = len;
b94e5c1d	348	hashmap_add(&map, &e->ent);
7b64d42d KB	349	}
	350	return e->data;
	351	}