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