aboutsummaryrefslogtreecommitdiff
path: root/src/lib/util/container_multishortmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/util/container_multishortmap.c')
-rw-r--r--src/lib/util/container_multishortmap.c904
1 files changed, 904 insertions, 0 deletions
diff --git a/src/lib/util/container_multishortmap.c b/src/lib/util/container_multishortmap.c
new file mode 100644
index 000000000..c626b55e5
--- /dev/null
+++ b/src/lib/util/container_multishortmap.c
@@ -0,0 +1,904 @@
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_multishortmap.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-multishortmap", __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_ShortHashCode 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_ShortHashCode *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_MultiShortmap
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 multishortmap.
152 * Allows to enumerate elements asynchronously.
153 */
154struct GNUNET_CONTAINER_MultiShortmapIterator
155{
156 /**
157 * Position in the bucket '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_MultiShortmap *map;
176};
177
178
179/**
180 * Create a multi hash map.
181 *
182 * @param len initial size (map will grow as needed)
183 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
184 * #GNUNET_YES means that on 'put', the 'key' does not have
185 * to be copied as the destination of the pointer is
186 * guaranteed to be life as long as the value is stored in
187 * the hashmap. This can significantly reduce memory
188 * consumption, but of course is also a recipe for
189 * heap corruption if the assumption is not true. Only
190 * use this if (1) memory use is important in this case and
191 * (2) you have triple-checked that the invariant holds
192 * @return NULL on error
193 */
194struct GNUNET_CONTAINER_MultiShortmap *
195GNUNET_CONTAINER_multishortmap_create (unsigned int len, int do_not_copy_keys)
196{
197 struct GNUNET_CONTAINER_MultiShortmap *map;
198
199 GNUNET_assert (len > 0);
200 map = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmap);
201 map->map = GNUNET_malloc_large (len * sizeof(union MapEntry));
202 if (NULL == map->map)
203 {
204 GNUNET_free (map);
205 return NULL;
206 }
207 map->map_length = len;
208 map->use_small_entries = do_not_copy_keys;
209 return map;
210}
211
212
213void
214GNUNET_CONTAINER_multishortmap_destroy (
215 struct GNUNET_CONTAINER_MultiShortmap *map)
216{
217 GNUNET_assert (0 == map->next_cache_off);
218 for (unsigned int i = 0; i < map->map_length; i++)
219 {
220 union MapEntry me;
221
222 me = map->map[i];
223 if (map->use_small_entries)
224 {
225 struct SmallMapEntry *sme;
226 struct SmallMapEntry *nxt;
227
228 nxt = me.sme;
229 while (NULL != (sme = nxt))
230 {
231 nxt = sme->next;
232 GNUNET_free (sme);
233 }
234 me.sme = NULL;
235 }
236 else
237 {
238 struct BigMapEntry *bme;
239 struct BigMapEntry *nxt;
240
241 nxt = me.bme;
242 while (NULL != (bme = nxt))
243 {
244 nxt = bme->next;
245 GNUNET_free (bme);
246 }
247 me.bme = NULL;
248 }
249 }
250 GNUNET_free (map->map);
251 GNUNET_free (map);
252}
253
254
255/**
256 * Compute the index of the bucket for the given key.
257 *
258 * @param map hash map for which to compute the index
259 * @param key what key should the index be computed for
260 * @return offset into the "map" array of "map"
261 */
262static unsigned int
263idx_of (const struct GNUNET_CONTAINER_MultiShortmap *map,
264 const struct GNUNET_ShortHashCode *key)
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}
272
273
274unsigned int
275GNUNET_CONTAINER_multishortmap_size (
276 const struct GNUNET_CONTAINER_MultiShortmap *map)
277{
278 return map->size;
279}
280
281
282void *
283GNUNET_CONTAINER_multishortmap_get (
284 const struct GNUNET_CONTAINER_MultiShortmap *map,
285 const struct GNUNET_ShortHashCode *key)
286{
287 union MapEntry me;
288
289 me = map->map[idx_of (map, key)];
290 if (map->use_small_entries)
291 {
292 for (struct SmallMapEntry *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 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
299 if (0 == GNUNET_memcmp (key, &bme->key))
300 return bme->value;
301 }
302 return NULL;
303}
304
305
306int
307GNUNET_CONTAINER_multishortmap_iterate (
308 struct GNUNET_CONTAINER_MultiShortmap *map,
309 GNUNET_CONTAINER_ShortmapIterator it,
310 void *it_cls)
311{
312 int count;
313 union MapEntry me;
314 union MapEntry *ce;
315 struct GNUNET_ShortHashCode kc;
316
317 count = 0;
318 GNUNET_assert (NULL != map);
319 ce = &map->next_cache[map->next_cache_off];
320 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
321 for (unsigned int i = 0; i < map->map_length; i++)
322 {
323 me = map->map[i];
324 if (map->use_small_entries)
325 {
326 struct SmallMapEntry *sme;
327
328 ce->sme = me.sme;
329 while (NULL != (sme = ce->sme))
330 {
331 ce->sme = sme->next;
332 if ((NULL != it) && (GNUNET_OK != it (it_cls, sme->key, sme->value)))
333 {
334 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
335 return GNUNET_SYSERR;
336 }
337 count++;
338 }
339 }
340 else
341 {
342 struct BigMapEntry *bme;
343
344 ce->bme = me.bme;
345 while (NULL != (bme = ce->bme))
346 {
347 ce->bme = bme->next;
348 if (NULL != it)
349 {
350 kc = bme->key;
351 if (GNUNET_OK != it (it_cls, &kc, bme->value))
352 {
353 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
354 return GNUNET_SYSERR;
355 }
356 }
357 count++;
358 }
359 }
360 }
361 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
362 return count;
363}
364
365
366/**
367 * We are about to free() the @a bme, make sure it is not in
368 * the list of next values for any iterator in the @a map's next_cache.
369 *
370 * @param map the map to check
371 * @param bme the entry that is about to be free'd
372 */
373static void
374update_next_cache_bme (struct GNUNET_CONTAINER_MultiShortmap *map,
375 const struct BigMapEntry *bme)
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}
381
382
383/**
384 * We are about to free() the @a sme, make sure it is not in
385 * the list of next values for any iterator in the @a map's next_cache.
386 *
387 * @param map the map to check
388 * @param sme the entry that is about to be free'd
389 */
390static void
391update_next_cache_sme (struct GNUNET_CONTAINER_MultiShortmap *map,
392 const struct SmallMapEntry *sme)
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}
398
399
400int
401GNUNET_CONTAINER_multishortmap_remove (
402 struct GNUNET_CONTAINER_MultiShortmap *map,
403 const struct GNUNET_ShortHashCode *key,
404 const void *value)
405{
406 union MapEntry me;
407 unsigned int i;
408
409 map->modification_counter++;
410 i = idx_of (map, key);
411 me = map->map[i];
412 if (map->use_small_entries)
413 {
414 struct SmallMapEntry *p = NULL;
415
416 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
417 {
418 if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value))
419 {
420 if (NULL == p)
421 map->map[i].sme = sme->next;
422 else
423 p->next = sme->next;
424 update_next_cache_sme (map, sme);
425 GNUNET_free (sme);
426 map->size--;
427 return GNUNET_YES;
428 }
429 p = sme;
430 }
431 }
432 else
433 {
434 struct BigMapEntry *p = NULL;
435
436 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
437 {
438 if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value))
439 {
440 if (NULL == p)
441 map->map[i].bme = bme->next;
442 else
443 p->next = bme->next;
444 update_next_cache_bme (map, bme);
445 GNUNET_free (bme);
446 map->size--;
447 return GNUNET_YES;
448 }
449 p = bme;
450 }
451 }
452 return GNUNET_NO;
453}
454
455
456int
457GNUNET_CONTAINER_multishortmap_remove_all (
458 struct GNUNET_CONTAINER_MultiShortmap *map,
459 const struct GNUNET_ShortHashCode *key)
460{
461 union MapEntry me;
462 unsigned int i;
463 int ret;
464
465 map->modification_counter++;
466
467 ret = 0;
468 i = idx_of (map, key);
469 me = map->map[i];
470 if (map->use_small_entries)
471 {
472 struct SmallMapEntry *sme;
473 struct SmallMapEntry *p;
474
475 p = NULL;
476 sme = me.sme;
477 while (NULL != sme)
478 {
479 if (0 == GNUNET_memcmp (key, sme->key))
480 {
481 if (NULL == p)
482 map->map[i].sme = sme->next;
483 else
484 p->next = sme->next;
485 update_next_cache_sme (map, sme);
486 GNUNET_free (sme);
487 map->size--;
488 if (NULL == p)
489 sme = map->map[i].sme;
490 else
491 sme = p->next;
492 ret++;
493 }
494 else
495 {
496 p = sme;
497 sme = sme->next;
498 }
499 }
500 }
501 else
502 {
503 struct BigMapEntry *bme;
504 struct BigMapEntry *p;
505
506 p = NULL;
507 bme = me.bme;
508 while (NULL != bme)
509 {
510 if (0 == GNUNET_memcmp (key, &bme->key))
511 {
512 if (NULL == p)
513 map->map[i].bme = bme->next;
514 else
515 p->next = bme->next;
516 update_next_cache_bme (map, bme);
517 GNUNET_free (bme);
518 map->size--;
519 if (NULL == p)
520 bme = map->map[i].bme;
521 else
522 bme = p->next;
523 ret++;
524 }
525 else
526 {
527 p = bme;
528 bme = bme->next;
529 }
530 }
531 }
532 return ret;
533}
534
535
536int
537GNUNET_CONTAINER_multishortmap_contains (
538 const struct GNUNET_CONTAINER_MultiShortmap *map,
539 const struct GNUNET_ShortHashCode *key)
540{
541 union MapEntry me;
542
543 me = map->map[idx_of (map, key)];
544 if (map->use_small_entries)
545 {
546 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
547 if (0 == GNUNET_memcmp (key, sme->key))
548 return GNUNET_YES;
549 }
550 else
551 {
552 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
553 if (0 == GNUNET_memcmp (key, &bme->key))
554 return GNUNET_YES;
555 }
556 return GNUNET_NO;
557}
558
559
560int
561GNUNET_CONTAINER_multishortmap_contains_value (
562 const struct GNUNET_CONTAINER_MultiShortmap *map,
563 const struct GNUNET_ShortHashCode *key,
564 const void *value)
565{
566 union MapEntry me;
567
568 me = map->map[idx_of (map, key)];
569 if (map->use_small_entries)
570 {
571 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
572 if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value))
573 return GNUNET_YES;
574 }
575 else
576 {
577 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
578 if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value))
579 return GNUNET_YES;
580 }
581 return GNUNET_NO;
582}
583
584
585/**
586 * Grow the given map to a more appropriate size.
587 *
588 * @param map the hash map to grow
589 */
590static void
591grow (struct GNUNET_CONTAINER_MultiShortmap *map)
592{
593 union MapEntry *old_map;
594 union MapEntry *new_map;
595 unsigned int old_len;
596 unsigned int new_len;
597 unsigned int idx;
598
599 old_map = map->map;
600 old_len = map->map_length;
601 new_len = old_len * 2;
602 if (0 == new_len) /* 2^31 * 2 == 0 */
603 new_len = old_len; /* never use 0 */
604 if (new_len == old_len)
605 return; /* nothing changed */
606 new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
607 if (NULL == new_map)
608 return; /* grow not possible */
609 map->modification_counter++;
610 map->map_length = new_len;
611 map->map = new_map;
612 for (unsigned int i = 0; i < old_len; i++)
613 {
614 if (map->use_small_entries)
615 {
616 struct SmallMapEntry *sme;
617
618 while (NULL != (sme = old_map[i].sme))
619 {
620 old_map[i].sme = sme->next;
621 idx = idx_of (map, sme->key);
622 sme->next = new_map[idx].sme;
623 new_map[idx].sme = sme;
624 }
625 }
626 else
627 {
628 struct BigMapEntry *bme;
629
630 while (NULL != (bme = old_map[i].bme))
631 {
632 old_map[i].bme = bme->next;
633 idx = idx_of (map, &bme->key);
634 bme->next = new_map[idx].bme;
635 new_map[idx].bme = bme;
636 }
637 }
638 }
639 GNUNET_free (old_map);
640}
641
642
643enum GNUNET_GenericReturnValue
644GNUNET_CONTAINER_multishortmap_put (
645 struct GNUNET_CONTAINER_MultiShortmap *map,
646 const struct GNUNET_ShortHashCode *key,
647 void *value,
648 enum GNUNET_CONTAINER_MultiHashMapOption opt)
649{
650 union MapEntry me;
651 unsigned int i;
652
653 i = idx_of (map, key);
654 if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
655 (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
656 {
657 me = map->map[i];
658 if (map->use_small_entries)
659 {
660 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
661 if (0 == GNUNET_memcmp (key, sme->key))
662 {
663 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
664 return GNUNET_SYSERR;
665 sme->value = value;
666 return GNUNET_NO;
667 }
668 }
669 else
670 {
671 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
672 if (0 == GNUNET_memcmp (key, &bme->key))
673 {
674 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
675 return GNUNET_SYSERR;
676 bme->value = value;
677 return GNUNET_NO;
678 }
679 }
680 }
681 if (map->size / 3 >= map->map_length / 4)
682 {
683 grow (map);
684 i = idx_of (map, key);
685 }
686 if (map->use_small_entries)
687 {
688 struct SmallMapEntry *sme;
689
690 sme = GNUNET_new (struct SmallMapEntry);
691 sme->key = key;
692 sme->value = value;
693 sme->next = map->map[i].sme;
694 map->map[i].sme = sme;
695 }
696 else
697 {
698 struct BigMapEntry *bme;
699
700 bme = GNUNET_new (struct BigMapEntry);
701 bme->key = *key;
702 bme->value = value;
703 bme->next = map->map[i].bme;
704 map->map[i].bme = bme;
705 }
706 map->size++;
707 return GNUNET_OK;
708}
709
710
711/**
712 * Iterate over all entries in the map that match a particular key.
713 *
714 * @param map the map
715 * @param key key that the entries must correspond to
716 * @param it function to call on each entry
717 * @param it_cls extra argument to @a it
718 * @return the number of key value pairs processed,
719 * #GNUNET_SYSERR if it aborted iteration
720 */
721int
722GNUNET_CONTAINER_multishortmap_get_multiple (
723 struct GNUNET_CONTAINER_MultiShortmap *map,
724 const struct GNUNET_ShortHashCode *key,
725 GNUNET_CONTAINER_ShortmapIterator it,
726 void *it_cls)
727{
728 int count;
729 union MapEntry me;
730 union MapEntry *ce;
731
732 ce = &map->next_cache[map->next_cache_off];
733 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
734 count = 0;
735 me = map->map[idx_of (map, key)];
736 if (map->use_small_entries)
737 {
738 struct SmallMapEntry *sme;
739
740 ce->sme = me.sme;
741 while (NULL != (sme = ce->sme))
742 {
743 ce->sme = sme->next;
744 if (0 != GNUNET_memcmp (key, sme->key))
745 continue;
746 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value)))
747 {
748 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
749 return GNUNET_SYSERR;
750 }
751 count++;
752 }
753 }
754 else
755 {
756 struct BigMapEntry *bme;
757
758 ce->bme = me.bme;
759 while (NULL != (bme = ce->bme))
760 {
761 ce->bme = bme->next;
762 if (0 != GNUNET_memcmp (key, &bme->key))
763 continue;
764 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value)))
765 {
766 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
767 return GNUNET_SYSERR;
768 }
769 count++;
770 }
771 }
772 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
773 return count;
774}
775
776
777/**
778 * @ingroup hashmap
779 * Call @a it on a random value from the map, or not at all
780 * if the map is empty. Note that this function has linear
781 * complexity (in the size of the map).
782 *
783 * @param map the map
784 * @param it function to call on a random entry
785 * @param it_cls extra argument to @a it
786 * @return the number of key value pairs processed, zero or one.
787 */
788unsigned int
789GNUNET_CONTAINER_multishortmap_get_random (
790 const struct GNUNET_CONTAINER_MultiShortmap *map,
791 GNUNET_CONTAINER_ShortmapIterator it,
792 void *it_cls)
793{
794 unsigned int off;
795 union MapEntry me;
796
797 if (0 == map->size)
798 return 0;
799 if (NULL == it)
800 return 1;
801 off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, map->size);
802 for (unsigned int idx = 0; idx < map->map_length; idx++)
803 {
804 me = map->map[idx];
805 if (map->use_small_entries)
806 {
807 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
808 {
809 if (0 == off)
810 {
811 if (GNUNET_OK != it (it_cls, sme->key, sme->value))
812 return GNUNET_SYSERR;
813 return 1;
814 }
815 off--;
816 }
817 }
818 else
819 {
820 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
821 {
822 if (0 == off)
823 {
824 if (GNUNET_OK != it (it_cls, &bme->key, bme->value))
825 return GNUNET_SYSERR;
826 return 1;
827 }
828 off--;
829 }
830 }
831 }
832 GNUNET_break (0);
833 return GNUNET_SYSERR;
834}
835
836
837struct GNUNET_CONTAINER_MultiShortmapIterator *
838GNUNET_CONTAINER_multishortmap_iterator_create (
839 const struct GNUNET_CONTAINER_MultiShortmap *map)
840{
841 struct GNUNET_CONTAINER_MultiShortmapIterator *iter;
842
843 iter = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmapIterator);
844 iter->map = map;
845 iter->modification_counter = map->modification_counter;
846 iter->me = map->map[0];
847 return iter;
848}
849
850
851enum GNUNET_GenericReturnValue
852GNUNET_CONTAINER_multishortmap_iterator_next (
853 struct GNUNET_CONTAINER_MultiShortmapIterator *iter,
854 struct GNUNET_ShortHashCode *key,
855 const void **value)
856{
857 /* make sure the map has not been modified */
858 GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
859
860 /* look for the next entry, skipping empty buckets */
861 while (1)
862 {
863 if (iter->idx >= iter->map->map_length)
864 return GNUNET_NO;
865 if (GNUNET_YES == iter->map->use_small_entries)
866 {
867 if (NULL != iter->me.sme)
868 {
869 if (NULL != key)
870 *key = *iter->me.sme->key;
871 if (NULL != value)
872 *value = iter->me.sme->value;
873 iter->me.sme = iter->me.sme->next;
874 return GNUNET_YES;
875 }
876 }
877 else
878 {
879 if (NULL != iter->me.bme)
880 {
881 if (NULL != key)
882 *key = iter->me.bme->key;
883 if (NULL != value)
884 *value = iter->me.bme->value;
885 iter->me.bme = iter->me.bme->next;
886 return GNUNET_YES;
887 }
888 }
889 iter->idx += 1;
890 if (iter->idx < iter->map->map_length)
891 iter->me = iter->map->map[iter->idx];
892 }
893}
894
895
896void
897GNUNET_CONTAINER_multishortmap_iterator_destroy (
898 struct GNUNET_CONTAINER_MultiShortmapIterator *iter)
899{
900 GNUNET_free (iter);
901}
902
903
904/* end of container_multishortmap.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-07 19:27:01 +0000