1 /*-*- Mode: C; c-basic-offset: 8 -*-*/
4 This file is part of systemd.
6 Copyright 2010 Lennart Poettering
8 systemd is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
13 systemd is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with systemd; If not, see <http://www.gnu.org/licenses/>.
37 struct hashmap_entry
{
40 struct hashmap_entry
*bucket_next
, *bucket_previous
;
41 struct hashmap_entry
*iterate_next
, *iterate_previous
;
45 hash_func_t hash_func
;
46 compare_func_t compare_func
;
48 struct hashmap_entry
*iterate_list_head
, *iterate_list_tail
;
52 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
54 unsigned string_hash_func(const void *p
) {
59 hash
= 31 * hash
+ (unsigned) *c
;
64 int string_compare_func(const void *a
, const void *b
) {
68 unsigned trivial_hash_func(const void *p
) {
69 return PTR_TO_UINT(p
);
72 int trivial_compare_func(const void *a
, const void *b
) {
73 return a
< b
? -1 : (a
> b
? 1 : 0);
76 Hashmap
*hashmap_new(hash_func_t hash_func
, compare_func_t compare_func
) {
79 if (!(h
= malloc0(ALIGN(sizeof(Hashmap
)) + NBUCKETS
* ALIGN(sizeof(struct hashmap_entry
*)))))
82 h
->hash_func
= hash_func
? hash_func
: trivial_hash_func
;
83 h
->compare_func
= compare_func
? compare_func
: trivial_compare_func
;
86 h
->iterate_list_head
= h
->iterate_list_tail
= NULL
;
91 int hashmap_ensure_allocated(Hashmap
**h
, hash_func_t hash_func
, compare_func_t compare_func
) {
97 if (!(*h
= hashmap_new(hash_func
, compare_func
)))
103 static void remove_entry(Hashmap
*h
, struct hashmap_entry
*e
) {
107 /* Remove from iteration list */
109 e
->iterate_next
->iterate_previous
= e
->iterate_previous
;
111 h
->iterate_list_tail
= e
->iterate_previous
;
113 if (e
->iterate_previous
)
114 e
->iterate_previous
->iterate_next
= e
->iterate_next
;
116 h
->iterate_list_head
= e
->iterate_next
;
118 /* Remove from hash table bucket list */
120 e
->bucket_next
->bucket_previous
= e
->bucket_previous
;
122 if (e
->bucket_previous
)
123 e
->bucket_previous
->bucket_next
= e
->bucket_next
;
125 unsigned hash
= h
->hash_func(e
->key
) % NBUCKETS
;
126 BY_HASH(h
)[hash
] = e
->bucket_next
;
131 assert(h
->n_entries
>= 1);
135 void hashmap_free(Hashmap
*h
) {
145 void hashmap_clear(Hashmap
*h
) {
149 while (h
->iterate_list_head
)
150 remove_entry(h
, h
->iterate_list_head
);
153 static struct hashmap_entry
*hash_scan(Hashmap
*h
, unsigned hash
, const void *key
) {
154 struct hashmap_entry
*e
;
156 assert(hash
< NBUCKETS
);
158 for (e
= BY_HASH(h
)[hash
]; e
; e
= e
->bucket_next
)
159 if (h
->compare_func(e
->key
, key
) == 0)
165 int hashmap_put(Hashmap
*h
, const void *key
, void *value
) {
166 struct hashmap_entry
*e
;
171 hash
= h
->hash_func(key
) % NBUCKETS
;
173 if ((e
= hash_scan(h
, hash
, key
))) {
175 if (e
->value
== value
)
181 if (!(e
= new(struct hashmap_entry
, 1)))
187 /* Insert into hash table */
188 e
->bucket_next
= BY_HASH(h
)[hash
];
189 e
->bucket_previous
= NULL
;
190 if (BY_HASH(h
)[hash
])
191 BY_HASH(h
)[hash
]->bucket_previous
= e
;
192 BY_HASH(h
)[hash
] = e
;
194 /* Insert into iteration list */
195 e
->iterate_previous
= h
->iterate_list_tail
;
196 e
->iterate_next
= NULL
;
197 if (h
->iterate_list_tail
) {
198 assert(h
->iterate_list_head
);
199 h
->iterate_list_tail
->iterate_next
= e
;
201 assert(!h
->iterate_list_head
);
202 h
->iterate_list_head
= e
;
204 h
->iterate_list_tail
= e
;
207 assert(h
->n_entries
>= 1);
212 int hashmap_replace(Hashmap
*h
, const void *key
, void *value
) {
213 struct hashmap_entry
*e
;
218 hash
= h
->hash_func(key
) % NBUCKETS
;
220 if ((e
= hash_scan(h
, hash
, key
))) {
225 return hashmap_put(h
, key
, value
);
228 void* hashmap_get(Hashmap
*h
, const void *key
) {
230 struct hashmap_entry
*e
;
235 hash
= h
->hash_func(key
) % NBUCKETS
;
237 if (!(e
= hash_scan(h
, hash
, key
)))
243 void* hashmap_remove(Hashmap
*h
, const void *key
) {
244 struct hashmap_entry
*e
;
251 hash
= h
->hash_func(key
) % NBUCKETS
;
253 if (!(e
= hash_scan(h
, hash
, key
)))
262 void* hashmap_remove_value(Hashmap
*h
, const void *key
, void *value
) {
263 struct hashmap_entry
*e
;
269 hash
= h
->hash_func(key
) % NBUCKETS
;
271 if (!(e
= hash_scan(h
, hash
, key
)))
274 if (e
->value
!= value
)
282 void *hashmap_iterate(Hashmap
*h
, Iterator
*i
, const void **key
) {
283 struct hashmap_entry
*e
;
290 if (*i
== ITERATOR_LAST
)
293 if (*i
== ITERATOR_FIRST
&& !h
->iterate_list_head
)
296 e
= *i
== ITERATOR_FIRST
? h
->iterate_list_head
: (struct hashmap_entry
*) *i
;
299 *i
= (Iterator
) e
->iterate_next
;
317 void *hashmap_iterate_backwards(Hashmap
*h
, Iterator
*i
, const void **key
) {
318 struct hashmap_entry
*e
;
325 if (*i
== ITERATOR_FIRST
)
328 if (*i
== ITERATOR_LAST
&& !h
->iterate_list_tail
)
331 e
= *i
== ITERATOR_LAST
? h
->iterate_list_tail
: (struct hashmap_entry
*) *i
;
333 if (e
->iterate_previous
)
334 *i
= (Iterator
) e
->iterate_previous
;
352 void *hashmap_iterate_skip(Hashmap
*h
, const void *key
, Iterator
*i
) {
354 struct hashmap_entry
*e
;
359 hash
= h
->hash_func(key
) % NBUCKETS
;
361 if (!(e
= hash_scan(h
, hash
, key
)))
369 void* hashmap_first(Hashmap
*h
) {
374 if (!h
->iterate_list_head
)
377 return h
->iterate_list_head
->value
;
380 void* hashmap_last(Hashmap
*h
) {
385 if (!h
->iterate_list_tail
)
388 return h
->iterate_list_tail
->value
;
391 void* hashmap_steal_first(Hashmap
*h
) {
397 if (!h
->iterate_list_head
)
400 data
= h
->iterate_list_head
->value
;
401 remove_entry(h
, h
->iterate_list_head
);
406 unsigned hashmap_size(Hashmap
*h
) {
414 bool hashmap_isempty(Hashmap
*h
) {
419 return h
->n_entries
== 0;
422 int hashmap_merge(Hashmap
*h
, Hashmap
*other
) {
423 struct hashmap_entry
*e
;
430 for (e
= other
->iterate_list_head
; e
; e
= e
->iterate_next
) {
433 if ((r
= hashmap_put(h
, e
->key
, e
->value
)) < 0)
441 Hashmap
*hashmap_copy(Hashmap
*h
) {
446 if (!(copy
= hashmap_new(h
->hash_func
, h
->compare_func
)))
449 if (hashmap_merge(copy
, h
) < 0) {