src/util/container_multishortmap.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_multishortmap.c
  22  * @brief hash map where the same key may be present multiple times
  23  * @author Christian Grothoff
  24  */
  25
  26 #include "platform.h"
  27 #include "gnunet_util_lib.h"
  28
  29 #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multishortmap", __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_ShortHashCode 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_ShortHashCode *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_MultiShortmap
 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 /**
 154  * Cursor into a multishortmap.
 155  * Allows to enumerate elements asynchronously.
 156  */
 157 struct GNUNET_CONTAINER_MultiShortmapIterator
 158 {
 159   /**
 160    * Position in the bucket 'idx'
 161    */
 162   union MapEntry me;
 163
 164   /**
 165    * Current bucket index.
 166    */
 167   unsigned int idx;
 168
 169   /**
 170    * Modification counter as observed on the map when the iterator
 171    * was created.
 172    */
 173   unsigned int modification_counter;
 174
 175   /**
 176    * Map that we are iterating over.
 177    */
 178   const struct GNUNET_CONTAINER_MultiShortmap *map;
 179 };
 180
 181
 182 /**
 183  * Create a multi hash map.
 184  *
 185  * @param len initial size (map will grow as needed)
 186  * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
 187  *                         #GNUNET_YES means that on 'put', the 'key' does not have
 188  *                         to be copied as the destination of the pointer is
 189  *                         guaranteed to be life as long as the value is stored in
 190  *                         the hashmap.  This can significantly reduce memory
 191  *                         consumption, but of course is also a recipie for
 192  *                         heap corruption if the assumption is not true.  Only
 193  *                         use this if (1) memory use is important in this case and
 194  *                         (2) you have triple-checked that the invariant holds
 195  * @return NULL on error
 196  */
 197 struct GNUNET_CONTAINER_MultiShortmap *
 198 GNUNET_CONTAINER_multishortmap_create (unsigned int len,
 199                                       int do_not_copy_keys)
 200 {
 201   struct GNUNET_CONTAINER_MultiShortmap *map;
 202
 203   GNUNET_assert (len > 0);
 204   map = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmap);
 205   map->map = GNUNET_malloc_large (len *
 206                                   sizeof (union MapEntry));
 207   if (NULL == map->map)
 208   {
 209     GNUNET_free (map);
 210     return NULL;
 211   }
 212   map->map_length = len;
 213   map->use_small_entries = do_not_copy_keys;
 214   return map;
 215 }
 216
 217
 218 /**
 219  * Destroy a hash map.  Will not free any values
 220  * stored in the hash map!
 221  *
 222  * @param map the map
 223  */
 224 void
 225 GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap *map)
 226 {
 227   GNUNET_assert (0 == map->next_cache_off);
 228   for (unsigned int i = 0; i < map->map_length; i++)
 229   {
 230     union MapEntry me;
 231
 232     me = map->map[i];
 233     if (map->use_small_entries)
 234     {
 235       struct SmallMapEntry *sme;
 236       struct SmallMapEntry *nxt;
 237
 238       nxt = me.sme;
 239       while (NULL != (sme = nxt))
 240       {
 241         nxt = sme->next;
 242         GNUNET_free (sme);
 243       }
 244       me.sme = NULL;
 245     }
 246     else
 247     {
 248       struct BigMapEntry *bme;
 249       struct BigMapEntry *nxt;
 250
 251       nxt = me.bme;
 252       while (NULL != (bme = nxt))
 253       {
 254         nxt = bme->next;
 255         GNUNET_free (bme);
 256       }
 257       me.bme = NULL;
 258     }
 259   }
 260   GNUNET_free (map->map);
 261   GNUNET_free (map);
 262 }
 263
 264
 265 /**
 266  * Compute the index of the bucket for the given key.
 267  *
 268  * @param map hash map for which to compute the index
 269  * @param key what key should the index be computed for
 270  * @return offset into the "map" array of "map"
 271  */
 272 static unsigned int
 273 idx_of (const struct GNUNET_CONTAINER_MultiShortmap *map,
 274         const struct GNUNET_ShortHashCode *key)
 275 {
 276   unsigned int kx;
 277
 278   GNUNET_assert (NULL != map);
 279   GNUNET_memcpy (&kx, key, sizeof (kx));
 280   return kx % map->map_length;
 281 }
 282
 283
 284 /**
 285  * Get the number of key-value pairs in the map.
 286  *
 287  * @param map the map
 288  * @return the number of key value pairs
 289  */
 290 unsigned int
 291 GNUNET_CONTAINER_multishortmap_size (const struct GNUNET_CONTAINER_MultiShortmap *map)
 292 {
 293   return map->size;
 294 }
 295
 296
 297 /**
 298  * Given a key find a value in the map matching the key.
 299  *
 300  * @param map the map
 301  * @param key what to look for
 302  * @return NULL if no value was found; note that
 303  *   this is indistinguishable from values that just
 304  *   happen to be NULL; use "contains" to test for
 305  *   key-value pairs with value NULL
 306  */
 307 void *
 308 GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap *map,
 309                                     const struct GNUNET_ShortHashCode *key)
 310 {
 311   union MapEntry me;
 312
 313   me = map->map[idx_of (map, key)];
 314   if (map->use_small_entries)
 315   {
 316     for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
 317       if (0 == memcmp (key,
 318                        sme->key,
 319                        sizeof (struct GNUNET_ShortHashCode)))
 320         return sme->value;
 321   }
 322   else
 323   {
 324     for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
 325       if (0 == memcmp (key,
 326                        &bme->key,
 327                        sizeof (struct GNUNET_ShortHashCode)))
 328         return bme->value;
 329   }
 330   return NULL;
 331 }
 332
 333
 334 /**
 335  * Iterate over all entries in the map.
 336  *
 337  * @param map the map
 338  * @param it function to call on each entry
 339  * @param it_cls extra argument to @a it
 340  * @return the number of key value pairs processed,
 341  *         #GNUNET_SYSERR if it aborted iteration
 342  */
 343 int
 344 GNUNET_CONTAINER_multishortmap_iterate (struct GNUNET_CONTAINER_MultiShortmap *map,
 345                                         GNUNET_CONTAINER_ShortmapIterator it,
 346                                         void *it_cls)
 347 {
 348   int count;
 349   union MapEntry me;
 350   union MapEntry *ce;
 351   struct GNUNET_ShortHashCode kc;
 352
 353   count = 0;
 354   GNUNET_assert (NULL != map);
 355   ce = &map->next_cache[map->next_cache_off];
 356   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 357   for (unsigned int i = 0; i < map->map_length; i++)
 358   {
 359     me = map->map[i];
 360     if (map->use_small_entries)
 361     {
 362       struct SmallMapEntry *sme;
 363
 364       ce->sme = me.sme;
 365       while (NULL != (sme = ce->sme))
 366       {
 367         ce->sme = sme->next;
 368         if ( (NULL != it) &&
 369              (GNUNET_OK != it (it_cls,
 370                                sme->key,
 371                                sme->value)) )
 372         {
 373           GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 374           return GNUNET_SYSERR;
 375         }
 376         count++;
 377       }
 378     }
 379     else
 380     {
 381       struct BigMapEntry *bme;
 382
 383       ce->bme = me.bme;
 384       while (NULL != (bme = ce->bme))
 385       {
 386         ce->bme = bme->next;
 387         if (NULL != it)
 388         {
 389           kc = bme->key;
 390           if (GNUNET_OK != it (it_cls,
 391                                &kc,
 392                                bme->value))
 393           {
 394             GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 395             return GNUNET_SYSERR;
 396           }
 397         }
 398         count++;
 399       }
 400     }
 401   }
 402   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 403   return count;
 404 }
 405
 406
 407 /**
 408  * We are about to free() the @a bme, make sure it is not in
 409  * the list of next values for any iterator in the @a map's next_cache.
 410  *
 411  * @param map the map to check
 412  * @param bme the entry that is about to be free'd
 413  */
 414 static void
 415 update_next_cache_bme (struct GNUNET_CONTAINER_MultiShortmap *map,
 416                        const struct BigMapEntry *bme)
 417 {
 418   for (unsigned int i=0;i<map->next_cache_off;i++)
 419     if (map->next_cache[i].bme == bme)
 420       map->next_cache[i].bme = bme->next;
 421 }
 422
 423
 424 /**
 425  * We are about to free() the @a sme, make sure it is not in
 426  * the list of next values for any iterator in the @a map's next_cache.
 427  *
 428  * @param map the map to check
 429  * @param sme the entry that is about to be free'd
 430  */
 431 static void
 432 update_next_cache_sme (struct GNUNET_CONTAINER_MultiShortmap *map,
 433                        const struct SmallMapEntry *sme)
 434 {
 435   for (unsigned int i=0;i<map->next_cache_off;i++)
 436     if (map->next_cache[i].sme == sme)
 437       map->next_cache[i].sme = sme->next;
 438 }
 439
 440
 441 /**
 442  * Remove the given key-value pair from the map.  Note that if the
 443  * key-value pair is in the map multiple times, only one of the pairs
 444  * will be removed.
 445  *
 446  * @param map the map
 447  * @param key key of the key-value pair
 448  * @param value value of the key-value pair
 449  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
 450  *  is not in the map
 451  */
 452 int
 453 GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *map,
 454                                        const struct GNUNET_ShortHashCode *key,
 455                                        const void *value)
 456 {
 457   union MapEntry me;
 458   unsigned int i;
 459
 460   map->modification_counter++;
 461   i = idx_of (map, key);
 462   me = map->map[i];
 463   if (map->use_small_entries)
 464   {
 465     struct SmallMapEntry *p = NULL;
 466
 467     for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
 468     {
 469       if ((0 == memcmp (key,
 470                         sme->key,
 471                         sizeof (struct GNUNET_ShortHashCode))) &&
 472           (value == sme->value))
 473       {
 474         if (NULL == p)
 475           map->map[i].sme = sme->next;
 476         else
 477           p->next = sme->next;
 478         update_next_cache_sme (map,
 479                                sme);
 480         GNUNET_free (sme);
 481         map->size--;
 482         return GNUNET_YES;
 483       }
 484       p = sme;
 485     }
 486   }
 487   else
 488   {
 489     struct BigMapEntry *p = NULL;
 490
 491     for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
 492     {
 493       if ((0 == memcmp (key,
 494                         &bme->key,
 495                         sizeof (struct GNUNET_ShortHashCode))) &&
 496           (value == bme->value))
 497       {
 498         if (NULL == p)
 499           map->map[i].bme = bme->next;
 500         else
 501           p->next = bme->next;
 502         update_next_cache_bme (map,
 503                                bme);
 504         GNUNET_free (bme);
 505         map->size--;
 506         return GNUNET_YES;
 507       }
 508       p = bme;
 509     }
 510   }
 511   return GNUNET_NO;
 512 }
 513
 514
 515 /**
 516  * Remove all entries for the given key from the map.
 517  * Note that the values would not be "freed".
 518  *
 519  * @param map the map
 520  * @param key identifies values to be removed
 521  * @return number of values removed
 522  */
 523 int
 524 GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap *map,
 525                                            const struct GNUNET_ShortHashCode *key)
 526 {
 527   union MapEntry me;
 528   unsigned int i;
 529   int ret;
 530
 531   map->modification_counter++;
 532
 533   ret = 0;
 534   i = idx_of (map, key);
 535   me = map->map[i];
 536   if (map->use_small_entries)
 537   {
 538     struct SmallMapEntry *sme;
 539     struct SmallMapEntry *p;
 540
 541     p = NULL;
 542     sme = me.sme;
 543     while (NULL != sme)
 544     {
 545       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode)))
 546       {
 547         if (NULL == p)
 548           map->map[i].sme = sme->next;
 549         else
 550           p->next = sme->next;
 551         update_next_cache_sme (map,
 552                                sme);
 553         GNUNET_free (sme);
 554         map->size--;
 555         if (NULL == p)
 556           sme = map->map[i].sme;
 557         else
 558           sme = p->next;
 559         ret++;
 560       }
 561       else
 562       {
 563         p = sme;
 564         sme = sme->next;
 565       }
 566     }
 567   }
 568   else
 569   {
 570     struct BigMapEntry *bme;
 571     struct BigMapEntry *p;
 572
 573     p = NULL;
 574     bme = me.bme;
 575     while (NULL != bme)
 576     {
 577       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode)))
 578       {
 579         if (NULL == p)
 580           map->map[i].bme = bme->next;
 581         else
 582           p->next = bme->next;
 583         update_next_cache_bme (map,
 584                                bme);
 585         GNUNET_free (bme);
 586         map->size--;
 587         if (NULL == p)
 588           bme = map->map[i].bme;
 589         else
 590           bme = p->next;
 591         ret++;
 592       }
 593       else
 594       {
 595         p = bme;
 596         bme = bme->next;
 597       }
 598     }
 599   }
 600   return ret;
 601 }
 602
 603
 604 /**
 605  * Check if the map contains any value under the given
 606  * key (including values that are NULL).
 607  *
 608  * @param map the map
 609  * @param key the key to test if a value exists for it
 610  * @return #GNUNET_YES if such a value exists,
 611  *         #GNUNET_NO if not
 612  */
 613 int
 614 GNUNET_CONTAINER_multishortmap_contains (const struct GNUNET_CONTAINER_MultiShortmap *map,
 615                                          const struct GNUNET_ShortHashCode *key)
 616 {
 617   union MapEntry me;
 618
 619   me = map->map[idx_of (map, key)];
 620   if (map->use_small_entries)
 621   {
 622     for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
 623       if (0 == memcmp (key,
 624                        sme->key,
 625                        sizeof (struct GNUNET_ShortHashCode)))
 626         return GNUNET_YES;
 627   }
 628   else
 629   {
 630     for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
 631       if (0 == memcmp (key,
 632                        &bme->key,
 633                        sizeof (struct GNUNET_ShortHashCode)))
 634         return GNUNET_YES;
 635   }
 636   return GNUNET_NO;
 637 }
 638
 639
 640 /**
 641  * Check if the map contains the given value under the given
 642  * key.
 643  *
 644  * @param map the map
 645  * @param key the key to test if a value exists for it
 646  * @param value value to test for
 647  * @return #GNUNET_YES if such a value exists,
 648  *         #GNUNET_NO if not
 649  */
 650 int
 651 GNUNET_CONTAINER_multishortmap_contains_value (const struct GNUNET_CONTAINER_MultiShortmap *map,
 652                                                const struct GNUNET_ShortHashCode *key,
 653                                                const void *value)
 654 {
 655   union MapEntry me;
 656
 657   me = map->map[idx_of (map, key)];
 658   if (map->use_small_entries)
 659   {
 660     for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
 661       if ( (0 == memcmp (key,
 662                          sme->key,
 663                          sizeof (struct GNUNET_ShortHashCode))) &&
 664            (sme->value == value) )
 665         return GNUNET_YES;
 666   }
 667   else
 668   {
 669     for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
 670       if ( (0 == memcmp (key,
 671                          &bme->key,
 672                          sizeof (struct GNUNET_ShortHashCode))) &&
 673            (bme->value == value) )
 674         return GNUNET_YES;
 675   }
 676   return GNUNET_NO;
 677 }
 678
 679
 680 /**
 681  * Grow the given map to a more appropriate size.
 682  *
 683  * @param map the hash map to grow
 684  */
 685 static void
 686 grow (struct GNUNET_CONTAINER_MultiShortmap *map)
 687 {
 688   union MapEntry *old_map;
 689   union MapEntry *new_map;
 690   unsigned int old_len;
 691   unsigned int new_len;
 692   unsigned int idx;
 693
 694   old_map = map->map;
 695   old_len = map->map_length;
 696   new_len = old_len * 2;
 697   if (0 == new_len) /* 2^31 * 2 == 0 */
 698     new_len = old_len; /* never use 0 */
 699   if (new_len == old_len)
 700     return; /* nothing changed */
 701   new_map = GNUNET_malloc_large (new_len *
 702                                  sizeof (union MapEntry));
 703   if (NULL == new_map)
 704     return; /* grow not possible */
 705   map->modification_counter++;
 706   map->map_length = new_len;
 707   map->map = new_map;
 708   for (unsigned int i = 0; i < old_len; i++)
 709   {
 710     if (map->use_small_entries)
 711     {
 712       struct SmallMapEntry *sme;
 713
 714       while (NULL != (sme = old_map[i].sme))
 715       {
 716         old_map[i].sme = sme->next;
 717         idx = idx_of (map, sme->key);
 718         sme->next = new_map[idx].sme;
 719         new_map[idx].sme = sme;
 720       }
 721     }
 722     else
 723     {
 724       struct BigMapEntry *bme;
 725
 726       while (NULL != (bme = old_map[i].bme))
 727       {
 728         old_map[i].bme = bme->next;
 729         idx = idx_of (map, &bme->key);
 730         bme->next = new_map[idx].bme;
 731         new_map[idx].bme = bme;
 732       }
 733     }
 734   }
 735   GNUNET_free (old_map);
 736 }
 737
 738
 739 /**
 740  * Store a key-value pair in the map.
 741  *
 742  * @param map the map
 743  * @param key key to use
 744  * @param value value to use
 745  * @param opt options for put
 746  * @return #GNUNET_OK on success,
 747  *         #GNUNET_NO if a value was replaced (with REPLACE)
 748  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
 749  *                       value already exists
 750  */
 751 int
 752 GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map,
 753                                     const struct GNUNET_ShortHashCode *key,
 754                                     void *value,
 755                                     enum GNUNET_CONTAINER_MultiHashMapOption opt)
 756 {
 757   union MapEntry me;
 758   unsigned int i;
 759
 760   i = idx_of (map, key);
 761   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 762       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 763   {
 764     me = map->map[i];
 765     if (map->use_small_entries)
 766     {
 767       for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
 768         if (0 == memcmp (key,
 769                          sme->key,
 770                          sizeof (struct GNUNET_ShortHashCode)))
 771         {
 772           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 773             return GNUNET_SYSERR;
 774           sme->value = value;
 775           return GNUNET_NO;
 776         }
 777     }
 778     else
 779     {
 780       for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
 781         if (0 == memcmp (key,
 782                          &bme->key,
 783                          sizeof (struct GNUNET_ShortHashCode)))
 784         {
 785           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 786             return GNUNET_SYSERR;
 787           bme->value = value;
 788           return GNUNET_NO;
 789         }
 790     }
 791   }
 792   if (map->size / 3 >= map->map_length / 4)
 793   {
 794     grow (map);
 795     i = idx_of (map, key);
 796   }
 797   if (map->use_small_entries)
 798   {
 799     struct SmallMapEntry *sme;
 800
 801     sme = GNUNET_new (struct SmallMapEntry);
 802     sme->key = key;
 803     sme->value = value;
 804     sme->next = map->map[i].sme;
 805     map->map[i].sme = sme;
 806   }
 807   else
 808   {
 809     struct BigMapEntry *bme;
 810
 811     bme = GNUNET_new (struct BigMapEntry);
 812     bme->key = *key;
 813     bme->value = value;
 814     bme->next = map->map[i].bme;
 815     map->map[i].bme = bme;
 816   }
 817   map->size++;
 818   return GNUNET_OK;
 819 }
 820
 821
 822 /**
 823  * Iterate over all entries in the map that match a particular key.
 824  *
 825  * @param map the map
 826  * @param key key that the entries must correspond to
 827  * @param it function to call on each entry
 828  * @param it_cls extra argument to @a it
 829  * @return the number of key value pairs processed,
 830  *         #GNUNET_SYSERR if it aborted iteration
 831  */
 832 int
 833 GNUNET_CONTAINER_multishortmap_get_multiple (struct GNUNET_CONTAINER_MultiShortmap *map,
 834                                              const struct GNUNET_ShortHashCode *key,
 835                                              GNUNET_CONTAINER_ShortmapIterator it,
 836                                              void *it_cls)
 837 {
 838   int count;
 839   union MapEntry me;
 840   union MapEntry *ce;
 841
 842   ce = &map->next_cache[map->next_cache_off];
 843   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 844   count = 0;
 845   me = map->map[idx_of (map, key)];
 846   if (map->use_small_entries)
 847   {
 848     struct SmallMapEntry *sme;
 849
 850     ce->sme = me.sme;
 851     while (NULL != (sme = ce->sme))
 852     {
 853       ce->sme = sme->next;
 854       if (0 != memcmp (key,
 855                        sme->key,
 856                        sizeof (struct GNUNET_ShortHashCode)))
 857         continue;
 858       if ( (NULL != it) &&
 859            (GNUNET_OK != it (it_cls,
 860                              key,
 861                              sme->value)) )
 862       {
 863         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 864         return GNUNET_SYSERR;
 865       }
 866       count++;
 867     }
 868   }
 869   else
 870   {
 871     struct BigMapEntry *bme;
 872
 873     ce->bme = me.bme;
 874     while (NULL != (bme = ce->bme))
 875     {
 876       ce->bme = bme->next;
 877       if (0 != memcmp (key,
 878                        &bme->key,
 879                        sizeof (struct GNUNET_ShortHashCode)))
 880         continue;
 881       if ( (NULL != it) &&
 882            (GNUNET_OK != it (it_cls,
 883                              key,
 884                              bme->value)) )
 885       {
 886         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 887         return GNUNET_SYSERR;
 888       }
 889       count++;
 890     }
 891   }
 892   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 893   return count;
 894 }
 895
 896
 897 /**
 898  * @ingroup hashmap
 899  * Call @a it on a random value from the map, or not at all
 900  * if the map is empty.  Note that this function has linear
 901  * complexity (in the size of the map).
 902  *
 903  * @param map the map
 904  * @param it function to call on a random entry
 905  * @param it_cls extra argument to @a it
 906  * @return the number of key value pairs processed, zero or one.
 907  */
 908 unsigned int
 909 GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiShortmap *map,
 910                                           GNUNET_CONTAINER_ShortmapIterator it,
 911                                           void *it_cls)
 912 {
 913   unsigned int off;
 914   union MapEntry me;
 915
 916   if (0 == map->size)
 917     return 0;
 918   if (NULL == it)
 919     return 1;
 920   off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
 921                                   map->size);
 922   for (unsigned int idx = 0; idx < map->map_length; idx++)
 923   {
 924     me = map->map[idx];
 925     if (map->use_small_entries)
 926     {
 927       for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
 928       {
 929         if (0 == off)
 930         {
 931           if (GNUNET_OK != it (it_cls,
 932                                sme->key,
 933                                sme->value))
 934             return GNUNET_SYSERR;
 935           return 1;
 936         }
 937         off--;
 938       }
 939     }
 940     else
 941     {
 942       for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
 943       {
 944         if (0 == off)
 945         {
 946           if (GNUNET_OK != it (it_cls,
 947                                &bme->key, bme->value))
 948             return GNUNET_SYSERR;
 949           return 1;
 950         }
 951         off--;
 952       }
 953     }
 954   }
 955   GNUNET_break (0);
 956   return GNUNET_SYSERR;
 957 }
 958
 959
 960 /**
 961  * Create an iterator for a multishortmap.
 962  * The iterator can be used to retrieve all the elements in the multishortmap
 963  * one by one, without having to handle all elements at once (in contrast to
 964  * #GNUNET_CONTAINER_multishortmap_iterate).  Note that the iterator can not be
 965  * used anymore if elements have been removed from 'map' after the creation of
 966  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
 967  * result in skipped or repeated elements.
 968  *
 969  * @param map the map to create an iterator for
 970  * @return an iterator over the given multishortmap 'map'
 971  */
 972 struct GNUNET_CONTAINER_MultiShortmapIterator *
 973 GNUNET_CONTAINER_multishortmap_iterator_create (const struct GNUNET_CONTAINER_MultiShortmap *map)
 974 {
 975   struct GNUNET_CONTAINER_MultiShortmapIterator *iter;
 976
 977   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmapIterator);
 978   iter->map = map;
 979   iter->modification_counter = map->modification_counter;
 980   iter->me = map->map[0];
 981   return iter;
 982 }
 983
 984
 985 /**
 986  * Retrieve the next element from the hash map at the iterator's position.
 987  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
 988  * are not modified.
 989  * This operation is only allowed if no elements have been removed from the
 990  * multishortmap since the creation of 'iter', and the map has not been destroyed.
 991  * Adding elements may result in repeating or skipping elements.
 992  *
 993  * @param iter the iterator to get the next element from
 994  * @param key pointer to store the key in, can be NULL
 995  * @param value pointer to store the value in, can be NULL
 996  * @return #GNUNET_YES we returned an element,
 997  *         #GNUNET_NO if we are out of elements
 998  */
 999 int
