2 This file is part of systemd.
4 Copyright 2010 Lennart Poettering
5 Copyright 2014 Michal Schmidt
7 systemd is free software; you can redistribute it and/or modify it
8 under the terms of the GNU Lesser General Public License as published by
9 the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version.
12 systemd is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Lesser General Public License for more details.
17 You should have received a copy of the GNU Lesser General Public License
18 along with systemd; If not, see <http://www.gnu.org/licenses/>.
26 #include "alloc-util.h"
31 #include "process-util.h"
32 #include "random-util.h"
34 #include "siphash24.h"
35 #include "string-util.h"
39 #if ENABLE_DEBUG_HASHMAP
45 * Implementation of hashmaps.
47 * - uses less RAM compared to closed addressing (chaining), because
48 * our entries are small (especially in Sets, which tend to contain
49 * the majority of entries in systemd).
50 * Collision resolution: Robin Hood
51 * - tends to equalize displacement of entries from their optimal buckets.
52 * Probe sequence: linear
53 * - though theoretically worse than random probing/uniform hashing/double
54 * hashing, it is good for cache locality.
57 * Celis, P. 1986. Robin Hood Hashing.
58 * Ph.D. Dissertation. University of Waterloo, Waterloo, Ont., Canada, Canada.
59 * https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
60 * - The results are derived for random probing. Suggests deletion with
61 * tombstones and two mean-centered search methods. None of that works
62 * well for linear probing.
64 * Janson, S. 2005. Individual displacements for linear probing hashing with different insertion policies.
65 * ACM Trans. Algorithms 1, 2 (October 2005), 177-213.
66 * DOI=10.1145/1103963.1103964 http://doi.acm.org/10.1145/1103963.1103964
67 * http://www.math.uu.se/~svante/papers/sj157.pdf
68 * - Applies to Robin Hood with linear probing. Contains remarks on
69 * the unsuitability of mean-centered search with linear probing.
71 * Viola, A. 2005. Exact distribution of individual displacements in linear probing hashing.
72 * ACM Trans. Algorithms 1, 2 (October 2005), 214-242.
73 * DOI=10.1145/1103963.1103965 http://doi.acm.org/10.1145/1103963.1103965
74 * - Similar to Janson. Note that Viola writes about C_{m,n} (number of probes
75 * in a successful search), and Janson writes about displacement. C = d + 1.
77 * Goossaert, E. 2013. Robin Hood hashing: backward shift deletion.
78 * http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
79 * - Explanation of backward shift deletion with pictures.
81 * Khuong, P. 2013. The Other Robin Hood Hashing.
82 * http://www.pvk.ca/Blog/2013/11/26/the-other-robin-hood-hashing/
83 * - Short summary of random vs. linear probing, and tombstones vs. backward shift.
87 * XXX Ideas for improvement:
88 * For unordered hashmaps, randomize iteration order, similarly to Perl:
89 * http://blog.booking.com/hardening-perls-hash-function.html
92 /* INV_KEEP_FREE = 1 / (1 - max_load_factor)
93 * e.g. 1 / (1 - 0.8) = 5 ... keep one fifth of the buckets free. */
94 #define INV_KEEP_FREE 5U
96 /* Fields common to entries of all hashmap/set types */
97 struct hashmap_base_entry
{
101 /* Entry types for specific hashmap/set types
102 * hashmap_base_entry must be at the beginning of each entry struct. */
104 struct plain_hashmap_entry
{
105 struct hashmap_base_entry b
;
109 struct ordered_hashmap_entry
{
110 struct plain_hashmap_entry p
;
111 unsigned iterate_next
, iterate_previous
;
115 struct hashmap_base_entry b
;
118 /* In several functions it is advantageous to have the hash table extended
119 * virtually by a couple of additional buckets. We reserve special index values
120 * for these "swap" buckets. */
121 #define _IDX_SWAP_BEGIN (UINT_MAX - 3)
122 #define IDX_PUT (_IDX_SWAP_BEGIN + 0)
123 #define IDX_TMP (_IDX_SWAP_BEGIN + 1)
124 #define _IDX_SWAP_END (_IDX_SWAP_BEGIN + 2)
126 #define IDX_FIRST (UINT_MAX - 1) /* special index for freshly initialized iterators */
127 #define IDX_NIL UINT_MAX /* special index value meaning "none" or "end" */
129 assert_cc(IDX_FIRST
== _IDX_SWAP_END
);
130 assert_cc(IDX_FIRST
== _IDX_ITERATOR_FIRST
);
132 /* Storage space for the "swap" buckets.
133 * All entry types can fit into a ordered_hashmap_entry. */
134 struct swap_entries
{
135 struct ordered_hashmap_entry e
[_IDX_SWAP_END
- _IDX_SWAP_BEGIN
];
138 /* Distance from Initial Bucket */
139 typedef uint8_t dib_raw_t
;
140 #define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */
141 #define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */
142 #define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */
143 #define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */
145 #define DIB_FREE UINT_MAX
147 #if ENABLE_DEBUG_HASHMAP
148 struct hashmap_debug_info
{
149 LIST_FIELDS(struct hashmap_debug_info
, debug_list
);
150 unsigned max_entries
; /* high watermark of n_entries */
152 /* who allocated this hashmap */
157 /* fields to detect modification while iterating */
158 unsigned put_count
; /* counts puts into the hashmap */
159 unsigned rem_count
; /* counts removals from hashmap */
160 unsigned last_rem_idx
; /* remembers last removal index */
163 /* Tracks all existing hashmaps. Get at it from gdb. See sd_dump_hashmaps.py */
164 static LIST_HEAD(struct hashmap_debug_info
, hashmap_debug_list
);
165 static pthread_mutex_t hashmap_debug_list_mutex
= PTHREAD_MUTEX_INITIALIZER
;
167 #define HASHMAP_DEBUG_FIELDS struct hashmap_debug_info debug;
169 #else /* !ENABLE_DEBUG_HASHMAP */
170 #define HASHMAP_DEBUG_FIELDS
171 #endif /* ENABLE_DEBUG_HASHMAP */
175 HASHMAP_TYPE_ORDERED
,
180 struct _packed_ indirect_storage
{
181 void *storage
; /* where buckets and DIBs are stored */
182 uint8_t hash_key
[HASH_KEY_SIZE
]; /* hash key; changes during resize */
184 unsigned n_entries
; /* number of stored entries */
185 unsigned n_buckets
; /* number of buckets */
187 unsigned idx_lowest_entry
; /* Index below which all buckets are free.
188 Makes "while(hashmap_steal_first())" loops
189 O(n) instead of O(n^2) for unordered hashmaps. */
190 uint8_t _pad
[3]; /* padding for the whole HashmapBase */
191 /* The bitfields in HashmapBase complete the alignment of the whole thing. */
194 struct direct_storage
{
195 /* This gives us 39 bytes on 64bit, or 35 bytes on 32bit.
196 * That's room for 4 set_entries + 4 DIB bytes + 3 unused bytes on 64bit,
197 * or 7 set_entries + 7 DIB bytes + 0 unused bytes on 32bit. */
198 uint8_t storage
[sizeof(struct indirect_storage
)];
201 #define DIRECT_BUCKETS(entry_t) \
202 (sizeof(struct direct_storage) / (sizeof(entry_t) + sizeof(dib_raw_t)))
204 /* We should be able to store at least one entry directly. */
205 assert_cc(DIRECT_BUCKETS(struct ordered_hashmap_entry
) >= 1);
207 /* We have 3 bits for n_direct_entries. */
208 assert_cc(DIRECT_BUCKETS(struct set_entry
) < (1 << 3));
210 /* Hashmaps with directly stored entries all use this shared hash key.
211 * It's no big deal if the key is guessed, because there can be only
212 * a handful of directly stored entries in a hashmap. When a hashmap
213 * outgrows direct storage, it gets its own key for indirect storage. */
214 static uint8_t shared_hash_key
[HASH_KEY_SIZE
];
215 static bool shared_hash_key_initialized
;
217 /* Fields that all hashmap/set types must have */
219 const struct hash_ops
*hash_ops
; /* hash and compare ops to use */
222 struct indirect_storage indirect
; /* if has_indirect */
223 struct direct_storage direct
; /* if !has_indirect */
226 enum HashmapType type
:2; /* HASHMAP_TYPE_* */
227 bool has_indirect
:1; /* whether indirect storage is used */
228 unsigned n_direct_entries
:3; /* Number of entries in direct storage.
229 * Only valid if !has_indirect. */
230 bool from_pool
:1; /* whether was allocated from mempool */
231 HASHMAP_DEBUG_FIELDS
/* optional hashmap_debug_info */
234 /* Specific hash types
235 * HashmapBase must be at the beginning of each hashmap struct. */
238 struct HashmapBase b
;
241 struct OrderedHashmap
{
242 struct HashmapBase b
;
243 unsigned iterate_list_head
, iterate_list_tail
;
247 struct HashmapBase b
;
250 DEFINE_MEMPOOL(hashmap_pool
, Hashmap
, 8);
251 DEFINE_MEMPOOL(ordered_hashmap_pool
, OrderedHashmap
, 8);
252 /* No need for a separate Set pool */
253 assert_cc(sizeof(Hashmap
) == sizeof(Set
));
255 struct hashmap_type_info
{
258 struct mempool
*mempool
;
259 unsigned n_direct_buckets
;
262 static const struct hashmap_type_info hashmap_type_info
[_HASHMAP_TYPE_MAX
] = {
263 [HASHMAP_TYPE_PLAIN
] = {
264 .head_size
= sizeof(Hashmap
),
265 .entry_size
= sizeof(struct plain_hashmap_entry
),
266 .mempool
= &hashmap_pool
,
267 .n_direct_buckets
= DIRECT_BUCKETS(struct plain_hashmap_entry
),
269 [HASHMAP_TYPE_ORDERED
] = {
270 .head_size
= sizeof(OrderedHashmap
),
271 .entry_size
= sizeof(struct ordered_hashmap_entry
),
272 .mempool
= &ordered_hashmap_pool
,
273 .n_direct_buckets
= DIRECT_BUCKETS(struct ordered_hashmap_entry
),
275 [HASHMAP_TYPE_SET
] = {
276 .head_size
= sizeof(Set
),
277 .entry_size
= sizeof(struct set_entry
),
278 .mempool
= &hashmap_pool
,
279 .n_direct_buckets
= DIRECT_BUCKETS(struct set_entry
),
284 __attribute__((destructor
)) static void cleanup_pools(void) {
285 _cleanup_free_
char *t
= NULL
;
288 /* Be nice to valgrind */
290 /* The pool is only allocated by the main thread, but the memory can
291 * be passed to other threads. Let's clean up if we are the main thread
292 * and no other threads are live. */
293 if (!is_main_thread())
296 r
= get_proc_field("/proc/self/status", "Threads", WHITESPACE
, &t
);
297 if (r
< 0 || !streq(t
, "1"))
300 mempool_drop(&hashmap_pool
);
301 mempool_drop(&ordered_hashmap_pool
);
305 static unsigned n_buckets(HashmapBase
*h
) {
306 return h
->has_indirect
? h
->indirect
.n_buckets
307 : hashmap_type_info
[h
->type
].n_direct_buckets
;
310 static unsigned n_entries(HashmapBase
*h
) {
311 return h
->has_indirect
? h
->indirect
.n_entries
312 : h
->n_direct_entries
;
315 static void n_entries_inc(HashmapBase
*h
) {
317 h
->indirect
.n_entries
++;
319 h
->n_direct_entries
++;
322 static void n_entries_dec(HashmapBase
*h
) {
324 h
->indirect
.n_entries
--;
326 h
->n_direct_entries
--;
329 static void *storage_ptr(HashmapBase
*h
) {
330 return h
->has_indirect
? h
->indirect
.storage
334 static uint8_t *hash_key(HashmapBase
*h
) {
335 return h
->has_indirect
? h
->indirect
.hash_key
339 static unsigned base_bucket_hash(HashmapBase
*h
, const void *p
) {
340 struct siphash state
;
343 siphash24_init(&state
, hash_key(h
));
345 h
->hash_ops
->hash(p
, &state
);
347 hash
= siphash24_finalize(&state
);
349 return (unsigned) (hash
% n_buckets(h
));
351 #define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p)
353 static void get_hash_key(uint8_t hash_key
[HASH_KEY_SIZE
], bool reuse_is_ok
) {
354 static uint8_t current
[HASH_KEY_SIZE
];
355 static bool current_initialized
= false;
357 /* Returns a hash function key to use. In order to keep things
358 * fast we will not generate a new key each time we allocate a
359 * new hash table. Instead, we'll just reuse the most recently
360 * generated one, except if we never generated one or when we
361 * are rehashing an entire hash table because we reached a
364 if (!current_initialized
|| !reuse_is_ok
) {
365 random_bytes(current
, sizeof(current
));
366 current_initialized
= true;
369 memcpy(hash_key
, current
, sizeof(current
));
372 static struct hashmap_base_entry
*bucket_at(HashmapBase
*h
, unsigned idx
) {
373 return (struct hashmap_base_entry
*)
374 ((uint8_t*) storage_ptr(h
) + idx
* hashmap_type_info
[h
->type
].entry_size
);
377 static struct plain_hashmap_entry
*plain_bucket_at(Hashmap
*h
, unsigned idx
) {
378 return (struct plain_hashmap_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
381 static struct ordered_hashmap_entry
*ordered_bucket_at(OrderedHashmap
*h
, unsigned idx
) {
382 return (struct ordered_hashmap_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
385 static struct set_entry
*set_bucket_at(Set
*h
, unsigned idx
) {
386 return (struct set_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
389 static struct ordered_hashmap_entry
*bucket_at_swap(struct swap_entries
*swap
, unsigned idx
) {
390 return &swap
->e
[idx
- _IDX_SWAP_BEGIN
];
393 /* Returns a pointer to the bucket at index idx.
394 * Understands real indexes and swap indexes, hence "_virtual". */
395 static struct hashmap_base_entry
*bucket_at_virtual(HashmapBase
*h
, struct swap_entries
*swap
,
397 if (idx
< _IDX_SWAP_BEGIN
)
398 return bucket_at(h
, idx
);
400 if (idx
< _IDX_SWAP_END
)
401 return &bucket_at_swap(swap
, idx
)->p
.b
;
403 assert_not_reached("Invalid index");
406 static dib_raw_t
*dib_raw_ptr(HashmapBase
*h
) {
408 ((uint8_t*) storage_ptr(h
) + hashmap_type_info
[h
->type
].entry_size
* n_buckets(h
));
411 static unsigned bucket_distance(HashmapBase
*h
, unsigned idx
, unsigned from
) {
412 return idx
>= from
? idx
- from
413 : n_buckets(h
) + idx
- from
;
416 static unsigned bucket_calculate_dib(HashmapBase
*h
, unsigned idx
, dib_raw_t raw_dib
) {
417 unsigned initial_bucket
;
419 if (raw_dib
== DIB_RAW_FREE
)
422 if (_likely_(raw_dib
< DIB_RAW_OVERFLOW
))
426 * Having an overflow DIB value is very unlikely. The hash function
427 * would have to be bad. For example, in a table of size 2^24 filled
428 * to load factor 0.9 the maximum observed DIB is only about 60.
429 * In theory (assuming I used Maxima correctly), for an infinite size
430 * hash table with load factor 0.8 the probability of a given entry
431 * having DIB > 40 is 1.9e-8.
432 * This returns the correct DIB value by recomputing the hash value in
433 * the unlikely case. XXX Hitting this case could be a hint to rehash.
435 initial_bucket
= bucket_hash(h
, bucket_at(h
, idx
)->key
);
436 return bucket_distance(h
, idx
, initial_bucket
);
439 static void bucket_set_dib(HashmapBase
*h
, unsigned idx
, unsigned dib
) {
440 dib_raw_ptr(h
)[idx
] = dib
!= DIB_FREE
? MIN(dib
, DIB_RAW_OVERFLOW
) : DIB_RAW_FREE
;
443 static unsigned skip_free_buckets(HashmapBase
*h
, unsigned idx
) {
446 dibs
= dib_raw_ptr(h
);
448 for ( ; idx
< n_buckets(h
); idx
++)
449 if (dibs
[idx
] != DIB_RAW_FREE
)
455 static void bucket_mark_free(HashmapBase
*h
, unsigned idx
) {
456 memzero(bucket_at(h
, idx
), hashmap_type_info
[h
->type
].entry_size
);
457 bucket_set_dib(h
, idx
, DIB_FREE
);
460 static void bucket_move_entry(HashmapBase
*h
, struct swap_entries
*swap
,
461 unsigned from
, unsigned to
) {
462 struct hashmap_base_entry
*e_from
, *e_to
;
466 e_from
= bucket_at_virtual(h
, swap
, from
);
467 e_to
= bucket_at_virtual(h
, swap
, to
);
469 memcpy(e_to
, e_from
, hashmap_type_info
[h
->type
].entry_size
);
471 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
472 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
473 struct ordered_hashmap_entry
*le
, *le_to
;
475 le_to
= (struct ordered_hashmap_entry
*) e_to
;
477 if (le_to
->iterate_next
!= IDX_NIL
) {
478 le
= (struct ordered_hashmap_entry
*)
479 bucket_at_virtual(h
, swap
, le_to
->iterate_next
);
480 le
->iterate_previous
= to
;
483 if (le_to
->iterate_previous
!= IDX_NIL
) {
484 le
= (struct ordered_hashmap_entry
*)
485 bucket_at_virtual(h
, swap
, le_to
->iterate_previous
);
486 le
->iterate_next
= to
;
489 if (lh
->iterate_list_head
== from
)
490 lh
->iterate_list_head
= to
;
491 if (lh
->iterate_list_tail
== from
)
492 lh
->iterate_list_tail
= to
;
496 static unsigned next_idx(HashmapBase
*h
, unsigned idx
) {
497 return (idx
+ 1U) % n_buckets(h
);
500 static unsigned prev_idx(HashmapBase
*h
, unsigned idx
) {
501 return (n_buckets(h
) + idx
- 1U) % n_buckets(h
);
504 static void *entry_value(HashmapBase
*h
, struct hashmap_base_entry
*e
) {
507 case HASHMAP_TYPE_PLAIN
:
508 case HASHMAP_TYPE_ORDERED
:
509 return ((struct plain_hashmap_entry
*)e
)->value
;
511 case HASHMAP_TYPE_SET
:
512 return (void*) e
->key
;
515 assert_not_reached("Unknown hashmap type");
519 static void base_remove_entry(HashmapBase
*h
, unsigned idx
) {
520 unsigned left
, right
, prev
, dib
;
521 dib_raw_t raw_dib
, *dibs
;
523 dibs
= dib_raw_ptr(h
);
524 assert(dibs
[idx
] != DIB_RAW_FREE
);
526 #if ENABLE_DEBUG_HASHMAP
527 h
->debug
.rem_count
++;
528 h
->debug
.last_rem_idx
= idx
;
532 /* Find the stop bucket ("right"). It is either free or has DIB == 0. */
533 for (right
= next_idx(h
, left
); ; right
= next_idx(h
, right
)) {
534 raw_dib
= dibs
[right
];
535 if (IN_SET(raw_dib
, 0, DIB_RAW_FREE
))
538 /* The buckets are not supposed to be all occupied and with DIB > 0.
539 * That would mean we could make everyone better off by shifting them
540 * backward. This scenario is impossible. */
541 assert(left
!= right
);
544 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
545 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
546 struct ordered_hashmap_entry
*le
= ordered_bucket_at(lh
, idx
);
548 if (le
->iterate_next
!= IDX_NIL
)
549 ordered_bucket_at(lh
, le
->iterate_next
)->iterate_previous
= le
->iterate_previous
;
551 lh
->iterate_list_tail
= le
->iterate_previous
;
553 if (le
->iterate_previous
!= IDX_NIL
)
554 ordered_bucket_at(lh
, le
->iterate_previous
)->iterate_next
= le
->iterate_next
;
556 lh
->iterate_list_head
= le
->iterate_next
;
559 /* Now shift all buckets in the interval (left, right) one step backwards */
560 for (prev
= left
, left
= next_idx(h
, left
); left
!= right
;
561 prev
= left
, left
= next_idx(h
, left
)) {
562 dib
= bucket_calculate_dib(h
, left
, dibs
[left
]);
564 bucket_move_entry(h
, NULL
, left
, prev
);
565 bucket_set_dib(h
, prev
, dib
- 1);
568 bucket_mark_free(h
, prev
);
571 #define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)
573 static unsigned hashmap_iterate_in_insertion_order(OrderedHashmap
*h
, Iterator
*i
) {
574 struct ordered_hashmap_entry
*e
;
580 if (i
->idx
== IDX_NIL
)
583 if (i
->idx
== IDX_FIRST
&& h
->iterate_list_head
== IDX_NIL
)
586 if (i
->idx
== IDX_FIRST
) {
587 idx
= h
->iterate_list_head
;
588 e
= ordered_bucket_at(h
, idx
);
591 e
= ordered_bucket_at(h
, idx
);
593 * We allow removing the current entry while iterating, but removal may cause
594 * a backward shift. The next entry may thus move one bucket to the left.
595 * To detect when it happens, we remember the key pointer of the entry we were
596 * going to iterate next. If it does not match, there was a backward shift.
598 if (e
->p
.b
.key
!= i
->next_key
) {
599 idx
= prev_idx(HASHMAP_BASE(h
), idx
);
600 e
= ordered_bucket_at(h
, idx
);
602 assert(e
->p
.b
.key
== i
->next_key
);
605 #if ENABLE_DEBUG_HASHMAP
609 if (e
->iterate_next
!= IDX_NIL
) {
610 struct ordered_hashmap_entry
*n
;
611 i
->idx
= e
->iterate_next
;
612 n
= ordered_bucket_at(h
, i
->idx
);
613 i
->next_key
= n
->p
.b
.key
;
624 static unsigned hashmap_iterate_in_internal_order(HashmapBase
*h
, Iterator
*i
) {
630 if (i
->idx
== IDX_NIL
)
633 if (i
->idx
== IDX_FIRST
) {
634 /* fast forward to the first occupied bucket */
635 if (h
->has_indirect
) {
636 i
->idx
= skip_free_buckets(h
, h
->indirect
.idx_lowest_entry
);
637 h
->indirect
.idx_lowest_entry
= i
->idx
;
639 i
->idx
= skip_free_buckets(h
, 0);
641 if (i
->idx
== IDX_NIL
)
644 struct hashmap_base_entry
*e
;
648 e
= bucket_at(h
, i
->idx
);
650 * We allow removing the current entry while iterating, but removal may cause
651 * a backward shift. The next entry may thus move one bucket to the left.
652 * To detect when it happens, we remember the key pointer of the entry we were
653 * going to iterate next. If it does not match, there was a backward shift.
655 if (e
->key
!= i
->next_key
)
656 e
= bucket_at(h
, --i
->idx
);
658 assert(e
->key
== i
->next_key
);
662 #if ENABLE_DEBUG_HASHMAP
666 i
->idx
= skip_free_buckets(h
, i
->idx
+ 1);
667 if (i
->idx
!= IDX_NIL
)
668 i
->next_key
= bucket_at(h
, i
->idx
)->key
;
679 static unsigned hashmap_iterate_entry(HashmapBase
*h
, Iterator
*i
) {
685 #if ENABLE_DEBUG_HASHMAP
686 if (i
->idx
== IDX_FIRST
) {
687 i
->put_count
= h
->debug
.put_count
;
688 i
->rem_count
= h
->debug
.rem_count
;
690 /* While iterating, must not add any new entries */
691 assert(i
->put_count
== h
->debug
.put_count
);
692 /* ... or remove entries other than the current one */
693 assert(i
->rem_count
== h
->debug
.rem_count
||
694 (i
->rem_count
== h
->debug
.rem_count
- 1 &&
695 i
->prev_idx
== h
->debug
.last_rem_idx
));
696 /* Reset our removals counter */
697 i
->rem_count
= h
->debug
.rem_count
;
701 return h
->type
== HASHMAP_TYPE_ORDERED
? hashmap_iterate_in_insertion_order((OrderedHashmap
*) h
, i
)
702 : hashmap_iterate_in_internal_order(h
, i
);
705 bool internal_hashmap_iterate(HashmapBase
*h
, Iterator
*i
, void **value
, const void **key
) {
706 struct hashmap_base_entry
*e
;
710 idx
= hashmap_iterate_entry(h
, i
);
711 if (idx
== IDX_NIL
) {
720 e
= bucket_at(h
, idx
);
721 data
= entry_value(h
, e
);
730 bool set_iterate(Set
*s
, Iterator
*i
, void **value
) {
731 return internal_hashmap_iterate(HASHMAP_BASE(s
), i
, value
, NULL
);
734 #define HASHMAP_FOREACH_IDX(idx, h, i) \
735 for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \
737 (idx) = hashmap_iterate_entry((h), &(i)))
739 static void reset_direct_storage(HashmapBase
*h
) {
740 const struct hashmap_type_info
*hi
= &hashmap_type_info
[h
->type
];
743 assert(!h
->has_indirect
);
745 p
= mempset(h
->direct
.storage
, 0, hi
->entry_size
* hi
->n_direct_buckets
);
746 memset(p
, DIB_RAW_INIT
, sizeof(dib_raw_t
) * hi
->n_direct_buckets
);
749 static struct HashmapBase
*hashmap_base_new(const struct hash_ops
*hash_ops
, enum HashmapType type HASHMAP_DEBUG_PARAMS
) {
751 const struct hashmap_type_info
*hi
= &hashmap_type_info
[type
];
754 use_pool
= is_main_thread();
756 h
= use_pool
? mempool_alloc0_tile(hi
->mempool
) : malloc0(hi
->head_size
);
762 h
->from_pool
= use_pool
;
763 h
->hash_ops
= hash_ops
? hash_ops
: &trivial_hash_ops
;
765 if (type
== HASHMAP_TYPE_ORDERED
) {
766 OrderedHashmap
*lh
= (OrderedHashmap
*)h
;
767 lh
->iterate_list_head
= lh
->iterate_list_tail
= IDX_NIL
;
770 reset_direct_storage(h
);
772 if (!shared_hash_key_initialized
) {
773 random_bytes(shared_hash_key
, sizeof(shared_hash_key
));
774 shared_hash_key_initialized
= true;
777 #if ENABLE_DEBUG_HASHMAP
778 h
->debug
.func
= func
;
779 h
->debug
.file
= file
;
780 h
->debug
.line
= line
;
781 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex
) == 0);
782 LIST_PREPEND(debug_list
, hashmap_debug_list
, &h
->debug
);
783 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex
) == 0);
789 Hashmap
*internal_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
790 return (Hashmap
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS
);
793 OrderedHashmap
*internal_ordered_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
794 return (OrderedHashmap
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS
);
797 Set
*internal_set_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
798 return (Set
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS
);
801 static int hashmap_base_ensure_allocated(HashmapBase
**h
, const struct hash_ops
*hash_ops
,
802 enum HashmapType type HASHMAP_DEBUG_PARAMS
) {
810 q
= hashmap_base_new(hash_ops
, type HASHMAP_DEBUG_PASS_ARGS
);
818 int internal_hashmap_ensure_allocated(Hashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
819 return hashmap_base_ensure_allocated((HashmapBase
**)h
, hash_ops
, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS
);
822 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
823 return hashmap_base_ensure_allocated((HashmapBase
**)h
, hash_ops
, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS
);
826 int internal_set_ensure_allocated(Set
**s
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
827 return hashmap_base_ensure_allocated((HashmapBase
**)s
, hash_ops
, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS
);
830 static void hashmap_free_no_clear(HashmapBase
*h
) {
831 assert(!h
->has_indirect
);
832 assert(!h
->n_direct_entries
);
834 #if ENABLE_DEBUG_HASHMAP
835 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex
) == 0);
836 LIST_REMOVE(debug_list
, hashmap_debug_list
, &h
->debug
);
837 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex
) == 0);
841 mempool_free_tile(hashmap_type_info
[h
->type
].mempool
, h
);
846 HashmapBase
*internal_hashmap_free(HashmapBase
*h
) {
848 /* Free the hashmap, but nothing in it */
851 internal_hashmap_clear(h
);
852 hashmap_free_no_clear(h
);
858 HashmapBase
*internal_hashmap_free_free(HashmapBase
*h
) {
860 /* Free the hashmap and all data objects in it, but not the
864 internal_hashmap_clear_free(h
);
865 hashmap_free_no_clear(h
);
871 Hashmap
*hashmap_free_free_free(Hashmap
*h
) {
873 /* Free the hashmap and all data and key objects in it */
876 hashmap_clear_free_free(h
);
877 hashmap_free_no_clear(HASHMAP_BASE(h
));
883 void internal_hashmap_clear(HashmapBase
*h
) {
887 if (h
->has_indirect
) {
888 free(h
->indirect
.storage
);
889 h
->has_indirect
= false;
892 h
->n_direct_entries
= 0;
893 reset_direct_storage(h
);
895 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
896 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
897 lh
->iterate_list_head
= lh
->iterate_list_tail
= IDX_NIL
;
901 void internal_hashmap_clear_free(HashmapBase
*h
) {
907 for (idx
= skip_free_buckets(h
, 0); idx
!= IDX_NIL
;
908 idx
= skip_free_buckets(h
, idx
+ 1))
909 free(entry_value(h
, bucket_at(h
, idx
)));
911 internal_hashmap_clear(h
);
914 void hashmap_clear_free_free(Hashmap
*h
) {
920 for (idx
= skip_free_buckets(HASHMAP_BASE(h
), 0); idx
!= IDX_NIL
;
921 idx
= skip_free_buckets(HASHMAP_BASE(h
), idx
+ 1)) {
922 struct plain_hashmap_entry
*e
= plain_bucket_at(h
, idx
);
923 free((void*)e
->b
.key
);
927 internal_hashmap_clear(HASHMAP_BASE(h
));
930 static int resize_buckets(HashmapBase
*h
, unsigned entries_add
);
933 * Finds an empty bucket to put an entry into, starting the scan at 'idx'.
934 * Performs Robin Hood swaps as it goes. The entry to put must be placed
935 * by the caller into swap slot IDX_PUT.
936 * If used for in-place resizing, may leave a displaced entry in swap slot
937 * IDX_PUT. Caller must rehash it next.
938 * Returns: true if it left a displaced entry to rehash next in IDX_PUT,
941 static bool hashmap_put_robin_hood(HashmapBase
*h
, unsigned idx
,
942 struct swap_entries
*swap
) {
943 dib_raw_t raw_dib
, *dibs
;
944 unsigned dib
, distance
;
946 #if ENABLE_DEBUG_HASHMAP
947 h
->debug
.put_count
++;
950 dibs
= dib_raw_ptr(h
);
952 for (distance
= 0; ; distance
++) {
954 if (IN_SET(raw_dib
, DIB_RAW_FREE
, DIB_RAW_REHASH
)) {
955 if (raw_dib
== DIB_RAW_REHASH
)
956 bucket_move_entry(h
, swap
, idx
, IDX_TMP
);
958 if (h
->has_indirect
&& h
->indirect
.idx_lowest_entry
> idx
)
959 h
->indirect
.idx_lowest_entry
= idx
;
961 bucket_set_dib(h
, idx
, distance
);
962 bucket_move_entry(h
, swap
, IDX_PUT
, idx
);
963 if (raw_dib
== DIB_RAW_REHASH
) {
964 bucket_move_entry(h
, swap
, IDX_TMP
, IDX_PUT
);
971 dib
= bucket_calculate_dib(h
, idx
, raw_dib
);
973 if (dib
< distance
) {
974 /* Found a wealthier entry. Go Robin Hood! */
975 bucket_set_dib(h
, idx
, distance
);
977 /* swap the entries */
978 bucket_move_entry(h
, swap
, idx
, IDX_TMP
);
979 bucket_move_entry(h
, swap
, IDX_PUT
, idx
);
980 bucket_move_entry(h
, swap
, IDX_TMP
, IDX_PUT
);
985 idx
= next_idx(h
, idx
);
990 * Puts an entry into a hashmap, boldly - no check whether key already exists.
991 * The caller must place the entry (only its key and value, not link indexes)
992 * in swap slot IDX_PUT.
993 * Caller must ensure: the key does not exist yet in the hashmap.
994 * that resize is not needed if !may_resize.
995 * Returns: 1 if entry was put successfully.
996 * -ENOMEM if may_resize==true and resize failed with -ENOMEM.
997 * Cannot return -ENOMEM if !may_resize.
999 static int hashmap_base_put_boldly(HashmapBase
*h
, unsigned idx
,
1000 struct swap_entries
*swap
, bool may_resize
) {
1001 struct ordered_hashmap_entry
*new_entry
;
1004 assert(idx
< n_buckets(h
));
1006 new_entry
= bucket_at_swap(swap
, IDX_PUT
);
1009 r
= resize_buckets(h
, 1);
1013 idx
= bucket_hash(h
, new_entry
->p
.b
.key
);
1015 assert(n_entries(h
) < n_buckets(h
));
1017 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
1018 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
1020 new_entry
->iterate_next
= IDX_NIL
;
1021 new_entry
->iterate_previous
= lh
->iterate_list_tail
;
1023 if (lh
->iterate_list_tail
!= IDX_NIL
) {
1024 struct ordered_hashmap_entry
*old_tail
;
1026 old_tail
= ordered_bucket_at(lh
, lh
->iterate_list_tail
);
1027 assert(old_tail
->iterate_next
== IDX_NIL
);
1028 old_tail
->iterate_next
= IDX_PUT
;
1031 lh
->iterate_list_tail
= IDX_PUT
;
1032 if (lh
->iterate_list_head
== IDX_NIL
)
1033 lh
->iterate_list_head
= IDX_PUT
;
1036 assert_se(hashmap_put_robin_hood(h
, idx
, swap
) == false);
1039 #if ENABLE_DEBUG_HASHMAP
1040 h
->debug
.max_entries
= MAX(h
->debug
.max_entries
, n_entries(h
));
1045 #define hashmap_put_boldly(h, idx, swap, may_resize) \
1046 hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
1049 * Returns 0 if resize is not needed.
1050 * 1 if successfully resized.
1051 * -ENOMEM on allocation failure.
1053 static int resize_buckets(HashmapBase
*h
, unsigned entries_add
) {
1054 struct swap_entries swap
;
1056 dib_raw_t
*old_dibs
, *new_dibs
;
1057 const struct hashmap_type_info
*hi
;
1058 unsigned idx
, optimal_idx
;
1059 unsigned old_n_buckets
, new_n_buckets
, n_rehashed
, new_n_entries
;
1065 hi
= &hashmap_type_info
[h
->type
];
1066 new_n_entries
= n_entries(h
) + entries_add
;
1069 if (_unlikely_(new_n_entries
< entries_add
))
1072 /* For direct storage we allow 100% load, because it's tiny. */
1073 if (!h
->has_indirect
&& new_n_entries
<= hi
->n_direct_buckets
)
1077 * Load factor = n/m = 1 - (1/INV_KEEP_FREE).
1078 * From it follows: m = n + n/(INV_KEEP_FREE - 1)
1080 new_n_buckets
= new_n_entries
+ new_n_entries
/ (INV_KEEP_FREE
- 1);
1082 if (_unlikely_(new_n_buckets
< new_n_entries
))
1085 if (_unlikely_(new_n_buckets
> UINT_MAX
/ (hi
->entry_size
+ sizeof(dib_raw_t
))))
1088 old_n_buckets
= n_buckets(h
);
1090 if (_likely_(new_n_buckets
<= old_n_buckets
))
1093 new_shift
= log2u_round_up(MAX(
1094 new_n_buckets
* (hi
->entry_size
+ sizeof(dib_raw_t
)),
1095 2 * sizeof(struct direct_storage
)));
1097 /* Realloc storage (buckets and DIB array). */
1098 new_storage
= realloc(h
->has_indirect
? h
->indirect
.storage
: NULL
,
1103 /* Must upgrade direct to indirect storage. */
1104 if (!h
->has_indirect
) {
1105 memcpy(new_storage
, h
->direct
.storage
,
1106 old_n_buckets
* (hi
->entry_size
+ sizeof(dib_raw_t
)));
1107 h
->indirect
.n_entries
= h
->n_direct_entries
;
1108 h
->indirect
.idx_lowest_entry
= 0;
1109 h
->n_direct_entries
= 0;
1112 /* Get a new hash key. If we've just upgraded to indirect storage,
1113 * allow reusing a previously generated key. It's still a different key
1114 * from the shared one that we used for direct storage. */
1115 get_hash_key(h
->indirect
.hash_key
, !h
->has_indirect
);
1117 h
->has_indirect
= true;
1118 h
->indirect
.storage
= new_storage
;
1119 h
->indirect
.n_buckets
= (1U << new_shift
) /
1120 (hi
->entry_size
+ sizeof(dib_raw_t
));
1122 old_dibs
= (dib_raw_t
*)((uint8_t*) new_storage
+ hi
->entry_size
* old_n_buckets
);
1123 new_dibs
= dib_raw_ptr(h
);
1126 * Move the DIB array to the new place, replacing valid DIB values with
1127 * DIB_RAW_REHASH to indicate all of the used buckets need rehashing.
1128 * Note: Overlap is not possible, because we have at least doubled the
1129 * number of buckets and dib_raw_t is smaller than any entry type.
1131 for (idx
= 0; idx
< old_n_buckets
; idx
++) {
1132 assert(old_dibs
[idx
] != DIB_RAW_REHASH
);
1133 new_dibs
[idx
] = old_dibs
[idx
] == DIB_RAW_FREE
? DIB_RAW_FREE
1137 /* Zero the area of newly added entries (including the old DIB area) */
1138 memzero(bucket_at(h
, old_n_buckets
),
1139 (n_buckets(h
) - old_n_buckets
) * hi
->entry_size
);
1141 /* The upper half of the new DIB array needs initialization */
1142 memset(&new_dibs
[old_n_buckets
], DIB_RAW_INIT
,
1143 (n_buckets(h
) - old_n_buckets
) * sizeof(dib_raw_t
));
1145 /* Rehash entries that need it */
1147 for (idx
= 0; idx
< old_n_buckets
; idx
++) {
1148 if (new_dibs
[idx
] != DIB_RAW_REHASH
)
1151 optimal_idx
= bucket_hash(h
, bucket_at(h
, idx
)->key
);
1154 * Not much to do if by luck the entry hashes to its current
1155 * location. Just set its DIB.
1157 if (optimal_idx
== idx
) {
1163 new_dibs
[idx
] = DIB_RAW_FREE
;
1164 bucket_move_entry(h
, &swap
, idx
, IDX_PUT
);
1165 /* bucket_move_entry does not clear the source */
1166 memzero(bucket_at(h
, idx
), hi
->entry_size
);
1170 * Find the new bucket for the current entry. This may make
1171 * another entry homeless and load it into IDX_PUT.
1173 rehash_next
= hashmap_put_robin_hood(h
, optimal_idx
, &swap
);
1176 /* Did the current entry displace another one? */
1178 optimal_idx
= bucket_hash(h
, bucket_at_swap(&swap
, IDX_PUT
)->p
.b
.key
);
1179 } while (rehash_next
);
1182 assert(n_rehashed
== n_entries(h
));
1188 * Finds an entry with a matching key
1189 * Returns: index of the found entry, or IDX_NIL if not found.
1191 static unsigned base_bucket_scan(HashmapBase
*h
, unsigned idx
, const void *key
) {
1192 struct hashmap_base_entry
*e
;
1193 unsigned dib
, distance
;
1194 dib_raw_t
*dibs
= dib_raw_ptr(h
);
1196 assert(idx
< n_buckets(h
));
1198 for (distance
= 0; ; distance
++) {
1199 if (dibs
[idx
] == DIB_RAW_FREE
)
1202 dib
= bucket_calculate_dib(h
, idx
, dibs
[idx
]);
1206 if (dib
== distance
) {
1207 e
= bucket_at(h
, idx
);
1208 if (h
->hash_ops
->compare(e
->key
, key
) == 0)
1212 idx
= next_idx(h
, idx
);
1215 #define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
1217 int hashmap_put(Hashmap
*h
, const void *key
, void *value
) {
1218 struct swap_entries swap
;
1219 struct plain_hashmap_entry
*e
;
1224 hash
= bucket_hash(h
, key
);
1225 idx
= bucket_scan(h
, hash
, key
);
1226 if (idx
!= IDX_NIL
) {
1227 e
= plain_bucket_at(h
, idx
);
1228 if (e
->value
== value
)
1233 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1236 return hashmap_put_boldly(h
, hash
, &swap
, true);
1239 int set_put(Set
*s
, const void *key
) {
1240 struct swap_entries swap
;
1241 struct hashmap_base_entry
*e
;
1246 hash
= bucket_hash(s
, key
);
1247 idx
= bucket_scan(s
, hash
, key
);
1251 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1253 return hashmap_put_boldly(s
, hash
, &swap
, true);
1256 int hashmap_replace(Hashmap
*h
, const void *key
, void *value
) {
1257 struct swap_entries swap
;
1258 struct plain_hashmap_entry
*e
;
1263 hash
= bucket_hash(h
, key
);
1264 idx
= bucket_scan(h
, hash
, key
);
1265 if (idx
!= IDX_NIL
) {
1266 e
= plain_bucket_at(h
, idx
);
1267 #if ENABLE_DEBUG_HASHMAP
1268 /* Although the key is equal, the key pointer may have changed,
1269 * and this would break our assumption for iterating. So count
1270 * this operation as incompatible with iteration. */
1271 if (e
->b
.key
!= key
) {
1272 h
->b
.debug
.put_count
++;
1273 h
->b
.debug
.rem_count
++;
1274 h
->b
.debug
.last_rem_idx
= idx
;
1282 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1285 return hashmap_put_boldly(h
, hash
, &swap
, true);
1288 int hashmap_update(Hashmap
*h
, const void *key
, void *value
) {
1289 struct plain_hashmap_entry
*e
;
1294 hash
= bucket_hash(h
, key
);
1295 idx
= bucket_scan(h
, hash
, key
);
1299 e
= plain_bucket_at(h
, idx
);
1304 void *internal_hashmap_get(HashmapBase
*h
, const void *key
) {
1305 struct hashmap_base_entry
*e
;
1311 hash
= bucket_hash(h
, key
);
1312 idx
= bucket_scan(h
, hash
, key
);
1316 e
= bucket_at(h
, idx
);
1317 return entry_value(h
, e
);
1320 void *hashmap_get2(Hashmap
*h
, const void *key
, void **key2
) {
1321 struct plain_hashmap_entry
*e
;
1327 hash
= bucket_hash(h
, key
);
1328 idx
= bucket_scan(h
, hash
, key
);
1332 e
= plain_bucket_at(h
, idx
);
1334 *key2
= (void*) e
->b
.key
;
1339 bool internal_hashmap_contains(HashmapBase
*h
, const void *key
) {
1345 hash
= bucket_hash(h
, key
);
1346 return bucket_scan(h
, hash
, key
) != IDX_NIL
;
1349 void *internal_hashmap_remove(HashmapBase
*h
, const void *key
) {
1350 struct hashmap_base_entry
*e
;
1357 hash
= bucket_hash(h
, key
);
1358 idx
= bucket_scan(h
, hash
, key
);
1362 e
= bucket_at(h
, idx
);
1363 data
= entry_value(h
, e
);
1364 remove_entry(h
, idx
);
1369 void *hashmap_remove2(Hashmap
*h
, const void *key
, void **rkey
) {
1370 struct plain_hashmap_entry
*e
;
1380 hash
= bucket_hash(h
, key
);
1381 idx
= bucket_scan(h
, hash
, key
);
1382 if (idx
== IDX_NIL
) {
1388 e
= plain_bucket_at(h
, idx
);
1391 *rkey
= (void*) e
->b
.key
;
1393 remove_entry(h
, idx
);
1398 int hashmap_remove_and_put(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
1399 struct swap_entries swap
;
1400 struct plain_hashmap_entry
*e
;
1401 unsigned old_hash
, new_hash
, idx
;
1406 old_hash
= bucket_hash(h
, old_key
);
1407 idx
= bucket_scan(h
, old_hash
, old_key
);
1411 new_hash
= bucket_hash(h
, new_key
);
1412 if (bucket_scan(h
, new_hash
, new_key
) != IDX_NIL
)
1415 remove_entry(h
, idx
);
1417 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1420 assert_se(hashmap_put_boldly(h
, new_hash
, &swap
, false) == 1);
1425 int set_remove_and_put(Set
*s
, const void *old_key
, const void *new_key
) {
1426 struct swap_entries swap
;
1427 struct hashmap_base_entry
*e
;
1428 unsigned old_hash
, new_hash
, idx
;
1433 old_hash
= bucket_hash(s
, old_key
);
1434 idx
= bucket_scan(s
, old_hash
, old_key
);
1438 new_hash
= bucket_hash(s
, new_key
);
1439 if (bucket_scan(s
, new_hash
, new_key
) != IDX_NIL
)
1442 remove_entry(s
, idx
);
1444 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1446 assert_se(hashmap_put_boldly(s
, new_hash
, &swap
, false) == 1);
1451 int hashmap_remove_and_replace(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
1452 struct swap_entries swap
;
1453 struct plain_hashmap_entry
*e
;
1454 unsigned old_hash
, new_hash
, idx_old
, idx_new
;
1459 old_hash
= bucket_hash(h
, old_key
);
1460 idx_old
= bucket_scan(h
, old_hash
, old_key
);
1461 if (idx_old
== IDX_NIL
)
1464 old_key
= bucket_at(HASHMAP_BASE(h
), idx_old
)->key
;
1466 new_hash
= bucket_hash(h
, new_key
);
1467 idx_new
= bucket_scan(h
, new_hash
, new_key
);
1468 if (idx_new
!= IDX_NIL
)
1469 if (idx_old
!= idx_new
) {
1470 remove_entry(h
, idx_new
);
1471 /* Compensate for a possible backward shift. */
1472 if (old_key
!= bucket_at(HASHMAP_BASE(h
), idx_old
)->key
)
1473 idx_old
= prev_idx(HASHMAP_BASE(h
), idx_old
);
1474 assert(old_key
== bucket_at(HASHMAP_BASE(h
), idx_old
)->key
);
1477 remove_entry(h
, idx_old
);
1479 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1482 assert_se(hashmap_put_boldly(h
, new_hash
, &swap
, false) == 1);
1487 void *hashmap_remove_value(Hashmap
*h
, const void *key
, void *value
) {
1488 struct plain_hashmap_entry
*e
;
1494 hash
= bucket_hash(h
, key
);
1495 idx
= bucket_scan(h
, hash
, key
);
1499 e
= plain_bucket_at(h
, idx
);
1500 if (e
->value
!= value
)
1503 remove_entry(h
, idx
);
1508 static unsigned find_first_entry(HashmapBase
*h
) {
1509 Iterator i
= ITERATOR_FIRST
;
1511 if (!h
|| !n_entries(h
))
1514 return hashmap_iterate_entry(h
, &i
);
1517 void *internal_hashmap_first(HashmapBase
*h
) {
1520 idx
= find_first_entry(h
);
1524 return entry_value(h
, bucket_at(h
, idx
));
1527 void *internal_hashmap_first_key(HashmapBase
*h
) {
1528 struct hashmap_base_entry
*e
;
1531 idx
= find_first_entry(h
);
1535 e
= bucket_at(h
, idx
);
1536 return (void*) e
->key
;
1539 void *internal_hashmap_steal_first(HashmapBase
*h
) {
1540 struct hashmap_base_entry
*e
;
1544 idx
= find_first_entry(h
);
1548 e
= bucket_at(h
, idx
);
1549 data
= entry_value(h
, e
);
1550 remove_entry(h
, idx
);
1555 void *internal_hashmap_steal_first_key(HashmapBase
*h
) {
1556 struct hashmap_base_entry
*e
;
1560 idx
= find_first_entry(h
);
1564 e
= bucket_at(h
, idx
);
1565 key
= (void*) e
->key
;
1566 remove_entry(h
, idx
);
1571 unsigned internal_hashmap_size(HashmapBase
*h
) {
1576 return n_entries(h
);
1579 unsigned internal_hashmap_buckets(HashmapBase
*h
) {
1584 return n_buckets(h
);
1587 int internal_hashmap_merge(Hashmap
*h
, Hashmap
*other
) {
1593 HASHMAP_FOREACH_IDX(idx
, HASHMAP_BASE(other
), i
) {
1594 struct plain_hashmap_entry
*pe
= plain_bucket_at(other
, idx
);
1597 r
= hashmap_put(h
, pe
->b
.key
, pe
->value
);
1598 if (r
< 0 && r
!= -EEXIST
)
1605 int set_merge(Set
*s
, Set
*other
) {
1611 HASHMAP_FOREACH_IDX(idx
, HASHMAP_BASE(other
), i
) {
1612 struct set_entry
*se
= set_bucket_at(other
, idx
);
1615 r
= set_put(s
, se
->b
.key
);
1623 int internal_hashmap_reserve(HashmapBase
*h
, unsigned entries_add
) {
1628 r
= resize_buckets(h
, entries_add
);
1636 * The same as hashmap_merge(), but every new item from other is moved to h.
1637 * Keys already in h are skipped and stay in other.
1638 * Returns: 0 on success.
1639 * -ENOMEM on alloc failure, in which case no move has been done.
1641 int internal_hashmap_move(HashmapBase
*h
, HashmapBase
*other
) {
1642 struct swap_entries swap
;
1643 struct hashmap_base_entry
*e
, *n
;
1653 assert(other
->type
== h
->type
);
1656 * This reserves buckets for the worst case, where none of other's
1657 * entries are yet present in h. This is preferable to risking
1658 * an allocation failure in the middle of the moving and having to
1659 * rollback or return a partial result.
1661 r
= resize_buckets(h
, n_entries(other
));
1665 HASHMAP_FOREACH_IDX(idx
, other
, i
) {
1668 e
= bucket_at(other
, idx
);
1669 h_hash
= bucket_hash(h
, e
->key
);
1670 if (bucket_scan(h
, h_hash
, e
->key
) != IDX_NIL
)
1673 n
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1675 if (h
->type
!= HASHMAP_TYPE_SET
)
1676 ((struct plain_hashmap_entry
*) n
)->value
=
1677 ((struct plain_hashmap_entry
*) e
)->value
;
1678 assert_se(hashmap_put_boldly(h
, h_hash
, &swap
, false) == 1);
1680 remove_entry(other
, idx
);
1686 int internal_hashmap_move_one(HashmapBase
*h
, HashmapBase
*other
, const void *key
) {
1687 struct swap_entries swap
;
1688 unsigned h_hash
, other_hash
, idx
;
1689 struct hashmap_base_entry
*e
, *n
;
1694 h_hash
= bucket_hash(h
, key
);
1695 if (bucket_scan(h
, h_hash
, key
) != IDX_NIL
)
1701 assert(other
->type
== h
->type
);
1703 other_hash
= bucket_hash(other
, key
);
1704 idx
= bucket_scan(other
, other_hash
, key
);
1708 e
= bucket_at(other
, idx
);
1710 n
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1712 if (h
->type
!= HASHMAP_TYPE_SET
)
1713 ((struct plain_hashmap_entry
*) n
)->value
=
1714 ((struct plain_hashmap_entry
*) e
)->value
;
1715 r
= hashmap_put_boldly(h
, h_hash
, &swap
, true);
1719 remove_entry(other
, idx
);
1723 HashmapBase
*internal_hashmap_copy(HashmapBase
*h
) {
1729 copy
= hashmap_base_new(h
->hash_ops
, h
->type HASHMAP_DEBUG_SRC_ARGS
);
1734 case HASHMAP_TYPE_PLAIN
:
1735 case HASHMAP_TYPE_ORDERED
:
1736 r
= hashmap_merge((Hashmap
*)copy
, (Hashmap
*)h
);
1738 case HASHMAP_TYPE_SET
:
1739 r
= set_merge((Set
*)copy
, (Set
*)h
);
1742 assert_not_reached("Unknown hashmap type");
1746 internal_hashmap_free(copy
);
1753 char **internal_hashmap_get_strv(HashmapBase
*h
) {
1758 sv
= new(char*, n_entries(h
)+1);
1763 HASHMAP_FOREACH_IDX(idx
, h
, i
)
1764 sv
[n
++] = entry_value(h
, bucket_at(h
, idx
));
1770 void *ordered_hashmap_next(OrderedHashmap
*h
, const void *key
) {
1771 struct ordered_hashmap_entry
*e
;
1777 hash
= bucket_hash(h
, key
);
1778 idx
= bucket_scan(h
, hash
, key
);
1782 e
= ordered_bucket_at(h
, idx
);
1783 if (e
->iterate_next
== IDX_NIL
)
1785 return ordered_bucket_at(h
, e
->iterate_next
)->p
.value
;
1788 int set_consume(Set
*s
, void *value
) {
1794 r
= set_put(s
, value
);
1801 int set_put_strdup(Set
*s
, const char *p
) {
1807 if (set_contains(s
, (char*) p
))
1814 return set_consume(s
, c
);
1817 int set_put_strdupv(Set
*s
, char **l
) {
1823 STRV_FOREACH(i
, l
) {
1824 r
= set_put_strdup(s
, *i
);
1834 int set_put_strsplit(Set
*s
, const char *v
, const char *separators
, ExtractFlags flags
) {
1844 r
= extract_first_word(&p
, &word
, separators
, flags
);
1848 r
= set_consume(s
, word
);