1 // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
4 * Generic non-thread safe hash map implementation.
6 * Copyright (c) 2019 Facebook
12 #include <linux/err.h>
15 /* make sure libbpf doesn't use kernel-only integer typedefs */
16 #pragma GCC poison u8 u16 u32 u64 s8 s16 s32 s64
18 /* start with 4 buckets */
19 #define HASHMAP_MIN_CAP_BITS 2
21 static void hashmap_add_entry(struct hashmap_entry **pprev,
22 struct hashmap_entry *entry)
28 static void hashmap_del_entry(struct hashmap_entry **pprev,
29 struct hashmap_entry *entry)
35 void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
36 hashmap_equal_fn equal_fn, void *ctx)
38 map->hash_fn = hash_fn;
39 map->equal_fn = equal_fn;
48 struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
49 hashmap_equal_fn equal_fn,
52 struct hashmap *map = malloc(sizeof(struct hashmap));
55 return ERR_PTR(-ENOMEM);
56 hashmap__init(map, hash_fn, equal_fn, ctx);
60 void hashmap__clear(struct hashmap *map)
62 struct hashmap_entry *cur, *tmp;
65 hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
70 map->cap = map->cap_bits = map->sz = 0;
73 void hashmap__free(struct hashmap *map)
82 size_t hashmap__size(const struct hashmap *map)
87 size_t hashmap__capacity(const struct hashmap *map)
92 static bool hashmap_needs_to_grow(struct hashmap *map)
94 /* grow if empty or more than 75% filled */
95 return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap);
98 static int hashmap_grow(struct hashmap *map)
100 struct hashmap_entry **new_buckets;
101 struct hashmap_entry *cur, *tmp;
102 size_t new_cap_bits, new_cap;
105 new_cap_bits = map->cap_bits + 1;
106 if (new_cap_bits < HASHMAP_MIN_CAP_BITS)
107 new_cap_bits = HASHMAP_MIN_CAP_BITS;
109 new_cap = 1UL << new_cap_bits;
110 new_buckets = calloc(new_cap, sizeof(new_buckets[0]));
114 hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
115 h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits);
116 hashmap_add_entry(&new_buckets[h], cur);
120 map->cap_bits = new_cap_bits;
122 map->buckets = new_buckets;
127 static bool hashmap_find_entry(const struct hashmap *map,
128 const void *key, size_t hash,
129 struct hashmap_entry ***pprev,
130 struct hashmap_entry **entry)
132 struct hashmap_entry *cur, **prev_ptr;
137 for (prev_ptr = &map->buckets[hash], cur = *prev_ptr;
139 prev_ptr = &cur->next, cur = cur->next) {
140 if (map->equal_fn(cur->key, key, map->ctx)) {
151 int hashmap__insert(struct hashmap *map, const void *key, void *value,
152 enum hashmap_insert_strategy strategy,
153 const void **old_key, void **old_value)
155 struct hashmap_entry *entry;
164 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
165 if (strategy != HASHMAP_APPEND &&
166 hashmap_find_entry(map, key, h, NULL, &entry)) {
168 *old_key = entry->key;
170 *old_value = entry->value;
172 if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) {
174 entry->value = value;
176 } else if (strategy == HASHMAP_ADD) {
181 if (strategy == HASHMAP_UPDATE)
184 if (hashmap_needs_to_grow(map)) {
185 err = hashmap_grow(map);
188 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
191 entry = malloc(sizeof(struct hashmap_entry));
196 entry->value = value;
197 hashmap_add_entry(&map->buckets[h], entry);
203 bool hashmap__find(const struct hashmap *map, const void *key, void **value)
205 struct hashmap_entry *entry;
208 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
209 if (!hashmap_find_entry(map, key, h, NULL, &entry))
213 *value = entry->value;
217 bool hashmap__delete(struct hashmap *map, const void *key,
218 const void **old_key, void **old_value)
220 struct hashmap_entry **pprev, *entry;
223 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
224 if (!hashmap_find_entry(map, key, h, &pprev, &entry))
228 *old_key = entry->key;
230 *old_value = entry->value;
232 hashmap_del_entry(pprev, entry);