1 /*-*- Mode: C; c-basic-offset: 8 -*-*/
18 struct hashmap_entry {
21 struct hashmap_entry *bucket_next, *bucket_previous;
22 struct hashmap_entry *iterate_next, *iterate_previous;
26 hash_func_t hash_func;
27 compare_func_t compare_func;
29 struct hashmap_entry *iterate_list_head, *iterate_list_tail;
33 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
35 unsigned string_hash_func(const void *p) {
40 hash = 31 * hash + (unsigned) *c;
45 int string_compare_func(const void *a, const void *b) {
49 unsigned trivial_hash_func(const void *p) {
50 return PTR_TO_UINT(p);
53 int trivial_compare_func(const void *a, const void *b) {
54 return a < b ? -1 : (a > b ? 1 : 0);
57 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
60 if (!(h = malloc0(ALIGN(sizeof(Hashmap)) + NBUCKETS * ALIGN(sizeof(struct hashmap_entry*)))))
63 h->hash_func = hash_func ? hash_func : trivial_hash_func;
64 h->compare_func = compare_func ? compare_func : trivial_compare_func;
67 h->iterate_list_head = h->iterate_list_tail = NULL;
72 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
76 /* Remove from iteration list */
78 e->iterate_next->iterate_previous = e->iterate_previous;
80 h->iterate_list_tail = e->iterate_previous;
82 if (e->iterate_previous)
83 e->iterate_previous->iterate_next = e->iterate_next;
85 h->iterate_list_head = e->iterate_next;
87 /* Remove from hash table bucket list */
89 e->bucket_next->bucket_previous = e->bucket_previous;
91 if (e->bucket_previous)
92 e->bucket_previous->bucket_next = e->bucket_next;
94 unsigned hash = h->hash_func(e->key) % NBUCKETS;
95 BY_HASH(h)[hash] = e->bucket_next;
100 assert(h->n_entries >= 1);
104 void hashmap_free(Hashmap*h) {
114 void hashmap_clear(Hashmap *h) {
118 while (h->iterate_list_head)
119 remove_entry(h, h->iterate_list_head);
122 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
123 struct hashmap_entry *e;
125 assert(hash < NBUCKETS);
127 for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
128 if (h->compare_func(e->key, key) == 0)
134 int hashmap_put(Hashmap *h, const void *key, void *value) {
135 struct hashmap_entry *e;
140 hash = h->hash_func(key) % NBUCKETS;
142 if ((e = hash_scan(h, hash, key))) {
144 if (e->value == value)
150 if (!(e = new(struct hashmap_entry, 1)))
156 /* Insert into hash table */
157 e->bucket_next = BY_HASH(h)[hash];
158 e->bucket_previous = NULL;
159 if (BY_HASH(h)[hash])
160 BY_HASH(h)[hash]->bucket_previous = e;
161 BY_HASH(h)[hash] = e;
163 /* Insert into iteration list */
164 e->iterate_previous = h->iterate_list_tail;
165 e->iterate_next = NULL;
166 if (h->iterate_list_tail) {
167 assert(h->iterate_list_head);
168 h->iterate_list_tail->iterate_next = e;
170 assert(!h->iterate_list_head);
171 h->iterate_list_head = e;
173 h->iterate_list_tail = e;
176 assert(h->n_entries >= 1);
181 int hashmap_replace(Hashmap *h, const void *key, void *value) {
182 struct hashmap_entry *e;
187 hash = h->hash_func(key) % NBUCKETS;
189 if ((e = hash_scan(h, hash, key))) {
194 return hashmap_put(h, key, value);
197 void* hashmap_get(Hashmap *h, const void *key) {
199 struct hashmap_entry *e;
204 hash = h->hash_func(key) % NBUCKETS;
206 if (!(e = hash_scan(h, hash, key)))
212 void* hashmap_remove(Hashmap *h, const void *key) {
213 struct hashmap_entry *e;
220 hash = h->hash_func(key) % NBUCKETS;
222 if (!(e = hash_scan(h, hash, key)))
231 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
232 struct hashmap_entry *e;
238 hash = h->hash_func(key) % NBUCKETS;
240 if (!(e = hash_scan(h, hash, key)))
243 if (e->value != value)
251 void *hashmap_iterate(Hashmap *h, void **state, const void **key) {
252 struct hashmap_entry *e;
259 if (*state == (void*) -1)
262 if (!*state && !h->iterate_list_head)
265 e = *state ? *state : h->iterate_list_head;
268 *state = e->iterate_next;
278 *state = (void *) -1;
286 void *hashmap_iterate_backwards(Hashmap *h, void **state, const void **key) {
287 struct hashmap_entry *e;
294 if (*state == (void*) -1)
297 if (!*state && !h->iterate_list_tail)
300 e = *state ? *state : h->iterate_list_tail;
302 if (e->iterate_previous)
303 *state = e->iterate_previous;
313 *state = (void *) -1;
321 void* hashmap_first(Hashmap *h) {
326 if (!h->iterate_list_head)
329 return h->iterate_list_head->value;
332 void* hashmap_last(Hashmap *h) {
337 if (!h->iterate_list_tail)
340 return h->iterate_list_tail->value;
343 void* hashmap_steal_first(Hashmap *h) {
349 if (!h->iterate_list_head)
352 data = h->iterate_list_head->value;
353 remove_entry(h, h->iterate_list_head);
358 unsigned hashmap_size(Hashmap *h) {
366 bool hashmap_isempty(Hashmap *h) {
371 return h->n_entries == 0;
374 int hashmap_merge(Hashmap *h, Hashmap *other) {
375 struct hashmap_entry *e;
382 for (e = other->iterate_list_head; e; e = e->iterate_next) {
385 if ((r = hashmap_put(h, e->key, e->value)) < 0)
393 Hashmap *hashmap_copy(Hashmap *h) {
398 if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
401 if (hashmap_merge(copy, h) < 0) {