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