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   old_map = map->map;
 768   old_len = map->map_length;
 769   GNUNET_assert (0 != old_len);
 770   new_len = old_len * 2;
 771   if (0 == new_len) /* 2^31 * 2 == 0 */
 772     new_len = old_len; /* never use 0 */
 773   if (new_len == old_len)
 774     return; /* nothing changed */
 775   new_map = GNUNET_malloc_large (new_len *
 776                                  sizeof (union MapEntry));
 777   if (NULL == new_map)
 778     return; /* grow not possible */
 779   map->modification_counter++;
 780   map->map_length = new_len;
 781   map->map = new_map;
 782   for (unsigned int i = 0; i < old_len; i++)
 783   {
 784     if (map->use_small_entries)
 785     {
 786       struct SmallMapEntry *sme;
 787
 788       while (NULL != (sme = old_map[i].sme))
 789       {
 790         old_map[i].sme = sme->next;
 791         idx = idx_of (map, sme->key);
 792         sme->next = new_map[idx].sme;
 793         new_map[idx].sme = sme;
 794       }
 795     }
 796     else
 797     {
 798       struct BigMapEntry *bme;
 799
 800       while (NULL != (bme = old_map[i].bme))
 801       {
 802         old_map[i].bme = bme->next;
 803         idx = idx_of (map, &bme->key);
 804         bme->next = new_map[idx].bme;
 805         new_map[idx].bme = bme;
 806       }
 807     }
 808   }
 809   GNUNET_free (old_map);
 810 }
 811
 812
 813 /**
 814  * Store a key-value pair in the map.
 815  *
 816  * @param map the map
 817  * @param key key to use
 818  * @param value value to use
 819  * @param opt options for put
 820  * @return #GNUNET_OK on success,
 821  *         #GNUNET_NO if a value was replaced (with REPLACE)
 822  *         #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 823  *                       value already exists
 824  */
 825 int
 826 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
 827                                    const struct GNUNET_HashCode *key,
 828                                    void *value,
 829                                    enum GNUNET_CONTAINER_MultiHashMapOption opt)
 830 {
 831   union MapEntry me;
 832   unsigned int i;
 833
 834   i = idx_of (map, key);
 835   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 836       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 837   {
 838     me = map->map[i];
 839     if (map->use_small_entries)
 840     {
 841       struct SmallMapEntry *sme;
 842
 843       for (sme = me.sme; NULL != sme; sme = sme->next)
 844         if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
 845         {
 846           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 847             return GNUNET_SYSERR;
 848           sme->value = value;
 849           return GNUNET_NO;
 850         }
 851     }
 852     else
 853     {
 854       struct BigMapEntry *bme;
 855
 856       for (bme = me.bme; NULL != bme; bme = bme->next)
 857         if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
 858         {
 859           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 860             return GNUNET_SYSERR;
 861           bme->value = value;
 862           return GNUNET_NO;
 863         }
 864     }
 865   }
 866   if (map->size / 3 >= map->map_length / 4)
 867   {
 868     grow (map);
 869     i = idx_of (map, key);
 870   }
 871   if (map->use_small_entries)
 872   {
 873     struct SmallMapEntry *sme;
 874
 875     sme = GNUNET_new (struct SmallMapEntry);
 876     sme->key = key;
 877     sme->value = value;
 878     sme->next = map->map[i].sme;
 879     map->map[i].sme = sme;
 880   }
 881   else
 882   {
 883     struct BigMapEntry *bme;
 884
 885     bme = GNUNET_new (struct BigMapEntry);
 886     bme->key = *key;
 887     bme->value = value;
 888     bme->next = map->map[i].bme;
 889     map->map[i].bme = bme;
 890   }
 891   map->size++;
 892   return GNUNET_OK;
 893 }
 894
 895
 896 /**
 897  * Iterate over all entries in the map that match a particular key.
 898  *
 899  * @param map the map
 900  * @param key key that the entries must correspond to
 901  * @param it function to call on each entry
 902  * @param it_cls extra argument to it
 903  * @return the number of key value pairs processed,
 904  *         #GNUNET_SYSERR if it aborted iteration
 905  */
 906 int
 907 GNUNET_CONTAINER_multihashmap_get_multiple (struct GNUNET_CONTAINER_MultiHashMap *map,
 908                                             const struct GNUNET_HashCode *key,
 909                                             GNUNET_CONTAINER_HashMapIterator it,
 910                                             void *it_cls)
 911 {
 912   int count;
 913   union MapEntry *me;
 914   union MapEntry *ce;
 915
 916   ce = &map->next_cache[map->next_cache_off];
 917   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 918   count = 0;
 919   me = &map->map[idx_of (map, key)];
 920   if (map->use_small_entries)
 921   {
 922     struct SmallMapEntry *sme;
 923
 924     ce->sme = me->sme;
 925     while (NULL != (sme = ce->sme))
 926     {
 927       ce->sme = sme->next;
 928       if (0 != memcmp (key,
 929                        sme->key,
 930                        sizeof (struct GNUNET_HashCode)))
 931         continue;
 932       if ( (NULL != it) &&
 933            (GNUNET_OK != it (it_cls,
 934                              key,
 935                              sme->value)))
 936       {
 937         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 938         return GNUNET_SYSERR;
 939       }
 940       count++;
 941     }
 942   }
 943   else
 944   {
 945     struct BigMapEntry *bme;
 946
 947     ce->bme = me->bme;
 948     while (NULL != (bme = ce->bme))
 949     {
 950       ce->bme = bme->next;
 951       if (0 != memcmp (key,
 952                        &bme->key,
 953                        sizeof (struct GNUNET_HashCode)))
 954         continue;
 955       if ( (NULL != it) &&
 956            (GNUNET_OK != it (it_cls,
 957                              key,
 958                              bme->value)))
 959       {
 960         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 961         return GNUNET_SYSERR;
 962       }
 963       count++;
 964     }
 965   }
 966   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 967   return count;
 968 }
 969
 970
 971 /**
 972  * @ingroup hashmap
 973  * Call @a it on a random value from the map, or not at all
 974  * if the map is empty. Note that this function has linear
 975  * complexity (in the size of the map).
 976  *
 977  * @param map the map
 978  * @param it function to call on a random entry
 979  * @param it_cls extra argument to @a it
 980  * @return the number of key value pairs processed, zero or one.
 981  */
 982 unsigned int
 983 GNUNET_CONTAINER_multihashmap_get_random (const struct GNUNET_CONTAINER_MultiHashMap *map,
 984                                           GNUNET_CONTAINER_HashMapIterator it,
 985                                           void *it_cls)
 986 {
 987   unsigned int off;
 988   unsigned int idx;
 989   union MapEntry me;
 990
 991   if (0 == map->size)
 992     return 0;
 993   if (NULL == it)
 994     return 1;
 995   off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
 996                                   map->size);
 997   for (idx = 0; idx < map->map_length; idx++)
 998   {
 999     me = map->map[idx];
1000     if (map->use_small_entries)
1001     {
1002       struct SmallMapEntry *sme;
1003       struct SmallMapEntry *nxt;
1004
1005       nxt = me.sme;
1006       while (NULL != (sme = nxt))
1007       {
1008         nxt = sme->next;
1009         if (0 == off)
1010         {
1011           if (GNUNET_OK != it (it_cls,
1012                                sme->key,
1013                                sme->value))
1014             return GNUNET_SYSERR;
1015           return 1;
1016         }
1017         off--;
1018       }
1019     }
1020     else
1021     {
1022       struct BigMapEntry *bme;
1023       struct BigMapEntry *nxt;
1024
1025       nxt = me.bme;
1026       while (NULL != (bme = nxt))
1027       {
1028         nxt = bme->next;
1029         if (0 == off)
1030         {
1031           if (GNUNET_OK != it (it_cls,
1032                                &bme->key, bme->value))
1033             return GNUNET_SYSERR;
1034           return 1;
1035         }
1036         off--;
1037       }
1038     }
1039   }
1040   GNUNET_break (0);
1041   return GNUNET_SYSERR;
1042 }
1043
1044
1045 /**
1046  * Create an iterator for a multihashmap.
1047  * The iterator can be used to retrieve all the elements in the multihashmap
1048  * one by one, without having to handle all elements at once (in contrast to
1049  * GNUNET_CONTAINER_multihashmap_iterate()).  Note that the iterator can not be
1050  * used anymore if elements have been removed from 'map' after the creation of
1051  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
1052  * result in skipped or repeated elements.
1053  *
1054  * @param map the map to create an iterator for
1055  * @return an iterator over the given multihashmap 'map'
1056  */
1057 struct GNUNET_CONTAINER_MultiHashMapIterator *
1058 GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map)
1059 {
1060   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
1061
1062   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMapIterator);
1063   iter->map = map;
1064   iter->modification_counter = map->modification_counter;
1065   iter->me = map->map[0];
1066   return iter;
1067 }
1068
1069
1070 /**
1071  * Retrieve the next element from the hash map at the iterator's position.
1072  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
1073  * are not modified.
1074  * This operation is only allowed if no elements have been removed from the
1075  * multihashmap since the creation of 'iter', and the map has not been destroyed.
1076  * Adding elements may result in repeating or skipping elements.
1077  *
1078  * @param iter the iterator to get the next element from
1079  * @param key pointer to store the key in, can be NULL
1080  * @param value pointer to store the value in, can be NULL
1081  * @return #GNUNET_YES we returned an element,
1082  *         #GNUNET_NO if we are out of elements
1083  */
1084 int
1085 GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
1086                                              struct GNUNET_HashCode *key,
1087                                              const void **value)
1088 {
1089   /* make sure the map has not been modified */
1090   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
1091
1092   /* look for the next entry, skipping empty buckets */
1093   while (1)
1094   {
1095     if (iter->idx >= iter->map->map_length)
1096       return GNUNET_NO;
1097     if (GNUNET_YES == iter->map->use_small_entries)
1098     {
1099       if (NULL != iter->me.sme)
1100       {
1101         if (NULL != key)
1102           *key = *iter->me.sme->key;
1103         if (NULL != value)
1104           *value = iter->me.sme->value;
1105         iter->me.sme = iter->me.sme->next;
1106         return GNUNET_YES;
1107       }
1108     }
1109     else
1110     {
1111       if (NULL != iter->me.bme)
1112       {
1113         if (NULL != key)
1114           *key = iter->me.bme->key;
1115         if (NULL != value)
1116           *value = iter->me.bme->value;
1117         iter->me.bme = iter->me.bme->next;
1118         return GNUNET_YES;
1119       }
1120     }
1121     iter->idx += 1;
1122     if (iter->idx < iter->map->map_length)
1123       iter->me = iter->map->map[iter->idx];
1124   }
1125 }
1126
1127
1128 /**
1129  * Destroy a multihashmap iterator.
1130  *
1131  * @param iter the iterator to destroy
1132  */
1133 void
1134 GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
1135 {
1136   GNUNET_free (iter);
1137 }
1138
1139
1140 /* end of container_multihashmap.c */