src/util/container_multihashmap.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2008, 2012 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 with the full key.
  35  */
  36 struct BigMapEntry
  37 {
  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 BigMapEntry *next;
  48
  49   /**
  50    * Key for the entry.
  51    */
  52   struct GNUNET_HashCode key;
  53
  54 };
  55
  56
  57 /**
  58  * An entry in the hash map with just a pointer to the key.
  59  */
  60 struct SmallMapEntry
  61 {
  62
  63   /**
  64    * Value of the entry.
  65    */
  66   void *value;
  67
  68   /**
  69    * If there is a hash collision, we create a linked list.
  70    */
  71   struct SmallMapEntry *next;
  72
  73   /**
  74    * Key for the entry.
  75    */
  76   const struct GNUNET_HashCode *key;
  77
  78 };
  79
  80
  81 /**
  82  * Entry in the map.
  83  */
  84 union MapEntry
  85 {
  86   /**
  87    * Variant used if map entries only contain a pointer to the key.
  88    */
  89   struct SmallMapEntry *sme;
  90
  91   /**
  92    * Variant used if map entries contain the full key.
  93    */
  94   struct BigMapEntry *bme;
  95 };
  96
  97
  98 /**
  99  * Internal representation of the hash map.
 100  */
 101 struct GNUNET_CONTAINER_MultiHashMap
 102 {
 103
 104   /**
 105    * All of our buckets.
 106    */
 107   union MapEntry *map;
 108
 109   /**
 110    * Number of entries in the map.
 111    */
 112   unsigned int size;
 113
 114   /**
 115    * Length of the "map" array.
 116    */
 117   unsigned int map_length;
 118
 119   /**
 120    * GNUNET_NO if the map entries are of type 'struct BigMapEntry',
 121    * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'.
 122    */
 123   int use_small_entries;
 124 };
 125
 126
 127 /**
 128  * Create a multi hash map.
 129  *
 130  * @param len initial size (map will grow as needed)
 131  * @param do_not_copy_keys GNUNET_NO is always safe and should be used by default;
 132  *                         GNUNET_YES means that on 'put', the 'key' does not have
 133  *                         to be copied as the destination of the pointer is
 134  *                         guaranteed to be life as long as the value is stored in
 135  *                         the hashmap.  This can significantly reduce memory
 136  *                         consumption, but of course is also a recipie for
 137  *                         heap corruption if the assumption is not true.  Only
 138  *                         use this if (1) memory use is important in this case and
 139  *                         (2) you have triple-checked that the invariant holds
 140  * @return NULL on error
 141  */
 142 struct GNUNET_CONTAINER_MultiHashMap *
 143 GNUNET_CONTAINER_multihashmap_create (unsigned int len,
 144                                       int do_not_copy_keys)
 145 {
 146   struct GNUNET_CONTAINER_MultiHashMap *map;
 147
 148   GNUNET_assert (len > 0);
 149   map = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap));
 150   map->map = GNUNET_malloc (len * sizeof (union MapEntry));
 151   map->map_length = len;
 152   map->use_small_entries = do_not_copy_keys;
 153   return map;
 154 }
 155
 156
 157 /**
 158  * Destroy a hash map.  Will not free any values
 159  * stored in the hash map!
 160  *
 161  * @param map the map
 162  */
 163 void
 164 GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap
 165                                        *map)
 166 {
 167   unsigned int i;
 168   union MapEntry me;
 169
 170   for (i = 0; i < map->map_length; i++)
 171   {
 172     me = map->map[i];
 173     if (map->use_small_entries)
 174     {
 175       struct SmallMapEntry *sme;
 176       struct SmallMapEntry *nxt;
 177
 178       nxt = me.sme;
 179       while (NULL != (sme = nxt))
 180       {
 181         nxt = sme->next;
 182         GNUNET_free (sme);
 183       }
 184       me.sme = NULL;
 185     }
 186     else
 187     {
 188       struct BigMapEntry *bme;
 189       struct BigMapEntry *nxt;
 190
 191       nxt = me.bme;
 192       while (NULL != (bme = nxt))
 193       {
 194         nxt = bme->next;
 195         GNUNET_free (bme);
 196       }
 197       me.bme = NULL;
 198     }
 199   }
 200   GNUNET_free (map->map);
 201   GNUNET_free (map);
 202 }
 203
 204
 205 /**
 206  * Compute the index of the bucket for the given key.
 207  *
 208  * @param map hash map for which to compute the index
 209  * @param key what key should the index be computed for
 210  * @return offset into the "map" array of "map"
 211  */
 212 static unsigned int
 213 idx_of (const struct GNUNET_CONTAINER_MultiHashMap *map,
 214         const struct GNUNET_HashCode *key)
 215 {
 216   GNUNET_assert (map != NULL);
 217   return (*(unsigned int *) key) % map->map_length;
 218 }
 219
 220
 221 /**
 222  * Get the number of key-value pairs in the map.
 223  *
 224  * @param map the map
 225  * @return the number of key value pairs
 226  */
 227 unsigned int
 228 GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap
 229                                     *map)
 230 {
 231   return map->size;
 232 }
 233
 234
 235 /**
 236  * Given a key find a value in the map matching the key.
 237  *
 238  * @param map the map
 239  * @param key what to look for
 240  * @return NULL if no value was found; note that
 241  *   this is indistinguishable from values that just
 242  *   happen to be NULL; use "contains" to test for
 243  *   key-value pairs with value NULL
 244  */
 245 void *
 246 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap
 247                                    *map, const struct GNUNET_HashCode *key)
 248 {
 249   union MapEntry me;
 250
 251   me = map->map[idx_of (map, key)];
 252   if (map->use_small_entries)
 253   {
 254     struct SmallMapEntry *sme;
 255
 256     for (sme = me.sme; NULL != sme; sme = sme->next)
 257       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
 258         return sme->value;
 259   }
 260   else
 261   {
 262     struct BigMapEntry *bme;
 263
 264     for (bme = me.bme; NULL != bme; bme = bme->next)
 265       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
 266         return bme->value;
 267   }
 268   return NULL;
 269 }
 270
 271
 272 /**
 273  * Iterate over all entries in the map.
 274  *
 275  * @param map the map
 276  * @param it function to call on each entry
 277  * @param it_cls extra argument to it
 278  * @return the number of key value pairs processed,
 279  *         GNUNET_SYSERR if it aborted iteration
 280  */
 281 int
 282 GNUNET_CONTAINER_multihashmap_iterate (const struct
 283                                        GNUNET_CONTAINER_MultiHashMap *map,
 284                                        GNUNET_CONTAINER_HashMapIterator it,
 285                                        void *it_cls)
 286 {
 287   int count;
 288   unsigned int i;
 289   union MapEntry me;
 290   struct GNUNET_HashCode kc;
 291
 292   count = 0;
 293   GNUNET_assert (NULL != map);
 294   for (i = 0; i < map->map_length; i++)
 295   {
 296     me = map->map[i];
 297     if (map->use_small_entries)
 298     {
 299       struct SmallMapEntry *sme;
 300       struct SmallMapEntry *nxt;
 301
 302       nxt = me.sme;
 303       while (NULL != (sme = nxt))
 304       {
 305         nxt = sme->next;
 306         if (NULL != it)
 307         {
 308           if (GNUNET_OK != it (it_cls, sme->key, sme->value))
 309             return GNUNET_SYSERR;
 310         }
 311         count++;
 312       }
 313     }
 314     else
 315     {
 316       struct BigMapEntry *bme;
 317       struct BigMapEntry *nxt;
 318
 319       nxt = me.bme;
 320       while (NULL != (bme = nxt))
 321       {
 322         nxt = bme->next;
 323         if (NULL != it)
 324         {
 325           kc = bme->key;
 326           if (GNUNET_OK != it (it_cls, &kc, bme->value))
 327             return GNUNET_SYSERR;
 328         }
 329         count++;
 330       }
 331     }
 332   }
 333   return count;
 334 }
 335
 336
 337 /**
 338  * Remove the given key-value pair from the map.  Note that if the
 339  * key-value pair is in the map multiple times, only one of the pairs
 340  * will be removed.
 341  *
 342  * @param map the map
 343  * @param key key of the key-value pair
 344  * @param value value of the key-value pair
 345  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
 346  *  is not in the map
 347  */
 348 int
 349 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
 350                                       const struct GNUNET_HashCode *key,
 351                                       const void *value)
 352 {
 353   union MapEntry me;
 354   unsigned int i;
 355
 356   i = idx_of (map, key);
 357   me = map->map[i];
 358   if (map->use_small_entries)
 359   {
 360     struct SmallMapEntry *sme;
 361     struct SmallMapEntry *p;
 362
 363     p = NULL;
 364     for (sme = me.sme; NULL != sme; sme = sme->next)
 365     {
 366       if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) &&
 367           (value == sme->value))
 368       {
 369         if (NULL == p)
 370           map->map[i].sme = sme->next;
 371         else
 372           p->next = sme->next;
 373         GNUNET_free (sme);
 374         map->size--;
 375         return GNUNET_YES;
 376       }
 377       p = sme;
 378     }
 379   }
 380   else
 381   {
 382     struct BigMapEntry *bme;
 383     struct BigMapEntry *p;
 384
 385     p = NULL;
 386     for (bme = me.bme; NULL != bme; bme = bme->next)
 387     {
 388       if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) &&
 389           (value == bme->value))
 390       {
 391         if (NULL == p)
 392           map->map[i].bme = bme->next;
 393         else
 394           p->next = bme->next;
 395         GNUNET_free (bme);
 396         map->size--;
 397         return GNUNET_YES;
 398       }
 399       p = bme;
 400     }
 401   }
 402   return GNUNET_NO;
 403 }
 404
 405
 406 /**
 407  * Remove all entries for the given key from the map.
 408  * Note that the values would not be "freed".
 409  *
 410  * @param map the map
 411  * @param key identifies values to be removed
 412  * @return number of values removed
 413  */
 414 int
 415 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap
 416                                           *map, const struct GNUNET_HashCode *key)
 417 {
 418   union MapEntry me;
 419   unsigned int i;
 420   int ret;
 421
 422   ret = 0;
 423   i = idx_of (map, key);
 424   me = map->map[i];
 425   if (map->use_small_entries)
 426   {
 427     struct SmallMapEntry *sme;
 428     struct SmallMapEntry *p;
 429
 430     p = NULL;
 431     sme = me.sme;
 432     while (NULL != sme)
 433     {
 434       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
 435       {
 436         if (NULL == p)
 437           map->map[i].sme = sme->next;
 438         else
 439           p->next = sme->next;
 440         GNUNET_free (sme);
 441         map->size--;
 442         if (NULL == p)
 443           sme = map->map[i].sme;
 444         else
 445           sme = p->next;
 446         ret++;
 447       }
 448       else
 449       {
 450         p = sme;
 451         sme = sme->next;
 452       }
 453     }
 454   }
 455   else
 456   {
 457     struct BigMapEntry *bme;
 458     struct BigMapEntry *p;
 459
 460     p = NULL;
 461     bme = me.bme;
 462     while (NULL != bme)
 463     {
 464       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
 465       {
 466         if (NULL == p)
 467           map->map[i].bme = bme->next;
 468         else
 469           p->next = bme->next;
 470         GNUNET_free (bme);
 471         map->size--;
 472         if (NULL == p)
 473           bme = map->map[i].bme;
 474         else
 475           bme = p->next;
 476         ret++;
 477       }
 478       else
 479       {
 480         p = bme;
 481         bme = bme->next;
 482       }
 483     }
 484   }
 485   return ret;
 486 }
 487
 488
 489 /**
 490  * Check if the map contains any value under the given
 491  * key (including values that are NULL).
 492  *
 493  * @param map the map
 494  * @param key the key to test if a value exists for it
 495  * @return GNUNET_YES if such a value exists,
 496  *         GNUNET_NO if not
 497  */
 498 int
 499 GNUNET_CONTAINER_multihashmap_contains (const struct
 500                                         GNUNET_CONTAINER_MultiHashMap *map,
 501                                         const struct GNUNET_HashCode *key)
 502 {
 503   union MapEntry me;
 504
 505   me = map->map[idx_of (map, key)];
 506   if (map->use_small_entries)
 507   {
 508     struct SmallMapEntry *sme;
 509
 510     for (sme = me.sme; NULL != sme; sme = sme->next)
 511       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
 512         return GNUNET_YES;
 513   }
 514   else
 515   {
 516     struct BigMapEntry *bme;
 517
 518     for (bme = me.bme; NULL != bme; bme = bme->next)
 519       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
 520         return GNUNET_YES;
 521   }
 522   return GNUNET_NO;
 523 }
 524
 525
 526 /**
 527  * Check if the map contains the given value under the given
 528  * key.
 529  *
 530  * @param map the map
 531  * @param key the key to test if a value exists for it
 532  * @param value value to test for
 533  * @return GNUNET_YES if such a value exists,
 534  *         GNUNET_NO if not
 535  */
 536 int
 537 GNUNET_CONTAINER_multihashmap_contains_value (const struct
 538                                               GNUNET_CONTAINER_MultiHashMap
 539                                               *map, const struct GNUNET_HashCode *key,
 540                                               const void *value)
 541 {
 542   union MapEntry me;
 543
 544   me = map->map[idx_of (map, key)];
 545   if (map->use_small_entries)
 546   {
 547     struct SmallMapEntry *sme;
 548
 549     for (sme = me.sme; NULL != sme; sme = sme->next)
 550       if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) &&
 551            (sme->value == value) )
 552         return GNUNET_YES;
 553   }
 554   else
 555   {
 556     struct BigMapEntry *bme;
 557
 558     for (bme = me.bme; NULL != bme; bme = bme->next)
 559       if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) &&
 560            (bme->value == value) )
 561         return GNUNET_YES;
 562   }
 563   return GNUNET_NO;
 564 }
 565
 566
 567 /**
 568  * Grow the given map to a more appropriate size.
 569  *
 570  * @param map the hash map to grow
 571  */
 572 static void
 573 grow (struct GNUNET_CONTAINER_MultiHashMap *map)
 574 {
 575   union MapEntry *old_map;
 576   union MapEntry *new_map;
 577   unsigned int old_len;
 578   unsigned int new_len;
 579   unsigned int idx;
 580   unsigned int i;
 581
 582   old_map = map->map;
 583   old_len = map->map_length;
 584   new_len = old_len * 2;
 585   new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len);
 586   map->map_length = new_len;
 587   map->map = new_map;
 588   for (i = 0; i < old_len; i++)
 589   {
 590     if (map->use_small_entries)
 591     {
 592       struct SmallMapEntry *sme;
 593
 594       while (NULL != (sme = old_map[i].sme))
 595       {
 596         old_map[i].sme = sme->next;
 597         idx = idx_of (map, sme->key);
 598         sme->next = new_map[idx].sme;
 599         new_map[idx].sme = sme;
 600       }
 601     }
 602     else
 603     {
 604       struct BigMapEntry *bme;
 605
 606       while (NULL != (bme = old_map[i].bme))
 607       {
 608         old_map[i].bme = bme->next;
 609         idx = idx_of (map, &bme->key);
 610         bme->next = new_map[idx].bme;
 611         new_map[idx].bme = bme;
 612       }
 613     }
 614   }
 615   GNUNET_free (old_map);
 616 }
 617
 618
 619 /**
 620  * Store a key-value pair in the map.
 621  *
 622  * @param map the map
 623  * @param key key to use
 624  * @param value value to use
 625  * @param opt options for put
 626  * @return GNUNET_OK on success,
 627  *         GNUNET_NO if a value was replaced (with REPLACE)
 628  *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 629  *                       value already exists
 630  */
 631 int
 632 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
 633                                    const struct GNUNET_HashCode *key,
 634                                    void *value,
 635                                    enum GNUNET_CONTAINER_MultiHashMapOption opt)
 636 {
 637   union MapEntry me;
 638   unsigned int i;
 639
 640   i = idx_of (map, key);
 641   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 642       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 643   {
 644     me = map->map[i];
 645     if (map->use_small_entries)
 646     {
 647       struct SmallMapEntry *sme;
 648
 649       for (sme = me.sme; NULL != sme; sme = sme->next)
 650         if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
 651         {
 652           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 653             return GNUNET_SYSERR;
 654           sme->value = value;
 655           return GNUNET_NO;
 656         }
 657     }
 658     else
 659     {
 660       struct BigMapEntry *bme;
 661
 662       for (bme = me.bme; NULL != bme; bme = bme->next)
 663         if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
 664         {
 665           if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 666             return GNUNET_SYSERR;
 667           bme->value = value;
 668           return GNUNET_NO;
 669         }
 670     }
 671   }
 672   if (map->size / 3 >= map->map_length / 4)
 673   {
 674     grow (map);
 675     i = idx_of (map, key);
 676   }
 677   if (map->use_small_entries)
 678   {
 679     struct SmallMapEntry *sme;
 680
 681     sme = GNUNET_malloc (sizeof (struct SmallMapEntry));
 682     sme->key = key;
 683     sme->value = value;
 684     sme->next = map->map[i].sme;
 685     map->map[i].sme = sme;
 686   }
 687   else
 688   {
 689     struct BigMapEntry *bme;
 690
 691     bme = GNUNET_malloc (sizeof (struct BigMapEntry));
 692     bme->key = *key;
 693     bme->value = value;
 694     bme->next = map->map[i].bme;
 695     map->map[i].bme = bme;
 696   }
 697   map->size++;
 698   return GNUNET_OK;
 699 }
 700
 701
 702 /**
 703  * Iterate over all entries in the map that match a particular key.
 704  *
 705  * @param map the map
 706  * @param key key that the entries must correspond to
 707  * @param it function to call on each entry
 708  * @param it_cls extra argument to it
 709  * @return the number of key value pairs processed,
 710  *         GNUNET_SYSERR if it aborted iteration
 711  */
 712 int
 713 GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 714                                             GNUNET_CONTAINER_MultiHashMap *map,
 715                                             const struct GNUNET_HashCode *key,
 716                                             GNUNET_CONTAINER_HashMapIterator it,
 717                                             void *it_cls)
 718 {
 719   int count;
 720   union MapEntry me;
 721
 722   count = 0;
 723   me = map->map[idx_of (map, key)];
 724   if (map->use_small_entries)
 725   {
 726     struct SmallMapEntry *sme;
 727     struct SmallMapEntry *nxt;
 728
 729     nxt = me.sme;
 730     while (NULL != (sme = nxt))
 731     {
 732       nxt = sme->next;
 733       if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
 734         continue;
 735       if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value)))
 736         return GNUNET_SYSERR;
 737       count++;
 738     }
 739   }
 740   else
 741   {
 742     struct BigMapEntry *bme;
 743     struct BigMapEntry *nxt;
 744
 745     nxt = me.bme;
 746     while (NULL != (bme = nxt))
 747     {
 748       nxt = bme->next;
 749       if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
 750         continue;
 751       if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value)))
 752         return GNUNET_SYSERR;
 753       count++;
 754     }
 755   }
 756   return count;
 757 }
 758
 759
 760 /* end of container_multihashmap.c */