hashmap.h

   1 #ifndef HASHMAP_H
   2 #define HASHMAP_H
   3
   4 #include "hash.h"
   5
   6 /*
   7  * Generic implementation of hash-based key-value mappings.
   8  *
   9  * An example that maps long to a string:
  10  * For the sake of the example this allows to lookup exact values, too
  11  * (i.e. it is operated as a set, the value is part of the key)
  12  * -------------------------------------
  13  *
  14  * struct hashmap map;
  15  * struct long2string {
  16  *     struct hashmap_entry ent;
  17  *     long key;
  18  *     char value[FLEX_ARRAY];   // be careful with allocating on stack!
  19  * };
  20  *
  21  * #define COMPARE_VALUE 1
  22  *
  23  * static int long2string_cmp(const void *hashmap_cmp_fn_data,
  24  *                            const struct hashmap_entry *eptr,
  25  *                            const struct hashmap_entry *entry_or_key,
  26  *                            const void *keydata)
  27  * {
  28  *     const char *string = keydata;
  29  *     unsigned flags = *(unsigned *)hashmap_cmp_fn_data;
  30  *     const struct long2string *e1, *e2;
  31  *
  32  *     e1 = container_of(eptr, const struct long2string, ent);
  33  *     e2 = container_of(entry_or_key, const struct long2string, ent);
  34  *
  35  *     if (flags & COMPARE_VALUE)
  36  *         return e1->key != e2->key ||
  37  *                  strcmp(e1->value, string ? string : e2->value);
  38  *     else
  39  *         return e1->key != e2->key;
  40  * }
  41  *
  42  * int main(int argc, char **argv)
  43  * {
  44  *     long key;
  45  *     char value[255], action[32];
  46  *     unsigned flags = 0;
  47  *
  48  *     hashmap_init(&map, long2string_cmp, &flags, 0);
  49  *
  50  *     while (scanf("%s %ld %s", action, &key, value)) {
  51  *
  52  *         if (!strcmp("add", action)) {
  53  *             struct long2string *e;
  54  *             FLEX_ALLOC_STR(e, value, value);
  55  *             hashmap_entry_init(&e->ent, memhash(&key, sizeof(long)));
  56  *             e->key = key;
  57  *             hashmap_add(&map, &e->ent);
  58  *         }
  59  *
  60  *         if (!strcmp("print_all_by_key", action)) {
  61  *             struct long2string k, *e;
  62  *             hashmap_entry_init(&k.ent, memhash(&key, sizeof(long)));
  63  *             k.key = key;
  64  *
  65  *             flags &= ~COMPARE_VALUE;
  66  *             e = hashmap_get_entry(&map, &k, ent, NULL);
  67  *             if (e) {
  68  *                 printf("first: %ld %s\n", e->key, e->value);
  69  *                 while ((e = hashmap_get_next_entry(&map, e,
  70  *                                              struct long2string, ent))) {
  71  *                     printf("found more: %ld %s\n", e->key, e->value);
  72  *                 }
  73  *             }
  74  *         }
  75  *
  76  *         if (!strcmp("has_exact_match", action)) {
  77  *             struct long2string *e;
  78  *             FLEX_ALLOC_STR(e, value, value);
  79  *             hashmap_entry_init(&e->ent, memhash(&key, sizeof(long)));
  80  *             e->key = key;
  81  *
  82  *             flags |= COMPARE_VALUE;
  83  *             printf("%sfound\n",
  84  *                    hashmap_get(&map, &e->ent, NULL) ? "" : "not ");
  85  *             free(e);
  86  *         }
  87  *
  88  *         if (!strcmp("has_exact_match_no_heap_alloc", action)) {
  89  *             struct long2string k;
  90  *             hashmap_entry_init(&k.ent, memhash(&key, sizeof(long)));
  91  *             k.key = key;
  92  *
  93  *             flags |= COMPARE_VALUE;
  94  *             printf("%sfound\n",
  95  *                    hashmap_get(&map, &k.ent, value) ? "" : "not ");
  96  *         }
  97  *
  98  *         if (!strcmp("end", action)) {
  99  *             hashmap_free_entries(&map, struct long2string, ent);
 100  *             break;
 101  *         }
 102  *     }
 103  *
 104  *     return 0;
 105  * }
 106  */
 107
 108 /*
 109  * Ready-to-use hash functions for strings, using the FNV-1 algorithm (see
 110  * http://www.isthe.com/chongo/tech/comp/fnv).
 111  * `strhash` and `strihash` take 0-terminated strings, while `memhash` and
 112  * `memihash` operate on arbitrary-length memory.
 113  * `strihash` and `memihash` are case insensitive versions.
 114  * `memihash_cont` is a variant of `memihash` that allows a computation to be
 115  * continued with another chunk of data.
 116  */
 117 unsigned int strhash(const char *buf);
 118 unsigned int strihash(const char *buf);
 119 unsigned int memhash(const void *buf, size_t len);
 120 unsigned int memihash(const void *buf, size_t len);
 121 unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len);
 122
 123 /*
 124  * Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code
 125  * for use in hash tables. Cryptographic hashes are supposed to have
 126  * uniform distribution, so in contrast to `memhash()`, this just copies
 127  * the first `sizeof(int)` bytes without shuffling any bits. Note that
 128  * the results will be different on big-endian and little-endian
 129  * platforms, so they should not be stored or transferred over the net.
 130  */
 131 static inline unsigned int oidhash(const struct object_id *oid)
 132 {
 133         /*
 134          * Equivalent to 'return *(unsigned int *)oid->hash;', but safe on
 135          * platforms that don't support unaligned reads.
 136          */
 137         unsigned int hash;
 138         memcpy(&hash, oid->hash, sizeof(hash));
 139         return hash;
 140 }
 141
 142 /*
 143  * struct hashmap_entry is an opaque structure representing an entry in the
 144  * hash table.
 145  * Ideally it should be followed by an int-sized member to prevent unused
 146  * memory on 64-bit systems due to alignment.
 147  */
 148 struct hashmap_entry {
 149         /*
 150          * next points to the next entry in case of collisions (i.e. if
 151          * multiple entries map to the same bucket)
 152          */
 153         struct hashmap_entry *next;
 154
 155         /* entry's hash code */
 156         unsigned int hash;
 157 };
 158
 159 /*
 160  * User-supplied function to test two hashmap entries for equality. Shall
 161  * return 0 if the entries are equal.
 162  *
 163  * This function is always called with non-NULL `entry` and `entry_or_key`
 164  * parameters that have the same hash code.
 165  *
 166  * When looking up an entry, the `key` and `keydata` parameters to hashmap_get
 167  * and hashmap_remove are always passed as second `entry_or_key` and third
 168  * argument `keydata`, respectively. Otherwise, `keydata` is NULL.
 169  *
 170  * When it is too expensive to allocate a user entry (either because it is
 171  * large or varialbe sized, such that it is not on the stack), then the
 172  * relevant data to check for equality should be passed via `keydata`.
 173  * In this case `key` can be a stripped down version of the user key data
 174  * or even just a hashmap_entry having the correct hash.
 175  *
 176  * The `hashmap_cmp_fn_data` entry is the pointer given in the init function.
 177  */
 178 typedef int (*hashmap_cmp_fn)(const void *hashmap_cmp_fn_data,
 179                               const struct hashmap_entry *entry,
 180                               const struct hashmap_entry *entry_or_key,
 181                               const void *keydata);
 182
 183 /*
 184  * struct hashmap is the hash table structure. Members can be used as follows,
 185  * but should not be modified directly.
 186  */
 187 struct hashmap {
 188         struct hashmap_entry **table;
 189
 190         /* Stores the comparison function specified in `hashmap_init()`. */
 191         hashmap_cmp_fn cmpfn;
 192         const void *cmpfn_data;
 193
 194         /* total number of entries (0 means the hashmap is empty) */
 195         unsigned int private_size; /* use hashmap_get_size() */
 196
 197         /*
 198          * tablesize is the allocated size of the hash table. A non-0 value
 199          * indicates that the hashmap is initialized. It may also be useful
 200          * for statistical purposes (i.e. `size / tablesize` is the current
 201          * load factor).
 202          */
 203         unsigned int tablesize;
 204
 205         unsigned int grow_at;
 206         unsigned int shrink_at;
 207
 208         unsigned int do_count_items : 1;
 209 };
 210
 211 /* hashmap functions */
 212
 213 /*
 214  * Initializes a hashmap structure.
 215  *
 216  * `map` is the hashmap to initialize.
 217  *
 218  * The `equals_function` can be specified to compare two entries for equality.
 219  * If NULL, entries are considered equal if their hash codes are equal.
 220  *
 221  * The `equals_function_data` parameter can be used to provide additional data
 222  * (a callback cookie) that will be passed to `equals_function` each time it
 223  * is called. This allows a single `equals_function` to implement multiple
 224  * comparison functions.
 225  *
 226  * If the total number of entries is known in advance, the `initial_size`
 227  * parameter may be used to preallocate a sufficiently large table and thus
 228  * prevent expensive resizing. If 0, the table is dynamically resized.
 229  */
 230 void hashmap_init(struct hashmap *map,
 231                          hashmap_cmp_fn equals_function,
 232                          const void *equals_function_data,
 233                          size_t initial_size);
 234
 235 /* internal function for freeing hashmap */
 236 void hashmap_free_(struct hashmap *map, ssize_t offset);
 237
 238 /*
 239  * Frees a hashmap structure and allocated memory, leaves entries undisturbed
 240  */
 241 #define hashmap_free(map) hashmap_free_(map, -1)
 242
 243 /*
 244  * Frees @map and all entries.  @type is the struct type of the entry
 245  * where @member is the hashmap_entry struct used to associate with @map
 246  */
 247 #define hashmap_free_entries(map, type, member) \
 248         hashmap_free_(map, offsetof(type, member));
 249
 250 /* hashmap_entry functions */
 251
 252 /*
 253  * Initializes a hashmap_entry structure.
 254  *
 255  * `entry` points to the entry to initialize.
 256  * `hash` is the hash code of the entry.
 257  *
 258  * The hashmap_entry structure does not hold references to external resources,
 259  * and it is safe to just discard it once you are done with it (i.e. if
 260  * your structure was allocated with xmalloc(), you can just free(3) it,
 261  * and if it is on stack, you can just let it go out of scope).
 262  */
 263 static inline void hashmap_entry_init(struct hashmap_entry *e,
 264                                         unsigned int hash)
 265 {
 266         e->hash = hash;
 267         e->next = NULL;
 268 }
 269
 270 /*
 271  * Return the number of items in the map.
 272  */
 273 static inline unsigned int hashmap_get_size(struct hashmap *map)
 274 {
 275         if (map->do_count_items)
 276                 return map->private_size;
 277
 278         BUG("hashmap_get_size: size not set");
 279         return 0;
 280 }
 281
 282 /*
 283  * Returns the hashmap entry for the specified key, or NULL if not found.
 284  *
 285  * `map` is the hashmap structure.
 286  *
 287  * `key` is a user data structure that starts with hashmap_entry that has at
 288  * least been initialized with the proper hash code (via `hashmap_entry_init`).
 289  *
 290  * `keydata` is a data structure that holds just enough information to check
 291  * for equality to a given entry.
 292  *
 293  * If the key data is variable-sized (e.g. a FLEX_ARRAY string) or quite large,
 294  * it is undesirable to create a full-fledged entry structure on the heap and
 295  * copy all the key data into the structure.
 296  *
 297  * In this case, the `keydata` parameter can be used to pass
 298  * variable-sized key data directly to the comparison function, and the `key`
 299  * parameter can be a stripped-down, fixed size entry structure allocated on the
 300  * stack.
 301  *
 302  * If an entry with matching hash code is found, `key` and `keydata` are passed
 303  * to `hashmap_cmp_fn` to decide whether the entry matches the key.
 304  */
 305 struct hashmap_entry *hashmap_get(const struct hashmap *map,
 306                                 const struct hashmap_entry *key,
 307                                 const void *keydata);
 308
 309 /*
 310  * Returns the hashmap entry for the specified hash code and key data,
 311  * or NULL if not found.
 312  *
 313  * `map` is the hashmap structure.
 314  * `hash` is the hash code of the entry to look up.
 315  *
 316  * If an entry with matching hash code is found, `keydata` is passed to
 317  * `hashmap_cmp_fn` to decide whether the entry matches the key. The
 318  * `entry_or_key` parameter of `hashmap_cmp_fn` points to a hashmap_entry
 319  * structure that should not be used in the comparison.
 320  */
 321 static inline struct hashmap_entry *hashmap_get_from_hash(
 322                                         const struct hashmap *map,
 323                                         unsigned int hash,
 324                                         const void *keydata)
 325 {
 326         struct hashmap_entry key;
 327         hashmap_entry_init(&key, hash);
 328         return hashmap_get(map, &key, keydata);
 329 }
 330
 331 /*
 332  * Returns the next equal hashmap entry, or NULL if not found. This can be
 333  * used to iterate over duplicate entries (see `hashmap_add`).
 334  *
 335  * `map` is the hashmap structure.
 336  * `entry` is the hashmap_entry to start the search from, obtained via a previous
 337  * call to `hashmap_get` or `hashmap_get_next`.
 338  */
 339 struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
 340                         const struct hashmap_entry *entry);
 341
 342 /*
 343  * Adds a hashmap entry. This allows to add duplicate entries (i.e.
 344  * separate values with the same key according to hashmap_cmp_fn).
 345  *
 346  * `map` is the hashmap structure.
 347  * `entry` is the entry to add.
 348  */
 349 void hashmap_add(struct hashmap *map, struct hashmap_entry *entry);
 350
 351 /*
 352  * Adds or replaces a hashmap entry. If the hashmap contains duplicate
 353  * entries equal to the specified entry, only one of them will be replaced.
 354  *
 355  * `map` is the hashmap structure.
 356  * `entry` is the entry to add or replace.
 357  * Returns the replaced entry, or NULL if not found (i.e. the entry was added).
 358  */
 359 struct hashmap_entry *hashmap_put(struct hashmap *map,
 360                                 struct hashmap_entry *entry);
 361
 362 /*
 363  * Adds or replaces a hashmap entry contained within @keyvar,
 364  * where @keyvar is a pointer to a struct containing a
 365  * "struct hashmap_entry" @member.
 366  *
 367  * Returns the replaced pointer which is of the same type as @keyvar,
 368  * or NULL if not found.
 369  */
 370 #define hashmap_put_entry(map, keyvar, member) \
 371         container_of_or_null_offset(hashmap_put(map, &(keyvar)->member), \
 372                                 OFFSETOF_VAR(keyvar, member))
 373
 374 /*
 375  * Removes a hashmap entry matching the specified key. If the hashmap contains
 376  * duplicate entries equal to the specified key, only one of them will be
 377  * removed. Returns the removed entry, or NULL if not found.
 378  *
 379  * Argument explanation is the same as in `hashmap_get`.
 380  */
 381 struct hashmap_entry *hashmap_remove(struct hashmap *map,
 382                                         const struct hashmap_entry *key,
 383                                         const void *keydata);
 384
 385 /*
 386  * Removes a hashmap entry contained within @keyvar,
 387  * where @keyvar is a pointer to a struct containing a
 388  * "struct hashmap_entry" @member.
 389  *
 390  * See `hashmap_get` for an explanation of @keydata
 391  *
 392  * Returns the replaced pointer which is of the same type as @keyvar,
 393  * or NULL if not found.
 394  */
 395 #define hashmap_remove_entry(map, keyvar, member, keydata) \
 396         container_of_or_null_offset( \
 397                         hashmap_remove(map, &(keyvar)->member, keydata), \
 398                         OFFSETOF_VAR(keyvar, member))
 399
 400 /*
 401  * Returns the `bucket` an entry is stored in.
 402  * Useful for multithreaded read access.
 403  */
 404 int hashmap_bucket(const struct hashmap *map, unsigned int hash);
 405
 406 /*
 407  * Used to iterate over all entries of a hashmap. Note that it is
 408  * not safe to add or remove entries to the hashmap while
 409  * iterating.
 410  */
 411 struct hashmap_iter {
 412         struct hashmap *map;
 413         struct hashmap_entry *next;
 414         unsigned int tablepos;
 415 };
 416
 417 /* Initializes a `hashmap_iter` structure. */
 418 void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);
 419
 420 /* Returns the next hashmap_entry, or NULL if there are no more entries. */
 421 struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter);
 422
 423 /* Initializes the iterator and returns the first entry, if any. */
 424 static inline struct hashmap_entry *hashmap_iter_first(struct hashmap *map,
 425                 struct hashmap_iter *iter)
 426 {
 427         hashmap_iter_init(map, iter);
 428         return hashmap_iter_next(iter);
 429 }
 430
 431 /*
 432  * returns the first entry in @map using @iter, where the entry is of
 433  * @type (e.g. "struct foo") and @member is the name of the
 434  * "struct hashmap_entry" in @type
 435  */
 436 #define hashmap_iter_first_entry(map, iter, type, member) \
 437         container_of_or_null(hashmap_iter_first(map, iter), type, member)
 438
 439 /* internal macro for hashmap_for_each_entry */
 440 #define hashmap_iter_next_entry_offset(iter, offset) \
 441         container_of_or_null_offset(hashmap_iter_next(iter), offset)
 442
 443 /* internal macro for hashmap_for_each_entry */
 444 #define hashmap_iter_first_entry_offset(map, iter, offset) \
 445         container_of_or_null_offset(hashmap_iter_first(map, iter), offset)
 446
 447 /*
 448  * iterate through @map using @iter, @var is a pointer to a type
 449  * containing a @member which is a "struct hashmap_entry"
 450  */
 451 #define hashmap_for_each_entry(map, iter, var, member) \
 452         for (var = hashmap_iter_first_entry_offset(map, iter, \
 453                                                 OFFSETOF_VAR(var, member)); \
 454                 var; \
 455                 var = hashmap_iter_next_entry_offset(iter, \
 456                                                 OFFSETOF_VAR(var, member)))
 457
 458 /*
 459  * returns a pointer of type matching @keyvar, or NULL if nothing found.
 460  * @keyvar is a pointer to a struct containing a
 461  * "struct hashmap_entry" @member.
 462  */
 463 #define hashmap_get_entry(map, keyvar, member, keydata) \
 464         container_of_or_null_offset( \
 465                                 hashmap_get(map, &(keyvar)->member, keydata), \
 466                                 OFFSETOF_VAR(keyvar, member))
 467
 468 #define hashmap_get_entry_from_hash(map, hash, keydata, type, member) \
 469         container_of_or_null(hashmap_get_from_hash(map, hash, keydata), \
 470                                 type, member)
 471 /*
 472  * returns the next equal pointer to @var, or NULL if not found.
 473  * @var is a pointer of any type containing "struct hashmap_entry"
 474  * @member is the name of the "struct hashmap_entry" field
 475  */
 476 #define hashmap_get_next_entry(map, var, member) \
 477         container_of_or_null_offset(hashmap_get_next(map, &(var)->member), \
 478                                 OFFSETOF_VAR(var, member))
 479
 480 /*
 481  * iterate @map starting from @var, where @var is a pointer of @type
 482  * and @member is the name of the "struct hashmap_entry" field in @type
 483  */
 484 #define hashmap_for_each_entry_from(map, var, member) \
 485         for (; \
 486                 var; \
 487                 var = hashmap_get_next_entry(map, var, member))
 488
 489 /*
 490  * Disable item counting and automatic rehashing when adding/removing items.
 491  *
 492  * Normally, the hashmap keeps track of the number of items in the map
 493  * and uses it to dynamically resize it.  This (both the counting and
 494  * the resizing) can cause problems when the map is being used by
 495  * threaded callers (because the hashmap code does not know about the
 496  * locking strategy used by the threaded callers and therefore, does
 497  * not know how to protect the "private_size" counter).
 498  */
 499 static inline void hashmap_disable_item_counting(struct hashmap *map)
 500 {
 501         map->do_count_items = 0;
 502 }
 503
 504 /*
 505  * Re-enable item counting when adding/removing items.
 506  * If counting is currently disabled, it will force count them.
 507  * It WILL NOT automatically rehash them.
 508  */
 509 static inline void hashmap_enable_item_counting(struct hashmap *map)
 510 {
 511         unsigned int n = 0;
 512         struct hashmap_iter iter;
 513
 514         if (map->do_count_items)
 515                 return;
 516
 517         hashmap_iter_init(map, &iter);
 518         while (hashmap_iter_next(&iter))
 519                 n++;
 520
 521         map->do_count_items = 1;
 522         map->private_size = n;
 523 }
 524
 525 /* String interning */
 526
 527 /*
 528  * Returns the unique, interned version of the specified string or data,
 529  * similar to the `String.intern` API in Java and .NET, respectively.
 530  * Interned strings remain valid for the entire lifetime of the process.
 531  *
 532  * Can be used as `[x]strdup()` or `xmemdupz` replacement, except that interned
 533  * strings / data must not be modified or freed.
 534  *
 535  * Interned strings are best used for short strings with high probability of
 536  * duplicates.
 537  *
 538  * Uses a hashmap to store the pool of interned strings.
 539  */
 540 const void *memintern(const void *data, size_t len);
 541 static inline const char *strintern(const char *string)
 542 {
 543         return memintern(string, strlen(string));
 544 }
 545
 546 #endif