freshlybakedca.ke
Git fork
1#ifndef HASHMAP_H
2#define HASHMAP_H
3
4/*
5 * Generic implementation of hash-based key-value mappings.
6 *
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 * -------------------------------------
11 *
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 * };
18 *
19 * #define COMPARE_VALUE 1
20 *
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;
29 *
30 * e1 = container_of(eptr, const struct long2string, ent);
31 * e2 = container_of(entry_or_key, const struct long2string, ent);
32 *
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 * }
39 *
40 * int main(int argc, char **argv)
41 * {
42 * long key;
43 * char value[255], action[32];
44 * unsigned flags = 0;
45 *
46 * hashmap_init(&map, long2string_cmp, &flags, 0);
47 *
48 * while (scanf("%s %ld %s", action, &key, value)) {
49 *
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 * }
57 *
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;
62 *
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 * }
73 *
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;
79 *
80 * flags |= COMPARE_VALUE;
81 * printf("%sfound\n",
82 * hashmap_get(&map, &e->ent, NULL) ? "" : "not ");
83 * free(e);
84 * }
85 *
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;
90 *
91 * flags |= COMPARE_VALUE;
92 * printf("%sfound\n",
93 * hashmap_get(&map, &k.ent, value) ? "" : "not ");
94 * }
95 *
96 * if (!strcmp("end", action)) {
97 * hashmap_clear_and_free(&map, struct long2string, ent);
98 * break;
99 * }
100 * }
101 *
102 * return 0;
103 * }
104 */
105
106/*
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.
114 */
115unsigned int strhash(const char *buf);
116unsigned int strihash(const char *buf);
117unsigned int memhash(const void *buf, size_t len);
118unsigned int memihash(const void *buf, size_t len);
119unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len);
120
121/*
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.
126 */
127struct hashmap_entry {
128 /*
129 * next points to the next entry in case of collisions (i.e. if
130 * multiple entries map to the same bucket)
131 */
132 struct hashmap_entry *next;
133
134 /* entry's hash code */
135 unsigned int hash;
136};
137
138/*
139 * User-supplied function to test two hashmap entries for equality. Shall
140 * return 0 if the entries are equal.
141 *
142 * This function is always called with non-NULL `entry` and `entry_or_key`
143 * parameters that have the same hash code.
144 *
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.
148 *
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.
154 *
155 * The `hashmap_cmp_fn_data` entry is the pointer given in the init function.
156 */
157typedef 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);
161
162/*
163 * struct hashmap is the hash table structure. Members can be used as follows,
164 * but should not be modified directly.
165 */
166struct hashmap {
167 struct hashmap_entry **table;
168
169 /* Stores the comparison function specified in `hashmap_init()`. */
170 hashmap_cmp_fn cmpfn;
171 const void *cmpfn_data;
172
173 /* total number of entries (0 means the hashmap is empty) */
174 unsigned int private_size; /* use hashmap_get_size() */
175
176 /*
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).
181 */
182 unsigned int tablesize;
183
184 unsigned int grow_at;
185 unsigned int shrink_at;
186
187 unsigned int do_count_items : 1;
188};
189
190/* hashmap functions */
191
192#define HASHMAP_INIT(fn, data) { .cmpfn = fn, .cmpfn_data = data, \
193 .do_count_items = 1 }
194
195/*
196 * Initializes a hashmap structure.
197 *
198 * `map` is the hashmap to initialize.
199 *
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.
202 *
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.
207 *
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.
211 */
212void hashmap_init(struct hashmap *map,
213 hashmap_cmp_fn equals_function,
214 const void *equals_function_data,
215 size_t initial_size);
216
217/* internal functions for clearing or freeing hashmap */
218void hashmap_partial_clear_(struct hashmap *map, ssize_t offset);
219void hashmap_clear_(struct hashmap *map, ssize_t offset);
220
221/*
222 * Frees a hashmap structure and allocated memory for the table, but does not
223 * free the entries nor anything they point to.
224 *
225 * Usage note:
226 *
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:
230 *
231 * hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) {
232 * free(e->somefield);
233 * free(e);
234 * }
235 * hashmap_clear(map);
236 *
237 * instead of
238 *
239 * hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) {
240 * free(e->somefield);
241 * }
242 * hashmap_clear_and_free(map, struct my_entry_struct, hashmap_entry_name);
243 *
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().
248 */
249#define hashmap_clear(map) hashmap_clear_(map, -1)
250
251/*
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.
257 */
258#define hashmap_partial_clear(map) hashmap_partial_clear_(map, -1)
259
260/*
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.
264 *
265 * See usage note above hashmap_clear().
266 */
267#define hashmap_clear_and_free(map, type, member) \
268 hashmap_clear_(map, offsetof(type, member))
269
270/*
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.
274 *
275 * See usage note above hashmap_clear().
276 */
277#define hashmap_partial_clear_and_free(map, type, member) \
278 hashmap_partial_clear_(map, offsetof(type, member))
279
280/* hashmap_entry functions */
281
282/*
283 * Initializes a hashmap_entry structure.
284 *
285 * `entry` points to the entry to initialize.
286 * `hash` is the hash code of the entry.
287 *
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).
292 */
293static inline void hashmap_entry_init(struct hashmap_entry *e,
294 unsigned int hash)
295{
296 e->hash = hash;
297 e->next = NULL;
298}
299
300/*
301 * Return the number of items in the map.
302 */
303static inline unsigned int hashmap_get_size(struct hashmap *map)
304{
305 if (map->do_count_items)
306 return map->private_size;
307
308 BUG("hashmap_get_size: size not set");
309 return 0;
310}
311
312/*
313 * Returns the hashmap entry for the specified key, or NULL if not found.
314 *
315 * `map` is the hashmap structure.
316 *
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`).
319 *
320 * `keydata` is a data structure that holds just enough information to check
321 * for equality to a given entry.
322 *
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.
326 *
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.
331 *
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.
334 */
335struct hashmap_entry *hashmap_get(const struct hashmap *map,
336 const struct hashmap_entry *key,
337 const void *keydata);
338
339/*
340 * Returns the hashmap entry for the specified hash code and key data,
341 * or NULL if not found.
342 *
343 * `map` is the hashmap structure.
344 * `hash` is the hash code of the entry to look up.
345 *
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.
350 */
351static inline struct hashmap_entry *hashmap_get_from_hash(
352 const struct hashmap *map,
353 unsigned int hash,
354 const void *keydata)
355{
356 struct hashmap_entry key;
357 hashmap_entry_init(&key, hash);
358 return hashmap_get(map, &key, keydata);
359}
360
361/*
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`).
364 *
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`.
368 */
369struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
370 const struct hashmap_entry *entry);
371
372/*
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).
375 *
376 * `map` is the hashmap structure.
377 * `entry` is the entry to add.
378 */
379void hashmap_add(struct hashmap *map, struct hashmap_entry *entry);
380
381/*
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.
384 *
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).
388 */
389struct hashmap_entry *hashmap_put(struct hashmap *map,
390 struct hashmap_entry *entry);
391
392/*
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.
396 *
397 * Returns the replaced pointer which is of the same type as @keyvar,
398 * or NULL if not found.
399 */
400#define hashmap_put_entry(map, keyvar, member) \
401 container_of_or_null_offset(hashmap_put(map, &(keyvar)->member), \
402 OFFSETOF_VAR(keyvar, member))
403
404/*
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.
408 *
409 * Argument explanation is the same as in `hashmap_get`.
410 */
411struct hashmap_entry *hashmap_remove(struct hashmap *map,
412 const struct hashmap_entry *key,
413 const void *keydata);
414
415/*
416 * Removes a hashmap entry contained within @keyvar,
417 * where @keyvar is a pointer to a struct containing a
418 * "struct hashmap_entry" @member.
419 *
420 * See `hashmap_get` for an explanation of @keydata
421 *
422 * Returns the replaced pointer which is of the same type as @keyvar,
423 * or NULL if not found.
424 */
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))
429
430/*
431 * Returns the `bucket` an entry is stored in.
432 * Useful for multithreaded read access.
433 */
434int hashmap_bucket(const struct hashmap *map, unsigned int hash);
435
436/*
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.
440 */
441struct hashmap_iter {
442 struct hashmap *map;
443 struct hashmap_entry *next;
444 unsigned int tablepos;
445};
446
447/* Initializes a `hashmap_iter` structure. */
448void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);
449
450/* Returns the next hashmap_entry, or NULL if there are no more entries. */
451struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter);
452
453/* Initializes the iterator and returns the first entry, if any. */
454static inline struct hashmap_entry *hashmap_iter_first(struct hashmap *map,
455 struct hashmap_iter *iter)
456{
457 hashmap_iter_init(map, iter);
458 return hashmap_iter_next(iter);
459}
460
461/*
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
465 */
466#define hashmap_iter_first_entry(map, iter, type, member) \
467 container_of_or_null(hashmap_iter_first(map, iter), type, member)
468
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)
472
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)
476
477/*
478 * iterate through @map using @iter, @var is a pointer to a type
479 * containing a @member which is a "struct hashmap_entry"
480 */
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)))
488
489/*
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.
493 */
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))
498
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)
502/*
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
506 */
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))
510
511/*
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
514 */
515#define hashmap_for_each_entry_from(map, var, member) \
516 for (; \
517 var; \
518 var = hashmap_get_next_entry(map, var, member))
519
520/*
521 * Disable item counting and automatic rehashing when adding/removing items.
522 *
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).
529 */
530static inline void hashmap_disable_item_counting(struct hashmap *map)
531{
532 map->do_count_items = 0;
533}
534
535/*
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.
539 */
540static inline void hashmap_enable_item_counting(struct hashmap *map)
541{
542 unsigned int n = 0;
543 struct hashmap_iter iter;
544
545 if (map->do_count_items)
546 return;
547
548 hashmap_iter_init(map, &iter);
549 while (hashmap_iter_next(&iter))
550 n++;
551
552 map->do_count_items = 1;
553 map->private_size = n;
554}
555
556/* String interning */
557
558/*
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.
562 *
563 * Can be used as `[x]strdup()` or `xmemdupz` replacement, except that interned
564 * strings / data must not be modified or freed.
565 *
566 * Interned strings are best used for short strings with high probability of
567 * duplicates.
568 *
569 * Uses a hashmap to store the pool of interned strings.
570 */
571const void *memintern(const void *data, size_t len);
572static inline const char *strintern(const char *string)
573{
574 return memintern(string, strlen(string));
575}
576
577#endif