aboutsummaryrefslogtreecommitdiffstats
path: root/tools/lib/bpf/hashmap.h
diff options
context:
space:
mode:
Diffstat (limited to 'tools/lib/bpf/hashmap.h')
-rw-r--r--tools/lib/bpf/hashmap.h173
1 files changed, 173 insertions, 0 deletions
diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h
new file mode 100644
index 000000000000..03748a742146
--- /dev/null
+++ b/tools/lib/bpf/hashmap.h
@@ -0,0 +1,173 @@
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#ifndef __LIBBPF_HASHMAP_H
9#define __LIBBPF_HASHMAP_H
10
11#include <stdbool.h>
12#include <stddef.h>
13#include "libbpf_internal.h"
14
15static inline size_t hash_bits(size_t h, int bits)
16{
17 /* shuffle bits and return requested number of upper bits */
18 return (h * 11400714819323198485llu) >> (__WORDSIZE - bits);
19}
20
21typedef size_t (*hashmap_hash_fn)(const void *key, void *ctx);
22typedef bool (*hashmap_equal_fn)(const void *key1, const void *key2, void *ctx);
23
24struct hashmap_entry {
25 const void *key;
26 void *value;
27 struct hashmap_entry *next;
28};
29
30struct hashmap {
31 hashmap_hash_fn hash_fn;
32 hashmap_equal_fn equal_fn;
33 void *ctx;
34
35 struct hashmap_entry **buckets;
36 size_t cap;
37 size_t cap_bits;
38 size_t sz;
39};
40
41#define HASHMAP_INIT(hash_fn, equal_fn, ctx) { \
42 .hash_fn = (hash_fn), \
43 .equal_fn = (equal_fn), \
44 .ctx = (ctx), \
45 .buckets = NULL, \
46 .cap = 0, \
47 .cap_bits = 0, \
48 .sz = 0, \
49}
50
51void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
52 hashmap_equal_fn equal_fn, void *ctx);
53struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
54 hashmap_equal_fn equal_fn,
55 void *ctx);
56void hashmap__clear(struct hashmap *map);
57void hashmap__free(struct hashmap *map);
58
59size_t hashmap__size(const struct hashmap *map);
60size_t hashmap__capacity(const struct hashmap *map);
61
62/*
63 * Hashmap insertion strategy:
64 * - HASHMAP_ADD - only add key/value if key doesn't exist yet;
65 * - HASHMAP_SET - add key/value pair if key doesn't exist yet; otherwise,
66 * update value;
67 * - HASHMAP_UPDATE - update value, if key already exists; otherwise, do
68 * nothing and return -ENOENT;
69 * - HASHMAP_APPEND - always add key/value pair, even if key already exists.
70 * This turns hashmap into a multimap by allowing multiple values to be
71 * associated with the same key. Most useful read API for such hashmap is
72 * hashmap__for_each_key_entry() iteration. If hashmap__find() is still
73 * used, it will return last inserted key/value entry (first in a bucket
74 * chain).
75 */
76enum hashmap_insert_strategy {
77 HASHMAP_ADD,
78 HASHMAP_SET,
79 HASHMAP_UPDATE,
80 HASHMAP_APPEND,
81};
82
83/*
84 * hashmap__insert() adds key/value entry w/ various semantics, depending on
85 * provided strategy value. If a given key/value pair replaced already
86 * existing key/value pair, both old key and old value will be returned
87 * through old_key and old_value to allow calling code do proper memory
88 * management.
89 */
90int hashmap__insert(struct hashmap *map, const void *key, void *value,
91 enum hashmap_insert_strategy strategy,
92 const void **old_key, void **old_value);
93
94static inline int hashmap__add(struct hashmap *map,
95 const void *key, void *value)
96{
97 return hashmap__insert(map, key, value, HASHMAP_ADD, NULL, NULL);
98}
99
100static inline int hashmap__set(struct hashmap *map,
101 const void *key, void *value,
102 const void **old_key, void **old_value)
103{
104 return hashmap__insert(map, key, value, HASHMAP_SET,
105 old_key, old_value);
106}
107
108static inline int hashmap__update(struct hashmap *map,
109 const void *key, void *value,
110 const void **old_key, void **old_value)
111{
112 return hashmap__insert(map, key, value, HASHMAP_UPDATE,
113 old_key, old_value);
114}
115
116static inline int hashmap__append(struct hashmap *map,
117 const void *key, void *value)
118{
119 return hashmap__insert(map, key, value, HASHMAP_APPEND, NULL, NULL);
120}
121
122bool hashmap__delete(struct hashmap *map, const void *key,
123 const void **old_key, void **old_value);
124
125bool hashmap__find(const struct hashmap *map, const void *key, void **value);
126
127/*
128 * hashmap__for_each_entry - iterate over all entries in hashmap
129 * @map: hashmap to iterate
130 * @cur: struct hashmap_entry * used as a loop cursor
131 * @bkt: integer used as a bucket loop cursor
132 */
133#define hashmap__for_each_entry(map, cur, bkt) \
134 for (bkt = 0; bkt < map->cap; bkt++) \
135 for (cur = map->buckets[bkt]; cur; cur = cur->next)
136
137/*
138 * hashmap__for_each_entry_safe - iterate over all entries in hashmap, safe
139 * against removals
140 * @map: hashmap to iterate
141 * @cur: struct hashmap_entry * used as a loop cursor
142 * @tmp: struct hashmap_entry * used as a temporary next cursor storage
143 * @bkt: integer used as a bucket loop cursor
144 */
145#define hashmap__for_each_entry_safe(map, cur, tmp, bkt) \
146 for (bkt = 0; bkt < map->cap; bkt++) \
147 for (cur = map->buckets[bkt]; \
148 cur && ({tmp = cur->next; true; }); \
149 cur = tmp)
150
151/*
152 * hashmap__for_each_key_entry - iterate over entries associated with given key
153 * @map: hashmap to iterate
154 * @cur: struct hashmap_entry * used as a loop cursor
155 * @key: key to iterate entries for
156 */
157#define hashmap__for_each_key_entry(map, cur, _key) \
158 for (cur = ({ size_t bkt = hash_bits(map->hash_fn((_key), map->ctx),\
159 map->cap_bits); \
160 map->buckets ? map->buckets[bkt] : NULL; }); \
161 cur; \
162 cur = cur->next) \
163 if (map->equal_fn(cur->key, (_key), map->ctx))
164
165#define hashmap__for_each_key_entry_safe(map, cur, tmp, _key) \
166 for (cur = ({ size_t bkt = hash_bits(map->hash_fn((_key), map->ctx),\
167 map->cap_bits); \
168 cur = map->buckets ? map->buckets[bkt] : NULL; }); \
169 cur && ({ tmp = cur->next; true; }); \
170 cur = tmp) \
171 if (map->equal_fn(cur->key, (_key), map->ctx))
172
173#endif /* __LIBBPF_HASHMAP_H */
generated by cgit v1.2.2 (git 2.25.0) at 2025-09-02 07:24:35 -0400