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 | |
24 | static void hashmap_add_entry(struct hashmap_entry **pprev, |
25 | struct hashmap_entry *entry) |
26 | { |
27 | entry->next = *pprev; |
28 | *pprev = entry; |
29 | } |
30 | |
31 | static void hashmap_del_entry(struct hashmap_entry **pprev, |
32 | struct hashmap_entry *entry) |
33 | { |
34 | *pprev = entry->next; |
35 | entry->next = NULL; |
36 | } |
37 | |
38 | void 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 | |
51 | struct 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(error: -ENOMEM); |
59 | hashmap__init(map, hash_fn, equal_fn, ctx); |
60 | return map; |
61 | } |
62 | |
63 | void 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 | |
76 | void hashmap__free(struct hashmap *map) |
77 | { |
78 | if (IS_ERR_OR_NULL(ptr: map)) |
79 | return; |
80 | |
81 | hashmap__clear(map); |
82 | free(map); |
83 | } |
84 | |
85 | size_t hashmap__size(const struct hashmap *map) |
86 | { |
87 | return map->sz; |
88 | } |
89 | |
90 | size_t hashmap__capacity(const struct hashmap *map) |
91 | { |
92 | return map->cap; |
93 | } |
94 | |
95 | static 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 | |
101 | static 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(h: map->hash_fn(cur->key, map->ctx), bits: new_cap_bits); |
119 | hashmap_add_entry(pprev: &new_buckets[h], entry: 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 | |
130 | static 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 | |
154 | int 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(h: map->hash_fn(key, map->ctx), bits: map->cap_bits); |
168 | if (strategy != HASHMAP_APPEND && |
169 | hashmap_find_entry(map, key, hash: h, NULL, entry: &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(h: map->hash_fn(key, map->ctx), bits: 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(pprev: &map->buckets[h], entry); |
201 | map->sz++; |
202 | |
203 | return 0; |
204 | } |
205 | |
206 | bool 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(h: map->hash_fn(key, map->ctx), bits: map->cap_bits); |
212 | if (!hashmap_find_entry(map, key, hash: h, NULL, entry: &entry)) |
213 | return false; |
214 | |
215 | if (value) |
216 | *value = entry->value; |
217 | return true; |
218 | } |
219 | |
220 | bool 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(h: map->hash_fn(key, map->ctx), bits: map->cap_bits); |
227 | if (!hashmap_find_entry(map, key, hash: h, pprev: &pprev, entry: &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 | } |
241 | |