Line data Source code
1 : /*
2 : This file is part of GNUnet.
3 : Copyright (C) 2001-2026 GNUnet e.V.
4 :
5 : GNUnet is free software: you can redistribute it and/or modify it
6 : under the terms of the GNU Affero General Public License as published
7 : by the Free Software Foundation, either version 3 of the License,
8 : or (at your option) any later version.
9 :
10 : GNUnet is distributed in the hope that it will be useful, but
11 : WITHOUT ANY WARRANTY; without even the implied warranty of
12 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 : Affero General Public License for more details.
14 :
15 : You should have received a copy of the GNU Affero General Public License
16 : along with this program. If not, see <http://www.gnu.org/licenses/>.
17 :
18 : SPDX-License-Identifier: AGPL3.0-or-later
19 : */
20 :
21 : /**
22 : * @addtogroup libgnunetutil
23 : * Multi-function utilities library for GNUnet programs
24 : * @{
25 : *
26 : * @author Christian Grothoff
27 : *
28 : * @file
29 : * Hash maps with multiple values per key
30 : *
31 : * @addtogroup hashmap
32 : * @{
33 : *
34 : * All hash maps in GNUnet share one implementation: a chained hash
35 : * table for keys of a fixed size, chosen when the map is created,
36 : * where the same key may be stored with several values. How a key
37 : * is stored depends on its size:
38 : *
39 : * - keys of at most 8 bytes are stored in the entry itself;
40 : * - longer keys are copied into the entry, or
41 : * - if the map was created with "do_not_copy_keys", the entry only
42 : * points to the key, which then must stay valid as long as the
43 : * entry is in the map (typically because the key is part of the
44 : * value).
45 : *
46 : * The map never frees or copies values; they are opaque pointers.
47 : *
48 : * Maps are protected against hash flooding: the bucket of a key is
49 : * chosen by SipHash under a random key of the map, so that whoever
50 : * chooses keys (another peer, say) cannot make many of them land in
51 : * the same bucket and turn lookups into linear scans. Where no one
52 : * but the local peer chooses the keys and speed matters, a map can be
53 : * created without that protection, see
54 : * #GNUNET_CONTAINER_MULTIMAP_FLAG_UNPROTECTED.
55 : *
56 : * The implementation (the GNUNET_CONTAINER_multimap_*_() functions
57 : * declared here) works on untyped keys and values. Code should not
58 : * call it directly, but use typed wrappers instead, which
59 : * #GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY (for keys passed by
60 : * pointer) and #GNUNET_CONTAINER_MULTIMAP_DEFINE_VALKEY (for keys of
61 : * up to 8 bytes passed by value, such as integers) generate as
62 : * static inline functions. The classic maps
63 : * #GNUNET_CONTAINER_MultiHashMap, #GNUNET_CONTAINER_MultiPeerMap,
64 : * #GNUNET_CONTAINER_MultiShortmap, #GNUNET_CONTAINER_MultiUuidmap and
65 : * #GNUNET_CONTAINER_MultiHashMap32 are defined that way at the end of
66 : * this file, and an application can define its own maps the same way,
67 : * for example to get a map whose values have a proper type instead of
68 : * `void *`.
69 : *
70 : * Iteration order is unspecified and changes as the map grows.
71 : */
72 :
73 : #include "gnunet_common.h"
74 : #if ! defined (__GNUNET_UTIL_LIB_H_INSIDE__)
75 : #error "Only <gnunet_util_lib.h> can be included directly."
76 : #endif
77 :
78 : #ifndef GNUNET_HASHMAP_LIB_H
79 : #define GNUNET_HASHMAP_LIB_H
80 :
81 : #ifdef __cplusplus
82 : extern "C" {
83 : #if 0 /* keep Emacsens' auto-indent happy */
84 : }
85 : #endif
86 : #endif
87 :
88 : #include <string.h>
89 : #include "gnunet_crypto_lib.h"
90 :
91 :
92 : /**
93 : * @ingroup hashmap
94 : * Options for storing values in the HashMap.
95 : */
96 : enum GNUNET_CONTAINER_MultiHashMapOption
97 : {
98 : /**
99 : * @ingroup hashmap
100 : * If a value with the given key exists, replace it. Note that the
101 : * old value would NOT be freed by replace (the application has to
102 : * make sure that this happens if required).
103 : */
104 : GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
105 :
106 : /**
107 : * @ingroup hashmap
108 : * Allow multiple values with the same key.
109 : */
110 : GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
111 :
112 : /**
113 : * @ingroup hashmap
114 : * There must only be one value per key; storing a value should fail
115 : * if a value under the same key already exists.
116 : */
117 : GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
118 :
119 : /**
120 : * @ingroup hashmap There must only be one value per key, but don't
121 : * bother checking if a value already exists (faster than
122 : * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY; implemented
123 : * just like #GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE but this
124 : * option documents better what is intended if
125 : * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY is what is
126 : * desired).
127 : */
128 : GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
129 : };
130 :
131 :
132 : /* ********************* untyped implementation ********************* */
133 :
134 : /**
135 : * @ingroup hashmap
136 : * Largest key size (in bytes) a map supports.
137 : */
138 : #define GNUNET_CONTAINER_MULTIMAP_MAX_KEY_SIZE 1024
139 :
140 :
141 : /**
142 : * @ingroup hashmap
143 : * Flags for #GNUNET_CONTAINER_multimap_create_().
144 : */
145 : enum GNUNET_CONTAINER_MultiMapFlags
146 : {
147 : /**
148 : * Copy keys longer than 8 bytes into the map.
149 : */
150 : GNUNET_CONTAINER_MULTIMAP_FLAG_NONE = 0,
151 :
152 : /**
153 : * Do not copy keys longer than 8 bytes into the map, only keep a
154 : * pointer to them. The caller must guarantee that the key stays
155 : * valid (and unchanged) as long as the entry is in the map. This
156 : * saves memory, but is also a recipe for heap corruption if that
157 : * guarantee does not hold. Ignored for keys of up to 8 bytes,
158 : * which are always stored in the entry.
159 : */
160 : GNUNET_CONTAINER_MULTIMAP_FLAG_DO_NOT_COPY_KEYS = 1,
161 :
162 : /**
163 : * Do not protect the map against hash flooding. The bucket of a key
164 : * is then computed from its first 8 bytes only, without a secret,
165 : * which makes lookups faster (perf_container_multimap shows by how
166 : * much), but lets anyone who can choose keys put them all into one
167 : * bucket. Only use this if no one but the local peer chooses the
168 : * keys (keys from other peers or from clients do not qualify), if
169 : * the first 8 bytes of the keys vary, and if speed matters; and say
170 : * at the call where the keys come from.
171 : */
172 : GNUNET_CONTAINER_MULTIMAP_FLAG_UNPROTECTED = 2
173 : };
174 :
175 :
176 : /**
177 : * @ingroup hashmap
178 : * Handle for a map with untyped keys and values.
179 : */
180 : struct GNUNET_CONTAINER_MultiMap;
181 :
182 :
183 : /**
184 : * @ingroup hashmap
185 : * Handle for an iterator over a map with untyped keys and values.
186 : */
187 : struct GNUNET_CONTAINER_MultiMapIterator;
188 :
189 :
190 : /**
191 : * @ingroup hashmap
192 : * Iterator over the entries of a map with untyped keys and values.
193 : *
194 : * @param cls closure
195 : * @param key the key of the entry; only valid during the call, except
196 : * that for maps that do not copy their keys this is the
197 : * pointer that was given to the map with the entry
198 : * @param value value of the entry
199 : * @return #GNUNET_OK to continue iterating, anything else to stop
200 : */
201 : typedef enum GNUNET_GenericReturnValue
202 : (*GNUNET_CONTAINER_MultiMapIteratorCallback)(
203 : void *cls,
204 : const void *key,
205 : void *value);
206 :
207 :
208 : /**
209 : * @ingroup hashmap
210 : * Create a map. Use the typed create function of a map instead.
211 : *
212 : * @param len initial number of buckets; the map grows as needed
213 : * @param key_size size of the keys in bytes, from 1 to
214 : * #GNUNET_CONTAINER_MULTIMAP_MAX_KEY_SIZE
215 : * @param flags how to store keys
216 : * @return NULL on error
217 : */
218 : struct GNUNET_CONTAINER_MultiMap *
219 : GNUNET_CONTAINER_multimap_create_ (unsigned int len,
220 : size_t key_size,
221 : enum GNUNET_CONTAINER_MultiMapFlags flags);
222 :
223 :
224 : /**
225 : * @ingroup hashmap
226 : * Destroy a map. Does not free the values. Must not be called
227 : * while the map is being iterated over.
228 : *
229 : * @param[in] map the map to destroy
230 : */
231 : void
232 : GNUNET_CONTAINER_multimap_destroy_ (struct GNUNET_CONTAINER_MultiMap *map);
233 :
234 :
235 : /**
236 : * @ingroup hashmap
237 : * Get the number of key-value pairs in a map.
238 : *
239 : * @param map the map
240 : * @return the number of key-value pairs
241 : */
242 : unsigned int
243 : GNUNET_CONTAINER_multimap_size_ (const struct GNUNET_CONTAINER_MultiMap *map);
244 :
245 :
246 : /**
247 : * @ingroup hashmap
248 : * Get a value stored under a key. If there are several, which one
249 : * is returned is unspecified.
250 : *
251 : * @param map the map
252 : * @param key the key to look for
253 : * @return the value, or NULL if the key is not in the map
254 : */
255 : void *
256 : GNUNET_CONTAINER_multimap_get_ (const struct GNUNET_CONTAINER_MultiMap *map,
257 : const void *key);
258 :
259 :
260 : /**
261 : * @ingroup hashmap
262 : * Check if the map has any value stored under a key.
263 : *
264 : * @param map the map
265 : * @param key the key to look for
266 : * @return #GNUNET_YES if so, #GNUNET_NO if not
267 : */
268 : enum GNUNET_GenericReturnValue
269 : GNUNET_CONTAINER_multimap_contains_ (
270 : const struct GNUNET_CONTAINER_MultiMap *map,
271 : const void *key);
272 :
273 :
274 : /**
275 : * @ingroup hashmap
276 : * Check if the map has a particular key-value pair.
277 : *
278 : * @param map the map
279 : * @param key the key to look for
280 : * @param value the value to look for
281 : * @return #GNUNET_YES if so, #GNUNET_NO if not
282 : */
283 : enum GNUNET_GenericReturnValue
284 : GNUNET_CONTAINER_multimap_contains_value_ (
285 : const struct GNUNET_CONTAINER_MultiMap *map,
286 : const void *key,
287 : const void *value);
288 :
289 :
290 : /**
291 : * @ingroup hashmap
292 : * Store a key-value pair in a map.
293 : *
294 : * @param map the map
295 : * @param key the key to use
296 : * @param value the value to store
297 : * @param opt what to do if the key is already in the map
298 : * @return #GNUNET_OK on success,
299 : * #GNUNET_NO if a value was replaced (with
300 : * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE),
301 : * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY
302 : * was given and the key is already in the map
303 : */
304 : enum GNUNET_GenericReturnValue
305 : GNUNET_CONTAINER_multimap_put_ (struct GNUNET_CONTAINER_MultiMap *map,
306 : const void *key,
307 : void *value,
308 : enum GNUNET_CONTAINER_MultiHashMapOption opt);
309 :
310 :
311 : /**
312 : * @ingroup hashmap
313 : * Remove a key-value pair from a map.
314 : *
315 : * @param map the map
316 : * @param key the key of the pair
317 : * @param value the value of the pair
318 : * @return #GNUNET_YES if the pair was removed,
319 : * #GNUNET_NO if it was not in the map
320 : */
321 : enum GNUNET_GenericReturnValue
322 : GNUNET_CONTAINER_multimap_remove_ (struct GNUNET_CONTAINER_MultiMap *map,
323 : const void *key,
324 : const void *value);
325 :
326 :
327 : /**
328 : * @ingroup hashmap
329 : * Remove all values stored under a key from a map.
330 : *
331 : * @param map the map
332 : * @param key the key to remove
333 : * @return the number of values removed
334 : */
335 : int
336 : GNUNET_CONTAINER_multimap_remove_all_ (struct GNUNET_CONTAINER_MultiMap *map,
337 : const void *key);
338 :
339 :
340 : /**
341 : * @ingroup hashmap
342 : * Remove all key-value pairs from a map. Does not free the values.
343 : *
344 : * @param map the map
345 : * @return the number of key-value pairs removed
346 : */
347 : unsigned int
348 : GNUNET_CONTAINER_multimap_clear_ (struct GNUNET_CONTAINER_MultiMap *map);
349 :
350 :
351 : /**
352 : * @ingroup hashmap
353 : * Call a function on every key-value pair of a map. @a it may
354 : * remove entries from the map, including the current one.
355 : *
356 : * @param map the map
357 : * @param it function to call on each entry, can be NULL
358 : * @param it_cls closure for @a it
359 : * @return the number of entries visited,
360 : * #GNUNET_SYSERR if @a it aborted the iteration
361 : */
362 : int
363 : GNUNET_CONTAINER_multimap_iterate_ (
364 : struct GNUNET_CONTAINER_MultiMap *map,
365 : GNUNET_CONTAINER_MultiMapIteratorCallback it,
366 : void *it_cls);
367 :
368 :
369 : /**
370 : * @ingroup hashmap
371 : * Call a function on every value stored under a key. @a it may
372 : * remove entries from the map, including the current one, and may
373 : * call this function again (up to a small nesting depth).
374 : *
375 : * @param map the map
376 : * @param key the key to look for; @a it is called with this pointer
377 : * @param it function to call on each matching entry, can be NULL
378 : * @param it_cls closure for @a it
379 : * @return the number of entries visited,
380 : * #GNUNET_SYSERR if @a it aborted the iteration
381 : */
382 : int
383 : GNUNET_CONTAINER_multimap_get_multiple_ (
384 : struct GNUNET_CONTAINER_MultiMap *map,
385 : const void *key,
386 : GNUNET_CONTAINER_MultiMapIteratorCallback it,
387 : void *it_cls);
388 :
389 :
390 : /**
391 : * @ingroup hashmap
392 : * Create an iterator over a map. The map must not be modified
393 : * destructively (by a removal, or by an insertion that makes it
394 : * grow) while the iterator is in use.
395 : *
396 : * @param map the map to iterate over
397 : * @return a new iterator, to be destroyed with
398 : * #GNUNET_CONTAINER_multimap_iterator_destroy_()
399 : */
400 : struct GNUNET_CONTAINER_MultiMapIterator *
401 : GNUNET_CONTAINER_multimap_iterator_create_ (
402 : const struct GNUNET_CONTAINER_MultiMap *map);
403 :
404 :
405 : /**
406 : * @ingroup hashmap
407 : * Get the next key-value pair from an iterator.
408 : *
409 : * @param iter the iterator
410 : * @param[out] key set to a copy of the key of the entry, can be NULL
411 : * @param[out] value set to the value of the entry, can be NULL
412 : * @return #GNUNET_YES if an entry was returned,
413 : * #GNUNET_NO if all entries have been visited
414 : */
415 : enum GNUNET_GenericReturnValue
416 : GNUNET_CONTAINER_multimap_iterator_next_ (
417 : struct GNUNET_CONTAINER_MultiMapIterator *iter,
418 : void *key,
419 : const void **value);
420 :
421 :
422 : /**
423 : * @ingroup hashmap
424 : * Destroy an iterator.
425 : *
426 : * @param[in] iter the iterator to destroy
427 : */
428 : void
429 : GNUNET_CONTAINER_multimap_iterator_destroy_ (
430 : struct GNUNET_CONTAINER_MultiMapIterator *iter);
431 :
432 :
433 : /* ************************* typed wrappers ************************* */
434 :
435 : /**
436 : * Fail to compile if @a cond is false. Unlike #GNUNET_static_assert,
437 : * this is an expression, valid in C and C++.
438 : *
439 : * @param cond integer constant expression that must be true
440 : */
441 : #define GNUNET_CONTAINER_MULTIMAP_CHECK_(cond) \
442 : ((void) sizeof (char[(cond) ? 1 : -1]))
443 :
444 :
445 : /* The function definitions in the following macros are formatted by
446 : hand: uncrustify cannot tell that they are function definitions. */
447 : /* *INDENT-OFF* */
448 :
449 : /**
450 : * Wrappers that are the same whether the keys are passed by pointer
451 : * or by value. Used by #GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY and
452 : * #GNUNET_CONTAINER_MULTIMAP_DEFINE_VALKEY.
453 : */
454 : #define GNUNET_CONTAINER_MULTIMAP_DEFINE_COMMON_(prefix, MapType, IterType, \
455 : ValueType) \
456 : struct MapType; \
457 : struct IterType; \
458 : \
459 : static inline GNUNET_UNUSED void \
460 : prefix ## _destroy (struct MapType *map) \
461 : { \
462 : GNUNET_CONTAINER_multimap_destroy_ ( \
463 : (struct GNUNET_CONTAINER_MultiMap *) map); \
464 : } \
465 : \
466 : static inline GNUNET_UNUSED unsigned int \
467 : prefix ## _size (const struct MapType *map) \
468 : { \
469 : return GNUNET_CONTAINER_multimap_size_ ( \
470 : (const struct GNUNET_CONTAINER_MultiMap *) map); \
471 : } \
472 : \
473 : static inline GNUNET_UNUSED unsigned int \
474 : prefix ## _clear (struct MapType *map) \
475 : { \
476 : return GNUNET_CONTAINER_multimap_clear_ ( \
477 : (struct GNUNET_CONTAINER_MultiMap *) map); \
478 : } \
479 : \
480 : static inline GNUNET_UNUSED struct IterType * \
481 : prefix ## _iterator_create (const struct MapType *map) \
482 : { \
483 : return (struct IterType *) \
484 : GNUNET_CONTAINER_multimap_iterator_create_ ( \
485 : (const struct GNUNET_CONTAINER_MultiMap *) map); \
486 : } \
487 : \
488 : static inline GNUNET_UNUSED void \
489 : prefix ## _iterator_destroy (struct IterType *iter) \
490 : { \
491 : GNUNET_CONTAINER_multimap_iterator_destroy_ ( \
492 : (struct GNUNET_CONTAINER_MultiMapIterator *) iter); \
493 : } \
494 : \
495 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
496 : prefix ## _iterator_next_value_ (struct IterType *iter, \
497 : void *key, \
498 : const ValueType **value) \
499 : { \
500 : const void *v; \
501 : enum GNUNET_GenericReturnValue ret; \
502 : \
503 : ret = GNUNET_CONTAINER_multimap_iterator_next_ ( \
504 : (struct GNUNET_CONTAINER_MultiMapIterator *) iter, \
505 : key, \
506 : &v); \
507 : if ((GNUNET_YES == ret) && (NULL != value)) \
508 : { \
509 : *value = (const ValueType *) v; \
510 : } \
511 : return ret; \
512 : }
513 :
514 :
515 : /**
516 : * @ingroup hashmap
517 : * Define a hash map type whose keys are passed by pointer.
518 : *
519 : * Declares `struct MapType` (the map), `struct IterType` (an iterator
520 : * over it) and the callback type
521 : *
522 : * typedef enum GNUNET_GenericReturnValue
523 : * (*CbType)(void *cls, const KeyType *key, ValueType *value);
524 : *
525 : * and defines the following static inline functions:
526 : *
527 : * - `struct MapType *prefix_create (unsigned int len, int do_not_copy_keys)`
528 : * creates a map with @a len buckets to start with (it grows as
529 : * needed). If @a do_not_copy_keys is true and keys are longer than
530 : * 8 bytes, the map only keeps a pointer to each key, which must
531 : * then stay valid as long as the entry is in the map; see
532 : * #GNUNET_CONTAINER_MULTIMAP_FLAG_DO_NOT_COPY_KEYS. #GNUNET_NO is
533 : * always safe. Returns NULL on error.
534 : * - `struct MapType *prefix_create_unprotected (unsigned int len,
535 : * int do_not_copy_keys)` creates a map without protection against
536 : * hash flooding; see #GNUNET_CONTAINER_MULTIMAP_FLAG_UNPROTECTED
537 : * for when that is acceptable.
538 : * - `void prefix_destroy (struct MapType *map)`; does not free the
539 : * values.
540 : * - `unsigned int prefix_size (const struct MapType *map)`
541 : * - `ValueType *prefix_get (const struct MapType *map, const KeyType *key)`
542 : * returns a value stored under @a key (which one, if there are
543 : * several, is unspecified), or NULL.
544 : * - `enum GNUNET_GenericReturnValue prefix_contains (map, key)` and
545 : * `prefix_contains_value (map, key, const ValueType *value)` return
546 : * #GNUNET_YES or #GNUNET_NO.
547 : * - `enum GNUNET_GenericReturnValue prefix_put (map, key, ValueType *value,
548 : * enum GNUNET_CONTAINER_MultiHashMapOption opt)`; see
549 : * #GNUNET_CONTAINER_multimap_put_() for the return values.
550 : * - `enum GNUNET_GenericReturnValue prefix_remove (map, key,
551 : * const ValueType *value)` removes one key-value pair; returns
552 : * #GNUNET_YES if it was found, #GNUNET_NO if not.
553 : * - `int prefix_remove_all (map, key)` removes all values stored
554 : * under @a key and returns how many there were.
555 : * - `unsigned int prefix_clear (struct MapType *map)` removes all
556 : * entries and returns how many there were.
557 : * - `int prefix_iterate (map, CbType it, void *it_cls)` and
558 : * `int prefix_get_multiple (map, key, CbType it, void *it_cls)`
559 : * call @a it (which can be NULL) on every entry, or every entry
560 : * with the given key, and return the number of entries visited, or
561 : * #GNUNET_SYSERR if @a it returned anything but #GNUNET_OK. @a it
562 : * may remove entries, including the current one. For
563 : * prefix_get_multiple(), @a it gets the @a key pointer passed in;
564 : * for prefix_iterate(), the key is only valid during the call,
565 : * unless the map does not copy its keys.
566 : * - `struct IterType *prefix_iterator_create (const struct MapType *map)`,
567 : * `enum GNUNET_GenericReturnValue prefix_iterator_next (
568 : * struct IterType *iter, KeyType *key, const ValueType **value)`
569 : * (copies the next key-value pair to @a key and @a value, either of
570 : * which can be NULL, and returns #GNUNET_YES, or #GNUNET_NO at the
571 : * end) and `void prefix_iterator_destroy (struct IterType *iter)`
572 : * iterate without callbacks. The map must not be modified
573 : * destructively while an iterator is in use.
574 : *
575 : * where `map` is a `struct MapType *` (const for the lookups) and
576 : * `key` a `const KeyType *`. Callbacks go through a trampoline, so
577 : * no function pointer is ever cast to an incompatible type.
578 : *
579 : * @param prefix prefix for the function names, e.g.
580 : * GNUNET_CONTAINER_multihashmap
581 : * @param MapType tag of the map struct (without `struct`)
582 : * @param IterType tag of the iterator struct (without `struct`)
583 : * @param CbType name to give the callback type
584 : * @param KeyType type of the keys (with `struct` if it is one); its
585 : * size must not exceed #GNUNET_CONTAINER_MULTIMAP_MAX_KEY_SIZE
586 : * and its alignment must not exceed 8
587 : * @param ValueType type the values point to, `void` for untyped values
588 : */
589 : #define GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY(prefix, MapType, IterType, \
590 : CbType, KeyType, ValueType) \
591 : GNUNET_CONTAINER_MULTIMAP_DEFINE_COMMON_ (prefix, MapType, IterType, \
592 : ValueType) \
593 : \
594 : typedef enum GNUNET_GenericReturnValue \
595 : (*CbType)(void *cls, \
596 : const KeyType *key, \
597 : ValueType *value); \
598 : \
599 : struct prefix ## _Trampoline_ \
600 : { \
601 : CbType cb; \
602 : void *cb_cls; \
603 : }; \
604 : \
605 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
606 : prefix ## _trampoline_ (void *cls, \
607 : const void *key, \
608 : void *value) \
609 : { \
610 : const struct prefix ## _Trampoline_ *t = \
611 : (const struct prefix ## _Trampoline_ *) cls; \
612 : \
613 : return t->cb (t->cb_cls, \
614 : (const KeyType *) key, \
615 : (ValueType *) value); \
616 : } \
617 : \
618 : static inline GNUNET_UNUSED struct MapType * \
619 : prefix ## _create (unsigned int len, \
620 : int do_not_copy_keys) \
621 : { \
622 : GNUNET_CONTAINER_MULTIMAP_CHECK_ ( \
623 : sizeof (KeyType) <= GNUNET_CONTAINER_MULTIMAP_MAX_KEY_SIZE); \
624 : GNUNET_CONTAINER_MULTIMAP_CHECK_ (__alignof__ (KeyType) <= 8); \
625 : return (struct MapType *) GNUNET_CONTAINER_multimap_create_ ( \
626 : len, \
627 : sizeof (KeyType), \
628 : do_not_copy_keys \
629 : ? GNUNET_CONTAINER_MULTIMAP_FLAG_DO_NOT_COPY_KEYS \
630 : : GNUNET_CONTAINER_MULTIMAP_FLAG_NONE); \
631 : } \
632 : \
633 : static inline GNUNET_UNUSED struct MapType * \
634 : prefix ## _create_unprotected (unsigned int len, \
635 : int do_not_copy_keys) \
636 : { \
637 : GNUNET_CONTAINER_MULTIMAP_CHECK_ ( \
638 : sizeof (KeyType) <= GNUNET_CONTAINER_MULTIMAP_MAX_KEY_SIZE); \
639 : GNUNET_CONTAINER_MULTIMAP_CHECK_ (__alignof__ (KeyType) <= 8); \
640 : return (struct MapType *) GNUNET_CONTAINER_multimap_create_ ( \
641 : len, \
642 : sizeof (KeyType), \
643 : (enum GNUNET_CONTAINER_MultiMapFlags) \
644 : (GNUNET_CONTAINER_MULTIMAP_FLAG_UNPROTECTED \
645 : | (do_not_copy_keys \
646 : ? GNUNET_CONTAINER_MULTIMAP_FLAG_DO_NOT_COPY_KEYS \
647 : : GNUNET_CONTAINER_MULTIMAP_FLAG_NONE))); \
648 : } \
649 : \
650 : static inline GNUNET_UNUSED ValueType * \
651 : prefix ## _get (const struct MapType *map, \
652 : const KeyType *key) \
653 : { \
654 : return (ValueType *) GNUNET_CONTAINER_multimap_get_ ( \
655 : (const struct GNUNET_CONTAINER_MultiMap *) map, \
656 : key); \
657 : } \
658 : \
659 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
660 : prefix ## _contains (const struct MapType *map, \
661 : const KeyType *key) \
662 : { \
663 : return GNUNET_CONTAINER_multimap_contains_ ( \
664 : (const struct GNUNET_CONTAINER_MultiMap *) map, \
665 : key); \
666 : } \
667 : \
668 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
669 : prefix ## _contains_value (const struct MapType *map, \
670 : const KeyType *key, \
671 : const ValueType *value) \
672 : { \
673 : return GNUNET_CONTAINER_multimap_contains_value_ ( \
674 : (const struct GNUNET_CONTAINER_MultiMap *) map, \
675 : key, \
676 : value); \
677 : } \
678 : \
679 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
680 : prefix ## _put (struct MapType *map, \
681 : const KeyType *key, \
682 : ValueType *value, \
683 : enum GNUNET_CONTAINER_MultiHashMapOption opt) \
684 : { \
685 : return GNUNET_CONTAINER_multimap_put_ ( \
686 : (struct GNUNET_CONTAINER_MultiMap *) map, \
687 : key, \
688 : (void *) value, \
689 : opt); \
690 : } \
691 : \
692 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
693 : prefix ## _remove (struct MapType *map, \
694 : const KeyType *key, \
695 : const ValueType *value) \
696 : { \
697 : return GNUNET_CONTAINER_multimap_remove_ ( \
698 : (struct GNUNET_CONTAINER_MultiMap *) map, \
699 : key, \
700 : value); \
701 : } \
702 : \
703 : static inline GNUNET_UNUSED int \
704 : prefix ## _remove_all (struct MapType *map, \
705 : const KeyType *key) \
706 : { \
707 : return GNUNET_CONTAINER_multimap_remove_all_ ( \
708 : (struct GNUNET_CONTAINER_MultiMap *) map, \
709 : key); \
710 : } \
711 : \
712 : static inline GNUNET_UNUSED int \
713 : prefix ## _iterate (struct MapType *map, \
714 : CbType it, \
715 : void *it_cls) \
716 : { \
717 : struct prefix ## _Trampoline_ t; \
718 : \
719 : t.cb = it; \
720 : t.cb_cls = it_cls; \
721 : return GNUNET_CONTAINER_multimap_iterate_ ( \
722 : (struct GNUNET_CONTAINER_MultiMap *) map, \
723 : (NULL == it) ? NULL : &prefix ## _trampoline_, \
724 : &t); \
725 : } \
726 : \
727 : static inline GNUNET_UNUSED int \
728 : prefix ## _get_multiple (struct MapType *map, \
729 : const KeyType *key, \
730 : CbType it, \
731 : void *it_cls) \
732 : { \
733 : struct prefix ## _Trampoline_ t; \
734 : \
735 : t.cb = it; \
736 : t.cb_cls = it_cls; \
737 : return GNUNET_CONTAINER_multimap_get_multiple_ ( \
738 : (struct GNUNET_CONTAINER_MultiMap *) map, \
739 : key, \
740 : (NULL == it) ? NULL : &prefix ## _trampoline_, \
741 : &t); \
742 : } \
743 : \
744 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
745 : prefix ## _iterator_next (struct IterType *iter, \
746 : KeyType *key, \
747 : const ValueType **value) \
748 : { \
749 : return prefix ## _iterator_next_value_ (iter, \
750 : key, \
751 : value); \
752 : }
753 :
754 :
755 : /**
756 : * @ingroup hashmap
757 : * Define a hash map type whose keys are passed by value, for keys of
758 : * up to 8 bytes such as integers.
759 : *
760 : * Generates the same declarations and functions as
761 : * #GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY, except that
762 : *
763 : * - keys are passed as `KeyType key` instead of `const KeyType *key`,
764 : * also to the callbacks, whose type is
765 : *
766 : * typedef enum GNUNET_GenericReturnValue
767 : * (*CbType)(void *cls, KeyType key, ValueType *value);
768 : *
769 : * - `prefix_iterator_next()` still takes a `KeyType *` to store the
770 : * key in, and
771 : * - `prefix_create (unsigned int len)` and
772 : * `prefix_create_unprotected (unsigned int len)` have no
773 : * "do_not_copy_keys" argument, as keys of up to 8 bytes are always
774 : * stored in the entry.
775 : *
776 : * @param prefix prefix for the function names, e.g.
777 : * GNUNET_CONTAINER_multihashmap32
778 : * @param MapType tag of the map struct (without `struct`)
779 : * @param IterType tag of the iterator struct (without `struct`)
780 : * @param CbType name to give the callback type
781 : * @param KeyType type of the keys, at most 8 bytes, such as `uint32_t`
782 : * @param ValueType type the values point to, `void` for untyped values
783 : */
784 : #define GNUNET_CONTAINER_MULTIMAP_DEFINE_VALKEY(prefix, MapType, IterType, \
785 : CbType, KeyType, ValueType) \
786 : GNUNET_CONTAINER_MULTIMAP_DEFINE_COMMON_ (prefix, MapType, IterType, \
787 : ValueType) \
788 : \
789 : typedef enum GNUNET_GenericReturnValue \
790 : (*CbType)(void *cls, \
791 : KeyType key, \
792 : ValueType *value); \
793 : \
794 : struct prefix ## _Trampoline_ \
795 : { \
796 : CbType cb; \
797 : void *cb_cls; \
798 : }; \
799 : \
800 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
801 : prefix ## _trampoline_ (void *cls, \
802 : const void *key, \
803 : void *value) \
804 : { \
805 : const struct prefix ## _Trampoline_ *t = \
806 : (const struct prefix ## _Trampoline_ *) cls; \
807 : KeyType k; \
808 : \
809 : memcpy (&k, key, sizeof (k)); \
810 : return t->cb (t->cb_cls, \
811 : k, \
812 : (ValueType *) value); \
813 : } \
814 : \
815 : static inline GNUNET_UNUSED struct MapType * \
816 : prefix ## _create (unsigned int len) \
817 : { \
818 : GNUNET_CONTAINER_MULTIMAP_CHECK_ (sizeof (KeyType) <= 8); \
819 : return (struct MapType *) GNUNET_CONTAINER_multimap_create_ ( \
820 : len, \
821 : sizeof (KeyType), \
822 : GNUNET_CONTAINER_MULTIMAP_FLAG_NONE); \
823 : } \
824 : \
825 : static inline GNUNET_UNUSED struct MapType * \
826 : prefix ## _create_unprotected (unsigned int len) \
827 : { \
828 : GNUNET_CONTAINER_MULTIMAP_CHECK_ (sizeof (KeyType) <= 8); \
829 : return (struct MapType *) GNUNET_CONTAINER_multimap_create_ ( \
830 : len, \
831 : sizeof (KeyType), \
832 : GNUNET_CONTAINER_MULTIMAP_FLAG_UNPROTECTED); \
833 : } \
834 : \
835 : static inline GNUNET_UNUSED ValueType * \
836 : prefix ## _get (const struct MapType *map, \
837 : KeyType key) \
838 : { \
839 : return (ValueType *) GNUNET_CONTAINER_multimap_get_ ( \
840 : (const struct GNUNET_CONTAINER_MultiMap *) map, \
841 : &key); \
842 : } \
843 : \
844 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
845 : prefix ## _contains (const struct MapType *map, \
846 : KeyType key) \
847 : { \
848 : return GNUNET_CONTAINER_multimap_contains_ ( \
849 : (const struct GNUNET_CONTAINER_MultiMap *) map, \
850 : &key); \
851 : } \
852 : \
853 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
854 : prefix ## _contains_value (const struct MapType *map, \
855 : KeyType key, \
856 : const ValueType *value) \
857 : { \
858 : return GNUNET_CONTAINER_multimap_contains_value_ ( \
859 : (const struct GNUNET_CONTAINER_MultiMap *) map, \
860 : &key, \
861 : value); \
862 : } \
863 : \
864 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
865 : prefix ## _put (struct MapType *map, \
866 : KeyType key, \
867 : ValueType *value, \
868 : enum GNUNET_CONTAINER_MultiHashMapOption opt) \
869 : { \
870 : return GNUNET_CONTAINER_multimap_put_ ( \
871 : (struct GNUNET_CONTAINER_MultiMap *) map, \
872 : &key, \
873 : (void *) value, \
874 : opt); \
875 : } \
876 : \
877 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
878 : prefix ## _remove (struct MapType *map, \
879 : KeyType key, \
880 : const ValueType *value) \
881 : { \
882 : return GNUNET_CONTAINER_multimap_remove_ ( \
883 : (struct GNUNET_CONTAINER_MultiMap *) map, \
884 : &key, \
885 : value); \
886 : } \
887 : \
888 : static inline GNUNET_UNUSED int \
889 : prefix ## _remove_all (struct MapType *map, \
890 : KeyType key) \
891 : { \
892 : return GNUNET_CONTAINER_multimap_remove_all_ ( \
893 : (struct GNUNET_CONTAINER_MultiMap *) map, \
894 : &key); \
895 : } \
896 : \
897 : static inline GNUNET_UNUSED int \
898 : prefix ## _iterate (struct MapType *map, \
899 : CbType it, \
900 : void *it_cls) \
901 : { \
902 : struct prefix ## _Trampoline_ t; \
903 : \
904 : t.cb = it; \
905 : t.cb_cls = it_cls; \
906 : return GNUNET_CONTAINER_multimap_iterate_ ( \
907 : (struct GNUNET_CONTAINER_MultiMap *) map, \
908 : (NULL == it) ? NULL : &prefix ## _trampoline_, \
909 : &t); \
910 : } \
911 : \
912 : static inline GNUNET_UNUSED int \
913 : prefix ## _get_multiple (struct MapType *map, \
914 : KeyType key, \
915 : CbType it, \
916 : void *it_cls) \
917 : { \
918 : struct prefix ## _Trampoline_ t; \
919 : \
920 : t.cb = it; \
921 : t.cb_cls = it_cls; \
922 : return GNUNET_CONTAINER_multimap_get_multiple_ ( \
923 : (struct GNUNET_CONTAINER_MultiMap *) map, \
924 : &key, \
925 : (NULL == it) ? NULL : &prefix ## _trampoline_, \
926 : &t); \
927 : } \
928 : \
929 : static inline GNUNET_UNUSED enum GNUNET_GenericReturnValue \
930 : prefix ## _iterator_next (struct IterType *iter, \
931 : KeyType *key, \
932 : const ValueType **value) \
933 : { \
934 : return prefix ## _iterator_next_value_ (iter, \
935 : key, \
936 : value); \
937 : }
938 :
939 :
940 : /* *INDENT-ON* */
941 :
942 :
943 : /* *************************** the classics ************************* */
944 :
945 : /**
946 : * @ingroup hashmap
947 : * Map from `struct GNUNET_HashCode` to `void *`, with the iterator
948 : * `struct GNUNET_CONTAINER_MultiHashMapIterator` and the callback type
949 : * #GNUNET_CONTAINER_MultiHashMapIteratorCallback. Defines
950 : * GNUNET_CONTAINER_multihashmap_create() and the other functions
951 : * listed for #GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY.
952 : */
953 38439 : GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY (
954 : GNUNET_CONTAINER_multihashmap,
955 : GNUNET_CONTAINER_MultiHashMap,
956 : GNUNET_CONTAINER_MultiHashMapIterator,
957 : GNUNET_CONTAINER_MultiHashMapIteratorCallback,
958 : struct GNUNET_HashCode,
959 : void)
960 :
961 : /**
962 : * @ingroup hashmap
963 : * Map from `struct GNUNET_PeerIdentity` to `void *`, with the iterator
964 : * `struct GNUNET_CONTAINER_MultiPeerMapIterator` and the callback type
965 : * #GNUNET_CONTAINER_PeerMapIterator. Defines
966 : * GNUNET_CONTAINER_multipeermap_create() and the other functions
967 : * listed for #GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY.
968 : */
969 1801 : GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY (
970 : GNUNET_CONTAINER_multipeermap,
971 : GNUNET_CONTAINER_MultiPeerMap,
972 : GNUNET_CONTAINER_MultiPeerMapIterator,
973 : GNUNET_CONTAINER_PeerMapIterator,
974 : struct GNUNET_PeerIdentity,
975 : void)
976 :
977 : /**
978 : * @ingroup hashmap
979 : * Map from `struct GNUNET_ShortHashCode` to `void *`, with the
980 : * iterator `struct GNUNET_CONTAINER_MultiShortmapIterator` and the
981 : * callback type #GNUNET_CONTAINER_ShortmapIterator. Defines
982 : * GNUNET_CONTAINER_multishortmap_create() and the other functions
983 : * listed for #GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY.
984 : */
985 0 : GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY (
986 : GNUNET_CONTAINER_multishortmap,
987 : GNUNET_CONTAINER_MultiShortmap,
988 : GNUNET_CONTAINER_MultiShortmapIterator,
989 : GNUNET_CONTAINER_ShortmapIterator,
990 : struct GNUNET_ShortHashCode,
991 : void)
992 :
993 : /**
994 : * @ingroup hashmap
995 : * Map from `struct GNUNET_Uuid` to `void *`, with the iterator
996 : * `struct GNUNET_CONTAINER_MultiUuidmapIterator` and the callback type
997 : * #GNUNET_CONTAINER_MultiUuidmapIteratorCallback. Defines
998 : * GNUNET_CONTAINER_multiuuidmap_create() and the other functions
999 : * listed for #GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY.
1000 : */
1001 490 : GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY (
1002 : GNUNET_CONTAINER_multiuuidmap,
1003 : GNUNET_CONTAINER_MultiUuidmap,
1004 : GNUNET_CONTAINER_MultiUuidmapIterator,
1005 : GNUNET_CONTAINER_MultiUuidmapIteratorCallback,
1006 : struct GNUNET_Uuid,
1007 : void)
1008 :
1009 : /**
1010 : * @ingroup hashmap
1011 : * Map from `uint32_t` to `void *`, with the iterator
1012 : * `struct GNUNET_CONTAINER_MultiHashMap32Iterator` and the callback
1013 : * type #GNUNET_CONTAINER_MultiHashMapIterator32Callback. Defines
1014 : * GNUNET_CONTAINER_multihashmap32_create() and the other functions
1015 : * listed for #GNUNET_CONTAINER_MULTIMAP_DEFINE_VALKEY.
1016 : */
1017 2531 : GNUNET_CONTAINER_MULTIMAP_DEFINE_VALKEY (
1018 : GNUNET_CONTAINER_multihashmap32,
1019 : GNUNET_CONTAINER_MultiHashMap32,
1020 : GNUNET_CONTAINER_MultiHashMap32Iterator,
1021 : GNUNET_CONTAINER_MultiHashMapIterator32Callback,
1022 : uint32_t,
1023 : void)
1024 :
1025 :
1026 : #if 0 /* keep Emacsens' auto-indent happy */
1027 : {
1028 : #endif
1029 : #ifdef __cplusplus
1030 : }
1031 : #endif
1032 :
1033 :
1034 : /* ifndef GNUNET_HASHMAP_LIB_H */
1035 : #endif
1036 :
1037 : /** @} */ /* end of group hashmap */
1038 :
1039 : /** @} */ /* end of group addition to libgnunetutil */
1040 :
1041 : /* end of gnunet_hashmap_lib.h */
|