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           return GNUNET_SYSERR;
 269       }
 270       count++;
 271     }
 272   }
 273   return count;
 274 }
 275
 276
 277 /**
 278  * We are about to free() the @a bme, make sure it is not in
 279  * the list of next values for any iterator in the @a map's next_cache.
 280  *
 281  * @param map the map to check
 282  * @param bme the entry that is about to be free'd
 283  */
 284 static void
 285 update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 286                    const struct MapEntry *me)
 287 {
 288   for (unsigned int i=0;i<map->next_cache_off;i++)
 289     if (map->next_cache[i] == me)
 290       map->next_cache[i] = me->next;
 291 }
 292
 293
 294 /**
 295  * Remove the given key-value pair from the map.  Note that if the
 296  * key-value pair is in the map multiple times, only one of the pairs
 297  * will be removed.
 298  *
 299  * @param map the map
 300  * @param key key of the key-value pair
 301  * @param value value of the key-value pair
 302  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
 303  *  is not in the map
 304  */
 305 int
 306 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 307                                         uint32_t key,
 308                                         const void *value)
 309 {
 310   struct MapEntry *e;
 311   struct MapEntry *p;
 312   unsigned int i;
 313
 314   map->modification_counter++;
 315
 316   i = idx_of (map, key);
 317   p = NULL;
 318   e = map->map[i];
 319   while (e != NULL)
 320   {
 321     if ( (key == e->key) && (value == e->value) )
 322     {
 323       if (p == NULL)
 324         map->map[i] = e->next;
 325       else
 326         p->next = e->next;
 327       update_next_cache (map,
 328                          e);
 329       GNUNET_free (e);
 330       map->size--;
 331       return GNUNET_YES;
 332     }
 333     p = e;
 334     e = e->next;
 335   }
 336   return GNUNET_NO;
 337 }
 338
 339
 340 /**
 341  * Remove all entries for the given key from the map.
 342  * Note that the values would not be "freed".
 343  *
 344  * @param map the map
 345  * @param key identifies values to be removed
 346  * @return number of values removed
 347  */
 348 int
 349 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 350                                             uint32_t key)
 351 {
 352   struct MapEntry *e;
 353   struct MapEntry *p;
 354   unsigned int i;
 355   int ret;
 356
 357   map->modification_counter++;
 358
 359   ret = 0;
 360   i = idx_of (map, key);
 361   p = NULL;
 362   e = map->map[i];
 363   while (e != NULL)
 364   {
 365     if (key == e->key)
 366     {
 367       if (p == NULL)
 368         map->map[i] = e->next;
 369       else
 370         p->next = e->next;
 371       update_next_cache (map,
 372                          e);
 373       GNUNET_free (e);
 374       map->size--;
 375       if (p == NULL)
 376         e = map->map[i];
 377       else
 378         e = p->next;
 379       ret++;
 380     }
 381     else
 382     {
 383       p = e;
 384       e = e->next;
 385     }
 386   }
 387   return ret;
 388 }
 389
 390
 391 /**
 392  * Check if the map contains any value under the given
 393  * key (including values that are NULL).
 394  *
 395  * @param map the map
 396  * @param key the key to test if a value exists for it
 397  * @return #GNUNET_YES if such a value exists,
 398  *         #GNUNET_NO if not
 399  */
 400 int
 401 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 402                                           uint32_t key)
 403 {
 404   struct MapEntry *e;
 405
 406   e = map->map[idx_of (map, key)];
 407   while (e != NULL)
 408   {
 409     if (key == e->key)
 410       return GNUNET_YES;
 411     e = e->next;
 412   }
 413   return GNUNET_NO;
 414 }
 415
 416
 417 /**
 418  * Check if the map contains the given value under the given
 419  * key.
 420  *
 421  * @param map the map
 422  * @param key the key to test if a value exists for it
 423  * @param value value to test for
 424  * @return #GNUNET_YES if such a value exists,
 425  *         #GNUNET_NO if not
 426  */
 427 int
 428 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
 429                                                 uint32_t key,
 430                                                 const void *value)
 431 {
 432   struct MapEntry *e;
 433
 434   e = map->map[idx_of (map, key)];
 435   while (e != NULL)
 436   {
 437     if ( (key == e->key) && (e->value == value) )
 438       return GNUNET_YES;
 439     e = e->next;
 440   }
 441   return GNUNET_NO;
 442 }
 443
 444
 445 /**
 446  * Grow the given map to a more appropriate size.
 447  *
 448  * @param map the hash map to grow
 449  */
 450 static void
 451 grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
 452 {
 453   struct MapEntry **old_map;
 454   struct MapEntry **new_map;
 455   struct MapEntry *e;
 456   unsigned int old_len;
 457   unsigned int new_len;
 458   unsigned int idx;
 459
 460   map->modification_counter++;
 461
 462   old_map = map->map;
 463   old_len = map->map_length;
 464   new_len = old_len * 2;
 465   new_map = GNUNET_new_array (new_len,
 466                               struct MapEntry *);
 467   map->map_length = new_len;
 468   map->map = new_map;
 469   for (unsigned int i = 0; i < old_len; i++)
 470   {
 471     while (NULL != (e = old_map[i]))
 472     {
 473       old_map[i] = e->next;
 474       idx = idx_of (map, e->key);
 475       e->next = new_map[idx];
 476       new_map[idx] = e;
 477     }
 478   }
 479   GNUNET_free (old_map);
 480 }
 481
 482
 483 /**
 484  * Store a key-value pair in the map.
 485  *
 486  * @param map the map
 487  * @param key key to use
 488  * @param value value to use
 489  * @param opt options for put
 490  * @return #GNUNET_OK on success,
 491  *         #GNUNET_NO if a value was replaced (with REPLACE)
 492  *         #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 493  *                       value already exists
 494  */
 495 int
 496 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
 497                                      *map, uint32_t key, void *value,
 498                                      enum GNUNET_CONTAINER_MultiHashMapOption
 499                                      opt)
 500 {
 501   struct MapEntry *e;
 502   unsigned int i;
 503
 504   i = idx_of (map, key);
 505   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 506       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 507   {
 508     e = map->map[i];
 509     while (e != NULL)
 510     {
 511       if (key == e->key)
 512       {
 513         if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 514           return GNUNET_SYSERR;
 515         e->value = value;
 516         return GNUNET_NO;
 517       }
 518       e = e->next;
 519     }
 520   }
 521   if (map->size / 3 >= map->map_length / 4)
 522   {
 523     grow (map);
 524     i = idx_of (map, key);
 525   }
 526   e = GNUNET_new (struct MapEntry);
 527   e->key = key;
 528   e->value = value;
 529   e->next = map->map[i];
 530   map->map[i] = e;
 531   map->size++;
 532   return GNUNET_OK;
 533 }
 534
 535
 536 /**
 537  * Iterate over all entries in the map that match a particular key.
 538  *
 539  * @param map the map
 540  * @param key key that the entries must correspond to
 541  * @param it function to call on each entry
 542  * @param it_cls extra argument to @a it
 543  * @return the number of key value pairs processed,
 544  *         GNUNET_SYSERR if it aborted iteration
 545  */
 546 int
 547 GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map,
 548                                               uint32_t key,
 549                                               GNUNET_CONTAINER_HashMapIterator32 it,
 550                                               void *it_cls)
 551 {
 552   int count;
 553   struct MapEntry *e;
 554   struct MapEntry **ce;
 555
 556   count = 0;
 557   ce = &map->next_cache[map->next_cache_off];
 558   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 559
 560   *ce = map->map[idx_of (map, key)];
 561   while (NULL != (e = *ce))
 562   {
 563     *ce = e->next;
 564     if (key != e->key)
 565       continue;
 566     if ( (NULL != it) &&
 567          (GNUNET_OK != it (it_cls,
 568                            key,
 569                            e->value)) )
 570       return GNUNET_SYSERR;
 571     count++;
 572   }
 573   return count;
 574 }
 575
 576
 577 /**
 578  * Create an iterator for a multihashmap.
 579  * The iterator can be used to retrieve all the elements in the multihashmap
 580  * one by one, without having to handle all elements at once (in contrast to
 581  * GNUNET_CONTAINER_multihashmap_iterate()).  Note that the iterator can not be
 582  * used anymore if elements have been removed from 'map' after the creation of
 583  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
 584  * result in skipped or repeated elements.
 585  *
 586  * @param map the map to create an iterator for
 587  * @return an iterator over the given multihashmap @a map
 588  */
 589 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
 590 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 591 {
 592   struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter;
 593
 594   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32Iterator);
 595   iter->map = map;
 596   iter->modification_counter = map->modification_counter;
 597   iter->me = map->map[0];
 598   return iter;
 599 }
 600
 601
 602 /**
 603  * Retrieve the next element from the hash map at the iterator's position.
 604  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
 605  * are not modified.
 606  * This operation is only allowed if no elements have been removed from the
 607  * multihashmap since the creation of 'iter', and the map has not been destroyed.
 608  * Adding elements may result in repeating or skipping elements.
 609  *
 610  * @param iter the iterator to get the next element from
 611  * @param key pointer to store the key in, can be NULL
 612  * @param value pointer to store the value in, can be NULL
 613  * @return #GNUNET_YES we returned an element,
 614  *         #GNUNET_NO if we are out of elements
 615  */
 616 int
 617 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
 618                                                uint32_t *key,
 619                                                const void **value)
 620 {
 621   /* make sure the map has not been modified */
 622   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
 623
 624   /* look for the next entry, skipping empty buckets */
 625   while (1)
 626   {
 627     if (iter->idx >= iter->map->map_length)
 628       return GNUNET_NO;
 629     if (NULL != iter->me)
 630     {
 631       if (NULL != key)
 632         *key = iter->me->key;
 633       if (NULL != value)
 634         *value = iter->me->value;
 635       iter->me = iter->me->next;
 636       return GNUNET_YES;
 637     }
 638     iter->idx += 1;
 639     if (iter->idx < iter->map->map_length)
 640       iter->me = iter->map->map[iter->idx];
 641   }
 642 }
 643
 644
 645 /**
 646  * Destroy a multihashmap iterator.
 647  *
 648  * @param iter the iterator to destroy
 649  */
 650 void
 651 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
 652 {
 653   GNUNET_free (iter);
 654 }
 655
 656
 657 /* end of container_multihashmap.c */