1e3b92422SAndrii Nakryiko // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
2e3b92422SAndrii Nakryiko
3e3b92422SAndrii Nakryiko /*
4e3b92422SAndrii Nakryiko * Generic non-thread safe hash map implementation.
5e3b92422SAndrii Nakryiko *
6e3b92422SAndrii Nakryiko * Copyright (c) 2019 Facebook
7e3b92422SAndrii Nakryiko */
8e3b92422SAndrii Nakryiko #include <stdint.h>
9e3b92422SAndrii Nakryiko #include <stdlib.h>
10e3b92422SAndrii Nakryiko #include <stdio.h>
11e3b92422SAndrii Nakryiko #include <errno.h>
12e3b92422SAndrii Nakryiko #include <linux/err.h>
13e3b92422SAndrii Nakryiko #include "hashmap.h"
14e3b92422SAndrii Nakryiko
151d1a3bcfSAndrii Nakryiko /* make sure libbpf doesn't use kernel-only integer typedefs */
161d1a3bcfSAndrii Nakryiko #pragma GCC poison u8 u16 u32 u64 s8 s16 s32 s64
171d1a3bcfSAndrii Nakryiko
1885367030SAndrii Nakryiko /* prevent accidental re-addition of reallocarray() */
1985367030SAndrii Nakryiko #pragma GCC poison reallocarray
2085367030SAndrii Nakryiko
21e3b92422SAndrii Nakryiko /* start with 4 buckets */
22e3b92422SAndrii Nakryiko #define HASHMAP_MIN_CAP_BITS 2
23e3b92422SAndrii Nakryiko
hashmap_add_entry(struct hashmap_entry ** pprev,struct hashmap_entry * entry)24e3b92422SAndrii Nakryiko static void hashmap_add_entry(struct hashmap_entry **pprev,
25e3b92422SAndrii Nakryiko struct hashmap_entry *entry)
26e3b92422SAndrii Nakryiko {
27e3b92422SAndrii Nakryiko entry->next = *pprev;
28e3b92422SAndrii Nakryiko *pprev = entry;
29e3b92422SAndrii Nakryiko }
30e3b92422SAndrii Nakryiko
hashmap_del_entry(struct hashmap_entry ** pprev,struct hashmap_entry * entry)31e3b92422SAndrii Nakryiko static void hashmap_del_entry(struct hashmap_entry **pprev,
32e3b92422SAndrii Nakryiko struct hashmap_entry *entry)
33e3b92422SAndrii Nakryiko {
34e3b92422SAndrii Nakryiko *pprev = entry->next;
35e3b92422SAndrii Nakryiko entry->next = NULL;
36e3b92422SAndrii Nakryiko }
37e3b92422SAndrii Nakryiko
hashmap__init(struct hashmap * map,hashmap_hash_fn hash_fn,hashmap_equal_fn equal_fn,void * ctx)38e3b92422SAndrii Nakryiko void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
39e3b92422SAndrii Nakryiko hashmap_equal_fn equal_fn, void *ctx)
40e3b92422SAndrii Nakryiko {
41e3b92422SAndrii Nakryiko map->hash_fn = hash_fn;
42e3b92422SAndrii Nakryiko map->equal_fn = equal_fn;
43e3b92422SAndrii Nakryiko map->ctx = ctx;
44e3b92422SAndrii Nakryiko
45e3b92422SAndrii Nakryiko map->buckets = NULL;
46e3b92422SAndrii Nakryiko map->cap = 0;
47e3b92422SAndrii Nakryiko map->cap_bits = 0;
48e3b92422SAndrii Nakryiko map->sz = 0;
49e3b92422SAndrii Nakryiko }
50e3b92422SAndrii Nakryiko
hashmap__new(hashmap_hash_fn hash_fn,hashmap_equal_fn equal_fn,void * ctx)51e3b92422SAndrii Nakryiko struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
52e3b92422SAndrii Nakryiko hashmap_equal_fn equal_fn,
53e3b92422SAndrii Nakryiko void *ctx)
54e3b92422SAndrii Nakryiko {
55e3b92422SAndrii Nakryiko struct hashmap *map = malloc(sizeof(struct hashmap));
56e3b92422SAndrii Nakryiko
57e3b92422SAndrii Nakryiko if (!map)
58e3b92422SAndrii Nakryiko return ERR_PTR(-ENOMEM);
59e3b92422SAndrii Nakryiko hashmap__init(map, hash_fn, equal_fn, ctx);
60e3b92422SAndrii Nakryiko return map;
61e3b92422SAndrii Nakryiko }
62e3b92422SAndrii Nakryiko
hashmap__clear(struct hashmap * map)63e3b92422SAndrii Nakryiko void hashmap__clear(struct hashmap *map)
64e3b92422SAndrii Nakryiko {
65229bf8bfSAndrii Nakryiko struct hashmap_entry *cur, *tmp;
668d35d74fSIan Rogers size_t bkt;
67229bf8bfSAndrii Nakryiko
68229bf8bfSAndrii Nakryiko hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
69229bf8bfSAndrii Nakryiko free(cur);
70229bf8bfSAndrii Nakryiko }
71e3b92422SAndrii Nakryiko free(map->buckets);
72229bf8bfSAndrii Nakryiko map->buckets = NULL;
73e3b92422SAndrii Nakryiko map->cap = map->cap_bits = map->sz = 0;
74e3b92422SAndrii Nakryiko }
75e3b92422SAndrii Nakryiko
hashmap__free(struct hashmap * map)76e3b92422SAndrii Nakryiko void hashmap__free(struct hashmap *map)
77e3b92422SAndrii Nakryiko {
78fba60b17SMauricio Vásquez if (IS_ERR_OR_NULL(map))
79e3b92422SAndrii Nakryiko return;
80e3b92422SAndrii Nakryiko
81e3b92422SAndrii Nakryiko hashmap__clear(map);
82e3b92422SAndrii Nakryiko free(map);
83e3b92422SAndrii Nakryiko }
84e3b92422SAndrii Nakryiko
hashmap__size(const struct hashmap * map)85e3b92422SAndrii Nakryiko size_t hashmap__size(const struct hashmap *map)
86e3b92422SAndrii Nakryiko {
87e3b92422SAndrii Nakryiko return map->sz;
88e3b92422SAndrii Nakryiko }
89e3b92422SAndrii Nakryiko
hashmap__capacity(const struct hashmap * map)90e3b92422SAndrii Nakryiko size_t hashmap__capacity(const struct hashmap *map)
91e3b92422SAndrii Nakryiko {
92e3b92422SAndrii Nakryiko return map->cap;
93e3b92422SAndrii Nakryiko }
94e3b92422SAndrii Nakryiko
hashmap_needs_to_grow(struct hashmap * map)95e3b92422SAndrii Nakryiko static bool hashmap_needs_to_grow(struct hashmap *map)
96e3b92422SAndrii Nakryiko {
97e3b92422SAndrii Nakryiko /* grow if empty or more than 75% filled */
98e3b92422SAndrii Nakryiko return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap);
99e3b92422SAndrii Nakryiko }
100e3b92422SAndrii Nakryiko
hashmap_grow(struct hashmap * map)101e3b92422SAndrii Nakryiko static int hashmap_grow(struct hashmap *map)
102e3b92422SAndrii Nakryiko {
103e3b92422SAndrii Nakryiko struct hashmap_entry **new_buckets;
104e3b92422SAndrii Nakryiko struct hashmap_entry *cur, *tmp;
105e3b92422SAndrii Nakryiko size_t new_cap_bits, new_cap;
1068d35d74fSIan Rogers size_t h, bkt;
107e3b92422SAndrii Nakryiko
108e3b92422SAndrii Nakryiko new_cap_bits = map->cap_bits + 1;
109e3b92422SAndrii Nakryiko if (new_cap_bits < HASHMAP_MIN_CAP_BITS)
110e3b92422SAndrii Nakryiko new_cap_bits = HASHMAP_MIN_CAP_BITS;
111e3b92422SAndrii Nakryiko
112e3b92422SAndrii Nakryiko new_cap = 1UL << new_cap_bits;
113e3b92422SAndrii Nakryiko new_buckets = calloc(new_cap, sizeof(new_buckets[0]));
114e3b92422SAndrii Nakryiko if (!new_buckets)
115e3b92422SAndrii Nakryiko return -ENOMEM;
116e3b92422SAndrii Nakryiko
117e3b92422SAndrii Nakryiko hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
118e3b92422SAndrii Nakryiko h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits);
119e3b92422SAndrii Nakryiko hashmap_add_entry(&new_buckets[h], cur);
120e3b92422SAndrii Nakryiko }
121e3b92422SAndrii Nakryiko
122e3b92422SAndrii Nakryiko map->cap = new_cap;
123e3b92422SAndrii Nakryiko map->cap_bits = new_cap_bits;
124e3b92422SAndrii Nakryiko free(map->buckets);
125e3b92422SAndrii Nakryiko map->buckets = new_buckets;
126e3b92422SAndrii Nakryiko
127e3b92422SAndrii Nakryiko return 0;
128e3b92422SAndrii Nakryiko }
129e3b92422SAndrii Nakryiko
hashmap_find_entry(const struct hashmap * map,const long key,size_t hash,struct hashmap_entry *** pprev,struct hashmap_entry ** entry)130e3b92422SAndrii Nakryiko static bool hashmap_find_entry(const struct hashmap *map,
131*c302378bSEduard Zingerman const long key, size_t hash,
132e3b92422SAndrii Nakryiko struct hashmap_entry ***pprev,
133e3b92422SAndrii Nakryiko struct hashmap_entry **entry)
134e3b92422SAndrii Nakryiko {
135e3b92422SAndrii Nakryiko struct hashmap_entry *cur, **prev_ptr;
136e3b92422SAndrii Nakryiko
137e3b92422SAndrii Nakryiko if (!map->buckets)
138e3b92422SAndrii Nakryiko return false;
139e3b92422SAndrii Nakryiko
140e3b92422SAndrii Nakryiko for (prev_ptr = &map->buckets[hash], cur = *prev_ptr;
141e3b92422SAndrii Nakryiko cur;
142e3b92422SAndrii Nakryiko prev_ptr = &cur->next, cur = cur->next) {
143e3b92422SAndrii Nakryiko if (map->equal_fn(cur->key, key, map->ctx)) {
144e3b92422SAndrii Nakryiko if (pprev)
145e3b92422SAndrii Nakryiko *pprev = prev_ptr;
146e3b92422SAndrii Nakryiko *entry = cur;
147e3b92422SAndrii Nakryiko return true;
148e3b92422SAndrii Nakryiko }
149e3b92422SAndrii Nakryiko }
150e3b92422SAndrii Nakryiko
151e3b92422SAndrii Nakryiko return false;
152e3b92422SAndrii Nakryiko }
153e3b92422SAndrii Nakryiko
hashmap_insert(struct hashmap * map,long key,long value,enum hashmap_insert_strategy strategy,long * old_key,long * old_value)154*c302378bSEduard Zingerman int hashmap_insert(struct hashmap *map, long key, long value,
155e3b92422SAndrii Nakryiko enum hashmap_insert_strategy strategy,
156*c302378bSEduard Zingerman long *old_key, long *old_value)
157e3b92422SAndrii Nakryiko {
158e3b92422SAndrii Nakryiko struct hashmap_entry *entry;
159e3b92422SAndrii Nakryiko size_t h;
160e3b92422SAndrii Nakryiko int err;
161e3b92422SAndrii Nakryiko
162e3b92422SAndrii Nakryiko if (old_key)
163*c302378bSEduard Zingerman *old_key = 0;
164e3b92422SAndrii Nakryiko if (old_value)
165*c302378bSEduard Zingerman *old_value = 0;
166e3b92422SAndrii Nakryiko
167e3b92422SAndrii Nakryiko h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
168e3b92422SAndrii Nakryiko if (strategy != HASHMAP_APPEND &&
169e3b92422SAndrii Nakryiko hashmap_find_entry(map, key, h, NULL, &entry)) {
170e3b92422SAndrii Nakryiko if (old_key)
171e3b92422SAndrii Nakryiko *old_key = entry->key;
172e3b92422SAndrii Nakryiko if (old_value)
173e3b92422SAndrii Nakryiko *old_value = entry->value;
174e3b92422SAndrii Nakryiko
175e3b92422SAndrii Nakryiko if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) {
176e3b92422SAndrii Nakryiko entry->key = key;
177e3b92422SAndrii Nakryiko entry->value = value;
178e3b92422SAndrii Nakryiko return 0;
179e3b92422SAndrii Nakryiko } else if (strategy == HASHMAP_ADD) {
180e3b92422SAndrii Nakryiko return -EEXIST;
181e3b92422SAndrii Nakryiko }
182e3b92422SAndrii Nakryiko }
183e3b92422SAndrii Nakryiko
184e3b92422SAndrii Nakryiko if (strategy == HASHMAP_UPDATE)
185e3b92422SAndrii Nakryiko return -ENOENT;
186e3b92422SAndrii Nakryiko
187e3b92422SAndrii Nakryiko if (hashmap_needs_to_grow(map)) {
188e3b92422SAndrii Nakryiko err = hashmap_grow(map);
189e3b92422SAndrii Nakryiko if (err)
190e3b92422SAndrii Nakryiko return err;
191e3b92422SAndrii Nakryiko h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
192e3b92422SAndrii Nakryiko }
193e3b92422SAndrii Nakryiko
194e3b92422SAndrii Nakryiko entry = malloc(sizeof(struct hashmap_entry));
195e3b92422SAndrii Nakryiko if (!entry)
196e3b92422SAndrii Nakryiko return -ENOMEM;
197e3b92422SAndrii Nakryiko
198e3b92422SAndrii Nakryiko entry->key = key;
199e3b92422SAndrii Nakryiko entry->value = value;
200e3b92422SAndrii Nakryiko hashmap_add_entry(&map->buckets[h], entry);
201e3b92422SAndrii Nakryiko map->sz++;
202e3b92422SAndrii Nakryiko
203e3b92422SAndrii Nakryiko return 0;
204e3b92422SAndrii Nakryiko }
205e3b92422SAndrii Nakryiko
hashmap_find(const struct hashmap * map,long key,long * value)206*c302378bSEduard Zingerman bool hashmap_find(const struct hashmap *map, long key, long *value)
207e3b92422SAndrii Nakryiko {
208e3b92422SAndrii Nakryiko struct hashmap_entry *entry;
209e3b92422SAndrii Nakryiko size_t h;
210e3b92422SAndrii Nakryiko
211e3b92422SAndrii Nakryiko h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
212e3b92422SAndrii Nakryiko if (!hashmap_find_entry(map, key, h, NULL, &entry))
213e3b92422SAndrii Nakryiko return false;
214e3b92422SAndrii Nakryiko
215e3b92422SAndrii Nakryiko if (value)
216e3b92422SAndrii Nakryiko *value = entry->value;
217e3b92422SAndrii Nakryiko return true;
218e3b92422SAndrii Nakryiko }
219e3b92422SAndrii Nakryiko
hashmap_delete(struct hashmap * map,long key,long * old_key,long * old_value)220*c302378bSEduard Zingerman bool hashmap_delete(struct hashmap *map, long key,
221*c302378bSEduard Zingerman long *old_key, long *old_value)
222e3b92422SAndrii Nakryiko {
223e3b92422SAndrii Nakryiko struct hashmap_entry **pprev, *entry;
224e3b92422SAndrii Nakryiko size_t h;
225e3b92422SAndrii Nakryiko
226e3b92422SAndrii Nakryiko h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
227e3b92422SAndrii Nakryiko if (!hashmap_find_entry(map, key, h, &pprev, &entry))
228e3b92422SAndrii Nakryiko return false;
229e3b92422SAndrii Nakryiko
230e3b92422SAndrii Nakryiko if (old_key)
231e3b92422SAndrii Nakryiko *old_key = entry->key;
232e3b92422SAndrii Nakryiko if (old_value)
233e3b92422SAndrii Nakryiko *old_value = entry->value;
234e3b92422SAndrii Nakryiko
235e3b92422SAndrii Nakryiko hashmap_del_entry(pprev, entry);
236e3b92422SAndrii Nakryiko free(entry);
237e3b92422SAndrii Nakryiko map->sz--;
238e3b92422SAndrii Nakryiko
239e3b92422SAndrii Nakryiko return true;
240e3b92422SAndrii Nakryiko }
241