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