1 /*-*- Mode: C; c-basic-offset: 8 -*-*/
18 struct hashmap_entry {
22 struct hashmap_entry *bucket_next, *bucket_previous;
23 struct hashmap_entry *iterate_next, *iterate_previous;
27 hash_func_t hash_func;
28 compare_func_t compare_func;
30 struct hashmap_entry *iterate_list_head, *iterate_list_tail;
34 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
36 unsigned string_hash_func(const void *p) {
41 hash = 31 * hash + (unsigned) *c;
46 int string_compare_func(const void *a, const void *b) {
50 unsigned trivial_hash_func(const void *p) {
51 return PTR_TO_UINT(p);
54 int trivial_compare_func(const void *a, const void *b) {
55 return a < b ? -1 : (a > b ? 1 : 0);
58 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
61 if (!(h = malloc0(ALIGN(sizeof(Hashmap)) + NBUCKETS * ALIGN(sizeof(struct hashmap_entry*)))))
64 h->hash_func = hash_func ? hash_func : trivial_hash_func;
65 h->compare_func = compare_func ? compare_func : trivial_compare_func;
68 h->iterate_list_head = h->iterate_list_tail = NULL;
73 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
77 /* Remove from iteration list */
79 e->iterate_next->iterate_previous = e->iterate_previous;
81 h->iterate_list_tail = e->iterate_previous;
83 if (e->iterate_previous)
84 e->iterate_previous->iterate_next = e->iterate_next;
86 h->iterate_list_head = e->iterate_next;
88 /* Remove from hash table bucket list */
90 e->bucket_next->bucket_previous = e->bucket_previous;
92 if (e->bucket_previous)
93 e->bucket_previous->bucket_next = e->bucket_next;
95 unsigned hash = h->hash_func(e->key) % NBUCKETS;
96 BY_HASH(h)[hash] = e->bucket_next;
101 assert(h->n_entries >= 1);
105 void hashmap_free(Hashmap*h) {
110 while (h->iterate_list_head)
111 remove_entry(h, h->iterate_list_head);
116 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
117 struct hashmap_entry *e;
119 assert(hash < NBUCKETS);
121 for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
122 if (h->compare_func(e->key, key) == 0)
128 int hashmap_put(Hashmap *h, const void *key, void *value) {
129 struct hashmap_entry *e;
134 hash = h->hash_func(key) % NBUCKETS;
136 if (hash_scan(h, hash, key))
139 if (!(e = new(struct hashmap_entry, 1)))
145 /* Insert into hash table */
146 e->bucket_next = BY_HASH(h)[hash];
147 e->bucket_previous = NULL;
148 if (BY_HASH(h)[hash])
149 BY_HASH(h)[hash]->bucket_previous = e;
150 BY_HASH(h)[hash] = e;
152 /* Insert into iteration list */
153 e->iterate_previous = h->iterate_list_tail;
154 e->iterate_next = NULL;
155 if (h->iterate_list_tail) {
156 assert(h->iterate_list_head);
157 h->iterate_list_tail->iterate_next = e;
159 assert(!h->iterate_list_head);
160 h->iterate_list_head = e;
162 h->iterate_list_tail = e;
165 assert(h->n_entries >= 1);
170 void* hashmap_get(Hashmap *h, const void *key) {
172 struct hashmap_entry *e;
177 hash = h->hash_func(key) % NBUCKETS;
179 if (!(e = hash_scan(h, hash, key)))
185 void* hashmap_remove(Hashmap *h, const void *key) {
186 struct hashmap_entry *e;
193 hash = h->hash_func(key) % NBUCKETS;
195 if (!(e = hash_scan(h, hash, key)))
204 void *hashmap_iterate(Hashmap *h, void **state, const void **key) {
205 struct hashmap_entry *e;
212 if (*state == (void*) -1)
215 if (!*state && !h->iterate_list_head)
218 e = *state ? *state : h->iterate_list_head;
221 *state = e->iterate_next;
231 *state = (void *) -1;
239 void *hashmap_iterate_backwards(Hashmap *h, void **state, const void **key) {
240 struct hashmap_entry *e;
247 if (*state == (void*) -1)
250 if (!*state && !h->iterate_list_tail)
253 e = *state ? *state : h->iterate_list_tail;
255 if (e->iterate_previous)
256 *state = e->iterate_previous;
266 *state = (void *) -1;
274 void* hashmap_first(Hashmap *h) {
279 if (!h->iterate_list_head)
282 return h->iterate_list_head->value;
285 void* hashmap_last(Hashmap *h) {
290 if (!h->iterate_list_tail)
293 return h->iterate_list_tail->value;
296 void* hashmap_steal_first(Hashmap *h) {
302 if (!h->iterate_list_head)
305 data = h->iterate_list_head->value;
306 remove_entry(h, h->iterate_list_head);
311 unsigned hashmap_size(Hashmap *h) {
319 bool hashmap_isempty(Hashmap *h) {
324 return h->n_entries == 0;