1 /* SPDX-License-Identifier: LGPL-2.1+ */
3 Copyright 2010 Lennart Poettering
4 Copyright 2014 Michal Schmidt
12 #include "alloc-util.h"
17 #include "process-util.h"
18 #include "random-util.h"
20 #include "siphash24.h"
21 #include "string-util.h"
25 #if ENABLE_DEBUG_HASHMAP
31 * Implementation of hashmaps.
33 * - uses less RAM compared to closed addressing (chaining), because
34 * our entries are small (especially in Sets, which tend to contain
35 * the majority of entries in systemd).
36 * Collision resolution: Robin Hood
37 * - tends to equalize displacement of entries from their optimal buckets.
38 * Probe sequence: linear
39 * - though theoretically worse than random probing/uniform hashing/double
40 * hashing, it is good for cache locality.
43 * Celis, P. 1986. Robin Hood Hashing.
44 * Ph.D. Dissertation. University of Waterloo, Waterloo, Ont., Canada, Canada.
45 * https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
46 * - The results are derived for random probing. Suggests deletion with
47 * tombstones and two mean-centered search methods. None of that works
48 * well for linear probing.
50 * Janson, S. 2005. Individual displacements for linear probing hashing with different insertion policies.
51 * ACM Trans. Algorithms 1, 2 (October 2005), 177-213.
52 * DOI=10.1145/1103963.1103964 http://doi.acm.org/10.1145/1103963.1103964
53 * http://www.math.uu.se/~svante/papers/sj157.pdf
54 * - Applies to Robin Hood with linear probing. Contains remarks on
55 * the unsuitability of mean-centered search with linear probing.
57 * Viola, A. 2005. Exact distribution of individual displacements in linear probing hashing.
58 * ACM Trans. Algorithms 1, 2 (October 2005), 214-242.
59 * DOI=10.1145/1103963.1103965 http://doi.acm.org/10.1145/1103963.1103965
60 * - Similar to Janson. Note that Viola writes about C_{m,n} (number of probes
61 * in a successful search), and Janson writes about displacement. C = d + 1.
63 * Goossaert, E. 2013. Robin Hood hashing: backward shift deletion.
64 * http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
65 * - Explanation of backward shift deletion with pictures.
67 * Khuong, P. 2013. The Other Robin Hood Hashing.
68 * http://www.pvk.ca/Blog/2013/11/26/the-other-robin-hood-hashing/
69 * - Short summary of random vs. linear probing, and tombstones vs. backward shift.
73 * XXX Ideas for improvement:
74 * For unordered hashmaps, randomize iteration order, similarly to Perl:
75 * http://blog.booking.com/hardening-perls-hash-function.html
78 /* INV_KEEP_FREE = 1 / (1 - max_load_factor)
79 * e.g. 1 / (1 - 0.8) = 5 ... keep one fifth of the buckets free. */
80 #define INV_KEEP_FREE 5U
82 /* Fields common to entries of all hashmap/set types */
83 struct hashmap_base_entry {
87 /* Entry types for specific hashmap/set types
88 * hashmap_base_entry must be at the beginning of each entry struct. */
90 struct plain_hashmap_entry {
91 struct hashmap_base_entry b;
95 struct ordered_hashmap_entry {
96 struct plain_hashmap_entry p;
97 unsigned iterate_next, iterate_previous;
101 struct hashmap_base_entry b;
104 /* In several functions it is advantageous to have the hash table extended
105 * virtually by a couple of additional buckets. We reserve special index values
106 * for these "swap" buckets. */
107 #define _IDX_SWAP_BEGIN (UINT_MAX - 3)
108 #define IDX_PUT (_IDX_SWAP_BEGIN + 0)
109 #define IDX_TMP (_IDX_SWAP_BEGIN + 1)
110 #define _IDX_SWAP_END (_IDX_SWAP_BEGIN + 2)
112 #define IDX_FIRST (UINT_MAX - 1) /* special index for freshly initialized iterators */
113 #define IDX_NIL UINT_MAX /* special index value meaning "none" or "end" */
115 assert_cc(IDX_FIRST == _IDX_SWAP_END);
116 assert_cc(IDX_FIRST == _IDX_ITERATOR_FIRST);
118 /* Storage space for the "swap" buckets.
119 * All entry types can fit into a ordered_hashmap_entry. */
120 struct swap_entries {
121 struct ordered_hashmap_entry e[_IDX_SWAP_END - _IDX_SWAP_BEGIN];
124 /* Distance from Initial Bucket */
125 typedef uint8_t dib_raw_t;
126 #define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */
127 #define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */
128 #define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */
129 #define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */
131 #define DIB_FREE UINT_MAX
133 #if ENABLE_DEBUG_HASHMAP
134 struct hashmap_debug_info {
135 LIST_FIELDS(struct hashmap_debug_info, debug_list);
136 unsigned max_entries; /* high watermark of n_entries */
138 /* who allocated this hashmap */
143 /* fields to detect modification while iterating */
144 unsigned put_count; /* counts puts into the hashmap */
145 unsigned rem_count; /* counts removals from hashmap */
146 unsigned last_rem_idx; /* remembers last removal index */
149 /* Tracks all existing hashmaps. Get at it from gdb. See sd_dump_hashmaps.py */
150 static LIST_HEAD(struct hashmap_debug_info, hashmap_debug_list);
151 static pthread_mutex_t hashmap_debug_list_mutex = PTHREAD_MUTEX_INITIALIZER;
153 #define HASHMAP_DEBUG_FIELDS struct hashmap_debug_info debug;
155 #else /* !ENABLE_DEBUG_HASHMAP */
156 #define HASHMAP_DEBUG_FIELDS
157 #endif /* ENABLE_DEBUG_HASHMAP */
161 HASHMAP_TYPE_ORDERED,
166 struct _packed_ indirect_storage {
167 void *storage; /* where buckets and DIBs are stored */
168 uint8_t hash_key[HASH_KEY_SIZE]; /* hash key; changes during resize */
170 unsigned n_entries; /* number of stored entries */
171 unsigned n_buckets; /* number of buckets */
173 unsigned idx_lowest_entry; /* Index below which all buckets are free.
174 Makes "while(hashmap_steal_first())" loops
175 O(n) instead of O(n^2) for unordered hashmaps. */
176 uint8_t _pad[3]; /* padding for the whole HashmapBase */
177 /* The bitfields in HashmapBase complete the alignment of the whole thing. */
180 struct direct_storage {
181 /* This gives us 39 bytes on 64bit, or 35 bytes on 32bit.
182 * That's room for 4 set_entries + 4 DIB bytes + 3 unused bytes on 64bit,
183 * or 7 set_entries + 7 DIB bytes + 0 unused bytes on 32bit. */
184 uint8_t storage[sizeof(struct indirect_storage)];
187 #define DIRECT_BUCKETS(entry_t) \
188 (sizeof(struct direct_storage) / (sizeof(entry_t) + sizeof(dib_raw_t)))
190 /* We should be able to store at least one entry directly. */
191 assert_cc(DIRECT_BUCKETS(struct ordered_hashmap_entry) >= 1);
193 /* We have 3 bits for n_direct_entries. */
194 assert_cc(DIRECT_BUCKETS(struct set_entry) < (1 << 3));
196 /* Hashmaps with directly stored entries all use this shared hash key.
197 * It's no big deal if the key is guessed, because there can be only
198 * a handful of directly stored entries in a hashmap. When a hashmap
199 * outgrows direct storage, it gets its own key for indirect storage. */
200 static uint8_t shared_hash_key[HASH_KEY_SIZE];
201 static bool shared_hash_key_initialized;
203 /* Fields that all hashmap/set types must have */
205 const struct hash_ops *hash_ops; /* hash and compare ops to use */
208 struct indirect_storage indirect; /* if has_indirect */
209 struct direct_storage direct; /* if !has_indirect */
212 enum HashmapType type:2; /* HASHMAP_TYPE_* */
213 bool has_indirect:1; /* whether indirect storage is used */
214 unsigned n_direct_entries:3; /* Number of entries in direct storage.
215 * Only valid if !has_indirect. */
216 bool from_pool:1; /* whether was allocated from mempool */
217 bool dirty:1; /* whether dirtied since last iterated_cache_get() */
218 bool cached:1; /* whether this hashmap is being cached */
219 HASHMAP_DEBUG_FIELDS /* optional hashmap_debug_info */
222 /* Specific hash types
223 * HashmapBase must be at the beginning of each hashmap struct. */
226 struct HashmapBase b;
229 struct OrderedHashmap {
230 struct HashmapBase b;
231 unsigned iterate_list_head, iterate_list_tail;
235 struct HashmapBase b;
238 typedef struct CacheMem {
240 size_t n_populated, n_allocated;
244 struct IteratedCache {
245 HashmapBase *hashmap;
246 CacheMem keys, values;
249 DEFINE_MEMPOOL(hashmap_pool, Hashmap, 8);
250 DEFINE_MEMPOOL(ordered_hashmap_pool, OrderedHashmap, 8);
251 /* No need for a separate Set pool */
252 assert_cc(sizeof(Hashmap) == sizeof(Set));
254 struct hashmap_type_info {
257 struct mempool *mempool;
258 unsigned n_direct_buckets;
261 static const struct hashmap_type_info hashmap_type_info[_HASHMAP_TYPE_MAX] = {
262 [HASHMAP_TYPE_PLAIN] = {
263 .head_size = sizeof(Hashmap),
264 .entry_size = sizeof(struct plain_hashmap_entry),
265 .mempool = &hashmap_pool,
266 .n_direct_buckets = DIRECT_BUCKETS(struct plain_hashmap_entry),
268 [HASHMAP_TYPE_ORDERED] = {
269 .head_size = sizeof(OrderedHashmap),
270 .entry_size = sizeof(struct ordered_hashmap_entry),
271 .mempool = &ordered_hashmap_pool,
272 .n_direct_buckets = DIRECT_BUCKETS(struct ordered_hashmap_entry),
274 [HASHMAP_TYPE_SET] = {
275 .head_size = sizeof(Set),
276 .entry_size = sizeof(struct set_entry),
277 .mempool = &hashmap_pool,
278 .n_direct_buckets = DIRECT_BUCKETS(struct set_entry),
283 __attribute__((destructor)) static void cleanup_pools(void) {
284 _cleanup_free_ char *t = NULL;
287 /* Be nice to valgrind */
289 /* The pool is only allocated by the main thread, but the memory can
290 * be passed to other threads. Let's clean up if we are the main thread
291 * and no other threads are live. */
292 if (!is_main_thread())
295 r = get_proc_field("/proc/self/status", "Threads", WHITESPACE, &t);
296 if (r < 0 || !streq(t, "1"))
299 mempool_drop(&hashmap_pool);
300 mempool_drop(&ordered_hashmap_pool);
304 static unsigned n_buckets(HashmapBase *h) {
305 return h->has_indirect ? h->indirect.n_buckets
306 : hashmap_type_info[h->type].n_direct_buckets;
309 static unsigned n_entries(HashmapBase *h) {
310 return h->has_indirect ? h->indirect.n_entries
311 : h->n_direct_entries;
314 static void n_entries_inc(HashmapBase *h) {
316 h->indirect.n_entries++;
318 h->n_direct_entries++;
321 static void n_entries_dec(HashmapBase *h) {
323 h->indirect.n_entries--;
325 h->n_direct_entries--;
328 static void *storage_ptr(HashmapBase *h) {
329 return h->has_indirect ? h->indirect.storage
333 static uint8_t *hash_key(HashmapBase *h) {
334 return h->has_indirect ? h->indirect.hash_key
338 static unsigned base_bucket_hash(HashmapBase *h, const void *p) {
339 struct siphash state;
342 siphash24_init(&state, hash_key(h));
344 h->hash_ops->hash(p, &state);
346 hash = siphash24_finalize(&state);
348 return (unsigned) (hash % n_buckets(h));
350 #define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p)
352 static inline void base_set_dirty(HashmapBase *h) {
355 #define hashmap_set_dirty(h) base_set_dirty(HASHMAP_BASE(h))
357 static void get_hash_key(uint8_t hash_key[HASH_KEY_SIZE], bool reuse_is_ok) {
358 static uint8_t current[HASH_KEY_SIZE];
359 static bool current_initialized = false;
361 /* Returns a hash function key to use. In order to keep things
362 * fast we will not generate a new key each time we allocate a
363 * new hash table. Instead, we'll just reuse the most recently
364 * generated one, except if we never generated one or when we
365 * are rehashing an entire hash table because we reached a
368 if (!current_initialized || !reuse_is_ok) {
369 random_bytes(current, sizeof(current));
370 current_initialized = true;
373 memcpy(hash_key, current, sizeof(current));
376 static struct hashmap_base_entry *bucket_at(HashmapBase *h, unsigned idx) {
377 return (struct hashmap_base_entry*)
378 ((uint8_t*) storage_ptr(h) + idx * hashmap_type_info[h->type].entry_size);
381 static struct plain_hashmap_entry *plain_bucket_at(Hashmap *h, unsigned idx) {
382 return (struct plain_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
385 static struct ordered_hashmap_entry *ordered_bucket_at(OrderedHashmap *h, unsigned idx) {
386 return (struct ordered_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
389 static struct set_entry *set_bucket_at(Set *h, unsigned idx) {
390 return (struct set_entry*) bucket_at(HASHMAP_BASE(h), idx);
393 static struct ordered_hashmap_entry *bucket_at_swap(struct swap_entries *swap, unsigned idx) {
394 return &swap->e[idx - _IDX_SWAP_BEGIN];
397 /* Returns a pointer to the bucket at index idx.
398 * Understands real indexes and swap indexes, hence "_virtual". */
399 static struct hashmap_base_entry *bucket_at_virtual(HashmapBase *h, struct swap_entries *swap,
401 if (idx < _IDX_SWAP_BEGIN)
402 return bucket_at(h, idx);
404 if (idx < _IDX_SWAP_END)
405 return &bucket_at_swap(swap, idx)->p.b;
407 assert_not_reached("Invalid index");
410 static dib_raw_t *dib_raw_ptr(HashmapBase *h) {
412 ((uint8_t*) storage_ptr(h) + hashmap_type_info[h->type].entry_size * n_buckets(h));
415 static unsigned bucket_distance(HashmapBase *h, unsigned idx, unsigned from) {
416 return idx >= from ? idx - from
417 : n_buckets(h) + idx - from;
420 static unsigned bucket_calculate_dib(HashmapBase *h, unsigned idx, dib_raw_t raw_dib) {
421 unsigned initial_bucket;
423 if (raw_dib == DIB_RAW_FREE)
426 if (_likely_(raw_dib < DIB_RAW_OVERFLOW))
430 * Having an overflow DIB value is very unlikely. The hash function
431 * would have to be bad. For example, in a table of size 2^24 filled
432 * to load factor 0.9 the maximum observed DIB is only about 60.
433 * In theory (assuming I used Maxima correctly), for an infinite size
434 * hash table with load factor 0.8 the probability of a given entry
435 * having DIB > 40 is 1.9e-8.
436 * This returns the correct DIB value by recomputing the hash value in
437 * the unlikely case. XXX Hitting this case could be a hint to rehash.
439 initial_bucket = bucket_hash(h, bucket_at(h, idx)->key);
440 return bucket_distance(h, idx, initial_bucket);
443 static void bucket_set_dib(HashmapBase *h, unsigned idx, unsigned dib) {
444 dib_raw_ptr(h)[idx] = dib != DIB_FREE ? MIN(dib, DIB_RAW_OVERFLOW) : DIB_RAW_FREE;
447 static unsigned skip_free_buckets(HashmapBase *h, unsigned idx) {
450 dibs = dib_raw_ptr(h);
452 for ( ; idx < n_buckets(h); idx++)
453 if (dibs[idx] != DIB_RAW_FREE)
459 static void bucket_mark_free(HashmapBase *h, unsigned idx) {
460 memzero(bucket_at(h, idx), hashmap_type_info[h->type].entry_size);
461 bucket_set_dib(h, idx, DIB_FREE);
464 static void bucket_move_entry(HashmapBase *h, struct swap_entries *swap,
465 unsigned from, unsigned to) {
466 struct hashmap_base_entry *e_from, *e_to;
470 e_from = bucket_at_virtual(h, swap, from);
471 e_to = bucket_at_virtual(h, swap, to);
473 memcpy(e_to, e_from, hashmap_type_info[h->type].entry_size);
475 if (h->type == HASHMAP_TYPE_ORDERED) {
476 OrderedHashmap *lh = (OrderedHashmap*) h;
477 struct ordered_hashmap_entry *le, *le_to;
479 le_to = (struct ordered_hashmap_entry*) e_to;
481 if (le_to->iterate_next != IDX_NIL) {
482 le = (struct ordered_hashmap_entry*)
483 bucket_at_virtual(h, swap, le_to->iterate_next);
484 le->iterate_previous = to;
487 if (le_to->iterate_previous != IDX_NIL) {
488 le = (struct ordered_hashmap_entry*)
489 bucket_at_virtual(h, swap, le_to->iterate_previous);
490 le->iterate_next = to;
493 if (lh->iterate_list_head == from)
494 lh->iterate_list_head = to;
495 if (lh->iterate_list_tail == from)
496 lh->iterate_list_tail = to;
500 static unsigned next_idx(HashmapBase *h, unsigned idx) {
501 return (idx + 1U) % n_buckets(h);
504 static unsigned prev_idx(HashmapBase *h, unsigned idx) {
505 return (n_buckets(h) + idx - 1U) % n_buckets(h);
508 static void *entry_value(HashmapBase *h, struct hashmap_base_entry *e) {
511 case HASHMAP_TYPE_PLAIN:
512 case HASHMAP_TYPE_ORDERED:
513 return ((struct plain_hashmap_entry*)e)->value;
515 case HASHMAP_TYPE_SET:
516 return (void*) e->key;
519 assert_not_reached("Unknown hashmap type");
523 static void base_remove_entry(HashmapBase *h, unsigned idx) {
524 unsigned left, right, prev, dib;
525 dib_raw_t raw_dib, *dibs;
527 dibs = dib_raw_ptr(h);
528 assert(dibs[idx] != DIB_RAW_FREE);
530 #if ENABLE_DEBUG_HASHMAP
531 h->debug.rem_count++;
532 h->debug.last_rem_idx = idx;
536 /* Find the stop bucket ("right"). It is either free or has DIB == 0. */
537 for (right = next_idx(h, left); ; right = next_idx(h, right)) {
538 raw_dib = dibs[right];
539 if (IN_SET(raw_dib, 0, DIB_RAW_FREE))
542 /* The buckets are not supposed to be all occupied and with DIB > 0.
543 * That would mean we could make everyone better off by shifting them
544 * backward. This scenario is impossible. */
545 assert(left != right);
548 if (h->type == HASHMAP_TYPE_ORDERED) {
549 OrderedHashmap *lh = (OrderedHashmap*) h;
550 struct ordered_hashmap_entry *le = ordered_bucket_at(lh, idx);
552 if (le->iterate_next != IDX_NIL)
553 ordered_bucket_at(lh, le->iterate_next)->iterate_previous = le->iterate_previous;
555 lh->iterate_list_tail = le->iterate_previous;
557 if (le->iterate_previous != IDX_NIL)
558 ordered_bucket_at(lh, le->iterate_previous)->iterate_next = le->iterate_next;
560 lh->iterate_list_head = le->iterate_next;
563 /* Now shift all buckets in the interval (left, right) one step backwards */
564 for (prev = left, left = next_idx(h, left); left != right;
565 prev = left, left = next_idx(h, left)) {
566 dib = bucket_calculate_dib(h, left, dibs[left]);
568 bucket_move_entry(h, NULL, left, prev);
569 bucket_set_dib(h, prev, dib - 1);
572 bucket_mark_free(h, prev);
576 #define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)
578 static unsigned hashmap_iterate_in_insertion_order(OrderedHashmap *h, Iterator *i) {
579 struct ordered_hashmap_entry *e;
585 if (i->idx == IDX_NIL)
588 if (i->idx == IDX_FIRST && h->iterate_list_head == IDX_NIL)
591 if (i->idx == IDX_FIRST) {
592 idx = h->iterate_list_head;
593 e = ordered_bucket_at(h, idx);
596 e = ordered_bucket_at(h, idx);
598 * We allow removing the current entry while iterating, but removal may cause
599 * a backward shift. The next entry may thus move one bucket to the left.
600 * To detect when it happens, we remember the key pointer of the entry we were
601 * going to iterate next. If it does not match, there was a backward shift.
603 if (e->p.b.key != i->next_key) {
604 idx = prev_idx(HASHMAP_BASE(h), idx);
605 e = ordered_bucket_at(h, idx);
607 assert(e->p.b.key == i->next_key);
610 #if ENABLE_DEBUG_HASHMAP
614 if (e->iterate_next != IDX_NIL) {
615 struct ordered_hashmap_entry *n;
616 i->idx = e->iterate_next;
617 n = ordered_bucket_at(h, i->idx);
618 i->next_key = n->p.b.key;
629 static unsigned hashmap_iterate_in_internal_order(HashmapBase *h, Iterator *i) {
635 if (i->idx == IDX_NIL)
638 if (i->idx == IDX_FIRST) {
639 /* fast forward to the first occupied bucket */
640 if (h->has_indirect) {
641 i->idx = skip_free_buckets(h, h->indirect.idx_lowest_entry);
642 h->indirect.idx_lowest_entry = i->idx;
644 i->idx = skip_free_buckets(h, 0);
646 if (i->idx == IDX_NIL)
649 struct hashmap_base_entry *e;
653 e = bucket_at(h, i->idx);
655 * We allow removing the current entry while iterating, but removal may cause
656 * a backward shift. The next entry may thus move one bucket to the left.
657 * To detect when it happens, we remember the key pointer of the entry we were
658 * going to iterate next. If it does not match, there was a backward shift.
660 if (e->key != i->next_key)
661 e = bucket_at(h, --i->idx);
663 assert(e->key == i->next_key);
667 #if ENABLE_DEBUG_HASHMAP
671 i->idx = skip_free_buckets(h, i->idx + 1);
672 if (i->idx != IDX_NIL)
673 i->next_key = bucket_at(h, i->idx)->key;
684 static unsigned hashmap_iterate_entry(HashmapBase *h, Iterator *i) {
690 #if ENABLE_DEBUG_HASHMAP
691 if (i->idx == IDX_FIRST) {
692 i->put_count = h->debug.put_count;
693 i->rem_count = h->debug.rem_count;
695 /* While iterating, must not add any new entries */
696 assert(i->put_count == h->debug.put_count);
697 /* ... or remove entries other than the current one */
698 assert(i->rem_count == h->debug.rem_count ||
699 (i->rem_count == h->debug.rem_count - 1 &&
700 i->prev_idx == h->debug.last_rem_idx));
701 /* Reset our removals counter */
702 i->rem_count = h->debug.rem_count;
706 return h->type == HASHMAP_TYPE_ORDERED ? hashmap_iterate_in_insertion_order((OrderedHashmap*) h, i)
707 : hashmap_iterate_in_internal_order(h, i);
710 bool internal_hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key) {
711 struct hashmap_base_entry *e;
715 idx = hashmap_iterate_entry(h, i);
716 if (idx == IDX_NIL) {
725 e = bucket_at(h, idx);
726 data = entry_value(h, e);
735 bool set_iterate(Set *s, Iterator *i, void **value) {
736 return internal_hashmap_iterate(HASHMAP_BASE(s), i, value, NULL);
739 #define HASHMAP_FOREACH_IDX(idx, h, i) \
740 for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \
742 (idx) = hashmap_iterate_entry((h), &(i)))
744 IteratedCache *internal_hashmap_iterated_cache_new(HashmapBase *h) {
745 IteratedCache *cache;
753 cache = new0(IteratedCache, 1);
763 static void reset_direct_storage(HashmapBase *h) {
764 const struct hashmap_type_info *hi = &hashmap_type_info[h->type];
767 assert(!h->has_indirect);
769 p = mempset(h->direct.storage, 0, hi->entry_size * hi->n_direct_buckets);
770 memset(p, DIB_RAW_INIT, sizeof(dib_raw_t) * hi->n_direct_buckets);
773 static struct HashmapBase *hashmap_base_new(const struct hash_ops *hash_ops, enum HashmapType type HASHMAP_DEBUG_PARAMS) {
775 const struct hashmap_type_info *hi = &hashmap_type_info[type];
778 use_pool = is_main_thread();
780 h = use_pool ? mempool_alloc0_tile(hi->mempool) : malloc0(hi->head_size);
786 h->from_pool = use_pool;
787 h->hash_ops = hash_ops ? hash_ops : &trivial_hash_ops;
789 if (type == HASHMAP_TYPE_ORDERED) {
790 OrderedHashmap *lh = (OrderedHashmap*)h;
791 lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;
794 reset_direct_storage(h);
796 if (!shared_hash_key_initialized) {
797 random_bytes(shared_hash_key, sizeof(shared_hash_key));
798 shared_hash_key_initialized= true;
801 #if ENABLE_DEBUG_HASHMAP
802 h->debug.func = func;
803 h->debug.file = file;
804 h->debug.line = line;
805 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex) == 0);
806 LIST_PREPEND(debug_list, hashmap_debug_list, &h->debug);
807 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex) == 0);
813 Hashmap *internal_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
814 return (Hashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
817 OrderedHashmap *internal_ordered_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
818 return (OrderedHashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
821 Set *internal_set_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
822 return (Set*) hashmap_base_new(hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
825 static int hashmap_base_ensure_allocated(HashmapBase **h, const struct hash_ops *hash_ops,
826 enum HashmapType type HASHMAP_DEBUG_PARAMS) {
834 q = hashmap_base_new(hash_ops, type HASHMAP_DEBUG_PASS_ARGS);
842 int internal_hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
843 return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
846 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
847 return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
850 int internal_set_ensure_allocated(Set **s, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
851 return hashmap_base_ensure_allocated((HashmapBase**)s, hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
854 static void hashmap_free_no_clear(HashmapBase *h) {
855 assert(!h->has_indirect);
856 assert(!h->n_direct_entries);
858 #if ENABLE_DEBUG_HASHMAP
859 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex) == 0);
860 LIST_REMOVE(debug_list, hashmap_debug_list, &h->debug);
861 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex) == 0);
865 mempool_free_tile(hashmap_type_info[h->type].mempool, h);
870 HashmapBase *internal_hashmap_free(HashmapBase *h) {
872 /* Free the hashmap, but nothing in it */
875 internal_hashmap_clear(h);
876 hashmap_free_no_clear(h);
882 HashmapBase *internal_hashmap_free_free(HashmapBase *h) {
884 /* Free the hashmap and all data objects in it, but not the
888 internal_hashmap_clear_free(h);
889 hashmap_free_no_clear(h);
895 Hashmap *hashmap_free_free_free(Hashmap *h) {
897 /* Free the hashmap and all data and key objects in it */
900 hashmap_clear_free_free(h);
901 hashmap_free_no_clear(HASHMAP_BASE(h));
907 void internal_hashmap_clear(HashmapBase *h) {
911 if (h->has_indirect) {
912 free(h->indirect.storage);
913 h->has_indirect = false;
916 h->n_direct_entries = 0;
917 reset_direct_storage(h);
919 if (h->type == HASHMAP_TYPE_ORDERED) {
920 OrderedHashmap *lh = (OrderedHashmap*) h;
921 lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;
927 void internal_hashmap_clear_free(HashmapBase *h) {
933 for (idx = skip_free_buckets(h, 0); idx != IDX_NIL;
934 idx = skip_free_buckets(h, idx + 1))
935 free(entry_value(h, bucket_at(h, idx)));
937 internal_hashmap_clear(h);
940 void hashmap_clear_free_free(Hashmap *h) {
946 for (idx = skip_free_buckets(HASHMAP_BASE(h), 0); idx != IDX_NIL;
947 idx = skip_free_buckets(HASHMAP_BASE(h), idx + 1)) {
948 struct plain_hashmap_entry *e = plain_bucket_at(h, idx);
949 free((void*)e->b.key);
953 internal_hashmap_clear(HASHMAP_BASE(h));
956 static int resize_buckets(HashmapBase *h, unsigned entries_add);
959 * Finds an empty bucket to put an entry into, starting the scan at 'idx'.
960 * Performs Robin Hood swaps as it goes. The entry to put must be placed
961 * by the caller into swap slot IDX_PUT.
962 * If used for in-place resizing, may leave a displaced entry in swap slot
963 * IDX_PUT. Caller must rehash it next.
964 * Returns: true if it left a displaced entry to rehash next in IDX_PUT,
967 static bool hashmap_put_robin_hood(HashmapBase *h, unsigned idx,
968 struct swap_entries *swap) {
969 dib_raw_t raw_dib, *dibs;
970 unsigned dib, distance;
972 #if ENABLE_DEBUG_HASHMAP
973 h->debug.put_count++;
976 dibs = dib_raw_ptr(h);
978 for (distance = 0; ; distance++) {
980 if (IN_SET(raw_dib, DIB_RAW_FREE, DIB_RAW_REHASH)) {
981 if (raw_dib == DIB_RAW_REHASH)
982 bucket_move_entry(h, swap, idx, IDX_TMP);
984 if (h->has_indirect && h->indirect.idx_lowest_entry > idx)
985 h->indirect.idx_lowest_entry = idx;
987 bucket_set_dib(h, idx, distance);
988 bucket_move_entry(h, swap, IDX_PUT, idx);
989 if (raw_dib == DIB_RAW_REHASH) {
990 bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
997 dib = bucket_calculate_dib(h, idx, raw_dib);
999 if (dib < distance) {
1000 /* Found a wealthier entry. Go Robin Hood! */
1001 bucket_set_dib(h, idx, distance);
1003 /* swap the entries */
1004 bucket_move_entry(h, swap, idx, IDX_TMP);
1005 bucket_move_entry(h, swap, IDX_PUT, idx);
1006 bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
1011 idx = next_idx(h, idx);
1016 * Puts an entry into a hashmap, boldly - no check whether key already exists.
1017 * The caller must place the entry (only its key and value, not link indexes)
1018 * in swap slot IDX_PUT.
1019 * Caller must ensure: the key does not exist yet in the hashmap.
1020 * that resize is not needed if !may_resize.
1021 * Returns: 1 if entry was put successfully.
1022 * -ENOMEM if may_resize==true and resize failed with -ENOMEM.
1023 * Cannot return -ENOMEM if !may_resize.
1025 static int hashmap_base_put_boldly(HashmapBase *h, unsigned idx,
1026 struct swap_entries *swap, bool may_resize) {
1027 struct ordered_hashmap_entry *new_entry;
1030 assert(idx < n_buckets(h));
1032 new_entry = bucket_at_swap(swap, IDX_PUT);
1035 r = resize_buckets(h, 1);
1039 idx = bucket_hash(h, new_entry->p.b.key);
1041 assert(n_entries(h) < n_buckets(h));
1043 if (h->type == HASHMAP_TYPE_ORDERED) {
1044 OrderedHashmap *lh = (OrderedHashmap*) h;
1046 new_entry->iterate_next = IDX_NIL;
1047 new_entry->iterate_previous = lh->iterate_list_tail;
1049 if (lh->iterate_list_tail != IDX_NIL) {
1050 struct ordered_hashmap_entry *old_tail;
1052 old_tail = ordered_bucket_at(lh, lh->iterate_list_tail);
1053 assert(old_tail->iterate_next == IDX_NIL);
1054 old_tail->iterate_next = IDX_PUT;
1057 lh->iterate_list_tail = IDX_PUT;
1058 if (lh->iterate_list_head == IDX_NIL)
1059 lh->iterate_list_head = IDX_PUT;
1062 assert_se(hashmap_put_robin_hood(h, idx, swap) == false);
1065 #if ENABLE_DEBUG_HASHMAP
1066 h->debug.max_entries = MAX(h->debug.max_entries, n_entries(h));
1073 #define hashmap_put_boldly(h, idx, swap, may_resize) \
1074 hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
1077 * Returns 0 if resize is not needed.
1078 * 1 if successfully resized.
1079 * -ENOMEM on allocation failure.
1081 static int resize_buckets(HashmapBase *h, unsigned entries_add) {
1082 struct swap_entries swap;
1084 dib_raw_t *old_dibs, *new_dibs;
1085 const struct hashmap_type_info *hi;
1086 unsigned idx, optimal_idx;
1087 unsigned old_n_buckets, new_n_buckets, n_rehashed, new_n_entries;
1093 hi = &hashmap_type_info[h->type];
1094 new_n_entries = n_entries(h) + entries_add;
1097 if (_unlikely_(new_n_entries < entries_add))
1100 /* For direct storage we allow 100% load, because it's tiny. */
1101 if (!h->has_indirect && new_n_entries <= hi->n_direct_buckets)
1105 * Load factor = n/m = 1 - (1/INV_KEEP_FREE).
1106 * From it follows: m = n + n/(INV_KEEP_FREE - 1)
1108 new_n_buckets = new_n_entries + new_n_entries / (INV_KEEP_FREE - 1);
1110 if (_unlikely_(new_n_buckets < new_n_entries))
1113 if (_unlikely_(new_n_buckets > UINT_MAX / (hi->entry_size + sizeof(dib_raw_t))))
1116 old_n_buckets = n_buckets(h);
1118 if (_likely_(new_n_buckets <= old_n_buckets))
1121 new_shift = log2u_round_up(MAX(
1122 new_n_buckets * (hi->entry_size + sizeof(dib_raw_t)),
1123 2 * sizeof(struct direct_storage)));
1125 /* Realloc storage (buckets and DIB array). */
1126 new_storage = realloc(h->has_indirect ? h->indirect.storage : NULL,
1131 /* Must upgrade direct to indirect storage. */
1132 if (!h->has_indirect) {
1133 memcpy(new_storage, h->direct.storage,
1134 old_n_buckets * (hi->entry_size + sizeof(dib_raw_t)));
1135 h->indirect.n_entries = h->n_direct_entries;
1136 h->indirect.idx_lowest_entry = 0;
1137 h->n_direct_entries = 0;
1140 /* Get a new hash key. If we've just upgraded to indirect storage,
1141 * allow reusing a previously generated key. It's still a different key
1142 * from the shared one that we used for direct storage. */
1143 get_hash_key(h->indirect.hash_key, !h->has_indirect);
1145 h->has_indirect = true;
1146 h->indirect.storage = new_storage;
1147 h->indirect.n_buckets = (1U << new_shift) /
1148 (hi->entry_size + sizeof(dib_raw_t));
1150 old_dibs = (dib_raw_t*)((uint8_t*) new_storage + hi->entry_size * old_n_buckets);
1151 new_dibs = dib_raw_ptr(h);
1154 * Move the DIB array to the new place, replacing valid DIB values with
1155 * DIB_RAW_REHASH to indicate all of the used buckets need rehashing.
1156 * Note: Overlap is not possible, because we have at least doubled the
1157 * number of buckets and dib_raw_t is smaller than any entry type.
1159 for (idx = 0; idx < old_n_buckets; idx++) {
1160 assert(old_dibs[idx] != DIB_RAW_REHASH);
1161 new_dibs[idx] = old_dibs[idx] == DIB_RAW_FREE ? DIB_RAW_FREE
1165 /* Zero the area of newly added entries (including the old DIB area) */
1166 memzero(bucket_at(h, old_n_buckets),
1167 (n_buckets(h) - old_n_buckets) * hi->entry_size);
1169 /* The upper half of the new DIB array needs initialization */
1170 memset(&new_dibs[old_n_buckets], DIB_RAW_INIT,
1171 (n_buckets(h) - old_n_buckets) * sizeof(dib_raw_t));
1173 /* Rehash entries that need it */
1175 for (idx = 0; idx < old_n_buckets; idx++) {
1176 if (new_dibs[idx] != DIB_RAW_REHASH)
1179 optimal_idx = bucket_hash(h, bucket_at(h, idx)->key);
1182 * Not much to do if by luck the entry hashes to its current
1183 * location. Just set its DIB.
1185 if (optimal_idx == idx) {
1191 new_dibs[idx] = DIB_RAW_FREE;
1192 bucket_move_entry(h, &swap, idx, IDX_PUT);
1193 /* bucket_move_entry does not clear the source */
1194 memzero(bucket_at(h, idx), hi->entry_size);
1198 * Find the new bucket for the current entry. This may make
1199 * another entry homeless and load it into IDX_PUT.
1201 rehash_next = hashmap_put_robin_hood(h, optimal_idx, &swap);
1204 /* Did the current entry displace another one? */
1206 optimal_idx = bucket_hash(h, bucket_at_swap(&swap, IDX_PUT)->p.b.key);
1207 } while (rehash_next);
1210 assert(n_rehashed == n_entries(h));
1216 * Finds an entry with a matching key
1217 * Returns: index of the found entry, or IDX_NIL if not found.
1219 static unsigned base_bucket_scan(HashmapBase *h, unsigned idx, const void *key) {
1220 struct hashmap_base_entry *e;
1221 unsigned dib, distance;
1222 dib_raw_t *dibs = dib_raw_ptr(h);
1224 assert(idx < n_buckets(h));
1226 for (distance = 0; ; distance++) {
1227 if (dibs[idx] == DIB_RAW_FREE)
1230 dib = bucket_calculate_dib(h, idx, dibs[idx]);
1234 if (dib == distance) {
1235 e = bucket_at(h, idx);
1236 if (h->hash_ops->compare(e->key, key) == 0)
1240 idx = next_idx(h, idx);
1243 #define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
1245 int hashmap_put(Hashmap *h, const void *key, void *value) {
1246 struct swap_entries swap;
1247 struct plain_hashmap_entry *e;
1252 hash = bucket_hash(h, key);
1253 idx = bucket_scan(h, hash, key);
1254 if (idx != IDX_NIL) {
1255 e = plain_bucket_at(h, idx);
1256 if (e->value == value)
1261 e = &bucket_at_swap(&swap, IDX_PUT)->p;
1264 return hashmap_put_boldly(h, hash, &swap, true);
1267 int set_put(Set *s, const void *key) {
1268 struct swap_entries swap;
1269 struct hashmap_base_entry *e;
1274 hash = bucket_hash(s, key);
1275 idx = bucket_scan(s, hash, key);
1279 e = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1281 return hashmap_put_boldly(s, hash, &swap, true);
1284 int hashmap_replace(Hashmap *h, const void *key, void *value) {
1285 struct swap_entries swap;
1286 struct plain_hashmap_entry *e;
1291 hash = bucket_hash(h, key);
1292 idx = bucket_scan(h, hash, key);
1293 if (idx != IDX_NIL) {
1294 e = plain_bucket_at(h, idx);
1295 #if ENABLE_DEBUG_HASHMAP
1296 /* Although the key is equal, the key pointer may have changed,
1297 * and this would break our assumption for iterating. So count
1298 * this operation as incompatible with iteration. */
1299 if (e->b.key != key) {
1300 h->b.debug.put_count++;
1301 h->b.debug.rem_count++;
1302 h->b.debug.last_rem_idx = idx;
1307 hashmap_set_dirty(h);
1312 e = &bucket_at_swap(&swap, IDX_PUT)->p;
1315 return hashmap_put_boldly(h, hash, &swap, true);
1318 int hashmap_update(Hashmap *h, const void *key, void *value) {
1319 struct plain_hashmap_entry *e;
1324 hash = bucket_hash(h, key);
1325 idx = bucket_scan(h, hash, key);
1329 e = plain_bucket_at(h, idx);
1331 hashmap_set_dirty(h);
1336 void *internal_hashmap_get(HashmapBase *h, const void *key) {
1337 struct hashmap_base_entry *e;
1343 hash = bucket_hash(h, key);
1344 idx = bucket_scan(h, hash, key);
1348 e = bucket_at(h, idx);
1349 return entry_value(h, e);
1352 void *hashmap_get2(Hashmap *h, const void *key, void **key2) {
1353 struct plain_hashmap_entry *e;
1359 hash = bucket_hash(h, key);
1360 idx = bucket_scan(h, hash, key);
1364 e = plain_bucket_at(h, idx);
1366 *key2 = (void*) e->b.key;
1371 bool internal_hashmap_contains(HashmapBase *h, const void *key) {
1377 hash = bucket_hash(h, key);
1378 return bucket_scan(h, hash, key) != IDX_NIL;
1381 void *internal_hashmap_remove(HashmapBase *h, const void *key) {
1382 struct hashmap_base_entry *e;
1389 hash = bucket_hash(h, key);
1390 idx = bucket_scan(h, hash, key);
1394 e = bucket_at(h, idx);
1395 data = entry_value(h, e);
1396 remove_entry(h, idx);
1401 void *hashmap_remove2(Hashmap *h, const void *key, void **rkey) {
1402 struct plain_hashmap_entry *e;
1412 hash = bucket_hash(h, key);
1413 idx = bucket_scan(h, hash, key);
1414 if (idx == IDX_NIL) {
1420 e = plain_bucket_at(h, idx);
1423 *rkey = (void*) e->b.key;
1425 remove_entry(h, idx);
1430 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
1431 struct swap_entries swap;
1432 struct plain_hashmap_entry *e;
1433 unsigned old_hash, new_hash, idx;
1438 old_hash = bucket_hash(h, old_key);
1439 idx = bucket_scan(h, old_hash, old_key);
1443 new_hash = bucket_hash(h, new_key);
1444 if (bucket_scan(h, new_hash, new_key) != IDX_NIL)
1447 remove_entry(h, idx);
1449 e = &bucket_at_swap(&swap, IDX_PUT)->p;
1452 assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
1457 #if 0 /// UNNEEDED by elogind
1458 int set_remove_and_put(Set *s, const void *old_key, const void *new_key) {
1459 struct swap_entries swap;
1460 struct hashmap_base_entry *e;
1461 unsigned old_hash, new_hash, idx;
1466 old_hash = bucket_hash(s, old_key);
1467 idx = bucket_scan(s, old_hash, old_key);
1471 new_hash = bucket_hash(s, new_key);
1472 if (bucket_scan(s, new_hash, new_key) != IDX_NIL)
1475 remove_entry(s, idx);
1477 e = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1479 assert_se(hashmap_put_boldly(s, new_hash, &swap, false) == 1);
1485 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
1486 struct swap_entries swap;
1487 struct plain_hashmap_entry *e;
1488 unsigned old_hash, new_hash, idx_old, idx_new;
1493 old_hash = bucket_hash(h, old_key);
1494 idx_old = bucket_scan(h, old_hash, old_key);
1495 if (idx_old == IDX_NIL)
1498 old_key = bucket_at(HASHMAP_BASE(h), idx_old)->key;
1500 new_hash = bucket_hash(h, new_key);
1501 idx_new = bucket_scan(h, new_hash, new_key);
1502 if (idx_new != IDX_NIL)
1503 if (idx_old != idx_new) {
1504 remove_entry(h, idx_new);
1505 /* Compensate for a possible backward shift. */
1506 if (old_key != bucket_at(HASHMAP_BASE(h), idx_old)->key)
1507 idx_old = prev_idx(HASHMAP_BASE(h), idx_old);
1508 assert(old_key == bucket_at(HASHMAP_BASE(h), idx_old)->key);
1511 remove_entry(h, idx_old);
1513 e = &bucket_at_swap(&swap, IDX_PUT)->p;
1516 assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
1521 void *hashmap_remove_value(Hashmap *h, const void *key, void *value) {
1522 struct plain_hashmap_entry *e;
1528 hash = bucket_hash(h, key);
1529 idx = bucket_scan(h, hash, key);
1533 e = plain_bucket_at(h, idx);
1534 if (e->value != value)
1537 remove_entry(h, idx);
1542 static unsigned find_first_entry(HashmapBase *h) {
1543 Iterator i = ITERATOR_FIRST;
1545 if (!h || !n_entries(h))
1548 return hashmap_iterate_entry(h, &i);
1551 void *internal_hashmap_first(HashmapBase *h) {
1554 idx = find_first_entry(h);
1558 return entry_value(h, bucket_at(h, idx));
1561 void *internal_hashmap_first_key(HashmapBase *h) {
1562 struct hashmap_base_entry *e;
1565 idx = find_first_entry(h);
1569 e = bucket_at(h, idx);
1570 return (void*) e->key;
1573 void *internal_hashmap_steal_first(HashmapBase *h) {
1574 struct hashmap_base_entry *e;
1578 idx = find_first_entry(h);
1582 e = bucket_at(h, idx);
1583 data = entry_value(h, e);
1584 remove_entry(h, idx);
1589 void *internal_hashmap_steal_first_key(HashmapBase *h) {
1590 struct hashmap_base_entry *e;
1594 idx = find_first_entry(h);
1598 e = bucket_at(h, idx);
1599 key = (void*) e->key;
1600 remove_entry(h, idx);
1605 unsigned internal_hashmap_size(HashmapBase *h) {
1610 return n_entries(h);
1613 unsigned internal_hashmap_buckets(HashmapBase *h) {
1618 return n_buckets(h);
1621 int internal_hashmap_merge(Hashmap *h, Hashmap *other) {
1627 HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1628 struct plain_hashmap_entry *pe = plain_bucket_at(other, idx);
1631 r = hashmap_put(h, pe->b.key, pe->value);
1632 if (r < 0 && r != -EEXIST)
1639 int set_merge(Set *s, Set *other) {
1645 HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1646 struct set_entry *se = set_bucket_at(other, idx);
1649 r = set_put(s, se->b.key);
1657 int internal_hashmap_reserve(HashmapBase *h, unsigned entries_add) {
1662 r = resize_buckets(h, entries_add);
1670 * The same as hashmap_merge(), but every new item from other is moved to h.
1671 * Keys already in h are skipped and stay in other.
1672 * Returns: 0 on success.
1673 * -ENOMEM on alloc failure, in which case no move has been done.
1675 int internal_hashmap_move(HashmapBase *h, HashmapBase *other) {
1676 struct swap_entries swap;
1677 struct hashmap_base_entry *e, *n;
1687 assert(other->type == h->type);
1690 * This reserves buckets for the worst case, where none of other's
1691 * entries are yet present in h. This is preferable to risking
1692 * an allocation failure in the middle of the moving and having to
1693 * rollback or return a partial result.
1695 r = resize_buckets(h, n_entries(other));
1699 HASHMAP_FOREACH_IDX(idx, other, i) {
1702 e = bucket_at(other, idx);
1703 h_hash = bucket_hash(h, e->key);
1704 if (bucket_scan(h, h_hash, e->key) != IDX_NIL)
1707 n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1709 if (h->type != HASHMAP_TYPE_SET)
1710 ((struct plain_hashmap_entry*) n)->value =
1711 ((struct plain_hashmap_entry*) e)->value;
1712 assert_se(hashmap_put_boldly(h, h_hash, &swap, false) == 1);
1714 remove_entry(other, idx);
1720 int internal_hashmap_move_one(HashmapBase *h, HashmapBase *other, const void *key) {
1721 struct swap_entries swap;
1722 unsigned h_hash, other_hash, idx;
1723 struct hashmap_base_entry *e, *n;
1728 h_hash = bucket_hash(h, key);
1729 if (bucket_scan(h, h_hash, key) != IDX_NIL)
1735 assert(other->type == h->type);
1737 other_hash = bucket_hash(other, key);
1738 idx = bucket_scan(other, other_hash, key);
1742 e = bucket_at(other, idx);
1744 n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1746 if (h->type != HASHMAP_TYPE_SET)
1747 ((struct plain_hashmap_entry*) n)->value =
1748 ((struct plain_hashmap_entry*) e)->value;
1749 r = hashmap_put_boldly(h, h_hash, &swap, true);
1753 remove_entry(other, idx);
1757 HashmapBase *internal_hashmap_copy(HashmapBase *h) {
1763 copy = hashmap_base_new(h->hash_ops, h->type HASHMAP_DEBUG_SRC_ARGS);
1768 case HASHMAP_TYPE_PLAIN:
1769 case HASHMAP_TYPE_ORDERED:
1770 r = hashmap_merge((Hashmap*)copy, (Hashmap*)h);
1772 case HASHMAP_TYPE_SET:
1773 r = set_merge((Set*)copy, (Set*)h);
1776 assert_not_reached("Unknown hashmap type");
1780 internal_hashmap_free(copy);
1787 char **internal_hashmap_get_strv(HashmapBase *h) {
1792 sv = new(char*, n_entries(h)+1);
1797 HASHMAP_FOREACH_IDX(idx, h, i)
1798 sv[n++] = entry_value(h, bucket_at(h, idx));
1804 void *ordered_hashmap_next(OrderedHashmap *h, const void *key) {
1805 struct ordered_hashmap_entry *e;
1811 hash = bucket_hash(h, key);
1812 idx = bucket_scan(h, hash, key);
1816 e = ordered_bucket_at(h, idx);
1817 if (e->iterate_next == IDX_NIL)
1819 return ordered_bucket_at(h, e->iterate_next)->p.value;
1822 int set_consume(Set *s, void *value) {
1828 r = set_put(s, value);
1835 int set_put_strdup(Set *s, const char *p) {
1841 if (set_contains(s, (char*) p))
1848 return set_consume(s, c);
1851 #if 0 /// UNNEEDED by elogind
1852 int set_put_strdupv(Set *s, char **l) {
1858 STRV_FOREACH(i, l) {
1859 r = set_put_strdup(s, *i);
1869 int set_put_strsplit(Set *s, const char *v, const char *separators, ExtractFlags flags) {
1879 r = extract_first_word(&p, &word, separators, flags);
1883 r = set_consume(s, word);
1890 /* expand the cachemem if needed, return true if newly (re)activated. */
1891 static int cachemem_maintain(CacheMem *mem, unsigned size) {
1894 if (!GREEDY_REALLOC(mem->ptr, mem->n_allocated, size)) {
1907 int iterated_cache_get(IteratedCache *cache, const void ***res_keys, const void ***res_values, unsigned *res_n_entries) {
1908 bool sync_keys = false, sync_values = false;
1913 assert(cache->hashmap);
1915 size = n_entries(cache->hashmap);
1918 r = cachemem_maintain(&cache->keys, size);
1924 cache->keys.active = false;
1927 r = cachemem_maintain(&cache->values, size);
1933 cache->values.active = false;
1935 if (cache->hashmap->dirty) {
1936 if (cache->keys.active)
1938 if (cache->values.active)
1941 cache->hashmap->dirty = false;
1944 if (sync_keys || sync_values) {
1949 HASHMAP_FOREACH_IDX(idx, cache->hashmap, iter) {
1950 struct hashmap_base_entry *e;
1952 e = bucket_at(cache->hashmap, idx);
1955 cache->keys.ptr[i] = e->key;
1957 cache->values.ptr[i] = entry_value(cache->hashmap, e);
1963 *res_keys = cache->keys.ptr;
1965 *res_values = cache->values.ptr;
1967 *res_n_entries = size;
1972 IteratedCache *iterated_cache_free(IteratedCache *cache) {
1974 free(cache->keys.ptr);
1975 free(cache->values.ptr);