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 int set_remove_and_put(Set
*s
, const void *old_key
, const void *new_key
) {
1458 struct swap_entries swap
;
1459 struct hashmap_base_entry
*e
;
1460 unsigned old_hash
, new_hash
, idx
;
1465 old_hash
= bucket_hash(s
, old_key
);
1466 idx
= bucket_scan(s
, old_hash
, old_key
);
1470 new_hash
= bucket_hash(s
, new_key
);
1471 if (bucket_scan(s
, new_hash
, new_key
) != IDX_NIL
)
1474 remove_entry(s
, idx
);
1476 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1478 assert_se(hashmap_put_boldly(s
, new_hash
, &swap
, false) == 1);
1483 int hashmap_remove_and_replace(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
1484 struct swap_entries swap
;
1485 struct plain_hashmap_entry
*e
;
1486 unsigned old_hash
, new_hash
, idx_old
, idx_new
;
1491 old_hash
= bucket_hash(h
, old_key
);
1492 idx_old
= bucket_scan(h
, old_hash
, old_key
);
1493 if (idx_old
== IDX_NIL
)
1496 old_key
= bucket_at(HASHMAP_BASE(h
), idx_old
)->key
;
1498 new_hash
= bucket_hash(h
, new_key
);
1499 idx_new
= bucket_scan(h
, new_hash
, new_key
);
1500 if (idx_new
!= IDX_NIL
)
1501 if (idx_old
!= idx_new
) {
1502 remove_entry(h
, idx_new
);
1503 /* Compensate for a possible backward shift. */
1504 if (old_key
!= bucket_at(HASHMAP_BASE(h
), idx_old
)->key
)
1505 idx_old
= prev_idx(HASHMAP_BASE(h
), idx_old
);
1506 assert(old_key
== bucket_at(HASHMAP_BASE(h
), idx_old
)->key
);
1509 remove_entry(h
, idx_old
);
1511 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1514 assert_se(hashmap_put_boldly(h
, new_hash
, &swap
, false) == 1);
1519 void *hashmap_remove_value(Hashmap
*h
, const void *key
, void *value
) {
1520 struct plain_hashmap_entry
*e
;
1526 hash
= bucket_hash(h
, key
);
1527 idx
= bucket_scan(h
, hash
, key
);
1531 e
= plain_bucket_at(h
, idx
);
1532 if (e
->value
!= value
)
1535 remove_entry(h
, idx
);
1540 static unsigned find_first_entry(HashmapBase
*h
) {
1541 Iterator i
= ITERATOR_FIRST
;
1543 if (!h
|| !n_entries(h
))
1546 return hashmap_iterate_entry(h
, &i
);
1549 void *internal_hashmap_first(HashmapBase
*h
) {
1552 idx
= find_first_entry(h
);
1556 return entry_value(h
, bucket_at(h
, idx
));
1559 void *internal_hashmap_first_key(HashmapBase
*h
) {
1560 struct hashmap_base_entry
*e
;
1563 idx
= find_first_entry(h
);
1567 e
= bucket_at(h
, idx
);
1568 return (void*) e
->key
;
1571 void *internal_hashmap_steal_first(HashmapBase
*h
) {
1572 struct hashmap_base_entry
*e
;
1576 idx
= find_first_entry(h
);
1580 e
= bucket_at(h
, idx
);
1581 data
= entry_value(h
, e
);
1582 remove_entry(h
, idx
);
1587 void *internal_hashmap_steal_first_key(HashmapBase
*h
) {
1588 struct hashmap_base_entry
*e
;
1592 idx
= find_first_entry(h
);
1596 e
= bucket_at(h
, idx
);
1597 key
= (void*) e
->key
;
1598 remove_entry(h
, idx
);
1603 unsigned internal_hashmap_size(HashmapBase
*h
) {
1608 return n_entries(h
);
1611 unsigned internal_hashmap_buckets(HashmapBase
*h
) {
1616 return n_buckets(h
);
1619 int internal_hashmap_merge(Hashmap
*h
, Hashmap
*other
) {
1625 HASHMAP_FOREACH_IDX(idx
, HASHMAP_BASE(other
), i
) {
1626 struct plain_hashmap_entry
*pe
= plain_bucket_at(other
, idx
);
1629 r
= hashmap_put(h
, pe
->b
.key
, pe
->value
);
1630 if (r
< 0 && r
!= -EEXIST
)
1637 int set_merge(Set
*s
, Set
*other
) {
1643 HASHMAP_FOREACH_IDX(idx
, HASHMAP_BASE(other
), i
) {
1644 struct set_entry
*se
= set_bucket_at(other
, idx
);
1647 r
= set_put(s
, se
->b
.key
);
1655 int internal_hashmap_reserve(HashmapBase
*h
, unsigned entries_add
) {
1660 r
= resize_buckets(h
, entries_add
);
1668 * The same as hashmap_merge(), but every new item from other is moved to h.
1669 * Keys already in h are skipped and stay in other.
1670 * Returns: 0 on success.
1671 * -ENOMEM on alloc failure, in which case no move has been done.
1673 int internal_hashmap_move(HashmapBase
*h
, HashmapBase
*other
) {
1674 struct swap_entries swap
;
1675 struct hashmap_base_entry
*e
, *n
;
1685 assert(other
->type
== h
->type
);
1688 * This reserves buckets for the worst case, where none of other's
1689 * entries are yet present in h. This is preferable to risking
1690 * an allocation failure in the middle of the moving and having to
1691 * rollback or return a partial result.
1693 r
= resize_buckets(h
, n_entries(other
));
1697 HASHMAP_FOREACH_IDX(idx
, other
, i
) {
1700 e
= bucket_at(other
, idx
);
1701 h_hash
= bucket_hash(h
, e
->key
);
1702 if (bucket_scan(h
, h_hash
, e
->key
) != IDX_NIL
)
1705 n
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1707 if (h
->type
!= HASHMAP_TYPE_SET
)
1708 ((struct plain_hashmap_entry
*) n
)->value
=
1709 ((struct plain_hashmap_entry
*) e
)->value
;
1710 assert_se(hashmap_put_boldly(h
, h_hash
, &swap
, false) == 1);
1712 remove_entry(other
, idx
);
1718 int internal_hashmap_move_one(HashmapBase
*h
, HashmapBase
*other
, const void *key
) {
1719 struct swap_entries swap
;
1720 unsigned h_hash
, other_hash
, idx
;
1721 struct hashmap_base_entry
*e
, *n
;
1726 h_hash
= bucket_hash(h
, key
);
1727 if (bucket_scan(h
, h_hash
, key
) != IDX_NIL
)
1733 assert(other
->type
== h
->type
);
1735 other_hash
= bucket_hash(other
, key
);
1736 idx
= bucket_scan(other
, other_hash
, key
);
1740 e
= bucket_at(other
, idx
);
1742 n
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1744 if (h
->type
!= HASHMAP_TYPE_SET
)
1745 ((struct plain_hashmap_entry
*) n
)->value
=
1746 ((struct plain_hashmap_entry
*) e
)->value
;
1747 r
= hashmap_put_boldly(h
, h_hash
, &swap
, true);
1751 remove_entry(other
, idx
);
1755 HashmapBase
*internal_hashmap_copy(HashmapBase
*h
) {
1761 copy
= hashmap_base_new(h
->hash_ops
, h
->type HASHMAP_DEBUG_SRC_ARGS
);
1766 case HASHMAP_TYPE_PLAIN
:
1767 case HASHMAP_TYPE_ORDERED
:
1768 r
= hashmap_merge((Hashmap
*)copy
, (Hashmap
*)h
);
1770 case HASHMAP_TYPE_SET
:
1771 r
= set_merge((Set
*)copy
, (Set
*)h
);
1774 assert_not_reached("Unknown hashmap type");
1778 internal_hashmap_free(copy
);
1785 char **internal_hashmap_get_strv(HashmapBase
*h
) {
1790 sv
= new(char*, n_entries(h
)+1);
1795 HASHMAP_FOREACH_IDX(idx
, h
, i
)
1796 sv
[n
++] = entry_value(h
, bucket_at(h
, idx
));
1802 void *ordered_hashmap_next(OrderedHashmap
*h
, const void *key
) {
1803 struct ordered_hashmap_entry
*e
;
1809 hash
= bucket_hash(h
, key
);
1810 idx
= bucket_scan(h
, hash
, key
);
1814 e
= ordered_bucket_at(h
, idx
);
1815 if (e
->iterate_next
== IDX_NIL
)
1817 return ordered_bucket_at(h
, e
->iterate_next
)->p
.value
;
1820 int set_consume(Set
*s
, void *value
) {
1826 r
= set_put(s
, value
);
1833 int set_put_strdup(Set
*s
, const char *p
) {
1839 if (set_contains(s
, (char*) p
))
1846 return set_consume(s
, c
);
1849 int set_put_strdupv(Set
*s
, char **l
) {
1855 STRV_FOREACH(i
, l
) {
1856 r
= set_put_strdup(s
, *i
);
1866 int set_put_strsplit(Set
*s
, const char *v
, const char *separators
, ExtractFlags flags
) {
1876 r
= extract_first_word(&p
, &word
, separators
, flags
);
1880 r
= set_consume(s
, word
);
1886 /* expand the cachemem if needed, return true if newly (re)activated. */
1887 static int cachemem_maintain(CacheMem
*mem
, unsigned size
) {
1890 if (!GREEDY_REALLOC(mem
->ptr
, mem
->n_allocated
, size
)) {
1903 int iterated_cache_get(IteratedCache
*cache
, const void ***res_keys
, const void ***res_values
, unsigned *res_n_entries
) {
1904 bool sync_keys
= false, sync_values
= false;
1909 assert(cache
->hashmap
);
1911 size
= n_entries(cache
->hashmap
);
1914 r
= cachemem_maintain(&cache
->keys
, size
);
1920 cache
->keys
.active
= false;
1923 r
= cachemem_maintain(&cache
->values
, size
);
1929 cache
->values
.active
= false;
1931 if (cache
->hashmap
->dirty
) {
1932 if (cache
->keys
.active
)
1934 if (cache
->values
.active
)
1937 cache
->hashmap
->dirty
= false;
1940 if (sync_keys
|| sync_values
) {
1945 HASHMAP_FOREACH_IDX(idx
, cache
->hashmap
, iter
) {
1946 struct hashmap_base_entry
*e
;
1948 e
= bucket_at(cache
->hashmap
, idx
);
1951 cache
->keys
.ptr
[i
] = e
->key
;
1953 cache
->values
.ptr
[i
] = entry_value(cache
->hashmap
, e
);
1959 *res_keys
= cache
->keys
.ptr
;
1961 *res_values
= cache
->values
.ptr
;
1963 *res_n_entries
= size
;
1968 IteratedCache
*iterated_cache_free(IteratedCache
*cache
) {
1970 free(cache
->keys
.ptr
);
1971 free(cache
->values
.ptr
);