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) {