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/>.
31 #define INITIAL_N_BUCKETS 31
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;
46 struct hashmap_entry ** buckets;
47 unsigned n_buckets, n_entries;
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) {
67 /* When a tile is released we add it to the list and simply
68 * place the next pointer at its offset 0. */
70 assert(tile_size >= sizeof(void*));
76 *first_tile = * (void**) (*first_tile);
80 if (_unlikely_(!*first_pool) || _unlikely_((*first_pool)->n_used >= (*first_pool)->n_tiles)) {
85 n = *first_pool ? (*first_pool)->n_tiles : 0;
87 size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*tile_size);
88 n = (size - ALIGN(sizeof(struct pool))) / tile_size;
94 p->next = *first_pool;
101 i = (*first_pool)->n_used++;
103 return ((uint8_t*) (*first_pool)) + ALIGN(sizeof(struct pool)) + i*tile_size;
106 static void deallocate_tile(void **first_tile, void *p) {
107 * (void**) p = *first_tile;
113 static void drop_pool(struct pool *p) {
122 __attribute__((destructor)) static void cleanup_pool(void) {
123 /* Be nice to valgrind */
125 drop_pool(first_hashmap_pool);
126 drop_pool(first_entry_pool);
131 unsigned string_hash_func(const void *p) {
132 unsigned hash = 5381;
133 const signed char *c;
135 /* DJB's hash function */
138 hash = (hash << 5) + hash + (unsigned) *c;
143 int string_compare_func(const void *a, const void *b) {
147 unsigned trivial_hash_func(const void *p) {
148 return PTR_TO_UINT(p);
151 int trivial_compare_func(const void *a, const void *b) {
152 return a < b ? -1 : (a > b ? 1 : 0);
155 unsigned uint64_hash_func(const void *p) {
158 assert_cc(sizeof(uint64_t) == 2*sizeof(unsigned));
160 u = *(const uint64_t*) p;
162 return (unsigned) ((u >> 32) ^ u);
165 int uint64_compare_func(const void *_a, const void *_b) {
168 a = *(const uint64_t*) _a;
169 b = *(const uint64_t*) _b;
171 return a < b ? -1 : (a > b ? 1 : 0);
174 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
179 b = is_main_thread();
181 size = ALIGN(sizeof(Hashmap)) + INITIAL_N_BUCKETS * sizeof(struct hashmap_entry*);
184 h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size);
196 h->hash_func = hash_func ? hash_func : trivial_hash_func;
197 h->compare_func = compare_func ? compare_func : trivial_compare_func;
199 h->n_buckets = INITIAL_N_BUCKETS;
201 h->iterate_list_head = h->iterate_list_tail = NULL;
203 h->buckets = (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap)));
210 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
218 q = hashmap_new(hash_func, compare_func);
226 static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
230 /* Insert into hash table */
231 e->bucket_next = h->buckets[hash];
232 e->bucket_previous = NULL;
233 if (h->buckets[hash])
234 h->buckets[hash]->bucket_previous = e;
235 h->buckets[hash] = e;
237 /* Insert into iteration list */
238 e->iterate_previous = h->iterate_list_tail;
239 e->iterate_next = NULL;
240 if (h->iterate_list_tail) {
241 assert(h->iterate_list_head);
242 h->iterate_list_tail->iterate_next = e;
244 assert(!h->iterate_list_head);
245 h->iterate_list_head = e;
247 h->iterate_list_tail = e;
250 assert(h->n_entries >= 1);
253 static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
257 /* Remove from iteration list */
259 e->iterate_next->iterate_previous = e->iterate_previous;
261 h->iterate_list_tail = e->iterate_previous;
263 if (e->iterate_previous)
264 e->iterate_previous->iterate_next = e->iterate_next;
266 h->iterate_list_head = e->iterate_next;
268 /* Remove from hash table bucket list */
270 e->bucket_next->bucket_previous = e->bucket_previous;
272 if (e->bucket_previous)
273 e->bucket_previous->bucket_next = e->bucket_next;
275 h->buckets[hash] = e->bucket_next;
277 assert(h->n_entries >= 1);
281 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
287 hash = h->hash_func(e->key) % h->n_buckets;
289 unlink_entry(h, e, hash);
292 deallocate_tile(&first_entry_tile, e);
297 void hashmap_free(Hashmap*h) {
299 /* Free the hashmap, but nothing in it */
306 if (h->buckets != (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap))))
310 deallocate_tile(&first_hashmap_tile, h);
315 void hashmap_free_free(Hashmap *h) {
317 /* Free the hashmap and all data objects in it, but not the
323 hashmap_clear_free(h);
327 void hashmap_free_free_free(Hashmap *h) {
329 /* Free the hashmap and all data and key objects in it */
334 hashmap_clear_free_free(h);
338 void hashmap_clear(Hashmap *h) {
342 while (h->iterate_list_head)
343 remove_entry(h, h->iterate_list_head);
346 void hashmap_clear_free(Hashmap *h) {
352 while ((p = hashmap_steal_first(h)))
356 void hashmap_clear_free_free(Hashmap *h) {
360 while (h->iterate_list_head) {
363 a = h->iterate_list_head->value;
364 b = (void*) h->iterate_list_head->key;
365 remove_entry(h, h->iterate_list_head);
372 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
373 struct hashmap_entry *e;
375 assert(hash < h->n_buckets);
377 for (e = h->buckets[hash]; e; e = e->bucket_next)
378 if (h->compare_func(e->key, key) == 0)
384 static bool resize_buckets(Hashmap *h) {
386 struct hashmap_entry **n, *i;
390 if (_likely_(h->n_entries*4 < h->n_buckets*3))
393 /* Increase by four */
394 m = (h->n_entries+1)*4-1;
396 /* If we hit OOM we simply risk packed hashmaps... */
397 n = new0(struct hashmap_entry*, m);
401 for (i = h->iterate_list_head; i; i = i->iterate_next) {
404 hash = h->hash_func(i->key);
406 /* First, drop from old bucket table */
408 i->bucket_next->bucket_previous = i->bucket_previous;
410 if (i->bucket_previous)
411 i->bucket_previous->bucket_next = i->bucket_next;
413 h->buckets[hash % h->n_buckets] = i->bucket_next;
415 /* Then, add to new backet table */
418 i->bucket_next = n[x];
419 i->bucket_previous = NULL;
421 n[x]->bucket_previous = i;
425 if (h->buckets != (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap))))
434 int hashmap_put(Hashmap *h, const void *key, void *value) {
435 struct hashmap_entry *e;
440 hash = h->hash_func(key) % h->n_buckets;
441 e = hash_scan(h, hash, key);
443 if (e->value == value)
448 if (resize_buckets(h))
449 hash = h->hash_func(key) % h->n_buckets;
452 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
454 e = new(struct hashmap_entry, 1);
462 link_entry(h, e, hash);
467 int hashmap_replace(Hashmap *h, const void *key, void *value) {
468 struct hashmap_entry *e;
473 hash = h->hash_func(key) % h->n_buckets;
474 e = hash_scan(h, hash, key);
481 return hashmap_put(h, key, value);
484 int hashmap_update(Hashmap *h, const void *key, void *value) {
485 struct hashmap_entry *e;
490 hash = h->hash_func(key) % h->n_buckets;
491 e = hash_scan(h, hash, key);
499 void* hashmap_get(Hashmap *h, const void *key) {
501 struct hashmap_entry *e;
506 hash = h->hash_func(key) % h->n_buckets;
507 e = hash_scan(h, hash, key);
514 void* hashmap_get2(Hashmap *h, const void *key, void **key2) {
516 struct hashmap_entry *e;
521 hash = h->hash_func(key) % h->n_buckets;
522 e = hash_scan(h, hash, key);
527 *key2 = (void*) e->key;
532 bool hashmap_contains(Hashmap *h, const void *key) {
538 hash = h->hash_func(key) % h->n_buckets;
540 if (!hash_scan(h, hash, key))
546 void* hashmap_remove(Hashmap *h, const void *key) {
547 struct hashmap_entry *e;
554 hash = h->hash_func(key) % h->n_buckets;
556 if (!(e = hash_scan(h, hash, key)))
565 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
566 struct hashmap_entry *e;
567 unsigned old_hash, new_hash;
572 old_hash = h->hash_func(old_key) % h->n_buckets;
573 if (!(e = hash_scan(h, old_hash, old_key)))
576 new_hash = h->hash_func(new_key) % h->n_buckets;
577 if (hash_scan(h, new_hash, new_key))
580 unlink_entry(h, e, old_hash);
585 link_entry(h, e, new_hash);
590 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
591 struct hashmap_entry *e, *k;
592 unsigned old_hash, new_hash;
597 old_hash = h->hash_func(old_key) % h->n_buckets;
598 if (!(e = hash_scan(h, old_hash, old_key)))
601 new_hash = h->hash_func(new_key) % h->n_buckets;
602 if ((k = hash_scan(h, new_hash, new_key)))
606 unlink_entry(h, e, old_hash);
611 link_entry(h, e, new_hash);
616 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
617 struct hashmap_entry *e;
623 hash = h->hash_func(key) % h->n_buckets;
625 e = hash_scan(h, hash, key);
629 if (e->value != value)
637 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
638 struct hashmap_entry *e;
645 if (*i == ITERATOR_LAST)
648 if (*i == ITERATOR_FIRST && !h->iterate_list_head)
651 e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
654 *i = (Iterator) e->iterate_next;
672 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
673 struct hashmap_entry *e;
680 if (*i == ITERATOR_FIRST)
683 if (*i == ITERATOR_LAST && !h->iterate_list_tail)
686 e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
688 if (e->iterate_previous)
689 *i = (Iterator) e->iterate_previous;
707 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
709 struct hashmap_entry *e;
714 hash = h->hash_func(key) % h->n_buckets;
716 e = hash_scan(h, hash, key);
725 void* hashmap_first(Hashmap *h) {
730 if (!h->iterate_list_head)
733 return h->iterate_list_head->value;
736 void* hashmap_first_key(Hashmap *h) {
741 if (!h->iterate_list_head)
744 return (void*) h->iterate_list_head->key;
747 void* hashmap_last(Hashmap *h) {
752 if (!h->iterate_list_tail)
755 return h->iterate_list_tail->value;
758 void* hashmap_steal_first(Hashmap *h) {
764 if (!h->iterate_list_head)
767 data = h->iterate_list_head->value;
768 remove_entry(h, h->iterate_list_head);
773 void* hashmap_steal_first_key(Hashmap *h) {
779 if (!h->iterate_list_head)
782 key = (void*) h->iterate_list_head->key;
783 remove_entry(h, h->iterate_list_head);
788 unsigned hashmap_size(Hashmap *h) {
796 unsigned hashmap_buckets(Hashmap *h) {
804 bool hashmap_isempty(Hashmap *h) {
809 return h->n_entries == 0;
812 int hashmap_merge(Hashmap *h, Hashmap *other) {
813 struct hashmap_entry *e;
820 for (e = other->iterate_list_head; e; e = e->iterate_next) {
823 if ((r = hashmap_put(h, e->key, e->value)) < 0)
831 void hashmap_move(Hashmap *h, Hashmap *other) {
832 struct hashmap_entry *e, *n;
836 /* The same as hashmap_merge(), but every new item from other
837 * is moved to h. This function is guaranteed to succeed. */
842 for (e = other->iterate_list_head; e; e = n) {
843 unsigned h_hash, other_hash;
847 h_hash = h->hash_func(e->key) % h->n_buckets;
849 if (hash_scan(h, h_hash, e->key))
852 other_hash = other->hash_func(e->key) % other->n_buckets;
854 unlink_entry(other, e, other_hash);
855 link_entry(h, e, h_hash);
859 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
860 unsigned h_hash, other_hash;
861 struct hashmap_entry *e;
868 h_hash = h->hash_func(key) % h->n_buckets;
869 if (hash_scan(h, h_hash, key))
872 other_hash = other->hash_func(key) % other->n_buckets;
873 e = hash_scan(other, other_hash, key);
877 unlink_entry(other, e, other_hash);
878 link_entry(h, e, h_hash);
883 Hashmap *hashmap_copy(Hashmap *h) {
888 copy = hashmap_new(h->hash_func, h->compare_func);
892 if (hashmap_merge(copy, h) < 0) {
900 char **hashmap_get_strv(Hashmap *h) {
906 sv = new(char*, h->n_entries+1);
911 HASHMAP_FOREACH(item, h, it)
918 void *hashmap_next(Hashmap *h, const void *key) {
920 struct hashmap_entry *e;
928 hash = h->hash_func(key) % h->n_buckets;
929 e = hash_scan(h, hash, key);