GNUnet debian-0.24.3-29-g453fda2cf
 
Loading...
Searching...
No Matches
container_multipeermap.c File Reference

hash map where the same key may be present multiple times More...

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

Go to the source code of this file.

Data Structures

struct  BigMapEntry
 An entry in the hash map with the full key. More...
 
struct  SmallMapEntry
 An entry in the hash map with just a pointer to the key. More...
 
union  MapEntry
 Entry in the map. More...
 
struct  GNUNET_CONTAINER_MultiPeerMap
 Internal representation of the hash map. More...
 
struct  GNUNET_CONTAINER_MultiPeerMapIterator
 Cursor into a multipeermap. More...
 

Macros

#define LOG(kind, ...)    GNUNET_log_from (kind, "util-container-multipeermap", __VA_ARGS__)
 
#define NEXT_CACHE_SIZE   16
 Maximum recursion depth for callbacks of GNUNET_CONTAINER_multihashmap_get_multiple() themselves s again calling GNUNET_CONTAINER_multihashmap_get_multiple().
 

Functions

struct GNUNET_CONTAINER_MultiPeerMapGNUNET_CONTAINER_multipeermap_create (unsigned int len, int do_not_copy_keys)
 Create a multi peer map (hash map for public keys of peers).
 
void GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map)
 Destroy a hash map.
 
static unsigned int idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
 Compute the index of the bucket for the given key.
 
unsigned int GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map)
 Get the number of key-value pairs in the map.
 
void * GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
 Given a key find a value in the map matching the key.
 
int GNUNET_CONTAINER_multipeermap_iterate (struct GNUNET_CONTAINER_MultiPeerMap *map, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
 Iterate over all entries in the map.
 
static void update_next_cache_bme (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct BigMapEntry *bme)
 We are about to free() the bme, make sure it is not in the list of next values for any iterator in the map's next_cache.
 
static void update_next_cache_sme (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct SmallMapEntry *sme)
 We are about to free() the sme, make sure it is not in the list of next values for any iterator in the map's next_cache.
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, const void *value)
 Remove the given key-value pair from the map.
 
int GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
 Remove all entries for the given key from the map.
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
 Check if the map contains any value under the given key (including values that are NULL).
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, const void *value)
 Check if the map contains the given value under the given key.
 
static void grow (struct GNUNET_CONTAINER_MultiPeerMap *map)
 Grow the given map to a more appropriate size.
 
int GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
 Store a key-value pair in the map.
 
int GNUNET_CONTAINER_multipeermap_get_multiple (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
 Iterate over all entries in the map that match a particular key.
 
unsigned int GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
 Call it on a random value from the map, or not at all if the map is empty.
 
struct GNUNET_CONTAINER_MultiPeerMapIteratorGNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map)
 Create an iterator for a multihashmap.
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter, struct GNUNET_PeerIdentity *key, const void **value)
 Retrieve the next element from the hash map at the iterator's position.
 
void GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter)
 Destroy a multipeermap iterator.
 

Detailed Description

hash map where the same key may be present multiple times

Author
Christian Grothoff

Definition in file container_multipeermap.c.

Macro Definition Documentation

◆ LOG

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

Definition at line 30 of file container_multipeermap.c.

