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   /**
  50    * Key for the entry.
  51    */
  52   uint32_t key;
  53
  54   /**
  55    * Value of the entry.
  56    */
  57   void *value;
  58
  59   /**
  60    * If there is a hash collision, we create a linked list.
  61    */
  62   struct MapEntry *next;
  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 * sizeof (struct MapEntry *));
 150   if (NULL == ret->map)
 151   {
 152     GNUNET_free (ret);
 153     return NULL;
 154   }
 155   ret->map_length = len;
 156   return ret;
 157 }
 158
 159
 160 /**
 161  * Destroy a hash map.  Will not free any values
 162  * stored in the hash map!
 163  *
 164  * @param map the map
 165  */
 166 void
 167 GNUNET_CONTAINER_multihashmap32_destroy (
 168   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, const uint32_t key)
 194 {
 195   GNUNET_assert (NULL != m);
 196   return ((unsigned int) key) % m->map_length;
 197 }
 198
 199
 200 /**
 201  * Get the number of key-value pairs in the map.
 202  *
 203  * @param map the map
 204  * @return the number of key value pairs
 205  */
 206 unsigned int
 207 GNUNET_CONTAINER_multihashmap32_size (
 208   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 (
 226   const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 227   uint32_t key)
 228 {
 229   struct MapEntry *e;
 230
 231   e = map->map[idx_of (map, key)];
 232   while (NULL != e)
 233   {
 234     if (key == e->key)
 235       return e->value;
 236     e = e->next;
 237   }
 238   return NULL;
 239 }
 240
 241
 242 /**
 243  * Iterate over all entries in the map.
 244  *
 245  * @param map the map
 246  * @param it function to call on each entry
 247  * @param it_cls extra argument to @a it
 248  * @return the number of key value pairs processed,
 249  *         #GNUNET_SYSERR if it aborted iteration
 250  */
 251 int
 252 GNUNET_CONTAINER_multihashmap32_iterate (
 253   struct GNUNET_CONTAINER_MultiHashMap32 *map,
 254   GNUNET_CONTAINER_MulitHashMapIterator32Callback it,
 255   void *it_cls)
 256 {
 257   int count;
 258   struct MapEntry **ce;
 259
 260   count = 0;
 261   GNUNET_assert (NULL != map);
 262   ce = &map->next_cache[map->next_cache_off];
 263   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 264   for (unsigned int i = 0; i < map->map_length; i++)
 265   {
 266     struct MapEntry *e;
 267
 268     *ce = map->map[i];
 269     while (NULL != (e = *ce))
 270     {
 271       *ce = e->next;
 272       if (NULL != it)
 273       {
 274         if (GNUNET_OK != it (it_cls, e->key, 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 (
 318   struct GNUNET_CONTAINER_MultiHashMap32 *map,
 319   uint32_t key,
 320   const void *value)
 321 {
 322   struct MapEntry *e;
 323   struct MapEntry *p;
 324   unsigned int i;
 325
 326   map->modification_counter++;
 327
 328   i = idx_of (map, key);
 329   p = NULL;
 330   e = map->map[i];
 331   while (e != NULL)
 332   {
 333     if ((key == e->key) && (value == e->value))
 334     {
 335       if (p == NULL)
 336         map->map[i] = e->next;
 337       else
 338         p->next = e->next;
 339       update_next_cache (map, 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 (
 361   struct GNUNET_CONTAINER_MultiHashMap32 *map,
 362   uint32_t key)
 363 {
 364   struct MapEntry *e;
 365   struct MapEntry *p;
 366   unsigned int i;
 367   int ret;
 368
 369   map->modification_counter++;
 370
 371   ret = 0;
 372   i = idx_of (map, key);
 373   p = NULL;
 374   e = map->map[i];
 375   while (e != NULL)
 376   {
 377     if (key == e->key)
 378     {
 379       if (p == NULL)
 380         map->map[i] = e->next;
 381       else
 382         p->next = e->next;
 383       update_next_cache (map, 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 (
 413   const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 414   uint32_t key)
 415 {
 416   struct MapEntry *e;
 417
 418   e = map->map[idx_of (map, key)];
 419   while (e != NULL)
 420   {
 421     if (key == e->key)
 422       return GNUNET_YES;
 423     e = e->next;
 424   }
 425   return GNUNET_NO;
 426 }
 427
 428
 429 /**
 430  * Check if the map contains the given value under the given
 431  * key.
 432  *
 433  * @param map the map
 434  * @param key the key to test if a value exists for it
 435  * @param value value to test for
 436  * @return #GNUNET_YES if such a value exists,
 437  *         #GNUNET_NO if not
 438  */
 439 int
 440 GNUNET_CONTAINER_multihashmap32_contains_value (
 441   const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 442   uint32_t key,
 443   const void *value)
 444 {
 445   struct MapEntry *e;
 446
 447   e = map->map[idx_of (map, key)];
 448   while (e != NULL)
 449   {
 450     if ((key == e->key) && (e->value == value))
 451       return GNUNET_YES;
 452     e = e->next;
 453   }
 454   return GNUNET_NO;
 455 }
 456
 457
 458 /**
 459  * Grow the given map to a more appropriate size.
 460  *
 461  * @param map the hash map to grow
 462  */
 463 static void
 464 grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
 465 {
 466   struct MapEntry **old_map;
 467   struct MapEntry **new_map;
 468   struct MapEntry *e;
 469   unsigned int old_len;
 470   unsigned int new_len;
 471   unsigned int idx;
 472
 473   old_map = map->map;
 474   old_len = map->map_length;
 475   new_len = old_len * 2;
 476   if (0 == new_len) /* 2^31 * 2 == 0 */
 477     new_len = old_len; /* never use 0 */
 478   if (new_len == old_len)
 479     return; /* nothing changed */
 480   new_map = GNUNET_malloc_large (new_len * sizeof (struct MapEntry *));
 481   if (NULL == new_map)
 482     return; /* grow not possible */
 483   map->modification_counter++;
 484   map->map_length = new_len;
 485   map->map = new_map;
 486   for (unsigned int i = 0; i < old_len; i++)
 487   {
 488     while (NULL != (e = old_map[i]))
 489     {
 490       old_map[i] = e->next;
 491       idx = idx_of (map, e->key);
 492       e->next = new_map[idx];
 493       new_map[idx] = e;
 494     }
 495   }
 496   GNUNET_free (old_map);
 497 }
 498
 499
 500 /**
 501  * Store a key-value pair in the map.
 502  *
 503  * @param map the map
 504  * @param key key to use
 505  * @param value value to use
 506  * @param opt options for put
 507  * @return #GNUNET_OK on success,
 508  *         #GNUNET_NO if a value was replaced (with REPLACE)
 509  *         #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 510  *                       value already exists
 511  */
 512 int
 513 GNUNET_CONTAINER_multihashmap32_put (
 514   struct GNUNET_CONTAINER_MultiHashMap32 *map,
 515   uint32_t key,
 516   void *value,
 517   enum GNUNET_CONTAINER_MultiHashMapOption opt)
 518 {
 519   struct MapEntry *e;
 520   unsigned int i;
 521
 522   i = idx_of (map, key);
 523   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 524       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 525   {
 526     e = map->map[i];
 527     while (e != NULL)
 528     {
 529       if (key == e->key)
 530       {
 531         if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 532           return GNUNET_SYSERR;
 533         e->value = value;
 534         return GNUNET_NO;
 535       }
 536       e = e->next;
 537     }
 538   }
 539   if (map->size / 3 >= map->map_length / 4)
 540   {
 541     grow (map);
 542     i = idx_of (map, key);
 543   }
 544   e = GNUNET_new (struct MapEntry);
 545   e->key = key;
 546   e->value = value;
 547   e->next = map->map[i];
 548   map->map[i] = e;
 549   map->size++;
 550   return GNUNET_OK;
 551 }
 552
 553
 554 /**
 555  * Iterate over all entries in the map that match a particular key.
 556  *
 557  * @param map the map
 558  * @param key key that the entries must correspond to
 559  * @param it function to call on each entry
 560  * @param it_cls extra argument to @a it
 561  * @return the number of key value pairs processed,
 562  *         GNUNET_SYSERR if it aborted iteration
 563  */
 564 int
 565 GNUNET_CONTAINER_multihashmap32_get_multiple (
 566   struct GNUNET_CONTAINER_MultiHashMap32 *map,
 567   uint32_t key,
 568   GNUNET_CONTAINER_MulitHashMapIterator32Callback it,
 569   void *it_cls)
 570 {
 571   int count;
 572   struct MapEntry *e;
 573   struct MapEntry **ce;
 574
 575   count = 0;
 576   ce = &map->next_cache[map->next_cache_off];
 577   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 578
 579   *ce = map->map[idx_of (map, key)];
 580   while (NULL != (e = *ce))
 581   {
 582     *ce = e->next;
 583     if (key != e->key)
 584       continue;
 585     if ((NULL != it) && (GNUNET_OK != it (it_cls, key, 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 (
 611   const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 612 {
 613   struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter;
 614
 615   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32Iterator);
 616   iter->map = map;
 617   iter->modification_counter = map->modification_counter;
 618   iter->me = map->map[0];
 619   return iter;
 620 }
 621
 622
 623 /**
 624  * Retrieve the next element from the hash map at the iterator's position.
 625  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
 626  * are not modified.
 627  * This operation is only allowed if no elements have been removed from the
 628  * multihashmap since the creation of 'iter', and the map has not been destroyed.
 629  * Adding elements may result in repeating or skipping elements.
 630  *
 631  * @param iter the iterator to get the next element from
 632  * @param key pointer to store the key in, can be NULL
 633  * @param value pointer to store the value in, can be NULL
 634  * @return #GNUNET_YES we returned an element,
 635  *         #GNUNET_NO if we are out of elements
 636  */
 637 int
 638 GNUNET_CONTAINER_multihashmap32_iterator_next (
 639   struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
 640   uint32_t *key,
 641   const void **value)
 642 {
 643   /* make sure the map has not been modified */
 644   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
 645
 646   /* look for the next entry, skipping empty buckets */
 647   while (1)
 648   {
 649     if (iter->idx >= iter->map->map_length)
 650       return GNUNET_NO;
 651     if (NULL != iter->me)
 652     {
 653       if (NULL != key)
 654         *key = iter->me->key;
 655       if (NULL != value)
 656         *value = iter->me->value;
 657       iter->me = iter->me->next;
 658       return GNUNET_YES;
 659     }
 660     iter->idx += 1;
 661     if (iter->idx < iter->map->map_length)
 662       iter->me = iter->map->map[iter->idx];
 663   }
 664 }
 665
 666
 667 /**
 668  * Destroy a multihashmap iterator.
 669  *
 670  * @param iter the iterator to destroy
 671  */
 672 void
 673 GNUNET_CONTAINER_multihashmap32_iterator_destroy (
 674   struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
 675 {
 676   GNUNET_free (iter);
 677 }
 678
 679
 680 /* end of container_multihashmap.c */