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", __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 */