src/util/container_multiuuidmap.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_multiuuidmap.c
  22  * @brief hash map for UUIDs 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-multiuuidmap", __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_Uuid 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_Uuid *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_MultiUuidmap {
 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 multiuuidmap.
 147  * Allows to enumerate elements asynchronously.
 148  */
 149 struct GNUNET_CONTAINER_MultiUuidmapIterator {
 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_MultiUuidmap *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_MultiUuidmap *
 189 GNUNET_CONTAINER_multiuuidmap_create(unsigned int len, int do_not_copy_keys)
 190 {
 191   struct GNUNET_CONTAINER_MultiUuidmap *map;
 192
 193   GNUNET_assert(len > 0);
 194   map = GNUNET_new(struct GNUNET_CONTAINER_MultiUuidmap);
 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_multiuuidmap_destroy(
 215   struct GNUNET_CONTAINER_MultiUuidmap *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_MultiUuidmap *map,
 264        const struct GNUNET_Uuid *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_multiuuidmap_size(
 282   const struct GNUNET_CONTAINER_MultiUuidmap *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_multiuuidmap_get(
 300   const struct GNUNET_CONTAINER_MultiUuidmap *map,
 301   const struct GNUNET_Uuid *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_multiuuidmap_iterate(
 333   struct GNUNET_CONTAINER_MultiUuidmap *map,
 334   GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
 335   void *it_cls)
 336 {
 337   int count;
 338   union MapEntry me;
 339   union MapEntry *ce;
 340   struct GNUNET_Uuid 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_MultiUuidmap *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_MultiUuidmap *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_multiuuidmap_remove(struct GNUNET_CONTAINER_MultiUuidmap *map,
 438                                      const struct GNUNET_Uuid *key,
 439                                      const void *value)
 440 {
 441   union MapEntry me;
 442   unsigned int i;
 443
 444   map->modification_counter++;
 445   i = idx_of(map, key);
 446   me = map->map[i];
 447   if (map->use_small_entries)
 448     {
 449       struct SmallMapEntry *p = NULL;
 450
 451       for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
 452         {
 453           if ((0 == GNUNET_memcmp(key, sme->key)) && (value == sme->value))
 454             {
 455               if (NULL == p)
 456                 map->map[i].sme = sme->next;
 457               else
 458                 p->next = sme->next;
 459               update_next_cache_sme(map, sme);
 460               GNUNET_free(sme);
 461               map->size--;
 462               return GNUNET_YES;
 463             }
 464           p = sme;
 465         }
 466     }
 467   else
 468     {
 469       struct BigMapEntry *p = NULL;
 470
 471       for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
 472         {
 473           if ((0 == GNUNET_memcmp(key, &bme->key)) && (value == bme->value))
 474             {
 475               if (NULL == p)
 476                 map->map[i].bme = bme->next;
 477               else
 478                 p->next = bme->next;
 479               update_next_cache_bme(map, bme);
 480               GNUNET_free(bme);
 481               map->size--;
 482               return GNUNET_YES;
 483             }
 484           p = bme;
 485         }
 486     }
 487   return GNUNET_NO;
 488 }
 489
 490
 491 /**
 492  * Remove all entries for the given key from the map.
 493  * Note that the values would not be "freed".
 494  *
 495  * @param map the map
 496  * @param key identifies values to be removed
 497  * @return number of values removed
 498  */
 499 int
 500 GNUNET_CONTAINER_multiuuidmap_remove_all(
 501   struct GNUNET_CONTAINER_MultiUuidmap *map,
 502   const struct GNUNET_Uuid *key)
 503 {
 504   union MapEntry me;
 505   unsigned int i;
 506   int ret;
 507
 508   map->modification_counter++;
 509
 510   ret = 0;
 511   i = idx_of(map, key);
 512   me = map->map[i];
 513   if (map->use_small_entries)
 514     {
 515       struct SmallMapEntry *sme;
 516       struct SmallMapEntry *p;
 517
 518       p = NULL;
 519       sme = me.sme;
 520       while (NULL != sme)
 521         {
 522           if (0 == GNUNET_memcmp(key, sme->key))
 523             {
 524               if (NULL == p)
 525                 map->map[i].sme = sme->next;
 526               else
 527                 p->next = sme->next;
 528               update_next_cache_sme(map, sme);
 529               GNUNET_free(sme);
 530               map->size--;
 531               if (NULL == p)
 532                 sme = map->map[i].sme;
 533               else
 534                 sme = p->next;
 535               ret++;
 536             }
 537           else
 538             {
 539               p = sme;
 540               sme = sme->next;
 541             }
 542         }
 543     }
 544   else
 545     {
 546       struct BigMapEntry *bme;
 547       struct BigMapEntry *p;
 548
 549       p = NULL;
 550       bme = me.bme;
 551       while (NULL != bme)
 552         {
 553           if (0 == GNUNET_memcmp(key, &bme->key))
 554             {
 555               if (NULL == p)
 556                 map->map[i].bme = bme->next;
 557               else
 558                 p->next = bme->next;
 559               update_next_cache_bme(map, bme);
 560               GNUNET_free(bme);
 561               map->size--;
 562               if (NULL == p)
 563                 bme = map->map[i].bme;
 564               else
 565                 bme = p->next;
 566               ret++;
 567             }
 568           else
 569             {
 570               p = bme;
 571               bme = bme->next;
 572             }
 573         }
 574     }
 575   return ret;
 576 }
 577
 578
 579 /**
 580  * Check if the map contains any value under the given
 581  * key (including values that are NULL).
 582  *
 583  * @param map the map
 584  * @param key the key to test if a value exists for it
 585  * @return #GNUNET_YES if such a value exists,
 586  *         #GNUNET_NO if not
 587  */
 588 int
 589 GNUNET_CONTAINER_multiuuidmap_contains(
 590   const struct GNUNET_CONTAINER_MultiUuidmap *map,
 591   const struct GNUNET_Uuid *key)
 592 {
 593   union MapEntry me;
 594
 595   me = map->map[idx_of(map, key)];
 596   if (map->use_small_entries)
 597     {
 598       for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
 599         if (0 == GNUNET_memcmp(key, sme->key))
 600           return GNUNET_YES;
 601     }
 602   else
 603     {
 604       for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
 605         if (0 == GNUNET_memcmp(key, &bme->key))
 606           return GNUNET_YES;
 607     }
 608   return GNUNET_NO;
 609 }
 610
 611
 612 /**
 613  * Check if the map contains the given value under the given
 614  * key.
 615  *
 616  * @param map the map
 617  * @param key the key to test if a value exists for it
 618  * @param value value to test for
 619  * @return #GNUNET_YES if such a value exists,
 620  *         #GNUNET_NO if not
 621  */
 622 int
 623 GNUNET_CONTAINER_multiuuidmap_contains_value(
 624   const struct GNUNET_CONTAINER_MultiUuidmap *map,
 625   const struct GNUNET_Uuid *key,
 626   const void *value)
 627 {
 628   union MapEntry me;
 629
 630   me = map->map[idx_of(map, key)];
 631   if (map->use_small_entries)
 632     {
 633       for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
 634         if ((0 == GNUNET_memcmp(key, sme->key)) && (sme->value == value))
 635           return GNUNET_YES;
 636     }
 637   else
 638     {
 639       for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
 640         if ((0 == GNUNET_memcmp(key, &bme->key)) && (bme->value == value))
 641           return GNUNET_YES;
 642     }
 643   return GNUNET_NO;
 644 }
 645
 646
 647 /**
 648  * Grow the given map to a more appropriate size.
 649  *
 650  * @param map the hash map to grow
 651  */
 652 static void
 653 grow(struct GNUNET_CONTAINER_MultiUuidmap *map)
 654 {
 655   union MapEntry *old_map;
 656   union MapEntry *new_map;
 657   unsigned int old_len;
 658   unsigned int new_len;
 659   unsigned int idx;
 660
 661   old_map = map->map;
 662   old_len = map->map_length;
 663   new_len = old_len * 2;
 664   if (0 == new_len) /* 2^31 * 2 == 0 */
 665     new_len = old_len; /* never use 0 */
 666   if (new_len == old_len)
 667     return; /* nothing changed */
 668   new_map = GNUNET_malloc_large(new_len * sizeof(union MapEntry));
 669   if (NULL == new_map)
 670     return; /* grow not possible */
 671   map->modification_counter++;
 672   map->map_length = new_len;
 673   map->map = new_map;
 674   for (unsigned int i = 0; i < old_len; i++)
 675     {
 676       if (map->use_small_entries)
 677         {
 678           struct SmallMapEntry *sme;
 679
 680           while (NULL != (sme = old_map[i].sme))
 681             {
 682               old_map[i].sme = sme->next;
 683               idx = idx_of(map, sme->key);
 684               sme->next = new_map[idx].sme;
 685               new_map[idx].sme = sme;
 686             }
 687         }
 688       else
 689         {
 690           struct BigMapEntry *bme;
 691
 692           while (NULL != (bme = old_map[i].bme))
 693             {
 694               old_map[i].bme = bme->next;
 695               idx = idx_of(map, &bme->key);
 696               bme->next = new_map[idx].bme;
 697               new_map[idx].bme = bme;
 698             }
 699         }
 700     }
 701   GNUNET_free(old_map);
 702 }
 703
 704
 705 /**
 706  * Store a key-value pair in the map.
 707  *
 708  * @param map the map
 709  * @param key key to use
 710  * @param value value to use
 711  * @param opt options for put
 712  * @return #GNUNET_OK on success,
 713  *         #GNUNET_NO if a value was replaced (with REPLACE)
 714  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
 715  *                       value already exists
 716  */
 717 int
 718 GNUNET_CONTAINER_multiuuidmap_put(struct GNUNET_CONTAINER_MultiUuidmap *map,
 719                                   const struct GNUNET_Uuid *key,
 720                                   void *value,
 721                                   enum GNUNET_CONTAINER_MultiHashMapOption opt)
 722 {
 723   union MapEntry me;
 724   unsigned int i;
 725
 726   i = idx_of(map, key);
 727   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 728       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 729     {
 730       me = map->map[i];
 731       if (map->use_small_entries)
 732         {
 733           for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
 734             if (0 == GNUNET_memcmp(key, sme->key))
 735               {
 736                 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 737                   return GNUNET_SYSERR;
 738                 sme->value = value;
 739                 return GNUNET_NO;
 740               }
 741         }
 742       else
 743         {
 744           for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
 745             if (0 == GNUNET_memcmp(key, &bme->key))
 746               {
 747                 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 748                   return GNUNET_SYSERR;
 749                 bme->value = value;
 750                 return GNUNET_NO;
 751               }
 752         }
 753     }
 754   if (map->size / 3 >= map->map_length / 4)
 755     {
 756       grow(map);
 757       i = idx_of(map, key);
 758     }
 759   if (map->use_small_entries)
 760     {
 761       struct SmallMapEntry *sme;
 762
 763       sme = GNUNET_new(struct SmallMapEntry);
 764       sme->key = key;
 765       sme->value = value;
 766       sme->next = map->map[i].sme;
 767       map->map[i].sme = sme;
 768     }
 769   else
 770     {
 771       struct BigMapEntry *bme;
 772
 773       bme = GNUNET_new(struct BigMapEntry);
 774       bme->key = *key;
 775       bme->value = value;
 776       bme->next = map->map[i].bme;
 777       map->map[i].bme = bme;
 778     }
 779   map->size++;
 780   return GNUNET_OK;
 781 }
 782
 783
 784 /**
 785  * Iterate over all entries in the map that match a particular key.
 786  *
 787  * @param map the map
 788  * @param key key that the entries must correspond to
 789  * @param it function to call on each entry
 790  * @param it_cls extra argument to @a it
 791  * @return the number of key value pairs processed,
 792  *         #GNUNET_SYSERR if it aborted iteration
 793  */
 794 int
 795 GNUNET_CONTAINER_multiuuidmap_get_multiple(
 796   struct GNUNET_CONTAINER_MultiUuidmap *map,
 797   const struct GNUNET_Uuid *key,
 798   GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
 799   void *it_cls)
 800 {
 801   int count;
 802   union MapEntry me;
 803   union MapEntry *ce;
 804
 805   ce = &map->next_cache[map->next_cache_off];
 806   GNUNET_assert(++map->next_cache_off < NEXT_CACHE_SIZE);
 807   count = 0;
 808   me = map->map[idx_of(map, key)];
 809   if (map->use_small_entries)
 810     {
 811       struct SmallMapEntry *sme;
 812
 813       ce->sme = me.sme;
 814       while (NULL != (sme = ce->sme))
 815         {
 816           ce->sme = sme->next;
 817           if (0 != GNUNET_memcmp(key, sme->key))
 818             continue;
 819           if ((NULL != it) && (GNUNET_OK != it(it_cls, key, sme->value)))
 820             {
 821               GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE);
 822               return GNUNET_SYSERR;
 823             }
 824           count++;
 825         }
 826     }
 827   else
 828     {
 829       struct BigMapEntry *bme;
 830
 831       ce->bme = me.bme;
 832       while (NULL != (bme = ce->bme))
 833         {
 834           ce->bme = bme->next;
 835           if (0 != GNUNET_memcmp(key, &bme->key))
 836             continue;
 837           if ((NULL != it) && (GNUNET_OK != it(it_cls, key, bme->value)))
 838             {
 839               GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE);
 840               return GNUNET_SYSERR;
 841             }
 842           count++;
 843         }
 844     }
 845   GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE);
 846   return count;
 847 }
 848
 849
 850 /**
 851  * @ingroup hashmap
 852  * Call @a it on a random value from the map, or not at all
 853  * if the map is empty.  Note that this function has linear
 854  * complexity (in the size of the map).
 855  *
 856  * @param map the map
 857  * @param it function to call on a random entry
 858  * @param it_cls extra argument to @a it
 859  * @return the number of key value pairs processed, zero or one.
 860  */
 861 unsigned int
 862 GNUNET_CONTAINER_multiuuidmap_get_random(
 863   const struct GNUNET_CONTAINER_MultiUuidmap *map,
 864   GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
 865   void *it_cls)
 866 {
 867   unsigned int off;
 868   union MapEntry me;
 869
 870   if (0 == map->size)
 871     return 0;
 872   if (NULL == it)
 873     return 1;
 874   off = GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_NONCE, map->size);
 875   for (unsigned int idx = 0; idx < map->map_length; idx++)
 876     {
 877       me = map->map[idx];
 878       if (map->use_small_entries)
 879         {
 880           for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
 881             {
 882               if (0 == off)
 883                 {
 884                   if (GNUNET_OK != it(it_cls, sme->key, sme->value))
 885                     return GNUNET_SYSERR;
 886                   return 1;
 887                 }
 888               off--;
 889             }
 890         }
 891       else
 892         {
 893           for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
 894             {
 895               if (0 == off)
 896                 {
 897                   if (GNUNET_OK != it(it_cls, &bme->key, bme->value))
 898                     return GNUNET_SYSERR;
 899                   return 1;
 900                 }
 901               off--;
 902             }
 903         }
 904     }
 905   GNUNET_break(0);
 906   return GNUNET_SYSERR;
 907 }
 908
 909
 910 /**
 911  * Create an iterator for a multiuuidmap.
 912  * The iterator can be used to retrieve all the elements in the multiuuidmap
 913  * one by one, without having to handle all elements at once (in contrast to
 914  * #GNUNET_CONTAINER_multiuuidmap_iterate).  Note that the iterator can not be
 915  * used anymore if elements have been removed from 'map' after the creation of
 916  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
 917  * result in skipped or repeated elements.
 918  *
 919  * @param map the map to create an iterator for
 920  * @return an iterator over the given multiuuidmap 'map'
 921  */
 922 struct GNUNET_CONTAINER_MultiUuidmapIterator *
 923 GNUNET_CONTAINER_multiuuidmap_iterator_create(
 924   const struct GNUNET_CONTAINER_MultiUuidmap *map)
 925 {
 926   struct GNUNET_CONTAINER_MultiUuidmapIterator *iter;
 927
 928   iter = GNUNET_new(struct GNUNET_CONTAINER_MultiUuidmapIterator);
 929   iter->map = map;
 930   iter->modification_counter = map->modification_counter;
 931   iter->me = map->map[0];
 932   return iter;
 933 }
 934
 935
 936 /**
 937  * Retrieve the next element from the hash map at the iterator's position.
 938  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
 939  * are not modified.
 940  * This operation is only allowed if no elements have been removed from the
 941  * multiuuidmap since the creation of 'iter', and the map has not been destroyed.
 942  * Adding elements may result in repeating or skipping elements.
 943  *
 944  * @param iter the iterator to get the next element from
 945  * @param key pointer to store the key in, can be NULL
 946  * @param value pointer to store the value in, can be NULL
 947  * @return #GNUNET_YES we returned an element,
 948  *         #GNUNET_NO if we are out of elements
 949  */
 950 int
 951 GNUNET_CONTAINER_multiuuidmap_iterator_next(
 952   struct GNUNET_CONTAINER_MultiUuidmapIterator *iter,
 953   struct GNUNET_Uuid *key,
 954   const void **value)
 955 {
 956   /* make sure the map has not been modified */
 957   GNUNET_assert(iter->modification_counter == iter->map->modification_counter);
 958
 959   /* look for the next entry, skipping empty buckets */
 960   while (1)
 961     {
 962       if (iter->idx >= iter->map->map_length)
 963         return GNUNET_NO;
 964       if (GNUNET_YES == iter->map->use_small_entries)
 965         {
 966           if (NULL != iter->me.sme)
 967             {
 968               if (NULL != key)
 969                 *key = *iter->me.sme->key;
 970               if (NULL != value)
 971                 *value = iter->me.sme->value;
 972               iter->me.sme = iter->me.sme->next;
 973               return GNUNET_YES;
 974             }
 975         }
 976       else
 977         {
 978           if (NULL != iter->me.bme)
 979             {
 980               if (NULL != key)
 981                 *key = iter->me.bme->key;
 982               if (NULL != value)
 983                 *value = iter->me.bme->value;
 984               iter->me.bme = iter->me.bme->next;
 985               return GNUNET_YES;
 986             }
 987         }
 988       iter->idx += 1;
 989       if (iter->idx < iter->map->map_length)
 990         iter->me = iter->map->map[iter->idx];
 991     }
 992 }
 993
 994
 995 /**
 996  * Destroy a multiuuidmap iterator.
 997  *
 998  * @param iter the iterator to destroy
 999  */
1000 void
1001 GNUNET_CONTAINER_multiuuidmap_iterator_destroy(
1002   struct GNUNET_CONTAINER_MultiUuidmapIterator *iter)
1003 {
1004   GNUNET_free(iter);
1005 }
1006
1007
1008 /* end of container_multiuuidmap.c */