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