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 HASHMAP_DEBUG_FIELDS
/* optional hashmap_debug_info */
235 /* Specific hash types
236 * HashmapBase must be at the beginning of each hashmap struct. */
239 struct HashmapBase b
;
242 struct OrderedHashmap
{
243 struct HashmapBase b
;
244 unsigned iterate_list_head
, iterate_list_tail
;
248 struct HashmapBase b
;
251 DEFINE_MEMPOOL(hashmap_pool
, Hashmap
, 8);
252 DEFINE_MEMPOOL(ordered_hashmap_pool
, OrderedHashmap
, 8);
253 /* No need for a separate Set pool */
254 assert_cc(sizeof(Hashmap
) == sizeof(Set
));
256 struct hashmap_type_info
{
259 struct mempool
*mempool
;
260 unsigned n_direct_buckets
;
263 static const struct hashmap_type_info hashmap_type_info
[_HASHMAP_TYPE_MAX
] = {
264 [HASHMAP_TYPE_PLAIN
] = {
265 .head_size
= sizeof(Hashmap
),
266 .entry_size
= sizeof(struct plain_hashmap_entry
),
267 .mempool
= &hashmap_pool
,
268 .n_direct_buckets
= DIRECT_BUCKETS(struct plain_hashmap_entry
),
270 [HASHMAP_TYPE_ORDERED
] = {
271 .head_size
= sizeof(OrderedHashmap
),
272 .entry_size
= sizeof(struct ordered_hashmap_entry
),
273 .mempool
= &ordered_hashmap_pool
,
274 .n_direct_buckets
= DIRECT_BUCKETS(struct ordered_hashmap_entry
),
276 [HASHMAP_TYPE_SET
] = {
277 .head_size
= sizeof(Set
),
278 .entry_size
= sizeof(struct set_entry
),
279 .mempool
= &hashmap_pool
,
280 .n_direct_buckets
= DIRECT_BUCKETS(struct set_entry
),
285 __attribute__((destructor
)) static void cleanup_pools(void) {
286 _cleanup_free_
char *t
= NULL
;
289 /* Be nice to valgrind */
291 /* The pool is only allocated by the main thread, but the memory can
292 * be passed to other threads. Let's clean up if we are the main thread
293 * and no other threads are live. */
294 if (!is_main_thread())
297 r
= get_proc_field("/proc/self/status", "Threads", WHITESPACE
, &t
);
298 if (r
< 0 || !streq(t
, "1"))
301 mempool_drop(&hashmap_pool
);
302 mempool_drop(&ordered_hashmap_pool
);
306 static unsigned n_buckets(HashmapBase
*h
) {
307 return h
->has_indirect
? h
->indirect
.n_buckets
308 : hashmap_type_info
[h
->type
].n_direct_buckets
;
311 static unsigned n_entries(HashmapBase
*h
) {
312 return h
->has_indirect
? h
->indirect
.n_entries
313 : h
->n_direct_entries
;
316 static void n_entries_inc(HashmapBase
*h
) {
318 h
->indirect
.n_entries
++;
320 h
->n_direct_entries
++;
323 static void n_entries_dec(HashmapBase
*h
) {
325 h
->indirect
.n_entries
--;
327 h
->n_direct_entries
--;
330 static void *storage_ptr(HashmapBase
*h
) {
331 return h
->has_indirect
? h
->indirect
.storage
335 static uint8_t *hash_key(HashmapBase
*h
) {
336 return h
->has_indirect
? h
->indirect
.hash_key
340 static unsigned base_bucket_hash(HashmapBase
*h
, const void *p
) {
341 struct siphash state
;
344 siphash24_init(&state
, hash_key(h
));
346 h
->hash_ops
->hash(p
, &state
);
348 hash
= siphash24_finalize(&state
);
350 return (unsigned) (hash
% n_buckets(h
));
352 #define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p)
354 static void get_hash_key(uint8_t hash_key
[HASH_KEY_SIZE
], bool reuse_is_ok
) {
355 static uint8_t current
[HASH_KEY_SIZE
];
356 static bool current_initialized
= false;
358 /* Returns a hash function key to use. In order to keep things
359 * fast we will not generate a new key each time we allocate a
360 * new hash table. Instead, we'll just reuse the most recently
361 * generated one, except if we never generated one or when we
362 * are rehashing an entire hash table because we reached a
365 if (!current_initialized
|| !reuse_is_ok
) {
366 random_bytes(current
, sizeof(current
));
367 current_initialized
= true;
370 memcpy(hash_key
, current
, sizeof(current
));
373 static struct hashmap_base_entry
*bucket_at(HashmapBase
*h
, unsigned idx
) {
374 return (struct hashmap_base_entry
*)
375 ((uint8_t*) storage_ptr(h
) + idx
* hashmap_type_info
[h
->type
].entry_size
);
378 static struct plain_hashmap_entry
*plain_bucket_at(Hashmap
*h
, unsigned idx
) {
379 return (struct plain_hashmap_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
382 static struct ordered_hashmap_entry
*ordered_bucket_at(OrderedHashmap
*h
, unsigned idx
) {
383 return (struct ordered_hashmap_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
386 static struct set_entry
*set_bucket_at(Set
*h
, unsigned idx
) {
387 return (struct set_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
390 static struct ordered_hashmap_entry
*bucket_at_swap(struct swap_entries
*swap
, unsigned idx
) {
391 return &swap
->e
[idx
- _IDX_SWAP_BEGIN
];
394 /* Returns a pointer to the bucket at index idx.
395 * Understands real indexes and swap indexes, hence "_virtual". */
396 static struct hashmap_base_entry
*bucket_at_virtual(HashmapBase
*h
, struct swap_entries
*swap
,
398 if (idx
< _IDX_SWAP_BEGIN
)
399 return bucket_at(h
, idx
);
401 if (idx
< _IDX_SWAP_END
)
402 return &bucket_at_swap(swap
, idx
)->p
.b
;
404 assert_not_reached("Invalid index");
407 static dib_raw_t
*dib_raw_ptr(HashmapBase
*h
) {
409 ((uint8_t*) storage_ptr(h
) + hashmap_type_info
[h
->type
].entry_size
* n_buckets(h
));
412 static unsigned bucket_distance(HashmapBase
*h
, unsigned idx
, unsigned from
) {
413 return idx
>= from
? idx
- from
414 : n_buckets(h
) + idx
- from
;
417 static unsigned bucket_calculate_dib(HashmapBase
*h
, unsigned idx
, dib_raw_t raw_dib
) {
418 unsigned initial_bucket
;
420 if (raw_dib
== DIB_RAW_FREE
)
423 if (_likely_(raw_dib
< DIB_RAW_OVERFLOW
))
427 * Having an overflow DIB value is very unlikely. The hash function
428 * would have to be bad. For example, in a table of size 2^24 filled
429 * to load factor 0.9 the maximum observed DIB is only about 60.
430 * In theory (assuming I used Maxima correctly), for an infinite size
431 * hash table with load factor 0.8 the probability of a given entry
432 * having DIB > 40 is 1.9e-8.
433 * This returns the correct DIB value by recomputing the hash value in
434 * the unlikely case. XXX Hitting this case could be a hint to rehash.
436 initial_bucket
= bucket_hash(h
, bucket_at(h
, idx
)->key
);
437 return bucket_distance(h
, idx
, initial_bucket
);
440 static void bucket_set_dib(HashmapBase
*h
, unsigned idx
, unsigned dib
) {
441 dib_raw_ptr(h
)[idx
] = dib
!= DIB_FREE
? MIN(dib
, DIB_RAW_OVERFLOW
) : DIB_RAW_FREE
;
444 static unsigned skip_free_buckets(HashmapBase
*h
, unsigned idx
) {
447 dibs
= dib_raw_ptr(h
);
449 for ( ; idx
< n_buckets(h
); idx
++)
450 if (dibs
[idx
] != DIB_RAW_FREE
)
456 static void bucket_mark_free(HashmapBase
*h
, unsigned idx
) {
457 memzero(bucket_at(h
, idx
), hashmap_type_info
[h
->type
].entry_size
);
458 bucket_set_dib(h
, idx
, DIB_FREE
);
461 static void bucket_move_entry(HashmapBase
*h
, struct swap_entries
*swap
,
462 unsigned from
, unsigned to
) {
463 struct hashmap_base_entry
*e_from
, *e_to
;
467 e_from
= bucket_at_virtual(h
, swap
, from
);
468 e_to
= bucket_at_virtual(h
, swap
, to
);
470 memcpy(e_to
, e_from
, hashmap_type_info
[h
->type
].entry_size
);
472 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
473 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
474 struct ordered_hashmap_entry
*le
, *le_to
;
476 le_to
= (struct ordered_hashmap_entry
*) e_to
;
478 if (le_to
->iterate_next
!= IDX_NIL
) {
479 le
= (struct ordered_hashmap_entry
*)
480 bucket_at_virtual(h
, swap
, le_to
->iterate_next
);
481 le
->iterate_previous
= to
;
484 if (le_to
->iterate_previous
!= IDX_NIL
) {
485 le
= (struct ordered_hashmap_entry
*)
486 bucket_at_virtual(h
, swap
, le_to
->iterate_previous
);
487 le
->iterate_next
= to
;
490 if (lh
->iterate_list_head
== from
)
491 lh
->iterate_list_head
= to
;
492 if (lh
->iterate_list_tail
== from
)
493 lh
->iterate_list_tail
= to
;
497 static unsigned next_idx(HashmapBase
*h
, unsigned idx
) {
498 return (idx
+ 1U) % n_buckets(h
);
501 static unsigned prev_idx(HashmapBase
*h
, unsigned idx
) {
502 return (n_buckets(h
) + idx
- 1U) % n_buckets(h
);
505 static void *entry_value(HashmapBase
*h
, struct hashmap_base_entry
*e
) {
508 case HASHMAP_TYPE_PLAIN
:
509 case HASHMAP_TYPE_ORDERED
:
510 return ((struct plain_hashmap_entry
*)e
)->value
;
512 case HASHMAP_TYPE_SET
:
513 return (void*) e
->key
;
516 assert_not_reached("Unknown hashmap type");
520 static void base_remove_entry(HashmapBase
*h
, unsigned idx
) {
521 unsigned left
, right
, prev
, dib
;
522 dib_raw_t raw_dib
, *dibs
;
524 dibs
= dib_raw_ptr(h
);
525 assert(dibs
[idx
] != DIB_RAW_FREE
);
527 #if ENABLE_DEBUG_HASHMAP
528 h
->debug
.rem_count
++;
529 h
->debug
.last_rem_idx
= idx
;
533 /* Find the stop bucket ("right"). It is either free or has DIB == 0. */
534 for (right
= next_idx(h
, left
); ; right
= next_idx(h
, right
)) {
535 raw_dib
= dibs
[right
];
536 if (IN_SET(raw_dib
, 0, DIB_RAW_FREE
))
539 /* The buckets are not supposed to be all occupied and with DIB > 0.
540 * That would mean we could make everyone better off by shifting them
541 * backward. This scenario is impossible. */
542 assert(left
!= right
);
545 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
546 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
547 struct ordered_hashmap_entry
*le
= ordered_bucket_at(lh
, idx
);
549 if (le
->iterate_next
!= IDX_NIL
)
550 ordered_bucket_at(lh
, le
->iterate_next
)->iterate_previous
= le
->iterate_previous
;
552 lh
->iterate_list_tail
= le
->iterate_previous
;
554 if (le
->iterate_previous
!= IDX_NIL
)
555 ordered_bucket_at(lh
, le
->iterate_previous
)->iterate_next
= le
->iterate_next
;
557 lh
->iterate_list_head
= le
->iterate_next
;
560 /* Now shift all buckets in the interval (left, right) one step backwards */
561 for (prev
= left
, left
= next_idx(h
, left
); left
!= right
;
562 prev
= left
, left
= next_idx(h
, left
)) {
563 dib
= bucket_calculate_dib(h
, left
, dibs
[left
]);
565 bucket_move_entry(h
, NULL
, left
, prev
);
566 bucket_set_dib(h
, prev
, dib
- 1);
569 bucket_mark_free(h
, prev
);
572 #define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)
574 static unsigned hashmap_iterate_in_insertion_order(OrderedHashmap
*h
, Iterator
*i
) {
575 struct ordered_hashmap_entry
*e
;
581 if (i
->idx
== IDX_NIL
)
584 if (i
->idx
== IDX_FIRST
&& h
->iterate_list_head
== IDX_NIL
)
587 if (i
->idx
== IDX_FIRST
) {
588 idx
= h
->iterate_list_head
;
589 e
= ordered_bucket_at(h
, idx
);
592 e
= ordered_bucket_at(h
, idx
);
594 * We allow removing the current entry while iterating, but removal may cause
595 * a backward shift. The next entry may thus move one bucket to the left.
596 * To detect when it happens, we remember the key pointer of the entry we were
597 * going to iterate next. If it does not match, there was a backward shift.
599 if (e
->p
.b
.key
!= i
->next_key
) {
600 idx
= prev_idx(HASHMAP_BASE(h
), idx
);
601 e
= ordered_bucket_at(h
, idx
);
603 assert(e
->p
.b
.key
== i
->next_key
);
606 #if ENABLE_DEBUG_HASHMAP
610 if (e
->iterate_next
!= IDX_NIL
) {
611 struct ordered_hashmap_entry
*n
;
612 i
->idx
= e
->iterate_next
;
613 n
= ordered_bucket_at(h
, i
->idx
);
614 i
->next_key
= n
->p
.b
.key
;
625 static unsigned hashmap_iterate_in_internal_order(HashmapBase
*h
, Iterator
*i
) {
631 if (i
->idx
== IDX_NIL
)
634 if (i
->idx
== IDX_FIRST
) {
635 /* fast forward to the first occupied bucket */
636 if (h
->has_indirect
) {
637 i
->idx
= skip_free_buckets(h
, h
->indirect
.idx_lowest_entry
);
638 h
->indirect
.idx_lowest_entry
= i
->idx
;
640 i
->idx
= skip_free_buckets(h
, 0);
642 if (i
->idx
== IDX_NIL
)
645 struct hashmap_base_entry
*e
;
649 e
= bucket_at(h
, i
->idx
);
651 * We allow removing the current entry while iterating, but removal may cause
652 * a backward shift. The next entry may thus move one bucket to the left.
653 * To detect when it happens, we remember the key pointer of the entry we were
654 * going to iterate next. If it does not match, there was a backward shift.
656 if (e
->key
!= i
->next_key
)
657 e
= bucket_at(h
, --i
->idx
);
659 assert(e
->key
== i
->next_key
);
663 #if ENABLE_DEBUG_HASHMAP
667 i
->idx
= skip_free_buckets(h
, i
->idx
+ 1);
668 if (i
->idx
!= IDX_NIL
)
669 i
->next_key
= bucket_at(h
, i
->idx
)->key
;
680 static unsigned hashmap_iterate_entry(HashmapBase
*h
, Iterator
*i
) {
686 #if ENABLE_DEBUG_HASHMAP
687 if (i
->idx
== IDX_FIRST
) {
688 i
->put_count
= h
->debug
.put_count
;
689 i
->rem_count
= h
->debug
.rem_count
;
691 /* While iterating, must not add any new entries */
692 assert(i
->put_count
== h
->debug
.put_count
);
693 /* ... or remove entries other than the current one */
694 assert(i
->rem_count
== h
->debug
.rem_count
||
695 (i
->rem_count
== h
->debug
.rem_count
- 1 &&
696 i
->prev_idx
== h
->debug
.last_rem_idx
));
697 /* Reset our removals counter */
698 i
->rem_count
= h
->debug
.rem_count
;
702 return h
->type
== HASHMAP_TYPE_ORDERED
? hashmap_iterate_in_insertion_order((OrderedHashmap
*) h
, i
)
703 : hashmap_iterate_in_internal_order(h
, i
);
706 bool internal_hashmap_iterate(HashmapBase
*h
, Iterator
*i
, void **value
, const void **key
) {
707 struct hashmap_base_entry
*e
;
711 idx
= hashmap_iterate_entry(h
, i
);
712 if (idx
== IDX_NIL
) {
721 e
= bucket_at(h
, idx
);
722 data
= entry_value(h
, e
);
731 bool set_iterate(Set
*s
, Iterator
*i
, void **value
) {
732 return internal_hashmap_iterate(HASHMAP_BASE(s
), i
, value
, NULL
);
735 #define HASHMAP_FOREACH_IDX(idx, h, i) \
736 for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \
738 (idx) = hashmap_iterate_entry((h), &(i)))
740 static void reset_direct_storage(HashmapBase
*h
) {
741 const struct hashmap_type_info
*hi
= &hashmap_type_info
[h
->type
];
744 assert(!h
->has_indirect
);
746 p
= mempset(h
->direct
.storage
, 0, hi
->entry_size
* hi
->n_direct_buckets
);
747 memset(p
, DIB_RAW_INIT
, sizeof(dib_raw_t
) * hi
->n_direct_buckets
);
750 static struct HashmapBase
*hashmap_base_new(const struct hash_ops
*hash_ops
, enum HashmapType type HASHMAP_DEBUG_PARAMS
) {
752 const struct hashmap_type_info
*hi
= &hashmap_type_info
[type
];
755 use_pool
= is_main_thread();
757 h
= use_pool
? mempool_alloc0_tile(hi
->mempool
) : malloc0(hi
->head_size
);
763 h
->from_pool
= use_pool
;
764 h
->hash_ops
= hash_ops
? hash_ops
: &trivial_hash_ops
;
766 if (type
== HASHMAP_TYPE_ORDERED
) {
767 OrderedHashmap
*lh
= (OrderedHashmap
*)h
;
768 lh
->iterate_list_head
= lh
->iterate_list_tail
= IDX_NIL
;
771 reset_direct_storage(h
);
773 if (!shared_hash_key_initialized
) {
774 random_bytes(shared_hash_key
, sizeof(shared_hash_key
));
775 shared_hash_key_initialized
= true;
778 #if ENABLE_DEBUG_HASHMAP
779 h
->debug
.func
= func
;
780 h
->debug
.file
= file
;
781 h
->debug
.line
= line
;
782 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex
) == 0);
783 LIST_PREPEND(debug_list
, hashmap_debug_list
, &h
->debug
);
784 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex
) == 0);
790 Hashmap
*internal_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
791 return (Hashmap
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS
);
794 OrderedHashmap
*internal_ordered_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
795 return (OrderedHashmap
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS
);
798 Set
*internal_set_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
799 return (Set
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS
);
802 static int hashmap_base_ensure_allocated(HashmapBase
**h
, const struct hash_ops
*hash_ops
,
803 enum HashmapType type HASHMAP_DEBUG_PARAMS
) {
811 q
= hashmap_base_new(hash_ops
, type HASHMAP_DEBUG_PASS_ARGS
);
819 int internal_hashmap_ensure_allocated(Hashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
820 return hashmap_base_ensure_allocated((HashmapBase
**)h
, hash_ops
, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS
);
823 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
824 return hashmap_base_ensure_allocated((HashmapBase
**)h
, hash_ops
, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS
);
827 int internal_set_ensure_allocated(Set
**s
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
828 return hashmap_base_ensure_allocated((HashmapBase
**)s
, hash_ops
, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS
);
831 static void hashmap_free_no_clear(HashmapBase
*h
) {
832 assert(!h
->has_indirect
);
833 assert(!h
->n_direct_entries
);
835 #if ENABLE_DEBUG_HASHMAP
836 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex
) == 0);
837 LIST_REMOVE(debug_list
, hashmap_debug_list
, &h
->debug
);
838 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex
) == 0);
842 mempool_free_tile(hashmap_type_info
[h
->type
].mempool
, h
);
847 HashmapBase
*internal_hashmap_free(HashmapBase
*h
) {
849 /* Free the hashmap, but nothing in it */
852 internal_hashmap_clear(h
);
853 hashmap_free_no_clear(h
);
859 HashmapBase
*internal_hashmap_free_free(HashmapBase
*h
) {
861 /* Free the hashmap and all data objects in it, but not the
865 internal_hashmap_clear_free(h
);
866 hashmap_free_no_clear(h
);
872 Hashmap
*hashmap_free_free_free(Hashmap
*h
) {
874 /* Free the hashmap and all data and key objects in it */
877 hashmap_clear_free_free(h
);
878 hashmap_free_no_clear(HASHMAP_BASE(h
));
884 void internal_hashmap_clear(HashmapBase
*h
) {
888 if (h
->has_indirect
) {
889 free(h
->indirect
.storage
);
890 h
->has_indirect
= false;
893 h
->n_direct_entries
= 0;
894 reset_direct_storage(h
);
896 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
897 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
898 lh
->iterate_list_head
= lh
->iterate_list_tail
= IDX_NIL
;
902 void internal_hashmap_clear_free(HashmapBase
*h
) {
908 for (idx
= skip_free_buckets(h
, 0); idx
!= IDX_NIL
;
909 idx
= skip_free_buckets(h
, idx
+ 1))
910 free(entry_value(h
, bucket_at(h
, idx
)));
912 internal_hashmap_clear(h
);
915 void hashmap_clear_free_free(Hashmap
*h
) {
921 for (idx
= skip_free_buckets(HASHMAP_BASE(h
), 0); idx
!= IDX_NIL
;
922 idx
= skip_free_buckets(HASHMAP_BASE(h
), idx
+ 1)) {
923 struct plain_hashmap_entry
*e
= plain_bucket_at(h
, idx
);
924 free((void*)e
->b
.key
);
928 internal_hashmap_clear(HASHMAP_BASE(h
));
931 static int resize_buckets(HashmapBase
*h
, unsigned entries_add
);
934 * Finds an empty bucket to put an entry into, starting the scan at 'idx'.
935 * Performs Robin Hood swaps as it goes. The entry to put must be placed
936 * by the caller into swap slot IDX_PUT.
937 * If used for in-place resizing, may leave a displaced entry in swap slot
938 * IDX_PUT. Caller must rehash it next.
939 * Returns: true if it left a displaced entry to rehash next in IDX_PUT,
942 static bool hashmap_put_robin_hood(HashmapBase
*h
, unsigned idx
,
943 struct swap_entries
*swap
) {
944 dib_raw_t raw_dib
, *dibs
;
945 unsigned dib
, distance
;
947 #if ENABLE_DEBUG_HASHMAP
948 h
->debug
.put_count
++;
951 dibs
= dib_raw_ptr(h
);
953 for (distance
= 0; ; distance
++) {
955 if (IN_SET(raw_dib
, DIB_RAW_FREE
, DIB_RAW_REHASH
)) {
956 if (raw_dib
== DIB_RAW_REHASH
)
957 bucket_move_entry(h
, swap
, idx
, IDX_TMP
);
959 if (h
->has_indirect
&& h
->indirect
.idx_lowest_entry
> idx
)
960 h
->indirect
.idx_lowest_entry
= idx
;
962 bucket_set_dib(h
, idx
, distance
);
963 bucket_move_entry(h
, swap
, IDX_PUT
, idx
);
964 if (raw_dib
== DIB_RAW_REHASH
) {
965 bucket_move_entry(h
, swap
, IDX_TMP
, IDX_PUT
);
972 dib
= bucket_calculate_dib(h
, idx
, raw_dib
);
974 if (dib
< distance
) {
975 /* Found a wealthier entry. Go Robin Hood! */
976 bucket_set_dib(h
, idx
, distance
);
978 /* swap the entries */
979 bucket_move_entry(h
, swap
, idx
, IDX_TMP
);
980 bucket_move_entry(h
, swap
, IDX_PUT
, idx
);
981 bucket_move_entry(h
, swap
, IDX_TMP
, IDX_PUT
);
986 idx
= next_idx(h
, idx
);
991 * Puts an entry into a hashmap, boldly - no check whether key already exists.
992 * The caller must place the entry (only its key and value, not link indexes)
993 * in swap slot IDX_PUT.
994 * Caller must ensure: the key does not exist yet in the hashmap.
995 * that resize is not needed if !may_resize.
996 * Returns: 1 if entry was put successfully.
997 * -ENOMEM if may_resize==true and resize failed with -ENOMEM.
998 * Cannot return -ENOMEM if !may_resize.
1000 static int hashmap_base_put_boldly(HashmapBase
*h
, unsigned idx
,
1001 struct swap_entries
*swap
, bool may_resize
) {
1002 struct ordered_hashmap_entry
*new_entry
;
1005 assert(idx
< n_buckets(h
));
1007 new_entry
= bucket_at_swap(swap
, IDX_PUT
);
1010 r
= resize_buckets(h
, 1);
1014 idx
= bucket_hash(h
, new_entry
->p
.b
.key
);
1016 assert(n_entries(h
) < n_buckets(h
));
1018 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
1019 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
1021 new_entry
->iterate_next
= IDX_NIL
;
1022 new_entry
->iterate_previous
= lh
->iterate_list_tail
;
1024 if (lh
->iterate_list_tail
!= IDX_NIL
) {
1025 struct ordered_hashmap_entry
*old_tail
;
1027 old_tail
= ordered_bucket_at(lh
, lh
->iterate_list_tail
);
1028 assert(old_tail
->iterate_next
== IDX_NIL
);
1029 old_tail
->iterate_next
= IDX_PUT
;
1032 lh
->iterate_list_tail
= IDX_PUT
;
1033 if (lh
->iterate_list_head
== IDX_NIL
)
1034 lh
->iterate_list_head
= IDX_PUT
;
1037 assert_se(hashmap_put_robin_hood(h
, idx
, swap
) == false);
1040 #if ENABLE_DEBUG_HASHMAP
1041 h
->debug
.max_entries
= MAX(h
->debug
.max_entries
, n_entries(h
));
1046 #define hashmap_put_boldly(h, idx, swap, may_resize) \
1047 hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
1050 * Returns 0 if resize is not needed.
1051 * 1 if successfully resized.
1052 * -ENOMEM on allocation failure.
1054 static int resize_buckets(HashmapBase
*h
, unsigned entries_add
) {
1055 struct swap_entries swap
;
1057 dib_raw_t
*old_dibs
, *new_dibs
;
1058 const struct hashmap_type_info
*hi
;
1059 unsigned idx
, optimal_idx
;
1060 unsigned old_n_buckets
, new_n_buckets
, n_rehashed
, new_n_entries
;
1066 hi
= &hashmap_type_info
[h
->type
];
1067 new_n_entries
= n_entries(h
) + entries_add
;
1070 if (_unlikely_(new_n_entries
< entries_add
))
1073 /* For direct storage we allow 100% load, because it's tiny. */
1074 if (!h
->has_indirect
&& new_n_entries
<= hi
->n_direct_buckets
)
1078 * Load factor = n/m = 1 - (1/INV_KEEP_FREE).
1079 * From it follows: m = n + n/(INV_KEEP_FREE - 1)
1081 new_n_buckets
= new_n_entries
+ new_n_entries
/ (INV_KEEP_FREE
- 1);
1083 if (_unlikely_(new_n_buckets
< new_n_entries
))
1086 if (_unlikely_(new_n_buckets
> UINT_MAX
/ (hi
->entry_size
+ sizeof(dib_raw_t
))))
1089 old_n_buckets
= n_buckets(h
);
1091 if (_likely_(new_n_buckets
<= old_n_buckets
))
1094 new_shift
= log2u_round_up(MAX(
1095 new_n_buckets
* (hi
->entry_size
+ sizeof(dib_raw_t
)),
1096 2 * sizeof(struct direct_storage
)));
1098 /* Realloc storage (buckets and DIB array). */
1099 new_storage
= realloc(h
->has_indirect
? h
->indirect
.storage
: NULL
,
1104 /* Must upgrade direct to indirect storage. */
1105 if (!h
->has_indirect
) {
1106 memcpy(new_storage
, h
->direct
.storage
,
1107 old_n_buckets
* (hi
->entry_size
+ sizeof(dib_raw_t
)));
1108 h
->indirect
.n_entries
= h
->n_direct_entries
;
1109 h
->indirect
.idx_lowest_entry
= 0;
1110 h
->n_direct_entries
= 0;
1113 /* Get a new hash key. If we've just upgraded to indirect storage,
1114 * allow reusing a previously generated key. It's still a different key
1115 * from the shared one that we used for direct storage. */
1116 get_hash_key(h
->indirect
.hash_key
, !h
->has_indirect
);
1118 h
->has_indirect
= true;
1119 h
->indirect
.storage
= new_storage
;
1120 h
->indirect
.n_buckets
= (1U << new_shift
) /
1121 (hi
->entry_size
+ sizeof(dib_raw_t
));
1123 old_dibs
= (dib_raw_t
*)((uint8_t*) new_storage
+ hi
->entry_size
* old_n_buckets
);
1124 new_dibs
= dib_raw_ptr(h
);
1127 * Move the DIB array to the new place, replacing valid DIB values with
1128 * DIB_RAW_REHASH to indicate all of the used buckets need rehashing.
1129 * Note: Overlap is not possible, because we have at least doubled the
1130 * number of buckets and dib_raw_t is smaller than any entry type.
1132 for (idx
= 0; idx
< old_n_buckets
; idx
++) {
1133 assert(old_dibs
[idx
] != DIB_RAW_REHASH
);
1134 new_dibs
[idx
] = old_dibs
[idx
] == DIB_RAW_FREE
? DIB_RAW_FREE
1138 /* Zero the area of newly added entries (including the old DIB area) */
1139 memzero(bucket_at(h
, old_n_buckets
),
1140 (n_buckets(h
) - old_n_buckets
) * hi
->entry_size
);
1142 /* The upper half of the new DIB array needs initialization */
1143 memset(&new_dibs
[old_n_buckets
], DIB_RAW_INIT
,
1144 (n_buckets(h
) - old_n_buckets
) * sizeof(dib_raw_t
));
1146 /* Rehash entries that need it */
1148 for (idx
= 0; idx
< old_n_buckets
; idx
++) {
1149 if (new_dibs
[idx
] != DIB_RAW_REHASH
)
1152 optimal_idx
= bucket_hash(h
, bucket_at(h
, idx
)->key
);
1155 * Not much to do if by luck the entry hashes to its current
1156 * location. Just set its DIB.
1158 if (optimal_idx
== idx
) {
1164 new_dibs
[idx
] = DIB_RAW_FREE
;
1165 bucket_move_entry(h
, &swap
, idx
, IDX_PUT
);
1166 /* bucket_move_entry does not clear the source */
1167 memzero(bucket_at(h
, idx
), hi
->entry_size
);
1171 * Find the new bucket for the current entry. This may make
1172 * another entry homeless and load it into IDX_PUT.
1174 rehash_next
= hashmap_put_robin_hood(h
, optimal_idx
, &swap
);
1177 /* Did the current entry displace another one? */
1179 optimal_idx
= bucket_hash(h
, bucket_at_swap(&swap
, IDX_PUT
)->p
.b
.key
);
1180 } while (rehash_next
);
1183 assert(n_rehashed
== n_entries(h
));
1189 * Finds an entry with a matching key
1190 * Returns: index of the found entry, or IDX_NIL if not found.
1192 static unsigned base_bucket_scan(HashmapBase
*h
, unsigned idx
, const void *key
) {
1193 struct hashmap_base_entry
*e
;
1194 unsigned dib
, distance
;
1195 dib_raw_t
*dibs
= dib_raw_ptr(h
);
1197 assert(idx
< n_buckets(h
));
1199 for (distance
= 0; ; distance
++) {
1200 if (dibs
[idx
] == DIB_RAW_FREE
)
1203 dib
= bucket_calculate_dib(h
, idx
, dibs
[idx
]);
1207 if (dib
== distance
) {
1208 e
= bucket_at(h
, idx
);
1209 if (h
->hash_ops
->compare(e
->key
, key
) == 0)
1213 idx
= next_idx(h
, idx
);
1216 #define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
1218 int hashmap_put(Hashmap
*h
, const void *key
, void *value
) {
1219 struct swap_entries swap
;
1220 struct plain_hashmap_entry
*e
;
1225 hash
= bucket_hash(h
, key
);
1226 idx
= bucket_scan(h
, hash
, key
);
1227 if (idx
!= IDX_NIL
) {
1228 e
= plain_bucket_at(h
, idx
);
1229 if (e
->value
== value
)
1234 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1237 return hashmap_put_boldly(h
, hash
, &swap
, true);
1240 int set_put(Set
*s
, const void *key
) {
1241 struct swap_entries swap
;
1242 struct hashmap_base_entry
*e
;
1247 hash
= bucket_hash(s
, key
);
1248 idx
= bucket_scan(s
, hash
, key
);
1252 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1254 return hashmap_put_boldly(s
, hash
, &swap
, true);
1257 int hashmap_replace(Hashmap
*h
, const void *key
, void *value
) {
1258 struct swap_entries swap
;
1259 struct plain_hashmap_entry
*e
;
1264 hash
= bucket_hash(h
, key
);
1265 idx
= bucket_scan(h
, hash
, key
);
1266 if (idx
!= IDX_NIL
) {
1267 e
= plain_bucket_at(h
, idx
);
1268 #if ENABLE_DEBUG_HASHMAP
1269 /* Although the key is equal, the key pointer may have changed,
1270 * and this would break our assumption for iterating. So count
1271 * this operation as incompatible with iteration. */
1272 if (e
->b
.key
!= key
) {
1273 h
->b
.debug
.put_count
++;
1274 h
->b
.debug
.rem_count
++;
1275 h
->b
.debug
.last_rem_idx
= idx
;
1283 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1286 return hashmap_put_boldly(h
, hash
, &swap
, true);
1289 int hashmap_update(Hashmap
*h
, const void *key
, void *value
) {
1290 struct plain_hashmap_entry
*e
;
1295 hash
= bucket_hash(h
, key
);
1296 idx
= bucket_scan(h
, hash
, key
);
1300 e
= plain_bucket_at(h
, idx
);
1305 void *internal_hashmap_get(HashmapBase
*h
, const void *key
) {
1306 struct hashmap_base_entry
*e
;
1312 hash
= bucket_hash(h
, key
);
1313 idx
= bucket_scan(h
, hash
, key
);
1317 e
= bucket_at(h
, idx
);
1318 return entry_value(h
, e
);
1321 void *hashmap_get2(Hashmap
*h
, const void *key
, void **key2
) {
1322 struct plain_hashmap_entry
*e
;
1328 hash
= bucket_hash(h
, key
);
1329 idx
= bucket_scan(h
, hash
, key
);
1333 e
= plain_bucket_at(h
, idx
);
1335 *key2
= (void*) e
->b
.key
;
1340 bool internal_hashmap_contains(HashmapBase
*h
, const void *key
) {
1346 hash
= bucket_hash(h
, key
);
1347 return bucket_scan(h
, hash
, key
) != IDX_NIL
;
1350 void *internal_hashmap_remove(HashmapBase
*h
, const void *key
) {
1351 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 data
= entry_value(h
, e
);
1365 remove_entry(h
, idx
);
1370 void *hashmap_remove2(Hashmap
*h
, const void *key
, void **rkey
) {
1371 struct plain_hashmap_entry
*e
;
1381 hash
= bucket_hash(h
, key
);
1382 idx
= bucket_scan(h
, hash
, key
);
1383 if (idx
== IDX_NIL
) {
1389 e
= plain_bucket_at(h
, idx
);
1392 *rkey
= (void*) e
->b
.key
;
1394 remove_entry(h
, idx
);
1399 int hashmap_remove_and_put(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
1400 struct swap_entries swap
;
1401 struct plain_hashmap_entry
*e
;
1402 unsigned old_hash
, new_hash
, idx
;
1407 old_hash
= bucket_hash(h
, old_key
);
1408 idx
= bucket_scan(h
, old_hash
, old_key
);
1412 new_hash
= bucket_hash(h
, new_key
);
1413 if (bucket_scan(h
, new_hash
, new_key
) != IDX_NIL
)
1416 remove_entry(h
, idx
);
1418 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1421 assert_se(hashmap_put_boldly(h
, new_hash
, &swap
, false) == 1);
1426 int set_remove_and_put(Set
*s
, const void *old_key
, const void *new_key
) {
1427 struct swap_entries swap
;
1428 struct hashmap_base_entry
*e
;
1429 unsigned old_hash
, new_hash
, idx
;
1434 old_hash
= bucket_hash(s
, old_key
);
1435 idx
= bucket_scan(s
, old_hash
, old_key
);
1439 new_hash
= bucket_hash(s
, new_key
);
1440 if (bucket_scan(s
, new_hash
, new_key
) != IDX_NIL
)
1443 remove_entry(s
, idx
);
1445 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1447 assert_se(hashmap_put_boldly(s
, new_hash
, &swap
, false) == 1);
1452 int hashmap_remove_and_replace(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
1453 struct swap_entries swap
;
1454 struct plain_hashmap_entry
*e
;
1455 unsigned old_hash
, new_hash
, idx_old
, idx_new
;
1460 old_hash
= bucket_hash(h
, old_key
);
1461 idx_old
= bucket_scan(h
, old_hash
, old_key
);
1462 if (idx_old
== IDX_NIL
)
1465 old_key
= bucket_at(HASHMAP_BASE(h
), idx_old
)->key
;
1467 new_hash
= bucket_hash(h
, new_key
);
1468 idx_new
= bucket_scan(h
, new_hash
, new_key
);
1469 if (idx_new
!= IDX_NIL
)
1470 if (idx_old
!= idx_new
) {
1471 remove_entry(h
, idx_new
);
1472 /* Compensate for a possible backward shift. */
1473 if (old_key
!= bucket_at(HASHMAP_BASE(h
), idx_old
)->key
)
1474 idx_old
= prev_idx(HASHMAP_BASE(h
), idx_old
);
1475 assert(old_key
== bucket_at(HASHMAP_BASE(h
), idx_old
)->key
);
1478 remove_entry(h
, idx_old
);
1480 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1483 assert_se(hashmap_put_boldly(h
, new_hash
, &swap
, false) == 1);
1488 void *hashmap_remove_value(Hashmap
*h
, const void *key
, void *value
) {
1489 struct plain_hashmap_entry
*e
;
1495 hash
= bucket_hash(h
, key
);
1496 idx
= bucket_scan(h
, hash
, key
);
1500 e
= plain_bucket_at(h
, idx
);
1501 if (e
->value
!= value
)
1504 remove_entry(h
, idx
);
1509 static unsigned find_first_entry(HashmapBase
*h
) {
1510 Iterator i
= ITERATOR_FIRST
;
1512 if (!h
|| !n_entries(h
))
1515 return hashmap_iterate_entry(h
, &i
);
1518 void *internal_hashmap_first(HashmapBase
*h
) {
1521 idx
= find_first_entry(h
);
1525 return entry_value(h
, bucket_at(h
, idx
));
1528 void *internal_hashmap_first_key(HashmapBase
*h
) {
1529 struct hashmap_base_entry
*e
;
1532 idx
= find_first_entry(h
);
1536 e
= bucket_at(h
, idx
);
1537 return (void*) e
->key
;
1540 void *internal_hashmap_steal_first(HashmapBase
*h
) {
1541 struct hashmap_base_entry
*e
;
1545 idx
= find_first_entry(h
);
1549 e
= bucket_at(h
, idx
);
1550 data
= entry_value(h
, e
);
1551 remove_entry(h
, idx
);
1556 void *internal_hashmap_steal_first_key(HashmapBase
*h
) {
1557 struct hashmap_base_entry
*e
;
1561 idx
= find_first_entry(h
);
1565 e
= bucket_at(h
, idx
);
1566 key
= (void*) e
->key
;
1567 remove_entry(h
, idx
);
1572 unsigned internal_hashmap_size(HashmapBase
*h
) {
1577 return n_entries(h
);
1580 unsigned internal_hashmap_buckets(HashmapBase
*h
) {
1585 return n_buckets(h
);
1588 int internal_hashmap_merge(Hashmap
*h
, Hashmap
*other
) {
1594 HASHMAP_FOREACH_IDX(idx
, HASHMAP_BASE(other
), i
) {
1595 struct plain_hashmap_entry
*pe
= plain_bucket_at(other
, idx
);
1598 r
= hashmap_put(h
, pe
->b
.key
, pe
->value
);
1599 if (r
< 0 && r
!= -EEXIST
)
1606 int set_merge(Set
*s
, Set
*other
) {
1612 HASHMAP_FOREACH_IDX(idx
, HASHMAP_BASE(other
), i
) {
1613 struct set_entry
*se
= set_bucket_at(other
, idx
);
1616 r
= set_put(s
, se
->b
.key
);
1624 int internal_hashmap_reserve(HashmapBase
*h
, unsigned entries_add
) {
1629 r
= resize_buckets(h
, entries_add
);
1637 * The same as hashmap_merge(), but every new item from other is moved to h.
1638 * Keys already in h are skipped and stay in other.
1639 * Returns: 0 on success.
1640 * -ENOMEM on alloc failure, in which case no move has been done.
1642 int internal_hashmap_move(HashmapBase
*h
, HashmapBase
*other
) {
1643 struct swap_entries swap
;
1644 struct hashmap_base_entry
*e
, *n
;
1654 assert(other
->type
== h
->type
);
1657 * This reserves buckets for the worst case, where none of other's
1658 * entries are yet present in h. This is preferable to risking
1659 * an allocation failure in the middle of the moving and having to
1660 * rollback or return a partial result.
1662 r
= resize_buckets(h
, n_entries(other
));
1666 HASHMAP_FOREACH_IDX(idx
, other
, i
) {
1669 e
= bucket_at(other
, idx
);
1670 h_hash
= bucket_hash(h
, e
->key
);
1671 if (bucket_scan(h
, h_hash
, e
->key
) != IDX_NIL
)
1674 n
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1676 if (h
->type
!= HASHMAP_TYPE_SET
)
1677 ((struct plain_hashmap_entry
*) n
)->value
=
1678 ((struct plain_hashmap_entry
*) e
)->value
;
1679 assert_se(hashmap_put_boldly(h
, h_hash
, &swap
, false) == 1);
1681 remove_entry(other
, idx
);
1687 int internal_hashmap_move_one(HashmapBase
*h
, HashmapBase
*other
, const void *key
) {
1688 struct swap_entries swap
;
1689 unsigned h_hash
, other_hash
, idx
;
1690 struct hashmap_base_entry
*e
, *n
;
1695 h_hash
= bucket_hash(h
, key
);
1696 if (bucket_scan(h
, h_hash
, key
) != IDX_NIL
)
1702 assert(other
->type
== h
->type
);
1704 other_hash
= bucket_hash(other
, key
);
1705 idx
= bucket_scan(other
, other_hash
, key
);
1709 e
= bucket_at(other
, idx
);
1711 n
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1713 if (h
->type
!= HASHMAP_TYPE_SET
)
1714 ((struct plain_hashmap_entry
*) n
)->value
=
1715 ((struct plain_hashmap_entry
*) e
)->value
;
1716 r
= hashmap_put_boldly(h
, h_hash
, &swap
, true);
1720 remove_entry(other
, idx
);
1724 HashmapBase
*internal_hashmap_copy(HashmapBase
*h
) {
1730 copy
= hashmap_base_new(h
->hash_ops
, h
->type HASHMAP_DEBUG_SRC_ARGS
);
1735 case HASHMAP_TYPE_PLAIN
:
1736 case HASHMAP_TYPE_ORDERED
:
1737 r
= hashmap_merge((Hashmap
*)copy
, (Hashmap
*)h
);
1739 case HASHMAP_TYPE_SET
:
1740 r
= set_merge((Set
*)copy
, (Set
*)h
);
1743 assert_not_reached("Unknown hashmap type");
1747 internal_hashmap_free(copy
);
1754 char **internal_hashmap_get_strv(HashmapBase
*h
) {
1759 sv
= new(char*, n_entries(h
)+1);
1764 HASHMAP_FOREACH_IDX(idx
, h
, i
)
1765 sv
[n
++] = entry_value(h
, bucket_at(h
, idx
));
1771 void *ordered_hashmap_next(OrderedHashmap
*h
, const void *key
) {
1772 struct ordered_hashmap_entry
*e
;
1778 hash
= bucket_hash(h
, key
);
1779 idx
= bucket_scan(h
, hash
, key
);
1783 e
= ordered_bucket_at(h
, idx
);
1784 if (e
->iterate_next
== IDX_NIL
)
1786 return ordered_bucket_at(h
, e
->iterate_next
)->p
.value
;
1789 int set_consume(Set
*s
, void *value
) {
1795 r
= set_put(s
, value
);
1802 int set_put_strdup(Set
*s
, const char *p
) {
1808 if (set_contains(s
, (char*) p
))
1815 return set_consume(s
, c
);
1818 int set_put_strdupv(Set
*s
, char **l
) {
1824 STRV_FOREACH(i
, l
) {
1825 r
= set_put_strdup(s
, *i
);
1835 int set_put_strsplit(Set
*s
, const char *v
, const char *separators
, ExtractFlags flags
) {
1845 r
= extract_first_word(&p
, &word
, separators
, flags
);
1849 r
= set_consume(s
, word
);