date: make DATE_MODE thread-safe
[git.git] / hashmap.h
blobc8216e47bb21171a59cdcc1f17b600ae60699dfa
1 #ifndef HASHMAP_H
2 #define HASHMAP_H
4 /*
5 * Generic implementation of hash-based key-value mappings.
7 * An example that maps long to a string:
8 * For the sake of the example this allows to lookup exact values, too
9 * (i.e. it is operated as a set, the value is part of the key)
10 * -------------------------------------
12 * struct hashmap map;
13 * struct long2string {
14 * struct hashmap_entry ent;
15 * long key;
16 * char value[FLEX_ARRAY]; // be careful with allocating on stack!
17 * };
19 * #define COMPARE_VALUE 1
21 * static int long2string_cmp(const void *hashmap_cmp_fn_data,
22 * const struct hashmap_entry *eptr,
23 * const struct hashmap_entry *entry_or_key,
24 * const void *keydata)
25 * {
26 * const char *string = keydata;
27 * unsigned flags = *(unsigned *)hashmap_cmp_fn_data;
28 * const struct long2string *e1, *e2;
30 * e1 = container_of(eptr, const struct long2string, ent);
31 * e2 = container_of(entry_or_key, const struct long2string, ent);
33 * if (flags & COMPARE_VALUE)
34 * return e1->key != e2->key ||
35 * strcmp(e1->value, string ? string : e2->value);
36 * else
37 * return e1->key != e2->key;
38 * }
40 * int main(int argc, char **argv)
41 * {
42 * long key;
43 * char value[255], action[32];
44 * unsigned flags = 0;
46 * hashmap_init(&map, long2string_cmp, &flags, 0);
48 * while (scanf("%s %ld %s", action, &key, value)) {
50 * if (!strcmp("add", action)) {
51 * struct long2string *e;
52 * FLEX_ALLOC_STR(e, value, value);
53 * hashmap_entry_init(&e->ent, memhash(&key, sizeof(long)));
54 * e->key = key;
55 * hashmap_add(&map, &e->ent);
56 * }
58 * if (!strcmp("print_all_by_key", action)) {
59 * struct long2string k, *e;
60 * hashmap_entry_init(&k.ent, memhash(&key, sizeof(long)));
61 * k.key = key;
63 * flags &= ~COMPARE_VALUE;
64 * e = hashmap_get_entry(&map, &k, ent, NULL);
65 * if (e) {
66 * printf("first: %ld %s\n", e->key, e->value);
67 * while ((e = hashmap_get_next_entry(&map, e,
68 * struct long2string, ent))) {
69 * printf("found more: %ld %s\n", e->key, e->value);
70 * }
71 * }
72 * }
74 * if (!strcmp("has_exact_match", action)) {
75 * struct long2string *e;
76 * FLEX_ALLOC_STR(e, value, value);
77 * hashmap_entry_init(&e->ent, memhash(&key, sizeof(long)));
78 * e->key = key;
80 * flags |= COMPARE_VALUE;
81 * printf("%sfound\n",
82 * hashmap_get(&map, &e->ent, NULL) ? "" : "not ");
83 * free(e);
84 * }
86 * if (!strcmp("has_exact_match_no_heap_alloc", action)) {
87 * struct long2string k;
88 * hashmap_entry_init(&k.ent, memhash(&key, sizeof(long)));
89 * k.key = key;
91 * flags |= COMPARE_VALUE;
92 * printf("%sfound\n",
93 * hashmap_get(&map, &k.ent, value) ? "" : "not ");
94 * }
96 * if (!strcmp("end", action)) {
97 * hashmap_clear_and_free(&map, struct long2string, ent);
98 * break;
99 * }
102 * return 0;
107 * Ready-to-use hash functions for strings, using the FNV-1 algorithm (see
108 * http://www.isthe.com/chongo/tech/comp/fnv).
109 * `strhash` and `strihash` take 0-terminated strings, while `memhash` and
110 * `memihash` operate on arbitrary-length memory.
111 * `strihash` and `memihash` are case insensitive versions.
112 * `memihash_cont` is a variant of `memihash` that allows a computation to be
113 * continued with another chunk of data.
115 unsigned int strhash(const char *buf);
116 unsigned int strihash(const char *buf);
117 unsigned int memhash(const void *buf, size_t len);
118 unsigned int memihash(const void *buf, size_t len);
119 unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len);
122 * struct hashmap_entry is an opaque structure representing an entry in the
123 * hash table.
124 * Ideally it should be followed by an int-sized member to prevent unused
125 * memory on 64-bit systems due to alignment.
127 struct hashmap_entry {
129 * next points to the next entry in case of collisions (i.e. if
130 * multiple entries map to the same bucket)
132 struct hashmap_entry *next;
134 /* entry's hash code */
135 unsigned int hash;
139 * User-supplied function to test two hashmap entries for equality. Shall
140 * return 0 if the entries are equal.
142 * This function is always called with non-NULL `entry` and `entry_or_key`
143 * parameters that have the same hash code.
145 * When looking up an entry, the `key` and `keydata` parameters to hashmap_get
146 * and hashmap_remove are always passed as second `entry_or_key` and third
147 * argument `keydata`, respectively. Otherwise, `keydata` is NULL.
149 * When it is too expensive to allocate a user entry (either because it is
150 * large or variable sized, such that it is not on the stack), then the
151 * relevant data to check for equality should be passed via `keydata`.
152 * In this case `key` can be a stripped down version of the user key data
153 * or even just a hashmap_entry having the correct hash.
155 * The `hashmap_cmp_fn_data` entry is the pointer given in the init function.
157 typedef int (*hashmap_cmp_fn)(const void *hashmap_cmp_fn_data,
158 const struct hashmap_entry *entry,
159 const struct hashmap_entry *entry_or_key,
160 const void *keydata);
163 * struct hashmap is the hash table structure. Members can be used as follows,
164 * but should not be modified directly.
166 struct hashmap {
167 struct hashmap_entry **table;
169 /* Stores the comparison function specified in `hashmap_init()`. */
170 hashmap_cmp_fn cmpfn;
171 const void *cmpfn_data;
173 /* total number of entries (0 means the hashmap is empty) */
174 unsigned int private_size; /* use hashmap_get_size() */
177 * tablesize is the allocated size of the hash table. A non-0 value
178 * indicates that the hashmap is initialized. It may also be useful
179 * for statistical purposes (i.e. `size / tablesize` is the current
180 * load factor).
182 unsigned int tablesize;
184 unsigned int grow_at;
185 unsigned int shrink_at;
187 unsigned int do_count_items : 1;
190 /* hashmap functions */
192 #define HASHMAP_INIT(fn, data) { .cmpfn = fn, .cmpfn_data = data, \
193 .do_count_items = 1 }
196 * Initializes a hashmap structure.
198 * `map` is the hashmap to initialize.
200 * The `equals_function` can be specified to compare two entries for equality.
201 * If NULL, entries are considered equal if their hash codes are equal.
203 * The `equals_function_data` parameter can be used to provide additional data
204 * (a callback cookie) that will be passed to `equals_function` each time it
205 * is called. This allows a single `equals_function` to implement multiple
206 * comparison functions.
208 * If the total number of entries is known in advance, the `initial_size`
209 * parameter may be used to preallocate a sufficiently large table and thus
210 * prevent expensive resizing. If 0, the table is dynamically resized.
212 void hashmap_init(struct hashmap *map,
213 hashmap_cmp_fn equals_function,
214 const void *equals_function_data,
215 size_t initial_size);
217 /* internal functions for clearing or freeing hashmap */
218 void hashmap_partial_clear_(struct hashmap *map, ssize_t offset);
219 void hashmap_clear_(struct hashmap *map, ssize_t offset);
222 * Frees a hashmap structure and allocated memory for the table, but does not
223 * free the entries nor anything they point to.
225 * Usage note:
227 * Many callers will need to iterate over all entries and free the data each
228 * entry points to; in such a case, they can free the entry itself while at it.
229 * Thus, you might see:
231 * hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) {
232 * free(e->somefield);
233 * free(e);
235 * hashmap_clear(map);
237 * instead of
239 * hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) {
240 * free(e->somefield);
242 * hashmap_clear_and_free(map, struct my_entry_struct, hashmap_entry_name);
244 * to avoid the implicit extra loop over the entries. However, if there are
245 * no special fields in your entry that need to be freed beyond the entry
246 * itself, it is probably simpler to avoid the explicit loop and just call
247 * hashmap_clear_and_free().
249 #define hashmap_clear(map) hashmap_clear_(map, -1)
252 * Similar to hashmap_clear(), except that the table is not deallocated; it
253 * is merely zeroed out but left the same size as before. If the hashmap
254 * will be reused, this avoids the overhead of deallocating and
255 * reallocating map->table. As with hashmap_clear(), you may need to free
256 * the entries yourself before calling this function.
258 #define hashmap_partial_clear(map) hashmap_partial_clear_(map, -1)
261 * Similar to hashmap_clear() but also frees all entries. @type is the
262 * struct type of the entry where @member is the hashmap_entry struct used
263 * to associate with @map.
265 * See usage note above hashmap_clear().
267 #define hashmap_clear_and_free(map, type, member) \
268 hashmap_clear_(map, offsetof(type, member))
271 * Similar to hashmap_partial_clear() but also frees all entries. @type is
272 * the struct type of the entry where @member is the hashmap_entry struct
273 * used to associate with @map.
275 * See usage note above hashmap_clear().
277 #define hashmap_partial_clear_and_free(map, type, member) \
278 hashmap_partial_clear_(map, offsetof(type, member))
280 /* hashmap_entry functions */
283 * Initializes a hashmap_entry structure.
285 * `entry` points to the entry to initialize.
286 * `hash` is the hash code of the entry.
288 * The hashmap_entry structure does not hold references to external resources,
289 * and it is safe to just discard it once you are done with it (i.e. if
290 * your structure was allocated with xmalloc(), you can just free(3) it,
291 * and if it is on stack, you can just let it go out of scope).
293 static inline void hashmap_entry_init(struct hashmap_entry *e,
294 unsigned int hash)
296 e->hash = hash;
297 e->next = NULL;
301 * Return the number of items in the map.
303 static inline unsigned int hashmap_get_size(struct hashmap *map)
305 if (map->do_count_items)
306 return map->private_size;
308 BUG("hashmap_get_size: size not set");
309 return 0;
313 * Returns the hashmap entry for the specified key, or NULL if not found.
315 * `map` is the hashmap structure.
317 * `key` is a user data structure that starts with hashmap_entry that has at
318 * least been initialized with the proper hash code (via `hashmap_entry_init`).
320 * `keydata` is a data structure that holds just enough information to check
321 * for equality to a given entry.
323 * If the key data is variable-sized (e.g. a FLEX_ARRAY string) or quite large,
324 * it is undesirable to create a full-fledged entry structure on the heap and
325 * copy all the key data into the structure.
327 * In this case, the `keydata` parameter can be used to pass
328 * variable-sized key data directly to the comparison function, and the `key`
329 * parameter can be a stripped-down, fixed size entry structure allocated on the
330 * stack.
332 * If an entry with matching hash code is found, `key` and `keydata` are passed
333 * to `hashmap_cmp_fn` to decide whether the entry matches the key.
335 struct hashmap_entry *hashmap_get(const struct hashmap *map,
336 const struct hashmap_entry *key,
337 const void *keydata);
340 * Returns the hashmap entry for the specified hash code and key data,
341 * or NULL if not found.
343 * `map` is the hashmap structure.
344 * `hash` is the hash code of the entry to look up.
346 * If an entry with matching hash code is found, `keydata` is passed to
347 * `hashmap_cmp_fn` to decide whether the entry matches the key. The
348 * `entry_or_key` parameter of `hashmap_cmp_fn` points to a hashmap_entry
349 * structure that should not be used in the comparison.
351 static inline struct hashmap_entry *hashmap_get_from_hash(
352 const struct hashmap *map,
353 unsigned int hash,
354 const void *keydata)
356 struct hashmap_entry key;
357 hashmap_entry_init(&key, hash);
358 return hashmap_get(map, &key, keydata);
362 * Returns the next equal hashmap entry, or NULL if not found. This can be
363 * used to iterate over duplicate entries (see `hashmap_add`).
365 * `map` is the hashmap structure.
366 * `entry` is the hashmap_entry to start the search from, obtained via a previous
367 * call to `hashmap_get` or `hashmap_get_next`.
369 struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
370 const struct hashmap_entry *entry);
373 * Adds a hashmap entry. This allows to add duplicate entries (i.e.
374 * separate values with the same key according to hashmap_cmp_fn).
376 * `map` is the hashmap structure.
377 * `entry` is the entry to add.
379 void hashmap_add(struct hashmap *map, struct hashmap_entry *entry);
382 * Adds or replaces a hashmap entry. If the hashmap contains duplicate
383 * entries equal to the specified entry, only one of them will be replaced.
385 * `map` is the hashmap structure.
386 * `entry` is the entry to add or replace.
387 * Returns the replaced entry, or NULL if not found (i.e. the entry was added).
389 struct hashmap_entry *hashmap_put(struct hashmap *map,
390 struct hashmap_entry *entry);
393 * Adds or replaces a hashmap entry contained within @keyvar,
394 * where @keyvar is a pointer to a struct containing a
395 * "struct hashmap_entry" @member.
397 * Returns the replaced pointer which is of the same type as @keyvar,
398 * or NULL if not found.
400 #define hashmap_put_entry(map, keyvar, member) \
401 container_of_or_null_offset(hashmap_put(map, &(keyvar)->member), \
402 OFFSETOF_VAR(keyvar, member))
405 * Removes a hashmap entry matching the specified key. If the hashmap contains
406 * duplicate entries equal to the specified key, only one of them will be
407 * removed. Returns the removed entry, or NULL if not found.
409 * Argument explanation is the same as in `hashmap_get`.
411 struct hashmap_entry *hashmap_remove(struct hashmap *map,
412 const struct hashmap_entry *key,
413 const void *keydata);
416 * Removes a hashmap entry contained within @keyvar,
417 * where @keyvar is a pointer to a struct containing a
418 * "struct hashmap_entry" @member.
420 * See `hashmap_get` for an explanation of @keydata
422 * Returns the replaced pointer which is of the same type as @keyvar,
423 * or NULL if not found.
425 #define hashmap_remove_entry(map, keyvar, member, keydata) \
426 container_of_or_null_offset( \
427 hashmap_remove(map, &(keyvar)->member, keydata), \
428 OFFSETOF_VAR(keyvar, member))
431 * Returns the `bucket` an entry is stored in.
432 * Useful for multithreaded read access.
434 int hashmap_bucket(const struct hashmap *map, unsigned int hash);
437 * Used to iterate over all entries of a hashmap. Note that it is
438 * not safe to add or remove entries to the hashmap while
439 * iterating.
441 struct hashmap_iter {
442 struct hashmap *map;
443 struct hashmap_entry *next;
444 unsigned int tablepos;
447 /* Initializes a `hashmap_iter` structure. */
448 void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);
450 /* Returns the next hashmap_entry, or NULL if there are no more entries. */
451 struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter);
453 /* Initializes the iterator and returns the first entry, if any. */
454 static inline struct hashmap_entry *hashmap_iter_first(struct hashmap *map,
455 struct hashmap_iter *iter)
457 hashmap_iter_init(map, iter);
458 return hashmap_iter_next(iter);
462 * returns the first entry in @map using @iter, where the entry is of
463 * @type (e.g. "struct foo") and @member is the name of the
464 * "struct hashmap_entry" in @type
466 #define hashmap_iter_first_entry(map, iter, type, member) \
467 container_of_or_null(hashmap_iter_first(map, iter), type, member)
469 /* internal macro for hashmap_for_each_entry */
470 #define hashmap_iter_next_entry_offset(iter, offset) \
471 container_of_or_null_offset(hashmap_iter_next(iter), offset)
473 /* internal macro for hashmap_for_each_entry */
474 #define hashmap_iter_first_entry_offset(map, iter, offset) \
475 container_of_or_null_offset(hashmap_iter_first(map, iter), offset)
478 * iterate through @map using @iter, @var is a pointer to a type
479 * containing a @member which is a "struct hashmap_entry"
481 #define hashmap_for_each_entry(map, iter, var, member) \
482 for (var = NULL, /* for systems without typeof */ \
483 var = hashmap_iter_first_entry_offset(map, iter, \
484 OFFSETOF_VAR(var, member)); \
485 var; \
486 var = hashmap_iter_next_entry_offset(iter, \
487 OFFSETOF_VAR(var, member)))
490 * returns a pointer of type matching @keyvar, or NULL if nothing found.
491 * @keyvar is a pointer to a struct containing a
492 * "struct hashmap_entry" @member.
494 #define hashmap_get_entry(map, keyvar, member, keydata) \
495 container_of_or_null_offset( \
496 hashmap_get(map, &(keyvar)->member, keydata), \
497 OFFSETOF_VAR(keyvar, member))
499 #define hashmap_get_entry_from_hash(map, hash, keydata, type, member) \
500 container_of_or_null(hashmap_get_from_hash(map, hash, keydata), \
501 type, member)
503 * returns the next equal pointer to @var, or NULL if not found.
504 * @var is a pointer of any type containing "struct hashmap_entry"
505 * @member is the name of the "struct hashmap_entry" field
507 #define hashmap_get_next_entry(map, var, member) \
508 container_of_or_null_offset(hashmap_get_next(map, &(var)->member), \
509 OFFSETOF_VAR(var, member))
512 * iterate @map starting from @var, where @var is a pointer of @type
513 * and @member is the name of the "struct hashmap_entry" field in @type
515 #define hashmap_for_each_entry_from(map, var, member) \
516 for (; \
517 var; \
518 var = hashmap_get_next_entry(map, var, member))
521 * Disable item counting and automatic rehashing when adding/removing items.
523 * Normally, the hashmap keeps track of the number of items in the map
524 * and uses it to dynamically resize it. This (both the counting and
525 * the resizing) can cause problems when the map is being used by
526 * threaded callers (because the hashmap code does not know about the
527 * locking strategy used by the threaded callers and therefore, does
528 * not know how to protect the "private_size" counter).
530 static inline void hashmap_disable_item_counting(struct hashmap *map)
532 map->do_count_items = 0;
536 * Re-enable item counting when adding/removing items.
537 * If counting is currently disabled, it will force count them.
538 * It WILL NOT automatically rehash them.
540 static inline void hashmap_enable_item_counting(struct hashmap *map)
542 unsigned int n = 0;
543 struct hashmap_iter iter;
545 if (map->do_count_items)
546 return;
548 hashmap_iter_init(map, &iter);
549 while (hashmap_iter_next(&iter))
550 n++;
552 map->do_count_items = 1;
553 map->private_size = n;
556 /* String interning */
559 * Returns the unique, interned version of the specified string or data,
560 * similar to the `String.intern` API in Java and .NET, respectively.
561 * Interned strings remain valid for the entire lifetime of the process.
563 * Can be used as `[x]strdup()` or `xmemdupz` replacement, except that interned
564 * strings / data must not be modified or freed.
566 * Interned strings are best used for short strings with high probability of
567 * duplicates.
569 * Uses a hashmap to store the pool of interned strings.
571 const void *memintern(const void *data, size_t len);
572 static inline const char *strintern(const char *string)
574 return memintern(string, strlen(string));
577 #endif