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