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