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_new_array (len,
 150                                struct MapEntry *);
 151   ret->map_length = len;
 152   return ret;
 153 }
 154
 155
 156 /**
 157  * Destroy a hash map.  Will not free any values
 158  * stored in the hash map!
 159  *
 160  * @param map the map
 161  */
 162 void
 163 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *map)
 164 {
 165   struct MapEntry *e;
 166
 167   for (unsigned int i = 0; i < map->map_length; i++)
 168   {
 169     while (NULL != (e = map->map[i]))
 170     {
 171       map->map[i] = e->next;
 172       GNUNET_free (e);
 173     }
 174   }
 175   GNUNET_free (map->map);
 176   GNUNET_free (map);
 177 }
 178
 179
 180 /**
 181  * Compute the index of the bucket for the given key.
 182  *
 183  * @param m hash map for which to compute the index
 184  * @param key what key should the index be computed for
 185  * @return offset into the "map" array of "m"
 186  */
 187 static unsigned int
 188 idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m,
 189         const uint32_t key)
 190 {
 191   GNUNET_assert (NULL != m);
 192   return ((unsigned int) key) % m->map_length;
 193 }
 194
 195
 196 /**
 197  * Get the number of key-value pairs in the map.
 198  *
 199  * @param map the map
 200  * @return the number of key value pairs
 201  */
 202 unsigned int
 203 GNUNET_CONTAINER_multihashmap32_size (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 204 {
 205   return map->size;
 206 }
 207
 208
 209 /**
 210  * Given a key find a value in the map matching the key.
 211  *
 212  * @param map the map
 213  * @param key what to look for
 214  * @return NULL if no value was found; note that
 215  *   this is indistinguishable from values that just
 216  *   happen to be NULL; use "contains" to test for
 217  *   key-value pairs with value NULL
 218  */
 219 void *
 220 GNUNET_CONTAINER_multihashmap32_get (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 221                                      uint32_t key)
 222 {
 223   struct MapEntry *e;
 224
 225   e = map->map[idx_of (map, key)];
 226   while (NULL != e)
 227   {
 228     if (key == e->key)
 229       return e->value;
 230     e = e->next;
 231   }
 232   return NULL;
 233 }
 234
 235
 236 /**
 237  * Iterate over all entries in the map.
 238  *
 239  * @param map the map
 240  * @param it function to call on each entry
 241  * @param it_cls extra argument to @a it
 242  * @return the number of key value pairs processed,
 243  *         #GNUNET_SYSERR if it aborted iteration
 244  */
 245 int
 246 GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 247                                          GNUNET_CONTAINER_HashMapIterator32 it,
 248                                          void *it_cls)
 249 {
 250   int count;
 251   struct MapEntry **ce;
 252
 253   count = 0;
 254   GNUNET_assert (NULL != map);
 255   ce = &map->next_cache[map->next_cache_off];
 256   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 257   for (unsigned int i = 0; i < map->map_length; i++)
 258   {
 259     struct MapEntry *e;
 260
 261     *ce = map->map[i];
 262     while (NULL != (e = *ce))
 263     {
 264       *ce = e->next;
 265       if (NULL != it)
 266       {
 267         if (GNUNET_OK != it (it_cls,
 268                              e->key,
 269                              e->value))
 270         {
 271           GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 272           return GNUNET_SYSERR;
 273         }
 274       }
 275       count++;
 276     }
 277   }
 278   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 279   return count;
 280 }
 281
 282
 283 /**
 284  * We are about to free() the @a bme, make sure it is not in
 285  * the list of next values for any iterator in the @a map's next_cache.
 286  *
 287  * @param map the map to check
 288  * @param bme the entry that is about to be free'd
 289  */
 290 static void
 291 update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 292                    const struct MapEntry *me)
 293 {
 294   for (unsigned int i=0;i<map->next_cache_off;i++)
 295     if (map->next_cache[i] == me)
 296       map->next_cache[i] = me->next;
 297 }
 298
 299
 300 /**
 301  * Remove the given key-value pair from the map.  Note that if the
 302  * key-value pair is in the map multiple times, only one of the pairs
 303  * will be removed.
 304  *
 305  * @param map the map
 306  * @param key key of the key-value pair
 307  * @param value value of the key-value pair
 308  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
 309  *  is not in the map
 310  */
 311 int
 312 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 313                                         uint32_t key,
 314                                         const void *value)
 315 {
 316   struct MapEntry *e;
 317   struct MapEntry *p;
 318   unsigned int i;
 319
 320   map->modification_counter++;
 321
 322   i = idx_of (map, key);
 323   p = NULL;
 324   e = map->map[i];
 325   while (e != NULL)
 326   {
 327     if ( (key == e->key) && (value == e->value) )
 328     {
 329       if (p == NULL)
 330         map->map[i] = e->next;
 331       else
 332         p->next = e->next;
 333       update_next_cache (map,
 334                          e);
 335       GNUNET_free (e);
 336       map->size--;
 337       return GNUNET_YES;
 338     }
 339     p = e;
 340     e = e->next;
 341   }
 342   return GNUNET_NO;
 343 }
 344
 345
 346 /**
 347  * Remove all entries for the given key from the map.
 348  * Note that the values would not be "freed".
 349  *
 350  * @param map the map
 351  * @param key identifies values to be removed
 352  * @return number of values removed
 353  */
 354 int
 355 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 356                                             uint32_t key)
 357 {
 358   struct MapEntry *e;
 359   struct MapEntry *p;
 360   unsigned int i;
 361   int ret;
 362
 363   map->modification_counter++;
 364
 365   ret = 0;
 366   i = idx_of (map, key);
 367   p = NULL;
 368   e = map->map[i];
 369   while (e != NULL)
 370   {
 371     if (key == e->key)
 372     {
 373       if (p == NULL)
 374         map->map[i] = e->next;
 375       else
 376         p->next = e->next;
 377       update_next_cache (map,
 378                          e);
 379       GNUNET_free (e);
 380       map->size--;
 381       if (p == NULL)
 382         e = map->map[i];
 383       else
 384         e = p->next;
 385       ret++;
 386     }
 387     else
 388     {
 389       p = e;
 390       e = e->next;
 391     }
 392   }
 393   return ret;
 394 }
 395
 396
 397 /**
 398  * Check if the map contains any value under the given
 399  * key (including values that are NULL).
 400  *
 401  * @param map the map
 402  * @param key the key to test if a value exists for it
 403  * @return #GNUNET_YES if such a value exists,
 404  *         #GNUNET_NO if not
 405  */
 406 int
 407 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 408                                           uint32_t key)
 409 {
 410   struct MapEntry *e;
 411
 412   e = map->map[idx_of (map, key)];
 413   while (e != NULL)
 414   {
 415     if (key == e->key)
 416       return GNUNET_YES;
 417     e = e->next;
 418   }
 419   return GNUNET_NO;
 420 }
 421
 422
 423 /**
 424  * Check if the map contains the given value under the given
 425  * key.
 426  *
 427  * @param map the map
 428  * @param key the key to test if a value exists for it
 429  * @param value value to test for
 430  * @return #GNUNET_YES if such a value exists,
 431  *         #GNUNET_NO if not
 432  */
 433 int
 434 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 435                                                 uint32_t key,
 436                                                 const void *value)
 437 {
 438   struct MapEntry *e;
 439
 440   e = map->map[idx_of (map, key)];
 441   while (e != NULL)
 442   {
 443     if ( (key == e->key) && (e->value == value) )
 444       return GNUNET_YES;
 445     e = e->next;
 446   }
 447   return GNUNET_NO;
 448 }
 449
 450
 451 /**
 452  * Grow the given map to a more appropriate size.
 453  *
 454  * @param map the hash map to grow
 455  */
 456 static void
 457 grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
 458 {
 459   struct MapEntry **old_map;
 460   struct MapEntry **new_map;
 461   struct MapEntry *e;
 462   unsigned int old_len;
 463   unsigned int new_len;
 464   unsigned int idx;
 465
 466   map->modification_counter++;
 467
 468   old_map = map->map;
 469   old_len = map->map_length;
 470   new_len = old_len * 2;
 471   new_map = GNUNET_new_array (new_len,
 472                               struct MapEntry *);
 473   map->map_length = new_len;
 474   map->map = new_map;
 475   for (unsigned int i = 0; i < old_len; i++)
 476   {
 477     while (NULL != (e = old_map[i]))
 478     {
 479       old_map[i] = e->next;
 480       idx = idx_of (map, e->key);
 481       e->next = new_map[idx];
 482       new_map[idx] = e;
 483     }
 484   }
 485   GNUNET_free (old_map);
 486 }
 487
 488
 489 /**
 490  * Store a key-value pair in the map.
 491  *
 492  * @param map the map
 493  * @param key key to use
 494  * @param value value to use
 495  * @param opt options for put
 496  * @return #GNUNET_OK on success,
 497  *         #GNUNET_NO if a value was replaced (with REPLACE)
 498  *         #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 499  *                       value already exists
 500  */
 501 int
 502 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
 503                                      *map, uint32_t key, void *value,
 504                                      enum GNUNET_CONTAINER_MultiHashMapOption
 505                                      opt)
 506 {
 507   struct MapEntry *e;
 508   unsigned int i;
 509
 510   i = idx_of (map, key);
 511   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 512       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 513   {
 514     e = map->map[i];
 515     while (e != NULL)
 516     {
 517       if (key == e->key)
 518       {
 519         if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 520           return GNUNET_SYSERR;
 521         e->value = value;
 522         return GNUNET_NO;
 523       }
 524       e = e->next;
 525     }
 526   }
 527   if (map->size / 3 >= map->map_length / 4)
 528   {
 529     grow (map);
 530     i = idx_of (map, key);
 531   }
 532   e = GNUNET_new (struct MapEntry);
 533   e->key = key;
 534   e->value = value;
 535   e->next = map->map[i];
 536   map->map[i] = e;
 537   map->size++;
 538   return GNUNET_OK;
 539 }
 540
 541
 542 /**
 543  * Iterate over all entries in the map that match a particular key.
 544  *
 545  * @param map the map
 546  * @param key key that the entries must correspond to
 547  * @param it function to call on each entry
 548  * @param it_cls extra argument to @a it
 549  * @return the number of key value pairs processed,
 550  *         GNUNET_SYSERR if it aborted iteration
 551  */
 552 int
 553 GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 554                                               uint32_t key,
 555                                               GNUNET_CONTAINER_HashMapIterator32 it,
 556                                               void *it_cls)
 557 {
 558   int count;
 559   struct MapEntry *e;
 560   struct MapEntry **ce;
 561
 562   count = 0;
 563   ce = &map->next_cache[map->next_cache_off];
 564   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 565
 566   *ce = map->map[idx_of (map, key)];
 567   while (NULL != (e = *ce))
 568   {
 569     *ce = e->next;
 570     if (key != e->key)
 571       continue;
 572     if ( (NULL != it) &&
 573          (GNUNET_OK != it (it_cls,
 574                            key,
 575                            e->value)) )
 576       {
 577         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 578         return GNUNET_SYSERR;
 579       }
 580     count++;
 581   }
 582   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 583   return count;
 584 }
 585
 586
 587 /**
 588  * Create an iterator for a multihashmap.
 589  * The iterator can be used to retrieve all the elements in the multihashmap
 590  * one by one, without having to handle all elements at once (in contrast to
 591  * GNUNET_CONTAINER_multihashmap_iterate()).  Note that the iterator can not be
 592  * used anymore if elements have been removed from 'map' after the creation of
 593  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
 594  * result in skipped or repeated elements.
 595  *
 596  * @param map the map to create an iterator for
 597  * @return an iterator over the given multihashmap @a map
 598  */
 599 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
 600 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 601 {
 602   struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter;
 603
 604   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32Iterator);
 605   iter->map = map;
 606   iter->modification_counter = map->modification_counter;
 607   iter->me = map->map[0];
 608   return iter;
 609 }
 610
 611
 612 /**
 613  * Retrieve the next element from the hash map at the iterator's position.
 614  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
 615  * are not modified.
 616  * This operation is only allowed if no elements have been removed from the
 617  * multihashmap since the creation of 'iter', and the map has not been destroyed.
 618  * Adding elements may result in repeating or skipping elements.
 619  *
 620  * @param iter the iterator to get the next element from
 621  * @param key pointer to store the key in, can be NULL
 622  * @param value pointer to store the value in, can be NULL
 623  * @return #GNUNET_YES we returned an element,
 624  *         #GNUNET_NO if we are out of elements
 625  */
 626 int
 627 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
 628                                                uint32_t *key,
 629                                                const void **value)
 630 {
 631   /* make sure the map has not been modified */
 632   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
 633
 634   /* look for the next entry, skipping empty buckets */
 635   while (1)
 636   {
 637     if (iter->idx >= iter->map->map_length)
 638       return GNUNET_NO;
 639     if (NULL != iter->me)
 640     {
 641       if (NULL != key)
 642         *key = iter->me->key;
 643       if (NULL != value)
 644         *value = iter->me->value;
 645       iter->me = iter->me->next;
 646       return GNUNET_YES;
 647     }
 648     iter->idx += 1;
 649     if (iter->idx < iter->map->map_length)
 650       iter->me = iter->map->map[iter->idx];
 651   }
 652 }
 653
 654
 655 /**
 656  * Destroy a multihashmap iterator.
 657  *
 658  * @param iter the iterator to destroy
 659  */
 660 void
 661 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
 662 {
 663   GNUNET_free (iter);
 664 }
 665
 666
 667 /* end of container_multihashmap.c */