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 unsigned uint64_hash_func(const void *p) {
153 assert_cc(sizeof(uint64_t) == 2*sizeof(unsigned));
155 u = *(const uint64_t*) p;
157 return (unsigned) ((u >> 32) ^ u);
160 int uint64_compare_func(const void *_a, const void *_b) {
163 a = *(const uint64_t*) _a;
164 b = *(const uint64_t*) _b;
166 return a < b ? -1 : (a > b ? 1 : 0);
169 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
174 b = is_main_thread();
176 size = ALIGN(sizeof(Hashmap)) + NBUCKETS * sizeof(struct hashmap_entry*);
179 h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size);
191 h->hash_func = hash_func ? hash_func : trivial_hash_func;
192 h->compare_func = compare_func ? compare_func : trivial_compare_func;
195 h->iterate_list_head = h->iterate_list_tail = NULL;
202 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
208 if (!(*h = hashmap_new(hash_func, compare_func)))
214 static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
218 /* Insert into hash table */
219 e->bucket_next = BY_HASH(h)[hash];
220 e->bucket_previous = NULL;
221 if (BY_HASH(h)[hash])
222 BY_HASH(h)[hash]->bucket_previous = e;
223 BY_HASH(h)[hash] = e;
225 /* Insert into iteration list */
226 e->iterate_previous = h->iterate_list_tail;
227 e->iterate_next = NULL;
228 if (h->iterate_list_tail) {
229 assert(h->iterate_list_head);
230 h->iterate_list_tail->iterate_next = e;
232 assert(!h->iterate_list_head);
233 h->iterate_list_head = e;
235 h->iterate_list_tail = e;
238 assert(h->n_entries >= 1);
241 static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
245 /* Remove from iteration list */
247 e->iterate_next->iterate_previous = e->iterate_previous;
249 h->iterate_list_tail = e->iterate_previous;
251 if (e->iterate_previous)
252 e->iterate_previous->iterate_next = e->iterate_next;
254 h->iterate_list_head = e->iterate_next;
256 /* Remove from hash table bucket list */
258 e->bucket_next->bucket_previous = e->bucket_previous;
260 if (e->bucket_previous)
261 e->bucket_previous->bucket_next = e->bucket_next;
263 BY_HASH(h)[hash] = e->bucket_next;
265 assert(h->n_entries >= 1);
269 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
275 hash = h->hash_func(e->key) % NBUCKETS;
277 unlink_entry(h, e, hash);
280 deallocate_tile(&first_entry_tile, e);
285 void hashmap_free(Hashmap*h) {
287 /* Free the hashmap, but nothing in it */
295 deallocate_tile(&first_hashmap_tile, h);
300 void hashmap_free_free(Hashmap *h) {
302 /* Free the hashmap and all data objects in it, but not the
308 hashmap_clear_free(h);
312 void hashmap_free_free_free(Hashmap *h) {
314 /* Free the hashmap and all data and key objects in it */
319 hashmap_clear_free_free(h);
323 void hashmap_clear(Hashmap *h) {
327 while (h->iterate_list_head)
328 remove_entry(h, h->iterate_list_head);
331 void hashmap_clear_free(Hashmap *h) {
337 while ((p = hashmap_steal_first(h)))
341 void hashmap_clear_free_free(Hashmap *h) {
345 while (h->iterate_list_head) {
348 a = h->iterate_list_head->value;
349 b = (void*) h->iterate_list_head->key;
350 remove_entry(h, h->iterate_list_head);
357 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
358 struct hashmap_entry *e;
360 assert(hash < NBUCKETS);
362 for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
363 if (h->compare_func(e->key, key) == 0)
369 int hashmap_put(Hashmap *h, const void *key, void *value) {
370 struct hashmap_entry *e;
375 hash = h->hash_func(key) % NBUCKETS;
376 e = hash_scan(h, hash, key);
378 if (e->value == value)
384 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
386 e = new(struct hashmap_entry, 1);
394 link_entry(h, e, hash);
399 int hashmap_replace(Hashmap *h, const void *key, void *value) {
400 struct hashmap_entry *e;
405 hash = h->hash_func(key) % NBUCKETS;
406 e = hash_scan(h, hash, key);
413 return hashmap_put(h, key, value);
416 int hashmap_update(Hashmap *h, const void *key, void *value) {
417 struct hashmap_entry *e;
422 hash = h->hash_func(key) % NBUCKETS;
423 e = hash_scan(h, hash, key);
431 void* hashmap_get(Hashmap *h, const void *key) {
433 struct hashmap_entry *e;
438 hash = h->hash_func(key) % NBUCKETS;
439 e = hash_scan(h, hash, key);
446 void* hashmap_get2(Hashmap *h, const void *key, void **key2) {
448 struct hashmap_entry *e;
453 hash = h->hash_func(key) % NBUCKETS;
454 e = hash_scan(h, hash, key);
459 *key2 = (void*) e->key;
464 bool hashmap_contains(Hashmap *h, const void *key) {
470 hash = h->hash_func(key) % NBUCKETS;
472 if (!hash_scan(h, hash, key))
478 void* hashmap_remove(Hashmap *h, const void *key) {
479 struct hashmap_entry *e;
486 hash = h->hash_func(key) % NBUCKETS;
488 if (!(e = hash_scan(h, hash, key)))
497 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
498 struct hashmap_entry *e;
499 unsigned old_hash, new_hash;
504 old_hash = h->hash_func(old_key) % NBUCKETS;
505 if (!(e = hash_scan(h, old_hash, old_key)))
508 new_hash = h->hash_func(new_key) % NBUCKETS;
509 if (hash_scan(h, new_hash, new_key))
512 unlink_entry(h, e, old_hash);
517 link_entry(h, e, new_hash);
522 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
523 struct hashmap_entry *e, *k;
524 unsigned old_hash, new_hash;
529 old_hash = h->hash_func(old_key) % NBUCKETS;
530 if (!(e = hash_scan(h, old_hash, old_key)))
533 new_hash = h->hash_func(new_key) % NBUCKETS;
534 if ((k = hash_scan(h, new_hash, new_key)))
538 unlink_entry(h, e, old_hash);
543 link_entry(h, e, new_hash);
548 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
549 struct hashmap_entry *e;
555 hash = h->hash_func(key) % NBUCKETS;
557 if (!(e = hash_scan(h, hash, key)))
560 if (e->value != value)
568 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
569 struct hashmap_entry *e;
576 if (*i == ITERATOR_LAST)
579 if (*i == ITERATOR_FIRST && !h->iterate_list_head)
582 e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
585 *i = (Iterator) e->iterate_next;
603 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
604 struct hashmap_entry *e;
611 if (*i == ITERATOR_FIRST)
614 if (*i == ITERATOR_LAST && !h->iterate_list_tail)
617 e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
619 if (e->iterate_previous)
620 *i = (Iterator) e->iterate_previous;
638 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
640 struct hashmap_entry *e;
645 hash = h->hash_func(key) % NBUCKETS;
647 if (!(e = hash_scan(h, hash, key)))
655 void* hashmap_first(Hashmap *h) {
660 if (!h->iterate_list_head)
663 return h->iterate_list_head->value;
666 void* hashmap_first_key(Hashmap *h) {
671 if (!h->iterate_list_head)
674 return (void*) h->iterate_list_head->key;
677 void* hashmap_last(Hashmap *h) {
682 if (!h->iterate_list_tail)
685 return h->iterate_list_tail->value;
688 void* hashmap_steal_first(Hashmap *h) {
694 if (!h->iterate_list_head)
697 data = h->iterate_list_head->value;
698 remove_entry(h, h->iterate_list_head);
703 void* hashmap_steal_first_key(Hashmap *h) {
709 if (!h->iterate_list_head)
712 key = (void*) h->iterate_list_head->key;
713 remove_entry(h, h->iterate_list_head);
718 unsigned hashmap_size(Hashmap *h) {
726 bool hashmap_isempty(Hashmap *h) {
731 return h->n_entries == 0;
734 int hashmap_merge(Hashmap *h, Hashmap *other) {
735 struct hashmap_entry *e;
742 for (e = other->iterate_list_head; e; e = e->iterate_next) {
745 if ((r = hashmap_put(h, e->key, e->value)) < 0)
753 void hashmap_move(Hashmap *h, Hashmap *other) {
754 struct hashmap_entry *e, *n;
758 /* The same as hashmap_merge(), but every new item from other
759 * is moved to h. This function is guaranteed to succeed. */
764 for (e = other->iterate_list_head; e; e = n) {
765 unsigned h_hash, other_hash;
769 h_hash = h->hash_func(e->key) % NBUCKETS;
771 if (hash_scan(h, h_hash, e->key))
774 other_hash = other->hash_func(e->key) % NBUCKETS;
776 unlink_entry(other, e, other_hash);
777 link_entry(h, e, h_hash);
781 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
782 unsigned h_hash, other_hash;
783 struct hashmap_entry *e;
790 h_hash = h->hash_func(key) % NBUCKETS;
791 if (hash_scan(h, h_hash, key))
794 other_hash = other->hash_func(key) % NBUCKETS;
795 if (!(e = hash_scan(other, other_hash, key)))
798 unlink_entry(other, e, other_hash);
799 link_entry(h, e, h_hash);
804 Hashmap *hashmap_copy(Hashmap *h) {
809 if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
812 if (hashmap_merge(copy, h) < 0) {
820 char **hashmap_get_strv(Hashmap *h) {
826 sv = new(char*, h->n_entries+1);
831 HASHMAP_FOREACH(item, h, it)
838 void *hashmap_next(Hashmap *h, const void *key) {
840 struct hashmap_entry *e;
848 hash = h->hash_func(key) % NBUCKETS;
849 e = hash_scan(h, hash, key);