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 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
78 if (!(*h = hashmap_new(hash_func, compare_func)))
84 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
88 /* Remove from iteration list */
90 e->iterate_next->iterate_previous = e->iterate_previous;
92 h->iterate_list_tail = e->iterate_previous;
94 if (e->iterate_previous)
95 e->iterate_previous->iterate_next = e->iterate_next;
97 h->iterate_list_head = e->iterate_next;
99 /* Remove from hash table bucket list */
101 e->bucket_next->bucket_previous = e->bucket_previous;
103 if (e->bucket_previous)
104 e->bucket_previous->bucket_next = e->bucket_next;
106 unsigned hash = h->hash_func(e->key) % NBUCKETS;
107 BY_HASH(h)[hash] = e->bucket_next;
112 assert(h->n_entries >= 1);
116 void hashmap_free(Hashmap*h) {
126 void hashmap_clear(Hashmap *h) {
130 while (h->iterate_list_head)
131 remove_entry(h, h->iterate_list_head);
134 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
135 struct hashmap_entry *e;
137 assert(hash < NBUCKETS);
139 for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
140 if (h->compare_func(e->key, key) == 0)
146 int hashmap_put(Hashmap *h, const void *key, void *value) {
147 struct hashmap_entry *e;
152 hash = h->hash_func(key) % NBUCKETS;
154 if ((e = hash_scan(h, hash, key))) {
156 if (e->value == value)
162 if (!(e = new(struct hashmap_entry, 1)))
168 /* Insert into hash table */
169 e->bucket_next = BY_HASH(h)[hash];
170 e->bucket_previous = NULL;
171 if (BY_HASH(h)[hash])
172 BY_HASH(h)[hash]->bucket_previous = e;
173 BY_HASH(h)[hash] = e;
175 /* Insert into iteration list */
176 e->iterate_previous = h->iterate_list_tail;
177 e->iterate_next = NULL;
178 if (h->iterate_list_tail) {
179 assert(h->iterate_list_head);
180 h->iterate_list_tail->iterate_next = e;
182 assert(!h->iterate_list_head);
183 h->iterate_list_head = e;
185 h->iterate_list_tail = e;
188 assert(h->n_entries >= 1);
193 int hashmap_replace(Hashmap *h, const void *key, void *value) {
194 struct hashmap_entry *e;
199 hash = h->hash_func(key) % NBUCKETS;
201 if ((e = hash_scan(h, hash, key))) {
206 return hashmap_put(h, key, value);
209 void* hashmap_get(Hashmap *h, const void *key) {
211 struct hashmap_entry *e;
216 hash = h->hash_func(key) % NBUCKETS;
218 if (!(e = hash_scan(h, hash, key)))
224 void* hashmap_remove(Hashmap *h, const void *key) {
225 struct hashmap_entry *e;
232 hash = h->hash_func(key) % NBUCKETS;
234 if (!(e = hash_scan(h, hash, key)))
243 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
244 struct hashmap_entry *e;
250 hash = h->hash_func(key) % NBUCKETS;
252 if (!(e = hash_scan(h, hash, key)))
255 if (e->value != value)
263 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
264 struct hashmap_entry *e;
271 if (*i == ITERATOR_LAST)
274 if (*i == ITERATOR_FIRST && !h->iterate_list_head)
277 e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
280 *i = (Iterator) e->iterate_next;
298 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
299 struct hashmap_entry *e;
306 if (*i == ITERATOR_FIRST)
309 if (*i == ITERATOR_LAST && !h->iterate_list_tail)
312 e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
314 if (e->iterate_previous)
315 *i = (Iterator) e->iterate_previous;
333 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
335 struct hashmap_entry *e;
340 hash = h->hash_func(key) % NBUCKETS;
342 if (!(e = hash_scan(h, hash, key)))
350 void* hashmap_first(Hashmap *h) {
355 if (!h->iterate_list_head)
358 return h->iterate_list_head->value;
361 void* hashmap_last(Hashmap *h) {
366 if (!h->iterate_list_tail)
369 return h->iterate_list_tail->value;
372 void* hashmap_steal_first(Hashmap *h) {
378 if (!h->iterate_list_head)
381 data = h->iterate_list_head->value;
382 remove_entry(h, h->iterate_list_head);
387 unsigned hashmap_size(Hashmap *h) {
395 bool hashmap_isempty(Hashmap *h) {
400 return h->n_entries == 0;
403 int hashmap_merge(Hashmap *h, Hashmap *other) {
404 struct hashmap_entry *e;
411 for (e = other->iterate_list_head; e; e = e->iterate_next) {
414 if ((r = hashmap_put(h, e->key, e->value)) < 0)
422 Hashmap *hashmap_copy(Hashmap *h) {
427 if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
430 if (hashmap_merge(copy, h) < 0) {