Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0-only
2 : : /*
3 : : * Copyright (c) Meta Platforms, Inc. and affiliates.
4 : : */
5 : :
6 : : #include "bpfilter/core/hashset.h"
7 : :
8 : : #include <errno.h>
9 : : #include <stdlib.h>
10 : :
11 : : #include "bpfilter/helper.h"
12 : : #include "bpfilter/logger.h"
13 : :
14 : : #define _BF_HASHSET_TOMBSTONE ((bf_hashset_elem *)1)
15 : : #define _BF_HASHSET_INIT_CAP 16UL
16 : : /* Maximum load factor before growing. Lowering this number reduces collisions
17 : : * but causes higher memory usage. */
18 : : #define _BF_HASHSET_MAX_LOAD_NUM 5
19 : : #define _BF_HASHSET_MAX_LOAD_DEN 10
20 : : /* Largest power-of-two element count (2^60) that still leaves headroom for
21 : : * load-factor arithmetic (slots_in_use * 10, cap * 5) without overflowing
22 : : * size_t. */
23 : : #define _BF_HASHSET_MAX_CAP (SIZE_MAX / 16 + 1)
24 : :
25 : 3 : static inline size_t _bf_round_next_power_of_2(size_t value)
26 : : {
27 [ + - ]: 3 : if (value == 0)
28 : : return 1;
29 : :
30 : 3 : value--;
31 : 3 : value |= value >> 1;
32 : 3 : value |= value >> 2;
33 : 3 : value |= value >> 4;
34 : 3 : value |= value >> 8;
35 : 3 : value |= value >> 16;
36 : : #if SIZE_MAX > 0xFFFFFFFFU
37 : 3 : value |= value >> 32;
38 : : #endif
39 : :
40 : 3 : return ++value;
41 : : }
42 : :
43 : : static inline bool _bf_hashset_slot_is_tombstone(const bf_hashset_elem *slot)
44 : : {
45 : : return slot == _BF_HASHSET_TOMBSTONE;
46 : : }
47 : :
48 : : // Caller must ensure set->cap > 0 to avoid division by zero.
49 : : static size_t _bf_hashset_index(const bf_hashset *set, const void *data)
50 : : {
51 : : assert(set);
52 : : assert(data);
53 : :
54 : 4106 : return set->ops.hash(data, set->ctx) % set->cap;
55 : : }
56 : :
57 : 1746 : static int _bf_hashset_resize(bf_hashset *set, size_t new_cap)
58 : : {
59 : : bf_hashset_elem **new_slots;
60 : :
61 : : assert(set);
62 : :
63 : : // We must have enough space for all elements.
64 [ + - ]: 1746 : if (new_cap <= set->len)
65 : : return -EINVAL;
66 : :
67 : 1746 : new_slots = (bf_hashset_elem **)calloc(new_cap, sizeof(*new_slots));
68 [ + - ]: 1746 : if (!new_slots)
69 : : return -ENOMEM;
70 : :
71 [ + + + + ]: 3728 : bf_hashset_foreach (set, elem) {
72 : 120 : size_t idx = set->ops.hash(elem->data, set->ctx) % new_cap;
73 [ - + ]: 120 : while (new_slots[idx])
74 : 0 : idx = (idx + 1) % new_cap;
75 [ + + ]: 120 : new_slots[idx] = elem;
76 : : }
77 : :
78 : : freep((void *)&set->slots);
79 : 1746 : set->slots = new_slots;
80 : 1746 : set->cap = new_cap;
81 : 1746 : set->slots_in_use = set->len;
82 : :
83 : 1746 : return 0;
84 : : }
85 : :
86 : 1743 : static int _bf_hashset_grow(bf_hashset *set)
87 : : {
88 : : size_t new_cap;
89 : :
90 : : assert(set);
91 : :
92 [ + - ]: 1743 : if (set->cap >= _BF_HASHSET_MAX_CAP)
93 : : return -ENOMEM;
94 [ + + ]: 1743 : new_cap = set->cap ? set->cap * 2 : _BF_HASHSET_INIT_CAP;
95 : :
96 : 1743 : return _bf_hashset_resize(set, new_cap);
97 : : }
98 : :
99 : : static bool _bf_hashset_needs_grow(const bf_hashset *set)
100 : : {
101 : : assert(set);
102 : :
103 : 3829 : return set->slots_in_use * _BF_HASHSET_MAX_LOAD_DEN >=
104 : 3829 : set->cap * _BF_HASHSET_MAX_LOAD_NUM;
105 : : }
106 : :
107 : : /**
108 : : * @brief Checks if an element is present in the hashset.
109 : : *
110 : : * If it is, also sets `found_index` to the index of the found element.
111 : : * If it is not, also sets `free_index` to the index of the first free slot,
112 : : * if there is any free slot.
113 : : *
114 : : * @param set Hashset to search. Can't be NULL.
115 : : * @param data Element to search for. Can't be NULL.
116 : : * @param found_index If non-NULL, set to the index of the matching element
117 : : * when found.
118 : : * @param free_index If non-NULL, set to the index of the first free slot
119 : : * when no match is found.
120 : : * @return true if the element was found, false otherwise.
121 : : */
122 : 5846 : static bool _bf_hashset_find(const bf_hashset *set, const void *data,
123 : : size_t *found_index, size_t *free_index)
124 : : {
125 : : size_t idx;
126 : : size_t first_free = SIZE_MAX;
127 : :
128 : : assert(set);
129 : : assert(data);
130 : :
131 [ + + ]: 5846 : if (set->cap == 0)
132 : : return false;
133 : :
134 : : idx = _bf_hashset_index(set, data);
135 : :
136 [ + - ]: 4346 : for (size_t i = 0; i < set->cap; ++i) {
137 : 4346 : bf_hashset_elem *slot = set->slots[idx];
138 : :
139 [ + + ]: 4346 : if (!slot) {
140 [ + + ]: 3843 : if (free_index)
141 [ + + ]: 7663 : *free_index = first_free != SIZE_MAX ? first_free : idx;
142 : 3843 : return false;
143 : : }
144 : :
145 [ + + ]: 503 : if (_bf_hashset_slot_is_tombstone(slot)) {
146 [ + + ]: 19 : if (first_free == SIZE_MAX)
147 : : first_free = idx;
148 [ + + ]: 484 : } else if (set->ops.equal(slot->data, data, set->ctx)) {
149 [ + + ]: 263 : if (found_index)
150 : 28 : *found_index = idx;
151 : 263 : return true;
152 : : }
153 : :
154 : 240 : idx = (idx + 1) % set->cap;
155 : : }
156 : :
157 [ # # ]: 0 : if (free_index && first_free != SIZE_MAX)
158 : 0 : *free_index = first_free;
159 : :
160 : : return false;
161 : : }
162 : :
163 : 2 : int bf_hashset_new(bf_hashset **set, const bf_hashset_ops *ops, void *ctx)
164 : : {
165 : 2 : _free_bf_hashset_ bf_hashset *_set = NULL;
166 : :
167 : : assert(set);
168 : : assert(ops);
169 : : assert(ops->hash);
170 : : assert(ops->equal);
171 : :
172 : 2 : _set = calloc(1, sizeof(*_set));
173 [ + - ]: 2 : if (!_set)
174 : : return -ENOMEM;
175 : :
176 : 2 : bf_hashset_init(_set, ops, ctx);
177 : :
178 : 2 : *set = TAKE_PTR(_set);
179 : :
180 : 2 : return 0;
181 : : }
182 : :
183 : 4 : void bf_hashset_free(bf_hashset **set)
184 : : {
185 : : assert(set);
186 : :
187 [ + + ]: 4 : if (!*set)
188 : : return;
189 : :
190 : 2 : bf_hashset_clean(*set);
191 : : freep((void *)set);
192 : : }
193 : :
194 : 1834 : void bf_hashset_init(bf_hashset *set, const bf_hashset_ops *ops, void *ctx)
195 : : {
196 : : assert(set);
197 : : assert(ops);
198 : : assert(ops->hash);
199 : : assert(ops->equal);
200 : :
201 : 1834 : *set = bf_hashset_default(ops, ctx);
202 : 1834 : }
203 : :
204 : 1834 : void bf_hashset_clean(bf_hashset *set)
205 : : {
206 : : assert(set);
207 : :
208 [ + + + + : 11270 : bf_hashset_foreach (set, elem) {
+ + ]
209 [ + - ]: 3801 : if (set->ops.free)
210 : 3801 : set->ops.free(&elem->data, set->ctx);
211 : : freep((void *)&elem);
212 : : }
213 : :
214 : : freep((void *)&set->slots);
215 : 1834 : set->cap = 0;
216 : 1834 : set->len = 0;
217 : 1834 : set->slots_in_use = 0;
218 : 1834 : set->head = NULL;
219 : 1834 : set->tail = NULL;
220 : 1834 : }
221 : :
222 : 365 : size_t bf_hashset_size(const bf_hashset *set)
223 : : {
224 : : assert(set);
225 : 365 : return set->len;
226 : : }
227 : :
228 : 2026 : bool bf_hashset_is_empty(const bf_hashset *set)
229 : : {
230 : : assert(set);
231 : 2026 : return set->len == 0;
232 : : }
233 : :
234 : 7 : int bf_hashset_reserve(bf_hashset *set, size_t count)
235 : : {
236 : : size_t needed, new_cap;
237 : :
238 : : assert(set);
239 : :
240 [ + + ]: 7 : if (count == 0)
241 : : return 0;
242 : :
243 [ + - ]: 5 : if (count > _BF_HASHSET_MAX_CAP)
244 : : return -ENOMEM;
245 : :
246 : 5 : needed = count * _BF_HASHSET_MAX_LOAD_DEN / _BF_HASHSET_MAX_LOAD_NUM;
247 [ + + ]: 5 : if (needed <= set->cap)
248 : : return 0;
249 : :
250 : 3 : new_cap = _bf_round_next_power_of_2(bf_max(needed, _BF_HASHSET_INIT_CAP));
251 [ + - ]: 3 : if (new_cap > _BF_HASHSET_MAX_CAP)
252 : : return -ENOMEM;
253 : :
254 : 3 : return _bf_hashset_resize(set, new_cap);
255 : : }
256 : :
257 : 3833 : int bf_hashset_add(bf_hashset *set, void **data)
258 : : {
259 : : bf_hashset_elem *elem;
260 : 3833 : size_t free_idx = SIZE_MAX;
261 : : bool was_tombstone;
262 : : int r;
263 : :
264 : : assert(set);
265 : : assert(data);
266 : : assert(*data);
267 : :
268 [ + + ]: 3833 : if (_bf_hashset_find(set, *data, NULL, &free_idx))
269 : : return -EEXIST;
270 : :
271 [ - + ]: 3829 : if (set->len >= _BF_HASHSET_MAX_CAP)
272 [ # # ]: 0 : return bf_err_r(-ENOMEM, "hashset reached maximum capacity");
273 : :
274 [ + + ]: 3829 : if (_bf_hashset_needs_grow(set)) {
275 : 1743 : r = _bf_hashset_grow(set);
276 [ + - ]: 1743 : if (r)
277 : : return r;
278 : : // Find new free_idx for this element.
279 [ - + ]: 1743 : if (_bf_hashset_find(set, *data, NULL, &free_idx))
280 : : return -EEXIST;
281 : : }
282 : :
283 : 3829 : elem = malloc(sizeof(*elem));
284 [ - + ]: 3829 : if (!elem)
285 : : return -ENOMEM;
286 : :
287 : 3829 : elem->data = TAKE_PTR(*data);
288 : :
289 : 3829 : was_tombstone = _bf_hashset_slot_is_tombstone(set->slots[free_idx]);
290 : 3829 : set->slots[free_idx] = elem;
291 : :
292 : 3829 : elem->prev = set->tail;
293 : 3829 : elem->next = NULL;
294 [ + + ]: 3829 : if (set->tail)
295 : 2087 : set->tail->next = elem;
296 : : else
297 : 1742 : set->head = elem;
298 : 3829 : set->tail = elem;
299 : :
300 : 3829 : ++set->len;
301 : :
302 [ + + ]: 3829 : if (!was_tombstone)
303 : 3826 : ++set->slots_in_use;
304 : :
305 : : return 0;
306 : : }
307 : :
308 : 238 : bool bf_hashset_contains(const bf_hashset *set, const void *data)
309 : : {
310 : : assert(set);
311 : : assert(data);
312 : :
313 : 238 : return _bf_hashset_find(set, data, NULL, NULL);
314 : : }
315 : :
316 : 28 : static void _bf_hashset_unlink(bf_hashset *set, size_t found_idx)
317 : : {
318 : 28 : bf_hashset_elem *elem = set->slots[found_idx];
319 : :
320 [ + + ]: 28 : if (elem->prev)
321 : 7 : elem->prev->next = elem->next;
322 : : else
323 : 21 : set->head = elem->next;
324 : :
325 [ + + ]: 28 : if (elem->next)
326 : 15 : elem->next->prev = elem->prev;
327 : : else
328 : 13 : set->tail = elem->prev;
329 : :
330 : 28 : set->slots[found_idx] = _BF_HASHSET_TOMBSTONE;
331 : : freep((void *)&elem);
332 : 28 : --set->len;
333 : 28 : }
334 : :
335 : 18 : int bf_hashset_delete(bf_hashset *set, const void *data)
336 : : {
337 : 18 : size_t found_idx = SIZE_MAX;
338 : :
339 : : assert(set);
340 : : assert(data);
341 : :
342 [ + + ]: 18 : if (!_bf_hashset_find(set, data, &found_idx, NULL))
343 : : return -ENOENT;
344 : :
345 [ + - ]: 15 : if (set->ops.free)
346 : 15 : set->ops.free(&set->slots[found_idx]->data, set->ctx);
347 : :
348 : 15 : _bf_hashset_unlink(set, found_idx);
349 : :
350 : 15 : return 0;
351 : : }
352 : :
353 : 14 : int bf_hashset_take(bf_hashset *set, const void *key, void **data)
354 : : {
355 : 14 : size_t found_idx = SIZE_MAX;
356 : :
357 : : assert(set);
358 : : assert(key);
359 : : assert(data);
360 : :
361 [ + + ]: 14 : if (!_bf_hashset_find(set, key, &found_idx, NULL))
362 : : return -ENOENT;
363 : :
364 : 13 : *data = set->slots[found_idx]->data;
365 : 13 : _bf_hashset_unlink(set, found_idx);
366 : :
367 : 13 : return 0;
368 : : }
|
