word diff: handle zero length matches
[git] / 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_clear_and_free(&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 variable 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 #define HASHMAP_INIT(fn, data) { .cmpfn = fn, .cmpfn_data = data, \
214                                  .do_count_items = 1 }
215
216 /*
217  * Initializes a hashmap structure.
218  *
219  * `map` is the hashmap to initialize.
220  *
221  * The `equals_function` can be specified to compare two entries for equality.
222  * If NULL, entries are considered equal if their hash codes are equal.
223  *
224  * The `equals_function_data` parameter can be used to provide additional data
225  * (a callback cookie) that will be passed to `equals_function` each time it
226  * is called. This allows a single `equals_function` to implement multiple
227  * comparison functions.
228  *
229  * If the total number of entries is known in advance, the `initial_size`
230  * parameter may be used to preallocate a sufficiently large table and thus
231  * prevent expensive resizing. If 0, the table is dynamically resized.
232  */
233 void hashmap_init(struct hashmap *map,
234                   hashmap_cmp_fn equals_function,
235                   const void *equals_function_data,
236                   size_t initial_size);
237
238 /* internal functions for clearing or freeing hashmap */
239 void hashmap_partial_clear_(struct hashmap *map, ssize_t offset);
240 void hashmap_clear_(struct hashmap *map, ssize_t offset);
241
242 /*
243  * Frees a hashmap structure and allocated memory for the table, but does not
244  * free the entries nor anything they point to.
245  *
246  * Usage note:
247  *
248  * Many callers will need to iterate over all entries and free the data each
249  * entry points to; in such a case, they can free the entry itself while at it.
250  * Thus, you might see:
251  *
252  *    hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) {
253  *      free(e->somefield);
254  *      free(e);
255  *    }
256  *    hashmap_clear(map);
257  *
258  * instead of
259  *
260  *    hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) {
261  *      free(e->somefield);
262  *    }
263  *    hashmap_clear_and_free(map, struct my_entry_struct, hashmap_entry_name);
264  *
265  * to avoid the implicit extra loop over the entries.  However, if there are
266  * no special fields in your entry that need to be freed beyond the entry
267  * itself, it is probably simpler to avoid the explicit loop and just call
268  * hashmap_clear_and_free().
269  */
270 #define hashmap_clear(map) hashmap_clear_(map, -1)
271
272 /*
273  * Similar to hashmap_clear(), except that the table is no deallocated; it
274  * is merely zeroed out but left the same size as before.  If the hashmap
275  * will be reused, this avoids the overhead of deallocating and
276  * reallocating map->table.  As with hashmap_clear(), you may need to free
277  * the entries yourself before calling this function.
278  */
279 #define hashmap_partial_clear(map) hashmap_partial_clear_(map, -1)
280
281 /*
282  * Similar to hashmap_clear() but also frees all entries.  @type is the
283  * struct type of the entry where @member is the hashmap_entry struct used
284  * to associate with @map.
285  *
286  * See usage note above hashmap_clear().
287  */
288 #define hashmap_clear_and_free(map, type, member) \
289         hashmap_clear_(map, offsetof(type, member))
290
291 /*
292  * Similar to hashmap_partial_clear() but also frees all entries.  @type is
293  * the struct type of the entry where @member is the hashmap_entry struct
294  * used to associate with @map.
295  *
296  * See usage note above hashmap_clear().
297  */
298 #define hashmap_partial_clear_and_free(map, type, member) \
299         hashmap_partial_clear_(map, offsetof(type, member))
300
301 /* hashmap_entry functions */
302
303 /*
304  * Initializes a hashmap_entry structure.
305  *
306  * `entry` points to the entry to initialize.
307  * `hash` is the hash code of the entry.
308  *
309  * The hashmap_entry structure does not hold references to external resources,
310  * and it is safe to just discard it once you are done with it (i.e. if
311  * your structure was allocated with xmalloc(), you can just free(3) it,
312  * and if it is on stack, you can just let it go out of scope).
313  */
314 static inline void hashmap_entry_init(struct hashmap_entry *e,
315                                       unsigned int hash)
316 {
317         e->hash = hash;
318         e->next = NULL;
319 }
320
321 /*
322  * Return the number of items in the map.
323  */
324 static inline unsigned int hashmap_get_size(struct hashmap *map)
325 {
326         if (map->do_count_items)
327                 return map->private_size;
328
329         BUG("hashmap_get_size: size not set");
330         return 0;
331 }
332
333 /*
334  * Returns the hashmap entry for the specified key, or NULL if not found.
335  *
336  * `map` is the hashmap structure.
337  *
338  * `key` is a user data structure that starts with hashmap_entry that has at
339  * least been initialized with the proper hash code (via `hashmap_entry_init`).
340  *
341  * `keydata` is a data structure that holds just enough information to check
342  * for equality to a given entry.
343  *
344  * If the key data is variable-sized (e.g. a FLEX_ARRAY string) or quite large,
345  * it is undesirable to create a full-fledged entry structure on the heap and
346  * copy all the key data into the structure.
347  *
348  * In this case, the `keydata` parameter can be used to pass
349  * variable-sized key data directly to the comparison function, and the `key`
350  * parameter can be a stripped-down, fixed size entry structure allocated on the
351  * stack.
352  *
353  * If an entry with matching hash code is found, `key` and `keydata` are passed
354  * to `hashmap_cmp_fn` to decide whether the entry matches the key.
355  */
356 struct hashmap_entry *hashmap_get(const struct hashmap *map,
357                                   const struct hashmap_entry *key,
358                                   const void *keydata);
359
360 /*
361  * Returns the hashmap entry for the specified hash code and key data,
362  * or NULL if not found.
363  *
364  * `map` is the hashmap structure.
365  * `hash` is the hash code of the entry to look up.
366  *
367  * If an entry with matching hash code is found, `keydata` is passed to
368  * `hashmap_cmp_fn` to decide whether the entry matches the key. The
369  * `entry_or_key` parameter of `hashmap_cmp_fn` points to a hashmap_entry
370  * structure that should not be used in the comparison.
371  */
372 static inline struct hashmap_entry *hashmap_get_from_hash(
373                                         const struct hashmap *map,
374                                         unsigned int hash,
375                                         const void *keydata)
376 {
377         struct hashmap_entry key;
378         hashmap_entry_init(&key, hash);
379         return hashmap_get(map, &key, keydata);
380 }
381
382 /*
383  * Returns the next equal hashmap entry, or NULL if not found. This can be
384  * used to iterate over duplicate entries (see `hashmap_add`).
385  *
386  * `map` is the hashmap structure.
387  * `entry` is the hashmap_entry to start the search from, obtained via a previous
388  * call to `hashmap_get` or `hashmap_get_next`.
389  */
390 struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
391                                        const struct hashmap_entry *entry);
392
393 /*
394  * Adds a hashmap entry. This allows to add duplicate entries (i.e.
395  * separate values with the same key according to hashmap_cmp_fn).
396  *
397  * `map` is the hashmap structure.
398  * `entry` is the entry to add.
399  */
400 void hashmap_add(struct hashmap *map, struct hashmap_entry *entry);
401
402 /*
403  * Adds or replaces a hashmap entry. If the hashmap contains duplicate
404  * entries equal to the specified entry, only one of them will be replaced.
405  *
406  * `map` is the hashmap structure.
407  * `entry` is the entry to add or replace.
408  * Returns the replaced entry, or NULL if not found (i.e. the entry was added).
409  */
410 struct hashmap_entry *hashmap_put(struct hashmap *map,
411                                   struct hashmap_entry *entry);
412
413 /*
414  * Adds or replaces a hashmap entry contained within @keyvar,
415  * where @keyvar is a pointer to a struct containing a
416  * "struct hashmap_entry" @member.
417  *
418  * Returns the replaced pointer which is of the same type as @keyvar,
419  * or NULL if not found.
420  */
421 #define hashmap_put_entry(map, keyvar, member) \
422         container_of_or_null_offset(hashmap_put(map, &(keyvar)->member), \
423                                 OFFSETOF_VAR(keyvar, member))
424
425 /*
426  * Removes a hashmap entry matching the specified key. If the hashmap contains
427  * duplicate entries equal to the specified key, only one of them will be
428  * removed. Returns the removed entry, or NULL if not found.
429  *
430  * Argument explanation is the same as in `hashmap_get`.
431  */
432 struct hashmap_entry *hashmap_remove(struct hashmap *map,
433                                      const struct hashmap_entry *key,
434                                      const void *keydata);
435
436 /*
437  * Removes a hashmap entry contained within @keyvar,
438  * where @keyvar is a pointer to a struct containing a
439  * "struct hashmap_entry" @member.
440  *
441  * See `hashmap_get` for an explanation of @keydata
442  *
443  * Returns the replaced pointer which is of the same type as @keyvar,
444  * or NULL if not found.
445  */
446 #define hashmap_remove_entry(map, keyvar, member, keydata) \
447         container_of_or_null_offset( \
448                         hashmap_remove(map, &(keyvar)->member, keydata), \
449                         OFFSETOF_VAR(keyvar, member))
450
451 /*
452  * Returns the `bucket` an entry is stored in.
453  * Useful for multithreaded read access.
454  */
455 int hashmap_bucket(const struct hashmap *map, unsigned int hash);
456
457 /*
458  * Used to iterate over all entries of a hashmap. Note that it is
459  * not safe to add or remove entries to the hashmap while
460  * iterating.
461  */
462 struct hashmap_iter {
463         struct hashmap *map;
464         struct hashmap_entry *next;
465         unsigned int tablepos;
466 };
467
468 /* Initializes a `hashmap_iter` structure. */
469 void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);
470
471 /* Returns the next hashmap_entry, or NULL if there are no more entries. */
472 struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter);
473
474 /* Initializes the iterator and returns the first entry, if any. */
475 static inline struct hashmap_entry *hashmap_iter_first(struct hashmap *map,
476                                                        struct hashmap_iter *iter)
477 {
478         hashmap_iter_init(map, iter);
479         return hashmap_iter_next(iter);
480 }
481
482 /*
483  * returns the first entry in @map using @iter, where the entry is of
484  * @type (e.g. "struct foo") and @member is the name of the
485  * "struct hashmap_entry" in @type
486  */
487 #define hashmap_iter_first_entry(map, iter, type, member) \
488         container_of_or_null(hashmap_iter_first(map, iter), type, member)
489
490 /* internal macro for hashmap_for_each_entry */
491 #define hashmap_iter_next_entry_offset(iter, offset) \
492         container_of_or_null_offset(hashmap_iter_next(iter), offset)
493
494 /* internal macro for hashmap_for_each_entry */
495 #define hashmap_iter_first_entry_offset(map, iter, offset) \
496         container_of_or_null_offset(hashmap_iter_first(map, iter), offset)
497
498 /*
499  * iterate through @map using @iter, @var is a pointer to a type
500  * containing a @member which is a "struct hashmap_entry"
501  */
502 #define hashmap_for_each_entry(map, iter, var, member) \
503         for (var = NULL, /* for systems without typeof */ \
504              var = hashmap_iter_first_entry_offset(map, iter, \
505                                                 OFFSETOF_VAR(var, member)); \
506                 var; \
507                 var = hashmap_iter_next_entry_offset(iter, \
508                                                 OFFSETOF_VAR(var, member)))
509
510 /*
511  * returns a pointer of type matching @keyvar, or NULL if nothing found.
512  * @keyvar is a pointer to a struct containing a
513  * "struct hashmap_entry" @member.
514  */
515 #define hashmap_get_entry(map, keyvar, member, keydata) \
516         container_of_or_null_offset( \
517                                 hashmap_get(map, &(keyvar)->member, keydata), \
518                                 OFFSETOF_VAR(keyvar, member))
519
520 #define hashmap_get_entry_from_hash(map, hash, keydata, type, member) \
521         container_of_or_null(hashmap_get_from_hash(map, hash, keydata), \
522                                 type, member)
523 /*
524  * returns the next equal pointer to @var, or NULL if not found.
525  * @var is a pointer of any type containing "struct hashmap_entry"
526  * @member is the name of the "struct hashmap_entry" field
527  */
528 #define hashmap_get_next_entry(map, var, member) \
529         container_of_or_null_offset(hashmap_get_next(map, &(var)->member), \
530                                 OFFSETOF_VAR(var, member))
531
532 /*
533  * iterate @map starting from @var, where @var is a pointer of @type
534  * and @member is the name of the "struct hashmap_entry" field in @type
535  */
536 #define hashmap_for_each_entry_from(map, var, member) \
537         for (; \
538                 var; \
539                 var = hashmap_get_next_entry(map, var, member))
540
541 /*
542  * Disable item counting and automatic rehashing when adding/removing items.
543  *
544  * Normally, the hashmap keeps track of the number of items in the map
545  * and uses it to dynamically resize it.  This (both the counting and
546  * the resizing) can cause problems when the map is being used by
547  * threaded callers (because the hashmap code does not know about the
548  * locking strategy used by the threaded callers and therefore, does
549  * not know how to protect the "private_size" counter).
550  */
551 static inline void hashmap_disable_item_counting(struct hashmap *map)
552 {
553         map->do_count_items = 0;
554 }
555
556 /*
557  * Re-enable item counting when adding/removing items.
558  * If counting is currently disabled, it will force count them.
559  * It WILL NOT automatically rehash them.
560  */
561 static inline void hashmap_enable_item_counting(struct hashmap *map)
562 {
563         unsigned int n = 0;
564         struct hashmap_iter iter;
565
566         if (map->do_count_items)
567                 return;
568
569         hashmap_iter_init(map, &iter);
570         while (hashmap_iter_next(&iter))
571                 n++;
572
573         map->do_count_items = 1;
574         map->private_size = n;
575 }
576
577 /* String interning */
578
579 /*
580  * Returns the unique, interned version of the specified string or data,
581  * similar to the `String.intern` API in Java and .NET, respectively.
582  * Interned strings remain valid for the entire lifetime of the process.
583  *
584  * Can be used as `[x]strdup()` or `xmemdupz` replacement, except that interned
585  * strings / data must not be modified or freed.
586  *
587  * Interned strings are best used for short strings with high probability of
588  * duplicates.
589  *
590  * Uses a hashmap to store the pool of interned strings.
591  */
592 const void *memintern(const void *data, size_t len);
593 static inline const char *strintern(const char *string)
594 {
595         return memintern(string, strlen(string));
596 }
597
598 #endif