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