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