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 e = hash_scan(h, hash, key);
334 if (e->value == value)
341 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
343 e = new(struct hashmap_entry, 1);
351 link_entry(h, e, hash);
356 int hashmap_replace(Hashmap *h, const void *key, void *value) {
357 struct hashmap_entry *e;
362 hash = h->hash_func(key) % NBUCKETS;
363 e = hash_scan(h, hash, key);
370 return hashmap_put(h, key, value);
373 int hashmap_update(Hashmap *h, const void *key, void *value) {
374 struct hashmap_entry *e;
379 hash = h->hash_func(key) % NBUCKETS;
380 e = hash_scan(h, hash, key);
388 void* hashmap_get(Hashmap *h, const void *key) {
390 struct hashmap_entry *e;
395 hash = h->hash_func(key) % NBUCKETS;
396 e = hash_scan(h, hash, key);
403 void* hashmap_get2(Hashmap *h, const void *key, void **key2) {
405 struct hashmap_entry *e;
410 hash = h->hash_func(key) % NBUCKETS;
411 e = hash_scan(h, hash, key);
416 *key2 = (void*) e->key;
421 bool hashmap_contains(Hashmap *h, const void *key) {
427 hash = h->hash_func(key) % NBUCKETS;
429 if (!hash_scan(h, hash, key))
435 void* hashmap_remove(Hashmap *h, const void *key) {
436 struct hashmap_entry *e;
443 hash = h->hash_func(key) % NBUCKETS;
445 if (!(e = hash_scan(h, hash, key)))
454 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
455 struct hashmap_entry *e;
456 unsigned old_hash, new_hash;
461 old_hash = h->hash_func(old_key) % NBUCKETS;
462 if (!(e = hash_scan(h, old_hash, old_key)))
465 new_hash = h->hash_func(new_key) % NBUCKETS;
466 if (hash_scan(h, new_hash, new_key))
469 unlink_entry(h, e, old_hash);
474 link_entry(h, e, new_hash);
479 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
480 struct hashmap_entry *e, *k;
481 unsigned old_hash, new_hash;
486 old_hash = h->hash_func(old_key) % NBUCKETS;
487 if (!(e = hash_scan(h, old_hash, old_key)))
490 new_hash = h->hash_func(new_key) % NBUCKETS;
492 if ((k = hash_scan(h, new_hash, new_key)))
496 unlink_entry(h, e, old_hash);
501 link_entry(h, e, new_hash);
506 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
507 struct hashmap_entry *e;
513 hash = h->hash_func(key) % NBUCKETS;
515 if (!(e = hash_scan(h, hash, key)))
518 if (e->value != value)
526 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
527 struct hashmap_entry *e;
534 if (*i == ITERATOR_LAST)
537 if (*i == ITERATOR_FIRST && !h->iterate_list_head)
540 e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
543 *i = (Iterator) e->iterate_next;
561 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
562 struct hashmap_entry *e;
569 if (*i == ITERATOR_FIRST)
572 if (*i == ITERATOR_LAST && !h->iterate_list_tail)
575 e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
577 if (e->iterate_previous)
578 *i = (Iterator) e->iterate_previous;
596 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
598 struct hashmap_entry *e;
603 hash = h->hash_func(key) % NBUCKETS;
605 if (!(e = hash_scan(h, hash, key)))
613 void* hashmap_first(Hashmap *h) {
618 if (!h->iterate_list_head)
621 return h->iterate_list_head->value;
624 void* hashmap_first_key(Hashmap *h) {
629 if (!h->iterate_list_head)
632 return (void*) h->iterate_list_head->key;
635 void* hashmap_last(Hashmap *h) {
640 if (!h->iterate_list_tail)
643 return h->iterate_list_tail->value;
646 void* hashmap_steal_first(Hashmap *h) {
652 if (!h->iterate_list_head)
655 data = h->iterate_list_head->value;
656 remove_entry(h, h->iterate_list_head);
661 void* hashmap_steal_first_key(Hashmap *h) {
667 if (!h->iterate_list_head)
670 key = (void*) h->iterate_list_head->key;
671 remove_entry(h, h->iterate_list_head);
676 unsigned hashmap_size(Hashmap *h) {
684 bool hashmap_isempty(Hashmap *h) {
689 return h->n_entries == 0;
692 int hashmap_merge(Hashmap *h, Hashmap *other) {
693 struct hashmap_entry *e;
700 for (e = other->iterate_list_head; e; e = e->iterate_next) {
703 if ((r = hashmap_put(h, e->key, e->value)) < 0)
711 void hashmap_move(Hashmap *h, Hashmap *other) {
712 struct hashmap_entry *e, *n;
716 /* The same as hashmap_merge(), but every new item from other
717 * is moved to h. This function is guaranteed to succeed. */
722 for (e = other->iterate_list_head; e; e = n) {
723 unsigned h_hash, other_hash;
727 h_hash = h->hash_func(e->key) % NBUCKETS;
729 if (hash_scan(h, h_hash, e->key))
732 other_hash = other->hash_func(e->key) % NBUCKETS;
734 unlink_entry(other, e, other_hash);
735 link_entry(h, e, h_hash);
739 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
740 unsigned h_hash, other_hash;
741 struct hashmap_entry *e;
748 h_hash = h->hash_func(key) % NBUCKETS;
749 if (hash_scan(h, h_hash, key))
752 other_hash = other->hash_func(key) % NBUCKETS;
753 if (!(e = hash_scan(other, other_hash, key)))
756 unlink_entry(other, e, other_hash);
757 link_entry(h, e, h_hash);
762 Hashmap *hashmap_copy(Hashmap *h) {
767 if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
770 if (hashmap_merge(copy, h) < 0) {
778 char **hashmap_get_strv(Hashmap *h) {
784 sv = new(char*, h->n_entries+1);
789 HASHMAP_FOREACH(item, h, it)
796 void *hashmap_next(Hashmap *h, const void *key) {
798 struct hashmap_entry *e;
806 hash = h->hash_func(key) % NBUCKETS;
807 e = hash_scan(h, hash, key);