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_clear(Hashmap *h) {
316 while (h->iterate_list_head)
317 remove_entry(h, h->iterate_list_head);
320 void hashmap_clear_free(Hashmap *h) {
326 while ((p = hashmap_steal_first(h)))
330 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
331 struct hashmap_entry *e;
333 assert(hash < NBUCKETS);
335 for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
336 if (h->compare_func(e->key, key) == 0)
342 int hashmap_put(Hashmap *h, const void *key, void *value) {
343 struct hashmap_entry *e;
348 hash = h->hash_func(key) % NBUCKETS;
350 e = hash_scan(h, hash, key);
353 if (e->value == value)
360 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
362 e = new(struct hashmap_entry, 1);
370 link_entry(h, e, hash);
375 int hashmap_replace(Hashmap *h, const void *key, void *value) {
376 struct hashmap_entry *e;
381 hash = h->hash_func(key) % NBUCKETS;
382 e = hash_scan(h, hash, key);
389 return hashmap_put(h, key, value);
392 int hashmap_update(Hashmap *h, const void *key, void *value) {
393 struct hashmap_entry *e;
398 hash = h->hash_func(key) % NBUCKETS;
399 e = hash_scan(h, hash, key);
407 void* hashmap_get(Hashmap *h, const void *key) {
409 struct hashmap_entry *e;
414 hash = h->hash_func(key) % NBUCKETS;
415 e = hash_scan(h, hash, key);
422 void* hashmap_get2(Hashmap *h, const void *key, void **key2) {
424 struct hashmap_entry *e;
429 hash = h->hash_func(key) % NBUCKETS;
430 e = hash_scan(h, hash, key);
435 *key2 = (void*) e->key;
440 bool hashmap_contains(Hashmap *h, const void *key) {
446 hash = h->hash_func(key) % NBUCKETS;
448 if (!hash_scan(h, hash, key))
454 void* hashmap_remove(Hashmap *h, const void *key) {
455 struct hashmap_entry *e;
462 hash = h->hash_func(key) % NBUCKETS;
464 if (!(e = hash_scan(h, hash, key)))
473 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
474 struct hashmap_entry *e;
475 unsigned old_hash, new_hash;
480 old_hash = h->hash_func(old_key) % NBUCKETS;
481 if (!(e = hash_scan(h, old_hash, old_key)))
484 new_hash = h->hash_func(new_key) % NBUCKETS;
485 if (hash_scan(h, new_hash, new_key))
488 unlink_entry(h, e, old_hash);
493 link_entry(h, e, new_hash);
498 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
499 struct hashmap_entry *e, *k;
500 unsigned old_hash, new_hash;
505 old_hash = h->hash_func(old_key) % NBUCKETS;
506 if (!(e = hash_scan(h, old_hash, old_key)))
509 new_hash = h->hash_func(new_key) % NBUCKETS;
511 if ((k = hash_scan(h, new_hash, new_key)))
515 unlink_entry(h, e, old_hash);
520 link_entry(h, e, new_hash);
525 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
526 struct hashmap_entry *e;
532 hash = h->hash_func(key) % NBUCKETS;
534 if (!(e = hash_scan(h, hash, key)))
537 if (e->value != value)
545 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
546 struct hashmap_entry *e;
553 if (*i == ITERATOR_LAST)
556 if (*i == ITERATOR_FIRST && !h->iterate_list_head)
559 e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
562 *i = (Iterator) e->iterate_next;
580 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
581 struct hashmap_entry *e;
588 if (*i == ITERATOR_FIRST)
591 if (*i == ITERATOR_LAST && !h->iterate_list_tail)
594 e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
596 if (e->iterate_previous)
597 *i = (Iterator) e->iterate_previous;
615 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
617 struct hashmap_entry *e;
622 hash = h->hash_func(key) % NBUCKETS;
624 if (!(e = hash_scan(h, hash, key)))
632 void* hashmap_first(Hashmap *h) {
637 if (!h->iterate_list_head)
640 return h->iterate_list_head->value;
643 void* hashmap_first_key(Hashmap *h) {
648 if (!h->iterate_list_head)
651 return (void*) h->iterate_list_head->key;
654 void* hashmap_last(Hashmap *h) {
659 if (!h->iterate_list_tail)
662 return h->iterate_list_tail->value;
665 void* hashmap_steal_first(Hashmap *h) {
671 if (!h->iterate_list_head)
674 data = h->iterate_list_head->value;
675 remove_entry(h, h->iterate_list_head);
680 void* hashmap_steal_first_key(Hashmap *h) {
686 if (!h->iterate_list_head)
689 key = (void*) h->iterate_list_head->key;
690 remove_entry(h, h->iterate_list_head);
695 unsigned hashmap_size(Hashmap *h) {
703 bool hashmap_isempty(Hashmap *h) {
708 return h->n_entries == 0;
711 int hashmap_merge(Hashmap *h, Hashmap *other) {
712 struct hashmap_entry *e;
719 for (e = other->iterate_list_head; e; e = e->iterate_next) {
722 if ((r = hashmap_put(h, e->key, e->value)) < 0)
730 void hashmap_move(Hashmap *h, Hashmap *other) {
731 struct hashmap_entry *e, *n;
735 /* The same as hashmap_merge(), but every new item from other
736 * is moved to h. This function is guaranteed to succeed. */
741 for (e = other->iterate_list_head; e; e = n) {
742 unsigned h_hash, other_hash;
746 h_hash = h->hash_func(e->key) % NBUCKETS;
748 if (hash_scan(h, h_hash, e->key))
751 other_hash = other->hash_func(e->key) % NBUCKETS;
753 unlink_entry(other, e, other_hash);
754 link_entry(h, e, h_hash);
758 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
759 unsigned h_hash, other_hash;
760 struct hashmap_entry *e;
767 h_hash = h->hash_func(key) % NBUCKETS;
768 if (hash_scan(h, h_hash, key))
771 other_hash = other->hash_func(key) % NBUCKETS;
772 if (!(e = hash_scan(other, other_hash, key)))
775 unlink_entry(other, e, other_hash);
776 link_entry(h, e, h_hash);
781 Hashmap *hashmap_copy(Hashmap *h) {
786 if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
789 if (hashmap_merge(copy, h) < 0) {
797 char **hashmap_get_strv(Hashmap *h) {
803 sv = new(char*, h->n_entries+1);
808 HASHMAP_FOREACH(item, h, it)
815 void *hashmap_next(Hashmap *h, const void *key) {
817 struct hashmap_entry *e;
825 hash = h->hash_func(key) % NBUCKETS;
826 e = hash_scan(h, hash, key);