32 void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,  in hashmap__init()  argument
35 	map->hash_fn = hash_fn;  in hashmap__init()
36 	map->equal_fn = equal_fn;  in hashmap__init()
37 	map->ctx = ctx;  in hashmap__init()
39 	map->buckets = NULL;  in hashmap__init()
40 	map->cap = 0;  in hashmap__init()
41 	map->cap_bits = 0;  in hashmap__init()
42 	map->sz = 0;  in hashmap__init()
49 	struct hashmap *map = malloc(sizeof(struct hashmap));  in hashmap__new()  local
51 	if (!map)  in hashmap__new()
53 	hashmap__init(map, hash_fn, equal_fn, ctx);  in hashmap__new()
54 	return map;  in hashmap__new()
57 void hashmap__clear(struct hashmap *map)  in hashmap__clear()  argument
59 	free(map->buckets);  in hashmap__clear()
60 	map->cap = map->cap_bits = map->sz = 0;  in hashmap__clear()
63 void hashmap__free(struct hashmap *map)  in hashmap__free()  argument
65 	if (!map)  in hashmap__free()
68 	hashmap__clear(map);  in hashmap__free()
69 	free(map);  in hashmap__free()
72 size_t hashmap__size(const struct hashmap *map)  in hashmap__size()  argument
74 	return map->sz;  in hashmap__size()
77 size_t hashmap__capacity(const struct hashmap *map)  in hashmap__capacity()  argument
79 	return map->cap;  in hashmap__capacity()
82 static bool hashmap_needs_to_grow(struct hashmap *map)  in hashmap_needs_to_grow()  argument
85 	return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap);  in hashmap_needs_to_grow()
88 static int hashmap_grow(struct hashmap *map)  in hashmap_grow()  argument
96 	new_cap_bits = map->cap_bits + 1;  in hashmap_grow()
105 	hashmap__for_each_entry_safe(map, cur, tmp, bkt) {  in hashmap_grow()
106 		h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits);  in hashmap_grow()
110 	map->cap = new_cap;  in hashmap_grow()
111 	map->cap_bits = new_cap_bits;  in hashmap_grow()
112 	free(map->buckets);  in hashmap_grow()
113 	map->buckets = new_buckets;  in hashmap_grow()
118 static bool hashmap_find_entry(const struct hashmap *map,  in hashmap_find_entry()  argument
125 	if (!map->buckets)  in hashmap_find_entry()
128 	for (prev_ptr = &map->buckets[hash], cur = *prev_ptr;  in hashmap_find_entry()
131 		if (map->equal_fn(cur->key, key, map->ctx)) {  in hashmap_find_entry()
142 int hashmap__insert(struct hashmap *map, const void *key, void *value,  in hashmap__insert()  argument
155 	h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);  in hashmap__insert()
157 	    hashmap_find_entry(map, key, h, NULL, &entry)) {  in hashmap__insert()
175 	if (hashmap_needs_to_grow(map)) {  in hashmap__insert()
176 		err = hashmap_grow(map);  in hashmap__insert()
179 		h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);  in hashmap__insert()
188 	hashmap_add_entry(&map->buckets[h], entry);  in hashmap__insert()
189 	map->sz++;  in hashmap__insert()
194 bool hashmap__find(const struct hashmap *map, const void *key, void **value)  in hashmap__find()  argument
199 	h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);  in hashmap__find()
200 	if (!hashmap_find_entry(map, key, h, NULL, &entry))  in hashmap__find()
208 bool hashmap__delete(struct hashmap *map, const void *key,  in hashmap__delete()  argument
214 	h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);  in hashmap__delete()
215 	if (!hashmap_find_entry(map, key, h, &pprev, &entry))  in hashmap__delete()
225 	map->sz--;  in hashmap__delete()