Merge branch 'master' of ssh://gnunet.org/gnunet
[oweals/gnunet.git] / src / util / container_multipeermap.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_multipeermap.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-multipeermap", __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_PeerIdentity 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_PeerIdentity *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_MultiPeerMap
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 multipeermap.
132  * Allows to enumerate elements asynchronously.
133  */
134 struct GNUNET_CONTAINER_MultiPeerMapIterator
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_MultiPeerMap *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_MultiPeerMap *
175 GNUNET_CONTAINER_multipeermap_create (unsigned int len,
176                                       int do_not_copy_keys)
177 {
178   struct GNUNET_CONTAINER_MultiPeerMap *map;
179
180   GNUNET_assert (len > 0);
181   map = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMap);
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_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap
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_MultiPeerMap *map,
246         const struct GNUNET_PeerIdentity *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_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap
264                                     *map)
265 {
266   return map->size;
267 }
268
269
270 /**
271  * Given a key find a value in the map matching the key.
272  *
273  * @param map the map
274  * @param key what to look for
275  * @return NULL if no value was found; note that
276  *   this is indistinguishable from values that just
277  *   happen to be NULL; use "contains" to test for
278  *   key-value pairs with value NULL
279  */
280 void *
281 GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap
282                                    *map, const struct GNUNET_PeerIdentity *key)
283 {
284   union MapEntry me;
285
286   me = map->map[idx_of (map, key)];
287   if (map->use_small_entries)
288   {
289     struct SmallMapEntry *sme;
290
291     for (sme = me.sme; NULL != sme; sme = sme->next)
292       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
293         return sme->value;
294   }
295   else
296   {
297     struct BigMapEntry *bme;
298
299     for (bme = me.bme; NULL != bme; bme = bme->next)
300       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
301         return bme->value;
302   }
303   return NULL;
304 }
305
306
307 /**
308  * Iterate over all entries in the map.
309  *
310  * @param map the map
311  * @param it function to call on each entry
312  * @param it_cls extra argument to @a it
313  * @return the number of key value pairs processed,
314  *         #GNUNET_SYSERR if it aborted iteration
315  */
316 int
317 GNUNET_CONTAINER_multipeermap_iterate (const struct
318                                        GNUNET_CONTAINER_MultiPeerMap *map,
319                                        GNUNET_CONTAINER_PeerMapIterator it,
320                                        void *it_cls)
321 {
322   int count;
323   unsigned int i;
324   union MapEntry me;
325   struct GNUNET_PeerIdentity kc;
326
327   count = 0;
328   GNUNET_assert (NULL != map);
329   for (i = 0; i < map->map_length; i++)
330   {
331     me = map->map[i];
332     if (map->use_small_entries)
333     {
334       struct SmallMapEntry *sme;
335       struct SmallMapEntry *nxt;
336
337       nxt = me.sme;
338       while (NULL != (sme = nxt))
339       {
340         nxt = sme->next;
341         if (NULL != it)
342         {
343           if (GNUNET_OK != it (it_cls, sme->key, sme->value))
344             return GNUNET_SYSERR;
345         }
346         count++;
347       }
348     }
349     else
350     {
351       struct BigMapEntry *bme;
352       struct BigMapEntry *nxt;
353
354       nxt = me.bme;
355       while (NULL != (bme = nxt))
356       {
357         nxt = bme->next;
358         if (NULL != it)
359         {
360           kc = bme->key;
361           if (GNUNET_OK != it (it_cls, &kc, bme->value))
362             return GNUNET_SYSERR;
363         }
364         count++;
365       }
366     }
367   }
368   return count;
369 }
370
371
372 /**
373  * Remove the given key-value pair from the map.  Note that if the
374  * key-value pair is in the map multiple times, only one of the pairs
375  * will be removed.
376  *
377  * @param map the map
378  * @param key key of the key-value pair
379  * @param value value of the key-value pair
380  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
381  *  is not in the map
382  */
383 int
384 GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
385                                       const struct GNUNET_PeerIdentity *key,
386                                       const void *value)
387 {
388   union MapEntry me;
389   unsigned int i;
390
391   map->modification_counter++;
392
393   i = idx_of (map, key);
394   me = map->map[i];
395   if (map->use_small_entries)
396   {
397     struct SmallMapEntry *sme;
398     struct SmallMapEntry *p;
399
400     p = NULL;
401     for (sme = me.sme; NULL != sme; sme = sme->next)
402     {
403       if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) &&
404           (value == sme->value))
405       {
406         if (NULL == p)
407           map->map[i].sme = sme->next;
408         else
409           p->next = sme->next;
410         GNUNET_free (sme);
411         map->size--;
412         return GNUNET_YES;
413       }
414       p = sme;
415     }
416   }
417   else
418   {
419     struct BigMapEntry *bme;
420     struct BigMapEntry *p;
421
422     p = NULL;
423     for (bme = me.bme; NULL != bme; bme = bme->next)
424     {
425       if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) &&
426           (value == bme->value))
427       {
428         if (NULL == p)
429           map->map[i].bme = bme->next;
430         else
431           p->next = bme->next;
432         GNUNET_free (bme);
433         map->size--;
434         return GNUNET_YES;
435       }
436       p = bme;
437     }
438   }
439   return GNUNET_NO;
440 }
441
442
443 /**
444  * Remove all entries for the given key from the map.
445  * Note that the values would not be "freed".
446  *
447  * @param map the map
448  * @param key identifies values to be removed
449  * @return number of values removed
450  */
451 int
452 GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap
453                                           *map, const struct GNUNET_PeerIdentity *key)
454 {
455   union MapEntry me;
456   unsigned int i;
457   int ret;
458
459   map->modification_counter++;
460
461   ret = 0;
462   i = idx_of (map, key);
463   me = map->map[i];
464   if (map->use_small_entries)
465   {
466     struct SmallMapEntry *sme;
467     struct SmallMapEntry *p;
468
469     p = NULL;
470     sme = me.sme;
471     while (NULL != sme)
472     {
473       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
474       {
475         if (NULL == p)
476           map->map[i].sme = sme->next;
477         else
478           p->next = sme->next;
479         GNUNET_free (sme);
480         map->size--;
481         if (NULL == p)
482           sme = map->map[i].sme;
483         else
484           sme = p->next;
485         ret++;
486       }
487       else
488       {
489         p = sme;
490         sme = sme->next;
491       }
492     }
493   }
494   else
495   {
496     struct BigMapEntry *bme;
497     struct BigMapEntry *p;
498
499     p = NULL;
500     bme = me.bme;
501     while (NULL != bme)
502     {
503       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
504       {
505         if (NULL == p)
506           map->map[i].bme = bme->next;
507         else
508           p->next = bme->next;
509         GNUNET_free (bme);
510         map->size--;
511         if (NULL == p)
512           bme = map->map[i].bme;
513         else
514           bme = p->next;
515         ret++;
516       }
517       else
518       {
519         p = bme;
520         bme = bme->next;
521       }
522     }
523   }
524   return ret;
525 }
526
527
528 /**
529  * Check if the map contains any value under the given
530  * key (including values that are NULL).
531  *
532  * @param map the map
533  * @param key the key to test if a value exists for it
534  * @return GNUNET_YES if such a value exists,
535  *         GNUNET_NO if not
536  */
537 int
538 GNUNET_CONTAINER_multipeermap_contains (const struct
539                                         GNUNET_CONTAINER_MultiPeerMap *map,
540                                         const struct GNUNET_PeerIdentity *key)
541 {
542   union MapEntry me;
543
544   me = map->map[idx_of (map, key)];
545   if (map->use_small_entries)
546   {
547     struct SmallMapEntry *sme;
548
549     for (sme = me.sme; NULL != sme; sme = sme->next)
550       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
551         return GNUNET_YES;
552   }
553   else
554   {
555     struct BigMapEntry *bme;
556
557     for (bme = me.bme; NULL != bme; bme = bme->next)
558       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
559         return GNUNET_YES;
560   }
561   return GNUNET_NO;
562 }
563
564
565 /**
566  * Check if the map contains the given value under the given
567  * key.
568  *
569  * @param map the map
570  * @param key the key to test if a value exists for it
571  * @param value value to test for
572  * @return GNUNET_YES if such a value exists,
573  *         GNUNET_NO if not
574  */
575 int
576 GNUNET_CONTAINER_multipeermap_contains_value (const struct
577                                               GNUNET_CONTAINER_MultiPeerMap
578                                               *map, const struct GNUNET_PeerIdentity *key,
579                                               const void *value)
580 {
581   union MapEntry me;
582
583   me = map->map[idx_of (map, key)];
584   if (map->use_small_entries)
585   {
586     struct SmallMapEntry *sme;
587
588     for (sme = me.sme; NULL != sme; sme = sme->next)
589       if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) &&
590            (sme->value == value) )
591         return GNUNET_YES;
592   }
593   else
594   {
595     struct BigMapEntry *bme;
596
597     for (bme = me.bme; NULL != bme; bme = bme->next)
598       if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) &&
599            (bme->value == value) )
600         return GNUNET_YES;
601   }
602   return GNUNET_NO;
603 }
604
605
606 /**
607  * Grow the given map to a more appropriate size.
608  *
609  * @param map the hash map to grow
610  */
611 static void
612 grow (struct GNUNET_CONTAINER_MultiPeerMap *map)
613 {
614   union MapEntry *old_map;
615   union MapEntry *new_map;
616   unsigned int old_len;
617   unsigned int new_len;
618   unsigned int idx;
619   unsigned int i;
620
621   map->modification_counter++;
622
623   old_map = map->map;
624   old_len = map->map_length;
625   new_len = old_len * 2;
626   new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len);
627   map->map_length = new_len;
628   map->map = new_map;
629   for (i = 0; i < old_len; i++)
630   {
631     if (map->use_small_entries)
632     {
633       struct SmallMapEntry *sme;
634
635       while (NULL != (sme = old_map[i].sme))
636       {
637         old_map[i].sme = sme->next;
638         idx = idx_of (map, sme->key);
639         sme->next = new_map[idx].sme;
640         new_map[idx].sme = sme;
641       }
642     }
643     else
644     {
645       struct BigMapEntry *bme;
646
647       while (NULL != (bme = old_map[i].bme))
648       {
649         old_map[i].bme = bme->next;
650         idx = idx_of (map, &bme->key);
651         bme->next = new_map[idx].bme;
652         new_map[idx].bme = bme;
653       }
654     }
655   }
656   GNUNET_free (old_map);
657 }
658
659
660 /**
661  * Store a key-value pair in the map.
662  *
663  * @param map the map
664  * @param key key to use
665  * @param value value to use
666  * @param opt options for put
667  * @return #GNUNET_OK on success,
668  *         #GNUNET_NO if a value was replaced (with REPLACE)
669  *         #GNUNET_SYSERR if GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
670  *                       value already exists
671  */
672 int
673 GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map,
674                                    const struct GNUNET_PeerIdentity *key,
675                                    void *value,
676                                    enum GNUNET_CONTAINER_MultiHashMapOption opt)
677 {
678   union MapEntry me;
679   unsigned int i;
680
681   i = idx_of (map, key);
682   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
683       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
684   {
685     me = map->map[i];
686     if (map->use_small_entries)
687     {
688       struct SmallMapEntry *sme;
689
690       for (sme = me.sme; NULL != sme; sme = sme->next)
691         if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
692         {
693           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
694             return GNUNET_SYSERR;
695           sme->value = value;
696           return GNUNET_NO;
697         }
698     }
699     else
700     {
701       struct BigMapEntry *bme;
702
703       for (bme = me.bme; NULL != bme; bme = bme->next)
704         if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
705         {
706           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
707             return GNUNET_SYSERR;
708           bme->value = value;
709           return GNUNET_NO;
710         }
711     }
712   }
713   if (map->size / 3 >= map->map_length / 4)
714   {
715     grow (map);
716     i = idx_of (map, key);
717   }
718   if (map->use_small_entries)
719   {
720     struct SmallMapEntry *sme;
721
722     sme = GNUNET_new (struct SmallMapEntry);
723     sme->key = key;
724     sme->value = value;
725     sme->next = map->map[i].sme;
726     map->map[i].sme = sme;
727   }
728   else
729   {
730     struct BigMapEntry *bme;
731
732     bme = GNUNET_new (struct BigMapEntry);
733     bme->key = *key;
734     bme->value = value;
735     bme->next = map->map[i].bme;
736     map->map[i].bme = bme;
737   }
738   map->size++;
739   return GNUNET_OK;
740 }
741
742
743 /**
744  * Iterate over all entries in the map that match a particular key.
745  *
746  * @param map the map
747  * @param key key that the entries must correspond to
748  * @param it function to call on each entry
749  * @param it_cls extra argument to @a it
750  * @return the number of key value pairs processed,
751  *         #GNUNET_SYSERR if it aborted iteration
752  */
753 int
754 GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map,
755                                             const struct GNUNET_PeerIdentity *key,
756                                             GNUNET_CONTAINER_PeerMapIterator it,
757                                             void *it_cls)
758 {
759   int count;
760   union MapEntry me;
761
762   count = 0;
763   me = map->map[idx_of (map, key)];
764   if (map->use_small_entries)
765   {
766     struct SmallMapEntry *sme;
767     struct SmallMapEntry *nxt;
768
769     nxt = me.sme;
770     while (NULL != (sme = nxt))
771     {
772       nxt = sme->next;
773       if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
774         continue;
775       if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value)))
776         return GNUNET_SYSERR;
777       count++;
778     }
779   }
780   else
781   {
782     struct BigMapEntry *bme;
783     struct BigMapEntry *nxt;
784
785     nxt = me.bme;
786     while (NULL != (bme = nxt))
787     {
788       nxt = bme->next;
789       if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
790         continue;
791       if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value)))
792         return GNUNET_SYSERR;
793       count++;
794     }
795   }
796   return count;
797 }
798
799
800 /**
801  * @ingroup hashmap
802  * Call @a it on a random value from the map, or not at all
803  * if the map is empty.  Note that this function has linear
804  * complexity (in the size of the map).
805  *
806  * @param map the map
807  * @param it function to call on a random entry
808  * @param it_cls extra argument to @a it
809  * @return the number of key value pairs processed, zero or one.
810  */
811 unsigned int
812 GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map,
813                                           GNUNET_CONTAINER_PeerMapIterator it,
814                                           void *it_cls)
815 {
816   unsigned int off;
817   unsigned int idx;
818   union MapEntry me;
819
820   if (0 == map->size)
821     return 0;
822   if (NULL == it)
823     return 1;
824   off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
825                                   map->size);
826   for (idx = 0; idx < map->map_length; idx++)
827   {
828     me = map->map[idx];
829     if (map->use_small_entries)
830     {
831       struct SmallMapEntry *sme;
832       struct SmallMapEntry *nxt;
833
834       nxt = me.sme;
835       while (NULL != (sme = nxt))
836       {
837         nxt = sme->next;
838         if (0 == off)
839         {
840           if (GNUNET_OK != it (it_cls,
841                                sme->key,
842                                sme->value))
843             return GNUNET_SYSERR;
844           return 1;
845         }
846         off--;
847       }
848     }
849     else
850     {
851       struct BigMapEntry *bme;
852       struct BigMapEntry *nxt;
853
854       nxt = me.bme;
855       while (NULL != (bme = nxt))
856       {
857         nxt = bme->next;
858         if (0 == off)
859         {
860           if (GNUNET_OK != it (it_cls,
861                                &bme->key, bme->value))
862             return GNUNET_SYSERR;
863           return 1;
864         }
865         off--;
866       }
867     }
868   }
869   GNUNET_break (0);
870   return GNUNET_SYSERR;
871 }
872
873
874 /**
875  * Create an iterator for a multipeermap.
876  * The iterator can be used to retrieve all the elements in the multipeermap
877  * one by one, without having to handle all elements at once (in contrast to
878  * #GNUNET_CONTAINER_multipeermap_iterate).  Note that the iterator can not be
879  * used anymore if elements have been removed from 'map' after the creation of
880  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
881  * result in skipped or repeated elements.
882  *
883  * @param map the map to create an iterator for
884  * @return an iterator over the given multipeermap 'map'
885  */
886 struct GNUNET_CONTAINER_MultiPeerMapIterator *
887 GNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map)
888 {
889   struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
890
891   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMapIterator);
892   iter->map = map;
893   iter->modification_counter = map->modification_counter;
894   iter->me = map->map[0];
895   return iter;
896 }
897
898
899 /**
900  * Retrieve the next element from the hash map at the iterator's position.
901  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
902  * are not modified.
903  * This operation is only allowed if no elements have been removed from the
904  * multipeermap since the creation of 'iter', and the map has not been destroyed.
905  * Adding elements may result in repeating or skipping elements.
906  *
907  * @param iter the iterator to get the next element from
908  * @param key pointer to store the key in, can be NULL
909  * @param value pointer to store the value in, can be NULL
910  * @return #GNUNET_YES we returned an element,
911  *         #GNUNET_NO if we are out of elements
912  */
913 int
914 GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
915                                              struct GNUNET_PeerIdentity *key, const void **value)
916 {
917   /* make sure the map has not been modified */
918   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
919
920   /* look for the next entry, skipping empty buckets */
921   while (1)
922   {
923     if (iter->idx >= iter->map->map_length)
924       return GNUNET_NO;
925     if (GNUNET_YES == iter->map->use_small_entries)
926     {
927       if (NULL != iter->me.sme)
928       {
929         if (NULL != key)
930           *key = *iter->me.sme->key;
931         if (NULL != value)
932           *value = iter->me.sme->value;
933         iter->me.sme = iter->me.sme->next;
934         return GNUNET_YES;
935       }
936     }
937     else
938     {
939       if (NULL != iter->me.bme)
940       {
941         if (NULL != key)
942           *key = iter->me.bme->key;
943         if (NULL != value)
944           *value = iter->me.bme->value;
945         iter->me.bme = iter->me.bme->next;
946         return GNUNET_YES;
947       }
948     }
949     iter->idx += 1;
950     if (iter->idx < iter->map->map_length)
951       iter->me = iter->map->map[iter->idx];
952   }
953 }
954
955
956 /**
957  * Destroy a multipeermap iterator.
958  *
959  * @param iter the iterator to destroy
960  */
961 void
962 GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter)
963 {
964   GNUNET_free (iter);
965 }
966
967
968 /* end of container_multipeermap.c */