fix assertion failure reported in #5578
[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 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_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  * 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  * An entry in the hash map with the full key.
41  */
42 struct BigMapEntry
43 {
44
45   /**
46    * Value of the entry.
47    */
48   void *value;
49
50   /**
51    * If there is a hash collision, we create a linked list.
52    */
53   struct BigMapEntry *next;
54
55   /**
56    * Key for the entry.
57    */
58   struct GNUNET_PeerIdentity key;
59
60 };
61
62
63 /**
64  * An entry in the hash map with just a pointer to the key.
65  */
66 struct SmallMapEntry
67 {
68
69   /**
70    * Value of the entry.
71    */
72   void *value;
73
74   /**
75    * If there is a hash collision, we create a linked list.
76    */
77   struct SmallMapEntry *next;
78
79   /**
80    * Key for the entry.
81    */
82   const struct GNUNET_PeerIdentity *key;
83
84 };
85
86
87 /**
88  * Entry in the map.
89  */
90 union MapEntry
91 {
92   /**
93    * Variant used if map entries only contain a pointer to the key.
94    */
95   struct SmallMapEntry *sme;
96
97   /**
98    * Variant used if map entries contain the full key.
99    */
100   struct BigMapEntry *bme;
101 };
102
103
104 /**
105  * Internal representation of the hash map.
106  */
107 struct GNUNET_CONTAINER_MultiPeerMap
108 {
109   /**
110    * All of our buckets.
111    */
112   union MapEntry *map;
113
114   /**
115    * Number of entries in the map.
116    */
117   unsigned int size;
118
119   /**
120    * Length of the "map" array.
121    */
122   unsigned int map_length;
123
124   /**
125    * #GNUNET_NO if the map entries are of type 'struct BigMapEntry',
126    * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'.
127    */
128   int use_small_entries;
129
130   /**
131    * Counts the destructive modifications (grow, remove)
132    * to the map, so that iterators can check if they are still valid.
133    */
134   unsigned int modification_counter;
135
136   /**
137    * Map entries indicating iteration positions currently
138    * in use by #GNUNET_CONTAINER_multihashmap_get_multiple().
139    * Only used up to @e next_cache_off.
140    */
141   union MapEntry next_cache[NEXT_CACHE_SIZE];
142
143   /**
144    * Offset of @e next_cache entries in use, must be smaller
145    * than #NEXT_CACHE_SIZE.
146    */
147   unsigned int next_cache_off;
148 };
149
150
151 /**
152  * Cursor into a multipeermap.
153  * Allows to enumerate elements asynchronously.
154  */
155 struct GNUNET_CONTAINER_MultiPeerMapIterator
156 {
157   /**
158    * Position in the bucket 'idx'
159    */
160   union MapEntry me;
161
162   /**
163    * Current bucket index.
164    */
165   unsigned int idx;
166
167   /**
168    * Modification counter as observed on the map when the iterator
169    * was created.
170    */
171   unsigned int modification_counter;
172
173   /**
174    * Map that we are iterating over.
175    */
176   const struct GNUNET_CONTAINER_MultiPeerMap *map;
177 };
178
179
180 /**
181  * Create a multi hash map.
182  *
183  * @param len initial size (map will grow as needed)
184  * @param do_not_copy_keys GNUNET_NO is always safe and should be used by default;
185  *                         GNUNET_YES means that on 'put', the 'key' does not have
186  *                         to be copied as the destination of the pointer is
187  *                         guaranteed to be life as long as the value is stored in
188  *                         the hashmap.  This can significantly reduce memory
189  *                         consumption, but of course is also a recipie for
190  *                         heap corruption if the assumption is not true.  Only
191  *                         use this if (1) memory use is important in this case and
192  *                         (2) you have triple-checked that the invariant holds
193  * @return NULL on error
194  */
195 struct GNUNET_CONTAINER_MultiPeerMap *
196 GNUNET_CONTAINER_multipeermap_create (unsigned int len,
197                                       int do_not_copy_keys)
198 {
199   struct GNUNET_CONTAINER_MultiPeerMap *map;
200
201   GNUNET_assert (len > 0);
202   map = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMap);
203   map->map = GNUNET_new_array (len,
204                                union MapEntry);
205   map->map_length = len;
206   map->use_small_entries = do_not_copy_keys;
207   return map;
208 }
209
210
211 /**
212  * Destroy a hash map.  Will not free any values
213  * stored in the hash map!
214  *
215  * @param map the map
216  */
217 void
218 GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map)
219 {
220   GNUNET_assert (0 == map->next_cache_off);
221   for (unsigned int i = 0; i < map->map_length; i++)
222   {
223     union MapEntry me;
224
225     me = map->map[i];
226     if (map->use_small_entries)
227     {
228       struct SmallMapEntry *sme;
229       struct SmallMapEntry *nxt;
230
231       nxt = me.sme;
232       while (NULL != (sme = nxt))
233       {
234         nxt = sme->next;
235         GNUNET_free (sme);
236       }
237       me.sme = NULL;
238     }
239     else
240     {
241       struct BigMapEntry *bme;
242       struct BigMapEntry *nxt;
243
244       nxt = me.bme;
245       while (NULL != (bme = nxt))
246       {
247         nxt = bme->next;
248         GNUNET_free (bme);
249       }
250       me.bme = NULL;
251     }
252   }
253   GNUNET_free (map->map);
254   GNUNET_free (map);
255 }
256
257
258 /**
259  * Compute the index of the bucket for the given key.
260  *
261  * @param map hash map for which to compute the index
262  * @param key what key should the index be computed for
263  * @return offset into the "map" array of "map"
264  */
265 static unsigned int
266 idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map,
267         const struct GNUNET_PeerIdentity *key)
268 {
269   unsigned int kx;
270
271   GNUNET_assert (NULL != map);
272   GNUNET_memcpy (&kx,
273                  key,
274                  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_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *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_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map,
304                                    const struct GNUNET_PeerIdentity *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_PeerIdentity)))
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_PeerIdentity)))
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_multipeermap_iterate (struct GNUNET_CONTAINER_MultiPeerMap *map,
340                                        GNUNET_CONTAINER_PeerMapIterator it,
341                                        void *it_cls)
342 {
343   int count;
344   union MapEntry me;
345   union MapEntry *ce;
346   struct GNUNET_PeerIdentity 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         {
365           if (GNUNET_OK != it (it_cls,
366                                sme->key,
367                                sme->value))
368           {
369             GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
370             return GNUNET_SYSERR;
371           }
372         }
373         count++;
374       }
375     }
376     else
377     {
378       struct BigMapEntry *bme;
379
380       ce->bme = me.bme;
381       while (NULL != (bme = ce->bme))
382       {
383         ce->bme = bme->next;
384         if (NULL != it)
385         {
386           kc = bme->key;
387           if (GNUNET_OK != it (it_cls,
388                                &kc,
389                                bme->value))
390           {
391             GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
392             return GNUNET_SYSERR;
393           }
394         }
395         count++;
396       }
397     }
398   }
399   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
400   return count;
401 }
402
403
404 /**
405  * We are about to free() the @a bme, make sure it is not in
406  * the list of next values for any iterator in the @a map's next_cache.
407  *
408  * @param map the map to check
409  * @param bme the entry that is about to be free'd
410  */
411 static void
412 update_next_cache_bme (struct GNUNET_CONTAINER_MultiPeerMap *map,
413                        const struct BigMapEntry *bme)
414 {
415   for (unsigned int i=0;i<map->next_cache_off;i++)
416     if (map->next_cache[i].bme == bme)
417       map->next_cache[i].bme = bme->next;
418 }
419
420
421 /**
422  * We are about to free() the @a sme, make sure it is not in
423  * the list of next values for any iterator in the @a map's next_cache.
424  *
425  * @param map the map to check
426  * @param sme the entry that is about to be free'd
427  */
428 static void
429 update_next_cache_sme (struct GNUNET_CONTAINER_MultiPeerMap *map,
430                        const struct SmallMapEntry *sme)
431 {
432   for (unsigned int i=0;i<map->next_cache_off;i++)
433     if (map->next_cache[i].sme == sme)
434       map->next_cache[i].sme = sme->next;
435 }
436
437
438 /**
439  * Remove the given key-value pair from the map.  Note that if the
440  * key-value pair is in the map multiple times, only one of the pairs
441  * will be removed.
442  *
443  * @param map the map
444  * @param key key of the key-value pair
445  * @param value value of the key-value pair
446  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
447  *  is not in the map
448  */
449 int
450 GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
451                                       const struct GNUNET_PeerIdentity *key,
452                                       const void *value)
453 {
454   union MapEntry me;
455   unsigned int i;
456
457   map->modification_counter++;
458   i = idx_of (map, key);
459   me = map->map[i];
460   if (map->use_small_entries)
461   {
462     struct SmallMapEntry *p = NULL;
463
464     for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
465     {
466       if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) &&
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_PeerIdentity))) &&
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_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map,
520                                           const struct GNUNET_PeerIdentity *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,
541                        sme->key,
542                        sizeof (struct GNUNET_PeerIdentity)))
543       {
544         if (NULL == p)
545           map->map[i].sme = sme->next;
546         else
547           p->next = sme->next;
548         update_next_cache_sme (map,
549                                sme);
550         GNUNET_free (sme);
551         map->size--;
552         if (NULL == p)
553           sme = map->map[i].sme;
554         else
555           sme = p->next;
556         ret++;
557       }
558       else
559       {
560         p = sme;
561         sme = sme->next;
562       }
563     }
564   }
565   else
566   {
567     struct BigMapEntry *bme;
568     struct BigMapEntry *p;
569
570     p = NULL;
571     bme = me.bme;
572     while (NULL != bme)
573     {
574       if (0 == memcmp (key,
575                        &bme->key,
576                        sizeof (struct GNUNET_PeerIdentity)))
577       {
578         if (NULL == p)
579           map->map[i].bme = bme->next;
580         else
581           p->next = bme->next;
582         update_next_cache_bme (map,
583                                bme);
584         GNUNET_free (bme);
585         map->size--;
586         if (NULL == p)
587           bme = map->map[i].bme;
588         else
589           bme = p->next;
590         ret++;
591       }
592       else
593       {
594         p = bme;
595         bme = bme->next;
596       }
597     }
598   }
599   return ret;
600 }
601
602
603 /**
604  * Check if the map contains any value under the given
605  * key (including values that are NULL).
606  *
607  * @param map the map
608  * @param key the key to test if a value exists for it
609  * @return #GNUNET_YES if such a value exists,
610  *         #GNUNET_NO if not
611  */
612 int
613 GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map,
614                                         const struct GNUNET_PeerIdentity *key)
615 {
616   union MapEntry me;
617
618   me = map->map[idx_of (map, key)];
619   if (map->use_small_entries)
620   {
621     for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
622       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
623         return GNUNET_YES;
624   }
625   else
626   {
627     for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
628       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
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_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map,
647                                               const struct GNUNET_PeerIdentity *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_PeerIdentity))) &&
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_PeerIdentity))) &&
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_MultiPeerMap *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   unsigned int i;
689
690   map->modification_counter++;
691
692   old_map = map->map;
693   old_len = map->map_length;
694   new_len = old_len * 2;
695   new_map = GNUNET_new_array (new_len,
696                               union MapEntry);
697   map->map_length = new_len;
698   map->map = new_map;
699   for (i = 0; i < old_len; i++)
700   {
701     if (map->use_small_entries)
702     {
703       struct SmallMapEntry *sme;
704
705       while (NULL != (sme = old_map[i].sme))
706       {
707         old_map[i].sme = sme->next;
708         idx = idx_of (map, sme->key);
709         sme->next = new_map[idx].sme;
710         new_map[idx].sme = sme;
711       }
712     }
713     else
714     {
715       struct BigMapEntry *bme;
716
717       while (NULL != (bme = old_map[i].bme))
718       {
719         old_map[i].bme = bme->next;
720         idx = idx_of (map, &bme->key);
721         bme->next = new_map[idx].bme;
722         new_map[idx].bme = bme;
723       }
724     }
725   }
726   GNUNET_free (old_map);
727 }
728
729
730 /**
731  * Store a key-value pair in the map.
732  *
733  * @param map the map
734  * @param key key to use
735  * @param value value to use
736  * @param opt options for put
737  * @return #GNUNET_OK on success,
738  *         #GNUNET_NO if a value was replaced (with REPLACE)
739  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
740  *                       value already exists
741  */
742 int
743 GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map,
744                                    const struct GNUNET_PeerIdentity *key,
745                                    void *value,
746                                    enum GNUNET_CONTAINER_MultiHashMapOption opt)
747 {
748   union MapEntry me;
749   unsigned int i;
750
751   i = idx_of (map, key);
752   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
753       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
754   {
755     me = map->map[i];
756     if (map->use_small_entries)
757     {
758       struct SmallMapEntry *sme;
759
760       for (sme = me.sme; NULL != sme; sme = sme->next)
761         if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
762         {
763           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
764             return GNUNET_SYSERR;
765           sme->value = value;
766           return GNUNET_NO;
767         }
768     }
769     else
770     {
771       struct BigMapEntry *bme;
772
773       for (bme = me.bme; NULL != bme; bme = bme->next)
774         if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
775         {
776           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
777             return GNUNET_SYSERR;
778           bme->value = value;
779           return GNUNET_NO;
780         }
781     }
782   }
783   if (map->size / 3 >= map->map_length / 4)
784   {
785     grow (map);
786     i = idx_of (map, key);
787   }
788   if (map->use_small_entries)
789   {
790     struct SmallMapEntry *sme;
791
792     sme = GNUNET_new (struct SmallMapEntry);
793     sme->key = key;
794     sme->value = value;
795     sme->next = map->map[i].sme;
796     map->map[i].sme = sme;
797   }
798   else
799   {
800     struct BigMapEntry *bme;
801
802     bme = GNUNET_new (struct BigMapEntry);
803     bme->key = *key;
804     bme->value = value;
805     bme->next = map->map[i].bme;
806     map->map[i].bme = bme;
807   }
808   map->size++;
809   return GNUNET_OK;
810 }
811
812
813 /**
814  * Iterate over all entries in the map that match a particular key.
815  *
816  * @param map the map
817  * @param key key that the entries must correspond to
818  * @param it function to call on each entry
819  * @param it_cls extra argument to @a it
820  * @return the number of key value pairs processed,
821  *         #GNUNET_SYSERR if it aborted iteration
822  */
823 int
824 GNUNET_CONTAINER_multipeermap_get_multiple (struct GNUNET_CONTAINER_MultiPeerMap *map,
825                                             const struct GNUNET_PeerIdentity *key,
826                                             GNUNET_CONTAINER_PeerMapIterator it,
827                                             void *it_cls)
828 {
829   int count;
830   union MapEntry me;
831   union MapEntry *ce;
832   
833   ce = &map->next_cache[map->next_cache_off];
834   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
835   count = 0;
836   me = map->map[idx_of (map, key)];
837   if (map->use_small_entries)
838   {
839     struct SmallMapEntry *sme;
840
841     ce->sme = me.sme;
842     while (NULL != (sme = ce->sme))
843     {
844       ce->sme = sme->next;
845       if (0 != memcmp (key,
846                        sme->key,
847                        sizeof (struct GNUNET_PeerIdentity)))
848         continue;
849       if ( (NULL != it) &&
850            (GNUNET_OK != it (it_cls,
851                              key,
852                              sme->value)))
853       {
854         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
855         return GNUNET_SYSERR;
856       }
857       count++;
858     }
859   }
860   else
861   {
862     struct BigMapEntry *bme;
863
864     ce->bme = me.bme;
865     while (NULL != (bme = ce->bme))
866     {
867       ce->bme = bme->next;
868       if (0 != memcmp (key,
869                        &bme->key,
870                        sizeof (struct GNUNET_PeerIdentity)))
871         continue;
872       if ( (NULL != it) &&
873            (GNUNET_OK != it (it_cls,
874                              key,
875                              bme->value)))
876       {
877         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
878         return GNUNET_SYSERR;
879       }
880       count++;
881     }
882   }
883   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
884   return count;
885 }
886
887
888 /**
889  * @ingroup hashmap
890  * Call @a it on a random value from the map, or not at all
891  * if the map is empty.  Note that this function has linear
892  * complexity (in the size of the map).
893  *
894  * @param map the map
895  * @param it function to call on a random entry
896  * @param it_cls extra argument to @a it
897  * @return the number of key value pairs processed, zero or one.
898  */
899 unsigned int
900 GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map,
901                                           GNUNET_CONTAINER_PeerMapIterator it,
902                                           void *it_cls)
903 {
904   unsigned int off;
905   union MapEntry me;
906   
907   if (0 == map->size)
908     return 0;
909   if (NULL == it)
910     return 1;
911   off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
912                                   map->size);
913   for (unsigned int idx = 0; idx < map->map_length; idx++)
914   {
915     me = map->map[idx];
916     if (map->use_small_entries)
917     {
918       struct SmallMapEntry *sme;
919       struct SmallMapEntry *nxt;
920
921       nxt = me.sme;
922       while (NULL != (sme = nxt))
923       {
924         nxt = sme->next;
925         if (0 == off)
926         {
927           if (GNUNET_OK != it (it_cls,
928                                sme->key,
929                                sme->value))
930             return GNUNET_SYSERR;
931           return 1;
932         }
933         off--;
934       }
935     }
936     else
937     {
938       struct BigMapEntry *bme;
939       struct BigMapEntry *nxt;
940
941       nxt = me.bme;
942       while (NULL != (bme = nxt))
943       {
944         nxt = bme->next;
945         if (0 == off)
946         {
947           if (GNUNET_OK != it (it_cls,
948                                &bme->key,
949                                bme->value))
950             return GNUNET_SYSERR;
951           return 1;
952         }
953         off--;
954       }
955     }
956   }
957   GNUNET_break (0);
958   return GNUNET_SYSERR;
959 }
960
961
962 /**
963  * Create an iterator for a multipeermap.
964  * The iterator can be used to retrieve all the elements in the multipeermap
965  * one by one, without having to handle all elements at once (in contrast to
966  * #GNUNET_CONTAINER_multipeermap_iterate).  Note that the iterator can not be
967  * used anymore if elements have been removed from 'map' after the creation of
968  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
969  * result in skipped or repeated elements.
970  *
971  * @param map the map to create an iterator for
972  * @return an iterator over the given multipeermap 'map'
973  */
974 struct GNUNET_CONTAINER_MultiPeerMapIterator *
975 GNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map)
976 {
977   struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
978
979   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMapIterator);
980   iter->map = map;
981   iter->modification_counter = map->modification_counter;
982   iter->me = map->map[0];
983   return iter;
984 }
985
986
987 /**
988  * Retrieve the next element from the hash map at the iterator's position.
989  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
990  * are not modified.
991  * This operation is only allowed if no elements have been removed from the
992  * multipeermap since the creation of 'iter', and the map has not been destroyed.
993  * Adding elements may result in repeating or skipping elements.
994  *
995  * @param iter the iterator to get the next element from
996  * @param key pointer to store the key in, can be NULL
997  * @param value pointer to store the value in, can be NULL
998  * @return #GNUNET_YES we returned an element,
999  *         #GNUNET_NO if we are out of elements
1000  */
1001 int
1002 GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
1003                                              struct GNUNET_PeerIdentity *key, const void **value)
1004 {
1005   /* make sure the map has not been modified */
1006   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
1007
1008   /* look for the next entry, skipping empty buckets */
1009   while (1)
1010   {
1011     if (iter->idx >= iter->map->map_length)
1012       return GNUNET_NO;
1013     if (GNUNET_YES == iter->map->use_small_entries)
1014     {
1015       if (NULL != iter->me.sme)
1016       {
1017         if (NULL != key)
1018           *key = *iter->me.sme->key;
1019         if (NULL != value)
1020           *value = iter->me.sme->value;
1021         iter->me.sme = iter->me.sme->next;
1022         return GNUNET_YES;
1023       }
1024     }
1025     else
1026     {
1027       if (NULL != iter->me.bme)
1028       {
1029         if (NULL != key)
1030           *key = iter->me.bme->key;
1031         if (NULL != value)
1032           *value = iter->me.bme->value;
1033         iter->me.bme = iter->me.bme->next;
1034         return GNUNET_YES;
1035       }
1036     }
1037     iter->idx += 1;
1038     if (iter->idx < iter->map->map_length)
1039       iter->me = iter->map->map[iter->idx];
1040   }
1041 }
1042
1043
1044 /**
1045  * Destroy a multipeermap iterator.
1046  *
1047  * @param iter the iterator to destroy
1048  */
1049 void
1050 GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter)
1051 {
1052   GNUNET_free (iter);
1053 }
1054
1055
1056 /* end of container_multipeermap.c */