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