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