GNUnet 0.29.1-12-g57a93edc3
 
Loading...
Searching...
No Matches
container_multimap.c File Reference

hash map for fixed-size keys where the same key may be present multiple times; the implementation behind all the maps in gnunet_hashmap_lib.h More...

#include "platform.h"
#include "gnunet_util_lib.h"
Include dependency graph for container_multimap.c:

Go to the source code of this file.

Data Structures

struct  MapEntry
 An entry in a map. More...
 
struct  GNUNET_CONTAINER_MultiMap
 Internal representation of a map. More...
 
struct  GNUNET_CONTAINER_MultiMapIterator
 Cursor into a map. More...
 

Macros

#define LOG(kind, ...)    GNUNET_log_from (kind, "util-container-multimap", __VA_ARGS__)
 
#define NEXT_CACHE_SIZE   16
 Maximum recursion depth for callbacks of GNUNET_CONTAINER_multimap_get_multiple_() themselves again calling GNUNET_CONTAINER_multimap_get_multiple_().
 
#define MIN_MAP_LENGTH   2
 Smallest number of buckets of a map.
 
#define MAX_MAP_LENGTH   (1U << 31)
 Largest number of buckets of a map (a power of two).
 
#define FIBONACCI_MULTIPLIER   UINT64_C (0x9E3779B97F4A7C15)
 2^64 divided by the golden ratio, rounded to an odd number; the multiplier for Fibonacci hashing, which unprotected maps use.
 
#define KEY_SHIFT(n)   (64 - 8 * (n))
 How far to shift a key of n bytes, loaded as an integer, to put it into the first n bytes (in memory) of a 64-bit word.
 
#define KEY_WORDS(n)   (((n) + sizeof (uint64_t) - 1) / sizeof (uint64_t))
 Number of 64-bit words needed to hold a key of n bytes.
 

Enumerations

enum  KeyStorage { KS_INLINE_VALUE , KS_INLINE_COPY , KS_BORROWED }
 How the keys of a map are stored. More...
 

Functions

 GNUNET_static_assert (0==offsetof(struct MapEntry, key_copy) % 8)
 Copied keys must be aligned at least as well as the keys that applications use (see GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY).
 
static uint64_t rotl64 (uint64_t x, unsigned int b)
 Rotate a 64-bit word left.
 
static void sip_round (uint64_t v[4])
 One SipRound.
 
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 use, as it is still a strong pseudo-random function for that purpose.
 
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 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.
 
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.
 
static const void * entry_key (const struct GNUNET_CONTAINER_MultiMap *map, const struct MapEntry *e)
 Get where the key of an entry is.
 
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 struct MapEntry ** allocate_buckets (unsigned int len)
 Allocate a bucket array.
 
struct GNUNET_CONTAINER_MultiMap * GNUNET_CONTAINER_multimap_create_ (unsigned int len, size_t key_size, enum GNUNET_CONTAINER_MultiMapFlags flags)
 Create a map.
 
static void free_entries (struct GNUNET_CONTAINER_MultiMap *map)
 Free all entries of a map, leaving its buckets empty.
 
void GNUNET_CONTAINER_multimap_destroy_ (struct GNUNET_CONTAINER_MultiMap *map)
 Destroy 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_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_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.
 
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.
 
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's next_cache.
 
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.
 
int GNUNET_CONTAINER_multimap_remove_all_ (struct GNUNET_CONTAINER_MultiMap *map, const void *key)
 Remove all values stored under a key from a map.
 
unsigned int GNUNET_CONTAINER_multimap_clear_ (struct GNUNET_CONTAINER_MultiMap *map)
 Remove all key-value pairs from a map.
 
static void grow (struct GNUNET_CONTAINER_MultiMap *map)
 Grow the given map to a more appropriate size.
 
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.
 
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.
 
struct GNUNET_CONTAINER_MultiMapIterator * GNUNET_CONTAINER_multimap_iterator_create_ (const struct GNUNET_CONTAINER_MultiMap *map)
 Create an iterator over a map.
 
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.
 
