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