1000 GNUNET_CONTAINER_multishortmap_iterator_next (struct GNUNET_CONTAINER_MultiShortmapIterator *iter,
1001                                               struct GNUNET_ShortHashCode *key,
1002                                               const void **value)
1003 {
1004   /* make sure the map has not been modified */
1005   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
1006
1007   /* look for the next entry, skipping empty buckets */
1008   while (1)
1009   {
1010     if (iter->idx >= iter->map->map_length)
1011       return GNUNET_NO;
1012     if (GNUNET_YES == iter->map->use_small_entries)
1013     {
1014       if (NULL != iter->me.sme)
1015       {
1016         if (NULL != key)
1017           *key = *iter->me.sme->key;
1018         if (NULL != value)
1019           *value = iter->me.sme->value;
1020         iter->me.sme = iter->me.sme->next;
1021         return GNUNET_YES;
1022       }
1023     }
1024     else
1025     {
1026       if (NULL != iter->me.bme)
1027       {
1028         if (NULL != key)
1029           *key = iter->me.bme->key;
1030         if (NULL != value)
1031           *value = iter->me.bme->value;
1032         iter->me.bme = iter->me.bme->next;
1033         return GNUNET_YES;
1034       }
1035     }
1036     iter->idx += 1;
1037     if (iter->idx < iter->map->map_length)
1038       iter->me = iter->map->map[iter->idx];
1039   }
1040 }
1041
1042
1043 /**
1044  * Destroy a multishortmap iterator.
1045  *
1046  * @param iter the iterator to destroy
1047  */
1048 void
1049 GNUNET_CONTAINER_multishortmap_iterator_destroy (struct GNUNET_CONTAINER_MultiShortmapIterator *iter)
1050 {
1051   GNUNET_free (iter);
1052 }
1053
1054
1055 /* end of container_multishortmap.c */