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