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