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