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) {
274 deallocate_tile(&first_hashmap_tile, h);
279 void hashmap_free_free(Hashmap *h) {
283 hashmap_clear_free(h);
287 void hashmap_clear(Hashmap *h) {
291 while (h->iterate_list_head)
292 remove_entry(h, h->iterate_list_head);
295 void hashmap_clear_free(Hashmap *h) {
301 while ((p = hashmap_steal_first(h)))
305 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
306 struct hashmap_entry *e;
308 assert(hash < NBUCKETS);
310 for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
311 if (h->compare_func(e->key, key) == 0)
317 int hashmap_put(Hashmap *h, const void *key, void *value) {
318 struct hashmap_entry *e;
323 hash = h->hash_func(key) % NBUCKETS;
325 if ((e = hash_scan(h, hash, key))) {
327 if (e->value == value)
334 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
336 e = new(struct hashmap_entry, 1);
344 link_entry(h, e, hash);
349 int hashmap_replace(Hashmap *h, const void *key, void *value) {
350 struct hashmap_entry *e;
355 hash = h->hash_func(key) % NBUCKETS;
357 if ((e = hash_scan(h, hash, key))) {
363 return hashmap_put(h, key, value);
366 void* hashmap_get(Hashmap *h, const void *key) {
368 struct hashmap_entry *e;
373 hash = h->hash_func(key) % NBUCKETS;
375 if (!(e = hash_scan(h, hash, key)))
381 void* hashmap_remove(Hashmap *h, const void *key) {
382 struct hashmap_entry *e;
389 hash = h->hash_func(key) % NBUCKETS;
391 if (!(e = hash_scan(h, hash, key)))
400 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
401 struct hashmap_entry *e;
402 unsigned old_hash, new_hash;
407 old_hash = h->hash_func(old_key) % NBUCKETS;
408 if (!(e = hash_scan(h, old_hash, old_key)))
411 new_hash = h->hash_func(new_key) % NBUCKETS;
412 if (hash_scan(h, new_hash, new_key))
415 unlink_entry(h, e, old_hash);
420 link_entry(h, e, new_hash);
425 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
426 struct hashmap_entry *e, *k;
427 unsigned old_hash, new_hash;
432 old_hash = h->hash_func(old_key) % NBUCKETS;
433 if (!(e = hash_scan(h, old_hash, old_key)))
436 new_hash = h->hash_func(new_key) % NBUCKETS;
438 if ((k = hash_scan(h, new_hash, new_key)))
442 unlink_entry(h, e, old_hash);
447 link_entry(h, e, new_hash);
452 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
453 struct hashmap_entry *e;
459 hash = h->hash_func(key) % NBUCKETS;
461 if (!(e = hash_scan(h, hash, key)))
464 if (e->value != value)
472 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
473 struct hashmap_entry *e;
480 if (*i == ITERATOR_LAST)
483 if (*i == ITERATOR_FIRST && !h->iterate_list_head)
486 e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
489 *i = (Iterator) e->iterate_next;
507 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
508 struct hashmap_entry *e;
515 if (*i == ITERATOR_FIRST)
518 if (*i == ITERATOR_LAST && !h->iterate_list_tail)
521 e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
523 if (e->iterate_previous)
524 *i = (Iterator) e->iterate_previous;
542 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
544 struct hashmap_entry *e;
549 hash = h->hash_func(key) % NBUCKETS;
551 if (!(e = hash_scan(h, hash, key)))
559 void* hashmap_first(Hashmap *h) {
564 if (!h->iterate_list_head)
567 return h->iterate_list_head->value;
570 void* hashmap_first_key(Hashmap *h) {
575 if (!h->iterate_list_head)
578 return (void*) h->iterate_list_head->key;
581 void* hashmap_last(Hashmap *h) {
586 if (!h->iterate_list_tail)
589 return h->iterate_list_tail->value;
592 void* hashmap_steal_first(Hashmap *h) {
598 if (!h->iterate_list_head)
601 data = h->iterate_list_head->value;
602 remove_entry(h, h->iterate_list_head);
607 void* hashmap_steal_first_key(Hashmap *h) {
613 if (!h->iterate_list_head)
616 key = (void*) h->iterate_list_head->key;
617 remove_entry(h, h->iterate_list_head);
622 unsigned hashmap_size(Hashmap *h) {
630 bool hashmap_isempty(Hashmap *h) {
635 return h->n_entries == 0;
638 int hashmap_merge(Hashmap *h, Hashmap *other) {
639 struct hashmap_entry *e;
646 for (e = other->iterate_list_head; e; e = e->iterate_next) {
649 if ((r = hashmap_put(h, e->key, e->value)) < 0)
657 void hashmap_move(Hashmap *h, Hashmap *other) {
658 struct hashmap_entry *e, *n;
662 /* The same as hashmap_merge(), but every new item from other
663 * is moved to h. This function is guaranteed to succeed. */
668 for (e = other->iterate_list_head; e; e = n) {
669 unsigned h_hash, other_hash;
673 h_hash = h->hash_func(e->key) % NBUCKETS;
675 if (hash_scan(h, h_hash, e->key))
678 other_hash = other->hash_func(e->key) % NBUCKETS;
680 unlink_entry(other, e, other_hash);
681 link_entry(h, e, h_hash);
685 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
686 unsigned h_hash, other_hash;
687 struct hashmap_entry *e;
694 h_hash = h->hash_func(key) % NBUCKETS;
695 if (hash_scan(h, h_hash, key))
698 other_hash = other->hash_func(key) % NBUCKETS;
699 if (!(e = hash_scan(other, other_hash, key)))
702 unlink_entry(other, e, other_hash);
703 link_entry(h, e, h_hash);
708 Hashmap *hashmap_copy(Hashmap *h) {
713 if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
716 if (hashmap_merge(copy, h) < 0) {
724 char **hashmap_get_strv(Hashmap *h) {
730 sv = new(char*, h->n_entries+1);
735 HASHMAP_FOREACH(item, h, it)