perf/util/hashmap.c

4  * Generic non-thread safe hash map implementation.
38 void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
41 	map->hash_fn = hash_fn;
42 	map->equal_fn = equal_fn;
43 	map->ctx = ctx;
45 	map->buckets = NULL;
46 	map->cap = 0;
47 	map->cap_bits = 0;
48 	map->sz = 0;
55 	struct hashmap *map = malloc(sizeof(struct hashmap));
57 	if (!map)
59 	hashmap__init(map, hash_fn, equal_fn, ctx);
60 	return map;
63 void hashmap__clear(struct hashmap *map)
68 	hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
71 	free(map->buckets);
72 	map->buckets = NULL;
73 	map->cap = map->cap_bits = map->sz = 0;
76 void hashmap__free(struct hashmap *map)
78 	if (IS_ERR_OR_NULL(map))
81 	hashmap__clear(map);
82 	free(map);
85 size_t hashmap__size(const struct hashmap *map)
87 	return map->sz;
90 size_t hashmap__capacity(const struct hashmap *map)
92 	return map->cap;
95 static bool hashmap_needs_to_grow(struct hashmap *map)
98 	return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap);
101 static int hashmap_grow(struct hashmap *map)
108 	new_cap_bits = map->cap_bits + 1;
117 	hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
118 		h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits);
122 	map->cap = new_cap;
123 	map->cap_bits = new_cap_bits;
124 	free(map->buckets);
125 	map->buckets = new_buckets;
130 static bool hashmap_find_entry(const struct hashmap *map,
137 	if (!map->buckets)
140 	for (prev_ptr = &map->buckets[hash], cur = *prev_ptr;
143 		if (map->equal_fn(cur->key, key, map->ctx)) {
154 int hashmap_insert(struct hashmap *map, long key, long value,
167 	h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
169 	    hashmap_find_entry(map, key, h, NULL, &entry)) {
187 	if (hashmap_needs_to_grow(map)) {
188 		err = hashmap_grow(map);
191 		h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
200 	hashmap_add_entry(&map->buckets[h], entry);
201 	map->sz++;
206 bool hashmap_find(const struct hashmap *map, long key, long *value)
211 	h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
212 	if (!hashmap_find_entry(map, key, h, NULL, &entry))
220 bool hashmap_delete(struct hashmap *map, long key,
226 	h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
227 	if (!hashmap_find_entry(map, key, h, &pprev, &entry))
237 	map->sz--;