void GNUNET_CONTAINER_multimap_iterator_destroy_ (struct GNUNET_CONTAINER_MultiMapIterator *iter)
 Destroy an iterator.
 

Detailed Description

hash map for fixed-size keys where the same key may be present multiple times; the implementation behind all the maps in gnunet_hashmap_lib.h

Author
Christian Grothoff

Definition in file container_multimap.c.

Macro Definition Documentation

◆ LOG

#define LOG (   kind,
  ... 
)     GNUNET_log_from (kind, "util-container-multimap", __VA_ARGS__)

Definition at line 31 of file container_multimap.c.

78{
85
92
99};
100
101
105struct MapEntry
106{
110 struct MapEntry *next;
111
115 void *value;
116
121 union
122 {
126 uint64_t u64;
127
131 unsigned char bytes[sizeof (uint64_t)];
132
136 const void *ptr;
137 } k;
138
142 unsigned char key_copy[];
143};
144
145
150GNUNET_static_assert (0 == offsetof (struct MapEntry, key_copy) % 8);
151
152
157{
161 struct MapEntry **buckets;
162
166 unsigned int size;
167
171 unsigned int map_length;
172
177 unsigned int shift;
178
185 bool unprotected;
186
191 unsigned int modification_counter;
192
197 unsigned int next_cache_off;
198
202 size_t key_size;
203
207 enum KeyStorage storage;
208
212 uint64_t sip_key[2];
213
221};
222
223
229{
233 struct MapEntry *me;
234
238 unsigned int idx;
239
244 unsigned int modification_counter;
245
249 const struct GNUNET_CONTAINER_MultiMap *map;
250};
251
252
260static inline uint64_t
261rotl64 (uint64_t x,
262 unsigned int b)
263{
264 return (x << b) | (x >> (64 - b));
265}
266
267
273static inline void
274sip_round (uint64_t v[4])
275{
276 v[0] += v[1];
277 v[1] = rotl64 (v[1], 13);
278 v[1] ^= v[0];
279 v[0] = rotl64 (v[0], 32);
280 v[2] += v[3];
281 v[3] = rotl64 (v[3], 16);
282 v[3] ^= v[2];
283 v[0] += v[3];
284 v[3] = rotl64 (v[3], 21);
285 v[3] ^= v[0];
286 v[2] += v[1];
287 v[1] = rotl64 (v[1], 17);
288 v[1] ^= v[2];
289 v[2] = rotl64 (v[2], 32);
290}
291
292
303static inline uint64_t
304siphash13 (const uint64_t key[2],
305 const void *data,
306 size_t len)
307{
308 const unsigned char *in = data;
309 const unsigned char *end = in + (len - len % 8);
310 uint64_t v[4] = {
311 key[0] ^ UINT64_C (0x736f6d6570736575),
312 key[1] ^ UINT64_C (0x646f72616e646f6d),
313 key[0] ^ UINT64_C (0x6c7967656e657261),
314 key[1] ^ UINT64_C (0x7465646279746573)
315 };
316 uint64_t b = ((uint64_t) len) << 56;
317
318 for (; in != end; in += 8)
319 {
320 uint64_t m;
321
322 memcpy (&m,
323 in,
324 sizeof (m));
325 m = GNUNET_le64toh (m);
326 v[3] ^= m;
327 sip_round (v);
328 v[0] ^= m;
329 }
330 for (size_t i = 0; i < len % 8; i++)
331 b |= ((uint64_t) in[i]) << (8 * i);
332 v[3] ^= b;
333 sip_round (v);
334 v[0] ^= b;
335 v[2] ^= 0xff;
336 sip_round (v);
337 sip_round (v);
338 sip_round (v);
339 return v[0] ^ v[1] ^ v[2] ^ v[3];
340}
341
342
350static inline uint64_t
352 const void *key)
353{
354 union
355 {
356 uint64_t u64;
357 unsigned char bytes[sizeof (uint64_t)];
358 } w;
359
360 /* Common sizes are loaded as integers: copying a short key into a
361 zeroed word in memory and reading the word back stalls the CPU,
362 as the load cannot be forwarded from the stores. */
363 switch (map->key_size)
364 {
365 case 2:
366 {
367 uint16_t v;
368
369 memcpy (&v, key, sizeof (v));
370 return ((uint64_t) v) << KEY_SHIFT (2);
371 }
372 case 4:
373 {
374 uint32_t v;
375
376 memcpy (&v, key, sizeof (v));
377 return ((uint64_t) v) << KEY_SHIFT (4);
378 }
379 case 8:
380 memcpy (&w.u64, key, sizeof (w.u64));
381 return w.u64;
382 default:
383 w.u64 = 0;
384 memcpy (w.bytes, key, map->key_size);
385 return w.u64;
386 }
387}
388
389
397static inline uint64_t
399 const void *key)
400{
401 if (KS_INLINE_VALUE == map->storage)
402 return key_to_word (map,
403 key);
404 return 0;
405}
406
407
416static inline unsigned int
418 const void *key,
419 uint64_t kw)
420{
421 if (map->unprotected)
422 {
423 if (KS_INLINE_VALUE != map->storage)
424 memcpy (&kw,
425 key,
426 sizeof (kw));
427 return (unsigned int) ((kw * FIBONACCI_MULTIPLIER) >> map->shift);
428 }
429 /* SipHash over the whole key: anyone who can choose keys could
430 otherwise vary only the bytes that are not hashed */
431 if (KS_INLINE_VALUE == map->storage)
432 return (unsigned int) siphash13 (map->sip_key,
433 &kw,
434 sizeof (kw)) & (map->map_length - 1);
435 return (unsigned int) siphash13 (map->sip_key,
436 key,
437 map->key_size) & (map->map_length - 1);
438}
439
440
450static inline bool
452 const struct MapEntry *e,
453 const void *key,
454 uint64_t kw)
455{
456 if (KS_INLINE_VALUE == map->storage)
457 return kw == e->k.u64;
458 /* Common sizes get a memcmp() of constant size, which the compiler
459 inlines. */
460 switch (map->key_size)
461 {
462 case 16:
463 return 0 == memcmp (key, e->k.ptr, 16);
464 case 32:
465 return 0 == memcmp (key, e->k.ptr, 32);
466 case 64:
467 return 0 == memcmp (key, e->k.ptr, 64);
468 default:
469 return 0 == memcmp (key, e->k.ptr, map->key_size);
470 }
471}
472
473
481static inline const void *
483 const struct MapEntry *e)
484{
485 if (KS_INLINE_VALUE == map->storage)
486 return e->k.bytes;
487 return e->k.ptr;
488}
489
490
501static inline const void *
503 const struct MapEntry *e,
504 uint64_t *buf)
505{
506 if (KS_BORROWED == map->storage)
507 return e->k.ptr;
508 memcpy (buf,
509 entry_key (map, e),
510 map->key_size);
511 return buf;
512}
513
514
521static struct MapEntry **
522allocate_buckets (unsigned int len)
523{
524 size_t s;
525
526 s = (size_t) len * sizeof (struct MapEntry *);
527 if (s / sizeof (struct MapEntry *) != len)
528 return NULL; /* integer overflow on multiplication */
530 return GNUNET_new_array (len,
531 struct MapEntry *);
532 /* application *explicitly* requested a very large map (or the map
533 grew that much), hopefully it checks the return value... */
534 return GNUNET_malloc_large (s);
535}
536
537
539GNUNET_CONTAINER_multimap_create_ (unsigned int len,
540 size_t key_size,
542{
544 unsigned int map_length;
545 unsigned int bits;
546
547 GNUNET_assert ( (key_size > 0) &&
550 bits = 1;
551 while ( (map_length < len) &&
553 {
554 map_length *= 2;
555 bits++;
556 }
558 map->buckets = allocate_buckets (map_length);
559 if (NULL == map->buckets)
560 {
562 "Out of memory allocating large hash map (%u entries)\n",
563 len);
565 return NULL;
566 }
567 map->map_length = map_length;
568 map->shift = 64 - bits;
569 map->key_size = key_size;
571 map->unprotected = true;
572 else
574 sizeof (map->sip_key));
575 if (key_size <= sizeof (uint64_t))
576 map->storage = KS_INLINE_VALUE;
578 map->storage = KS_BORROWED;
579 else
580 map->storage = KS_INLINE_COPY;
581 return map;
582}
583
584
590static void
592{
593 for (unsigned int i = 0; i < map->map_length; i++)
594 {
595 struct MapEntry *e;
596
597 while (NULL != (e = map->buckets[i]))
598 {
599 map->buckets[i] = e->next;
600 GNUNET_free (e);
601 }
602 }
603 map->size = 0;
604}
605
606
607void
609{
610 GNUNET_assert (0 == map->next_cache_off);
612 GNUNET_free (map->buckets);
614}
615
616
617unsigned int
619{
620 return map->size;
621}
622
623
624void *
626 const void *key)
627{
628 uint64_t kw = lookup_word (map, key);
629
630 for (const struct MapEntry *e = map->buckets[bucket_of (map, key, kw)];
631 NULL != e;
632 e = e->next)
633 if (keys_equal (map, e, key, kw))
634 return e->value;
635 return NULL;
636}
637
638
641 const struct GNUNET_CONTAINER_MultiMap *map,
642 const void *key)
643{
644 uint64_t kw = lookup_word (map, key);
645
646 for (const struct MapEntry *e = map->buckets[bucket_of (map, key, kw)];
647 NULL != e;
648 e = e->next)
649 if (keys_equal (map, e, key, kw))
650 return GNUNET_YES;
651 return GNUNET_NO;
652}
653
654
657 const struct GNUNET_CONTAINER_MultiMap *map,
658 const void *key,
659 const void *value)
660{
661 uint64_t kw = lookup_word (map, key);
662
663 for (const struct MapEntry *e = map->buckets[bucket_of (map, key, kw)];
664 NULL != e;
665 e = e->next)
666 if ( (value == e->value) &&
667 keys_equal (map, e, key, kw) )
668 return GNUNET_YES;
669 return GNUNET_NO;
670}
671
672
673int
677 void *it_cls)
678{
679 uint64_t kc[KEY_WORDS (map->key_size)];
680 struct MapEntry **ce;
681 int count;
682
683 ce = &map->next_cache[map->next_cache_off];
684 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
685 count = 0;
686 for (unsigned int i = 0; i < map->map_length; i++)
687 {
688 struct MapEntry *e;
689
690 *ce = map->buckets[i];
691 while (NULL != (e = *ce))
692 {
693 /* advance first: if 'it' removes the next entry,
694 update_next_cache() moves *ce past it */
695 *ce = e->next;
696 if ( (NULL != it) &&
697 (GNUNET_OK != it (it_cls,
698 callback_key (map, e, kc),
699 e->value)) )
700 {
701 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
702 return GNUNET_SYSERR;
703 }
704 count++;
705 }
706 }
707 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
708 return count;
709}
710
711
719static void
721 const struct MapEntry *e)
722{
723 for (unsigned int i = 0; i < map->next_cache_off; i++)
724 if (map->next_cache[i] == e)
725 map->next_cache[i] = e->next;
726}
727
728
731 const void *key,
732 const void *value)
733{
734 uint64_t kw = lookup_word (map, key);
735 struct MapEntry **pp;
736
737 map->modification_counter++;
738 for (pp = &map->buckets[bucket_of (map, key, kw)];
739 NULL != *pp;
740 pp = &(*pp)->next)
741 {
742 struct MapEntry *e = *pp;
743
744 if ( (value == e->value) &&
745 keys_equal (map, e, key, kw) )
746 {
747 *pp = e->next;
749 GNUNET_free (e);
750 map->size--;
751 return GNUNET_YES;
752 }
753 }
754 return GNUNET_NO;
755}
756
757
758int
760 const void *key)
761{
762 uint64_t kw = lookup_word (map, key);
763 struct MapEntry **pp;
764 struct MapEntry *e;
765 int ret;
766
767 map->modification_counter++;
768 ret = 0;
769 pp = &map->buckets[bucket_of (map, key, kw)];
770 while (NULL != (e = *pp))
771 {
772 if (! keys_equal (map, e, key, kw))
773 {
774 pp = &e->next;
775 continue;
776 }
777 *pp = e->next;
779 GNUNET_free (e);
780 map->size--;
781 ret++;
782 }
783 return ret;
784}
785
786
787unsigned int
789{
790 unsigned int ret;
791
792 ret = map->size;
793 map->modification_counter++;
795 /* running iterations simply end: there is nothing left to visit */
796 for (unsigned int i = 0; i < map->next_cache_off; i++)
797 map->next_cache[i] = NULL;
798 return ret;
799}
800
801
807static void
809{
810 struct MapEntry **old_buckets;
811 struct MapEntry **new_buckets;
812 unsigned int old_len;
813
814 old_buckets = map->buckets;
815 old_len = map->map_length;
816 if (old_len >= MAX_MAP_LENGTH)
817 return; /* cannot grow any further */
818 new_buckets = allocate_buckets (old_len * 2);
819 if (NULL == new_buckets)
820 return; /* grow not possible */
821 map->modification_counter++;
822 map->map_length = old_len * 2;
823 map->shift--;
824 map->buckets = new_buckets;
825 for (unsigned int i = 0; i < old_len; i++)
826 {
827 struct MapEntry *e;
828
829 while (NULL != (e = old_buckets[i]))
830 {
831 unsigned int idx;
832
833 old_buckets[i] = e->next;
834 idx = bucket_of (map,
835 entry_key (map, e),
836 (KS_INLINE_VALUE == map->storage) ? e->k.u64 : 0);
837 e->next = new_buckets[idx];
838 new_buckets[idx] = e;
839 }
840 }
841 GNUNET_free (old_buckets);
842}
843
844
847 const void *key,
848 void *value,
850{
851 uint64_t kw = lookup_word (map, key);
852 unsigned int i;
853 struct MapEntry *e;
854
855 i = bucket_of (map, key, kw);
858 {
859 for (e = map->buckets[i]; NULL != e; e = e->next)
860 {
861 if (! keys_equal (map, e, key, kw))
862 continue;
864 return GNUNET_SYSERR;
865 e->value = value;
866 return GNUNET_NO;
867 }
868 }
869 if (map->size / 3 >= map->map_length / 4)
870 {
871 grow (map);
872 i = bucket_of (map, key, kw);
873 }
874 switch (map->storage)
875 {
876 case KS_INLINE_VALUE:
877 e = GNUNET_new (struct MapEntry);
878 e->k.u64 = kw;
879 break;
880 case KS_INLINE_COPY:
881 e = GNUNET_malloc (sizeof (struct MapEntry) + map->key_size);
882 memcpy (e->key_copy,
883 key,
884 map->key_size);
885 e->k.ptr = e->key_copy;
886 break;
887 case KS_BORROWED:
888 e = GNUNET_new (struct MapEntry);
889 e->k.ptr = key;
890 break;
891 default:
892 GNUNET_assert (0);
893 }
894 e->value = value;
895 e->next = map->buckets[i];
896 map->buckets[i] = e;
897 map->size++;
898 return GNUNET_OK;
899}
900
901
902int
905 const void *key,
907 void *it_cls)
908{
909 uint64_t kw = lookup_word (map, key);
910 struct MapEntry **ce;
911 struct MapEntry *e;
912 int count;
913
914 ce = &map->next_cache[map->next_cache_off];
915 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
916 count = 0;
917 *ce = map->buckets[bucket_of (map, key, kw)];
918 while (NULL != (e = *ce))
919 {
920 *ce = e->next;
921 if (! keys_equal (map, e, key, kw))
922 continue;
923 if ( (NULL != it) &&
924 (GNUNET_OK != it (it_cls,
925 key,
926 e->value)) )
927 {
928 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
929 return GNUNET_SYSERR;
930 }
931 count++;
932 }
933 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
934 return count;
935}
936
937
940 const struct GNUNET_CONTAINER_MultiMap *map)
941{
943
945 iter->map = map;
946 iter->modification_counter = map->modification_counter;
947 iter->me = map->buckets[0];
948 return iter;
949}
950
951
955 void *key,
956 const void **value)
957{
958 const struct GNUNET_CONTAINER_MultiMap *map = iter->map;
959
960 /* make sure the map has not been modified */
961 GNUNET_assert (iter->modification_counter == map->modification_counter);
962
963 /* look for the next entry, skipping empty buckets */
964 while (1)
965 {
966 if (iter->idx >= map->map_length)
967 return GNUNET_NO;
968 if (NULL != iter->me)
969 {
970 if (NULL != key)
971 memcpy (key,
972 entry_key (map, iter->me),
973 map->key_size);
974 if (NULL != value)
975 *value = iter->me->value;
976 iter->me = iter->me->next;
977 return GNUNET_YES;
978 }
979 iter->idx += 1;
980 if (iter->idx < map->map_length)
981 iter->me = map->buckets[iter->idx];
982 }
983}
984
985
986void
989{
990 GNUNET_free (iter);
991}
992
993
994/* 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.

◆ NEXT_CACHE_SIZE

#define NEXT_CACHE_SIZE   16

Maximum recursion depth for callbacks of GNUNET_CONTAINER_multimap_get_multiple_() themselves again calling GNUNET_CONTAINER_multimap_get_multiple_().

Should be totally excessive, but if violated we die.

Definition at line 40 of file container_multimap.c.

◆ MIN_MAP_LENGTH

#define MIN_MAP_LENGTH   2

Smallest number of buckets of a map.

Must be a power of two, and at least two so that the shift for Fibonacci hashing stays below 64.

Definition at line 46 of file container_multimap.c.

◆ MAX_MAP_LENGTH

#define MAX_MAP_LENGTH   (1U << 31)

Largest number of buckets of a map (a power of two).

Definition at line 51 of file container_multimap.c.

◆ FIBONACCI_MULTIPLIER

#define FIBONACCI_MULTIPLIER   UINT64_C (0x9E3779B97F4A7C15)

2^64 divided by the golden ratio, rounded to an odd number; the multiplier for Fibonacci hashing, which unprotected maps use.

Definition at line 57 of file container_multimap.c.

◆ KEY_SHIFT

#define KEY_SHIFT (   n)    (64 - 8 * (n))

How far to shift a key of n bytes, loaded as an integer, to put it into the first n bytes (in memory) of a 64-bit word.

Definition at line 64 of file container_multimap.c.

◆ KEY_WORDS

#define KEY_WORDS (   n)    (((n) + sizeof (uint64_t) - 1) / sizeof (uint64_t))

Number of 64-bit words needed to hold a key of n bytes.

Definition at line 72 of file container_multimap.c.

Enumeration Type Documentation

◆ KeyStorage

enum KeyStorage

How the keys of a map are stored.

Fixed when the map is created.

Enumerator
KS_INLINE_VALUE 

The key has at most 8 bytes.

It is copied into the first key_size bytes of k.bytes and the rest is zero, so that keys compare as one k.u64.

KS_INLINE_COPY 

The key is longer than 8 bytes and was copied: the entry was allocated with key_size extra bytes for key_copy, and k.ptr points there.

KS_BORROWED 

The key is longer than 8 bytes and was not copied: k.ptr points to memory that the application keeps valid while the entry is in the map.

Definition at line 78 of file container_multimap.c.

79{
86
93
100};

Function Documentation

◆ GNUNET_static_assert()

GNUNET_static_assert ( 0  = =offsetof(struct MapEntry, key_copy) % 8)

Copied keys must be aligned at least as well as the keys that applications use (see GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY).

◆ rotl64()

static uint64_t rotl64 ( uint64_t  x,
unsigned int  b 
)
inlinestatic

Rotate a 64-bit word left.

Parameters
xthe word
bnumber of bits to rotate by, 1 to 63
Returns
x rotated left by b bits

Definition at line 262 of file container_multimap.c.

264{
265 return (x << b) | (x >> (64 - b));
266}

Referenced by sip_round().

Here is the caller graph for this function:

◆ sip_round()

static void sip_round ( uint64_t  v[4])
inlinestatic

One SipRound.

Parameters
[in,out]vthe SipHash state

Definition at line 275 of file container_multimap.c.

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}

References rotl64().

Referenced by siphash13().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ siphash13()

static uint64_t siphash13 ( const uint64_t  key[2],
const void *  data,
size_t  len 
)
inlinestatic

SipHash-1-3 (one compression and three finalization rounds), the variant hash tables such as Rust's use, as it is still a strong pseudo-random function for that purpose.

Parameters
keythe 128-bit key
datawhat to hash
lennumber of bytes in data
Returns
the 64-bit hash

Definition at line 305 of file container_multimap.c.

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}

References data, end, GNUNET_le64toh, key, m, and sip_round().

Referenced by bucket_of().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ key_to_word()

static uint64_t key_to_word ( const struct GNUNET_CONTAINER_MultiMap *  map,
const void *  key 
)
inlinestatic

Convert a key of at most 8 bytes to the form it is stored in.

Parameters
mapthe map, which must use KS_INLINE_VALUE
keythe key
Returns
the key, zero-extended to 64 bits

Definition at line 352 of file container_multimap.c.

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}

References key, KEY_SHIFT, and map.

Referenced by lookup_word().

Here is the caller graph for this function:

◆ lookup_word()

static uint64_t lookup_word ( const struct GNUNET_CONTAINER_MultiMap *  map,
const void *  key 
)
inlinestatic

Prepare a key for looking it up in a map.

Parameters
mapthe map
keythe key
Returns
what keys_equal() and bucket_of() need besides key

Definition at line 399 of file container_multimap.c.

401{
402 if (KS_INLINE_VALUE == map->storage)
403 return key_to_word (map,
404 key);
405 return 0;
406}

References key, key_to_word(), KS_INLINE_VALUE, and map.

Referenced by GNUNET_CONTAINER_multimap_contains_(), GNUNET_CONTAINER_multimap_contains_value_(), GNUNET_CONTAINER_multimap_get_(), GNUNET_CONTAINER_multimap_get_multiple_(), GNUNET_CONTAINER_multimap_put_(), GNUNET_CONTAINER_multimap_remove_(), and GNUNET_CONTAINER_multimap_remove_all_().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ bucket_of()

static unsigned int bucket_of ( const struct GNUNET_CONTAINER_MultiMap *  map,
const void *  key,
uint64_t  kw 
)
inlinestatic

Compute the bucket for a key.

Parameters
mapthe map
keythe key
kwthe result of lookup_word() for key
Returns
offset into the buckets array of map

Definition at line 418 of file container_multimap.c.

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}

References FIBONACCI_MULTIPLIER, key, KS_INLINE_VALUE, map, and siphash13().

Referenced by GNUNET_CONTAINER_multimap_contains_(), GNUNET_CONTAINER_multimap_contains_value_(), GNUNET_CONTAINER_multimap_get_(), GNUNET_CONTAINER_multimap_get_multiple_(), GNUNET_CONTAINER_multimap_put_(), GNUNET_CONTAINER_multimap_remove_(), GNUNET_CONTAINER_multimap_remove_all_(), and grow().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ keys_equal()

static bool keys_equal ( const struct GNUNET_CONTAINER_MultiMap *  map,
const struct MapEntry *  e,
const void *  key,
uint64_t  kw 
)
inlinestatic

Check if an entry has a key.

Parameters
mapthe map
ethe entry
keythe key to compare to
kwthe result of lookup_word() for key
Returns
true if the key of e is key

Definition at line 452 of file container_multimap.c.

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}

References MapEntry::k, key, KS_INLINE_VALUE, map, MapEntry::ptr, and MapEntry::u64.

Referenced by GNUNET_CONTAINER_multimap_contains_(), GNUNET_CONTAINER_multimap_contains_value_(), GNUNET_CONTAINER_multimap_get_(), GNUNET_CONTAINER_multimap_get_multiple_(), GNUNET_CONTAINER_multimap_put_(), GNUNET_CONTAINER_multimap_remove_(), and GNUNET_CONTAINER_multimap_remove_all_().

Here is the caller graph for this function:

◆ entry_key()

static const void * entry_key ( const struct GNUNET_CONTAINER_MultiMap *  map,
const struct MapEntry *  e 
)
inlinestatic

Get where the key of an entry is.

Parameters
mapthe map
ethe entry
Returns
the key of e

Definition at line 483 of file container_multimap.c.

485{
486 if (KS_INLINE_VALUE == map->storage)
487 return e->k.bytes;
488 return e->k.ptr;
489}

References MapEntry::bytes, MapEntry::k, KS_INLINE_VALUE, map, and MapEntry::ptr.

Referenced by callback_key(), GNUNET_CONTAINER_multimap_iterator_next_(), and grow().

Here is the caller graph for this function:

◆ callback_key()

static const void * callback_key ( const struct GNUNET_CONTAINER_MultiMap *  map,
const struct MapEntry *  e,
uint64_t *  buf 
)
inlinestatic

Get the key of an entry to give to a callback.

Copied and inline keys are copied to buf, so that the callback may free the entry (and then still use the key, for example to remove more entries).

Parameters
mapthe map
ethe entry
[out]bufat least KEY_WORDS (key_size) words
Returns
the key to give to the callback

Definition at line 503 of file container_multimap.c.

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}

References entry_key(), MapEntry::k, KS_BORROWED, map, and MapEntry::ptr.

Referenced by GNUNET_CONTAINER_multimap_iterate_().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ allocate_buckets()

static struct MapEntry ** allocate_buckets ( unsigned int  len)
static

Allocate a bucket array.

Parameters
lennumber of buckets
Returns
NULL if out of memory

Definition at line 523 of file container_multimap.c.

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}

References GNUNET_malloc_large, GNUNET_MAX_MALLOC_CHECKED, and GNUNET_new_array.

Referenced by GNUNET_CONTAINER_multimap_create_(), and grow().

Here is the caller graph for this function:

◆ free_entries()

static void free_entries ( struct GNUNET_CONTAINER_MultiMap *  map)
static

Free all entries of a map, leaving its buckets empty.

Parameters
mapthe map

Definition at line 592 of file container_multimap.c.

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}

References GNUNET_free, map, and MapEntry::next.

Referenced by GNUNET_CONTAINER_multimap_clear_(), and GNUNET_CONTAINER_multimap_destroy_().

Here is the caller graph for this function:

◆ update_next_cache()

static void update_next_cache ( struct GNUNET_CONTAINER_MultiMap *  map,
const struct MapEntry *  e 
)
static

We are about to free() e, make sure it is not in the list of next values for any iteration in the map's next_cache.

Parameters
mapthe map to check
ethe entry that is about to be free'd

Definition at line 721 of file container_multimap.c.

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}

References map, and MapEntry::next.

Referenced by GNUNET_CONTAINER_multimap_remove_(), and GNUNET_CONTAINER_multimap_remove_all_().

Here is the caller graph for this function:

◆ grow()

static void grow ( struct GNUNET_CONTAINER_MultiMap *  map)
static

Grow the given map to a more appropriate size.

Parameters
mapthe hash map to grow

Definition at line 809 of file container_multimap.c.

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}

References allocate_buckets(), bucket_of(), entry_key(), GNUNET_free, MapEntry::k, KS_INLINE_VALUE, map, MAX_MAP_LENGTH, MapEntry::next, and MapEntry::u64.

Referenced by GNUNET_CONTAINER_multimap_put_().

Here is the call graph for this function:
Here is the caller graph for this function: