aboutsummaryrefslogtreecommitdiff
path: root/src/lib/util/container_multihashmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/util/container_multihashmap.c')
-rw-r--r--src/lib/util/container_multihashmap.c974
1 files changed, 974 insertions, 0 deletions
diff --git a/src/lib/util/container_multihashmap.c b/src/lib/util/container_multihashmap.c
new file mode 100644
index 000000000..d403cd220
--- /dev/null
+++ b/src/lib/util/container_multihashmap.c
@@ -0,0 +1,974 @@
1/*
2 This file is part of GNUnet.
3 Copyright (C) 2008, 2012 GNUnet e.V.
4
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
9
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details.
14
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17
18 SPDX-License-Identifier: AGPL3.0-or-later
19 */
20/**
21 * @file util/container_multihashmap.c
22 * @brief hash map where the same key may be present multiple times
23 * @author Christian Grothoff
24 */
25
26
27#include "platform.h"
28#include "gnunet_util_lib.h"
29
30#define LOG(kind, ...) \
31 GNUNET_log_from (kind, "util-container-multihashmap", __VA_ARGS__)
32
33/**
34 * Maximum recursion depth for callbacks of
35 * #GNUNET_CONTAINER_multihashmap_get_multiple() themselves s
36 * again calling #GNUNET_CONTAINER_multihashmap_get_multiple().
37 * Should be totally excessive, but if violated we die.
38 */
39#define NEXT_CACHE_SIZE 16
40
41
42/**
43 * An entry in the hash map with the full key.
44 */
45struct BigMapEntry
46{
47 /**
48 * Value of the entry.
49 */
50 void *value;
51
52 /**
53 * If there is a hash collision, we create a linked list.
54 */
55 struct BigMapEntry *next;
56
57 /**
58 * Key for the entry.
59 */
60 struct GNUNET_HashCode key;
61};
62
63
64/**
65 * An entry in the hash map with just a pointer to the key.
66 */
67struct SmallMapEntry
68{
69 /**
70 * Value of the entry.
71 */
72 void *value;
73
74 /**
75 * If there is a hash collision, we create a linked list.
76 */
77 struct SmallMapEntry *next;
78
79 /**
80 * Key for the entry.
81 */
82 const struct GNUNET_HashCode *key;
83};
84
85
86/**
87 * Entry in the map.
88 */
89union MapEntry
90{
91 /**
92 * Variant used if map entries only contain a pointer to the key.
93 */
94 struct SmallMapEntry *sme;
95
96 /**
97 * Variant used if map entries contain the full key.
98 */
99 struct BigMapEntry *bme;
100};
101
102
103/**
104 * Internal representation of the hash map.
105 */
106struct GNUNET_CONTAINER_MultiHashMap
107{
108 /**
109 * All of our buckets.
110 */
111 union MapEntry *map;
112
113 /**
114 * Number of entries in the map.
115 */
116 unsigned int size;
117
118 /**
119 * Length of the "map" array.
120 */
121 unsigned int map_length;
122
123 /**
124 * #GNUNET_NO if the map entries are of type 'struct BigMapEntry',
125 * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'.
126 */
127 int use_small_entries;
128
129 /**
130 * Counts the destructive modifications (grow, remove)
131 * to the map, so that iterators can check if they are still valid.
132 */
133 unsigned int modification_counter;
134
135 /**
136 * Map entries indicating iteration positions currently
137 * in use by #GNUNET_CONTAINER_multihashmap_get_multiple().
138 * Only used up to @e next_cache_off.
139 */
140 union MapEntry next_cache[NEXT_CACHE_SIZE];
141
142 /**
143 * Offset of @e next_cache entries in use, must be smaller
144 * than #NEXT_CACHE_SIZE.
145 */
146 unsigned int next_cache_off;
147};
148
149
150/**
151 * Cursor into a multihashmap.
152 * Allows to enumerate elements asynchronously.
153 */
154struct GNUNET_CONTAINER_MultiHashMapIterator
155{
156 /**
157 * Position in the bucket @e idx
158 */
159 union MapEntry me;
160
161 /**
162 * Current bucket index.
163 */
164 unsigned int idx;
165
166 /**
167 * Modification counter as observed on the map when the iterator
168 * was created.
169 */
170 unsigned int modification_counter;
171
172 /**
173 * Map that we are iterating over.
174 */
175 const struct GNUNET_CONTAINER_MultiHashMap *map;
176};
177
178
179struct GNUNET_CONTAINER_MultiHashMap *
180GNUNET_CONTAINER_multihashmap_create (unsigned int len, int do_not_copy_keys)
181{
182 struct GNUNET_CONTAINER_MultiHashMap *hm;
183
184 GNUNET_assert (len > 0);
185 hm = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap);
186 if (len * sizeof(union MapEntry) > GNUNET_MAX_MALLOC_CHECKED)
187 {
188 size_t s;
189 /* application *explicitly* requested very large map, hopefully
190 it checks the return value... */
191 s = len * sizeof(union MapEntry);
192 if ((s / sizeof(union MapEntry)) != len)
193 return NULL; /* integer overflow on multiplication */
194 if (NULL == (hm->map = GNUNET_malloc_large (s)))
195 {
196 /* out of memory */
197 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
198 "Out of memory allocating large hash map (%u entries)\n",
199 len);
200 GNUNET_free (hm);
201 return NULL;
202 }
203 }
204 else
205 {
206 hm->map = GNUNET_new_array (len, union MapEntry);
207 }
208 hm->map_length = len;
209 hm->use_small_entries = do_not_copy_keys;
210 return hm;
211}
212
213
214void
215GNUNET_CONTAINER_multihashmap_destroy (
216 struct GNUNET_CONTAINER_MultiHashMap *map)
217{
218 GNUNET_assert (0 == map->next_cache_off);
219 for (unsigned int i = 0; i < map->map_length; i++)
220 {
221 union MapEntry me;
222
223 me = map->map[i];
224 if (map->use_small_entries)
225 {
226 struct SmallMapEntry *sme;
227 struct SmallMapEntry *nxt;
228
229 nxt = me.sme;
230 while (NULL != (sme = nxt))
231 {
232 nxt = sme->next;
233 GNUNET_free (sme);
234 }
235 me.sme = NULL;
236 }
237 else
238 {
239 struct BigMapEntry *bme;
240 struct BigMapEntry *nxt;
241
242 nxt = me.bme;
243 while (NULL != (bme = nxt))
244 {
245 nxt = bme->next;
246 GNUNET_free (bme);
247 }
248 me.bme = NULL;
249 }
250 }
251 GNUNET_free (map->map);
252 GNUNET_free (map);
253}
254
255
256/**
257 * Compute the index of the bucket for the given key.
258 *
259 * @param map hash map for which to compute the index
260 * @param key what key should the index be computed for
261 * @return offset into the "map" array of "map"
262 */
263static unsigned int
264idx_of (const struct GNUNET_CONTAINER_MultiHashMap *map,
265 const struct GNUNET_HashCode *key)
266{
267 GNUNET_assert (map != NULL);
268 return (*(unsigned int *) key) % map->map_length;
269}
270
271
272unsigned int
273GNUNET_CONTAINER_multihashmap_size (
274 const struct GNUNET_CONTAINER_MultiHashMap *map)
275{
276 return map->size;
277}
278
279
280void *
281GNUNET_CONTAINER_multihashmap_get (
282 const struct GNUNET_CONTAINER_MultiHashMap *map,
283 const struct GNUNET_HashCode *key)
284{
285 union MapEntry me;
286
287 me = map->map[idx_of (map, key)];
288 if (map->use_small_entries)
289 {
290 struct SmallMapEntry *sme;
291
292 for (sme = me.sme; NULL != sme; sme = sme->next)
293 if (0 == GNUNET_memcmp (key, sme->key))
294 return sme->value;
295 }
296 else
297 {
298 struct BigMapEntry *bme;
299
300 for (bme = me.bme; NULL != bme; bme = bme->next)
301 if (0 == GNUNET_memcmp (key, &bme->key))
302 return bme->value;
303 }
304 return NULL;
305}
306
307
308int
309GNUNET_CONTAINER_multihashmap_iterate (
310 struct GNUNET_CONTAINER_MultiHashMap *map,
311 GNUNET_CONTAINER_MultiHashMapIteratorCallback it,
312 void *it_cls)
313{
314 int count;
315 union MapEntry me;
316 union MapEntry *ce;
317 struct GNUNET_HashCode kc;
318
319 GNUNET_assert (NULL != map);
320 ce = &map->next_cache[map->next_cache_off];
321 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
322 count = 0;
323 for (unsigned i = 0; i < map->map_length; i++)
324 {
325 me = map->map[i];
326 if (map->use_small_entries)
327 {
328 struct SmallMapEntry *sme;
329
330 ce->sme = me.sme;
331 while (NULL != (sme = ce->sme))
332 {
333 ce->sme = sme->next;
334 if (NULL != it)
335 {
336 if (GNUNET_OK != it (it_cls, sme->key, sme->value))
337 {
338 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
339 return GNUNET_SYSERR;
340 }
341 }
342 count++;
343 }
344 }
345 else
346 {
347 struct BigMapEntry *bme;
348
349 ce->bme = me.bme;
350 while (NULL != (bme = ce->bme))
351 {
352 ce->bme = bme->next;
353 if (NULL != it)
354 {
355 kc = bme->key;
356 if (GNUNET_OK != it (it_cls, &kc, bme->value))
357 {
358 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
359 return GNUNET_SYSERR;
360 }
361 }
362 count++;
363 }
364 }
365 }
366 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
367 return count;
368}
369
370
371/**
372 * We are about to free() the @a bme, make sure it is not in
373 * the list of next values for any iterator in the @a map's next_cache.
374 *
375 * @param map the map to check
376 * @param bme the entry that is about to be free'd
377 */
378static void
379update_next_cache_bme (struct GNUNET_CONTAINER_MultiHashMap *map,
380 const struct BigMapEntry *bme)
381{
382 for (unsigned int i = 0; i < map->next_cache_off; i++)
383 if (map->next_cache[i].bme == bme)
384 map->next_cache[i].bme = bme->next;
385}
386
387
388/**
389 * We are about to free() the @a sme, make sure it is not in
390 * the list of next values for any iterator in the @a map's next_cache.
391 *
392 * @param map the map to check
393 * @param sme the entry that is about to be free'd
394 */
395static void
396update_next_cache_sme (struct GNUNET_CONTAINER_MultiHashMap *map,
397 const struct SmallMapEntry *sme)
398{
399 for (unsigned int i = 0; i < map->next_cache_off; i++)
400 if (map->next_cache[i].sme == sme)
401 map->next_cache[i].sme = sme->next;
402}
403
404
405enum GNUNET_GenericReturnValue
406GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
407 const struct GNUNET_HashCode *key,
408 const void *value)
409{
410 union MapEntry me;
411 unsigned int i;
412
413 map->modification_counter++;
414
415 i = idx_of (map, key);
416 me = map->map[i];
417 if (map->use_small_entries)
418 {
419 struct SmallMapEntry *p;
420
421 p = NULL;
422 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
423 {
424 if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value))
425 {
426 if (NULL == p)
427 map->map[i].sme = sme->next;
428 else
429 p->next = sme->next;
430 update_next_cache_sme (map, sme);
431 GNUNET_free (sme);
432 map->size--;
433 return GNUNET_YES;
434 }
435 p = sme;
436 }
437 }
438 else
439 {
440 struct BigMapEntry *p;
441
442 p = NULL;
443 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
444 {
445 if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value))
446 {
447 if (NULL == p)
448 map->map[i].bme = bme->next;
449 else
450 p->next = bme->next;
451 update_next_cache_bme (map, bme);
452 GNUNET_free (bme);
453 map->size--;
454 return GNUNET_YES;
455 }
456 p = bme;
457 }
458 }
459 return GNUNET_NO;
460}
461
462
463int
464GNUNET_CONTAINER_multihashmap_remove_all (
465 struct GNUNET_CONTAINER_MultiHashMap *map,
466 const struct GNUNET_HashCode *key)
467{
468 union MapEntry me;
469 unsigned int i;
470 int ret;
471
472 map->modification_counter++;
473
474 ret = 0;
475 i = idx_of (map, key);
476 me = map->map[i];
477 if (map->use_small_entries)
478 {
479 struct SmallMapEntry *sme;
480 struct SmallMapEntry *p;
481
482 p = NULL;
483 sme = me.sme;
484 while (NULL != sme)
485 {
486 if (0 == GNUNET_memcmp (key, sme->key))
487 {
488 if (NULL == p)
489 map->map[i].sme = sme->next;
490 else
491 p->next = sme->next;
492 update_next_cache_sme (map, sme);
493 GNUNET_free (sme);
494 map->size--;
495 if (NULL == p)
496 sme = map->map[i].sme;
497 else
498 sme = p->next;
499 ret++;
500 }
501 else
502 {
503 p = sme;
504 sme = sme->next;
505 }
506 }
507 }
508 else
509 {
510 struct BigMapEntry *bme;
511 struct BigMapEntry *p;
512
513 p = NULL;
514 bme = me.bme;
515 while (NULL != bme)
516 {
517 if (0 == GNUNET_memcmp (key, &bme->key))
518 {
519 if (NULL == p)
520 map->map[i].bme = bme->next;
521 else
522 p->next = bme->next;
523 update_next_cache_bme (map, bme);
524 GNUNET_free (bme);
525 map->size--;
526 if (NULL == p)
527 bme = map->map[i].bme;
528 else
529 bme = p->next;
530 ret++;
531 }
532 else
533 {
534 p = bme;
535 bme = bme->next;
536 }
537 }
538 }
539 return ret;
540}
541
542
543/**
544 * Callback used to remove all entries from the map.
545 *
546 * @param cls the `struct GNUNET_CONTAINER_MultiHashMap`
547 * @param key the key
548 * @param value the value
549 * @return #GNUNET_OK (continue to iterate)
550 */
551static int
552remove_all (void *cls, const struct GNUNET_HashCode *key, void *value)
553{
554 struct GNUNET_CONTAINER_MultiHashMap *map = cls;
555
556 GNUNET_assert (GNUNET_YES ==
557 GNUNET_CONTAINER_multihashmap_remove (map, key, value));
558 return GNUNET_OK;
559}
560
561
562/**
563 * @ingroup hashmap
564 * Remove all entries from the map.
565 * Note that the values would not be "freed".
566 *
567 * @param map the map
568 * @return number of values removed
569 */
570unsigned int
571GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map)
572{
573 unsigned int ret;
574
575 ret = map->size;
576 GNUNET_CONTAINER_multihashmap_iterate (map, &remove_all, map);
577 return ret;
578}
579
580
581enum GNUNET_GenericReturnValue
582GNUNET_CONTAINER_multihashmap_contains (
583 const struct GNUNET_CONTAINER_MultiHashMap *map,
584 const struct GNUNET_HashCode *key)
585{
586 union MapEntry me;
587
588 me = map->map[idx_of (map, key)];
589 if (map->use_small_entries)
590 {
591 struct SmallMapEntry *sme;
592
593 for (sme = me.sme; NULL != sme; sme = sme->next)
594 if (0 == GNUNET_memcmp (key, sme->key))
595 return GNUNET_YES;
596 }
597 else
598 {
599 struct BigMapEntry *bme;
600
601 for (bme = me.bme; NULL != bme; bme = bme->next)
602 if (0 == GNUNET_memcmp (key, &bme->key))
603 return GNUNET_YES;
604 }
605 return GNUNET_NO;
606}
607
608
609enum GNUNET_GenericReturnValue
610GNUNET_CONTAINER_multihashmap_contains_value (
611 const struct GNUNET_CONTAINER_MultiHashMap *map,
612 const struct GNUNET_HashCode *key,
613 const void *value)
614{
615 union MapEntry me;
616
617 me = map->map[idx_of (map, key)];
618 if (map->use_small_entries)
619 {
620 struct SmallMapEntry *sme;
621
622 for (sme = me.sme; NULL != sme; sme = sme->next)
623 if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value))
624 return GNUNET_YES;
625 }
626 else
627 {
628 struct BigMapEntry *bme;
629
630 for (bme = me.bme; NULL != bme; bme = bme->next)
631 if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value))
632 return GNUNET_YES;
633 }
634 return GNUNET_NO;
635}
636
637
638/**
639 * Grow the given map to a more appropriate size.
640 *
641 * @param map the hash map to grow
642 */
643static void
644grow (struct GNUNET_CONTAINER_MultiHashMap *map)
645{
646 union MapEntry *old_map;
647 union MapEntry *new_map;
648 unsigned int old_len;
649 unsigned int new_len;
650 unsigned int idx;
651
652 old_map = map->map;
653 old_len = map->map_length;
654 GNUNET_assert (0 != old_len);
655 new_len = old_len * 2;
656 if (0 == new_len) /* 2^31 * 2 == 0 */
657 new_len = old_len; /* never use 0 */
658 if (new_len == old_len)
659 return; /* nothing changed */
660 new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
661 if (NULL == new_map)
662 return; /* grow not possible */
663 map->modification_counter++;
664 map->map_length = new_len;
665 map->map = new_map;
666 for (unsigned int i = 0; i < old_len; i++)
667 {
668 if (map->use_small_entries)
669 {
670 struct SmallMapEntry *sme;
671
672 while (NULL != (sme = old_map[i].sme))
673 {
674 old_map[i].sme = sme->next;
675 idx = idx_of (map, sme->key);
676 sme->next = new_map[idx].sme;
677 new_map[idx].sme = sme;
678 }
679 }
680 else
681 {
682 struct BigMapEntry *bme;
683
684 while (NULL != (bme = old_map[i].bme))
685 {
686 old_map[i].bme = bme->next;
687 idx = idx_of (map, &bme->key);
688 bme->next = new_map[idx].bme;
689 new_map[idx].bme = bme;
690 }
691 }
692 }
693 GNUNET_free (old_map);
694}
695
696
697/**
698 * Store a key-value pair in the map.
699 *
700 * @param map the map
701 * @param key key to use
702 * @param value value to use
703 * @param opt options for put
704 * @return #GNUNET_OK on success,
705 * #GNUNET_NO if a value was replaced (with REPLACE)
706 * #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
707 * value already exists
708 */
709enum GNUNET_GenericReturnValue
710GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
711 const struct GNUNET_HashCode *key,
712 void *value,
713 enum GNUNET_CONTAINER_MultiHashMapOption opt)
714{
715 union MapEntry me;
716 unsigned int i;
717
718 i = idx_of (map, key);
719 if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
720 (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
721 {
722 me = map->map[i];
723 if (map->use_small_entries)
724 {
725 struct SmallMapEntry *sme;
726
727 for (sme = me.sme; NULL != sme; sme = sme->next)
728 if (0 == GNUNET_memcmp (key, sme->key))
729 {
730 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
731 return GNUNET_SYSERR;
732 sme->value = value;
733 return GNUNET_NO;
734 }
735 }
736 else
737 {
738 struct BigMapEntry *bme;
739
740 for (bme = me.bme; NULL != bme; bme = bme->next)
741 if (0 == GNUNET_memcmp (key, &bme->key))
742 {
743 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
744 return GNUNET_SYSERR;
745 bme->value = value;
746 return GNUNET_NO;
747 }
748 }
749 }
750 if (map->size / 3 >= map->map_length / 4)
751 {
752 grow (map);
753 i = idx_of (map, key);
754 }
755 if (map->use_small_entries)
756 {
757 struct SmallMapEntry *sme;
758
759 sme = GNUNET_new (struct SmallMapEntry);
760 sme->key = key;
761 sme->value = value;
762 sme->next = map->map[i].sme;
763 map->map[i].sme = sme;
764 }
765 else
766 {
767 struct BigMapEntry *bme;
768
769 bme = GNUNET_new (struct BigMapEntry);
770 bme->key = *key;
771 bme->value = value;
772 bme->next = map->map[i].bme;
773 map->map[i].bme = bme;
774 }
775 map->size++;
776 return GNUNET_OK;
777}
778
779
780enum GNUNET_GenericReturnValue
781GNUNET_CONTAINER_multihashmap_get_multiple (
782 struct GNUNET_CONTAINER_MultiHashMap *map,
783 const struct GNUNET_HashCode *key,
784 GNUNET_CONTAINER_MultiHashMapIteratorCallback it,
785 void *it_cls)
786{
787 int count;
788 union MapEntry *me;
789 union MapEntry *ce;
790
791 ce = &map->next_cache[map->next_cache_off];
792 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
793 count = 0;
794 me = &map->map[idx_of (map, key)];
795 if (map->use_small_entries)
796 {
797 struct SmallMapEntry *sme;
798
799 ce->sme = me->sme;
800 while (NULL != (sme = ce->sme))
801 {
802 ce->sme = sme->next;
803 if (0 != GNUNET_memcmp (key, sme->key))
804 continue;
805 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value)))
806 {
807 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
808 return GNUNET_SYSERR;
809 }
810 count++;
811 }
812 }
813 else
814 {
815 struct BigMapEntry *bme;
816
817 ce->bme = me->bme;
818 while (NULL != (bme = ce->bme))
819 {
820 ce->bme = bme->next;
821 if (0 != GNUNET_memcmp (key, &bme->key))
822 continue;
823 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value)))
824 {
825 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
826 return GNUNET_SYSERR;
827 }
828 count++;
829 }
830 }
831 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
832 return count;
833}
834
835
836/**
837 * @ingroup hashmap
838 * Call @a it on a random value from the map, or not at all
839 * if the map is empty. Note that this function has linear
840 * complexity (in the size of the map).
841 *
842 * @param map the map
843 * @param it function to call on a random entry
844 * @param it_cls extra argument to @a it
845 * @return the number of key value pairs processed, zero or one.
846 */
847unsigned int
848GNUNET_CONTAINER_multihashmap_get_random (
849 const struct GNUNET_CONTAINER_MultiHashMap *map,
850 GNUNET_CONTAINER_MultiHashMapIteratorCallback it,
851 void *it_cls)
852{
853 unsigned int off;
854 unsigned int idx;
855 union MapEntry me;
856
857 if (0 == map->size)
858 return 0;
859 if (NULL == it)
860 return 1;
861 off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, map->size);
862 for (idx = 0; idx < map->map_length; idx++)
863 {
864 me = map->map[idx];
865 if (map->use_small_entries)
866 {
867 struct SmallMapEntry *sme;
868 struct SmallMapEntry *nxt;
869
870 nxt = me.sme;
871 while (NULL != (sme = nxt))
872 {
873 nxt = sme->next;
874 if (0 == off)
875 {
876 if (GNUNET_OK != it (it_cls, sme->key, sme->value))
877 return GNUNET_SYSERR;
878 return 1;
879 }
880 off--;
881 }
882 }
883 else
884 {
885 struct BigMapEntry *bme;
886 struct BigMapEntry *nxt;
887
888 nxt = me.bme;
889 while (NULL != (bme = nxt))
890 {
891 nxt = bme->next;
892 if (0 == off)
893 {
894 if (GNUNET_OK != it (it_cls, &bme->key, bme->value))
895 return GNUNET_SYSERR;
896 return 1;
897 }
898 off--;
899 }
900 }
901 }
902 GNUNET_break (0);
903 return GNUNET_SYSERR;
904}
905
906
907struct GNUNET_CONTAINER_MultiHashMapIterator *
908GNUNET_CONTAINER_multihashmap_iterator_create (
909 const struct GNUNET_CONTAINER_MultiHashMap *map)
910{
911 struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
912
913 iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMapIterator);
914 iter->map = map;
915 iter->modification_counter = map->modification_counter;
916 iter->me = map->map[0];
917 return iter;
918}
919
920
921enum GNUNET_GenericReturnValue
922GNUNET_CONTAINER_multihashmap_iterator_next (
923 struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
924 struct GNUNET_HashCode *key,
925 const void **value)
926{
927 /* make sure the map has not been modified */
928 GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
929
930 /* look for the next entry, skipping empty buckets */
931 while (1)
932 {
933 if (iter->idx >= iter->map->map_length)
934 return GNUNET_NO;
935 if (GNUNET_YES == iter->map->use_small_entries)
936 {
937 if (NULL != iter->me.sme)
938 {
939 if (NULL != key)
940 *key = *iter->me.sme->key;
941 if (NULL != value)
942 *value = iter->me.sme->value;
943 iter->me.sme = iter->me.sme->next;
944 return GNUNET_YES;
945 }
946 }
947 else
948 {
949 if (NULL != iter->me.bme)
950 {
951 if (NULL != key)
952 *key = iter->me.bme->key;
953 if (NULL != value)
954 *value = iter->me.bme->value;
955 iter->me.bme = iter->me.bme->next;
956 return GNUNET_YES;
957 }
958 }
959 iter->idx += 1;
960 if (iter->idx < iter->map->map_length)
961 iter->me = iter->map->map[iter->idx];
962 }
963}
964
965
966void
967GNUNET_CONTAINER_multihashmap_iterator_destroy (
968 struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
969{
970 GNUNET_free (iter);
971}
972
973
974/* end of container_multihashmap.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-10 00:29:19 +0000