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

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

#include "platform.h"
#include "gnunet_util_lib.h"
Include dependency graph for container_multiuuidmap.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_MultiUuidmap
 Internal representation of the hash map. More...
 
struct  GNUNET_CONTAINER_MultiUuidmapIterator
 Cursor into a multiuuidmap. More...
 

Macros

#define LOG(kind, ...)    GNUNET_log_from (kind, "util-container-multiuuidmap", __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_MultiUuidmapGNUNET_CONTAINER_multiuuidmap_create (unsigned int len, int do_not_copy_keys)
 Create a multi hash map.
 
void GNUNET_CONTAINER_multiuuidmap_destroy (struct GNUNET_CONTAINER_MultiUuidmap *map)
 Destroy a hash map.
 
static unsigned int idx_of (const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
 Compute the index of the bucket for the given key.
 
unsigned int GNUNET_CONTAINER_multiuuidmap_size (const struct GNUNET_CONTAINER_MultiUuidmap *map)
 Get the number of key-value pairs in the map.
 
void * GNUNET_CONTAINER_multiuuidmap_get (const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
 Given a key find a value in the map matching the key.
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multiuuidmap_iterate (struct GNUNET_CONTAINER_MultiUuidmap *map, GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, void *it_cls)
 Iterate over all entries in the map.
 
static void update_next_cache_bme (struct GNUNET_CONTAINER_MultiUuidmap *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_MultiUuidmap *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_multiuuidmap_remove (struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, const void *value)
 Remove the given key-value pair from the map.
 
int GNUNET_CONTAINER_multiuuidmap_remove_all (struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
 Remove all entries for the given key from the map.
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multiuuidmap_contains (const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
 Check if the map contains any value under the given key (including values that are NULL).
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multiuuidmap_contains_value (const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, const void *value)
 Check if the map contains the given value under the given key.
 
static void grow (struct GNUNET_CONTAINER_MultiUuidmap *map)
 Grow the given map to a more appropriate size.
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multiuuidmap_put (struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
 Store a key-value pair in the map.
 
int GNUNET_CONTAINER_multiuuidmap_get_multiple (struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, void *it_cls)
 Iterate over all entries in the map that match a particular key.
 
unsigned int GNUNET_CONTAINER_multiuuidmap_get_random (const struct GNUNET_CONTAINER_MultiUuidmap *map, GNUNET_CONTAINER_MultiUuidmapIteratorCallback 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_MultiUuidmapIteratorGNUNET_CONTAINER_multiuuidmap_iterator_create (const struct GNUNET_CONTAINER_MultiUuidmap *map)
 Create an iterator for a multihashmap.
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multiuuidmap_iterator_next (struct GNUNET_CONTAINER_MultiUuidmapIterator *iter, struct GNUNET_Uuid *key, const void **value)
 Retrieve the next element from the hash map at the iterator's position.
 
void GNUNET_CONTAINER_multiuuidmap_iterator_destroy (struct GNUNET_CONTAINER_MultiUuidmapIterator *iter)
 Destroy a multiuuidmap iterator.
 

Detailed Description

hash map for UUIDs where the same key may be present multiple times

Author
Christian Grothoff

Definition in file container_multiuuidmap.c.

Macro Definition Documentation

◆ LOG

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

Definition at line 30 of file container_multiuuidmap.c.

45{
49 void *value;
50
54 struct BigMapEntry *next;
55
59 struct GNUNET_Uuid key;
60};
61
62
66struct SmallMapEntry
67{
71 void *value;
72
76 struct SmallMapEntry *next;
77
81 const struct GNUNET_Uuid *key;
82};
83
84
88union MapEntry
89{
93 struct SmallMapEntry *sme;
94
98 struct BigMapEntry *bme;
99};
100
101
106{
110 union MapEntry *map;
111
115 unsigned int size;
116
120 unsigned int map_length;
121
127
132 unsigned int modification_counter;
133
140
145 unsigned int next_cache_off;
146};
147
148
154{
158 union MapEntry me;
159
163 unsigned int idx;
164
169 unsigned int modification_counter;
170
175};
176
177
194GNUNET_CONTAINER_multiuuidmap_create (unsigned int len, int do_not_copy_keys)
195{
197
198 GNUNET_assert (len > 0);
200 map->map = GNUNET_malloc_large (len * sizeof(union MapEntry));
201 if (NULL == map->map)
202 {
204 return NULL;
205 }
206 map->map_length = len;
207 map->use_small_entries = do_not_copy_keys;
208 return map;
209}
210
211
212void
215{
217 for (unsigned int i = 0; i < map->map_length; i++)
218 {
219 union MapEntry me;
220
221 me = map->map[i];
223 {
224 struct SmallMapEntry *sme;
225 struct SmallMapEntry *nxt;
226
227 nxt = me.sme;
228 while (NULL != (sme = nxt))
229 {
230 nxt = sme->next;
231 GNUNET_free (sme);
232 }
233 me.sme = NULL;
234 }
235 else
236 {
237 struct BigMapEntry *bme;
238 struct BigMapEntry *nxt;
239
240 nxt = me.bme;
241 while (NULL != (bme = nxt))
242 {
243 nxt = bme->next;
244 GNUNET_free (bme);
245 }
246 me.bme = NULL;
247 }
248 }
251}
252
253
261static unsigned int
263 const struct GNUNET_Uuid *key)
264{
265 unsigned int kx;
266
267 GNUNET_assert (NULL != map);
268 GNUNET_memcpy (&kx, key, sizeof(kx));
269 return kx % map->map_length;
270}
271
272
273unsigned int
276{
277 return map->size;
278}
279
280
281void *
284 const struct GNUNET_Uuid *key)
285{
286 union MapEntry me;
287
288 me = map->map[idx_of (map, key)];
290 {
291 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
292 if (0 == GNUNET_memcmp (key, sme->key))
293 return sme->value;
294 }
295 else
296 {
297 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
298 if (0 == GNUNET_memcmp (key, &bme->key))
299 return bme->value;
300 }
301 return NULL;
302}
303
304
309 void *it_cls)
310{
311 int count;
312 union MapEntry me;
313 union MapEntry *ce;
314 struct GNUNET_Uuid kc;
315
316 count = 0;
317 GNUNET_assert (NULL != map);
320 for (unsigned int i = 0; i < map->map_length; i++)
321 {
322 me = map->map[i];
324 {
325 struct SmallMapEntry *sme;
326
327 ce->sme = me.sme;
328 while (NULL != (sme = ce->sme))
329 {
330 ce->sme = sme->next;
331 if ((NULL != it) && (GNUNET_OK != it (it_cls, sme->key, sme->value)))
332 {
334 return GNUNET_SYSERR;
335 }
336 count++;
337 }
338 }
339 else
340 {
341 struct BigMapEntry *bme;
342
343 ce->bme = me.bme;
344 while (NULL != (bme = ce->bme))
345 {
346 ce->bme = bme->next;
347 if (NULL != it)
348 {
349 kc = bme->key;
350 if (GNUNET_OK != it (it_cls, &kc, bme->value))
351 {
353 return GNUNET_SYSERR;
354 }
355 }
356 count++;
357 }
358 }
359 }
361 return count;
362}
363
364
372static void
374 const struct BigMapEntry *bme)
375{
376 for (unsigned int i = 0; i < map->next_cache_off; i++)
377 if (map->next_cache[i].bme == bme)
378 map->next_cache[i].bme = bme->next;
379}
380
381
389static void
391 const struct SmallMapEntry *sme)
392{
393 for (unsigned int i = 0; i < map->next_cache_off; i++)
394 if (map->next_cache[i].sme == sme)
395 map->next_cache[i].sme = sme->next;
396}
397
398
401 const struct GNUNET_Uuid *key,
402 const void *value)
403{
404 union MapEntry me;
405 unsigned int i;
406
408 i = idx_of (map, key);
409 me = map->map[i];
411 {
412 struct SmallMapEntry *p = NULL;
413
414 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
415 {
416 if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value))
417 {
418 if (NULL == p)
419 map->map[i].sme = sme->next;
420 else
421 p->next = sme->next;
423 GNUNET_free (sme);
424 map->size--;
425 return GNUNET_YES;
426 }
427 p = sme;
428 }
429 }
430 else
431 {
432 struct BigMapEntry *p = NULL;
433
434 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
435 {
436 if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value))
437 {
438 if (NULL == p)
439 map->map[i].bme = bme->next;
440 else
441 p->next = bme->next;
443 GNUNET_free (bme);
444 map->size--;
445 return GNUNET_YES;
446 }
447 p = bme;
448 }
449 }
450 return GNUNET_NO;
451}
452
453
454int
457 const struct GNUNET_Uuid *key)
458{
459 union MapEntry me;
460 unsigned int i;
461 int ret;
462
464
465 ret = 0;
466 i = idx_of (map, key);
467 me = map->map[i];
469 {
470 struct SmallMapEntry *sme;
471 struct SmallMapEntry *p;
472
473 p = NULL;
474 sme = me.sme;
475 while (NULL != sme)
476 {
477 if (0 == GNUNET_memcmp (key, sme->key))
478 {
479 if (NULL == p)
480 map->map[i].sme = sme->next;
481 else
482 p->next = sme->next;
484 GNUNET_free (sme);
485 map->size--;
486 if (NULL == p)
487 sme = map->map[i].sme;
488 else
489 sme = p->next;
490 ret++;
491 }
492 else
493 {
494 p = sme;
495 sme = sme->next;
496 }
497 }
498 }
499 else
500 {
501 struct BigMapEntry *bme;
502 struct BigMapEntry *p;
503
504 p = NULL;
505 bme = me.bme;
506 while (NULL != bme)
507 {
508 if (0 == GNUNET_memcmp (key, &bme->key))
509 {
510 if (NULL == p)
511 map->map[i].bme = bme->next;
512 else
513 p->next = bme->next;
515 GNUNET_free (bme);
516 map->size--;
517 if (NULL == p)
518 bme = map->map[i].bme;
519 else
520 bme = p->next;
521 ret++;
522 }
523 else
524 {
525 p = bme;
526 bme = bme->next;
527 }
528 }
529 }
530 return ret;
531}
532
533
537 const struct GNUNET_Uuid *key)
538{
539 union MapEntry me;
540
541 me = map->map[idx_of (map, key)];
543 {
544 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
545 if (0 == GNUNET_memcmp (key, sme->key))
546 return GNUNET_YES;
547 }
548 else
549 {
550 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
551 if (0 == GNUNET_memcmp (key, &bme->key))
552 return GNUNET_YES;
553 }
554 return GNUNET_NO;
555}
556
557
561 const struct GNUNET_Uuid *key,
562 const void *value)
563{
564 union MapEntry me;
565
566 me = map->map[idx_of (map, key)];
568 {
569 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
570 if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value))
571 return GNUNET_YES;
572 }
573 else
574 {
575 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
576 if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value))
577 return GNUNET_YES;
578 }
579 return GNUNET_NO;
580}
581
582
588static void
590{
591 union MapEntry *old_map;
592 union MapEntry *new_map;
593 unsigned int old_len;
594 unsigned int new_len;
595 unsigned int idx;
596
597 old_map = map->map;
598 old_len = map->map_length;
599 new_len = old_len * 2;
600 if (0 == new_len) /* 2^31 * 2 == 0 */
601 new_len = old_len; /* never use 0 */
602 if (new_len == old_len)
603 return; /* nothing changed */
604 new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
605 if (NULL == new_map)
606 return; /* grow not possible */
608 map->map_length = new_len;
609 map->map = new_map;
610 for (unsigned int i = 0; i < old_len; i++)
611 {
613 {
614 struct SmallMapEntry *sme;
615
616 while (NULL != (sme = old_map[i].sme))
617 {
618 old_map[i].sme = sme->next;
619 idx = idx_of (map, sme->key);
620 sme->next = new_map[idx].sme;
621 new_map[idx].sme = sme;
622 }
623 }
624 else
625 {
626 struct BigMapEntry *bme;
627
628 while (NULL != (bme = old_map[i].bme))
629 {
630 old_map[i].bme = bme->next;
631 idx = idx_of (map, &bme->key);
632 bme->next = new_map[idx].bme;
633 new_map[idx].bme = bme;
634 }
635 }
636 }
637 GNUNET_free (old_map);
638}
639
640
643 const struct GNUNET_Uuid *key,
644 void *value,
646{
647 union MapEntry me;
648 unsigned int i;
649
650 i = idx_of (map, key);
653 {
654 me = map->map[i];
656 {
657 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
658 if (0 == GNUNET_memcmp (key, sme->key))
659 {
661 return GNUNET_SYSERR;
662 sme->value = value;
663 return GNUNET_NO;
664 }
665 }
666 else
667 {
668 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
669 if (0 == GNUNET_memcmp (key, &bme->key))
670 {
672 return GNUNET_SYSERR;
673 bme->value = value;
674 return GNUNET_NO;
675 }
676 }
677 }
678 if (map->size / 3 >= map->map_length / 4)
679 {
680 grow (map);
681 i = idx_of (map, key);
682 }
684 {
685 struct SmallMapEntry *sme;
686
687 sme = GNUNET_new (struct SmallMapEntry);
688 sme->key = key;
689 sme->value = value;
690 sme->next = map->map[i].sme;
691 map->map[i].sme = sme;
692 }
693 else
694 {
695 struct BigMapEntry *bme;
696
697 bme = GNUNET_new (struct BigMapEntry);
698 bme->key = *key;
699 bme->value = value;
700 bme->next = map->map[i].bme;
701 map->map[i].bme = bme;
702 }
703 map->size++;
704 return GNUNET_OK;
705}
706
707
718int
721 const struct GNUNET_Uuid *key,
723 void *it_cls)
724{
725 int count;
726 union MapEntry me;
727 union MapEntry *ce;
728
731 count = 0;
732 me = map->map[idx_of (map, key)];
734 {
735 struct SmallMapEntry *sme;
736
737 ce->sme = me.sme;
738 while (NULL != (sme = ce->sme))
739 {
740 ce->sme = sme->next;
741 if (0 != GNUNET_memcmp (key, sme->key))
742 continue;
743 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value)))
744 {
746 return GNUNET_SYSERR;
747 }
748 count++;
749 }
750 }
751 else
752 {
753 struct BigMapEntry *bme;
754
755 ce->bme = me.bme;
756 while (NULL != (bme = ce->bme))
757 {
758 ce->bme = bme->next;
759 if (0 != GNUNET_memcmp (key, &bme->key))
760 continue;
761 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value)))
762 {
764 return GNUNET_SYSERR;
765 }
766 count++;
767 }
768 }
770 return count;
771}
772
773
785unsigned int
789 void *it_cls)
790{
791 unsigned int off;
792 union MapEntry me;
793
794 if (0 == map->size)
795 return 0;
796 if (NULL == it)
797 return 1;
799 for (unsigned int idx = 0; idx < map->map_length; idx++)
800 {
801 me = map->map[idx];
803 {
804 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
805 {
806 if (0 == off)
807 {
808 if (GNUNET_OK != it (it_cls, sme->key, sme->value))
809 return GNUNET_SYSERR;
810 return 1;
811 }
812 off--;
813 }
814 }
815 else
816 {
817 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
818 {
819 if (0 == off)
820 {
821 if (GNUNET_OK != it (it_cls, &bme->key, bme->value))
822 return GNUNET_SYSERR;
823 return 1;
824 }
825 off--;
826 }
827 }
828 }
829 GNUNET_break (0);
830 return GNUNET_SYSERR;
831}
832
833
837{
839
841 iter->map = map;
843 iter->me = map->map[0];
844 return iter;
845}
846
847
851 struct GNUNET_Uuid *key,
852 const void **value)
853{
854 /* make sure the map has not been modified */
856
857 /* look for the next entry, skipping empty buckets */
858 while (1)
859 {
860 if (iter->idx >= iter->map->map_length)
861 return GNUNET_NO;
862 if (GNUNET_YES == iter->map->use_small_entries)
863 {
864 if (NULL != iter->me.sme)
865 {
866 if (NULL != key)
867 *key = *iter->me.sme->key;
868 if (NULL != value)
869 *value = iter->me.sme->value;
870 iter->me.sme = iter->me.sme->next;
871 return GNUNET_YES;
872 }
873 }
874 else
875 {
876 if (NULL != iter->me.bme)
877 {
878 if (NULL != key)
879 *key = iter->me.bme->key;
880 if (NULL != value)
881 *value = iter->me.bme->value;
882 iter->me.bme = iter->me.bme->next;
883 return GNUNET_YES;
884 }
885 }
886 iter->idx += 1;
887 if (iter->idx < iter->map->map_length)
888 iter->me = iter->map->map[iter->idx];
889 }
890}
891
892
893void
896{
897 GNUNET_free (iter);
898}
899
900
901/* end of container_multiuuidmap.c */
#define NEXT_CACHE_SIZE
Maximum recursion depth for callbacks of GNUNET_CONTAINER_multihashmap_get_multiple() themselves s ag...
static unsigned int idx_of(const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
Compute the index of the bucket for the given key.
static void update_next_cache_sme(struct GNUNET_CONTAINER_MultiUuidmap *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 void update_next_cache_bme(struct GNUNET_CONTAINER_MultiUuidmap *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 void grow(struct GNUNET_CONTAINER_MultiUuidmap *map)
Grow the given map to a more appropriate size.
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.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multiuuidmap_contains_value(const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, const void *value)
Check if the map contains the given value under the given key.
unsigned int GNUNET_CONTAINER_multiuuidmap_size(const struct GNUNET_CONTAINER_MultiUuidmap *map)
Get the number of key-value pairs in the map.
struct GNUNET_CONTAINER_MultiUuidmap * GNUNET_CONTAINER_multiuuidmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
unsigned int GNUNET_CONTAINER_multiuuidmap_get_random(const struct GNUNET_CONTAINER_MultiUuidmap *map, GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, void *it_cls)
Call it on a random value from the map, or not at all if the map is empty.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multiuuidmap_iterator_next(struct GNUNET_CONTAINER_MultiUuidmapIterator *iter, struct GNUNET_Uuid *key, const void **value)
Retrieve the next element from the hash map at the iterator's position.
int GNUNET_CONTAINER_multiuuidmap_remove_all(struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
Remove all entries for the given key from the map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multiuuidmap_remove(struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, const void *value)
Remove the given key-value pair from the map.
void GNUNET_CONTAINER_multiuuidmap_destroy(struct GNUNET_CONTAINER_MultiUuidmap *map)
Destroy a hash map.
GNUNET_CONTAINER_MultiHashMapOption
Options for storing values in the HashMap.
int GNUNET_CONTAINER_multiuuidmap_get_multiple(struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, void *it_cls)
Iterate over all entries in the map that match a particular key.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multiuuidmap_contains(const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
Check if the map contains any value under the given key (including values that are NULL).
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_MultiUuidmapIteratorCallback)(void *cls, const struct GNUNET_Uuid *key, void *value)
Iterator over uuid map entries.
struct GNUNET_CONTAINER_MultiUuidmapIterator * GNUNET_CONTAINER_multiuuidmap_iterator_create(const struct GNUNET_CONTAINER_MultiUuidmap *map)
Create an iterator for a multihashmap.
void GNUNET_CONTAINER_multiuuidmap_iterator_destroy(struct GNUNET_CONTAINER_MultiUuidmapIterator *iter)
Destroy a multiuuidmap iterator.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multiuuidmap_iterate(struct GNUNET_CONTAINER_MultiUuidmap *map, GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multiuuidmap_put(struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
void * GNUNET_CONTAINER_multiuuidmap_get(const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
Given a key find a value in the map matching the key.
@ 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 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...
const struct GNUNET_CONTAINER_MultiUuidmap * map
Map that we are iterating over.
union MapEntry me
Position in the bucket 'idx'.
unsigned int modification_counter
Modification counter as observed on the map when the iterator was created.
unsigned int idx
Current bucket index.
Internal representation of the hash map.
union MapEntry * map
All of our buckets.
union MapEntry next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multihashmap_get_mult...
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...
unsigned int next_cache_off
Offset of next_cache entries in use, must be smaller than NEXT_CACHE_SIZE.
unsigned int size
Number of entries in the map.
int use_small_entries
GNUNET_NO if the map entries are of type 'struct BigMapEntry', GNUNET_YES if the map entries are of t...
A UUID, a 128 bit "random" value.
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_multiuuidmap.c.

Function Documentation

◆ idx_of()

static unsigned int idx_of ( const struct GNUNET_CONTAINER_MultiUuidmap map,
const struct GNUNET_Uuid 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 263 of file container_multiuuidmap.c.

265{
266 unsigned int kx;
267
268 GNUNET_assert (NULL != map);
269 GNUNET_memcpy (&kx, key, sizeof(kx));
270 return kx % map->map_length;
271}

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

Referenced by GNUNET_CONTAINER_multiuuidmap_contains(), GNUNET_CONTAINER_multiuuidmap_contains_value(), GNUNET_CONTAINER_multiuuidmap_get(), GNUNET_CONTAINER_multiuuidmap_get_multiple(), GNUNET_CONTAINER_multiuuidmap_put(), GNUNET_CONTAINER_multiuuidmap_remove(), GNUNET_CONTAINER_multiuuidmap_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_MultiUuidmap 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 374 of file container_multiuuidmap.c.

376{
377 for (unsigned int i = 0; i < map->next_cache_off; i++)
378 if (map->next_cache[i].bme == bme)
379 map->next_cache[i].bme = bme->next;
380}

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

Referenced by GNUNET_CONTAINER_multiuuidmap_remove(), and GNUNET_CONTAINER_multiuuidmap_remove_all().

Here is the caller graph for this function:

◆ update_next_cache_sme()

static void update_next_cache_sme ( struct GNUNET_CONTAINER_MultiUuidmap 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 391 of file container_multiuuidmap.c.

393{
394 for (unsigned int i = 0; i < map->next_cache_off; i++)
395 if (map->next_cache[i].sme == sme)
396 map->next_cache[i].sme = sme->next;
397}

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

Referenced by GNUNET_CONTAINER_multiuuidmap_remove(), and GNUNET_CONTAINER_multiuuidmap_remove_all().

Here is the caller graph for this function:

◆ grow()

static void grow ( struct GNUNET_CONTAINER_MultiUuidmap map)
static

Grow the given map to a more appropriate size.

Parameters
mapthe hash map to grow

Definition at line 590 of file container_multiuuidmap.c.

591{
592 union MapEntry *old_map;
593 union MapEntry *new_map;
594 unsigned int old_len;
595 unsigned int new_len;
596 unsigned int idx;
597
598 old_map = map->map;
599 old_len = map->map_length;
600 new_len = old_len * 2;
601 if (0 == new_len) /* 2^31 * 2 == 0 */
602 new_len = old_len; /* never use 0 */
603 if (new_len == old_len)
604 return; /* nothing changed */
605 new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
606 if (NULL == new_map)
607 return; /* grow not possible */
609 map->map_length = new_len;
610 map->map = new_map;
611 for (unsigned int i = 0; i < old_len; i++)
612 {
614 {
615 struct SmallMapEntry *sme;
616
617 while (NULL != (sme = old_map[i].sme))
618 {
619 old_map[i].sme = sme->next;
620 idx = idx_of (map, sme->key);
621 sme->next = new_map[idx].sme;
622 new_map[idx].sme = sme;
623 }
624 }
625 else
626 {
627 struct BigMapEntry *bme;
628
629 while (NULL != (bme = old_map[i].bme))
630 {
631 old_map[i].bme = bme->next;
632 idx = idx_of (map, &bme->key);
633 bme->next = new_map[idx].bme;
634 new_map[idx].bme = bme;
635 }
636 }
637 }
638 GNUNET_free (old_map);
639}

References MapEntry::bme, 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_multiuuidmap_put().

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