GNUnet 0.29.1-12-g57a93edc3
 
Loading...
Searching...
No Matches
container_multimap.c
Go to the documentation of this file.
1/*
2 This file is part of GNUnet.
3 Copyright (C) 2008, 2012, 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 */
28#include "platform.h"
29#include "gnunet_util_lib.h"
30
31#define LOG(kind, ...) \
32 GNUNET_log_from (kind, "util-container-multimap", __VA_ARGS__)
33
40#define NEXT_CACHE_SIZE 16
41
46#define MIN_MAP_LENGTH 2
47
51#define MAX_MAP_LENGTH (1U << 31)
52
57#define FIBONACCI_MULTIPLIER UINT64_C (0x9E3779B97F4A7C15)
58
63#if __BYTE_ORDER == __BIG_ENDIAN
64#define KEY_SHIFT(n) (64 - 8 * (n))
65#else
66#define KEY_SHIFT(n) 0
67#endif
68
72#define KEY_WORDS(n) (((n) + sizeof (uint64_t) - 1) / sizeof (uint64_t))
73
74
101
102
107{
111 struct MapEntry *next;
112
116 void *value;
117
122 union
123 {
127 uint64_t u64;
128
132 unsigned char bytes[sizeof (uint64_t)];
133
137 const void *ptr;
138 } k;
139
143 unsigned char key_copy[];
144};
145
146
151GNUNET_static_assert (0 == offsetof (struct MapEntry, key_copy) % 8);
152
153
158{
163
167 unsigned int size;
168
172 unsigned int map_length;
173
178 unsigned int shift;
179
187
193
198 unsigned int next_cache_off;
199
203 size_t key_size;
204
209
213 uint64_t sip_key[2];
214
222};
223
224
230{
234 struct MapEntry *me;
235
239 unsigned int idx;
240
246
251};
252
253
261static inline uint64_t
262rotl64 (uint64_t x,
263 unsigned int b)
264{
265 return (x << b) | (x >> (64 - b));
266}
267
268
274static inline void
275sip_round (uint64_t v[4])
276{
277 v[0] += v[1];
278 v[1] = rotl64 (v[1], 13);
279 v[1] ^= v[0];
280 v[0] = rotl64 (v[0], 32);
281 v[2] += v[3];
282 v[3] = rotl64 (v[3], 16);
283 v[3] ^= v[2];
284 v[0] += v[3];
285 v[3] = rotl64 (v[3], 21);
286 v[3] ^= v[0];
287 v[2] += v[1];
288 v[1] = rotl64 (v[1], 17);
289 v[1] ^= v[2];
290 v[2] = rotl64 (v[2], 32);
291}
292
293
304static inline uint64_t
305siphash13 (const uint64_t key[2],
306 const void *data,
307 size_t len)
308{
309 const unsigned char *in = data;
310 const unsigned char *end = in + (len - len % 8);
311 uint64_t v[4] = {
312 key[0] ^ UINT64_C (0x736f6d6570736575),
313 key[1] ^ UINT64_C (0x646f72616e646f6d),
314 key[0] ^ UINT64_C (0x6c7967656e657261),
315 key[1] ^ UINT64_C (0x7465646279746573)
316 };
317 uint64_t b = ((uint64_t) len) << 56;
318
319 for (; in != end; in += 8)
320 {
321 uint64_t m;
322
323 memcpy (&m,
324 in,
325 sizeof (m));
326 m = GNUNET_le64toh (m);
327 v[3] ^= m;
328 sip_round (v);
329 v[0] ^= m;
330 }
331 for (size_t i = 0; i < len % 8; i++)
332 b |= ((uint64_t) in[i]) << (8 * i);
333 v[3] ^= b;
334 sip_round (v);
335 v[0] ^= b;
336 v[2] ^= 0xff;
337 sip_round (v);
338 sip_round (v);
339 sip_round (v);
340 return v[0] ^ v[1] ^ v[2] ^ v[3];
341}
342
343
351static inline uint64_t
353 const void *key)
354{
355 union
356 {
357 uint64_t u64;
358 unsigned char bytes[sizeof (uint64_t)];
359 } w;
360
361 /* Common sizes are loaded as integers: copying a short key into a
362 zeroed word in memory and reading the word back stalls the CPU,
363 as the load cannot be forwarded from the stores. */
364 switch (map->key_size)
365 {
366 case 2:
367 {
368 uint16_t v;
369
370 memcpy (&v, key, sizeof (v));
371 return ((uint64_t) v) << KEY_SHIFT (2);
372 }
373 case 4:
374 {
375 uint32_t v;
376
377 memcpy (&v, key, sizeof (v));
378 return ((uint64_t) v) << KEY_SHIFT (4);
379 }
380 case 8:
381 memcpy (&w.u64, key, sizeof (w.u64));
382 return w.u64;
383 default:
384 w.u64 = 0;
385 memcpy (w.bytes, key, map->key_size);
386 return w.u64;
387 }
388}
389
390
398static inline uint64_t
400 const void *key)
401{
402 if (KS_INLINE_VALUE == map->storage)
403 return key_to_word (map,
404 key);
405 return 0;
406}
407
408
417static inline unsigned int
419 const void *key,
420 uint64_t kw)
421{
422 if (map->unprotected)
423 {
424 if (KS_INLINE_VALUE != map->storage)
425 memcpy (&kw,
426 key,
427 sizeof (kw));
428 return (unsigned int) ((kw * FIBONACCI_MULTIPLIER) >> map->shift);
429 }
430 /* SipHash over the whole key: anyone who can choose keys could
431 otherwise vary only the bytes that are not hashed */
432 if (KS_INLINE_VALUE == map->storage)
433 return (unsigned int) siphash13 (map->sip_key,
434 &kw,
435 sizeof (kw)) & (map->map_length - 1);
436 return (unsigned int) siphash13 (map->sip_key,
437 key,
438 map->key_size) & (map->map_length - 1);
439}
440
441
451static inline bool
453 const struct MapEntry *e,
454 const void *key,
455 uint64_t kw)
456{
457 if (KS_INLINE_VALUE == map->storage)
458 return kw == e->k.u64;
459 /* Common sizes get a memcmp() of constant size, which the compiler
460 inlines. */
461 switch (map->key_size)
462 {
463 case 16:
464 return 0 == memcmp (key, e->k.ptr, 16);
465 case 32:
466 return 0 == memcmp (key, e->k.ptr, 32);
467 case 64:
468 return 0 == memcmp (key, e->k.ptr, 64);
469 default:
470 return 0 == memcmp (key, e->k.ptr, map->key_size);
471 }
472}
473
474
482static inline const void *
484 const struct MapEntry *e)
485{
486 if (KS_INLINE_VALUE == map->storage)
487 return e->k.bytes;
488 return e->k.ptr;
489}
490
491
502static inline const void *
504 const struct MapEntry *e,
505 uint64_t *buf)
506{
507 if (KS_BORROWED == map->storage)
508 return e->k.ptr;
509 memcpy (buf,
510 entry_key (map, e),
511 map->key_size);
512 return buf;
513}
514
515
522static struct MapEntry **
523allocate_buckets (unsigned int len)
524{
525 size_t s;
526
527 s = (size_t) len * sizeof (struct MapEntry *);
528 if (s / sizeof (struct MapEntry *) != len)
529 return NULL; /* integer overflow on multiplication */
531 return GNUNET_new_array (len,
532 struct MapEntry *);
533 /* application *explicitly* requested a very large map (or the map
534 grew that much), hopefully it checks the return value... */
535 return GNUNET_malloc_large (s);
536}
537
538
541 size_t key_size,
543{
545 unsigned int map_length;
546 unsigned int bits;
547
548 GNUNET_assert ( (key_size > 0) &&
551 bits = 1;
552 while ( (map_length < len) &&
554 {
555 map_length *= 2;
556 bits++;
557 }
559 map->buckets = allocate_buckets (map_length);
560 if (NULL == map->buckets)
561 {
563 "Out of memory allocating large hash map (%u entries)\n",
564 len);
566 return NULL;
567 }
568 map->map_length = map_length;
569 map->shift = 64 - bits;
570 map->key_size = key_size;
572 map->unprotected = true;
573 else
575 sizeof (map->sip_key));
576 if (key_size <= sizeof (uint64_t))
577 map->storage = KS_INLINE_VALUE;
579 map->storage = KS_BORROWED;
580 else
581 map->storage = KS_INLINE_COPY;
582 return map;
583}
584
585
591static void
593{
594 for (unsigned int i = 0; i < map->map_length; i++)
595 {
596 struct MapEntry *e;
597
598 while (NULL != (e = map->buckets[i]))
599 {
600 map->buckets[i] = e->next;
601 GNUNET_free (e);
602 }
603 }
604 map->size = 0;
605}
606
607
608void
610{
611 GNUNET_assert (0 == map->next_cache_off);
613 GNUNET_free (map->buckets);
615}
616
617
618unsigned int
620{
621 return map->size;
622}
623
624
625void *
627 const void *key)
628{
629 uint64_t kw = lookup_word (map, key);
630
631 for (const struct MapEntry *e = map->buckets[bucket_of (map, key, kw)];
632 NULL != e;
633 e = e->next)
634 if (keys_equal (map, e, key, kw))
635 return e->value;
636 return NULL;
637}
638
639
642 const struct GNUNET_CONTAINER_MultiMap *map,
643 const void *key)
644{
645 uint64_t kw = lookup_word (map, key);
646
647 for (const struct MapEntry *e = map->buckets[bucket_of (map, key, kw)];
648 NULL != e;
649 e = e->next)
650 if (keys_equal (map, e, key, kw))
651 return GNUNET_YES;
652 return GNUNET_NO;
653}
654
655
658 const struct GNUNET_CONTAINER_MultiMap *map,
659 const void *key,
660 const void *value)
661{
662 uint64_t kw = lookup_word (map, key);
663
664 for (const struct MapEntry *e = map->buckets[bucket_of (map, key, kw)];
665 NULL != e;
666 e = e->next)
667 if ( (value == e->value) &&
668 keys_equal (map, e, key, kw) )
669 return GNUNET_YES;
670 return GNUNET_NO;
671}
672
673
674int
678 void *it_cls)
679{
680 uint64_t kc[KEY_WORDS (map->key_size)];
681 struct MapEntry **ce;
682 int count;
683
684 ce = &map->next_cache[map->next_cache_off];
685 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
686 count = 0;
687 for (unsigned int i = 0; i < map->map_length; i++)
688 {
689 struct MapEntry *e;
690
691 *ce = map->buckets[i];
692 while (NULL != (e = *ce))
693 {
694 /* advance first: if 'it' removes the next entry,
695 update_next_cache() moves *ce past it */
696 *ce = e->next;
697 if ( (NULL != it) &&
698 (GNUNET_OK != it (it_cls,
699 callback_key (map, e, kc),
700 e->value)) )
701 {
702 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
703 return GNUNET_SYSERR;
704 }
705 count++;
706 }
707 }
708 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
709 return count;
710}
711
712
720static void
722 const struct MapEntry *e)
723{
724 for (unsigned int i = 0; i < map->next_cache_off; i++)
725 if (map->next_cache[i] == e)
726 map->next_cache[i] = e->next;
727}
728
729
732 const void *key,
733 const void *value)
734{
735 uint64_t kw = lookup_word (map, key);
736 struct MapEntry **pp;
737
738 map->modification_counter++;
739 for (pp = &map->buckets[bucket_of (map, key, kw)];
740 NULL != *pp;
741 pp = &(*pp)->next)
742 {
743 struct MapEntry *e = *pp;
744
745 if ( (value == e->value) &&
746 keys_equal (map, e, key, kw) )
747 {
748 *pp = e->next;
750 GNUNET_free (e);
751 map->size--;
752 return GNUNET_YES;
753 }
754 }
755 return GNUNET_NO;
756}
757
758
759int
761 const void *key)
762{
763 uint64_t kw = lookup_word (map, key);
764 struct MapEntry **pp;
765 struct MapEntry *e;
766 int ret;
767
768 map->modification_counter++;
769 ret = 0;
770 pp = &map->buckets[bucket_of (map, key, kw)];
771 while (NULL != (e = *pp))
772 {
773 if (! keys_equal (map, e, key, kw))
774 {
775 pp = &e->next;
776 continue;
777 }
778 *pp = e->next;
780 GNUNET_free (e);
781 map->size--;
782 ret++;
783 }
784 return ret;
785}
786
787
788unsigned int
790{
791 unsigned int ret;
792
793 ret = map->size;
794 map->modification_counter++;
796 /* running iterations simply end: there is nothing left to visit */
797 for (unsigned int i = 0; i < map->next_cache_off; i++)
798 map->next_cache[i] = NULL;
799 return ret;
800}
801
802
808static void
810{
811 struct MapEntry **old_buckets;
812 struct MapEntry **new_buckets;
813 unsigned int old_len;
814
815 old_buckets = map->buckets;
816 old_len = map->map_length;
817 if (old_len >= MAX_MAP_LENGTH)
818 return; /* cannot grow any further */
819 new_buckets = allocate_buckets (old_len * 2);
820 if (NULL == new_buckets)
821 return; /* grow not possible */
822 map->modification_counter++;
823 map->map_length = old_len * 2;
824 map->shift--;
825 map->buckets = new_buckets;
826 for (unsigned int i = 0; i < old_len; i++)
827 {
828 struct MapEntry *e;
829
830 while (NULL != (e = old_buckets[i]))
831 {
832 unsigned int idx;
833
834 old_buckets[i] = e->next;
835 idx = bucket_of (map,
836 entry_key (map, e),
837 (KS_INLINE_VALUE == map->storage) ? e->k.u64 : 0);
838 e->next = new_buckets[idx];
839 new_buckets[idx] = e;
840 }
841 }
842 GNUNET_free (old_buckets);
843}
844
845
848 const void *key,
849 void *value,
851{
852 uint64_t kw = lookup_word (map, key);
853 unsigned int i;
854 struct MapEntry *e;
855
856 i = bucket_of (map, key, kw);
859 {
860 for (e = map->buckets[i]; NULL != e; e = e->next)
861 {
862 if (! keys_equal (map, e, key, kw))
863 continue;
865 return GNUNET_SYSERR;
866 e->value = value;
867 return GNUNET_NO;
868 }
869 }
870 if (map->size / 3 >= map->map_length / 4)
871 {
872 grow (map);
873 i = bucket_of (map, key, kw);
874 }
875 switch (map->storage)
876 {
877 case KS_INLINE_VALUE:
878 e = GNUNET_new (struct MapEntry);
879 e->k.u64 = kw;
880 break;
881 case KS_INLINE_COPY:
882 e = GNUNET_malloc (sizeof (struct MapEntry) + map->key_size);
883 memcpy (e->key_copy,
884 key,
885 map->key_size);
886 e->k.ptr = e->key_copy;
887 break;
888 case KS_BORROWED:
889 e = GNUNET_new (struct MapEntry);
890 e->k.ptr = key;
891 break;
892 default:
893 GNUNET_assert (0);
894 }
895 e->value = value;
896 e->next = map->buckets[i];
897 map->buckets[i] = e;
898 map->size++;
899 return GNUNET_OK;
900}
901
902
903int
906 const void *key,
908 void *it_cls)
909{
910 uint64_t kw = lookup_word (map, key);
911 struct MapEntry **ce;
912 struct MapEntry *e;
913 int count;
914
915 ce = &map->next_cache[map->next_cache_off];
916 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
917 count = 0;
918 *ce = map->buckets[bucket_of (map, key, kw)];
919 while (NULL != (e = *ce))
920 {
921 *ce = e->next;
922 if (! keys_equal (map, e, key, kw))
923 continue;
924 if ( (NULL != it) &&
925 (GNUNET_OK != it (it_cls,
926 key,
927 e->value)) )
928 {
929 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
930 return GNUNET_SYSERR;
931 }
932 count++;
933 }
934 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
935 return count;
936}
937
938
941 const struct GNUNET_CONTAINER_MultiMap *map)
942{
944
946 iter->map = map;
947 iter->modification_counter = map->modification_counter;
948 iter->me = map->buckets[0];
949 return iter;
950}
951
952
956 void *key,
957 const void **value)
958{
959 const struct GNUNET_CONTAINER_MultiMap *map = iter->map;
960
961 /* make sure the map has not been modified */
962 GNUNET_assert (iter->modification_counter == map->modification_counter);
963
964 /* look for the next entry, skipping empty buckets */
965 while (1)
966 {
967 if (iter->idx >= map->map_length)
968 return GNUNET_NO;
969 if (NULL != iter->me)
970 {
971 if (NULL != key)
972 memcpy (key,
973 entry_key (map, iter->me),
974 map->key_size);
975 if (NULL != value)
976 *value = iter->me->value;
977 iter->me = iter->me->next;
978 return GNUNET_YES;
979 }
980 iter->idx += 1;
981 if (iter->idx < map->map_length)
982 iter->me = map->buckets[iter->idx];
983 }
984}
985
986
987void
993
994
995/* end of container_multimap.c */
#define NEXT_CACHE_SIZE
Maximum recursion depth for callbacks of GNUNET_CONTAINER_multimap_get_multiple_() themselves again c...
#define KEY_WORDS(n)
Number of 64-bit words needed to hold a key of n bytes.
#define MIN_MAP_LENGTH
Smallest number of buckets of a map.
static const void * entry_key(const struct GNUNET_CONTAINER_MultiMap *map, const struct MapEntry *e)
Get where the key of an entry is.
static uint64_t siphash13(const uint64_t key[2], const void *data, size_t len)
SipHash-1-3 (one compression and three finalization rounds), the variant hash tables such as Rust's u...
static uint64_t key_to_word(const struct GNUNET_CONTAINER_MultiMap *map, const void *key)
Convert a key of at most 8 bytes to the form it is stored in.
static void free_entries(struct GNUNET_CONTAINER_MultiMap *map)
Free all entries of a map, leaving its buckets empty.
#define MAX_MAP_LENGTH
Largest number of buckets of a map (a power of two).
KeyStorage
How the keys of a map are stored.
@ KS_INLINE_VALUE
The key has at most 8 bytes.
@ KS_BORROWED
The key is longer than 8 bytes and was not copied: k.ptr points to memory that the application keeps ...
@ KS_INLINE_COPY
The key is longer than 8 bytes and was copied: the entry was allocated with key_size extra bytes for ...
static struct MapEntry ** allocate_buckets(unsigned int len)
Allocate a bucket array.
static uint64_t rotl64(uint64_t x, unsigned int b)
Rotate a 64-bit word left.
#define KEY_SHIFT(n)
How far to shift a key of n bytes, loaded as an integer, to put it into the first n bytes (in memory)...
static const void * callback_key(const struct GNUNET_CONTAINER_MultiMap *map, const struct MapEntry *e, uint64_t *buf)
Get the key of an entry to give to a callback.
static bool keys_equal(const struct GNUNET_CONTAINER_MultiMap *map, const struct MapEntry *e, const void *key, uint64_t kw)
Check if an entry has a key.
#define FIBONACCI_MULTIPLIER
2^64 divided by the golden ratio, rounded to an odd number; the multiplier for Fibonacci hashing,...
static void update_next_cache(struct GNUNET_CONTAINER_MultiMap *map, const struct MapEntry *e)
We are about to free() e, make sure it is not in the list of next values for any iteration in the map...
static uint64_t lookup_word(const struct GNUNET_CONTAINER_MultiMap *map, const void *key)
Prepare a key for looking it up in a map.
static unsigned int bucket_of(const struct GNUNET_CONTAINER_MultiMap *map, const void *key, uint64_t kw)
Compute the bucket for a key.
#define LOG(kind,...)
static void grow(struct GNUNET_CONTAINER_MultiMap *map)
Grow the given map to a more appropriate size.
static void sip_round(uint64_t v[4])
One SipRound.
static struct GNUNET_ARM_MonitorHandle * m
Monitor connection with ARM.
Definition gnunet-arm.c:103
static int ret
Final status code.
Definition gnunet-arm.c:93
static int end
Set if we are to shutdown all services (including ARM).
Definition gnunet-arm.c:33
static char * data
The data to insert into the dht.
struct GNUNET_HashCode key
The key used in the DHT.
static char * value
Value of the record to add/remove.
void GNUNET_CRYPTO_random_block(void *buffer, size_t length)
Fill block with a random values.
int GNUNET_CONTAINER_multimap_iterate_(struct GNUNET_CONTAINER_MultiMap *map, GNUNET_CONTAINER_MultiMapIteratorCallback it, void *it_cls)
Call a function on every key-value pair of a map.
unsigned int GNUNET_CONTAINER_multimap_clear_(struct GNUNET_CONTAINER_MultiMap *map)
Remove all key-value pairs from a map.
struct GNUNET_CONTAINER_MultiMapIterator * GNUNET_CONTAINER_multimap_iterator_create_(const struct GNUNET_CONTAINER_MultiMap *map)
Create an iterator over a map.
void GNUNET_CONTAINER_multimap_iterator_destroy_(struct GNUNET_CONTAINER_MultiMapIterator *iter)
Destroy an iterator.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multimap_contains_(const struct GNUNET_CONTAINER_MultiMap *map, const void *key)
Check if the map has any value stored under a key.
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_MultiMapIteratorCallback)(void *cls, const void *key, void *value)
Iterator over the entries of a map with untyped keys and values.
GNUNET_CONTAINER_MultiHashMapOption
Options for storing values in the HashMap.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multimap_remove_(struct GNUNET_CONTAINER_MultiMap *map, const void *key, const void *value)
Remove a key-value pair from a map.
void GNUNET_CONTAINER_multimap_destroy_(struct GNUNET_CONTAINER_MultiMap *map)
Destroy a map.
#define GNUNET_CONTAINER_MULTIMAP_MAX_KEY_SIZE
Largest key size (in bytes) a map supports.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multimap_put_(struct GNUNET_CONTAINER_MultiMap *map, const void *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in a map.
unsigned int GNUNET_CONTAINER_multimap_size_(const struct GNUNET_CONTAINER_MultiMap *map)
Get the number of key-value pairs in a map.
void * GNUNET_CONTAINER_multimap_get_(const struct GNUNET_CONTAINER_MultiMap *map, const void *key)
Get a value stored under a key.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multimap_iterator_next_(struct GNUNET_CONTAINER_MultiMapIterator *iter, void *key, const void **value)
Get the next key-value pair from an iterator.
struct GNUNET_CONTAINER_MultiMap * GNUNET_CONTAINER_multimap_create_(unsigned int len, size_t key_size, enum GNUNET_CONTAINER_MultiMapFlags flags)
Create a map.
int GNUNET_CONTAINER_multimap_remove_all_(struct GNUNET_CONTAINER_MultiMap *map, const void *key)
Remove all values stored under a key from a map.
int GNUNET_CONTAINER_multimap_get_multiple_(struct GNUNET_CONTAINER_MultiMap *map, const void *key, GNUNET_CONTAINER_MultiMapIteratorCallback it, void *it_cls)
Call a function on every value stored under a key.
GNUNET_CONTAINER_MultiMapFlags
Flags for GNUNET_CONTAINER_multimap_create_().
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multimap_contains_value_(const struct GNUNET_CONTAINER_MultiMap *map, const void *key, const void *value)
Check if the map has a particular key-value pair.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
, ' bother checking if a value already exists (faster than GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE...
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE
Allow multiple values with the same key.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY
There must only be one value per key; storing a value should fail if a value under the same key alrea...
@ GNUNET_CONTAINER_MULTIMAP_FLAG_UNPROTECTED
Do not protect the map against hash flooding.
@ GNUNET_CONTAINER_MULTIMAP_FLAG_DO_NOT_COPY_KEYS
Do not copy keys longer than 8 bytes into the map, only keep a pointer to them.
#define GNUNET_le64toh(x)
GNUNET_GenericReturnValue
Named constants for return values.
#define GNUNET_static_assert(cond)
@ GNUNET_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
@ GNUNET_ERROR_TYPE_WARNING
#define GNUNET_MAX_MALLOC_CHECKED
Maximum allocation with GNUNET_malloc macro.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
#define GNUNET_free(ptr)
Wrapper around free.
static struct GNUNET_CONTAINER_MultiPeerMap * map
Peermap of PeerIdentities to "struct PeerEntry" (for fast lookup).
Definition peer.c:63
unsigned int idx
Current bucket index.
const struct GNUNET_CONTAINER_MultiMap * map
Map that we are iterating over.
struct MapEntry * me
Position in the bucket idx.
unsigned int modification_counter
Modification counter as observed on the map when the iterator was created.
Internal representation of a map.
uint64_t sip_key[2]
Random SipHash key of this map, unless it is unprotected.
enum KeyStorage storage
How keys are stored.
struct MapEntry ** buckets
All of our buckets, map_length many.
struct MapEntry * next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multimap_iterate_() a...
bool unprotected
True if the map was created with GNUNET_CONTAINER_MULTIMAP_FLAG_UNPROTECTED: buckets are then chosen ...
size_t key_size
Size of the keys in bytes.
unsigned int size
Number of entries in the map.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
unsigned int map_length
Length of the buckets array, always a power of two.
unsigned int next_cache_off
Offset of next_cache entries in use, must be smaller than NEXT_CACHE_SIZE.
unsigned int shift
64 minus the binary logarithm of map_length, for Fibonacci hashing.
An entry in a map.
const void * ptr
KS_INLINE_COPY and KS_BORROWED: the key_size bytes of the key.
unsigned char key_copy[]
KS_INLINE_COPY only: the key; allocated with the entry.
union MapEntry::@43 k
The key itself (KS_INLINE_VALUE), or where to find it (the other kinds of storage).
void * value
The application's value.
uint64_t u64
KS_INLINE_VALUE: the key, zero-extended, for comparing.
struct MapEntry * next
Next entry in the same bucket.
unsigned char bytes[sizeof(uint64_t)]
KS_INLINE_VALUE: the key, as the first key_size bytes.