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  * An entry in the hash map.
  33  */
  34 struct MapEntry
  35 {
  36
  37   /**
  38    * Key for the entry.
  39    */
  40   uint32_t key;
  41
  42   /**
  43    * Value of the entry.
  44    */
  45   void *value;
  46
  47   /**
  48    * If there is a hash collision, we create a linked list.
  49    */
  50   struct MapEntry *next;
  51
  52 };
  53
  54 /**
  55  * Internal representation of the hash map.
  56  */
  57 struct GNUNET_CONTAINER_MultiHashMap32
  58 {
  59
  60   /**
  61    * All of our buckets.
  62    */
  63   struct MapEntry **map;
  64
  65   /**
  66    * Number of entries in the map.
  67    */
  68   unsigned int size;
  69
  70   /**
  71    * Length of the "map" array.
  72    */
  73   unsigned int map_length;
  74
  75   /**
  76    * Counts the destructive modifications (grow, remove)
  77    * to the map, so that iterators can check if they are still valid.
  78    */
  79   unsigned int modification_counter;
  80 };
  81
  82
  83 /**
  84  * Cursor into a multihashmap.
  85  * Allows to enumerate elements asynchronously.
  86  */
  87 struct GNUNET_CONTAINER_MultiHashMap32Iterator
  88 {
  89   /**
  90    * Position in the bucket 'idx'
  91    */
  92   struct MapEntry *me;
  93
  94   /**
  95    * Current bucket index.
  96    */
  97   unsigned int idx;
  98
  99   /**
 100    * Modification counter as observed on the map when the iterator
 101    * was created.
 102    */
 103   unsigned int modification_counter;
 104
 105   /**
 106    * Map that we are iterating over.
 107    */
 108   const struct GNUNET_CONTAINER_MultiHashMap32 *map;
 109 };
 110
 111
 112 /**
 113  * Create a multi hash map.
 114  *
 115  * @param len initial size (map will grow as needed)
 116  * @return NULL on error
 117  */
 118 struct GNUNET_CONTAINER_MultiHashMap32 *
 119 GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
 120 {
 121   struct GNUNET_CONTAINER_MultiHashMap32 *ret;
 122
 123   GNUNET_assert (len > 0);
 124   ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32);
 125   ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *));
 126   ret->map_length = len;
 127   return ret;
 128 }
 129
 130
 131 /**
 132  * Destroy a hash map.  Will not free any values
 133  * stored in the hash map!
 134  *
 135  * @param map the map
 136  */
 137 void
 138 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
 139                                          *map)
 140 {
 141   unsigned int i;
 142   struct MapEntry *e;
 143
 144   for (i = 0; i < map->map_length; i++)
 145   {
 146     while (NULL != (e = map->map[i]))
 147     {
 148       map->map[i] = e->next;
 149       GNUNET_free (e);
 150     }
 151   }
 152   GNUNET_free (map->map);
 153   GNUNET_free (map);
 154 }
 155
 156
 157 /**
 158  * Compute the index of the bucket for the given key.
 159  *
 160  * @param m hash map for which to compute the index
 161  * @param key what key should the index be computed for
 162  * @return offset into the "map" array of "m"
 163  */
 164 static unsigned int
 165 idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m,
 166         const uint32_t key)
 167 {
 168   GNUNET_assert (m != NULL);
 169   return ((unsigned int) key) % m->map_length;
 170 }
 171
 172
 173 /**
 174  * Get the number of key-value pairs in the map.
 175  *
 176  * @param map the map
 177  * @return the number of key value pairs
 178  */
 179 unsigned int
 180 GNUNET_CONTAINER_multihashmap32_size (const struct
 181                                       GNUNET_CONTAINER_MultiHashMap32 *map)
 182 {
 183   return map->size;
 184 }
 185
 186
 187 /**
 188  * Given a key find a value in the map matching the key.
 189  *
 190  * @param map the map
 191  * @param key what to look for
 192  * @return NULL if no value was found; note that
 193  *   this is indistinguishable from values that just
 194  *   happen to be NULL; use "contains" to test for
 195  *   key-value pairs with value NULL
 196  */
 197 void *
 198 GNUNET_CONTAINER_multihashmap32_get (const struct
 199                                      GNUNET_CONTAINER_MultiHashMap32 *map,
 200                                      uint32_t key)
 201 {
 202   struct MapEntry *e;
 203
 204   e = map->map[idx_of (map, key)];
 205   while (e != NULL)
 206   {
 207     if (key == e->key)
 208       return e->value;
 209     e = e->next;
 210   }
 211   return NULL;
 212 }
 213
 214
 215 /**
 216  * Iterate over all entries in the map.
 217  *
 218  * @param map the map
 219  * @param it function to call on each entry
 220  * @param it_cls extra argument to @a it
 221  * @return the number of key value pairs processed,
 222  *         #GNUNET_SYSERR if it aborted iteration
 223  */
 224 int
 225 GNUNET_CONTAINER_multihashmap32_iterate (const struct
 226                                          GNUNET_CONTAINER_MultiHashMap32 *map,
 227                                          GNUNET_CONTAINER_HashMapIterator32 it,
 228                                          void *it_cls)
 229 {
 230   int count;
 231   unsigned int i;
 232   struct MapEntry *e;
 233   struct MapEntry *n;
 234
 235   count = 0;
 236   GNUNET_assert (NULL != map);
 237   for (i = 0; i < map->map_length; i++)
 238   {
 239     n = map->map[i];
 240     while (NULL != (e = n))
 241     {
 242       n = e->next;
 243       if (NULL != it)
 244       {
 245         if (GNUNET_OK != it (it_cls, e->key, e->value))
 246           return GNUNET_SYSERR;
 247       }
 248       count++;
 249     }
 250   }
 251   return count;
 252 }
 253
 254
 255 /**
 256  * Remove the given key-value pair from the map.  Note that if the
 257  * key-value pair is in the map multiple times, only one of the pairs
 258  * will be removed.
 259  *
 260  * @param map the map
 261  * @param key key of the key-value pair
 262  * @param value value of the key-value pair
 263  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
 264  *  is not in the map
 265  */
 266 int
 267 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32
 268                                         *map,
 269                                         uint32_t key, const void *value)
 270 {
 271   struct MapEntry *e;
 272   struct MapEntry *p;
 273   unsigned int i;
 274
 275   map->modification_counter++;
 276
 277   i = idx_of (map, key);
 278   p = NULL;
 279   e = map->map[i];
 280   while (e != NULL)
 281   {
 282     if ( (key == e->key) && (value == e->value) )
 283     {
 284       if (p == NULL)
 285         map->map[i] = e->next;
 286       else
 287         p->next = e->next;
 288       GNUNET_free (e);
 289       map->size--;
 290       return GNUNET_YES;
 291     }
 292     p = e;
 293     e = e->next;
 294   }
 295   return GNUNET_NO;
 296 }
 297
 298
 299 /**
 300  * Remove all entries for the given key from the map.
 301  * Note that the values would not be "freed".
 302  *
 303  * @param map the map
 304  * @param key identifies values to be removed
 305  * @return number of values removed
 306  */
 307 int
 308 GNUNET_CONTAINER_multihashmap32_remove_all (struct
 309                                             GNUNET_CONTAINER_MultiHashMap32
 310                                             *map,
 311                                             uint32_t key)
 312 {
 313   struct MapEntry *e;
 314   struct MapEntry *p;
 315   unsigned int i;
 316   int ret;
 317
 318   map->modification_counter++;
 319
 320   ret = 0;
 321   i = idx_of (map, key);
 322   p = NULL;
 323   e = map->map[i];
 324   while (e != NULL)
 325   {
 326     if (key == e->key)
 327     {
 328       if (p == NULL)
 329         map->map[i] = e->next;
 330       else
 331         p->next = e->next;
 332       GNUNET_free (e);
 333       map->size--;
 334       if (p == NULL)
 335         e = map->map[i];
 336       else
 337         e = p->next;
 338       ret++;
 339     }
 340     else
 341     {
 342       p = e;
 343       e = e->next;
 344     }
 345   }
 346   return ret;
 347 }
 348
 349
 350 /**
 351  * Check if the map contains any value under the given
 352  * key (including values that are NULL).
 353  *
 354  * @param map the map
 355  * @param key the key to test if a value exists for it
 356  * @return GNUNET_YES if such a value exists,
 357  *         GNUNET_NO if not
 358  */
 359 int
 360 GNUNET_CONTAINER_multihashmap32_contains (const struct
 361                                           GNUNET_CONTAINER_MultiHashMap32 *map,
 362                                           uint32_t key)
 363 {
 364   struct MapEntry *e;
 365
 366   e = map->map[idx_of (map, key)];
 367   while (e != NULL)
 368   {
 369     if (key == e->key)
 370       return GNUNET_YES;
 371     e = e->next;
 372   }
 373   return GNUNET_NO;
 374 }
 375
 376
 377 /**
 378  * Check if the map contains the given value under the given
 379  * key.
 380  *
 381  * @param map the map
 382  * @param key the key to test if a value exists for it
 383  * @param value value to test for
 384  * @return GNUNET_YES if such a value exists,
 385  *         GNUNET_NO if not
 386  */
 387 int
 388 GNUNET_CONTAINER_multihashmap32_contains_value (const struct
 389                                                 GNUNET_CONTAINER_MultiHashMap32
 390                                                 *map,
 391                                                 uint32_t key,
 392                                                 const void *value)
 393 {
 394   struct MapEntry *e;
 395
 396   e = map->map[idx_of (map, key)];
 397   while (e != NULL)
 398   {
 399     if ( (key == e->key) && (e->value == value) )
 400       return GNUNET_YES;
 401     e = e->next;
 402   }
 403   return GNUNET_NO;
 404 }
 405
 406
 407 /**
 408  * Grow the given map to a more appropriate size.
 409  *
 410  * @param map the hash map to grow
 411  */
 412 static void
 413 grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
 414 {
 415   struct MapEntry **old_map;
 416   struct MapEntry **new_map;
 417   struct MapEntry *e;
 418   unsigned int old_len;
 419   unsigned int new_len;
 420   unsigned int idx;
 421   unsigned int i;
 422
 423   map->modification_counter++;
 424
 425   old_map = map->map;
 426   old_len = map->map_length;
 427   new_len = old_len * 2;
 428   new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len);
 429   map->map_length = new_len;
 430   map->map = new_map;
 431   for (i = 0; i < old_len; i++)
 432   {
 433     while (NULL != (e = old_map[i]))
 434     {
 435       old_map[i] = e->next;
 436       idx = idx_of (map, e->key);
 437       e->next = new_map[idx];
 438       new_map[idx] = e;
 439     }
 440   }
 441   GNUNET_free (old_map);
 442 }
 443
 444
 445 /**
 446  * Store a key-value pair in the map.
 447  *
 448  * @param map the map
 449  * @param key key to use
 450  * @param value value to use
 451  * @param opt options for put
 452  * @return GNUNET_OK on success,
 453  *         GNUNET_NO if a value was replaced (with REPLACE)
 454  *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 455  *                       value already exists
 456  */
 457 int
 458 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
 459                                      *map, uint32_t key, void *value,
 460                                      enum GNUNET_CONTAINER_MultiHashMapOption
 461                                      opt)
 462 {
 463   struct MapEntry *e;
 464   unsigned int i;
 465
 466   i = idx_of (map, key);
 467   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 468       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 469   {
 470     e = map->map[i];
 471     while (e != NULL)
 472     {
 473       if (key == e->key)
 474       {
 475         if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 476           return GNUNET_SYSERR;
 477         e->value = value;
 478         return GNUNET_NO;
 479       }
 480       e = e->next;
 481     }
 482   }
 483   if (map->size / 3 >= map->map_length / 4)
 484   {
 485     grow (map);
 486     i = idx_of (map, key);
 487   }
 488   e = GNUNET_new (struct MapEntry);
 489   e->key = key;
 490   e->value = value;
 491   e->next = map->map[i];
 492   map->map[i] = e;
 493   map->size++;
 494   return GNUNET_OK;
 495 }
 496
 497
 498 /**
 499  * Iterate over all entries in the map that match a particular key.
 500  *
 501  * @param map the map
 502  * @param key key that the entries must correspond to
 503  * @param it function to call on each entry
 504  * @param it_cls extra argument to it
 505  * @return the number of key value pairs processed,
 506  *         GNUNET_SYSERR if it aborted iteration
 507  */
 508 int
 509 GNUNET_CONTAINER_multihashmap32_get_multiple (const struct
 510                                               GNUNET_CONTAINER_MultiHashMap32
 511                                               *map, uint32_t key,
 512                                               GNUNET_CONTAINER_HashMapIterator32
 513                                               it, void *it_cls)
 514 {
 515   int count;
 516   struct MapEntry *e;
 517   struct MapEntry *n;
 518
 519   count = 0;
 520   n = map->map[idx_of (map, key)];
 521   while (NULL != (e = n))
 522   {
 523     n = e->next;
 524     if (key != e->key)
 525       continue;
 526     if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value)))
 527       return GNUNET_SYSERR;
 528     count++;
 529   }
 530   return count;
 531 }
 532
 533
 534 /**
 535  * Create an iterator for a multihashmap.
 536  * The iterator can be used to retrieve all the elements in the multihashmap
 537  * one by one, without having to handle all elements at once (in contrast to
 538  * GNUNET_CONTAINER_multihashmap_iterate()).  Note that the iterator can not be
 539  * used anymore if elements have been removed from 'map' after the creation of
 540  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
 541  * result in skipped or repeated elements.
 542  *
 543  * @param map the map to create an iterator for
 544  * @return an iterator over the given multihashmap 'map'
 545  */
 546 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
 547 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 548 {
 549   struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter;
 550
 551   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32Iterator);
 552   iter->map = map;
 553   iter->modification_counter = map->modification_counter;
 554   iter->me = map->map[0];
 555   return iter;
 556 }
 557
 558
 559 /**
 560  * Retrieve the next element from the hash map at the iterator's position.
 561  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
 562  * are not modified.
 563  * This operation is only allowed if no elements have been removed from the
 564  * multihashmap since the creation of 'iter', and the map has not been destroyed.
 565  * Adding elements may result in repeating or skipping elements.
 566  *
 567  * @param iter the iterator to get the next element from
 568  * @param key pointer to store the key in, can be NULL
 569  * @param value pointer to store the value in, can be NULL
 570  * @return #GNUNET_YES we returned an element,
 571  *         #GNUNET_NO if we are out of elements
 572  */
 573 int
 574 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
 575                                                uint32_t *key,
 576                                                const void **value)
 577 {
 578   /* make sure the map has not been modified */
 579   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
 580
 581   /* look for the next entry, skipping empty buckets */
 582   while (1)
 583   {
 584     if (iter->idx >= iter->map->map_length)
 585       return GNUNET_NO;
 586     if (NULL != iter->me)
 587     {
 588       if (NULL != key)
 589         *key = iter->me->key;
 590       if (NULL != value)
 591         *value = iter->me->value;
 592       iter->me = iter->me->next;
 593       return GNUNET_YES;
 594     }
 595     iter->idx += 1;
 596     if (iter->idx < iter->map->map_length)
 597       iter->me = iter->map->map[iter->idx];
 598   }
 599 }
 600
 601
 602 /**
 603  * Destroy a multihashmap iterator.
 604  *
 605  * @param iter the iterator to destroy
 606  */
 607 void
 608 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
 609 {
 610   GNUNET_free (iter);
 611 }
 612
 613
 614 /* end of container_multihashmap.c */