4 The hashmap API is a generic implementation of hash-based key-value mappings.
11 The hash table structure. Members can be used as follows, but should
12 not be modified directly:
14 The `size` member keeps track of the total number of entries (0 means the
17 `tablesize` is the allocated size of the hash table. A non-0 value indicates
18 that the hashmap is initialized. It may also be useful for statistical purposes
19 (i.e. `size / tablesize` is the current load factor).
21 `cmpfn` stores the comparison function specified in `hashmap_init()`. In
22 advanced scenarios, it may be useful to change this, e.g. to switch between
23 case-sensitive and case-insensitive lookup.
25 `struct hashmap_entry`::
27 An opaque structure representing an entry in the hash table, which must
28 be used as first member of user data structures. Ideally it should be
29 followed by an int-sized member to prevent unused memory on 64-bit
30 systems due to alignment.
32 The `hash` member is the entry's hash code and the `next` member points to the
33 next entry in case of collisions (i.e. if multiple entries map to the same
36 `struct hashmap_iter`::
38 An iterator structure, to be used with hashmap_iter_* functions.
43 `int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`::
45 User-supplied function to test two hashmap entries for equality. Shall
46 return 0 if the entries are equal.
48 This function is always called with non-NULL `entry` / `entry_or_key`
49 parameters that have the same hash code. When looking up an entry, the `key`
50 and `keydata` parameters to hashmap_get and hashmap_remove are always passed
51 as second and third argument, respectively. Otherwise, `keydata` is NULL.
56 `unsigned int strhash(const char *buf)`::
57 `unsigned int strihash(const char *buf)`::
58 `unsigned int memhash(const void *buf, size_t len)`::
59 `unsigned int memihash(const void *buf, size_t len)`::
61 Ready-to-use hash functions for strings, using the FNV-1 algorithm (see
62 http://www.isthe.com/chongo/tech/comp/fnv).
64 `strhash` and `strihash` take 0-terminated strings, while `memhash` and
65 `memihash` operate on arbitrary-length memory.
67 `strihash` and `memihash` are case insensitive versions.
69 `unsigned int sha1hash(const unsigned char *sha1)`::
71 Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code
72 for use in hash tables. Cryptographic hashes are supposed to have
73 uniform distribution, so in contrast to `memhash()`, this just copies
74 the first `sizeof(int)` bytes without shuffling any bits. Note that
75 the results will be different on big-endian and little-endian
76 platforms, so they should not be stored or transferred over the net.
78 `void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)`::
80 Initializes a hashmap structure.
82 `map` is the hashmap to initialize.
84 The `equals_function` can be specified to compare two entries for equality.
85 If NULL, entries are considered equal if their hash codes are equal.
87 If the total number of entries is known in advance, the `initial_size`
88 parameter may be used to preallocate a sufficiently large table and thus
89 prevent expensive resizing. If 0, the table is dynamically resized.
91 `void hashmap_free(struct hashmap *map, int free_entries)`::
93 Frees a hashmap structure and allocated memory.
95 `map` is the hashmap to free.
97 If `free_entries` is true, each hashmap_entry in the map is freed as well
98 (using stdlib's free()).
100 `void hashmap_entry_init(void *entry, unsigned int hash)`::
102 Initializes a hashmap_entry structure.
104 `entry` points to the entry to initialize.
106 `hash` is the hash code of the entry.
108 `void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`::
110 Returns the hashmap entry for the specified key, or NULL if not found.
112 `map` is the hashmap structure.
114 `key` is a hashmap_entry structure (or user data structure that starts with
115 hashmap_entry) that has at least been initialized with the proper hash code
116 (via `hashmap_entry_init`).
118 If an entry with matching hash code is found, `key` and `keydata` are passed
119 to `hashmap_cmp_fn` to decide whether the entry matches the key.
121 `void *hashmap_get_from_hash(const struct hashmap *map, unsigned int hash, const void *keydata)`::
123 Returns the hashmap entry for the specified hash code and key data,
124 or NULL if not found.
126 `map` is the hashmap structure.
128 `hash` is the hash code of the entry to look up.
130 If an entry with matching hash code is found, `keydata` is passed to
131 `hashmap_cmp_fn` to decide whether the entry matches the key. The
132 `entry_or_key` parameter points to a bogus hashmap_entry structure that
133 should not be used in the comparison.
135 `void *hashmap_get_next(const struct hashmap *map, const void *entry)`::
137 Returns the next equal hashmap entry, or NULL if not found. This can be
138 used to iterate over duplicate entries (see `hashmap_add`).
140 `map` is the hashmap structure.
142 `entry` is the hashmap_entry to start the search from, obtained via a previous
143 call to `hashmap_get` or `hashmap_get_next`.
145 `void hashmap_add(struct hashmap *map, void *entry)`::
147 Adds a hashmap entry. This allows to add duplicate entries (i.e.
148 separate values with the same key according to hashmap_cmp_fn).
150 `map` is the hashmap structure.
152 `entry` is the entry to add.
154 `void *hashmap_put(struct hashmap *map, void *entry)`::
156 Adds or replaces a hashmap entry. If the hashmap contains duplicate
157 entries equal to the specified entry, only one of them will be replaced.
159 `map` is the hashmap structure.
161 `entry` is the entry to add or replace.
163 Returns the replaced entry, or NULL if not found (i.e. the entry was added).
165 `void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`::
167 Removes a hashmap entry matching the specified key. If the hashmap
168 contains duplicate entries equal to the specified key, only one of
169 them will be removed.
171 `map` is the hashmap structure.
173 `key` is a hashmap_entry structure (or user data structure that starts with
174 hashmap_entry) that has at least been initialized with the proper hash code
175 (via `hashmap_entry_init`).
177 If an entry with matching hash code is found, `key` and `keydata` are
178 passed to `hashmap_cmp_fn` to decide whether the entry matches the key.
180 Returns the removed entry, or NULL if not found.
182 `void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`::
183 `void *hashmap_iter_next(struct hashmap_iter *iter)`::
184 `void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`::
186 Used to iterate over all entries of a hashmap.
188 `hashmap_iter_init` initializes a `hashmap_iter` structure.
190 `hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no
193 `hashmap_iter_first` is a combination of both (i.e. initializes the iterator
194 and returns the first entry, if any).
199 Here's a simple usage example that maps long keys to double values.
204 struct hashmap_entry ent; /* must be the first member! */
209 static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused)
211 return !(e1->key == e2->key);
214 void long2double_init(void)
216 hashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0);
219 void long2double_free(void)
221 hashmap_free(&map, 1);
224 static struct long2double *find_entry(long key)
226 struct long2double k;
227 hashmap_entry_init(&k, memhash(&key, sizeof(long)));
229 return hashmap_get(&map, &k, NULL);
232 double get_value(long key)
234 struct long2double *e = find_entry(key);
235 return e ? e->value : 0;
238 void set_value(long key, double value)
240 struct long2double *e = find_entry(key);
242 e = malloc(sizeof(struct long2double));
243 hashmap_entry_init(e, memhash(&key, sizeof(long)));
245 hashmap_add(&map, e);
251 Using variable-sized keys
252 -------------------------
254 The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary
255 `hashmap_entry` structure as key to find the correct entry. If the key data is
256 variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable
257 to create a full-fledged entry structure on the heap and copy all the key data
260 In this case, the `keydata` parameter can be used to pass
261 variable-sized key data directly to the comparison function, and the `key`
262 parameter can be a stripped-down, fixed size entry structure allocated on the
265 See test-hashmap.c for an example using arbitrary-length strings as keys.