src/util/container_multihashmap32.c

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