Merge branch 'master' of git+ssh://gnunet.org/gnunet
[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   old_map = map->map;
768   old_len = map->map_length;
769   GNUNET_assert (0 != old_len);
770   new_len = old_len * 2;
771   if (0 == new_len) /* 2^31 * 2 == 0 */
772     new_len = old_len; /* never use 0 */
773   if (new_len == old_len)
774     return; /* nothing changed */
775   new_map = GNUNET_malloc_large (new_len *
776                                  sizeof (union MapEntry));
777   if (NULL == new_map)
778     return; /* grow not possible */
779   map->modification_counter++;
780   map->map_length = new_len;
781   map->map = new_map;
782   for (unsigned int i = 0; i < old_len; i++)
783   {
784     if (map->use_small_entries)
785     {
786       struct SmallMapEntry *sme;
787
788       while (NULL != (sme = old_map[i].sme))
789       {
790         old_map[i].sme = sme->next;
791         idx = idx_of (map, sme->key);
792         sme->next = new_map[idx].sme;
793         new_map[idx].sme = sme;
794       }
795     }
796     else
797     {
798       struct BigMapEntry *bme;
799
800       while (NULL != (bme = old_map[i].bme))
801       {
802         old_map[i].bme = bme->next;
803         idx = idx_of (map, &bme->key);
804         bme->next = new_map[idx].bme;
805         new_map[idx].bme = bme;
806       }
807     }
808   }
809   GNUNET_free (old_map);
810 }
811
812
813 /**
814  * Store a key-value pair in the map.
815  *
816  * @param map the map
817  * @param key key to use
818  * @param value value to use
819  * @param opt options for put
820  * @return #GNUNET_OK on success,
821  *         #GNUNET_NO if a value was replaced (with REPLACE)
822  *         #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
823  *                       value already exists
824  */
825 int
826 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
827                                    const struct GNUNET_HashCode *key,
828                                    void *value,
829                                    enum GNUNET_CONTAINER_MultiHashMapOption opt)
830 {
831   union MapEntry me;
832   unsigned int i;
833
834   i = idx_of (map, key);
835   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
836       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
837   {
838     me = map->map[i];
839     if (map->use_small_entries)
840     {
841       struct SmallMapEntry *sme;
842
843       for (sme = me.sme; NULL != sme; sme = sme->next)
844         if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
845         {
846           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
847             return GNUNET_SYSERR;
848           sme->value = value;
849           return GNUNET_NO;
850         }
851     }
852     else
853     {
854       struct BigMapEntry *bme;
855
856       for (bme = me.bme; NULL != bme; bme = bme->next)
857         if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
858         {
859           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
860             return GNUNET_SYSERR;
861           bme->value = value;
862           return GNUNET_NO;
863         }
864     }
865   }
866   if (map->size / 3 >= map->map_length / 4)
867   {
868     grow (map);
869     i = idx_of (map, key);
870   }
871   if (map->use_small_entries)
872   {
873     struct SmallMapEntry *sme;
874
875     sme = GNUNET_new (struct SmallMapEntry);
876     sme->key = key;
877     sme->value = value;
878     sme->next = map->map[i].sme;
879     map->map[i].sme = sme;
880   }
881   else
882   {
883     struct BigMapEntry *bme;
884
885     bme = GNUNET_new (struct BigMapEntry);
886     bme->key = *key;
887     bme->value = value;
888     bme->next = map->map[i].bme;
889     map->map[i].bme = bme;
890   }
891   map->size++;
892   return GNUNET_OK;
893 }
894
895
896 /**
897  * Iterate over all entries in the map that match a particular key.
898  *
899  * @param map the map
900  * @param key key that the entries must correspond to
901  * @param it function to call on each entry
902  * @param it_cls extra argument to it
903  * @return the number of key value pairs processed,
904  *         #GNUNET_SYSERR if it aborted iteration
905  */
906 int
907 GNUNET_CONTAINER_multihashmap_get_multiple (struct GNUNET_CONTAINER_MultiHashMap *map,
908                                             const struct GNUNET_HashCode *key,
909                                             GNUNET_CONTAINER_HashMapIterator it,
910                                             void *it_cls)
911 {
912   int count;
913   union MapEntry *me;
914   union MapEntry *ce;
915
916   ce = &map->next_cache[map->next_cache_off];
917   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
918   count = 0;
919   me = &map->map[idx_of (map, key)];
920   if (map->use_small_entries)
921   {
922     struct SmallMapEntry *sme;
923
924     ce->sme = me->sme;
925     while (NULL != (sme = ce->sme))
926     {
927       ce->sme = sme->next;
928       if (0 != memcmp (key,
929                        sme->key,
930                        sizeof (struct GNUNET_HashCode)))
931         continue;
932       if ( (NULL != it) &&
933            (GNUNET_OK != it (it_cls,
934                              key,
935                              sme->value)))
936       {
937         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
938         return GNUNET_SYSERR;
939       }
940       count++;
941     }
942   }
943   else
944   {
945     struct BigMapEntry *bme;
946
947     ce->bme = me->bme;
948     while (NULL != (bme = ce->bme))
949     {
950       ce->bme = bme->next;
951       if (0 != memcmp (key,
952                        &bme->key,
953                        sizeof (struct GNUNET_HashCode)))
954         continue;
955       if ( (NULL != it) &&
956            (GNUNET_OK != it (it_cls,
957                              key,
958                              bme->value)))
959       {
960         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
961         return GNUNET_SYSERR;
962       }
963       count++;
964     }
965   }
966   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
967   return count;
968 }
969
970
971 /**
972  * @ingroup hashmap
973  * Call @a it on a random value from the map, or not at all
974  * if the map is empty. Note that this function has linear
975  * complexity (in the size of the map).
976  *
977  * @param map the map
978  * @param it function to call on a random entry
979  * @param it_cls extra argument to @a it
980  * @return the number of key value pairs processed, zero or one.
981  */
982 unsigned int
983 GNUNET_CONTAINER_multihashmap_get_random (const struct GNUNET_CONTAINER_MultiHashMap *map,
984                                           GNUNET_CONTAINER_HashMapIterator it,
985                                           void *it_cls)
986 {
987   unsigned int off;
988   unsigned int idx;
989   union MapEntry me;
990
991   if (0 == map->size)
992     return 0;
993   if (NULL == it)
994     return 1;
995   off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
996                                   map->size);
997   for (idx = 0; idx < map->map_length; idx++)
998   {
999     me = map->map[idx];
1000     if (map->use_small_entries)
1001     {
1002       struct SmallMapEntry *sme;
1003       struct SmallMapEntry *nxt;
1004
1005       nxt = me.sme;
1006       while (NULL != (sme = nxt))
1007       {
1008         nxt = sme->next;
1009         if (0 == off)
1010         {
1011           if (GNUNET_OK != it (it_cls,
1012                                sme->key,
1013                                sme->value))
1014             return GNUNET_SYSERR;
1015           return 1;
1016         }
1017         off--;
1018       }
1019     }
1020     else
1021     {
1022       struct BigMapEntry *bme;
1023       struct BigMapEntry *nxt;
1024
1025       nxt = me.bme;
1026       while (NULL != (bme = nxt))
1027       {
1028         nxt = bme->next;
1029         if (0 == off)
1030         {
1031           if (GNUNET_OK != it (it_cls,
1032                                &bme->key, bme->value))
1033             return GNUNET_SYSERR;
1034           return 1;
1035         }
1036         off--;
1037       }
1038     }
1039   }
1040   GNUNET_break (0);
1041   return GNUNET_SYSERR;
1042 }
1043
1044
1045 /**
1046  * Create an iterator for a multihashmap.
1047  * The iterator can be used to retrieve all the elements in the multihashmap
1048  * one by one, without having to handle all elements at once (in contrast to
1049  * GNUNET_CONTAINER_multihashmap_iterate()).  Note that the iterator can not be
1050  * used anymore if elements have been removed from 'map' after the creation of
1051  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
1052  * result in skipped or repeated elements.
1053  *
1054  * @param map the map to create an iterator for
1055  * @return an iterator over the given multihashmap 'map'
1056  */
1057 struct GNUNET_CONTAINER_MultiHashMapIterator *
1058 GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map)
1059 {
1060   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
1061
1062   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMapIterator);
1063   iter->map = map;
1064   iter->modification_counter = map->modification_counter;
1065   iter->me = map->map[0];
1066   return iter;
1067 }
1068
1069
1070 /**
1071  * Retrieve the next element from the hash map at the iterator's position.
1072  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
1073  * are not modified.
1074  * This operation is only allowed if no elements have been removed from the
1075  * multihashmap since the creation of 'iter', and the map has not been destroyed.
1076  * Adding elements may result in repeating or skipping elements.
1077  *
1078  * @param iter the iterator to get the next element from
1079  * @param key pointer to store the key in, can be NULL
1080  * @param value pointer to store the value in, can be NULL
1081  * @return #GNUNET_YES we returned an element,
1082  *         #GNUNET_NO if we are out of elements
1083  */
1084 int
1085 GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
1086                                              struct GNUNET_HashCode *key,
1087                                              const void **value)
1088 {
1089   /* make sure the map has not been modified */
1090   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
1091
1092   /* look for the next entry, skipping empty buckets */
1093   while (1)
1094   {
1095     if (iter->idx >= iter->map->map_length)
1096       return GNUNET_NO;
1097     if (GNUNET_YES == iter->map->use_small_entries)
1098     {
1099       if (NULL != iter->me.sme)
1100       {
1101         if (NULL != key)
1102           *key = *iter->me.sme->key;
1103         if (NULL != value)
1104           *value = iter->me.sme->value;
1105         iter->me.sme = iter->me.sme->next;
1106         return GNUNET_YES;
1107       }
1108     }
1109     else
1110     {
1111       if (NULL != iter->me.bme)
1112       {
1113         if (NULL != key)
1114           *key = iter->me.bme->key;
1115         if (NULL != value)
1116           *value = iter->me.bme->value;
1117         iter->me.bme = iter->me.bme->next;
1118         return GNUNET_YES;
1119       }
1120     }
1121     iter->idx += 1;
1122     if (iter->idx < iter->map->map_length)
1123       iter->me = iter->map->map[iter->idx];
1124   }
1125 }
1126
1127
1128 /**
1129  * Destroy a multihashmap iterator.
1130  *
1131  * @param iter the iterator to destroy
1132  */
1133 void
1134 GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
1135 {
1136   GNUNET_free (iter);
1137 }
1138
1139
1140 /* end of container_multihashmap.c */