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 Lesser General Public License as published by
10 the Free Software Foundation; either version 2.1 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 Lesser General Public License for more details.
18 You should have received a copy of the GNU Lesser 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
;
50 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
58 static struct pool
*first_hashmap_pool
= NULL
;
59 static void *first_hashmap_tile
= NULL
;
61 static struct pool
*first_entry_pool
= NULL
;
62 static void *first_entry_tile
= NULL
;
64 static void* allocate_tile(struct pool
**first_pool
, void **first_tile
, size_t tile_size
) {
71 *first_tile
= * (void**) (*first_tile
);
75 if (_unlikely_(!*first_pool
) || _unlikely_((*first_pool
)->n_used
>= (*first_pool
)->n_tiles
)) {
80 n
= *first_pool
? (*first_pool
)->n_tiles
: 0;
82 size
= PAGE_ALIGN(ALIGN(sizeof(struct pool
)) + n
*tile_size
);
83 n
= (size
- ALIGN(sizeof(struct pool
))) / tile_size
;
89 p
->next
= *first_pool
;
96 i
= (*first_pool
)->n_used
++;
98 return ((uint8_t*) (*first_pool
)) + ALIGN(sizeof(struct pool
)) + i
*tile_size
;
101 static void deallocate_tile(void **first_tile
, void *p
) {
102 * (void**) p
= *first_tile
;
108 static void drop_pool(struct pool
*p
) {
117 __attribute__((destructor
)) static void cleanup_pool(void) {
118 /* Be nice to valgrind */
120 drop_pool(first_hashmap_pool
);
121 drop_pool(first_entry_pool
);
126 unsigned string_hash_func(const void *p
) {
127 unsigned hash
= 5381;
128 const signed char *c
;
130 /* DJB's hash function */
133 hash
= (hash
<< 5) + hash
+ (unsigned) *c
;
138 int string_compare_func(const void *a
, const void *b
) {
142 unsigned trivial_hash_func(const void *p
) {
143 return PTR_TO_UINT(p
);
146 int trivial_compare_func(const void *a
, const void *b
) {
147 return a
< b
? -1 : (a
> b
? 1 : 0);
150 Hashmap
*hashmap_new(hash_func_t hash_func
, compare_func_t compare_func
) {
155 b
= is_main_thread();
157 size
= ALIGN(sizeof(Hashmap
)) + NBUCKETS
* sizeof(struct hashmap_entry
*);
160 h
= allocate_tile(&first_hashmap_pool
, &first_hashmap_tile
, size
);
172 h
->hash_func
= hash_func
? hash_func
: trivial_hash_func
;
173 h
->compare_func
= compare_func
? compare_func
: trivial_compare_func
;
176 h
->iterate_list_head
= h
->iterate_list_tail
= NULL
;
183 int hashmap_ensure_allocated(Hashmap
**h
, hash_func_t hash_func
, compare_func_t compare_func
) {
189 if (!(*h
= hashmap_new(hash_func
, compare_func
)))
195 static void link_entry(Hashmap
*h
, struct hashmap_entry
*e
, unsigned hash
) {
199 /* Insert into hash table */
200 e
->bucket_next
= BY_HASH(h
)[hash
];
201 e
->bucket_previous
= NULL
;
202 if (BY_HASH(h
)[hash
])
203 BY_HASH(h
)[hash
]->bucket_previous
= e
;
204 BY_HASH(h
)[hash
] = e
;
206 /* Insert into iteration list */
207 e
->iterate_previous
= h
->iterate_list_tail
;
208 e
->iterate_next
= NULL
;
209 if (h
->iterate_list_tail
) {
210 assert(h
->iterate_list_head
);
211 h
->iterate_list_tail
->iterate_next
= e
;
213 assert(!h
->iterate_list_head
);
214 h
->iterate_list_head
= e
;
216 h
->iterate_list_tail
= e
;
219 assert(h
->n_entries
>= 1);
222 static void unlink_entry(Hashmap
*h
, struct hashmap_entry
*e
, unsigned hash
) {
226 /* Remove from iteration list */
228 e
->iterate_next
->iterate_previous
= e
->iterate_previous
;
230 h
->iterate_list_tail
= e
->iterate_previous
;
232 if (e
->iterate_previous
)
233 e
->iterate_previous
->iterate_next
= e
->iterate_next
;
235 h
->iterate_list_head
= e
->iterate_next
;
237 /* Remove from hash table bucket list */
239 e
->bucket_next
->bucket_previous
= e
->bucket_previous
;
241 if (e
->bucket_previous
)
242 e
->bucket_previous
->bucket_next
= e
->bucket_next
;
244 BY_HASH(h
)[hash
] = e
->bucket_next
;
246 assert(h
->n_entries
>= 1);
250 static void remove_entry(Hashmap
*h
, struct hashmap_entry
*e
) {
256 hash
= h
->hash_func(e
->key
) % NBUCKETS
;
258 unlink_entry(h
, e
, hash
);
261 deallocate_tile(&first_entry_tile
, e
);
266 void hashmap_free(Hashmap
*h
) {
268 /* Free the hashmap, but nothing in it */
276 deallocate_tile(&first_hashmap_tile
, h
);
281 void hashmap_free_free(Hashmap
*h
) {
283 /* Free the hashmap and all data objects in it, but not the
289 hashmap_clear_free(h
);
293 void hashmap_clear(Hashmap
*h
) {
297 while (h
->iterate_list_head
)
298 remove_entry(h
, h
->iterate_list_head
);
301 void hashmap_clear_free(Hashmap
*h
) {
307 while ((p
= hashmap_steal_first(h
)))
311 static struct hashmap_entry
*hash_scan(Hashmap
*h
, unsigned hash
, const void *key
) {
312 struct hashmap_entry
*e
;
314 assert(hash
< NBUCKETS
);
316 for (e
= BY_HASH(h
)[hash
]; e
; e
= e
->bucket_next
)
317 if (h
->compare_func(e
->key
, key
) == 0)
323 int hashmap_put(Hashmap
*h
, const void *key
, void *value
) {
324 struct hashmap_entry
*e
;
329 hash
= h
->hash_func(key
) % NBUCKETS
;
331 if ((e
= hash_scan(h
, hash
, key
))) {
333 if (e
->value
== value
)
340 e
= allocate_tile(&first_entry_pool
, &first_entry_tile
, sizeof(struct hashmap_entry
));
342 e
= new(struct hashmap_entry
, 1);
350 link_entry(h
, e
, hash
);
355 int hashmap_replace(Hashmap
*h
, const void *key
, void *value
) {
356 struct hashmap_entry
*e
;
361 hash
= h
->hash_func(key
) % NBUCKETS
;
363 if ((e
= hash_scan(h
, hash
, key
))) {
369 return hashmap_put(h
, key
, value
);
372 void* hashmap_get(Hashmap
*h
, const void *key
) {
374 struct hashmap_entry
*e
;
379 hash
= h
->hash_func(key
) % NBUCKETS
;
380 e
= hash_scan(h
, hash
, key
);
387 bool hashmap_contains(Hashmap
*h
, const void *key
) {
393 hash
= h
->hash_func(key
) % NBUCKETS
;
395 if (!hash_scan(h
, hash
, key
))
401 void* hashmap_remove(Hashmap
*h
, const void *key
) {
402 struct hashmap_entry
*e
;
409 hash
= h
->hash_func(key
) % NBUCKETS
;
411 if (!(e
= hash_scan(h
, hash
, key
)))
420 int hashmap_remove_and_put(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
421 struct hashmap_entry
*e
;
422 unsigned old_hash
, new_hash
;
427 old_hash
= h
->hash_func(old_key
) % NBUCKETS
;
428 if (!(e
= hash_scan(h
, old_hash
, old_key
)))
431 new_hash
= h
->hash_func(new_key
) % NBUCKETS
;
432 if (hash_scan(h
, new_hash
, new_key
))
435 unlink_entry(h
, e
, old_hash
);
440 link_entry(h
, e
, new_hash
);
445 int hashmap_remove_and_replace(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
446 struct hashmap_entry
*e
, *k
;
447 unsigned old_hash
, new_hash
;
452 old_hash
= h
->hash_func(old_key
) % NBUCKETS
;
453 if (!(e
= hash_scan(h
, old_hash
, old_key
)))
456 new_hash
= h
->hash_func(new_key
) % NBUCKETS
;
458 if ((k
= hash_scan(h
, new_hash
, new_key
)))
462 unlink_entry(h
, e
, old_hash
);
467 link_entry(h
, e
, new_hash
);
472 void* hashmap_remove_value(Hashmap
*h
, const void *key
, void *value
) {
473 struct hashmap_entry
*e
;
479 hash
= h
->hash_func(key
) % NBUCKETS
;
481 if (!(e
= hash_scan(h
, hash
, key
)))
484 if (e
->value
!= value
)
492 void *hashmap_iterate(Hashmap
*h
, Iterator
*i
, const void **key
) {
493 struct hashmap_entry
*e
;
500 if (*i
== ITERATOR_LAST
)
503 if (*i
== ITERATOR_FIRST
&& !h
->iterate_list_head
)
506 e
= *i
== ITERATOR_FIRST
? h
->iterate_list_head
: (struct hashmap_entry
*) *i
;
509 *i
= (Iterator
) e
->iterate_next
;
527 void *hashmap_iterate_backwards(Hashmap
*h
, Iterator
*i
, const void **key
) {
528 struct hashmap_entry
*e
;
535 if (*i
== ITERATOR_FIRST
)
538 if (*i
== ITERATOR_LAST
&& !h
->iterate_list_tail
)
541 e
= *i
== ITERATOR_LAST
? h
->iterate_list_tail
: (struct hashmap_entry
*) *i
;
543 if (e
->iterate_previous
)
544 *i
= (Iterator
) e
->iterate_previous
;
562 void *hashmap_iterate_skip(Hashmap
*h
, const void *key
, Iterator
*i
) {
564 struct hashmap_entry
*e
;
569 hash
= h
->hash_func(key
) % NBUCKETS
;
571 if (!(e
= hash_scan(h
, hash
, key
)))
579 void* hashmap_first(Hashmap
*h
) {
584 if (!h
->iterate_list_head
)
587 return h
->iterate_list_head
->value
;
590 void* hashmap_first_key(Hashmap
*h
) {
595 if (!h
->iterate_list_head
)
598 return (void*) h
->iterate_list_head
->key
;
601 void* hashmap_last(Hashmap
*h
) {
606 if (!h
->iterate_list_tail
)
609 return h
->iterate_list_tail
->value
;
612 void* hashmap_steal_first(Hashmap
*h
) {
618 if (!h
->iterate_list_head
)
621 data
= h
->iterate_list_head
->value
;
622 remove_entry(h
, h
->iterate_list_head
);
627 void* hashmap_steal_first_key(Hashmap
*h
) {
633 if (!h
->iterate_list_head
)
636 key
= (void*) h
->iterate_list_head
->key
;
637 remove_entry(h
, h
->iterate_list_head
);
642 unsigned hashmap_size(Hashmap
*h
) {
650 bool hashmap_isempty(Hashmap
*h
) {
655 return h
->n_entries
== 0;
658 int hashmap_merge(Hashmap
*h
, Hashmap
*other
) {
659 struct hashmap_entry
*e
;
666 for (e
= other
->iterate_list_head
; e
; e
= e
->iterate_next
) {
669 if ((r
= hashmap_put(h
, e
->key
, e
->value
)) < 0)
677 void hashmap_move(Hashmap
*h
, Hashmap
*other
) {
678 struct hashmap_entry
*e
, *n
;
682 /* The same as hashmap_merge(), but every new item from other
683 * is moved to h. This function is guaranteed to succeed. */
688 for (e
= other
->iterate_list_head
; e
; e
= n
) {
689 unsigned h_hash
, other_hash
;
693 h_hash
= h
->hash_func(e
->key
) % NBUCKETS
;
695 if (hash_scan(h
, h_hash
, e
->key
))
698 other_hash
= other
->hash_func(e
->key
) % NBUCKETS
;
700 unlink_entry(other
, e
, other_hash
);
701 link_entry(h
, e
, h_hash
);
705 int hashmap_move_one(Hashmap
*h
, Hashmap
*other
, const void *key
) {
706 unsigned h_hash
, other_hash
;
707 struct hashmap_entry
*e
;
714 h_hash
= h
->hash_func(key
) % NBUCKETS
;
715 if (hash_scan(h
, h_hash
, key
))
718 other_hash
= other
->hash_func(key
) % NBUCKETS
;
719 if (!(e
= hash_scan(other
, other_hash
, key
)))
722 unlink_entry(other
, e
, other_hash
);
723 link_entry(h
, e
, h_hash
);
728 Hashmap
*hashmap_copy(Hashmap
*h
) {
733 if (!(copy
= hashmap_new(h
->hash_func
, h
->compare_func
)))
736 if (hashmap_merge(copy
, h
) < 0) {
744 char **hashmap_get_strv(Hashmap
*h
) {
750 sv
= new(char*, h
->n_entries
+1);
755 HASHMAP_FOREACH(item
, h
, it
)