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;