1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
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/>.
33 struct hashmap_entry
{
36 struct hashmap_entry
*bucket_next
, *bucket_previous
;
37 struct hashmap_entry
*iterate_next
, *iterate_previous
;
41 hash_func_t hash_func
;
42 compare_func_t compare_func
;
44 struct hashmap_entry
*iterate_list_head
, *iterate_list_tail
;
48 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
50 unsigned string_hash_func(const void *p
) {
55 hash
= 31 * hash
+ (unsigned) *c
;
60 int string_compare_func(const void *a
, const void *b
) {
64 unsigned trivial_hash_func(const void *p
) {
65 return PTR_TO_UINT(p
);
68 int trivial_compare_func(const void *a
, const void *b
) {
69 return a
< b
? -1 : (a
> b
? 1 : 0);
72 Hashmap
*hashmap_new(hash_func_t hash_func
, compare_func_t compare_func
) {
75 if (!(h
= malloc0(ALIGN(sizeof(Hashmap
)) + NBUCKETS
* ALIGN(sizeof(struct hashmap_entry
*)))))
78 h
->hash_func
= hash_func
? hash_func
: trivial_hash_func
;
79 h
->compare_func
= compare_func
? compare_func
: trivial_compare_func
;
82 h
->iterate_list_head
= h
->iterate_list_tail
= NULL
;
87 int hashmap_ensure_allocated(Hashmap
**h
, hash_func_t hash_func
, compare_func_t compare_func
) {
93 if (!(*h
= hashmap_new(hash_func
, compare_func
)))
99 static void link_entry(Hashmap
*h
, struct hashmap_entry
*e
, unsigned hash
) {
103 /* Insert into hash table */
104 e
->bucket_next
= BY_HASH(h
)[hash
];
105 e
->bucket_previous
= NULL
;
106 if (BY_HASH(h
)[hash
])
107 BY_HASH(h
)[hash
]->bucket_previous
= e
;
108 BY_HASH(h
)[hash
] = e
;
110 /* Insert into iteration list */
111 e
->iterate_previous
= h
->iterate_list_tail
;
112 e
->iterate_next
= NULL
;
113 if (h
->iterate_list_tail
) {
114 assert(h
->iterate_list_head
);
115 h
->iterate_list_tail
->iterate_next
= e
;
117 assert(!h
->iterate_list_head
);
118 h
->iterate_list_head
= e
;
120 h
->iterate_list_tail
= e
;
123 assert(h
->n_entries
>= 1);
126 static void unlink_entry(Hashmap
*h
, struct hashmap_entry
*e
, unsigned hash
) {
130 /* Remove from iteration list */
132 e
->iterate_next
->iterate_previous
= e
->iterate_previous
;
134 h
->iterate_list_tail
= e
->iterate_previous
;
136 if (e
->iterate_previous
)
137 e
->iterate_previous
->iterate_next
= e
->iterate_next
;
139 h
->iterate_list_head
= e
->iterate_next
;
141 /* Remove from hash table bucket list */
143 e
->bucket_next
->bucket_previous
= e
->bucket_previous
;
145 if (e
->bucket_previous
)
146 e
->bucket_previous
->bucket_next
= e
->bucket_next
;
148 BY_HASH(h
)[hash
] = e
->bucket_next
;
150 assert(h
->n_entries
>= 1);
154 static void remove_entry(Hashmap
*h
, struct hashmap_entry
*e
) {
160 hash
= h
->hash_func(e
->key
) % NBUCKETS
;
162 unlink_entry(h
, e
, hash
);
166 void hashmap_free(Hashmap
*h
) {
176 void hashmap_free_free(Hashmap
*h
) {
179 while ((p
= hashmap_steal_first(h
)))
185 void hashmap_clear(Hashmap
*h
) {
189 while (h
->iterate_list_head
)
190 remove_entry(h
, h
->iterate_list_head
);
193 static struct hashmap_entry
*hash_scan(Hashmap
*h
, unsigned hash
, const void *key
) {
194 struct hashmap_entry
*e
;
196 assert(hash
< NBUCKETS
);
198 for (e
= BY_HASH(h
)[hash
]; e
; e
= e
->bucket_next
)
199 if (h
->compare_func(e
->key
, key
) == 0)
205 int hashmap_put(Hashmap
*h
, const void *key
, void *value
) {
206 struct hashmap_entry
*e
;
211 hash
= h
->hash_func(key
) % NBUCKETS
;
213 if ((e
= hash_scan(h
, hash
, key
))) {
215 if (e
->value
== value
)
221 if (!(e
= new(struct hashmap_entry
, 1)))
227 link_entry(h
, e
, hash
);
232 int hashmap_replace(Hashmap
*h
, const void *key
, void *value
) {
233 struct hashmap_entry
*e
;
238 hash
= h
->hash_func(key
) % NBUCKETS
;
240 if ((e
= hash_scan(h
, hash
, key
))) {
246 return hashmap_put(h
, key
, value
);
249 void* hashmap_get(Hashmap
*h
, const void *key
) {
251 struct hashmap_entry
*e
;
256 hash
= h
->hash_func(key
) % NBUCKETS
;
258 if (!(e
= hash_scan(h
, hash
, key
)))
264 void* hashmap_remove(Hashmap
*h
, const void *key
) {
265 struct hashmap_entry
*e
;
272 hash
= h
->hash_func(key
) % NBUCKETS
;
274 if (!(e
= hash_scan(h
, hash
, key
)))
283 int hashmap_remove_and_put(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
284 struct hashmap_entry
*e
;
285 unsigned old_hash
, new_hash
;
290 old_hash
= h
->hash_func(old_key
) % NBUCKETS
;
291 if (!(e
= hash_scan(h
, old_hash
, old_key
)))
294 new_hash
= h
->hash_func(new_key
) % NBUCKETS
;
295 if (hash_scan(h
, new_hash
, new_key
))
298 unlink_entry(h
, e
, old_hash
);
303 link_entry(h
, e
, new_hash
);
308 int hashmap_remove_and_replace(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
309 struct hashmap_entry
*e
, *k
;
310 unsigned old_hash
, new_hash
;
315 old_hash
= h
->hash_func(old_key
) % NBUCKETS
;
316 if (!(e
= hash_scan(h
, old_hash
, old_key
)))
319 new_hash
= h
->hash_func(new_key
) % NBUCKETS
;
321 if ((k
= hash_scan(h
, new_hash
, new_key
)))
325 unlink_entry(h
, e
, old_hash
);
330 link_entry(h
, e
, new_hash
);
335 void* hashmap_remove_value(Hashmap
*h
, const void *key
, void *value
) {
336 struct hashmap_entry
*e
;
342 hash
= h
->hash_func(key
) % NBUCKETS
;
344 if (!(e
= hash_scan(h
, hash
, key
)))
347 if (e
->value
!= value
)
355 void *hashmap_iterate(Hashmap
*h
, Iterator
*i
, const void **key
) {
356 struct hashmap_entry
*e
;
363 if (*i
== ITERATOR_LAST
)
366 if (*i
== ITERATOR_FIRST
&& !h
->iterate_list_head
)
369 e
= *i
== ITERATOR_FIRST
? h
->iterate_list_head
: (struct hashmap_entry
*) *i
;
372 *i
= (Iterator
) e
->iterate_next
;
390 void *hashmap_iterate_backwards(Hashmap
*h
, Iterator
*i
, const void **key
) {
391 struct hashmap_entry
*e
;
398 if (*i
== ITERATOR_FIRST
)
401 if (*i
== ITERATOR_LAST
&& !h
->iterate_list_tail
)
404 e
= *i
== ITERATOR_LAST
? h
->iterate_list_tail
: (struct hashmap_entry
*) *i
;
406 if (e
->iterate_previous
)
407 *i
= (Iterator
) e
->iterate_previous
;
425 void *hashmap_iterate_skip(Hashmap
*h
, const void *key
, Iterator
*i
) {
427 struct hashmap_entry
*e
;
432 hash
= h
->hash_func(key
) % NBUCKETS
;
434 if (!(e
= hash_scan(h
, hash
, key
)))
442 void* hashmap_first(Hashmap
*h
) {
447 if (!h
->iterate_list_head
)
450 return h
->iterate_list_head
->value
;
453 void* hashmap_last(Hashmap
*h
) {
458 if (!h
->iterate_list_tail
)
461 return h
->iterate_list_tail
->value
;
464 void* hashmap_steal_first(Hashmap
*h
) {
470 if (!h
->iterate_list_head
)
473 data
= h
->iterate_list_head
->value
;
474 remove_entry(h
, h
->iterate_list_head
);
479 void* hashmap_steal_first_key(Hashmap
*h
) {
485 if (!h
->iterate_list_head
)
488 key
= (void*) h
->iterate_list_head
->key
;
489 remove_entry(h
, h
->iterate_list_head
);
494 unsigned hashmap_size(Hashmap
*h
) {
502 bool hashmap_isempty(Hashmap
*h
) {
507 return h
->n_entries
== 0;
510 int hashmap_merge(Hashmap
*h
, Hashmap
*other
) {
511 struct hashmap_entry
*e
;
518 for (e
= other
->iterate_list_head
; e
; e
= e
->iterate_next
) {
521 if ((r
= hashmap_put(h
, e
->key
, e
->value
)) < 0)
529 void hashmap_move(Hashmap
*h
, Hashmap
*other
) {
530 struct hashmap_entry
*e
, *n
;
534 /* The same as hashmap_merge(), but every new item from other
535 * is moved to h. This function is guaranteed to succeed. */
540 for (e
= other
->iterate_list_head
; e
; e
= n
) {
541 unsigned h_hash
, other_hash
;
545 h_hash
= h
->hash_func(e
->key
) % NBUCKETS
;
547 if (hash_scan(h
, h_hash
, e
->key
))
550 other_hash
= other
->hash_func(e
->key
) % NBUCKETS
;
552 unlink_entry(other
, e
, other_hash
);
553 link_entry(h
, e
, h_hash
);
557 int hashmap_move_one(Hashmap
*h
, Hashmap
*other
, const void *key
) {
558 unsigned h_hash
, other_hash
;
559 struct hashmap_entry
*e
;
566 h_hash
= h
->hash_func(key
) % NBUCKETS
;
567 if (hash_scan(h
, h_hash
, key
))
570 other_hash
= other
->hash_func(key
) % NBUCKETS
;
571 if (!(e
= hash_scan(other
, other_hash
, key
)))
574 unlink_entry(other
, e
, other_hash
);
575 link_entry(h
, e
, h_hash
);
580 Hashmap
*hashmap_copy(Hashmap
*h
) {
585 if (!(copy
= hashmap_new(h
->hash_func
, h
->compare_func
)))
588 if (hashmap_merge(copy
, h
) < 0) {