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 2, 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_common.h"
  30 #include "gnunet_container_lib.h"
  31 #include "gnunet_crypto_lib.h"
  32
  33 #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
  34
  35 /**
  36  * An entry in the hash map.
  37  */
  38 struct MapEntry
  39 {
  40
  41   /**
  42    * Key for the entry.
  43    */
  44   uint32_t key;
  45
  46   /**
  47    * Value of the entry.
  48    */
  49   void *value;
  50
  51   /**
  52    * If there is a hash collision, we create a linked list.
  53    */
  54   struct MapEntry *next;
  55
  56 };
  57
  58 /**
  59  * Internal representation of the hash map.
  60  */
  61 struct GNUNET_CONTAINER_MultiHashMap32
  62 {
  63
  64   /**
  65    * All of our buckets.
  66    */
  67   struct MapEntry **map;
  68
  69   /**
  70    * Number of entries in the map.
  71    */
  72   unsigned int size;
  73
  74   /**
  75    * Length of the "map" array.
  76    */
  77   unsigned int map_length;
  78 };
  79
  80
  81 /**
  82  * Create a multi hash map.
  83  *
  84  * @param len initial size (map will grow as needed)
  85  * @return NULL on error
  86  */
  87 struct GNUNET_CONTAINER_MultiHashMap32 *
  88 GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
  89 {
  90   struct GNUNET_CONTAINER_MultiHashMap32 *ret;
  91
  92   GNUNET_assert (len > 0);
  93   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap32));
  94   ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *));
  95   ret->map_length = len;
  96   return ret;
  97 }
  98
  99
 100 /**
 101  * Destroy a hash map.  Will not free any values
 102  * stored in the hash map!
 103  *
 104  * @param map the map
 105  */
 106 void
 107 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
 108                                          *map)
 109 {
 110   unsigned int i;
 111   struct MapEntry *e;
 112
 113   for (i = 0; i < map->map_length; i++)
 114   {
 115     while (NULL != (e = map->map[i]))
 116     {
 117       map->map[i] = e->next;
 118       GNUNET_free (e);
 119     }
 120   }
 121   GNUNET_free (map->map);
 122   GNUNET_free (map);
 123 }
 124
 125
 126 /**
 127  * Compute the index of the bucket for the given key.
 128  *
 129  * @param m hash map for which to compute the index
 130  * @param key what key should the index be computed for
 131  * @return offset into the "map" array of "m"
 132  */
 133 static unsigned int
 134 idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m,
 135         const uint32_t key)
 136 {
 137   GNUNET_assert (m != NULL);
 138   return ((unsigned int) key) % m->map_length;
 139 }
 140
 141
 142 /**
 143  * Get the number of key-value pairs in the map.
 144  *
 145  * @param map the map
 146  * @return the number of key value pairs
 147  */
 148 unsigned int
 149 GNUNET_CONTAINER_multihashmap32_size (const struct
 150                                       GNUNET_CONTAINER_MultiHashMap32 *map)
 151 {
 152   return map->size;
 153 }
 154
 155
 156 /**
 157  * Given a key find a value in the map matching the key.
 158  *
 159  * @param map the map
 160  * @param key what to look for
 161  * @return NULL if no value was found; note that
 162  *   this is indistinguishable from values that just
 163  *   happen to be NULL; use "contains" to test for
 164  *   key-value pairs with value NULL
 165  */
 166 void *
 167 GNUNET_CONTAINER_multihashmap32_get (const struct
 168                                      GNUNET_CONTAINER_MultiHashMap32 *map,
 169                                      uint32_t key)
 170 {
 171   struct MapEntry *e;
 172
 173   e = map->map[idx_of (map, key)];
 174   while (e != NULL)
 175   {
 176     if (key == e->key)
 177       return e->value;
 178     e = e->next;
 179   }
 180   return NULL;
 181 }
 182
 183
 184 /**
 185  * Iterate over all entries in the map.
 186  *
 187  * @param map the map
 188  * @param it function to call on each entry
 189  * @param it_cls extra argument to it
 190  * @return the number of key value pairs processed,
 191  *         GNUNET_SYSERR if it aborted iteration
 192  */
 193 int
 194 GNUNET_CONTAINER_multihashmap32_iterate (const struct
 195                                          GNUNET_CONTAINER_MultiHashMap32 *map,
 196                                          GNUNET_CONTAINER_HashMapIterator32 it,
 197                                          void *it_cls)
 198 {
 199   int count;
 200   unsigned int i;
 201   struct MapEntry *e;
 202   struct MapEntry *n;
 203
 204   count = 0;
 205   GNUNET_assert (map != NULL);
 206   for (i = 0; i < map->map_length; i++)
 207   {
 208     n = map->map[i];
 209     while (NULL != (e = n))
 210     {
 211       n = e->next;
 212       if (NULL != it)
 213       {
 214         if (GNUNET_OK != it (it_cls, e->key, e->value))
 215           return GNUNET_SYSERR;
 216       }
 217       count++;
 218     }
 219   }
 220   return count;
 221 }
 222
 223
 224 /**
 225  * Remove the given key-value pair from the map.  Note that if the
 226  * key-value pair is in the map multiple times, only one of the pairs
 227  * will be removed.
 228  *
 229  * @param map the map
 230  * @param key key of the key-value pair
 231  * @param value value of the key-value pair
 232  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
 233  *  is not in the map
 234  */
 235 int
 236 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32
 237                                         *map,
 238                                         uint32_t key, const void *value)
 239 {
 240   struct MapEntry *e;
 241   struct MapEntry *p;
 242   unsigned int i;
 243
 244   i = idx_of (map, key);
 245   p = NULL;
 246   e = map->map[i];
 247   while (e != NULL)
 248   {
 249     if ( (key == e->key) && (value == e->value) )
 250     {
 251       if (p == NULL)
 252         map->map[i] = e->next;
 253       else
 254         p->next = e->next;
 255       GNUNET_free (e);
 256       map->size--;
 257       return GNUNET_YES;
 258     }
 259     p = e;
 260     e = e->next;
 261   }
 262   return GNUNET_NO;
 263 }
 264
 265
 266 /**
 267  * Remove all entries for the given key from the map.
 268  * Note that the values would not be "freed".
 269  *
 270  * @param map the map
 271  * @param key identifies values to be removed
 272  * @return number of values removed
 273  */
 274 int
 275 GNUNET_CONTAINER_multihashmap32_remove_all (struct
 276                                             GNUNET_CONTAINER_MultiHashMap32
 277                                             *map,
 278                                             uint32_t key)
 279 {
 280   struct MapEntry *e;
 281   struct MapEntry *p;
 282   unsigned int i;
 283   int ret;
 284
 285   ret = 0;
 286   i = idx_of (map, key);
 287   p = NULL;
 288   e = map->map[i];
 289   while (e != NULL)
 290   {
 291     if (key == e->key)
 292     {
 293       if (p == NULL)
 294         map->map[i] = e->next;
 295       else
 296         p->next = e->next;
 297       GNUNET_free (e);
 298       map->size--;
 299       if (p == NULL)
 300         e = map->map[i];
 301       else
 302         e = p->next;
 303       ret++;
 304     }
 305     else
 306     {
 307       p = e;
 308       e = e->next;
 309     }
 310   }
 311   return ret;
 312 }
 313
 314
 315 /**
 316  * Check if the map contains any value under the given
 317  * key (including values that are NULL).
 318  *
 319  * @param map the map
 320  * @param key the key to test if a value exists for it
 321  * @return GNUNET_YES if such a value exists,
 322  *         GNUNET_NO if not
 323  */
 324 int
 325 GNUNET_CONTAINER_multihashmap32_contains (const struct
 326                                           GNUNET_CONTAINER_MultiHashMap32 *map,
 327                                           uint32_t key)
 328 {
 329   struct MapEntry *e;
 330
 331   e = map->map[idx_of (map, key)];
 332   while (e != NULL)
 333   {
 334     if (key == e->key)
 335       return GNUNET_YES;
 336     e = e->next;
 337   }
 338   return GNUNET_NO;
 339 }
 340
 341
 342 /**
 343  * Check if the map contains the given value under the given
 344  * key.
 345  *
 346  * @param map the map
 347  * @param key the key to test if a value exists for it
 348  * @param value value to test for
 349  * @return GNUNET_YES if such a value exists,
 350  *         GNUNET_NO if not
 351  */
 352 int
 353 GNUNET_CONTAINER_multihashmap32_contains_value (const struct
 354                                                 GNUNET_CONTAINER_MultiHashMap32
 355                                                 *map,
 356                                                 uint32_t key,
 357                                                 const void *value)
 358 {
 359   struct MapEntry *e;
 360
 361   e = map->map[idx_of (map, key)];
 362   while (e != NULL)
 363   {
 364     if ( (key == e->key) && (e->value == value) )
 365       return GNUNET_YES;
 366     e = e->next;
 367   }
 368   return GNUNET_NO;
 369 }
 370
 371
 372 /**
 373  * Grow the given map to a more appropriate size.
 374  *
 375  * @param map the hash map to grow
 376  */
 377 static void
 378 grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
 379 {
 380   struct MapEntry **old_map;
 381   struct MapEntry **new_map;
 382   struct MapEntry *e;
 383   unsigned int old_len;
 384   unsigned int new_len;
 385   unsigned int idx;
 386   unsigned int i;
 387
 388   old_map = map->map;
 389   old_len = map->map_length;
 390   new_len = old_len * 2;
 391   new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len);
 392   map->map_length = new_len;
 393   map->map = new_map;
 394   for (i = 0; i < old_len; i++)
 395   {
 396     while (NULL != (e = old_map[i]))
 397     {
 398       old_map[i] = e->next;
 399       idx = idx_of (map, e->key);
 400       e->next = new_map[idx];
 401       new_map[idx] = e;
 402     }
 403   }
 404   GNUNET_free (old_map);
 405 }
 406
 407
 408 /**
 409  * Store a key-value pair in the map.
 410  *
 411  * @param map the map
 412  * @param key key to use
 413  * @param value value to use
 414  * @param opt options for put
 415  * @return GNUNET_OK on success,
 416  *         GNUNET_NO if a value was replaced (with REPLACE)
 417  *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 418  *                       value already exists
 419  */
 420 int
 421 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
 422                                      *map, uint32_t key, void *value,
 423                                      enum GNUNET_CONTAINER_MultiHashMapOption
 424                                      opt)
 425 {
 426   struct MapEntry *e;
 427   unsigned int i;
 428
 429   i = idx_of (map, key);
 430   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 431       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 432   {
 433     e = map->map[i];
 434     while (e != NULL)
 435     {
 436       if (key == e->key)
 437       {
 438         if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 439           return GNUNET_SYSERR;
 440         e->value = value;
 441         return GNUNET_NO;
 442       }
 443       e = e->next;
 444     }
 445   }
 446   if (map->size / 3 >= map->map_length / 4)
 447   {
 448     grow (map);
 449     i = idx_of (map, key);
 450   }
 451   e = GNUNET_malloc (sizeof (struct MapEntry));
 452   e->key = key;
 453   e->value = value;
 454   e->next = map->map[i];
 455   map->map[i] = e;
 456   map->size++;
 457   return GNUNET_OK;
 458 }
 459
 460
 461 /**
 462  * Iterate over all entries in the map that match a particular key.
 463  *
 464  * @param map the map
 465  * @param key key that the entries must correspond to
 466  * @param it function to call on each entry
 467  * @param it_cls extra argument to it
 468  * @return the number of key value pairs processed,
 469  *         GNUNET_SYSERR if it aborted iteration
 470  */
 471 int
 472 GNUNET_CONTAINER_multihashmap32_get_multiple (const struct
 473                                               GNUNET_CONTAINER_MultiHashMap32
 474                                               *map, uint32_t key,
 475                                               GNUNET_CONTAINER_HashMapIterator32
 476                                               it, void *it_cls)
 477 {
 478   int count;
 479   struct MapEntry *e;
 480   struct MapEntry *n;
 481
 482   count = 0;
 483   n = map->map[idx_of (map, key)];
 484   while (NULL != (e = n))
 485   {
 486     n = e->next;
 487     if (key != e->key)
 488       continue;
 489     if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value)))
 490       return GNUNET_SYSERR;
 491     count++;
 492   }
 493   return count;
 494 }
 495
 496
 497 /* end of container_multihashmap.c */