1 /* SPDX-License-Identifier: LGPL-2.1+ */
3 This file is part of systemd.
5 Copyright 2010 Lennart Poettering
6 Copyright 2014 Michal Schmidt
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/>.
27 #include "alloc-util.h"
32 #include "process-util.h"
33 #include "random-util.h"
35 #include "siphash24.h"
36 #include "string-util.h"
40 #if ENABLE_DEBUG_HASHMAP
46 * Implementation of hashmaps.
48 * - uses less RAM compared to closed addressing (chaining), because
49 * our entries are small (especially in Sets, which tend to contain
50 * the majority of entries in systemd).
51 * Collision resolution: Robin Hood
52 * - tends to equalize displacement of entries from their optimal buckets.
53 * Probe sequence: linear
54 * - though theoretically worse than random probing/uniform hashing/double
55 * hashing, it is good for cache locality.
58 * Celis, P. 1986. Robin Hood Hashing.
59 * Ph.D. Dissertation. University of Waterloo, Waterloo, Ont., Canada, Canada.
60 * https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
61 * - The results are derived for random probing. Suggests deletion with
62 * tombstones and two mean-centered search methods. None of that works
63 * well for linear probing.
65 * Janson, S. 2005. Individual displacements for linear probing hashing with different insertion policies.
66 * ACM Trans. Algorithms 1, 2 (October 2005), 177-213.
67 * DOI=10.1145/1103963.1103964 http://doi.acm.org/10.1145/1103963.1103964
68 * http://www.math.uu.se/~svante/papers/sj157.pdf
69 * - Applies to Robin Hood with linear probing. Contains remarks on
70 * the unsuitability of mean-centered search with linear probing.
72 * Viola, A. 2005. Exact distribution of individual displacements in linear probing hashing.
73 * ACM Trans. Algorithms 1, 2 (October 2005), 214-242.
74 * DOI=10.1145/1103963.1103965 http://doi.acm.org/10.1145/1103963.1103965
75 * - Similar to Janson. Note that Viola writes about C_{m,n} (number of probes
76 * in a successful search), and Janson writes about displacement. C = d + 1.
78 * Goossaert, E. 2013. Robin Hood hashing: backward shift deletion.
79 * http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
80 * - Explanation of backward shift deletion with pictures.
82 * Khuong, P. 2013. The Other Robin Hood Hashing.
83 * http://www.pvk.ca/Blog/2013/11/26/the-other-robin-hood-hashing/
84 * - Short summary of random vs. linear probing, and tombstones vs. backward shift.
88 * XXX Ideas for improvement:
89 * For unordered hashmaps, randomize iteration order, similarly to Perl:
90 * http://blog.booking.com/hardening-perls-hash-function.html
93 /* INV_KEEP_FREE = 1 / (1 - max_load_factor)
94 * e.g. 1 / (1 - 0.8) = 5 ... keep one fifth of the buckets free. */
95 #define INV_KEEP_FREE 5U
97 /* Fields common to entries of all hashmap/set types */
98 struct hashmap_base_entry
{
102 /* Entry types for specific hashmap/set types
103 * hashmap_base_entry must be at the beginning of each entry struct. */
105 struct plain_hashmap_entry
{
106 struct hashmap_base_entry b
;
110 struct ordered_hashmap_entry
{
111 struct plain_hashmap_entry p
;
112 unsigned iterate_next
, iterate_previous
;
116 struct hashmap_base_entry b
;
119 /* In several functions it is advantageous to have the hash table extended
120 * virtually by a couple of additional buckets. We reserve special index values
121 * for these "swap" buckets. */
122 #define _IDX_SWAP_BEGIN (UINT_MAX - 3)
123 #define IDX_PUT (_IDX_SWAP_BEGIN + 0)
124 #define IDX_TMP (_IDX_SWAP_BEGIN + 1)
125 #define _IDX_SWAP_END (_IDX_SWAP_BEGIN + 2)
127 #define IDX_FIRST (UINT_MAX - 1) /* special index for freshly initialized iterators */
128 #define IDX_NIL UINT_MAX /* special index value meaning "none" or "end" */
130 assert_cc(IDX_FIRST
== _IDX_SWAP_END
);
131 assert_cc(IDX_FIRST
== _IDX_ITERATOR_FIRST
);
133 /* Storage space for the "swap" buckets.
134 * All entry types can fit into a ordered_hashmap_entry. */
135 struct swap_entries
{
136 struct ordered_hashmap_entry e
[_IDX_SWAP_END
- _IDX_SWAP_BEGIN
];
139 /* Distance from Initial Bucket */
140 typedef uint8_t dib_raw_t
;
141 #define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */
142 #define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */
143 #define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */
144 #define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */
146 #define DIB_FREE UINT_MAX
148 #if ENABLE_DEBUG_HASHMAP
149 struct hashmap_debug_info
{
150 LIST_FIELDS(struct hashmap_debug_info
, debug_list
);
151 unsigned max_entries
; /* high watermark of n_entries */
153 /* who allocated this hashmap */
158 /* fields to detect modification while iterating */
159 unsigned put_count
; /* counts puts into the hashmap */
160 unsigned rem_count
; /* counts removals from hashmap */
161 unsigned last_rem_idx
; /* remembers last removal index */
164 /* Tracks all existing hashmaps. Get at it from gdb. See sd_dump_hashmaps.py */
165 static LIST_HEAD(struct hashmap_debug_info
, hashmap_debug_list
);
166 static pthread_mutex_t hashmap_debug_list_mutex
= PTHREAD_MUTEX_INITIALIZER
;
168 #define HASHMAP_DEBUG_FIELDS struct hashmap_debug_info debug;
170 #else /* !ENABLE_DEBUG_HASHMAP */
171 #define HASHMAP_DEBUG_FIELDS
172 #endif /* ENABLE_DEBUG_HASHMAP */
176 HASHMAP_TYPE_ORDERED
,
181 struct _packed_ indirect_storage
{
182 void *storage
; /* where buckets and DIBs are stored */
183 uint8_t hash_key
[HASH_KEY_SIZE
]; /* hash key; changes during resize */
185 unsigned n_entries
; /* number of stored entries */
186 unsigned n_buckets
; /* number of buckets */
188 unsigned idx_lowest_entry
; /* Index below which all buckets are free.
189 Makes "while(hashmap_steal_first())" loops
190 O(n) instead of O(n^2) for unordered hashmaps. */
191 uint8_t _pad
[3]; /* padding for the whole HashmapBase */
192 /* The bitfields in HashmapBase complete the alignment of the whole thing. */
195 struct direct_storage
{
196 /* This gives us 39 bytes on 64bit, or 35 bytes on 32bit.
197 * That's room for 4 set_entries + 4 DIB bytes + 3 unused bytes on 64bit,
198 * or 7 set_entries + 7 DIB bytes + 0 unused bytes on 32bit. */
199 uint8_t storage
[sizeof(struct indirect_storage
)];
202 #define DIRECT_BUCKETS(entry_t) \
203 (sizeof(struct direct_storage) / (sizeof(entry_t) + sizeof(dib_raw_t)))
205 /* We should be able to store at least one entry directly. */
206 assert_cc(DIRECT_BUCKETS(struct ordered_hashmap_entry
) >= 1);
208 /* We have 3 bits for n_direct_entries. */
209 assert_cc(DIRECT_BUCKETS(struct set_entry
) < (1 << 3));
211 /* Hashmaps with directly stored entries all use this shared hash key.
212 * It's no big deal if the key is guessed, because there can be only
213 * a handful of directly stored entries in a hashmap. When a hashmap
214 * outgrows direct storage, it gets its own key for indirect storage. */
215 static uint8_t shared_hash_key
[HASH_KEY_SIZE
];
216 static bool shared_hash_key_initialized
;
218 /* Fields that all hashmap/set types must have */
220 const struct hash_ops
*hash_ops
; /* hash and compare ops to use */
223 struct indirect_storage indirect
; /* if has_indirect */
224 struct direct_storage direct
; /* if !has_indirect */
227 enum HashmapType type
:2; /* HASHMAP_TYPE_* */
228 bool has_indirect
:1; /* whether indirect storage is used */
229 unsigned n_direct_entries
:3; /* Number of entries in direct storage.
230 * Only valid if !has_indirect. */
231 bool from_pool
:1; /* whether was allocated from mempool */
232 bool dirty
:1; /* whether dirtied since last iterated_cache_get() */
233 bool cached
:1; /* whether this hashmap is being cached */
234 HASHMAP_DEBUG_FIELDS
/* optional hashmap_debug_info */
237 /* Specific hash types
238 * HashmapBase must be at the beginning of each hashmap struct. */
241 struct HashmapBase b
;
244 struct OrderedHashmap
{
245 struct HashmapBase b
;
246 unsigned iterate_list_head
, iterate_list_tail
;
250 struct HashmapBase b
;
253 typedef struct CacheMem
{
255 size_t n_populated
, n_allocated
;
259 struct IteratedCache
{
260 HashmapBase
*hashmap
;
261 CacheMem keys
, values
;
264 DEFINE_MEMPOOL(hashmap_pool
, Hashmap
, 8);
265 DEFINE_MEMPOOL(ordered_hashmap_pool
, OrderedHashmap
, 8);
266 /* No need for a separate Set pool */
267 assert_cc(sizeof(Hashmap
) == sizeof(Set
));
269 struct hashmap_type_info
{
272 struct mempool
*mempool
;
273 unsigned n_direct_buckets
;
276 static const struct hashmap_type_info hashmap_type_info
[_HASHMAP_TYPE_MAX
] = {
277 [HASHMAP_TYPE_PLAIN
] = {
278 .head_size
= sizeof(Hashmap
),
279 .entry_size
= sizeof(struct plain_hashmap_entry
),
280 .mempool
= &hashmap_pool
,
281 .n_direct_buckets
= DIRECT_BUCKETS(struct plain_hashmap_entry
),
283 [HASHMAP_TYPE_ORDERED
] = {
284 .head_size
= sizeof(OrderedHashmap
),
285 .entry_size
= sizeof(struct ordered_hashmap_entry
),
286 .mempool
= &ordered_hashmap_pool
,
287 .n_direct_buckets
= DIRECT_BUCKETS(struct ordered_hashmap_entry
),
289 [HASHMAP_TYPE_SET
] = {
290 .head_size
= sizeof(Set
),
291 .entry_size
= sizeof(struct set_entry
),
292 .mempool
= &hashmap_pool
,
293 .n_direct_buckets
= DIRECT_BUCKETS(struct set_entry
),
298 __attribute__((destructor
)) static void cleanup_pools(void) {
299 _cleanup_free_
char *t
= NULL
;
302 /* Be nice to valgrind */
304 /* The pool is only allocated by the main thread, but the memory can
305 * be passed to other threads. Let's clean up if we are the main thread
306 * and no other threads are live. */
307 if (!is_main_thread())
310 r
= get_proc_field("/proc/self/status", "Threads", WHITESPACE
, &t
);
311 if (r
< 0 || !streq(t
, "1"))
314 mempool_drop(&hashmap_pool
);
315 mempool_drop(&ordered_hashmap_pool
);
319 static unsigned n_buckets(HashmapBase
*h
) {
320 return h
->has_indirect
? h
->indirect
.n_buckets
321 : hashmap_type_info
[h
->type
].n_direct_buckets
;
324 static unsigned n_entries(HashmapBase
*h
) {
325 return h
->has_indirect
? h
->indirect
.n_entries
326 : h
->n_direct_entries
;
329 static void n_entries_inc(HashmapBase
*h
) {
331 h
->indirect
.n_entries
++;
333 h
->n_direct_entries
++;
336 static void n_entries_dec(HashmapBase
*h
) {
338 h
->indirect
.n_entries
--;
340 h
->n_direct_entries
--;
343 static void *storage_ptr(HashmapBase
*h
) {
344 return h
->has_indirect
? h
->indirect
.storage
348 static uint8_t *hash_key(HashmapBase
*h
) {
349 return h
->has_indirect
? h
->indirect
.hash_key
353 static unsigned base_bucket_hash(HashmapBase
*h
, const void *p
) {
354 struct siphash state
;
357 siphash24_init(&state
, hash_key(h
));
359 h
->hash_ops
->hash(p
, &state
);
361 hash
= siphash24_finalize(&state
);
363 return (unsigned) (hash
% n_buckets(h
));
365 #define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p)
367 static inline void base_set_dirty(HashmapBase
*h
) {
370 #define hashmap_set_dirty(h) base_set_dirty(HASHMAP_BASE(h))
372 static void get_hash_key(uint8_t hash_key
[HASH_KEY_SIZE
], bool reuse_is_ok
) {
373 static uint8_t current
[HASH_KEY_SIZE
];
374 static bool current_initialized
= false;
376 /* Returns a hash function key to use. In order to keep things
377 * fast we will not generate a new key each time we allocate a
378 * new hash table. Instead, we'll just reuse the most recently
379 * generated one, except if we never generated one or when we
380 * are rehashing an entire hash table because we reached a
383 if (!current_initialized
|| !reuse_is_ok
) {
384 random_bytes(current
, sizeof(current
));
385 current_initialized
= true;
388 memcpy(hash_key
, current
, sizeof(current
));
391 static struct hashmap_base_entry
*bucket_at(HashmapBase
*h
, unsigned idx
) {
392 return (struct hashmap_base_entry
*)
393 ((uint8_t*) storage_ptr(h
) + idx
* hashmap_type_info
[h
->type
].entry_size
);
396 static struct plain_hashmap_entry
*plain_bucket_at(Hashmap
*h
, unsigned idx
) {
397 return (struct plain_hashmap_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
400 static struct ordered_hashmap_entry
*ordered_bucket_at(OrderedHashmap
*h
, unsigned idx
) {
401 return (struct ordered_hashmap_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
404 static struct set_entry
*set_bucket_at(Set
*h
, unsigned idx
) {
405 return (struct set_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
408 static struct ordered_hashmap_entry
*bucket_at_swap(struct swap_entries
*swap
, unsigned idx
) {
409 return &swap
->e
[idx
- _IDX_SWAP_BEGIN
];
412 /* Returns a pointer to the bucket at index idx.
413 * Understands real indexes and swap indexes, hence "_virtual". */
414 static struct hashmap_base_entry
*bucket_at_virtual(HashmapBase
*h
, struct swap_entries
*swap
,
416 if (idx
< _IDX_SWAP_BEGIN
)
417 return bucket_at(h
, idx
);
419 if (idx
< _IDX_SWAP_END
)
420 return &bucket_at_swap(swap
, idx
)->p
.b
;
422 assert_not_reached("Invalid index");
425 static dib_raw_t
*dib_raw_ptr(HashmapBase
*h
) {
427 ((uint8_t*) storage_ptr(h
) + hashmap_type_info
[h
->type
].entry_size
* n_buckets(h
));
430 static unsigned bucket_distance(HashmapBase
*h
, unsigned idx
, unsigned from
) {
431 return idx
>= from
? idx
- from
432 : n_buckets(h
) + idx
- from
;
435 static unsigned bucket_calculate_dib(HashmapBase
*h
, unsigned idx
, dib_raw_t raw_dib
) {
436 unsigned initial_bucket
;
438 if (raw_dib
== DIB_RAW_FREE
)
441 if (_likely_(raw_dib
< DIB_RAW_OVERFLOW
))
445 * Having an overflow DIB value is very unlikely. The hash function
446 * would have to be bad. For example, in a table of size 2^24 filled
447 * to load factor 0.9 the maximum observed DIB is only about 60.
448 * In theory (assuming I used Maxima correctly), for an infinite size
449 * hash table with load factor 0.8 the probability of a given entry
450 * having DIB > 40 is 1.9e-8.
451 * This returns the correct DIB value by recomputing the hash value in
452 * the unlikely case. XXX Hitting this case could be a hint to rehash.
454 initial_bucket
= bucket_hash(h
, bucket_at(h
, idx
)->key
);
455 return bucket_distance(h
, idx
, initial_bucket
);
458 static void bucket_set_dib(HashmapBase
*h
, unsigned idx
, unsigned dib
) {
459 dib_raw_ptr(h
)[idx
] = dib
!= DIB_FREE
? MIN(dib
, DIB_RAW_OVERFLOW
) : DIB_RAW_FREE
;
462 static unsigned skip_free_buckets(HashmapBase
*h
, unsigned idx
) {
465 dibs
= dib_raw_ptr(h
);
467 for ( ; idx
< n_buckets(h
); idx
++)
468 if (dibs
[idx
] != DIB_RAW_FREE
)
474 static void bucket_mark_free(HashmapBase
*h
, unsigned idx
) {
475 memzero(bucket_at(h
, idx
), hashmap_type_info
[h
->type
].entry_size
);
476 bucket_set_dib(h
, idx
, DIB_FREE
);
479 static void bucket_move_entry(HashmapBase
*h
, struct swap_entries
*swap
,
480 unsigned from
, unsigned to
) {
481 struct hashmap_base_entry
*e_from
, *e_to
;
485 e_from
= bucket_at_virtual(h
, swap
, from
);
486 e_to
= bucket_at_virtual(h
, swap
, to
);
488 memcpy(e_to
, e_from
, hashmap_type_info
[h
->type
].entry_size
);
490 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
491 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
492 struct ordered_hashmap_entry
*le
, *le_to
;
494 le_to
= (struct ordered_hashmap_entry
*) e_to
;
496 if (le_to
->iterate_next
!= IDX_NIL
) {
497 le
= (struct ordered_hashmap_entry
*)
498 bucket_at_virtual(h
, swap
, le_to
->iterate_next
);
499 le
->iterate_previous
= to
;
502 if (le_to
->iterate_previous
!= IDX_NIL
) {
503 le
= (struct ordered_hashmap_entry
*)
504 bucket_at_virtual(h
, swap
, le_to
->iterate_previous
);
505 le
->iterate_next
= to
;
508 if (lh
->iterate_list_head
== from
)
509 lh
->iterate_list_head
= to
;
510 if (lh
->iterate_list_tail
== from
)
511 lh
->iterate_list_tail
= to
;
515 static unsigned next_idx(HashmapBase
*h
, unsigned idx
) {
516 return (idx
+ 1U) % n_buckets(h
);
519 static unsigned prev_idx(HashmapBase
*h
, unsigned idx
) {
520 return (n_buckets(h
) + idx
- 1U) % n_buckets(h
);
523 static void *entry_value(HashmapBase
*h
, struct hashmap_base_entry
*e
) {
526 case HASHMAP_TYPE_PLAIN
:
527 case HASHMAP_TYPE_ORDERED
:
528 return ((struct plain_hashmap_entry
*)e
)->value
;
530 case HASHMAP_TYPE_SET
:
531 return (void*) e
->key
;
534 assert_not_reached("Unknown hashmap type");
538 static void base_remove_entry(HashmapBase
*h
, unsigned idx
) {
539 unsigned left
, right
, prev
, dib
;
540 dib_raw_t raw_dib
, *dibs
;
542 dibs
= dib_raw_ptr(h
);
543 assert(dibs
[idx
] != DIB_RAW_FREE
);
545 #if ENABLE_DEBUG_HASHMAP
546 h
->debug
.rem_count
++;
547 h
->debug
.last_rem_idx
= idx
;
551 /* Find the stop bucket ("right"). It is either free or has DIB == 0. */
552 for (right
= next_idx(h
, left
); ; right
= next_idx(h
, right
)) {
553 raw_dib
= dibs
[right
];
554 if (IN_SET(raw_dib
, 0, DIB_RAW_FREE
))
557 /* The buckets are not supposed to be all occupied and with DIB > 0.
558 * That would mean we could make everyone better off by shifting them
559 * backward. This scenario is impossible. */
560 assert(left
!= right
);
563 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
564 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
565 struct ordered_hashmap_entry
*le
= ordered_bucket_at(lh
, idx
);
567 if (le
->iterate_next
!= IDX_NIL
)
568 ordered_bucket_at(lh
, le
->iterate_next
)->iterate_previous
= le
->iterate_previous
;
570 lh
->iterate_list_tail
= le
->iterate_previous
;
572 if (le
->iterate_previous
!= IDX_NIL
)
573 ordered_bucket_at(lh
, le
->iterate_previous
)->iterate_next
= le
->iterate_next
;
575 lh
->iterate_list_head
= le
->iterate_next
;
578 /* Now shift all buckets in the interval (left, right) one step backwards */
579 for (prev
= left
, left
= next_idx(h
, left
); left
!= right
;
580 prev
= left
, left
= next_idx(h
, left
)) {
581 dib
= bucket_calculate_dib(h
, left
, dibs
[left
]);
583 bucket_move_entry(h
, NULL
, left
, prev
);
584 bucket_set_dib(h
, prev
, dib
- 1);
587 bucket_mark_free(h
, prev
);
591 #define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)
593 static unsigned hashmap_iterate_in_insertion_order(OrderedHashmap
*h
, Iterator
*i
) {
594 struct ordered_hashmap_entry
*e
;
600 if (i
->idx
== IDX_NIL
)
603 if (i
->idx
== IDX_FIRST
&& h
->iterate_list_head
== IDX_NIL
)
606 if (i
->idx
== IDX_FIRST
) {
607 idx
= h
->iterate_list_head
;
608 e
= ordered_bucket_at(h
, idx
);
611 e
= ordered_bucket_at(h
, idx
);
613 * We allow removing the current entry while iterating, but removal may cause
614 * a backward shift. The next entry may thus move one bucket to the left.
615 * To detect when it happens, we remember the key pointer of the entry we were
616 * going to iterate next. If it does not match, there was a backward shift.
618 if (e
->p
.b
.key
!= i
->next_key
) {
619 idx
= prev_idx(HASHMAP_BASE(h
), idx
);
620 e
= ordered_bucket_at(h
, idx
);
622 assert(e
->p
.b
.key
== i
->next_key
);
625 #if ENABLE_DEBUG_HASHMAP
629 if (e
->iterate_next
!= IDX_NIL
) {
630 struct ordered_hashmap_entry
*n
;
631 i
->idx
= e
->iterate_next
;
632 n
= ordered_bucket_at(h
, i
->idx
);
633 i
->next_key
= n
->p
.b
.key
;
644 static unsigned hashmap_iterate_in_internal_order(HashmapBase
*h
, Iterator
*i
) {
650 if (i
->idx
== IDX_NIL
)
653 if (i
->idx
== IDX_FIRST
) {
654 /* fast forward to the first occupied bucket */
655 if (h
->has_indirect
) {
656 i
->idx
= skip_free_buckets(h
, h
->indirect
.idx_lowest_entry
);
657 h
->indirect
.idx_lowest_entry
= i
->idx
;
659 i
->idx
= skip_free_buckets(h
, 0);
661 if (i
->idx
== IDX_NIL
)
664 struct hashmap_base_entry
*e
;
668 e
= bucket_at(h
, i
->idx
);
670 * We allow removing the current entry while iterating, but removal may cause
671 * a backward shift. The next entry may thus move one bucket to the left.
672 * To detect when it happens, we remember the key pointer of the entry we were
673 * going to iterate next. If it does not match, there was a backward shift.
675 if (e
->key
!= i
->next_key
)
676 e
= bucket_at(h
, --i
->idx
);
678 assert(e
->key
== i
->next_key
);
682 #if ENABLE_DEBUG_HASHMAP
686 i
->idx
= skip_free_buckets(h
, i
->idx
+ 1);
687 if (i
->idx
!= IDX_NIL
)
688 i
->next_key
= bucket_at(h
, i
->idx
)->key
;
699 static unsigned hashmap_iterate_entry(HashmapBase
*h
, Iterator
*i
) {
705 #if ENABLE_DEBUG_HASHMAP
706 if (i
->idx
== IDX_FIRST
) {
707 i
->put_count
= h
->debug
.put_count
;
708 i
->rem_count
= h
->debug
.rem_count
;
710 /* While iterating, must not add any new entries */
711 assert(i
->put_count
== h
->debug
.put_count
);
712 /* ... or remove entries other than the current one */
713 assert(i
->rem_count
== h
->debug
.rem_count
||
714 (i
->rem_count
== h
->debug
.rem_count
- 1 &&
715 i
->prev_idx
== h
->debug
.last_rem_idx
));
716 /* Reset our removals counter */
717 i
->rem_count
= h
->debug
.rem_count
;
721 return h
->type
== HASHMAP_TYPE_ORDERED
? hashmap_iterate_in_insertion_order((OrderedHashmap
*) h
, i
)
722 : hashmap_iterate_in_internal_order(h
, i
);
725 bool internal_hashmap_iterate(HashmapBase
*h
, Iterator
*i
, void **value
, const void **key
) {
726 struct hashmap_base_entry
*e
;
730 idx
= hashmap_iterate_entry(h
, i
);
731 if (idx
== IDX_NIL
) {
740 e
= bucket_at(h
, idx
);
741 data
= entry_value(h
, e
);
750 bool set_iterate(Set
*s
, Iterator
*i
, void **value
) {
751 return internal_hashmap_iterate(HASHMAP_BASE(s
), i
, value
, NULL
);
754 #define HASHMAP_FOREACH_IDX(idx, h, i) \
755 for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \
757 (idx) = hashmap_iterate_entry((h), &(i)))
759 IteratedCache
*internal_hashmap_iterated_cache_new(HashmapBase
*h
) {
760 IteratedCache
*cache
;
768 cache
= new0(IteratedCache
, 1);
778 static void reset_direct_storage(HashmapBase
*h
) {
779 const struct hashmap_type_info
*hi
= &hashmap_type_info
[h
->type
];
782 assert(!h
->has_indirect
);
784 p
= mempset(h
->direct
.storage
, 0, hi
->entry_size
* hi
->n_direct_buckets
);
785 memset(p
, DIB_RAW_INIT
, sizeof(dib_raw_t
) * hi
->n_direct_buckets
);
788 static struct HashmapBase
*hashmap_base_new(const struct hash_ops
*hash_ops
, enum HashmapType type HASHMAP_DEBUG_PARAMS
) {
790 const struct hashmap_type_info
*hi
= &hashmap_type_info
[type
];
793 use_pool
= is_main_thread();
795 h
= use_pool
? mempool_alloc0_tile(hi
->mempool
) : malloc0(hi
->head_size
);
801 h
->from_pool
= use_pool
;
802 h
->hash_ops
= hash_ops
? hash_ops
: &trivial_hash_ops
;
804 if (type
== HASHMAP_TYPE_ORDERED
) {
805 OrderedHashmap
*lh
= (OrderedHashmap
*)h
;
806 lh
->iterate_list_head
= lh
->iterate_list_tail
= IDX_NIL
;
809 reset_direct_storage(h
);
811 if (!shared_hash_key_initialized
) {
812 random_bytes(shared_hash_key
, sizeof(shared_hash_key
));
813 shared_hash_key_initialized
= true;
816 #if ENABLE_DEBUG_HASHMAP
817 h
->debug
.func
= func
;
818 h
->debug
.file
= file
;
819 h
->debug
.line
= line
;
820 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex
) == 0);
821 LIST_PREPEND(debug_list
, hashmap_debug_list
, &h
->debug
);
822 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex
) == 0);
828 Hashmap
*internal_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
829 return (Hashmap
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS
);
832 OrderedHashmap
*internal_ordered_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
833 return (OrderedHashmap
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS
);
836 Set
*internal_set_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
837 return (Set
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS
);
840 static int hashmap_base_ensure_allocated(HashmapBase
**h
, const struct hash_ops
*hash_ops
,
841 enum HashmapType type HASHMAP_DEBUG_PARAMS
) {
849 q
= hashmap_base_new(hash_ops
, type HASHMAP_DEBUG_PASS_ARGS
);
857 int internal_hashmap_ensure_allocated(Hashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
858 return hashmap_base_ensure_allocated((HashmapBase
**)h
, hash_ops
, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS
);
861 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
862 return hashmap_base_ensure_allocated((HashmapBase
**)h
, hash_ops
, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS
);
865 int internal_set_ensure_allocated(Set
**s
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
866 return hashmap_base_ensure_allocated((HashmapBase
**)s
, hash_ops
, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS
);
869 static void hashmap_free_no_clear(HashmapBase
*h
) {
870 assert(!h
->has_indirect
);
871 assert(!h
->n_direct_entries
);
873 #if ENABLE_DEBUG_HASHMAP
874 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex
) == 0);
875 LIST_REMOVE(debug_list
, hashmap_debug_list
, &h
->debug
);
876 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex
) == 0);
880 mempool_free_tile(hashmap_type_info
[h
->type
].mempool
, h
);
885 HashmapBase
*internal_hashmap_free(HashmapBase
*h
) {
887 /* Free the hashmap, but nothing in it */
890 internal_hashmap_clear(h
);
891 hashmap_free_no_clear(h
);
897 HashmapBase
*internal_hashmap_free_free(HashmapBase
*h
) {
899 /* Free the hashmap and all data objects in it, but not the
903 internal_hashmap_clear_free(h
);
904 hashmap_free_no_clear(h
);
910 Hashmap
*hashmap_free_free_free(Hashmap
*h
) {
912 /* Free the hashmap and all data and key objects in it */
915 hashmap_clear_free_free(h
);
916 hashmap_free_no_clear(HASHMAP_BASE(h
));
922 void internal_hashmap_clear(HashmapBase
*h
) {
926 if (h
->has_indirect
) {
927 free(h
->indirect
.storage
);
928 h
->has_indirect
= false;
931 h
->n_direct_entries
= 0;
932 reset_direct_storage(h
);
934 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
935 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
936 lh
->iterate_list_head
= lh
->iterate_list_tail
= IDX_NIL
;
942 void internal_hashmap_clear_free(HashmapBase
*h
) {
948 for (idx
= skip_free_buckets(h
, 0); idx
!= IDX_NIL
;
949 idx
= skip_free_buckets(h
, idx
+ 1))
950 free(entry_value(h
, bucket_at(h
, idx
)));
952 internal_hashmap_clear(h
);
955 void hashmap_clear_free_free(Hashmap
*h
) {
961 for (idx
= skip_free_buckets(HASHMAP_BASE(h
), 0); idx
!= IDX_NIL
;
962 idx
= skip_free_buckets(HASHMAP_BASE(h
), idx
+ 1)) {
963 struct plain_hashmap_entry
*e
= plain_bucket_at(h
, idx
);
964 free((void*)e
->b
.key
);
968 internal_hashmap_clear(HASHMAP_BASE(h
));
971 static int resize_buckets(HashmapBase
*h
, unsigned entries_add
);
974 * Finds an empty bucket to put an entry into, starting the scan at 'idx'.
975 * Performs Robin Hood swaps as it goes. The entry to put must be placed
976 * by the caller into swap slot IDX_PUT.
977 * If used for in-place resizing, may leave a displaced entry in swap slot
978 * IDX_PUT. Caller must rehash it next.
979 * Returns: true if it left a displaced entry to rehash next in IDX_PUT,
982 static bool hashmap_put_robin_hood(HashmapBase
*h
, unsigned idx
,
983 struct swap_entries
*swap
) {
984 dib_raw_t raw_dib
, *dibs
;
985 unsigned dib
, distance
;
987 #if ENABLE_DEBUG_HASHMAP
988 h
->debug
.put_count
++;
991 dibs
= dib_raw_ptr(h
);
993 for (distance
= 0; ; distance
++) {
995 if (IN_SET(raw_dib
, DIB_RAW_FREE
, DIB_RAW_REHASH
)) {
996 if (raw_dib
== DIB_RAW_REHASH
)
997 bucket_move_entry(h
, swap
, idx
, IDX_TMP
);
999 if (h
->has_indirect
&& h
->indirect
.idx_lowest_entry
> idx
)
1000 h
->indirect
.idx_lowest_entry
= idx
;
1002 bucket_set_dib(h
, idx
, distance
);
1003 bucket_move_entry(h
, swap
, IDX_PUT
, idx
);
1004 if (raw_dib
== DIB_RAW_REHASH
) {
1005 bucket_move_entry(h
, swap
, IDX_TMP
, IDX_PUT
);
1012 dib
= bucket_calculate_dib(h
, idx
, raw_dib
);
1014 if (dib
< distance
) {
1015 /* Found a wealthier entry. Go Robin Hood! */
1016 bucket_set_dib(h
, idx
, distance
);
1018 /* swap the entries */
1019 bucket_move_entry(h
, swap
, idx
, IDX_TMP
);
1020 bucket_move_entry(h
, swap
, IDX_PUT
, idx
);
1021 bucket_move_entry(h
, swap
, IDX_TMP
, IDX_PUT
);
1026 idx
= next_idx(h
, idx
);
1031 * Puts an entry into a hashmap, boldly - no check whether key already exists.
1032 * The caller must place the entry (only its key and value, not link indexes)
1033 * in swap slot IDX_PUT.
1034 * Caller must ensure: the key does not exist yet in the hashmap.
1035 * that resize is not needed if !may_resize.
1036 * Returns: 1 if entry was put successfully.
1037 * -ENOMEM if may_resize==true and resize failed with -ENOMEM.
1038 * Cannot return -ENOMEM if !may_resize.
1040 static int hashmap_base_put_boldly(HashmapBase
*h
, unsigned idx
,
1041 struct swap_entries
*swap
, bool may_resize
) {
1042 struct ordered_hashmap_entry
*new_entry
;
1045 assert(idx
< n_buckets(h
));
1047 new_entry
= bucket_at_swap(swap
, IDX_PUT
);
1050 r
= resize_buckets(h
, 1);
1054 idx
= bucket_hash(h
, new_entry
->p
.b
.key
);
1056 assert(n_entries(h
) < n_buckets(h
));
1058 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
1059 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
1061 new_entry
->iterate_next
= IDX_NIL
;
1062 new_entry
->iterate_previous
= lh
->iterate_list_tail
;
1064 if (lh
->iterate_list_tail
!= IDX_NIL
) {
1065 struct ordered_hashmap_entry
*old_tail
;
1067 old_tail
= ordered_bucket_at(lh
, lh
->iterate_list_tail
);
1068 assert(old_tail
->iterate_next
== IDX_NIL
);
1069 old_tail
->iterate_next
= IDX_PUT
;
1072 lh
->iterate_list_tail
= IDX_PUT
;
1073 if (lh
->iterate_list_head
== IDX_NIL
)
1074 lh
->iterate_list_head
= IDX_PUT
;
1077 assert_se(hashmap_put_robin_hood(h
, idx
, swap
) == false);
1080 #if ENABLE_DEBUG_HASHMAP
1081 h
->debug
.max_entries
= MAX(h
->debug
.max_entries
, n_entries(h
));
1088 #define hashmap_put_boldly(h, idx, swap, may_resize) \
1089 hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
1092 * Returns 0 if resize is not needed.
1093 * 1 if successfully resized.
1094 * -ENOMEM on allocation failure.
1096 static int resize_buckets(HashmapBase
*h
, unsigned entries_add
) {
1097 struct swap_entries swap
;
1099 dib_raw_t
*old_dibs
, *new_dibs
;
1100 const struct hashmap_type_info
*hi
;
1101 unsigned idx
, optimal_idx
;
1102 unsigned old_n_buckets
, new_n_buckets
, n_rehashed
, new_n_entries
;
1108 hi
= &hashmap_type_info
[h
->type
];
1109 new_n_entries
= n_entries(h
) + entries_add
;
1112 if (_unlikely_(new_n_entries
< entries_add
))
1115 /* For direct storage we allow 100% load, because it's tiny. */
1116 if (!h
->has_indirect
&& new_n_entries
<= hi
->n_direct_buckets
)
1120 * Load factor = n/m = 1 - (1/INV_KEEP_FREE).
1121 * From it follows: m = n + n/(INV_KEEP_FREE - 1)
1123 new_n_buckets
= new_n_entries
+ new_n_entries
/ (INV_KEEP_FREE
- 1);
1125 if (_unlikely_(new_n_buckets
< new_n_entries
))
1128 if (_unlikely_(new_n_buckets
> UINT_MAX
/ (hi
->entry_size
+ sizeof(dib_raw_t
))))
1131 old_n_buckets
= n_buckets(h
);
1133 if (_likely_(new_n_buckets
<= old_n_buckets
))
1136 new_shift
= log2u_round_up(MAX(
1137 new_n_buckets
* (hi
->entry_size
+ sizeof(dib_raw_t
)),
1138 2 * sizeof(struct direct_storage
)));
1140 /* Realloc storage (buckets and DIB array). */
1141 new_storage
= realloc(h
->has_indirect
? h
->indirect
.storage
: NULL
,
1146 /* Must upgrade direct to indirect storage. */
1147 if (!h
->has_indirect
) {
1148 memcpy(new_storage
, h
->direct
.storage
,
1149 old_n_buckets
* (hi
->entry_size
+ sizeof(dib_raw_t
)));
1150 h
->indirect
.n_entries
= h
->n_direct_entries
;
1151 h
->indirect
.idx_lowest_entry
= 0;
1152 h
->n_direct_entries
= 0;
1155 /* Get a new hash key. If we've just upgraded to indirect storage,
1156 * allow reusing a previously generated key. It's still a different key
1157 * from the shared one that we used for direct storage. */
1158 get_hash_key(h
->indirect
.hash_key
, !h
->has_indirect
);
1160 h
->has_indirect
= true;
1161 h
->indirect
.storage
= new_storage
;
1162 h
->indirect
.n_buckets
= (1U << new_shift
) /
1163 (hi
->entry_size
+ sizeof(dib_raw_t
));
1165 old_dibs
= (dib_raw_t
*)((uint8_t*) new_storage
+ hi
->entry_size
* old_n_buckets
);
1166 new_dibs
= dib_raw_ptr(h
);
1169 * Move the DIB array to the new place, replacing valid DIB values with
1170 * DIB_RAW_REHASH to indicate all of the used buckets need rehashing.
1171 * Note: Overlap is not possible, because we have at least doubled the
1172 * number of buckets and dib_raw_t is smaller than any entry type.
1174 for (idx
= 0; idx
< old_n_buckets
; idx
++) {
1175 assert(old_dibs
[idx
] != DIB_RAW_REHASH
);
1176 new_dibs
[idx
] = old_dibs
[idx
] == DIB_RAW_FREE
? DIB_RAW_FREE
1180 /* Zero the area of newly added entries (including the old DIB area) */
1181 memzero(bucket_at(h
, old_n_buckets
),
1182 (n_buckets(h
) - old_n_buckets
) * hi
->entry_size
);
1184 /* The upper half of the new DIB array needs initialization */
1185 memset(&new_dibs
[old_n_buckets
], DIB_RAW_INIT
,
1186 (n_buckets(h
) - old_n_buckets
) * sizeof(dib_raw_t
));
1188 /* Rehash entries that need it */
1190 for (idx
= 0; idx
< old_n_buckets
; idx
++) {
1191 if (new_dibs
[idx
] != DIB_RAW_REHASH
)
1194 optimal_idx
= bucket_hash(h
, bucket_at(h
, idx
)->key
);
1197 * Not much to do if by luck the entry hashes to its current
1198 * location. Just set its DIB.
1200 if (optimal_idx
== idx
) {
1206 new_dibs
[idx
] = DIB_RAW_FREE
;
1207 bucket_move_entry(h
, &swap
, idx
, IDX_PUT
);
1208 /* bucket_move_entry does not clear the source */
1209 memzero(bucket_at(h
, idx
), hi
->entry_size
);
1213 * Find the new bucket for the current entry. This may make
1214 * another entry homeless and load it into IDX_PUT.
1216 rehash_next
= hashmap_put_robin_hood(h
, optimal_idx
, &swap
);
1219 /* Did the current entry displace another one? */
1221 optimal_idx
= bucket_hash(h
, bucket_at_swap(&swap
, IDX_PUT
)->p
.b
.key
);
1222 } while (rehash_next
);
1225 assert(n_rehashed
== n_entries(h
));
1231 * Finds an entry with a matching key
1232 * Returns: index of the found entry, or IDX_NIL if not found.
1234 static unsigned base_bucket_scan(HashmapBase
*h
, unsigned idx
, const void *key
) {
1235 struct hashmap_base_entry
*e
;
1236 unsigned dib
, distance
;
1237 dib_raw_t
*dibs
= dib_raw_ptr(h
);
1239 assert(idx
< n_buckets(h
));
1241 for (distance
= 0; ; distance
++) {
1242 if (dibs
[idx
] == DIB_RAW_FREE
)
1245 dib
= bucket_calculate_dib(h
, idx
, dibs
[idx
]);
1249 if (dib
== distance
) {
1250 e
= bucket_at(h
, idx
);
1251 if (h
->hash_ops
->compare(e
->key
, key
) == 0)
1255 idx
= next_idx(h
, idx
);
1258 #define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
1260 int hashmap_put(Hashmap
*h
, const void *key
, void *value
) {
1261 struct swap_entries swap
;
1262 struct plain_hashmap_entry
*e
;
1267 hash
= bucket_hash(h
, key
);
1268 idx
= bucket_scan(h
, hash
, key
);
1269 if (idx
!= IDX_NIL
) {
1270 e
= plain_bucket_at(h
, idx
);
1271 if (e
->value
== value
)
1276 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1279 return hashmap_put_boldly(h
, hash
, &swap
, true);
1282 int set_put(Set
*s
, const void *key
) {
1283 struct swap_entries swap
;
1284 struct hashmap_base_entry
*e
;
1289 hash
= bucket_hash(s
, key
);
1290 idx
= bucket_scan(s
, hash
, key
);
1294 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1296 return hashmap_put_boldly(s
, hash
, &swap
, true);
1299 int hashmap_replace(Hashmap
*h
, const void *key
, void *value
) {
1300 struct swap_entries swap
;
1301 struct plain_hashmap_entry
*e
;
1306 hash
= bucket_hash(h
, key
);
1307 idx
= bucket_scan(h
, hash
, key
);
1308 if (idx
!= IDX_NIL
) {
1309 e
= plain_bucket_at(h
, idx
);
1310 #if ENABLE_DEBUG_HASHMAP
1311 /* Although the key is equal, the key pointer may have changed,
1312 * and this would break our assumption for iterating. So count
1313 * this operation as incompatible with iteration. */
1314 if (e
->b
.key
!= key
) {
1315 h
->b
.debug
.put_count
++;
1316 h
->b
.debug
.rem_count
++;
1317 h
->b
.debug
.last_rem_idx
= idx
;
1322 hashmap_set_dirty(h
);
1327 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1330 return hashmap_put_boldly(h
, hash
, &swap
, true);
1333 int hashmap_update(Hashmap
*h
, const void *key
, void *value
) {
1334 struct plain_hashmap_entry
*e
;
1339 hash
= bucket_hash(h
, key
);
1340 idx
= bucket_scan(h
, hash
, key
);
1344 e
= plain_bucket_at(h
, idx
);
1346 hashmap_set_dirty(h
);
1351 void *internal_hashmap_get(HashmapBase
*h
, const void *key
) {
1352 struct hashmap_base_entry
*e
;
1358 hash
= bucket_hash(h
, key
);
1359 idx
= bucket_scan(h
, hash
, key
);
1363 e
= bucket_at(h
, idx
);
1364 return entry_value(h
, e
);
1367 void *hashmap_get2(Hashmap
*h
, const void *key
, void **key2
) {
1368 struct plain_hashmap_entry
*e
;
1374 hash
= bucket_hash(h
, key
);
1375 idx
= bucket_scan(h
, hash
, key
);
1379 e
= plain_bucket_at(h
, idx
);
1381 *key2
= (void*) e
->b
.key
;
1386 bool internal_hashmap_contains(HashmapBase
*h
, const void *key
) {
1392 hash
= bucket_hash(h
, key
);
1393 return bucket_scan(h
, hash
, key
) != IDX_NIL
;
1396 void *internal_hashmap_remove(HashmapBase
*h
, const void *key
) {
1397 struct hashmap_base_entry
*e
;
1404 hash
= bucket_hash(h
, key
);
1405 idx
= bucket_scan(h
, hash
, key
);
1409 e
= bucket_at(h
, idx
);
1410 data
= entry_value(h
, e
);
1411 remove_entry(h
, idx
);
1416 void *hashmap_remove2(Hashmap
*h
, const void *key
, void **rkey
) {
1417 struct plain_hashmap_entry
*e
;
1427 hash
= bucket_hash(h
, key
);
1428 idx
= bucket_scan(h
, hash
, key
);
1429 if (idx
== IDX_NIL
) {
1435 e
= plain_bucket_at(h
, idx
);
1438 *rkey
= (void*) e
->b
.key
;
1440 remove_entry(h
, idx
);
1445 int hashmap_remove_and_put(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
1446 struct swap_entries swap
;
1447 struct plain_hashmap_entry
*e
;
1448 unsigned old_hash
, new_hash
, idx
;
1453 old_hash
= bucket_hash(h
, old_key
);
1454 idx
= bucket_scan(h
, old_hash
, old_key
);
1458 new_hash
= bucket_hash(h
, new_key
);
1459 if (bucket_scan(h
, new_hash
, new_key
) != IDX_NIL
)
1462 remove_entry(h
, idx
);
1464 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1467 assert_se(hashmap_put_boldly(h
, new_hash
, &swap
, false) == 1);
1472 int set_remove_and_put(Set
*s
, const void *old_key
, const void *new_key
) {
1473 struct swap_entries swap
;
1474 struct hashmap_base_entry
*e
;
1475 unsigned old_hash
, new_hash
, idx
;
1480 old_hash
= bucket_hash(s
, old_key
);
1481 idx
= bucket_scan(s
, old_hash
, old_key
);
1485 new_hash
= bucket_hash(s
, new_key
);
1486 if (bucket_scan(s
, new_hash
, new_key
) != IDX_NIL
)
1489 remove_entry(s
, idx
);
1491 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1493 assert_se(hashmap_put_boldly(s
, new_hash
, &swap
, false) == 1);
1498 int hashmap_remove_and_replace(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
1499 struct swap_entries swap
;
1500 struct plain_hashmap_entry
*e
;
1501 unsigned old_hash
, new_hash
, idx_old
, idx_new
;
1506 old_hash
= bucket_hash(h
, old_key
);
1507 idx_old
= bucket_scan(h
, old_hash
, old_key
);
1508 if (idx_old
== IDX_NIL
)
1511 old_key
= bucket_at(HASHMAP_BASE(h
), idx_old
)->key
;
1513 new_hash
= bucket_hash(h
, new_key
);
1514 idx_new
= bucket_scan(h
, new_hash
, new_key
);
1515 if (idx_new
!= IDX_NIL
)
1516 if (idx_old
!= idx_new
) {
1517 remove_entry(h
, idx_new
);
1518 /* Compensate for a possible backward shift. */
1519 if (old_key
!= bucket_at(HASHMAP_BASE(h
), idx_old
)->key
)
1520 idx_old
= prev_idx(HASHMAP_BASE(h
), idx_old
);
1521 assert(old_key
== bucket_at(HASHMAP_BASE(h
), idx_old
)->key
);
1524 remove_entry(h
, idx_old
);
1526 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1529 assert_se(hashmap_put_boldly(h
, new_hash
, &swap
, false) == 1);
1534 void *hashmap_remove_value(Hashmap
*h
, const void *key
, void *value
) {
1535 struct plain_hashmap_entry
*e
;
1541 hash
= bucket_hash(h
, key
);
1542 idx
= bucket_scan(h
, hash
, key
);
1546 e
= plain_bucket_at(h
, idx
);
1547 if (e
->value
!= value
)
1550 remove_entry(h
, idx
);
1555 static unsigned find_first_entry(HashmapBase
*h
) {
1556 Iterator i
= ITERATOR_FIRST
;
1558 if (!h
|| !n_entries(h
))
1561 return hashmap_iterate_entry(h
, &i
);
1564 void *internal_hashmap_first(HashmapBase
*h
) {
1567 idx
= find_first_entry(h
);
1571 return entry_value(h
, bucket_at(h
, idx
));
1574 void *internal_hashmap_first_key(HashmapBase
*h
) {
1575 struct hashmap_base_entry
*e
;
1578 idx
= find_first_entry(h
);
1582 e
= bucket_at(h
, idx
);
1583 return (void*) e
->key
;
1586 void *internal_hashmap_steal_first(HashmapBase
*h
) {
1587 struct hashmap_base_entry
*e
;
1591 idx
= find_first_entry(h
);
1595 e
= bucket_at(h
, idx
);
1596 data
= entry_value(h
, e
);
1597 remove_entry(h
, idx
);
1602 void *internal_hashmap_steal_first_key(HashmapBase
*h
) {
1603 struct hashmap_base_entry
*e
;
1607 idx
= find_first_entry(h
);
1611 e
= bucket_at(h
, idx
);
1612 key
= (void*) e
->key
;
1613 remove_entry(h
, idx
);
1618 unsigned internal_hashmap_size(HashmapBase
*h
) {
1623 return n_entries(h
);
1626 unsigned internal_hashmap_buckets(HashmapBase
*h
) {
1631 return n_buckets(h
);
1634 int internal_hashmap_merge(Hashmap
*h
, Hashmap
*other
) {
1640 HASHMAP_FOREACH_IDX(idx
, HASHMAP_BASE(other
), i
) {
1641 struct plain_hashmap_entry
*pe
= plain_bucket_at(other
, idx
);
1644 r
= hashmap_put(h
, pe
->b
.key
, pe
->value
);
1645 if (r
< 0 && r
!= -EEXIST
)
1652 int set_merge(Set
*s
, Set
*other
) {
1658 HASHMAP_FOREACH_IDX(idx
, HASHMAP_BASE(other
), i
) {
1659 struct set_entry
*se
= set_bucket_at(other
, idx
);
1662 r
= set_put(s
, se
->b
.key
);
1670 int internal_hashmap_reserve(HashmapBase
*h
, unsigned entries_add
) {
1675 r
= resize_buckets(h
, entries_add
);
1683 * The same as hashmap_merge(), but every new item from other is moved to h.
1684 * Keys already in h are skipped and stay in other.
1685 * Returns: 0 on success.
1686 * -ENOMEM on alloc failure, in which case no move has been done.
1688 int internal_hashmap_move(HashmapBase
*h
, HashmapBase
*other
) {
1689 struct swap_entries swap
;
1690 struct hashmap_base_entry
*e
, *n
;
1700 assert(other
->type
== h
->type
);
1703 * This reserves buckets for the worst case, where none of other's
1704 * entries are yet present in h. This is preferable to risking
1705 * an allocation failure in the middle of the moving and having to
1706 * rollback or return a partial result.
1708 r
= resize_buckets(h
, n_entries(other
));
1712 HASHMAP_FOREACH_IDX(idx
, other
, i
) {
1715 e
= bucket_at(other
, idx
);
1716 h_hash
= bucket_hash(h
, e
->key
);
1717 if (bucket_scan(h
, h_hash
, e
->key
) != IDX_NIL
)
1720 n
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1722 if (h
->type
!= HASHMAP_TYPE_SET
)
1723 ((struct plain_hashmap_entry
*) n
)->value
=
1724 ((struct plain_hashmap_entry
*) e
)->value
;
1725 assert_se(hashmap_put_boldly(h
, h_hash
, &swap
, false) == 1);
1727 remove_entry(other
, idx
);
1733 int internal_hashmap_move_one(HashmapBase
*h
, HashmapBase
*other
, const void *key
) {
1734 struct swap_entries swap
;
1735 unsigned h_hash
, other_hash
, idx
;
1736 struct hashmap_base_entry
*e
, *n
;
1741 h_hash
= bucket_hash(h
, key
);
1742 if (bucket_scan(h
, h_hash
, key
) != IDX_NIL
)
1748 assert(other
->type
== h
->type
);
1750 other_hash
= bucket_hash(other
, key
);
1751 idx
= bucket_scan(other
, other_hash
, key
);
1755 e
= bucket_at(other
, idx
);
1757 n
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1759 if (h
->type
!= HASHMAP_TYPE_SET
)
1760 ((struct plain_hashmap_entry
*) n
)->value
=
1761 ((struct plain_hashmap_entry
*) e
)->value
;
1762 r
= hashmap_put_boldly(h
, h_hash
, &swap
, true);
1766 remove_entry(other
, idx
);
1770 HashmapBase
*internal_hashmap_copy(HashmapBase
*h
) {
1776 copy
= hashmap_base_new(h
->hash_ops
, h
->type HASHMAP_DEBUG_SRC_ARGS
);
1781 case HASHMAP_TYPE_PLAIN
:
1782 case HASHMAP_TYPE_ORDERED
:
1783 r
= hashmap_merge((Hashmap
*)copy
, (Hashmap
*)h
);
1785 case HASHMAP_TYPE_SET
:
1786 r
= set_merge((Set
*)copy
, (Set
*)h
);
1789 assert_not_reached("Unknown hashmap type");
1793 internal_hashmap_free(copy
);
1800 char **internal_hashmap_get_strv(HashmapBase
*h
) {
1805 sv
= new(char*, n_entries(h
)+1);
1810 HASHMAP_FOREACH_IDX(idx
, h
, i
)
1811 sv
[n
++] = entry_value(h
, bucket_at(h
, idx
));
1817 void *ordered_hashmap_next(OrderedHashmap
*h
, const void *key
) {
1818 struct ordered_hashmap_entry
*e
;
1824 hash
= bucket_hash(h
, key
);
1825 idx
= bucket_scan(h
, hash
, key
);
1829 e
= ordered_bucket_at(h
, idx
);
1830 if (e
->iterate_next
== IDX_NIL
)
1832 return ordered_bucket_at(h
, e
->iterate_next
)->p
.value
;
1835 int set_consume(Set
*s
, void *value
) {
1841 r
= set_put(s
, value
);
1848 int set_put_strdup(Set
*s
, const char *p
) {
1854 if (set_contains(s
, (char*) p
))
1861 return set_consume(s
, c
);
1864 int set_put_strdupv(Set
*s
, char **l
) {
1870 STRV_FOREACH(i
, l
) {
1871 r
= set_put_strdup(s
, *i
);
1881 int set_put_strsplit(Set
*s
, const char *v
, const char *separators
, ExtractFlags flags
) {
1891 r
= extract_first_word(&p
, &word
, separators
, flags
);
1895 r
= set_consume(s
, word
);
1901 /* expand the cachemem if needed, return true if newly (re)activated. */
1902 static int cachemem_maintain(CacheMem
*mem
, unsigned size
) {
1905 if (!GREEDY_REALLOC(mem
->ptr
, mem
->n_allocated
, size
)) {
1918 int iterated_cache_get(IteratedCache
*cache
, const void ***res_keys
, const void ***res_values
, unsigned *res_n_entries
) {
1919 bool sync_keys
= false, sync_values
= false;
1924 assert(cache
->hashmap
);
1926 size
= n_entries(cache
->hashmap
);
1929 r
= cachemem_maintain(&cache
->keys
, size
);
1935 cache
->keys
.active
= false;
1938 r
= cachemem_maintain(&cache
->values
, size
);
1944 cache
->values
.active
= false;
1946 if (cache
->hashmap
->dirty
) {
1947 if (cache
->keys
.active
)
1949 if (cache
->values
.active
)
1952 cache
->hashmap
->dirty
= false;
1955 if (sync_keys
|| sync_values
) {
1960 HASHMAP_FOREACH_IDX(idx
, cache
->hashmap
, iter
) {
1961 struct hashmap_base_entry
*e
;
1963 e
= bucket_at(cache
->hashmap
, idx
);
1966 cache
->keys
.ptr
[i
] = e
->key
;
1968 cache
->values
.ptr
[i
] = entry_value(cache
->hashmap
, e
);
1974 *res_keys
= cache
->keys
.ptr
;
1976 *res_values
= cache
->values
.ptr
;
1978 *res_n_entries
= size
;
1983 IteratedCache
*iterated_cache_free(IteratedCache
*cache
) {
1985 free(cache
->keys
.ptr
);
1986 free(cache
->values
.ptr
);