aboutsummaryrefslogtreecommitdiffstats
path: root/tools/lib/bpf/hashmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'tools/lib/bpf/hashmap.c')
-rw-r--r--tools/lib/bpf/hashmap.c229
1 files changed, 229 insertions, 0 deletions
diff --git a/tools/lib/bpf/hashmap.c b/tools/lib/bpf/hashmap.c
new file mode 100644
index 000000000000..6122272943e6
--- /dev/null
+++ b/tools/lib/bpf/hashmap.c
@@ -0,0 +1,229 @@
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/* start with 4 buckets */
16#define HASHMAP_MIN_CAP_BITS 2
17
18static void hashmap_add_entry(struct hashmap_entry **pprev,
19 struct hashmap_entry *entry)
20{
21 entry->next = *pprev;
22 *pprev = entry;
23}
24
25static void hashmap_del_entry(struct hashmap_entry **pprev,
26 struct hashmap_entry *entry)
27{
28 *pprev = entry->next;
29 entry->next = NULL;
30}
31
32void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
33 hashmap_equal_fn equal_fn, void *ctx)
34{
35 map->hash_fn = hash_fn;
36 map->equal_fn = equal_fn;
37 map->ctx = ctx;
38
39 map->buckets = NULL;
40 map->cap = 0;
41 map->cap_bits = 0;
42 map->sz = 0;
43}
44
45struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
46 hashmap_equal_fn equal_fn,
47 void *ctx)
48{
49 struct hashmap *map = malloc(sizeof(struct hashmap));
50
51 if (!map)
52 return ERR_PTR(-ENOMEM);
53 hashmap__init(map, hash_fn, equal_fn, ctx);
54 return map;
55}
56
57void hashmap__clear(struct hashmap *map)
58{
59 free(map->buckets);
60 map->cap = map->cap_bits = map->sz = 0;
61}
62
63void hashmap__free(struct hashmap *map)
64{
65 if (!map)
66 return;
67
68 hashmap__clear(map);
69 free(map);
70}
71
72size_t hashmap__size(const struct hashmap *map)
73{
74 return map->sz;
75}
76
77size_t hashmap__capacity(const struct hashmap *map)
78{
79 return map->cap;
80}
81
82static bool hashmap_needs_to_grow(struct hashmap *map)
83{
84 /* grow if empty or more than 75% filled */
85 return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap);
86}
87
88static int hashmap_grow(struct hashmap *map)
89{
90 struct hashmap_entry **new_buckets;
91 struct hashmap_entry *cur, *tmp;
92 size_t new_cap_bits, new_cap;
93 size_t h;
94 int bkt;
95
96 new_cap_bits = map->cap_bits + 1;
97 if (new_cap_bits < HASHMAP_MIN_CAP_BITS)
98 new_cap_bits = HASHMAP_MIN_CAP_BITS;
99
100 new_cap = 1UL << new_cap_bits;
101 new_buckets = calloc(new_cap, sizeof(new_buckets[0]));
102 if (!new_buckets)
103 return -ENOMEM;
104
105 hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
106 h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits);
107 hashmap_add_entry(&new_buckets[h], cur);
108 }
109
110 map->cap = new_cap;
111 map->cap_bits = new_cap_bits;
112 free(map->buckets);
113 map->buckets = new_buckets;
114
115 return 0;
116}
117
118static bool hashmap_find_entry(const struct hashmap *map,
119 const void *key, size_t hash,
120 struct hashmap_entry ***pprev,
121 struct hashmap_entry **entry)
122{
123 struct hashmap_entry *cur, **prev_ptr;
124
125 if (!map->buckets)
126 return false;
127
128 for (prev_ptr = &map->buckets[hash], cur = *prev_ptr;
129 cur;
130 prev_ptr = &cur->next, cur = cur->next) {
131 if (map->equal_fn(cur->key, key, map->ctx)) {
132 if (pprev)
133 *pprev = prev_ptr;
134 *entry = cur;
135 return true;
136 }
137 }
138
139 return false;
140}
141
142int hashmap__insert(struct hashmap *map, const void *key, void *value,
143 enum hashmap_insert_strategy strategy,
144 const void **old_key, void **old_value)
145{
146 struct hashmap_entry *entry;
147 size_t h;
148 int err;
149
150 if (old_key)
151 *old_key = NULL;
152 if (old_value)
153 *old_value = NULL;
154
155 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
156 if (strategy != HASHMAP_APPEND &&
157 hashmap_find_entry(map, key, h, NULL, &entry)) {
158 if (old_key)
159 *old_key = entry->key;
160 if (old_value)
161 *old_value = entry->value;
162
163 if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) {
164 entry->key = key;
165 entry->value = value;
166 return 0;
167 } else if (strategy == HASHMAP_ADD) {
168 return -EEXIST;
169 }
170 }
171
172 if (strategy == HASHMAP_UPDATE)
173 return -ENOENT;
174
175 if (hashmap_needs_to_grow(map)) {
176 err = hashmap_grow(map);
177 if (err)
178 return err;
179 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
180 }
181
182 entry = malloc(sizeof(struct hashmap_entry));
183 if (!entry)
184 return -ENOMEM;
185
186 entry->key = key;
187 entry->value = value;
188 hashmap_add_entry(&map->buckets[h], entry);
189 map->sz++;
190
191 return 0;
192}
193
194bool hashmap__find(const struct hashmap *map, const void *key, void **value)
195{
196 struct hashmap_entry *entry;
197 size_t h;
198
199 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
200 if (!hashmap_find_entry(map, key, h, NULL, &entry))
201 return false;
202
203 if (value)
204 *value = entry->value;
205 return true;
206}
207
208bool hashmap__delete(struct hashmap *map, const void *key,
209 const void **old_key, void **old_value)
210{
211 struct hashmap_entry **pprev, *entry;
212 size_t h;
213
214 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
215 if (!hashmap_find_entry(map, key, h, &pprev, &entry))
216 return false;
217
218 if (old_key)
219 *old_key = entry->key;
220 if (old_value)
221 *old_value = entry->value;
222
223 hashmap_del_entry(pprev, entry);
224 free(entry);
225 map->sz--;
226
227 return true;
228}
229
generated by cgit v1.2.2 (git 2.25.0) at 2025-09-02 11:40:36 -0400