Merge branch 'master' of gnunet.org:gnunet
[oweals/gnunet.git] / src / util / container_multishortmap.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_multishortmap.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_util_lib.h"
28
29 #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multishortmap", __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_ShortHashCode 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_ShortHashCode *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_MultiShortmap
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 /**
154  * Cursor into a multishortmap.
155  * Allows to enumerate elements asynchronously.
156  */
157 struct GNUNET_CONTAINER_MultiShortmapIterator
158 {
159   /**
160    * Position in the bucket 'idx'
161    */
162   union MapEntry me;
163
164   /**
165    * Current bucket index.
166    */
167   unsigned int idx;
168
169   /**
170    * Modification counter as observed on the map when the iterator
171    * was created.
172    */
173   unsigned int modification_counter;
174
175   /**
176    * Map that we are iterating over.
177    */
178   const struct GNUNET_CONTAINER_MultiShortmap *map;
179 };
180
181
182 /**
183  * Create a multi hash map.
184  *
185  * @param len initial size (map will grow as needed)
186  * @param do_not_copy_keys GNUNET_NO is always safe and should be used by default;
187  *                         GNUNET_YES means that on 'put', the 'key' does not have
188  *                         to be copied as the destination of the pointer is
189  *                         guaranteed to be life as long as the value is stored in
190  *                         the hashmap.  This can significantly reduce memory
191  *                         consumption, but of course is also a recipie for
192  *                         heap corruption if the assumption is not true.  Only
193  *                         use this if (1) memory use is important in this case and
194  *                         (2) you have triple-checked that the invariant holds
195  * @return NULL on error
196  */
197 struct GNUNET_CONTAINER_MultiShortmap *
198 GNUNET_CONTAINER_multishortmap_create (unsigned int len,
199                                       int do_not_copy_keys)
200 {
201   struct GNUNET_CONTAINER_MultiShortmap *map;
202
203   GNUNET_assert (len > 0);
204   map = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmap);
205   map->map = GNUNET_new_array (len,
206                                union MapEntry);
207   map->map_length = len;
208   map->use_small_entries = do_not_copy_keys;
209   return map;
210 }
211
212
213 /**
214  * Destroy a hash map.  Will not free any values
215  * stored in the hash map!
216  *
217  * @param map the map
218  */
219 void
220 GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap *map)
221 {
222   GNUNET_assert (0 == map->next_cache_off);
223   for (unsigned int i = 0; i < map->map_length; i++)
224   {
225     union MapEntry me;
226
227     me = map->map[i];
228     if (map->use_small_entries)
229     {
230       struct SmallMapEntry *sme;
231       struct SmallMapEntry *nxt;
232
233       nxt = me.sme;
234       while (NULL != (sme = nxt))
235       {
236         nxt = sme->next;
237         GNUNET_free (sme);
238       }
239       me.sme = NULL;
240     }
241     else
242     {
243       struct BigMapEntry *bme;
244       struct BigMapEntry *nxt;
245
246       nxt = me.bme;
247       while (NULL != (bme = nxt))
248       {
249         nxt = bme->next;
250         GNUNET_free (bme);
251       }
252       me.bme = NULL;
253     }
254   }
255   GNUNET_free (map->map);
256   GNUNET_free (map);
257 }
258
259
260 /**
261  * Compute the index of the bucket for the given key.
262  *
263  * @param map hash map for which to compute the index
264  * @param key what key should the index be computed for
265  * @return offset into the "map" array of "map"
266  */
267 static unsigned int
268 idx_of (const struct GNUNET_CONTAINER_MultiShortmap *map,
269         const struct GNUNET_ShortHashCode *key)
270 {
271   unsigned int kx;
272
273   GNUNET_assert (NULL != map);
274   GNUNET_memcpy (&kx, key, sizeof (kx));
275   return kx % map->map_length;
276 }
277
278
279 /**
280  * Get the number of key-value pairs in the map.
281  *
282  * @param map the map
283  * @return the number of key value pairs
284  */
285 unsigned int
286 GNUNET_CONTAINER_multishortmap_size (const struct GNUNET_CONTAINER_MultiShortmap *map)
287 {
288   return map->size;
289 }
290
291
292 /**
293  * Given a key find a value in the map matching the key.
294  *
295  * @param map the map
296  * @param key what to look for
297  * @return NULL if no value was found; note that
298  *   this is indistinguishable from values that just
299  *   happen to be NULL; use "contains" to test for
300  *   key-value pairs with value NULL
301  */
302 void *
303 GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap *map,
304                                     const struct GNUNET_ShortHashCode *key)
305 {
306   union MapEntry me;
307
308   me = map->map[idx_of (map, key)];
309   if (map->use_small_entries)
310   {
311     for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
312       if (0 == memcmp (key,
313                        sme->key,
314                        sizeof (struct GNUNET_ShortHashCode)))
315         return sme->value;
316   }
317   else
318   {
319     for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
320       if (0 == memcmp (key,
321                        &bme->key,
322                        sizeof (struct GNUNET_ShortHashCode)))
323         return bme->value;
324   }
325   return NULL;
326 }
327
328
329 /**
330  * Iterate over all entries in the map.
331  *
332  * @param map the map
333  * @param it function to call on each entry
334  * @param it_cls extra argument to @a it
335  * @return the number of key value pairs processed,
336  *         #GNUNET_SYSERR if it aborted iteration
337  */
338 int
339 GNUNET_CONTAINER_multishortmap_iterate (struct GNUNET_CONTAINER_MultiShortmap *map,
340                                         GNUNET_CONTAINER_ShortmapIterator it,
341                                         void *it_cls)
342 {
343   int count;
344   union MapEntry me;
345   union MapEntry *ce;
346   struct GNUNET_ShortHashCode kc;
347
348   count = 0;
349   GNUNET_assert (NULL != map);
350   ce = &map->next_cache[map->next_cache_off];
351   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
352   for (unsigned int i = 0; i < map->map_length; i++)
353   {
354     me = map->map[i];
355     if (map->use_small_entries)
356     {
357       struct SmallMapEntry *sme;
358     
359       ce->sme = me.sme;
360       while (NULL != (sme = ce->sme))
361       {
362         ce->sme = sme->next;
363         if ( (NULL != it) &&
364              (GNUNET_OK != it (it_cls,
365                                sme->key,
366                                sme->value)) )
367         {
368           GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
369           return GNUNET_SYSERR; 
370         }
371         count++;
372       }
373     }
374     else
375     {
376       struct BigMapEntry *bme;
377
378       ce->bme = me.bme;
379       while (NULL != (bme = ce->bme))
380       {
381         ce->bme = bme->next;
382         if (NULL != it)
383         {
384           kc = bme->key;
385           if (GNUNET_OK != it (it_cls,
386                                &kc,
387                                bme->value))
388           {
389             GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
390             return GNUNET_SYSERR;
391           }
392         }
393         count++;
394       }
395     }
396   }
397   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
398   return count;
399 }
400
401
402 /**
403  * We are about to free() the @a bme, make sure it is not in
404  * the list of next values for any iterator in the @a map's next_cache.
405  *
406  * @param map the map to check
407  * @param bme the entry that is about to be free'd
408  */
409 static void
410 update_next_cache_bme (struct GNUNET_CONTAINER_MultiShortmap *map,
411                        const struct BigMapEntry *bme)
412 {
413   for (unsigned int i=0;i<map->next_cache_off;i++)
414     if (map->next_cache[i].bme == bme)
415       map->next_cache[i].bme = bme->next;
416 }
417
418
419 /**
420  * We are about to free() the @a sme, make sure it is not in
421  * the list of next values for any iterator in the @a map's next_cache.
422  *
423  * @param map the map to check
424  * @param sme the entry that is about to be free'd
425  */
426 static void
427 update_next_cache_sme (struct GNUNET_CONTAINER_MultiShortmap *map,
428                        const struct SmallMapEntry *sme)
429 {
430   for (unsigned int i=0;i<map->next_cache_off;i++)
431     if (map->next_cache[i].sme == sme)
432       map->next_cache[i].sme = sme->next;
433 }
434
435
436 /**
437  * Remove the given key-value pair from the map.  Note that if the
438  * key-value pair is in the map multiple times, only one of the pairs
439  * will be removed.
440  *
441  * @param map the map
442  * @param key key of the key-value pair
443  * @param value value of the key-value pair
444  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
445  *  is not in the map
446  */
447 int
448 GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *map,
449                                        const struct GNUNET_ShortHashCode *key,
450                                        const void *value)
451 {
452   union MapEntry me;
453   unsigned int i;
454
455   map->modification_counter++;
456   i = idx_of (map, key);
457   me = map->map[i];
458   if (map->use_small_entries)
459   {
460     struct SmallMapEntry *p = NULL;
461     
462     for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
463     {
464       if ((0 == memcmp (key,
465                         sme->key,
466                         sizeof (struct GNUNET_ShortHashCode))) &&
467           (value == sme->value))
468       {
469         if (NULL == p)
470           map->map[i].sme = sme->next;
471         else
472           p->next = sme->next;
473         update_next_cache_sme (map,
474                                sme);
475         GNUNET_free (sme);
476         map->size--;
477         return GNUNET_YES;
478       }
479       p = sme;
480     }
481   }
482   else
483   {
484     struct BigMapEntry *p = NULL;
485     
486     for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
487     {
488       if ((0 == memcmp (key,
489                         &bme->key,
490                         sizeof (struct GNUNET_ShortHashCode))) &&
491           (value == bme->value))
492       {
493         if (NULL == p)
494           map->map[i].bme = bme->next;
495         else
496           p->next = bme->next;
497         update_next_cache_bme (map,
498                                bme);
499         GNUNET_free (bme);
500         map->size--;
501         return GNUNET_YES;
502       }
503       p = bme;
504     }
505   }
506   return GNUNET_NO;
507 }
508
509
510 /**
511  * Remove all entries for the given key from the map.
512  * Note that the values would not be "freed".
513  *
514  * @param map the map
515  * @param key identifies values to be removed
516  * @return number of values removed
517  */
518 int
519 GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap *map,
520                                            const struct GNUNET_ShortHashCode *key)
521 {
522   union MapEntry me;
523   unsigned int i;
524   int ret;
525
526   map->modification_counter++;
527
528   ret = 0;
529   i = idx_of (map, key);
530   me = map->map[i];
531   if (map->use_small_entries)
532   {
533     struct SmallMapEntry *sme;
534     struct SmallMapEntry *p;
535
536     p = NULL;
537     sme = me.sme;
538     while (NULL != sme)
539     {
540       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode)))
541       {
542         if (NULL == p)
543           map->map[i].sme = sme->next;
544         else
545           p->next = sme->next;
546         update_next_cache_sme (map,
547                                sme);
548         GNUNET_free (sme);
549         map->size--;
550         if (NULL == p)
551           sme = map->map[i].sme;
552         else
553           sme = p->next;
554         ret++;
555       }
556       else
557       {
558         p = sme;
559         sme = sme->next;
560       }
561     }
562   }
563   else
564   {
565     struct BigMapEntry *bme;
566     struct BigMapEntry *p;
567
568     p = NULL;
569     bme = me.bme;
570     while (NULL != bme)
571     {
572       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode)))
573       {
574         if (NULL == p)
575           map->map[i].bme = bme->next;
576         else
577           p->next = bme->next;
578         update_next_cache_bme (map,
579                                bme);
580         GNUNET_free (bme);
581         map->size--;
582         if (NULL == p)
583           bme = map->map[i].bme;
584         else
585           bme = p->next;
586         ret++;
587       }
588       else
589       {
590         p = bme;
591         bme = bme->next;
592       }
593     }
594   }
595   return ret;
596 }
597
598
599 /**
600  * Check if the map contains any value under the given
601  * key (including values that are NULL).
602  *
603  * @param map the map
604  * @param key the key to test if a value exists for it
605  * @return #GNUNET_YES if such a value exists,
606  *         #GNUNET_NO if not
607  */
608 int
609 GNUNET_CONTAINER_multishortmap_contains (const struct GNUNET_CONTAINER_MultiShortmap *map,
610                                          const struct GNUNET_ShortHashCode *key)
611 {
612   union MapEntry me;
613
614   me = map->map[idx_of (map, key)];
615   if (map->use_small_entries)
616   {
617     for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
618       if (0 == memcmp (key,
619                        sme->key,
620                        sizeof (struct GNUNET_ShortHashCode)))
621         return GNUNET_YES;
622   }
623   else
624   {
625     for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
626       if (0 == memcmp (key,
627                        &bme->key,
628                        sizeof (struct GNUNET_ShortHashCode)))
629         return GNUNET_YES;
630   }
631   return GNUNET_NO;
632 }
633
634
635 /**
636  * Check if the map contains the given value under the given
637  * key.
638  *
639  * @param map the map
640  * @param key the key to test if a value exists for it
641  * @param value value to test for
642  * @return #GNUNET_YES if such a value exists,
643  *         #GNUNET_NO if not
644  */
645 int
646 GNUNET_CONTAINER_multishortmap_contains_value (const struct GNUNET_CONTAINER_MultiShortmap *map,
647                                                const struct GNUNET_ShortHashCode *key,
648                                                const void *value)
649 {
650   union MapEntry me;
651
652   me = map->map[idx_of (map, key)];
653   if (map->use_small_entries)
654   {
655     for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
656       if ( (0 == memcmp (key,
657                          sme->key,
658                          sizeof (struct GNUNET_ShortHashCode))) &&
659            (sme->value == value) )
660         return GNUNET_YES;
661   }
662   else
663   {
664     for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
665       if ( (0 == memcmp (key,
666                          &bme->key,
667                          sizeof (struct GNUNET_ShortHashCode))) &&
668            (bme->value == value) )
669         return GNUNET_YES;
670   }
671   return GNUNET_NO;
672 }
673
674
675 /**
676  * Grow the given map to a more appropriate size.
677  *
678  * @param map the hash map to grow
679  */
680 static void
681 grow (struct GNUNET_CONTAINER_MultiShortmap *map)
682 {
683   union MapEntry *old_map;
684   union MapEntry *new_map;
685   unsigned int old_len;
686   unsigned int new_len;
687   unsigned int idx;
688
689   map->modification_counter++;
690
691   old_map = map->map;
692   old_len = map->map_length;
693   new_len = old_len * 2;
694   new_map = GNUNET_new_array (new_len,
695                               union MapEntry);
696   map->map_length = new_len;
697   map->map = new_map;
698   for (unsigned int i = 0; i < old_len; i++)
699   {
700     if (map->use_small_entries)
701     {
702       struct SmallMapEntry *sme;
703
704       while (NULL != (sme = old_map[i].sme))
705       {
706         old_map[i].sme = sme->next;
707         idx = idx_of (map, sme->key);
708         sme->next = new_map[idx].sme;
709         new_map[idx].sme = sme;
710       }
711     }
712     else
713     {
714       struct BigMapEntry *bme;
715
716       while (NULL != (bme = old_map[i].bme))
717       {
718         old_map[i].bme = bme->next;
719         idx = idx_of (map, &bme->key);
720         bme->next = new_map[idx].bme;
721         new_map[idx].bme = bme;
722       }
723     }
724   }
725   GNUNET_free (old_map);
726 }
727
728
729 /**
730  * Store a key-value pair in the map.
731  *
732  * @param map the map
733  * @param key key to use
734  * @param value value to use
735  * @param opt options for put
736  * @return #GNUNET_OK on success,
737  *         #GNUNET_NO if a value was replaced (with REPLACE)
738  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
739  *                       value already exists
740  */
741 int
742 GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map,
743                                     const struct GNUNET_ShortHashCode *key,
744                                     void *value,
745                                     enum GNUNET_CONTAINER_MultiHashMapOption opt)
746 {
747   union MapEntry me;
748   unsigned int i;
749
750   i = idx_of (map, key);
751   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
752       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
753   {
754     me = map->map[i];
755     if (map->use_small_entries)
756     {
757       for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
758         if (0 == memcmp (key,
759                          sme->key,
760                          sizeof (struct GNUNET_ShortHashCode)))
761         {
762           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
763             return GNUNET_SYSERR;
764           sme->value = value;
765           return GNUNET_NO;
766         }
767     }
768     else
769     {
770       for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
771         if (0 == memcmp (key,
772                          &bme->key,
773                          sizeof (struct GNUNET_ShortHashCode)))
774         {
775           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
776             return GNUNET_SYSERR;
777           bme->value = value;
778           return GNUNET_NO;
779         }
780     }
781   }
782   if (map->size / 3 >= map->map_length / 4)
783   {
784     grow (map);
785     i = idx_of (map, key);
786   }
787   if (map->use_small_entries)
788   {
789     struct SmallMapEntry *sme;
790
791     sme = GNUNET_new (struct SmallMapEntry);
792     sme->key = key;
793     sme->value = value;
794     sme->next = map->map[i].sme;
795     map->map[i].sme = sme;
796   }
797   else
798   {
799     struct BigMapEntry *bme;
800
801     bme = GNUNET_new (struct BigMapEntry);
802     bme->key = *key;
803     bme->value = value;
804     bme->next = map->map[i].bme;
805     map->map[i].bme = bme;
806   }
807   map->size++;
808   return GNUNET_OK;
809 }
810
811
812 /**
813  * Iterate over all entries in the map that match a particular key.
814  *
815  * @param map the map
816  * @param key key that the entries must correspond to
817  * @param it function to call on each entry
818  * @param it_cls extra argument to @a it
819  * @return the number of key value pairs processed,
820  *         #GNUNET_SYSERR if it aborted iteration
821  */
822 int
823 GNUNET_CONTAINER_multishortmap_get_multiple (struct GNUNET_CONTAINER_MultiShortmap *map,
824                                              const struct GNUNET_ShortHashCode *key,
825                                              GNUNET_CONTAINER_ShortmapIterator it,
826                                              void *it_cls)
827 {
828   int count;
829   union MapEntry me;
830   union MapEntry *ce;
831
832   ce = &map->next_cache[map->next_cache_off];
833   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
834   count = 0;
835   me = map->map[idx_of (map, key)];
836   if (map->use_small_entries)
837   {
838     struct SmallMapEntry *sme;
839
840     ce->sme = me.sme;
841     while (NULL != (sme = ce->sme))
842     {
843       ce->sme = sme->next;
844       if (0 != memcmp (key,
845                        sme->key,
846                        sizeof (struct GNUNET_ShortHashCode)))
847         continue;
848       if ( (NULL != it) &&
849            (GNUNET_OK != it (it_cls,
850                              key,
851                              sme->value)) )
852       {
853         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
854         return GNUNET_SYSERR;
855       }
856       count++;
857     }
858   }
859   else
860   {
861     struct BigMapEntry *bme;
862
863     ce->bme = me.bme;
864     while (NULL != (bme = ce->bme))
865     {
866       ce->bme = bme->next;
867       if (0 != memcmp (key,
868                        &bme->key,
869                        sizeof (struct GNUNET_ShortHashCode)))
870         continue;
871       if ( (NULL != it) &&
872            (GNUNET_OK != it (it_cls,
873                              key,
874                              bme->value)) )
875       {
876         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
877         return GNUNET_SYSERR;
878       }
879       count++;
880     }
881   }
882   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
883   return count;
884 }
885
886
887 /**
888  * @ingroup hashmap
889  * Call @a it on a random value from the map, or not at all
890  * if the map is empty.  Note that this function has linear
891  * complexity (in the size of the map).
892  *
893  * @param map the map
894  * @param it function to call on a random entry
895  * @param it_cls extra argument to @a it
896  * @return the number of key value pairs processed, zero or one.
897  */
898 unsigned int
899 GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiShortmap *map,
900                                           GNUNET_CONTAINER_ShortmapIterator it,
901                                           void *it_cls)
902 {
903   unsigned int off;
904   union MapEntry me;
905
906   if (0 == map->size)
907     return 0;
908   if (NULL == it)
909     return 1;
910   off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
911                                   map->size);
912   for (unsigned int idx = 0; idx < map->map_length; idx++)
913   {
914     me = map->map[idx];
915     if (map->use_small_entries)
916     {
917       for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
918       {
919         if (0 == off)
920         {
921           if (GNUNET_OK != it (it_cls,
922                                sme->key,
923                                sme->value))
924             return GNUNET_SYSERR;
925           return 1;
926         }
927         off--;
928       }
929     }
930     else
931     {
932       for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
933       {
934         if (0 == off)
935         {
936           if (GNUNET_OK != it (it_cls,
937                                &bme->key, bme->value))
938             return GNUNET_SYSERR;
939           return 1;
940         }
941         off--;
942       }
943     }
944   }
945   GNUNET_break (0);
946   return GNUNET_SYSERR;
947 }
948
949
950 /**
951  * Create an iterator for a multishortmap.
952  * The iterator can be used to retrieve all the elements in the multishortmap
953  * one by one, without having to handle all elements at once (in contrast to
954  * #GNUNET_CONTAINER_multishortmap_iterate).  Note that the iterator can not be
955  * used anymore if elements have been removed from 'map' after the creation of
956  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
957  * result in skipped or repeated elements.
958  *
959  * @param map the map to create an iterator for
960  * @return an iterator over the given multishortmap 'map'
961  */
962 struct GNUNET_CONTAINER_MultiShortmapIterator *
963 GNUNET_CONTAINER_multishortmap_iterator_create (const struct GNUNET_CONTAINER_MultiShortmap *map)
964 {
965   struct GNUNET_CONTAINER_MultiShortmapIterator *iter;
966
967   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmapIterator);
968   iter->map = map;
969   iter->modification_counter = map->modification_counter;
970   iter->me = map->map[0];
971   return iter;
972 }
973
974
975 /**
976  * Retrieve the next element from the hash map at the iterator's position.
977  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
978  * are not modified.
979  * This operation is only allowed if no elements have been removed from the
980  * multishortmap since the creation of 'iter', and the map has not been destroyed.
981  * Adding elements may result in repeating or skipping elements.
982  *
983  * @param iter the iterator to get the next element from
984  * @param key pointer to store the key in, can be NULL
985  * @param value pointer to store the value in, can be NULL
986  * @return #GNUNET_YES we returned an element,
987  *         #GNUNET_NO if we are out of elements
988  */
989 int
990 GNUNET_CONTAINER_multishortmap_iterator_next (struct GNUNET_CONTAINER_MultiShortmapIterator *iter,
991                                               struct GNUNET_ShortHashCode *key,
992                                               const void **value)
993 {
994   /* make sure the map has not been modified */
995   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
996
997   /* look for the next entry, skipping empty buckets */
998   while (1)
999   {
1000     if (iter->idx >= iter->map->map_length)
1001       return GNUNET_NO;
1002     if (GNUNET_YES == iter->map->use_small_entries)
1003     {
1004       if (NULL != iter->me.sme)
1005       {
1006         if (NULL != key)
1007           *key = *iter->me.sme->key;
1008         if (NULL != value)
1009           *value = iter->me.sme->value;
1010         iter->me.sme = iter->me.sme->next;
1011         return GNUNET_YES;
1012       }
1013     }
1014     else
1015     {
1016       if (NULL != iter->me.bme)
1017       {
1018         if (NULL != key)
1019           *key = iter->me.bme->key;
1020         if (NULL != value)
1021           *value = iter->me.bme->value;
1022         iter->me.bme = iter->me.bme->next;
1023         return GNUNET_YES;
1024       }
1025     }
1026     iter->idx += 1;
1027     if (iter->idx < iter->map->map_length)
1028       iter->me = iter->map->map[iter->idx];
1029   }
1030 }
1031
1032
1033 /**
1034  * Destroy a multishortmap iterator.
1035  *
1036  * @param iter the iterator to destroy
1037  */
1038 void
1039 GNUNET_CONTAINER_multishortmap_iterator_destroy (struct GNUNET_CONTAINER_MultiShortmapIterator *iter)
1040 {
1041   GNUNET_free (iter);
1042 }
1043
1044
1045 /* end of container_multishortmap.c */