44{
48 void *value;
49
53 struct BigMapEntry *next;
54
59};
60
61
65struct SmallMapEntry
66{
70 void *value;
71
75 struct SmallMapEntry *next;
76
80 const struct GNUNET_PeerIdentity *key;
81};
82
83
87union MapEntry
88{
92 struct SmallMapEntry *sme;
93
97 struct BigMapEntry *bme;
98};
99
100
105{
109 union MapEntry *map;
110
114 unsigned int size;
115
119 unsigned int map_length;
120
126
131 unsigned int modification_counter;
132
139
144 unsigned int next_cache_off;
145};
146
147
153{
157 union MapEntry me;
158
162 unsigned int idx;
163
168 unsigned int modification_counter;
169
174};
175
176
179 int do_not_copy_keys)
180{
182
183 GNUNET_assert (len > 0);
185 map->map = GNUNET_malloc_large (len * sizeof(union MapEntry));
186 if (NULL == map->map)
187 {
189 return NULL;
190 }
191 map->map_length = len;
192 map->use_small_entries = do_not_copy_keys;
193 return map;
194}
195
196
197void
200{
202 for (unsigned int i = 0; i < map->map_length; i++)
203 {
204 union MapEntry me;
205
206 me = map->map[i];
208 {
209 struct SmallMapEntry *sme;
210 struct SmallMapEntry *nxt;
211
212 nxt = me.sme;
213 while (NULL != (sme = nxt))
214 {
215 nxt = sme->next;
216 GNUNET_free (sme);
217 }
218 me.sme = NULL;
219 }
220 else
221 {
222 struct BigMapEntry *bme;
223 struct BigMapEntry *nxt;
224
225 nxt = me.bme;
226 while (NULL != (bme = nxt))
227 {
228 nxt = bme->next;
229 GNUNET_free (bme);
230 }
231 me.bme = NULL;
232 }
233 }
236}
237
238
246static unsigned int
248 const struct GNUNET_PeerIdentity *key)
249{
250 unsigned int kx;
251
252 GNUNET_assert (NULL != map);
253 GNUNET_memcpy (&kx, key, sizeof(kx));
254 return kx % map->map_length;
255}
256
257
258unsigned int
261{
262 return map->size;
263}
264
265
266void *
269 const struct GNUNET_PeerIdentity *key)
270{
271 union MapEntry me;
272
273 me = map->map[idx_of (map, key)];
275 {
276 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
277 if (0 == GNUNET_memcmp (key, sme->key))
278 return sme->value;
279 }
280 else
281 {
282 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
283 if (0 == GNUNET_memcmp (key, &bme->key))
284 return bme->value;
285 }
286 return NULL;
287}
288
289
290int
294 void *it_cls)
295{
296 int count;
297 union MapEntry me;
298 union MapEntry *ce;
299 struct GNUNET_PeerIdentity kc;
300
301 count = 0;
302 GNUNET_assert (NULL != map);
305 for (unsigned int i = 0; i < map->map_length; i++)
306 {
307 me = map->map[i];
309 {
310 struct SmallMapEntry *sme;
311
312 ce->sme = me.sme;
313 while (NULL != (sme = ce->sme))
314 {
315 ce->sme = sme->next;
316 if (NULL != it)
317 {
318 if (GNUNET_OK != it (it_cls, sme->key, sme->value))
319 {
321 return GNUNET_SYSERR;
322 }
323 }
324 count++;
325 }
326 }
327 else
328 {
329 struct BigMapEntry *bme;
330
331 ce->bme = me.bme;
332 while (NULL != (bme = ce->bme))
333 {
334 ce->bme = bme->next;
335 if (NULL != it)
336 {
337 kc = bme->key;
338 if (GNUNET_OK != it (it_cls, &kc, bme->value))
339 {
341 return GNUNET_SYSERR;
342 }
343 }
344 count++;
345 }
346 }
347 }
349 return count;
350}
351
352
360static void
362 const struct BigMapEntry *bme)
363{
364 for (unsigned int i = 0; i < map->next_cache_off; i++)
365 if (map->next_cache[i].bme == bme)
366 map->next_cache[i].bme = bme->next;
367}
368
369
377static void
379 const struct SmallMapEntry *sme)
380{
381 for (unsigned int i = 0; i < map->next_cache_off; i++)
382 if (map->next_cache[i].sme == sme)
383 map->next_cache[i].sme = sme->next;
384}
385
386
389 const struct GNUNET_PeerIdentity *key,
390 const void *value)
391{
392 union MapEntry me;
393 unsigned int i;
394
396 i = idx_of (map, key);
397 me = map->map[i];
399 {
400 struct SmallMapEntry *p = NULL;
401
402 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
403 {
404 if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value))
405 {
406 if (NULL == p)
407 map->map[i].sme = sme->next;
408 else
409 p->next = sme->next;
411 GNUNET_free (sme);
412 map->size--;
413 return GNUNET_YES;
414 }
415 p = sme;
416 }
417 }
418 else
419 {
420 struct BigMapEntry *p = NULL;
421
422 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
423 {
424 if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value))
425 {
426 if (NULL == p)
427 map->map[i].bme = bme->next;
428 else
429 p->next = bme->next;
431 GNUNET_free (bme);
432 map->size--;
433 return GNUNET_YES;
434 }
435 p = bme;
436 }
437 }
438 return GNUNET_NO;
439}
440
441
442int
445 const struct GNUNET_PeerIdentity *key)
446{
447 union MapEntry me;
448 unsigned int i;
449 int ret;
450
452
453 ret = 0;
454 i = idx_of (map, key);
455 me = map->map[i];
457 {
458 struct SmallMapEntry *sme;
459 struct SmallMapEntry *p;
460
461 p = NULL;
462 sme = me.sme;
463 while (NULL != sme)
464 {
465 if (0 == GNUNET_memcmp (key, sme->key))
466 {
467 if (NULL == p)
468 map->map[i].sme = sme->next;
469 else
470 p->next = sme->next;
472 GNUNET_free (sme);
473 map->size--;
474 if (NULL == p)
475 sme = map->map[i].sme;
476 else
477 sme = p->next;
478 ret++;
479 }
480 else
481 {
482 p = sme;
483 sme = sme->next;
484 }
485 }
486 }
487 else
488 {
489 struct BigMapEntry *bme;
490 struct BigMapEntry *p;
491
492 p = NULL;
493 bme = me.bme;
494 while (NULL != bme)
495 {
496 if (0 == GNUNET_memcmp (key, &bme->key))
497 {
498 if (NULL == p)
499 map->map[i].bme = bme->next;
500 else
501 p->next = bme->next;
503 GNUNET_free (bme);
504 map->size--;
505 if (NULL == p)
506 bme = map->map[i].bme;
507 else
508 bme = p->next;
509 ret++;
510 }
511 else
512 {
513 p = bme;
514 bme = bme->next;
515 }
516 }
517 }
518 return ret;
519}
520
521
525 const struct GNUNET_PeerIdentity *key)
526{
527 union MapEntry me;
528
529 me = map->map[idx_of (map, key)];
531 {
532 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
533 if (0 == GNUNET_memcmp (key, sme->key))
534 return GNUNET_YES;
535 }
536 else
537 {
538 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
539 if (0 == GNUNET_memcmp (key, &bme->key))
540 return GNUNET_YES;
541 }
542 return GNUNET_NO;
543}
544
545
549 const struct GNUNET_PeerIdentity *key,
550 const void *value)
551{
552 union MapEntry me;
553
554 me = map->map[idx_of (map, key)];
556 {
557 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
558 if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value))
559 return GNUNET_YES;
560 }
561 else
562 {
563 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
564 if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value))
565 return GNUNET_YES;
566 }
567 return GNUNET_NO;
568}
569
570
576static void
578{
579 union MapEntry *old_map;
580 union MapEntry *new_map;
581 unsigned int old_len;
582 unsigned int new_len;
583 unsigned int idx;
584
585 old_map = map->map;
586 old_len = map->map_length;
587 GNUNET_assert (0 != old_len);
588 new_len = old_len * 2;
589 if (0 == new_len) /* 2^31 * 2 == 0 */
590 new_len = old_len; /* never use 0 */
591 if (new_len == old_len)
592 return; /* nothing changed */
593 new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
594 if (NULL == new_map)
595 return; /* grow not possible */
597 map->map_length = new_len;
598 map->map = new_map;
599 for (unsigned int i = 0; i < old_len; i++)
600 {
602 {
603 struct SmallMapEntry *sme;
604
605 while (NULL != (sme = old_map[i].sme))
606 {
607 old_map[i].sme = sme->next;
608 idx = idx_of (map, sme->key);
609 sme->next = new_map[idx].sme;
610 new_map[idx].sme = sme;
611 }
612 }
613 else
614 {
615 struct BigMapEntry *bme;
616
617 while (NULL != (bme = old_map[i].bme))
618 {
619 old_map[i].bme = bme->next;
620 idx = idx_of (map, &bme->key);
621 bme->next = new_map[idx].bme;
622 new_map[idx].bme = bme;
623 }
624 }
625 }
626 GNUNET_free (old_map);
627}
628
629
630int
632 const struct GNUNET_PeerIdentity *key,
633 void *value,
635{
636 union MapEntry me;
637 unsigned int i;
638
639 i = idx_of (map, key);
642 {
643 me = map->map[i];
645 {
646 struct SmallMapEntry *sme;
647
648 for (sme = me.sme; NULL != sme; sme = sme->next)
649 if (0 == GNUNET_memcmp (key, sme->key))
650 {
652 return GNUNET_SYSERR;
653 sme->value = value;
654 return GNUNET_NO;
655 }
656 }
657 else
658 {
659 struct BigMapEntry *bme;
660
661 for (bme = me.bme; NULL != bme; bme = bme->next)
662 if (0 == GNUNET_memcmp (key, &bme->key))
663 {
665 return GNUNET_SYSERR;
666 bme->value = value;
667 return GNUNET_NO;
668 }
669 }
670 }
671 if (map->size / 3 >= map->map_length / 4)
672 {
673 grow (map);
674 i = idx_of (map, key);
675 }
677 {
678 struct SmallMapEntry *sme;
679
680 sme = GNUNET_new (struct SmallMapEntry);
681 sme->key = key;
682 sme->value = value;
683 sme->next = map->map[i].sme;
684 map->map[i].sme = sme;
685 }
686 else
687 {
688 struct BigMapEntry *bme;
689
690 bme = GNUNET_new (struct BigMapEntry);
691 bme->key = *key;
692 bme->value = value;
693 bme->next = map->map[i].bme;
694 map->map[i].bme = bme;
695 }
696 map->size++;
697 return GNUNET_OK;
698}
699
700
701int
704 const struct GNUNET_PeerIdentity *key,
706 void *it_cls)
707{
708 int count;
709 union MapEntry me;
710 union MapEntry *ce;
711
714 count = 0;
715 me = map->map[idx_of (map, key)];
717 {
718 struct SmallMapEntry *sme;
719
720 ce->sme = me.sme;
721 while (NULL != (sme = ce->sme))
722 {
723 ce->sme = sme->next;
724 if (0 != GNUNET_memcmp (key, sme->key))
725 continue;
726 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value)))
727 {
729 return GNUNET_SYSERR;
730 }
731 count++;
732 }
733 }
734 else
735 {
736 struct BigMapEntry *bme;
737
738 ce->bme = me.bme;
739 while (NULL != (bme = ce->bme))
740 {
741 ce->bme = bme->next;
742 if (0 != GNUNET_memcmp (key, &bme->key))
743 continue;
744 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value)))
745 {
747 return GNUNET_SYSERR;
748 }
749 count++;
750 }
751 }
753 return count;
754}
755
756
768unsigned int
772 void *it_cls)
773{
774 unsigned int off;
775 union MapEntry me;
776
777 if (0 == map->size)
778 return 0;
779 if (NULL == it)
780 return 1;
782 for (unsigned int idx = 0; idx < map->map_length; idx++)
783 {
784 me = map->map[idx];
786 {
787 struct SmallMapEntry *sme;
788 struct SmallMapEntry *nxt;
789
790 nxt = me.sme;
791 while (NULL != (sme = nxt))
792 {
793 nxt = sme->next;
794 if (0 == off)
795 {
796 if (GNUNET_OK != it (it_cls, sme->key, sme->value))
797 return GNUNET_SYSERR;
798 return 1;
799 }
800 off--;
801 }
802 }
803 else
804 {
805 struct BigMapEntry *bme;
806 struct BigMapEntry *nxt;
807
808 nxt = me.bme;
809 while (NULL != (bme = nxt))
810 {
811 nxt = bme->next;
812 if (0 == off)
813 {
814 if (GNUNET_OK != it (it_cls, &bme->key, bme->value))
815 return GNUNET_SYSERR;
816 return 1;
817 }
818 off--;
819 }
820 }
821 }
822 GNUNET_break (0);
823 return GNUNET_SYSERR;
824}
825
826
830{
832
834 iter->map = map;
836 iter->me = map->map[0];
837 return iter;
838}
839
840
844 struct GNUNET_PeerIdentity *key,
845 const void **value)
846{
847 /* make sure the map has not been modified */
849
850 /* look for the next entry, skipping empty buckets */
851 while (1)
852 {
853 if (iter->idx >= iter->map->map_length)
854 return GNUNET_NO;
855 if (GNUNET_YES == iter->map->use_small_entries)
856 {
857 if (NULL != iter->me.sme)
858 {
859 if (NULL != key)
860 *key = *iter->me.sme->key;
861 if (NULL != value)
862 *value = iter->me.sme->value;
863 iter->me.sme = iter->me.sme->next;
864 return GNUNET_YES;
865 }
866 }
867 else
868 {
869 if (NULL != iter->me.bme)
870 {
871 if (NULL != key)
872 *key = iter->me.bme->key;
873 if (NULL != value)
874 *value = iter->me.bme->value;
875 iter->me.bme = iter->me.bme->next;
876 return GNUNET_YES;
877 }
878 }
879 iter->idx += 1;
880 if (iter->idx < iter->map->map_length)
881 iter->me = iter->map->map[iter->idx];
882 }
883}
884
885
886void
889{
890 GNUNET_free (iter);
891}
892
893
894/* end of container_multipeermap.c */
#define NEXT_CACHE_SIZE
Maximum recursion depth for callbacks of GNUNET_CONTAINER_multihashmap_get_multiple() themselves s ag...
static void grow(struct GNUNET_CONTAINER_MultiPeerMap *map)
Grow the given map to a more appropriate size.
static void update_next_cache_sme(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct SmallMapEntry *sme)
We are about to free() the sme, make sure it is not in the list of next values for any iterator in th...
static unsigned int idx_of(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Compute the index of the bucket for the given key.
static void update_next_cache_bme(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct BigMapEntry *bme)
We are about to free() the bme, make sure it is not in the list of next values for any iterator in th...
static int ret
Final status code.
Definition gnunet-arm.c:93
static GNUNET_NETWORK_STRUCT_END struct GNUNET_PeerIdentity me
Our own peer identity.
struct GNUNET_HashCode key
The key used in the DHT.
static char * value
Value of the record to add/remove.
static struct GNUNET_OS_Process * p
Helper process we started.
Definition gnunet-uri.c:38
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
@ GNUNET_CRYPTO_QUALITY_NONCE
Randomness for IVs etc.
void * GNUNET_CONTAINER_multipeermap_get(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Given a key find a value in the map matching the key.
struct GNUNET_CONTAINER_MultiPeerMapIterator * GNUNET_CONTAINER_multipeermap_iterator_create(const struct GNUNET_CONTAINER_MultiPeerMap *map)
Create an iterator for a multihashmap.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_contains(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Check if the map contains any value under the given key (including values that are NULL).
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_PeerMapIterator)(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Iterator over hash map entries.
void GNUNET_CONTAINER_multipeermap_destroy(struct GNUNET_CONTAINER_MultiPeerMap *map)
Destroy a hash map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_contains_value(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, const void *value)
Check if the map contains the given value under the given key.
int GNUNET_CONTAINER_multipeermap_iterate(struct GNUNET_CONTAINER_MultiPeerMap *map, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
Iterate over all entries in the map.
unsigned int GNUNET_CONTAINER_multipeermap_get_random(const struct GNUNET_CONTAINER_MultiPeerMap *map, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
Call it on a random value from the map, or not at all if the map is empty.
void GNUNET_CONTAINER_multipeermap_iterator_destroy(struct GNUNET_CONTAINER_MultiPeerMapIterator *iter)
Destroy a multipeermap iterator.
int GNUNET_CONTAINER_multipeermap_remove_all(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Remove all entries for the given key from the map.
GNUNET_CONTAINER_MultiHashMapOption
Options for storing values in the HashMap.
struct GNUNET_CONTAINER_MultiPeerMap * GNUNET_CONTAINER_multipeermap_create(unsigned int len, int do_not_copy_keys)
Create a multi peer map (hash map for public keys of peers).
int GNUNET_CONTAINER_multipeermap_get_multiple(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
Iterate over all entries in the map that match a particular key.
unsigned int GNUNET_CONTAINER_multipeermap_size(const struct GNUNET_CONTAINER_MultiPeerMap *map)
Get the number of key-value pairs in the map.
int GNUNET_CONTAINER_multipeermap_put(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_iterator_next(struct GNUNET_CONTAINER_MultiPeerMapIterator *iter, struct GNUNET_PeerIdentity *key, const void **value)
Retrieve the next element from the hash map at the iterator's position.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_remove(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, const void *value)
Remove the given key-value pair from the map.
@ 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...
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
GNUNET_GenericReturnValue
Named constants for return values.
@ GNUNET_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
#define GNUNET_new(type)
Allocate a struct or union 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
An entry in the hash map with the full key.
struct BigMapEntry * next
If there is a hash collision, we create a linked list.
void * value
Value of the entry.
struct GNUNET_HashCode key
Key for the entry.
unsigned int idx
Current bucket index.
union MapEntry me
Position in the bucket 'idx'.
unsigned int modification_counter
Modification counter as observed on the map when the iterator was created.
const struct GNUNET_CONTAINER_MultiPeerMap * map
Map that we are iterating over.
Internal representation of the hash map.
unsigned int next_cache_off
Offset of next_cache entries in use, must be smaller than NEXT_CACHE_SIZE.
unsigned int map_length
Length of the "map" array.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
union MapEntry * map
All of our buckets.
int use_small_entries
GNUNET_NO if the map entries are of type 'struct BigMapEntry', GNUNET_YES if the map entries are of t...
unsigned int size
Number of entries in the map.
union MapEntry next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multihashmap_get_mult...
The identity of the host (wraps the signing key of the peer).
An entry in the hash map with just a pointer to the key.
struct SmallMapEntry * next
If there is a hash collision, we create a linked list.
void * value
Value of the entry.
const struct GNUNET_HashCode * key
Key for the entry.
Entry in the map.
struct SmallMapEntry * sme
Variant used if map entries only contain a pointer to the key.
struct BigMapEntry * bme
Variant used if map entries contain the full key.

◆ NEXT_CACHE_SIZE

#define NEXT_CACHE_SIZE   16

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

Should be totally excessive, but if violated we die.

Definition at line 39 of file container_multipeermap.c.

Function Documentation

◆ idx_of()

static unsigned int idx_of ( const struct GNUNET_CONTAINER_MultiPeerMap map,
const struct GNUNET_PeerIdentity key 
)
static

Compute the index of the bucket for the given key.

Parameters
maphash map for which to compute the index
keywhat key should the index be computed for
Returns
offset into the "map" array of "map"

Definition at line 248 of file container_multipeermap.c.

250{
251 unsigned int kx;
252
253 GNUNET_assert (NULL != map);
254 GNUNET_memcpy (&kx, key, sizeof(kx));
255 return kx % map->map_length;
256}

References GNUNET_assert, GNUNET_memcpy, key, map, and GNUNET_CONTAINER_MultiPeerMap::map_length.

Referenced by GNUNET_CONTAINER_multipeermap_contains(), GNUNET_CONTAINER_multipeermap_contains_value(), GNUNET_CONTAINER_multipeermap_get(), GNUNET_CONTAINER_multipeermap_get_multiple(), GNUNET_CONTAINER_multipeermap_put(), GNUNET_CONTAINER_multipeermap_remove(), GNUNET_CONTAINER_multipeermap_remove_all(), and grow().

Here is the caller graph for this function:

◆ update_next_cache_bme()

static void update_next_cache_bme ( struct GNUNET_CONTAINER_MultiPeerMap map,
const struct BigMapEntry bme 
)
static

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

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

Definition at line 362 of file container_multipeermap.c.

364{
365 for (unsigned int i = 0; i < map->next_cache_off; i++)
366 if (map->next_cache[i].bme == bme)
367 map->next_cache[i].bme = bme->next;
368}

References MapEntry::bme, map, BigMapEntry::next, GNUNET_CONTAINER_MultiPeerMap::next_cache, and GNUNET_CONTAINER_MultiPeerMap::next_cache_off.

Referenced by GNUNET_CONTAINER_multipeermap_remove(), and GNUNET_CONTAINER_multipeermap_remove_all().

Here is the caller graph for this function:

◆ update_next_cache_sme()

static void update_next_cache_sme ( struct GNUNET_CONTAINER_MultiPeerMap map,
const struct SmallMapEntry sme 
)
static

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

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

Definition at line 379 of file container_multipeermap.c.

381{
382 for (unsigned int i = 0; i < map->next_cache_off; i++)
383 if (map->next_cache[i].sme == sme)
384 map->next_cache[i].sme = sme->next;
385}

References map, SmallMapEntry::next, GNUNET_CONTAINER_MultiPeerMap::next_cache, GNUNET_CONTAINER_MultiPeerMap::next_cache_off, and MapEntry::sme.

Referenced by GNUNET_CONTAINER_multipeermap_remove(), and GNUNET_CONTAINER_multipeermap_remove_all().

Here is the caller graph for this function:

◆ grow()

static void grow ( struct GNUNET_CONTAINER_MultiPeerMap map)
static

Grow the given map to a more appropriate size.

Parameters
mapthe hash map to grow

Definition at line 578 of file container_multipeermap.c.

579{
580 union MapEntry *old_map;
581 union MapEntry *new_map;
582 unsigned int old_len;
583 unsigned int new_len;
584 unsigned int idx;
585
586 old_map = map->map;
587 old_len = map->map_length;
588 GNUNET_assert (0 != old_len);
589 new_len = old_len * 2;
590 if (0 == new_len) /* 2^31 * 2 == 0 */
591 new_len = old_len; /* never use 0 */
592 if (new_len == old_len)
593 return; /* nothing changed */
594 new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
595 if (NULL == new_map)
596 return; /* grow not possible */
598 map->map_length = new_len;
599 map->map = new_map;
600 for (unsigned int i = 0; i < old_len; i++)
601 {
603 {
604 struct SmallMapEntry *sme;
605
606 while (NULL != (sme = old_map[i].sme))
607 {
608 old_map[i].sme = sme->next;
609 idx = idx_of (map, sme->key);
610 sme->next = new_map[idx].sme;
611 new_map[idx].sme = sme;
612 }
613 }
614 else
615 {
616 struct BigMapEntry *bme;
617
618 while (NULL != (bme = old_map[i].bme))
619 {
620 old_map[i].bme = bme->next;
621 idx = idx_of (map, &bme->key);
622 bme->next = new_map[idx].bme;
623 new_map[idx].bme = bme;
624 }
625 }
626 }
627 GNUNET_free (old_map);
628}

References MapEntry::bme, GNUNET_assert, GNUNET_free, GNUNET_malloc_large, idx_of(), BigMapEntry::key, SmallMapEntry::key, GNUNET_CONTAINER_MultiPeerMap::map, map, GNUNET_CONTAINER_MultiPeerMap::map_length, GNUNET_CONTAINER_MultiPeerMap::modification_counter, BigMapEntry::next, SmallMapEntry::next, MapEntry::sme, and GNUNET_CONTAINER_MultiPeerMap::use_small_entries.

Referenced by GNUNET_CONTAINER_multipeermap_put().

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