src/util/container_multihashmap.c

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