src/util/container_multihashmap.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_multihashmap.c
  22  * @brief hash map where the same key may be present multiple times
  23  * @author Christian Grothoff
  24  */
  25
  26 #include "platform.h"
  27 #include "gnunet_common.h"
  28 #include "gnunet_container_lib.h"
  29 #include "gnunet_crypto_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   struct GNUNET_HashCode 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_MultiHashMap
  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
  79 /**
  80  * Create a multi hash map.
  81  *
  82  * @param len initial size (map will grow as needed)
  83  * @param do_not_copy_keys GNUNET_NO is always safe and should be used by default;
  84  *                         GNUNET_YES means that on 'put', the 'key' does not have
  85  *                         to be copied as the destination of the pointer is
  86  *                         guaranteed to be life as long as the value is stored in
  87  *                         the hashmap.  This can significantly reduce memory
  88  *                         consumption, but of course is also a recipie for
  89  *                         heap corruption if the assumption is not true.  Only
  90  *                         use this if (1) memory use is important in this case and
  91  *                         (2) you have triple-checked that the invariant holds
  92  * @return NULL on error
  93  */
  94 struct GNUNET_CONTAINER_MultiHashMap *
  95 GNUNET_CONTAINER_multihashmap_create (unsigned int len,
  96                                       int do_not_copy_keys)
  97 {
  98   struct GNUNET_CONTAINER_MultiHashMap *ret;
  99
 100   GNUNET_assert (len > 0);
 101   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap));
 102   ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *));
 103   ret->map_length = len;
 104   return ret;
 105 }
 106
 107
 108 /**
 109  * Destroy a hash map.  Will not free any values
 110  * stored in the hash map!
 111  *
 112  * @param map the map
 113  */
 114 void
 115 GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap
 116                                        *map)
 117 {
 118   unsigned int i;
 119   struct MapEntry *e;
 120
 121   for (i = 0; i < map->map_length; i++)
 122   {
 123     while (NULL != (e = map->map[i]))
 124     {
 125       map->map[i] = e->next;
 126       GNUNET_free (e);
 127     }
 128   }
 129   GNUNET_free (map->map);
 130   GNUNET_free (map);
 131 }
 132
 133
 134 /**
 135  * Compute the index of the bucket for the given key.
 136  *
 137  * @param m hash map for which to compute the index
 138  * @param key what key should the index be computed for
 139  * @return offset into the "map" array of "m"
 140  */
 141 static unsigned int
 142 idx_of (const struct GNUNET_CONTAINER_MultiHashMap *m,
 143         const struct GNUNET_HashCode * key)
 144 {
 145   GNUNET_assert (m != NULL);
 146   return (*(unsigned int *) key) % m->map_length;
 147 }
 148
 149
 150 /**
 151  * Get the number of key-value pairs in the map.
 152  *
 153  * @param map the map
 154  * @return the number of key value pairs
 155  */
 156 unsigned int
 157 GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap
 158                                     *map)
 159 {
 160   return map->size;
 161 }
 162
 163
 164 /**
 165  * Given a key find a value in the map matching the key.
 166  *
 167  * @param map the map
 168  * @param key what to look for
 169  * @return NULL if no value was found; note that
 170  *   this is indistinguishable from values that just
 171  *   happen to be NULL; use "contains" to test for
 172  *   key-value pairs with value NULL
 173  */
 174 void *
 175 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap
 176                                    *map, const struct GNUNET_HashCode * key)
 177 {
 178   struct MapEntry *e;
 179
 180   e = map->map[idx_of (map, key)];
 181   while (e != NULL)
 182   {
 183     if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode)))
 184       return e->value;
 185     e = e->next;
 186   }
 187   return NULL;
 188 }
 189
 190
 191 /**
 192  * Iterate over all entries in the map.
 193  *
 194  * @param map the map
 195  * @param it function to call on each entry
 196  * @param it_cls extra argument to it
 197  * @return the number of key value pairs processed,
 198  *         GNUNET_SYSERR if it aborted iteration
 199  */
 200 int
 201 GNUNET_CONTAINER_multihashmap_iterate (const struct
 202                                        GNUNET_CONTAINER_MultiHashMap *map,
 203                                        GNUNET_CONTAINER_HashMapIterator it,
 204                                        void *it_cls)
 205 {
 206   int count;
 207   unsigned int i;
 208   struct MapEntry *e;
 209   struct MapEntry *n;
 210   struct GNUNET_HashCode kc;
 211
 212   count = 0;
 213   GNUNET_assert (map != NULL);
 214   for (i = 0; i < map->map_length; i++)
 215   {
 216     n = map->map[i];
 217     while (NULL != (e = n))
 218     {
 219       n = e->next;
 220       if (NULL != it)
 221       {
 222         kc = e->key;
 223         if (GNUNET_OK != it (it_cls, &kc, e->value))
 224           return GNUNET_SYSERR;
 225       }
 226       count++;
 227     }
 228   }
 229   return count;
 230 }
 231
 232
 233 /**
 234  * Remove the given key-value pair from the map.  Note that if the
 235  * key-value pair is in the map multiple times, only one of the pairs
 236  * will be removed.
 237  *
 238  * @param map the map
 239  * @param key key of the key-value pair
 240  * @param value value of the key-value pair
 241  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
 242  *  is not in the map
 243  */
 244 int
 245 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
 246                                       const struct GNUNET_HashCode * key, void *value)
 247 {
 248   struct MapEntry *e;
 249   struct MapEntry *p;
 250   unsigned int i;
 251
 252   i = idx_of (map, key);
 253   p = NULL;
 254   e = map->map[i];
 255   while (e != NULL)
 256   {
 257     if ((0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode))) &&
 258         (value == e->value))
 259     {
 260       if (p == NULL)
 261         map->map[i] = e->next;
 262       else
 263         p->next = e->next;
 264       GNUNET_free (e);
 265       map->size--;
 266       return GNUNET_YES;
 267     }
 268     p = e;
 269     e = e->next;
 270   }
 271   return GNUNET_NO;
 272 }
 273
 274
 275 /**
 276  * Remove all entries for the given key from the map.
 277  * Note that the values would not be "freed".
 278  *
 279  * @param map the map
 280  * @param key identifies values to be removed
 281  * @return number of values removed
 282  */
 283 int
 284 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap
 285                                           *map, const struct GNUNET_HashCode * key)
 286 {
 287   struct MapEntry *e;
 288   struct MapEntry *p;
 289   unsigned int i;
 290   int ret;
 291
 292   ret = 0;
 293   i = idx_of (map, key);
 294   p = NULL;
 295   e = map->map[i];
 296   while (e != NULL)
 297   {
 298     if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode)))
 299     {
 300       if (p == NULL)
 301         map->map[i] = e->next;
 302       else
 303         p->next = e->next;
 304       GNUNET_free (e);
 305       map->size--;
 306       if (p == NULL)
 307         e = map->map[i];
 308       else
 309         e = p->next;
 310       ret++;
 311     }
 312     else
 313     {
 314       p = e;
 315       e = e->next;
 316     }
 317   }
 318   return ret;
 319 }
 320
 321
 322 /**
 323  * Check if the map contains any value under the given
 324  * key (including values that are NULL).
 325  *
 326  * @param map the map
 327  * @param key the key to test if a value exists for it
 328  * @return GNUNET_YES if such a value exists,
 329  *         GNUNET_NO if not
 330  */
 331 int
 332 GNUNET_CONTAINER_multihashmap_contains (const struct
 333                                         GNUNET_CONTAINER_MultiHashMap *map,
 334                                         const struct GNUNET_HashCode * key)
 335 {
 336   struct MapEntry *e;
 337
 338   e = map->map[idx_of (map, key)];
 339   while (e != NULL)
 340   {
 341     if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode)))
 342       return GNUNET_YES;
 343     e = e->next;
 344   }
 345   return GNUNET_NO;
 346 }
 347
 348
 349 /**
 350  * Check if the map contains the given value under the given
 351  * key.
 352  *
 353  * @param map the map
 354  * @param key the key to test if a value exists for it
 355  * @param value value to test for
 356  * @return GNUNET_YES if such a value exists,
 357  *         GNUNET_NO if not
 358  */
 359 int
 360 GNUNET_CONTAINER_multihashmap_contains_value (const struct
 361                                               GNUNET_CONTAINER_MultiHashMap
 362                                               *map, const struct GNUNET_HashCode * key,
 363                                               const void *value)
 364 {
 365   struct MapEntry *e;
 366
 367   e = map->map[idx_of (map, key)];
 368   while (e != NULL)
 369   {
 370     if ((0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode))) &&
 371         (e->value == value))
 372       return GNUNET_YES;
 373     e = e->next;
 374   }
 375   return GNUNET_NO;
 376 }
 377
 378
 379 /**
 380  * Grow the given map to a more appropriate size.
 381  *
 382  * @param map the hash map to grow
 383  */
 384 static void
 385 grow (struct GNUNET_CONTAINER_MultiHashMap *map)
 386 {
 387   struct MapEntry **old_map;
 388   struct MapEntry **new_map;
 389   struct MapEntry *e;
 390   unsigned int old_len;
 391   unsigned int new_len;
 392   unsigned int idx;
 393   unsigned int i;
 394
 395   old_map = map->map;
 396   old_len = map->map_length;
 397   new_len = old_len * 2;
 398   new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len);
 399   map->map_length = new_len;
 400   map->map = new_map;
 401   for (i = 0; i < old_len; i++)
 402   {
 403     while (NULL != (e = old_map[i]))
 404     {
 405       old_map[i] = e->next;
 406       idx = idx_of (map, &e->key);
 407       e->next = new_map[idx];
 408       new_map[idx] = e;
 409     }
 410   }
 411   GNUNET_free (old_map);
 412 }
 413
 414
 415 /**
 416  * Store a key-value pair in the map.
 417  *
 418  * @param map the map
 419  * @param key key to use
 420  * @param value value to use
 421  * @param opt options for put
 422  * @return GNUNET_OK on success,
 423  *         GNUNET_NO if a value was replaced (with REPLACE)
 424  *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 425  *                       value already exists
 426  */
 427 int
 428 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
 429                                    const struct GNUNET_HashCode * key, void *value,
 430                                    enum GNUNET_CONTAINER_MultiHashMapOption opt)
 431 {
 432   struct MapEntry *e;
 433   unsigned int i;
 434
 435   i = idx_of (map, key);
 436   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 437       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 438   {
 439     e = map->map[i];
 440     while (e != NULL)
 441     {
 442       if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode)))
 443       {
 444         if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 445           return GNUNET_SYSERR;
 446         e->value = value;
 447         return GNUNET_NO;
 448       }
 449       e = e->next;
 450     }
 451   }
 452   if (map->size / 3 >= map->map_length / 4)
 453   {
 454     grow (map);
 455     i = idx_of (map, key);
 456   }
 457   e = GNUNET_malloc (sizeof (struct MapEntry));
 458   e->key = *key;
 459   e->value = value;
 460   e->next = map->map[i];
 461   map->map[i] = e;
 462   map->size++;
 463   return GNUNET_OK;
 464 }
 465
 466
 467 /**
 468  * Iterate over all entries in the map that match a particular key.
 469  *
 470  * @param map the map
 471  * @param key key that the entries must correspond to
 472  * @param it function to call on each entry
 473  * @param it_cls extra argument to it
 474  * @return the number of key value pairs processed,
 475  *         GNUNET_SYSERR if it aborted iteration
 476  */
 477 int
 478 GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 479                                             GNUNET_CONTAINER_MultiHashMap *map,
 480                                             const struct GNUNET_HashCode * key,
 481                                             GNUNET_CONTAINER_HashMapIterator it,
 482                                             void *it_cls)
 483 {
 484   int count;
 485   struct MapEntry *e;
 486   struct MapEntry *n;
 487
 488   count = 0;
 489   n = map->map[idx_of (map, key)];
 490   while (NULL != (e = n))
 491   {
 492     n = e->next;
 493     if (0 != memcmp (key, &e->key, sizeof (struct GNUNET_HashCode)))
 494       continue;
 495     if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value)))
 496       return GNUNET_SYSERR;
 497     count++;
 498   }
 499   return count;
 500 }
 501
 502
 503 /* end of container_multihashmap.c */