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