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