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, ...) \
  32   GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__)
  33
  34
  35 /**
  36  * Maximum recursion depth for callbacks of
  37  * #GNUNET_CONTAINER_multihashmap_get_multiple() themselves
  38  * again calling #GNUNET_CONTAINER_multihashmap_get_multiple().
  39  * Should be totally excessive, but if violated we die.
  40  */
  41 #define NEXT_CACHE_SIZE 16
  42
  43 /**
  44  * An entry in the hash map.
  45  */
  46 struct MapEntry
  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  * Internal representation of the hash map.
  66  */
  67 struct GNUNET_CONTAINER_MultiHashMap32
  68 {
  69   /**
  70    * All of our buckets.
  71    */
  72   struct MapEntry **map;
  73
  74   /**
  75    * Number of entries in the map.
  76    */
  77   unsigned int size;
  78
  79   /**
  80    * Length of the @e map array.
  81    */
  82   unsigned int map_length;
  83
  84   /**
  85    * Counts the destructive modifications (grow, remove)
  86    * to the map, so that iterators can check if they are still valid.
  87    */
  88   unsigned int modification_counter;
  89
  90   /**
  91    * Map entries indicating iteration positions currently
  92    * in use by #GNUNET_CONTAINER_multihashmap_get_multiple().
  93    * Only used up to @e next_cache_off.
  94    */
  95   struct MapEntry *next_cache[NEXT_CACHE_SIZE];
  96
  97   /**
  98    * Offset of @e next_cache entries in use, must be smaller
  99    * than #NEXT_CACHE_SIZE.
 100    */
 101   unsigned int next_cache_off;
 102 };
 103
 104
 105 /**
 106  * Cursor into a multihashmap.
 107  * Allows to enumerate elements asynchronously.
 108  */
 109 struct GNUNET_CONTAINER_MultiHashMap32Iterator
 110 {
 111   /**
 112    * Position in the bucket @e idx
 113    */
 114   struct MapEntry *me;
 115
 116   /**
 117    * Current bucket index.
 118    */
 119   unsigned int idx;
 120
 121   /**
 122    * Modification counter as observed on the map when the iterator
 123    * was created.
 124    */
 125   unsigned int modification_counter;
 126
 127   /**
 128    * Map that we are iterating over.
 129    */
 130   const struct GNUNET_CONTAINER_MultiHashMap32 *map;
 131 };
 132
 133
 134 /**
 135  * Create a multi hash map.
 136  *
 137  * @param len initial size (map will grow as needed)
 138  * @return NULL on error
 139  */
 140 struct GNUNET_CONTAINER_MultiHashMap32 *
 141 GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
 142 {
 143   struct GNUNET_CONTAINER_MultiHashMap32 *ret;
 144
 145   GNUNET_assert (len > 0);
 146   ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32);
 147   ret->map = GNUNET_malloc_large (len * sizeof(struct MapEntry *));
 148   if (NULL == ret->map)
 149   {
 150     GNUNET_free (ret);
 151     return NULL;
 152   }
 153   ret->map_length = len;
 154   return ret;
 155 }
 156
 157
 158 /**
 159  * Destroy a hash map.  Will not free any values
 160  * stored in the hash map!
 161  *
 162  * @param map the map
 163  */
 164 void
 165 GNUNET_CONTAINER_multihashmap32_destroy (
 166   struct GNUNET_CONTAINER_MultiHashMap32 *map)
 167 {
 168   struct MapEntry *e;
 169
 170   for (unsigned int i = 0; i < map->map_length; i++)
 171   {
 172     while (NULL != (e = map->map[i]))
 173     {
 174       map->map[i] = e->next;
 175       GNUNET_free (e);
 176     }
 177   }
 178   GNUNET_free (map->map);
 179   GNUNET_free (map);
 180 }
 181
 182
 183 /**
 184  * Compute the index of the bucket for the given key.
 185  *
 186  * @param m hash map for which to compute the index
 187  * @param key what key should the index be computed for
 188  * @return offset into the "map" array of "m"
 189  */
 190 static unsigned int
 191 idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, const uint32_t key)
 192 {
 193   GNUNET_assert (NULL != m);
 194   return ((unsigned int) key) % m->map_length;
 195 }
 196
 197
 198 /**
 199  * Get the number of key-value pairs in the map.
 200  *
 201  * @param map the map
 202  * @return the number of key value pairs
 203  */
 204 unsigned int
 205 GNUNET_CONTAINER_multihashmap32_size (
 206   const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 207 {
 208   return map->size;
 209 }
 210
 211
 212 /**
 213  * Given a key find a value in the map matching the key.
 214  *
 215  * @param map the map
 216  * @param key what to look for
 217  * @return NULL if no value was found; note that
 218  *   this is indistinguishable from values that just
 219  *   happen to be NULL; use "contains" to test for
 220  *   key-value pairs with value NULL
 221  */
 222 void *
 223 GNUNET_CONTAINER_multihashmap32_get (
 224   const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 225   uint32_t key)
 226 {
 227   struct MapEntry *e;
 228
 229   e = map->map[idx_of (map, key)];
 230   while (NULL != e)
 231   {
 232     if (key == e->key)
 233       return e->value;
 234     e = e->next;
 235   }
 236   return NULL;
 237 }
 238
 239
 240 /**
 241  * Iterate over all entries in the map.
 242  *
 243  * @param map the map
 244  * @param it function to call on each entry
 245  * @param it_cls extra argument to @a it
 246  * @return the number of key value pairs processed,
 247  *         #GNUNET_SYSERR if it aborted iteration
 248  */
 249 int
 250 GNUNET_CONTAINER_multihashmap32_iterate (
 251   struct GNUNET_CONTAINER_MultiHashMap32 *map,
 252   GNUNET_CONTAINER_MulitHashMapIterator32Callback 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, e->key, e->value))
 273         {
 274           GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 275           return GNUNET_SYSERR;
 276         }
 277       }
 278       count++;
 279     }
 280   }
 281   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 282   return count;
 283 }
 284
 285
 286 /**
 287  * We are about to free() the @a bme, make sure it is not in
 288  * the list of next values for any iterator in the @a map's next_cache.
 289  *
 290  * @param map the map to check
 291  * @param bme the entry that is about to be free'd
 292  */
 293 static void
 294 update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 295                    const struct MapEntry *me)
 296 {
 297   for (unsigned int i = 0; i < map->next_cache_off; i++)
 298     if (map->next_cache[i] == me)
 299       map->next_cache[i] = me->next;
 300 }
 301
 302
 303 /**
 304  * Remove the given key-value pair from the map.  Note that if the
 305  * key-value pair is in the map multiple times, only one of the pairs
 306  * will be removed.
 307  *
 308  * @param map the map
 309  * @param key key of the key-value pair
 310  * @param value value of the key-value pair
 311  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
 312  *  is not in the map
 313  */
 314 int
 315 GNUNET_CONTAINER_multihashmap32_remove (
 316   struct GNUNET_CONTAINER_MultiHashMap32 *map,
 317   uint32_t key,
 318   const void *value)
 319 {
 320   struct MapEntry *e;
 321   struct MapEntry *p;
 322   unsigned int i;
 323
 324   map->modification_counter++;
 325
 326   i = idx_of (map, key);
 327   p = NULL;
 328   e = map->map[i];
 329   while (e != NULL)
 330   {
 331     if ((key == e->key) && (value == e->value))
 332     {
 333       if (p == NULL)
 334         map->map[i] = e->next;
 335       else
 336         p->next = e->next;
 337       update_next_cache (map, e);
 338       GNUNET_free (e);
 339       map->size--;
 340       return GNUNET_YES;
 341     }
 342     p = e;
 343     e = e->next;
 344   }
 345   return GNUNET_NO;
 346 }
 347
 348
 349 /**
 350  * Remove all entries for the given key from the map.
 351  * Note that the values would not be "freed".
 352  *
 353  * @param map the map
 354  * @param key identifies values to be removed
 355  * @return number of values removed
 356  */
 357 int
 358 GNUNET_CONTAINER_multihashmap32_remove_all (
 359   struct GNUNET_CONTAINER_MultiHashMap32 *map,
 360   uint32_t key)
 361 {
 362   struct MapEntry *e;
 363   struct MapEntry *p;
 364   unsigned int i;
 365   int ret;
 366
 367   map->modification_counter++;
 368
 369   ret = 0;
 370   i = idx_of (map, key);
 371   p = NULL;
 372   e = map->map[i];
 373   while (e != NULL)
 374   {
 375     if (key == e->key)
 376     {
 377       if (p == NULL)
 378         map->map[i] = e->next;
 379       else
 380         p->next = e->next;
 381       update_next_cache (map, e);
 382       GNUNET_free (e);
 383       map->size--;
 384       if (p == NULL)
 385         e = map->map[i];
 386       else
 387         e = p->next;
 388       ret++;
 389     }
 390     else
 391     {
 392       p = e;
 393       e = e->next;
 394     }
 395   }
 396   return ret;
 397 }
 398
 399
 400 /**
 401  * Check if the map contains any value under the given
 402  * key (including values that are NULL).
 403  *
 404  * @param map the map
 405  * @param key the key to test if a value exists for it
 406  * @return #GNUNET_YES if such a value exists,
 407  *         #GNUNET_NO if not
 408  */
 409 int
 410 GNUNET_CONTAINER_multihashmap32_contains (
 411   const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 412   uint32_t key)
 413 {
 414   struct MapEntry *e;
 415
 416   e = map->map[idx_of (map, key)];
 417   while (e != NULL)
 418   {
 419     if (key == e->key)
 420       return GNUNET_YES;
 421     e = e->next;
 422   }
 423   return GNUNET_NO;
 424 }
 425
 426
 427 /**
 428  * Check if the map contains the given value under the given
 429  * key.
 430  *
 431  * @param map the map
 432  * @param key the key to test if a value exists for it
 433  * @param value value to test for
 434  * @return #GNUNET_YES if such a value exists,
 435  *         #GNUNET_NO if not
 436  */
 437 int
 438 GNUNET_CONTAINER_multihashmap32_contains_value (
 439   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 * sizeof(struct MapEntry *));
 479   if (NULL == new_map)
 480     return; /* grow not possible */
 481   map->modification_counter++;
 482   map->map_length = new_len;
 483   map->map = new_map;
 484   for (unsigned int i = 0; i < old_len; i++)
 485   {
 486     while (NULL != (e = old_map[i]))
 487     {
 488       old_map[i] = e->next;
 489       idx = idx_of (map, e->key);
 490       e->next = new_map[idx];
 491       new_map[idx] = e;
 492     }
 493   }
 494   GNUNET_free (old_map);
 495 }
 496
 497
 498 /**
 499  * Store a key-value pair in the map.
 500  *
 501  * @param map the map
 502  * @param key key to use
 503  * @param value value to use
 504  * @param opt options for put
 505  * @return #GNUNET_OK on success,
 506  *         #GNUNET_NO if a value was replaced (with REPLACE)
 507  *         #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 508  *                       value already exists
 509  */
 510 int
 511 GNUNET_CONTAINER_multihashmap32_put (
 512   struct GNUNET_CONTAINER_MultiHashMap32 *map,
 513   uint32_t key,
 514   void *value,
 515   enum GNUNET_CONTAINER_MultiHashMapOption 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 (
 564   struct GNUNET_CONTAINER_MultiHashMap32 *map,
 565   uint32_t key,
 566   GNUNET_CONTAINER_MulitHashMapIterator32Callback it,
 567   void *it_cls)
 568 {
 569   int count;
 570   struct MapEntry *e;
 571   struct MapEntry **ce;
 572
 573   count = 0;
 574   ce = &map->next_cache[map->next_cache_off];
 575   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 576
 577   *ce = map->map[idx_of (map, key)];
 578   while (NULL != (e = *ce))
 579   {
 580     *ce = e->next;
 581     if (key != e->key)
 582       continue;
 583     if ((NULL != it) && (GNUNET_OK != it (it_cls, key, e->value)))
 584     {
 585       GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 586       return GNUNET_SYSERR;
 587     }
 588     count++;
 589   }
 590   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
 591   return count;
 592 }
 593
 594
 595 /**
 596  * Create an iterator for a multihashmap.
 597  * The iterator can be used to retrieve all the elements in the multihashmap
 598  * one by one, without having to handle all elements at once (in contrast to
 599  * GNUNET_CONTAINER_multihashmap_iterate()).  Note that the iterator can not be
 600  * used anymore if elements have been removed from 'map' after the creation of
 601  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
 602  * result in skipped or repeated elements.
 603  *
 604  * @param map the map to create an iterator for
 605  * @return an iterator over the given multihashmap @a map
 606  */
 607 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
 608 GNUNET_CONTAINER_multihashmap32_iterator_create (
 609   const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 610 {
 611   struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter;
 612
 613   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32Iterator);
 614   iter->map = map;
 615   iter->modification_counter = map->modification_counter;
 616   iter->me = map->map[0];
 617   return iter;
 618 }
 619
 620
 621 /**
 622  * Retrieve the next element from the hash map at the iterator's position.
 623  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
 624  * are not modified.
 625  * This operation is only allowed if no elements have been removed from the
 626  * multihashmap since the creation of 'iter', and the map has not been destroyed.
 627  * Adding elements may result in repeating or skipping elements.
 628  *
 629  * @param iter the iterator to get the next element from
 630  * @param key pointer to store the key in, can be NULL
 631  * @param value pointer to store the value in, can be NULL
 632  * @return #GNUNET_YES we returned an element,
 633  *         #GNUNET_NO if we are out of elements
 634  */
 635 int
 636 GNUNET_CONTAINER_multihashmap32_iterator_next (
 637   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 (
 672   struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
 673 {
 674   GNUNET_free (iter);
 675 }
 676
 677
 678 /* end of container_multihashmap.c */