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