src/util/container_multihashmap32.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2008 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_multihashmap32.c
  22  * @brief a version of hash map implemented in container_multihashmap.c but with
  23  *          uint32_t as keys
  24  * @author Christian Grothoff
  25  * @author Sree Harsha Totakura
  26  */
  27
  28 #include "platform.h"
  29 #include "gnunet_container_lib.h"
  30
  31 #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__)
  32
  33
  34 /**
  35  * Maximum recursion depth for callbacks of
  36  * #GNUNET_CONTAINER_multihashmap_get_multiple() themselves
  37  * again calling #GNUNET_CONTAINER_multihashmap_get_multiple().
  38  * Should be totally excessive, but if violated we die.
  39  */
  40 #define NEXT_CACHE_SIZE 16
  41
  42 /**
  43  * An entry in the hash map.
  44  */
  45 struct MapEntry
  46 {
  47
  48   /**
  49    * Key for the entry.
  50    */
  51   uint32_t key;
  52
  53   /**
  54    * Value of the entry.
  55    */
  56   void *value;
  57
  58   /**
  59    * If there is a hash collision, we create a linked list.
  60    */
  61   struct MapEntry *next;
  62
  63 };
  64
  65 /**
  66  * Internal representation of the hash map.
  67  */
  68 struct GNUNET_CONTAINER_MultiHashMap32
  69 {
  70
  71   /**
  72    * All of our buckets.
  73    */
  74   struct MapEntry **map;
  75
  76   /**
  77    * Number of entries in the map.
  78    */
  79   unsigned int size;
  80
  81   /**
  82    * Length of the @e map array.
  83    */
  84   unsigned int map_length;
  85
  86   /**
  87    * Counts the destructive modifications (grow, remove)
  88    * to the map, so that iterators can check if they are still valid.
  89    */
  90   unsigned int modification_counter;
  91
  92   /**
  93    * Map entries indicating iteration positions currently
  94    * in use by #GNUNET_CONTAINER_multihashmap_get_multiple().
  95    * Only used up to @e next_cache_off.
  96    */
  97   struct MapEntry *next_cache[NEXT_CACHE_SIZE];
  98
  99   /**
 100    * Offset of @e next_cache entries in use, must be smaller
 101    * than #NEXT_CACHE_SIZE.
 102    */
 103   unsigned int next_cache_off;
 104 };
 105
 106
 107 /**
 108  * Cursor into a multihashmap.
 109  * Allows to enumerate elements asynchronously.
 110  */
 111 struct GNUNET_CONTAINER_MultiHashMap32Iterator
 112 {
 113   /**
 114    * Position in the bucket @e idx
 115    */
 116   struct MapEntry *me;
 117
 118   /**
 119    * Current bucket index.
 120    */
 121   unsigned int idx;
 122
 123   /**
 124    * Modification counter as observed on the map when the iterator
 125    * was created.
 126    */
 127   unsigned int modification_counter;
 128
 129   /**
 130    * Map that we are iterating over.
 131    */
 132   const struct GNUNET_CONTAINER_MultiHashMap32 *map;
 133 };
 134
 135
 136 /**
 137  * Create a multi hash map.
 138  *
 139  * @param len initial size (map will grow as needed)
 140  * @return NULL on error
 141  */
 142 struct GNUNET_CONTAINER_MultiHashMap32 *
 143 GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
 144 {
 145   struct GNUNET_CONTAINER_MultiHashMap32 *ret;
 146
 147   GNUNET_assert (len > 0);
 148   ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32);
 149   ret->map = GNUNET_malloc_large (len *
 150                                   sizeof (struct MapEntry *));
 151   if (NULL == ret->map)
 152   {
 153     GNUNET_free (ret);
 154     return NULL;
 155   }
 156   ret->map_length = len;
 157   return ret;
 158 }
 159
 160
 161 /**
 162  * Destroy a hash map.  Will not free any values
 163  * stored in the hash map!
 164  *
 165  * @param map the map
 166  */
 167 void
 168 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *map)
 169 {
 170   struct MapEntry *e;
 171
 172   for (unsigned int i = 0; i < map->map_length; i++)
 173   {
 174     while (NULL != (e = map->map[i]))
 175     {
 176       map->map[i] = e->next;
 177       GNUNET_free (e);
 178     }
 179   }
 180   GNUNET_free (map->map);
 181   GNUNET_free (map);
 182 }
 183
 184
 185 /**
 186  * Compute the index of the bucket for the given key.
 187  *
 188  * @param m hash map for which to compute the index
 189  * @param key what key should the index be computed for
 190  * @return offset into the "map" array of "m"
 191  */
 192 static unsigned int
 193 idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m,
 194         const uint32_t key)
 195 {
 196   GNUNET_assert (NULL != m);
 197   return ((unsigned int) key) % m->map_length;
 198 }
 199
 200
 201 /**
 202  * Get the number of key-value pairs in the map.
 203  *
 204  * @param map the map
 205  * @return the number of key value pairs
 206  */
 207 unsigned int
 208 GNUNET_CONTAINER_multihashmap32_size (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 209 {
 210   return map->size;
 211 }
 212
 213
 214 /**
 215  * Given a key find a value in the map matching the key.
 216  *
 217  * @param map the map
 218  * @param key what to look for
 219  * @return NULL if no value was found; note that
 220  *   this is indistinguishable from values that just
 221  *   happen to be NULL; use "contains" to test for
 222  *   key-value pairs with value NULL
 223  */
 224 void *
 225 GNUNET_CONTAINER_multihashmap32_get (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 226                                      uint32_t key)
 227 {
 228   struct MapEntry *e;
 229
 230   e = map->map[idx_of (map, key)];
 231   while (NULL != e)
 232   {
 233     if (key == e->key)
 234       return e->value;
 235     e = e->next;
 236   }
 237   return NULL;
 238 }
 239
 240
 241 /**
 242  * Iterate over all entries in the map.
 243  *
 244  * @param map the map
 245  * @param it function to call on each entry
 246  * @param it_cls extra argument to @a it
 247  * @return the number of key value pairs processed,
 248  *         #GNUNET_SYSERR if it aborted iteration
 249  */
 250 int
 251 GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 252                                          GNUNET_CONTAINER_HashMapIterator32 it,
 253                                          void *it_cls)
 254 {
 255   int count;
 256   struct MapEntry **ce;
 257
 258   count = 0;
 259   GNUNET_assert (NULL != map);
 260   ce = &map->next_cache[map->next_cache_off];
 261   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 262   for (unsigned int i = 0; i < map->map_length; i++)
 263   {
 264     struct MapEntry *e;
 265
 266     *ce = map->map[i];
 267     while (NULL != (e = *ce))
 268     {
 269       *ce = e->next;
 270       if (NULL != it)
 271       {
 272         if (GNUNET_OK != it (it_cls,
 273                              e->key,
 274                              e->value))
 275         {
 276           GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 277           return GNUNET_SYSERR;
 278         }
 279       }
 280       count++;
 281     }
 282   }
 283   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 284   return count;
 285 }
 286
 287
 288 /**
 289  * We are about to free() the @a bme, make sure it is not in
 290  * the list of next values for any iterator in the @a map's next_cache.
 291  *
 292  * @param map the map to check
 293  * @param bme the entry that is about to be free'd
 294  */
 295 static void
 296 update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 297                    const struct MapEntry *me)
 298 {
 299   for (unsigned int i=0;i<map->next_cache_off;i++)
 300     if (map->next_cache[i] == me)
 301       map->next_cache[i] = me->next;
 302 }
 303
 304
 305 /**
 306  * Remove the given key-value pair from the map.  Note that if the
 307  * key-value pair is in the map multiple times, only one of the pairs
 308  * will be removed.
 309  *
 310  * @param map the map
 311  * @param key key of the key-value pair
 312  * @param value value of the key-value pair
 313  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
 314  *  is not in the map
 315  */
 316 int
 317 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 318                                         uint32_t key,
 319                                         const void *value)
 320 {
 321   struct MapEntry *e;
 322   struct MapEntry *p;
 323   unsigned int i;
 324
 325   map->modification_counter++;
 326
 327   i = idx_of (map, key);
 328   p = NULL;
 329   e = map->map[i];
 330   while (e != NULL)
 331   {
 332     if ( (key == e->key) && (value == e->value) )
 333     {
 334       if (p == NULL)
 335         map->map[i] = e->next;
 336       else
 337         p->next = e->next;
 338       update_next_cache (map,
 339                          e);
 340       GNUNET_free (e);
 341       map->size--;
 342       return GNUNET_YES;
 343     }
 344     p = e;
 345     e = e->next;
 346   }
 347   return GNUNET_NO;
 348 }
 349
 350
 351 /**
 352  * Remove all entries for the given key from the map.
 353  * Note that the values would not be "freed".
 354  *
 355  * @param map the map
 356  * @param key identifies values to be removed
 357  * @return number of values removed
 358  */
 359 int
 360 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 361                                             uint32_t key)
 362 {
 363   struct MapEntry *e;
 364   struct MapEntry *p;
 365   unsigned int i;
 366   int ret;
 367
 368   map->modification_counter++;
 369
 370   ret = 0;
 371   i = idx_of (map, key);
 372   p = NULL;
 373   e = map->map[i];
 374   while (e != NULL)
 375   {
 376     if (key == e->key)
 377     {
 378       if (p == NULL)
 379         map->map[i] = e->next;
 380       else
 381         p->next = e->next;
 382       update_next_cache (map,
 383                          e);
 384       GNUNET_free (e);
 385       map->size--;
 386       if (p == NULL)
 387         e = map->map[i];
 388       else
 389         e = p->next;
 390       ret++;
 391     }
 392     else
 393     {
 394       p = e;
 395       e = e->next;
 396     }
 397   }
 398   return ret;
 399 }
 400
 401
 402 /**
 403  * Check if the map contains any value under the given
 404  * key (including values that are NULL).
 405  *
 406  * @param map the map
 407  * @param key the key to test if a value exists for it
 408  * @return #GNUNET_YES if such a value exists,
 409  *         #GNUNET_NO if not
 410  */
 411 int
 412 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 413                                           uint32_t key)
 414 {
 415   struct MapEntry *e;
 416
 417   e = map->map[idx_of (map, key)];
 418   while (e != NULL)
 419   {
 420     if (key == e->key)
 421       return GNUNET_YES;
 422     e = e->next;
 423   }
 424   return GNUNET_NO;
 425 }
 426
 427
 428 /**
 429  * Check if the map contains the given value under the given
 430  * key.
 431  *
 432  * @param map the map
 433  * @param key the key to test if a value exists for it
 434  * @param value value to test for
 435  * @return #GNUNET_YES if such a value exists,
 436  *         #GNUNET_NO if not
 437  */
 438 int
 439 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 440                                                 uint32_t key,
 441                                                 const void *value)
 442 {
 443   struct MapEntry *e;
 444
 445   e = map->map[idx_of (map, key)];
 446   while (e != NULL)
 447   {
 448     if ( (key == e->key) && (e->value == value) )
 449       return GNUNET_YES;
 450     e = e->next;
 451   }
 452   return GNUNET_NO;
 453 }
 454
 455
 456 /**
 457  * Grow the given map to a more appropriate size.
 458  *
 459  * @param map the hash map to grow
 460  */
 461 static void
 462 grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
 463 {
 464   struct MapEntry **old_map;
 465   struct MapEntry **new_map;
 466   struct MapEntry *e;
 467   unsigned int old_len;
 468   unsigned int new_len;
 469   unsigned int idx;
 470
 471   old_map = map->map;
 472   old_len = map->map_length;
 473   new_len = old_len * 2;
 474   if (0 == new_len) /* 2^31 * 2 == 0 */
 475     new_len = old_len; /* never use 0 */
 476   if (new_len == old_len)
 477     return; /* nothing changed */
 478   new_map = GNUNET_malloc_large (new_len *
 479                                  sizeof (struct MapEntry *));
 480   if (NULL == new_map)
 481     return; /* grow not possible */
 482   map->modification_counter++;
 483   map->map_length = new_len;
 484   map->map = new_map;
 485   for (unsigned int i = 0; i < old_len; i++)
 486   {
 487     while (NULL != (e = old_map[i]))
 488     {
 489       old_map[i] = e->next;
 490       idx = idx_of (map, e->key);
 491       e->next = new_map[idx];
 492       new_map[idx] = e;
 493     }
 494   }
 495   GNUNET_free (old_map);
 496 }
 497
 498
 499 /**
 500  * Store a key-value pair in the map.
 501  *
 502  * @param map the map
 503  * @param key key to use
 504  * @param value value to use
 505  * @param opt options for put
 506  * @return #GNUNET_OK on success,
 507  *         #GNUNET_NO if a value was replaced (with REPLACE)
 508  *         #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 509  *                       value already exists
 510  */
 511 int
 512 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
 513                                      *map, uint32_t key, void *value,
 514                                      enum GNUNET_CONTAINER_MultiHashMapOption
 515                                      opt)
 516 {
 517   struct MapEntry *e;
 518   unsigned int i;
 519
 520   i = idx_of (map, key);
 521   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 522       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 523   {
 524     e = map->map[i];
 525     while (e != NULL)
 526     {
 527       if (key == e->key)
 528       {
 529         if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 530           return GNUNET_SYSERR;
 531         e->value = value;
 532         return GNUNET_NO;
 533       }
 534       e = e->next;
 535     }
 536   }
 537   if (map->size / 3 >= map->map_length / 4)
 538   {
 539     grow (map);
 540     i = idx_of (map, key);
 541   }
 542   e = GNUNET_new (struct MapEntry);
 543   e->key = key;
 544   e->value = value;
 545   e->next = map->map[i];
 546   map->map[i] = e;
 547   map->size++;
 548   return GNUNET_OK;
 549 }
 550
 551
 552 /**
 553  * Iterate over all entries in the map that match a particular key.
 554  *
 555  * @param map the map
 556  * @param key key that the entries must correspond to
 557  * @param it function to call on each entry
 558  * @param it_cls extra argument to @a it
 559  * @return the number of key value pairs processed,
 560  *         GNUNET_SYSERR if it aborted iteration
 561  */
 562 int
 563 GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 564                                               uint32_t key,
 565                                               GNUNET_CONTAINER_HashMapIterator32 it,
 566                                               void *it_cls)
 567 {
 568   int count;
 569   struct MapEntry *e;
 570   struct MapEntry **ce;
 571
 572   count = 0;
 573   ce = &map->next_cache[map->next_cache_off];
 574   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 575
 576   *ce = map->map[idx_of (map, key)];
 577   while (NULL != (e = *ce))
 578   {
 579     *ce = e->next;
 580     if (key != e->key)
 581       continue;
 582     if ( (NULL != it) &&
 583          (GNUNET_OK != it (it_cls,
 584                            key,
 585                            e->value)) )
 586       {
 587         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 588         return GNUNET_SYSERR;
 589       }
 590     count++;
 591   }
 592   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 593   return count;
 594 }
 595
 596
 597 /**
 598  * Create an iterator for a multihashmap.
 599  * The iterator can be used to retrieve all the elements in the multihashmap
 600  * one by one, without having to handle all elements at once (in contrast to
 601  * GNUNET_CONTAINER_multihashmap_iterate()).  Note that the iterator can not be
 602  * used anymore if elements have been removed from 'map' after the creation of
 603  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
 604  * result in skipped or repeated elements.
 605  *
 606  * @param map the map to create an iterator for
 607  * @return an iterator over the given multihashmap @a map
 608  */
 609 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
 610 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 611 {
 612   struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter;
 613
 614   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32Iterator);
 615   iter->map = map;
 616   iter->modification_counter = map->modification_counter;
 617   iter->me = map->map[0];
 618   return iter;
 619 }
 620
 621
 622 /**
 623  * Retrieve the next element from the hash map at the iterator's position.
 624  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
 625  * are not modified.
 626  * This operation is only allowed if no elements have been removed from the
 627  * multihashmap since the creation of 'iter', and the map has not been destroyed.
 628  * Adding elements may result in repeating or skipping elements.
 629  *
 630  * @param iter the iterator to get the next element from
 631  * @param key pointer to store the key in, can be NULL
 632  * @param value pointer to store the value in, can be NULL
 633  * @return #GNUNET_YES we returned an element,
 634  *         #GNUNET_NO if we are out of elements
 635  */
 636 int
 637 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
 638                                                uint32_t *key,
 639                                                const void **value)
 640 {
 641   /* make sure the map has not been modified */
 642   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
 643
 644   /* look for the next entry, skipping empty buckets */
 645   while (1)
 646   {
 647     if (iter->idx >= iter->map->map_length)
 648       return GNUNET_NO;
 649     if (NULL != iter->me)
 650     {
 651       if (NULL != key)
 652         *key = iter->me->key;
 653       if (NULL != value)
 654         *value = iter->me->value;
 655       iter->me = iter->me->next;
 656       return GNUNET_YES;
 657     }
 658     iter->idx += 1;
 659     if (iter->idx < iter->map->map_length)
 660       iter->me = iter->map->map[iter->idx];
 661   }
 662 }
 663
 664
 665 /**
 666  * Destroy a multihashmap iterator.
 667  *
 668  * @param iter the iterator to destroy
 669  */
 670 void
 671 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
 672 {
 673   GNUNET_free (iter);
 674 }
 675
 676
 677 /* end of container_multihashmap.c */