Merge branch 'master' of ssh://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
6      it under the terms of the GNU General Public License as published
7      by the Free Software Foundation; either version 3, or (at your
8      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      General Public License for more details.
14
15      You should have received a copy of the GNU General Public License
16      along with GNUnet; see the file COPYING.  If not, write to the
17      Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18      Boston, MA 02110-1301, USA.
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  * An entry in the hash map with the full key.
33  */
34 struct BigMapEntry
35 {
36
37   /**
38    * Value of the entry.
39    */
40   void *value;
41
42   /**
43    * If there is a hash collision, we create a linked list.
44    */
45   struct BigMapEntry *next;
46
47   /**
48    * Key for the entry.
49    */
50   struct GNUNET_ShortHashCode key;
51
52 };
53
54
55 /**
56  * An entry in the hash map with just a pointer to the key.
57  */
58 struct SmallMapEntry
59 {
60
61   /**
62    * Value of the entry.
63    */
64   void *value;
65
66   /**
67    * If there is a hash collision, we create a linked list.
68    */
69   struct SmallMapEntry *next;
70
71   /**
72    * Key for the entry.
73    */
74   const struct GNUNET_ShortHashCode *key;
75
76 };
77
78
79 /**
80  * Entry in the map.
81  */
82 union MapEntry
83 {
84   /**
85    * Variant used if map entries only contain a pointer to the key.
86    */
87   struct SmallMapEntry *sme;
88
89   /**
90    * Variant used if map entries contain the full key.
91    */
92   struct BigMapEntry *bme;
93 };
94
95
96 /**
97  * Internal representation of the hash map.
98  */
99 struct GNUNET_CONTAINER_MultiShortmap
100 {
101   /**
102    * All of our buckets.
103    */
104   union MapEntry *map;
105
106   /**
107    * Number of entries in the map.
108    */
109   unsigned int size;
110
111   /**
112    * Length of the "map" array.
113    */
114   unsigned int map_length;
115
116   /**
117    * GNUNET_NO if the map entries are of type 'struct BigMapEntry',
118    * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'.
119    */
120   int use_small_entries;
121
122   /**
123    * Counts the destructive modifications (grow, remove)
124    * to the map, so that iterators can check if they are still valid.
125    */
126   unsigned int modification_counter;
127 };
128
129
130 /**
131  * Cursor into a multishortmap.
132  * Allows to enumerate elements asynchronously.
133  */
134 struct GNUNET_CONTAINER_MultiShortmapIterator
135 {
136   /**
137    * Position in the bucket 'idx'
138    */
139   union MapEntry me;
140
141   /**
142    * Current bucket index.
143    */
144   unsigned int idx;
145
146   /**
147    * Modification counter as observed on the map when the iterator
148    * was created.
149    */
150   unsigned int modification_counter;
151
152   /**
153    * Map that we are iterating over.
154    */
155   const struct GNUNET_CONTAINER_MultiShortmap *map;
156 };
157
158
159 /**
160  * Create a multi hash map.
161  *
162  * @param len initial size (map will grow as needed)
163  * @param do_not_copy_keys GNUNET_NO is always safe and should be used by default;
164  *                         GNUNET_YES means that on 'put', the 'key' does not have
165  *                         to be copied as the destination of the pointer is
166  *                         guaranteed to be life as long as the value is stored in
167  *                         the hashmap.  This can significantly reduce memory
168  *                         consumption, but of course is also a recipie for
169  *                         heap corruption if the assumption is not true.  Only
170  *                         use this if (1) memory use is important in this case and
171  *                         (2) you have triple-checked that the invariant holds
172  * @return NULL on error
173  */
174 struct GNUNET_CONTAINER_MultiShortmap *
175 GNUNET_CONTAINER_multishortmap_create (unsigned int len,
176                                       int do_not_copy_keys)
177 {
178   struct GNUNET_CONTAINER_MultiShortmap *map;
179
180   GNUNET_assert (len > 0);
181   map = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmap);
182   map->map = GNUNET_malloc (len * sizeof (union MapEntry));
183   map->map_length = len;
184   map->use_small_entries = do_not_copy_keys;
185   return map;
186 }
187
188
189 /**
190  * Destroy a hash map.  Will not free any values
191  * stored in the hash map!
192  *
193  * @param map the map
194  */
195 void
196 GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap
197                                        *map)
198 {
199   unsigned int i;
200   union MapEntry me;
201
202   for (i = 0; i < map->map_length; i++)
203   {
204     me = map->map[i];
205     if (map->use_small_entries)
206     {
207       struct SmallMapEntry *sme;
208       struct SmallMapEntry *nxt;
209
210       nxt = me.sme;
211       while (NULL != (sme = nxt))
212       {
213         nxt = sme->next;
214         GNUNET_free (sme);
215       }
216       me.sme = NULL;
217     }
218     else
219     {
220       struct BigMapEntry *bme;
221       struct BigMapEntry *nxt;
222
223       nxt = me.bme;
224       while (NULL != (bme = nxt))
225       {
226         nxt = bme->next;
227         GNUNET_free (bme);
228       }
229       me.bme = NULL;
230     }
231   }
232   GNUNET_free (map->map);
233   GNUNET_free (map);
234 }
235
236
237 /**
238  * Compute the index of the bucket for the given key.
239  *
240  * @param map hash map for which to compute the index
241  * @param key what key should the index be computed for
242  * @return offset into the "map" array of "map"
243  */
244 static unsigned int
245 idx_of (const struct GNUNET_CONTAINER_MultiShortmap *map,
246         const struct GNUNET_ShortHashCode *key)
247 {
248   unsigned int kx;
249
250   GNUNET_assert (NULL != map);
251   GNUNET_memcpy (&kx, key, sizeof (kx));
252   return kx % map->map_length;
253 }
254
255
256 /**
257  * Get the number of key-value pairs in the map.
258  *
259  * @param map the map
260  * @return the number of key value pairs
261  */
262 unsigned int
263 GNUNET_CONTAINER_multishortmap_size (const struct GNUNET_CONTAINER_MultiShortmap *map)
264 {
265   return map->size;
266 }
267
268
269 /**
270  * Given a key find a value in the map matching the key.
271  *
272  * @param map the map
273  * @param key what to look for
274  * @return NULL if no value was found; note that
275  *   this is indistinguishable from values that just
276  *   happen to be NULL; use "contains" to test for
277  *   key-value pairs with value NULL
278  */
279 void *
280 GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap *map,
281                                     const struct GNUNET_ShortHashCode *key)
282 {
283   union MapEntry me;
284
285   me = map->map[idx_of (map, key)];
286   if (map->use_small_entries)
287   {
288     struct SmallMapEntry *sme;
289
290     for (sme = me.sme; NULL != sme; sme = sme->next)
291       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode)))
292         return sme->value;
293   }
294   else
295   {
296     struct BigMapEntry *bme;
297
298     for (bme = me.bme; NULL != bme; bme = bme->next)
299       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode)))
300         return bme->value;
301   }
302   return NULL;
303 }
304
305
306 /**
307  * Iterate over all entries in the map.
308  *
309  * @param map the map
310  * @param it function to call on each entry
311  * @param it_cls extra argument to @a it
312  * @return the number of key value pairs processed,
313  *         #GNUNET_SYSERR if it aborted iteration
314  */
315 int
316 GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map,
317                                        GNUNET_CONTAINER_ShortmapIterator it,
318                                        void *it_cls)
319 {
320   int count;
321   unsigned int i;
322   union MapEntry me;
323   struct GNUNET_ShortHashCode kc;
324
325   count = 0;
326   GNUNET_assert (NULL != map);
327   for (i = 0; i < map->map_length; i++)
328   {
329     me = map->map[i];
330     if (map->use_small_entries)
331     {
332       struct SmallMapEntry *sme;
333       struct SmallMapEntry *nxt;
334
335       nxt = me.sme;
336       while (NULL != (sme = nxt))
337       {
338         nxt = sme->next;
339         if (NULL != it)
340         {
341           if (GNUNET_OK != it (it_cls, sme->key, sme->value))
342             return GNUNET_SYSERR;
343         }
344         count++;
345       }
346     }
347     else
348     {
349       struct BigMapEntry *bme;
350       struct BigMapEntry *nxt;
351
352       nxt = me.bme;
353       while (NULL != (bme = nxt))
354       {
355         nxt = bme->next;
356         if (NULL != it)
357         {
358           kc = bme->key;
359           if (GNUNET_OK != it (it_cls, &kc, bme->value))
360             return GNUNET_SYSERR;
361         }
362         count++;
363       }
364     }
365   }
366   return count;
367 }
368
369
370 /**
371  * Remove the given key-value pair from the map.  Note that if the
372  * key-value pair is in the map multiple times, only one of the pairs
373  * will be removed.
374  *
375  * @param map the map
376  * @param key key of the key-value pair
377  * @param value value of the key-value pair
378  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
379  *  is not in the map
380  */
381 int
382 GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *map,
383                                        const struct GNUNET_ShortHashCode *key,
384                                        const void *value)
385 {
386   union MapEntry me;
387   unsigned int i;
388
389   map->modification_counter++;
390
391   i = idx_of (map, key);
392   me = map->map[i];
393   if (map->use_small_entries)
394   {
395     struct SmallMapEntry *sme;
396     struct SmallMapEntry *p;
397
398     p = NULL;
399     for (sme = me.sme; NULL != sme; sme = sme->next)
400     {
401       if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) &&
402           (value == sme->value))
403       {
404         if (NULL == p)
405           map->map[i].sme = sme->next;
406         else
407           p->next = sme->next;
408         GNUNET_free (sme);
409         map->size--;
410         return GNUNET_YES;
411       }
412       p = sme;
413     }
414   }
415   else
416   {
417     struct BigMapEntry *bme;
418     struct BigMapEntry *p;
419
420     p = NULL;
421     for (bme = me.bme; NULL != bme; bme = bme->next)
422     {
423       if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) &&
424           (value == bme->value))
425       {
426         if (NULL == p)
427           map->map[i].bme = bme->next;
428         else
429           p->next = bme->next;
430         GNUNET_free (bme);
431         map->size--;
432         return GNUNET_YES;
433       }
434       p = bme;
435     }
436   }
437   return GNUNET_NO;
438 }
439
440
441 /**
442  * Remove all entries for the given key from the map.
443  * Note that the values would not be "freed".
444  *
445  * @param map the map
446  * @param key identifies values to be removed
447  * @return number of values removed
448  */
449 int
450 GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap *map,
451                                            const struct GNUNET_ShortHashCode *key)
452 {
453   union MapEntry me;
454   unsigned int i;
455   int ret;
456
457   map->modification_counter++;
458
459   ret = 0;
460   i = idx_of (map, key);
461   me = map->map[i];
462   if (map->use_small_entries)
463   {
464     struct SmallMapEntry *sme;
465     struct SmallMapEntry *p;
466
467     p = NULL;
468     sme = me.sme;
469     while (NULL != sme)
470     {
471       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode)))
472       {
473         if (NULL == p)
474           map->map[i].sme = sme->next;
475         else
476           p->next = sme->next;
477         GNUNET_free (sme);
478         map->size--;
479         if (NULL == p)
480           sme = map->map[i].sme;
481         else
482           sme = p->next;
483         ret++;
484       }
485       else
486       {
487         p = sme;
488         sme = sme->next;
489       }
490     }
491   }
492   else
493   {
494     struct BigMapEntry *bme;
495     struct BigMapEntry *p;
496
497     p = NULL;
498     bme = me.bme;
499     while (NULL != bme)
500     {
501       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode)))
502       {
503         if (NULL == p)
504           map->map[i].bme = bme->next;
505         else
506           p->next = bme->next;
507         GNUNET_free (bme);
508         map->size--;
509         if (NULL == p)
510           bme = map->map[i].bme;
511         else
512           bme = p->next;
513         ret++;
514       }
515       else
516       {
517         p = bme;
518         bme = bme->next;
519       }
520     }
521   }
522   return ret;
523 }
524
525
526 /**
527  * Check if the map contains any value under the given
528  * key (including values that are NULL).
529  *
530  * @param map the map
531  * @param key the key to test if a value exists for it
532  * @return #GNUNET_YES if such a value exists,
533  *         #GNUNET_NO if not
534  */
535 int
536 GNUNET_CONTAINER_multishortmap_contains (const struct GNUNET_CONTAINER_MultiShortmap *map,
537                                          const struct GNUNET_ShortHashCode *key)
538 {
539   union MapEntry me;
540
541   me = map->map[idx_of (map, key)];
542   if (map->use_small_entries)
543   {
544     struct SmallMapEntry *sme;
545
546     for (sme = me.sme; NULL != sme; sme = sme->next)
547       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode)))
548         return GNUNET_YES;
549   }
550   else
551   {
552     struct BigMapEntry *bme;
553
554     for (bme = me.bme; NULL != bme; bme = bme->next)
555       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode)))
556         return GNUNET_YES;
557   }
558   return GNUNET_NO;
559 }
560
561
562 /**
563  * Check if the map contains the given value under the given
564  * key.
565  *
566  * @param map the map
567  * @param key the key to test if a value exists for it
568  * @param value value to test for
569  * @return #GNUNET_YES if such a value exists,
570  *         #GNUNET_NO if not
571  */
572 int
573 GNUNET_CONTAINER_multishortmap_contains_value (const struct GNUNET_CONTAINER_MultiShortmap *map,
574                                                const struct GNUNET_ShortHashCode *key,
575                                                const void *value)
576 {
577   union MapEntry me;
578
579   me = map->map[idx_of (map, key)];
580   if (map->use_small_entries)
581   {
582     struct SmallMapEntry *sme;
583
584     for (sme = me.sme; NULL != sme; sme = sme->next)
585       if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) &&
586            (sme->value == value) )
587         return GNUNET_YES;
588   }
589   else
590   {
591     struct BigMapEntry *bme;
592
593     for (bme = me.bme; NULL != bme; bme = bme->next)
594       if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) &&
595            (bme->value == value) )
596         return GNUNET_YES;
597   }
598   return GNUNET_NO;
599 }
600
601
602 /**
603  * Grow the given map to a more appropriate size.
604  *
605  * @param map the hash map to grow
606  */
607 static void
608 grow (struct GNUNET_CONTAINER_MultiShortmap *map)
609 {
610   union MapEntry *old_map;
611   union MapEntry *new_map;
612   unsigned int old_len;
613   unsigned int new_len;
614   unsigned int idx;
615   unsigned int i;
616
617   map->modification_counter++;
618
619   old_map = map->map;
620   old_len = map->map_length;
621   new_len = old_len * 2;
622   new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len);
623   map->map_length = new_len;
624   map->map = new_map;
625   for (i = 0; i < old_len; i++)
626   {
627     if (map->use_small_entries)
628     {
629       struct SmallMapEntry *sme;
630
631       while (NULL != (sme = old_map[i].sme))
632       {
633         old_map[i].sme = sme->next;
634         idx = idx_of (map, sme->key);
635         sme->next = new_map[idx].sme;
636         new_map[idx].sme = sme;
637       }
638     }
639     else
640     {
641       struct BigMapEntry *bme;
642
643       while (NULL != (bme = old_map[i].bme))
644       {
645         old_map[i].bme = bme->next;
646         idx = idx_of (map, &bme->key);
647         bme->next = new_map[idx].bme;
648         new_map[idx].bme = bme;
649       }
650     }
651   }
652   GNUNET_free (old_map);
653 }
654
655
656 /**
657  * Store a key-value pair in the map.
658  *
659  * @param map the map
660  * @param key key to use
661  * @param value value to use
662  * @param opt options for put
663  * @return #GNUNET_OK on success,
664  *         #GNUNET_NO if a value was replaced (with REPLACE)
665  *         #GNUNET_SYSERR if GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
666  *                       value already exists
667  */
668 int
669 GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map,
670                                     const struct GNUNET_ShortHashCode *key,
671                                     void *value,
672                                     enum GNUNET_CONTAINER_MultiHashMapOption opt)
673 {
674   union MapEntry me;
675   unsigned int i;
676
677   i = idx_of (map, key);
678   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
679       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
680   {
681     me = map->map[i];
682     if (map->use_small_entries)
683     {
684       struct SmallMapEntry *sme;
685
686       for (sme = me.sme; NULL != sme; sme = sme->next)
687         if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode)))
688         {
689           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
690             return GNUNET_SYSERR;
691           sme->value = value;
692           return GNUNET_NO;
693         }
694     }
695     else
696     {
697       struct BigMapEntry *bme;
698
699       for (bme = me.bme; NULL != bme; bme = bme->next)
700         if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode)))
701         {
702           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
703             return GNUNET_SYSERR;
704           bme->value = value;
705           return GNUNET_NO;
706         }
707     }
708   }
709   if (map->size / 3 >= map->map_length / 4)
710   {
711     grow (map);
712     i = idx_of (map, key);
713   }
714   if (map->use_small_entries)
715   {
716     struct SmallMapEntry *sme;
717
718     sme = GNUNET_new (struct SmallMapEntry);
719     sme->key = key;
720     sme->value = value;
721     sme->next = map->map[i].sme;
722     map->map[i].sme = sme;
723   }
724   else
725   {
726     struct BigMapEntry *bme;
727
728     bme = GNUNET_new (struct BigMapEntry);
729     bme->key = *key;
730     bme->value = value;
731     bme->next = map->map[i].bme;
732     map->map[i].bme = bme;
733   }
734   map->size++;
735   return GNUNET_OK;
736 }
737
738
739 /**
740  * Iterate over all entries in the map that match a particular key.
741  *
742  * @param map the map
743  * @param key key that the entries must correspond to
744  * @param it function to call on each entry
745  * @param it_cls extra argument to @a it
746  * @return the number of key value pairs processed,
747  *         #GNUNET_SYSERR if it aborted iteration
748  */
749 int
750 GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map,
751                                              const struct GNUNET_ShortHashCode *key,
752                                              GNUNET_CONTAINER_ShortmapIterator it,
753                                              void *it_cls)
754 {
755   int count;
756   union MapEntry me;
757
758   count = 0;
759   me = map->map[idx_of (map, key)];
760   if (map->use_small_entries)
761   {
762     struct SmallMapEntry *sme;
763     struct SmallMapEntry *nxt;
764
765     nxt = me.sme;
766     while (NULL != (sme = nxt))
767     {
768       nxt = sme->next;
769       if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode)))
770         continue;
771       if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value)))
772         return GNUNET_SYSERR;
773       count++;
774     }
775   }
776   else
777   {
778     struct BigMapEntry *bme;
779     struct BigMapEntry *nxt;
780
781     nxt = me.bme;
782     while (NULL != (bme = nxt))
783     {
784       nxt = bme->next;
785       if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode)))
786         continue;
787       if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value)))
788         return GNUNET_SYSERR;
789       count++;
790     }
791   }
792   return count;
793 }
794
795
796 /**
797  * @ingroup hashmap
798  * Call @a it on a random value from the map, or not at all
799  * if the map is empty.  Note that this function has linear
800  * complexity (in the size of the map).
801  *
802  * @param map the map
803  * @param it function to call on a random entry
804  * @param it_cls extra argument to @a it
805  * @return the number of key value pairs processed, zero or one.
806  */
807 unsigned int
808 GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiShortmap *map,
809                                           GNUNET_CONTAINER_ShortmapIterator it,
810                                           void *it_cls)
811 {
812   unsigned int off;
813   unsigned int idx;
814   union MapEntry me;
815
816   if (0 == map->size)
817     return 0;
818   if (NULL == it)
819     return 1;
820   off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
821                                   map->size);
822   for (idx = 0; idx < map->map_length; idx++)
823   {
824     me = map->map[idx];
825     if (map->use_small_entries)
826     {
827       struct SmallMapEntry *sme;
828       struct SmallMapEntry *nxt;
829
830       nxt = me.sme;
831       while (NULL != (sme = nxt))
832       {
833         nxt = sme->next;
834         if (0 == off)
835         {
836           if (GNUNET_OK != it (it_cls,
837                                sme->key,
838                                sme->value))
839             return GNUNET_SYSERR;
840           return 1;
841         }
842         off--;
843       }
844     }
845     else
846     {
847       struct BigMapEntry *bme;
848       struct BigMapEntry *nxt;
849
850       nxt = me.bme;
851       while (NULL != (bme = nxt))
852       {
853         nxt = bme->next;
854         if (0 == off)
855         {
856           if (GNUNET_OK != it (it_cls,
857                                &bme->key, bme->value))
858             return GNUNET_SYSERR;
859           return 1;
860         }
861         off--;
862       }
863     }
864   }
865   GNUNET_break (0);
866   return GNUNET_SYSERR;
867 }
868
869
870 /**
871  * Create an iterator for a multishortmap.
872  * The iterator can be used to retrieve all the elements in the multishortmap
873  * one by one, without having to handle all elements at once (in contrast to
874  * #GNUNET_CONTAINER_multishortmap_iterate).  Note that the iterator can not be
875  * used anymore if elements have been removed from 'map' after the creation of
876  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
877  * result in skipped or repeated elements.
878  *
879  * @param map the map to create an iterator for
880  * @return an iterator over the given multishortmap 'map'
881  */
882 struct GNUNET_CONTAINER_MultiShortmapIterator *
883 GNUNET_CONTAINER_multishortmap_iterator_create (const struct GNUNET_CONTAINER_MultiShortmap *map)
884 {
885   struct GNUNET_CONTAINER_MultiShortmapIterator *iter;
886
887   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmapIterator);
888   iter->map = map;
889   iter->modification_counter = map->modification_counter;
890   iter->me = map->map[0];
891   return iter;
892 }
893
894
895 /**
896  * Retrieve the next element from the hash map at the iterator's position.
897  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
898  * are not modified.
899  * This operation is only allowed if no elements have been removed from the
900  * multishortmap since the creation of 'iter', and the map has not been destroyed.
901  * Adding elements may result in repeating or skipping elements.
902  *
903  * @param iter the iterator to get the next element from
904  * @param key pointer to store the key in, can be NULL
905  * @param value pointer to store the value in, can be NULL
906  * @return #GNUNET_YES we returned an element,
907  *         #GNUNET_NO if we are out of elements
908  */
909 int
910 GNUNET_CONTAINER_multishortmap_iterator_next (struct GNUNET_CONTAINER_MultiShortmapIterator *iter,
911                                               struct GNUNET_ShortHashCode *key,
912                                               const void **value)
913 {
914   /* make sure the map has not been modified */
915   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
916
917   /* look for the next entry, skipping empty buckets */
918   while (1)
919   {
920     if (iter->idx >= iter->map->map_length)
921       return GNUNET_NO;
922     if (GNUNET_YES == iter->map->use_small_entries)
923     {
924       if (NULL != iter->me.sme)
925       {
926         if (NULL != key)
927           *key = *iter->me.sme->key;
928         if (NULL != value)
929           *value = iter->me.sme->value;
930         iter->me.sme = iter->me.sme->next;
931         return GNUNET_YES;
932       }
933     }
934     else
935     {
936       if (NULL != iter->me.bme)
937       {
938         if (NULL != key)
939           *key = iter->me.bme->key;
940         if (NULL != value)
941           *value = iter->me.bme->value;
942         iter->me.bme = iter->me.bme->next;
943         return GNUNET_YES;
944       }
945     }
946     iter->idx += 1;
947     if (iter->idx < iter->map->map_length)
948       iter->me = iter->map->map[iter->idx];
949   }
950 }
951
952
953 /**
954  * Destroy a multishortmap iterator.
955  *
956  * @param iter the iterator to destroy
957  */
958 void
959 GNUNET_CONTAINER_multishortmap_iterator_destroy (struct GNUNET_CONTAINER_MultiShortmapIterator *iter)
960 {
961   GNUNET_free (iter);
962 }
963
964
965 /* end of container_multishortmap.c */