1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
4 This file is part of systemd.
6 Copyright 2010 Lennart Poettering
7 Copyright 2014 Michal Schmidt
9 systemd is free software; you can redistribute it and/or modify it
10 under the terms of the GNU Lesser General Public License as published by
11 the Free Software Foundation; either version 2.1 of the License, or
12 (at your option) any later version.
14 systemd is distributed in the hope that it will be useful, but
15 WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 Lesser General Public License for more details.
19 You should have received a copy of the GNU Lesser General Public License
20 along with systemd; If not, see <http://www.gnu.org/licenses/>.
28 #include "alloc-util.h"
32 #include "process-util.h"
33 #include "random-util.h"
35 #include "siphash24.h"
39 #ifdef ENABLE_DEBUG_HASHMAP
44 * Implementation of hashmaps.
46 * - uses less RAM compared to closed addressing (chaining), because
47 * our entries are small (especially in Sets, which tend to contain
48 * the majority of entries in systemd).
49 * Collision resolution: Robin Hood
50 * - tends to equalize displacement of entries from their optimal buckets.
51 * Probe sequence: linear
52 * - though theoretically worse than random probing/uniform hashing/double
53 * hashing, it is good for cache locality.
56 * Celis, P. 1986. Robin Hood Hashing.
57 * Ph.D. Dissertation. University of Waterloo, Waterloo, Ont., Canada, Canada.
58 * https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
59 * - The results are derived for random probing. Suggests deletion with
60 * tombstones and two mean-centered search methods. None of that works
61 * well for linear probing.
63 * Janson, S. 2005. Individual displacements for linear probing hashing with different insertion policies.
64 * ACM Trans. Algorithms 1, 2 (October 2005), 177-213.
65 * DOI=10.1145/1103963.1103964 http://doi.acm.org/10.1145/1103963.1103964
66 * http://www.math.uu.se/~svante/papers/sj157.pdf
67 * - Applies to Robin Hood with linear probing. Contains remarks on
68 * the unsuitability of mean-centered search with linear probing.
70 * Viola, A. 2005. Exact distribution of individual displacements in linear probing hashing.
71 * ACM Trans. Algorithms 1, 2 (October 2005), 214-242.
72 * DOI=10.1145/1103963.1103965 http://doi.acm.org/10.1145/1103963.1103965
73 * - Similar to Janson. Note that Viola writes about C_{m,n} (number of probes
74 * in a successful search), and Janson writes about displacement. C = d + 1.
76 * Goossaert, E. 2013. Robin Hood hashing: backward shift deletion.
77 * http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
78 * - Explanation of backward shift deletion with pictures.
80 * Khuong, P. 2013. The Other Robin Hood Hashing.
81 * http://www.pvk.ca/Blog/2013/11/26/the-other-robin-hood-hashing/
82 * - Short summary of random vs. linear probing, and tombstones vs. backward shift.
86 * XXX Ideas for improvement:
87 * For unordered hashmaps, randomize iteration order, similarly to Perl:
88 * http://blog.booking.com/hardening-perls-hash-function.html
91 /* INV_KEEP_FREE = 1 / (1 - max_load_factor)
92 * e.g. 1 / (1 - 0.8) = 5 ... keep one fifth of the buckets free. */
93 #define INV_KEEP_FREE 5U
95 /* Fields common to entries of all hashmap/set types */
96 struct hashmap_base_entry
{
100 /* Entry types for specific hashmap/set types
101 * hashmap_base_entry must be at the beginning of each entry struct. */
103 struct plain_hashmap_entry
{
104 struct hashmap_base_entry b
;
108 struct ordered_hashmap_entry
{
109 struct plain_hashmap_entry p
;
110 unsigned iterate_next
, iterate_previous
;
114 struct hashmap_base_entry b
;
117 /* In several functions it is advantageous to have the hash table extended
118 * virtually by a couple of additional buckets. We reserve special index values
119 * for these "swap" buckets. */
120 #define _IDX_SWAP_BEGIN (UINT_MAX - 3)
121 #define IDX_PUT (_IDX_SWAP_BEGIN + 0)
122 #define IDX_TMP (_IDX_SWAP_BEGIN + 1)
123 #define _IDX_SWAP_END (_IDX_SWAP_BEGIN + 2)
125 #define IDX_FIRST (UINT_MAX - 1) /* special index for freshly initialized iterators */
126 #define IDX_NIL UINT_MAX /* special index value meaning "none" or "end" */
128 assert_cc(IDX_FIRST
== _IDX_SWAP_END
);
129 assert_cc(IDX_FIRST
== _IDX_ITERATOR_FIRST
);
131 /* Storage space for the "swap" buckets.
132 * All entry types can fit into a ordered_hashmap_entry. */
133 struct swap_entries
{
134 struct ordered_hashmap_entry e
[_IDX_SWAP_END
- _IDX_SWAP_BEGIN
];
137 /* Distance from Initial Bucket */
138 typedef uint8_t dib_raw_t
;
139 #define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */
140 #define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */
141 #define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */
142 #define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */
144 #define DIB_FREE UINT_MAX
146 #ifdef ENABLE_DEBUG_HASHMAP
147 struct hashmap_debug_info
{
148 LIST_FIELDS(struct hashmap_debug_info
, debug_list
);
149 unsigned max_entries
; /* high watermark of n_entries */
151 /* who allocated this hashmap */
156 /* fields to detect modification while iterating */
157 unsigned put_count
; /* counts puts into the hashmap */
158 unsigned rem_count
; /* counts removals from hashmap */
159 unsigned last_rem_idx
; /* remembers last removal index */
162 /* Tracks all existing hashmaps. Get at it from gdb. See sd_dump_hashmaps.py */
163 static LIST_HEAD(struct hashmap_debug_info
, hashmap_debug_list
);
164 static pthread_mutex_t hashmap_debug_list_mutex
= PTHREAD_MUTEX_INITIALIZER
;
166 #define HASHMAP_DEBUG_FIELDS struct hashmap_debug_info debug;
168 #else /* !ENABLE_DEBUG_HASHMAP */
169 #define HASHMAP_DEBUG_FIELDS
170 #endif /* ENABLE_DEBUG_HASHMAP */
174 HASHMAP_TYPE_ORDERED
,
179 struct _packed_ indirect_storage
{
180 char *storage
; /* where buckets and DIBs are stored */
181 uint8_t hash_key
[HASH_KEY_SIZE
]; /* hash key; changes during resize */
183 unsigned n_entries
; /* number of stored entries */
184 unsigned n_buckets
; /* number of buckets */
186 unsigned idx_lowest_entry
; /* Index below which all buckets are free.
187 Makes "while(hashmap_steal_first())" loops
188 O(n) instead of O(n^2) for unordered hashmaps. */
189 uint8_t _pad
[3]; /* padding for the whole HashmapBase */
190 /* The bitfields in HashmapBase complete the alignment of the whole thing. */
193 struct direct_storage
{
194 /* This gives us 39 bytes on 64bit, or 35 bytes on 32bit.
195 * That's room for 4 set_entries + 4 DIB bytes + 3 unused bytes on 64bit,
196 * or 7 set_entries + 7 DIB bytes + 0 unused bytes on 32bit. */
197 char storage
[sizeof(struct indirect_storage
)];
200 #define DIRECT_BUCKETS(entry_t) \
201 (sizeof(struct direct_storage) / (sizeof(entry_t) + sizeof(dib_raw_t)))
203 /* We should be able to store at least one entry directly. */
204 assert_cc(DIRECT_BUCKETS(struct ordered_hashmap_entry
) >= 1);
206 /* We have 3 bits for n_direct_entries. */
207 assert_cc(DIRECT_BUCKETS(struct set_entry
) < (1 << 3));
209 /* Hashmaps with directly stored entries all use this shared hash key.
210 * It's no big deal if the key is guessed, because there can be only
211 * a handful of directly stored entries in a hashmap. When a hashmap
212 * outgrows direct storage, it gets its own key for indirect storage. */
213 static uint8_t shared_hash_key
[HASH_KEY_SIZE
];
214 static bool shared_hash_key_initialized
;
216 /* Fields that all hashmap/set types must have */
218 const struct hash_ops
*hash_ops
; /* hash and compare ops to use */
221 struct indirect_storage indirect
; /* if has_indirect */
222 struct direct_storage direct
; /* if !has_indirect */
225 enum HashmapType type
:2; /* HASHMAP_TYPE_* */
226 bool has_indirect
:1; /* whether indirect storage is used */
227 unsigned n_direct_entries
:3; /* Number of entries in direct storage.
228 * Only valid if !has_indirect. */
229 bool from_pool
:1; /* whether was allocated from mempool */
230 HASHMAP_DEBUG_FIELDS
/* optional hashmap_debug_info */
233 /* Specific hash types
234 * HashmapBase must be at the beginning of each hashmap struct. */
237 struct HashmapBase b
;
240 struct OrderedHashmap
{
241 struct HashmapBase b
;
242 unsigned iterate_list_head
, iterate_list_tail
;
246 struct HashmapBase b
;
249 DEFINE_MEMPOOL(hashmap_pool
, Hashmap
, 8);
250 DEFINE_MEMPOOL(ordered_hashmap_pool
, OrderedHashmap
, 8);
251 /* No need for a separate Set pool */
252 assert_cc(sizeof(Hashmap
) == sizeof(Set
));
254 struct hashmap_type_info
{
257 struct mempool
*mempool
;
258 unsigned n_direct_buckets
;
261 static const struct hashmap_type_info hashmap_type_info
[_HASHMAP_TYPE_MAX
] = {
262 [HASHMAP_TYPE_PLAIN
] = {
263 .head_size
= sizeof(Hashmap
),
264 .entry_size
= sizeof(struct plain_hashmap_entry
),
265 .mempool
= &hashmap_pool
,
266 .n_direct_buckets
= DIRECT_BUCKETS(struct plain_hashmap_entry
),
268 [HASHMAP_TYPE_ORDERED
] = {
269 .head_size
= sizeof(OrderedHashmap
),
270 .entry_size
= sizeof(struct ordered_hashmap_entry
),
271 .mempool
= &ordered_hashmap_pool
,
272 .n_direct_buckets
= DIRECT_BUCKETS(struct ordered_hashmap_entry
),
274 [HASHMAP_TYPE_SET
] = {
275 .head_size
= sizeof(Set
),
276 .entry_size
= sizeof(struct set_entry
),
277 .mempool
= &hashmap_pool
,
278 .n_direct_buckets
= DIRECT_BUCKETS(struct set_entry
),
282 void string_hash_func(const void *p
, struct siphash
*state
) {
283 siphash24_compress(p
, strlen(p
) + 1, state
);
286 int string_compare_func(const void *a
, const void *b
) {
290 const struct hash_ops string_hash_ops
= {
291 .hash
= string_hash_func
,
292 .compare
= string_compare_func
295 void trivial_hash_func(const void *p
, struct siphash
*state
) {
296 siphash24_compress(&p
, sizeof(p
), state
);
299 int trivial_compare_func(const void *a
, const void *b
) {
300 return a
< b
? -1 : (a
> b
? 1 : 0);
303 const struct hash_ops trivial_hash_ops
= {
304 .hash
= trivial_hash_func
,
305 .compare
= trivial_compare_func
308 void uint64_hash_func(const void *p
, struct siphash
*state
) {
309 siphash24_compress(p
, sizeof(uint64_t), state
);
312 int uint64_compare_func(const void *_a
, const void *_b
) {
314 a
= *(const uint64_t*) _a
;
315 b
= *(const uint64_t*) _b
;
316 return a
< b
? -1 : (a
> b
? 1 : 0);
319 const struct hash_ops uint64_hash_ops
= {
320 .hash
= uint64_hash_func
,
321 .compare
= uint64_compare_func
324 #if SIZEOF_DEV_T != 8
325 void devt_hash_func(const void *p
, struct siphash
*state
) {
326 siphash24_compress(p
, sizeof(dev_t
), state
);
329 int devt_compare_func(const void *_a
, const void *_b
) {
331 a
= *(const dev_t
*) _a
;
332 b
= *(const dev_t
*) _b
;
333 return a
< b
? -1 : (a
> b
? 1 : 0);
336 const struct hash_ops devt_hash_ops
= {
337 .hash
= devt_hash_func
,
338 .compare
= devt_compare_func
342 static unsigned n_buckets(HashmapBase
*h
) {
343 return h
->has_indirect
? h
->indirect
.n_buckets
344 : hashmap_type_info
[h
->type
].n_direct_buckets
;
347 static unsigned n_entries(HashmapBase
*h
) {
348 return h
->has_indirect
? h
->indirect
.n_entries
349 : h
->n_direct_entries
;
352 static void n_entries_inc(HashmapBase
*h
) {
354 h
->indirect
.n_entries
++;
356 h
->n_direct_entries
++;
359 static void n_entries_dec(HashmapBase
*h
) {
361 h
->indirect
.n_entries
--;
363 h
->n_direct_entries
--;
366 static char *storage_ptr(HashmapBase
*h
) {
367 return h
->has_indirect
? h
->indirect
.storage
371 static uint8_t *hash_key(HashmapBase
*h
) {
372 return h
->has_indirect
? h
->indirect
.hash_key
376 static unsigned base_bucket_hash(HashmapBase
*h
, const void *p
) {
377 struct siphash state
;
380 siphash24_init(&state
, hash_key(h
));
382 h
->hash_ops
->hash(p
, &state
);
384 hash
= siphash24_finalize(&state
);
386 return (unsigned) (hash
% n_buckets(h
));
388 #define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p)
390 static void get_hash_key(uint8_t hash_key
[HASH_KEY_SIZE
], bool reuse_is_ok
) {
391 static uint8_t current
[HASH_KEY_SIZE
];
392 static bool current_initialized
= false;
394 /* Returns a hash function key to use. In order to keep things
395 * fast we will not generate a new key each time we allocate a
396 * new hash table. Instead, we'll just reuse the most recently
397 * generated one, except if we never generated one or when we
398 * are rehashing an entire hash table because we reached a
401 if (!current_initialized
|| !reuse_is_ok
) {
402 random_bytes(current
, sizeof(current
));
403 current_initialized
= true;
406 memcpy(hash_key
, current
, sizeof(current
));
409 static struct hashmap_base_entry
*bucket_at(HashmapBase
*h
, unsigned idx
) {
410 return (struct hashmap_base_entry
*)
411 (storage_ptr(h
) + idx
* hashmap_type_info
[h
->type
].entry_size
);
414 static struct plain_hashmap_entry
*plain_bucket_at(Hashmap
*h
, unsigned idx
) {
415 return (struct plain_hashmap_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
418 static struct ordered_hashmap_entry
*ordered_bucket_at(OrderedHashmap
*h
, unsigned idx
) {
419 return (struct ordered_hashmap_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
422 static struct set_entry
*set_bucket_at(Set
*h
, unsigned idx
) {
423 return (struct set_entry
*) bucket_at(HASHMAP_BASE(h
), idx
);
426 static struct ordered_hashmap_entry
*bucket_at_swap(struct swap_entries
*swap
, unsigned idx
) {
427 return &swap
->e
[idx
- _IDX_SWAP_BEGIN
];
430 /* Returns a pointer to the bucket at index idx.
431 * Understands real indexes and swap indexes, hence "_virtual". */
432 static struct hashmap_base_entry
*bucket_at_virtual(HashmapBase
*h
, struct swap_entries
*swap
,
434 if (idx
< _IDX_SWAP_BEGIN
)
435 return bucket_at(h
, idx
);
437 if (idx
< _IDX_SWAP_END
)
438 return &bucket_at_swap(swap
, idx
)->p
.b
;
440 assert_not_reached("Invalid index");
443 static dib_raw_t
*dib_raw_ptr(HashmapBase
*h
) {
445 (storage_ptr(h
) + hashmap_type_info
[h
->type
].entry_size
* n_buckets(h
));
448 static unsigned bucket_distance(HashmapBase
*h
, unsigned idx
, unsigned from
) {
449 return idx
>= from
? idx
- from
450 : n_buckets(h
) + idx
- from
;
453 static unsigned bucket_calculate_dib(HashmapBase
*h
, unsigned idx
, dib_raw_t raw_dib
) {
454 unsigned initial_bucket
;
456 if (raw_dib
== DIB_RAW_FREE
)
459 if (_likely_(raw_dib
< DIB_RAW_OVERFLOW
))
463 * Having an overflow DIB value is very unlikely. The hash function
464 * would have to be bad. For example, in a table of size 2^24 filled
465 * to load factor 0.9 the maximum observed DIB is only about 60.
466 * In theory (assuming I used Maxima correctly), for an infinite size
467 * hash table with load factor 0.8 the probability of a given entry
468 * having DIB > 40 is 1.9e-8.
469 * This returns the correct DIB value by recomputing the hash value in
470 * the unlikely case. XXX Hitting this case could be a hint to rehash.
472 initial_bucket
= bucket_hash(h
, bucket_at(h
, idx
)->key
);
473 return bucket_distance(h
, idx
, initial_bucket
);
476 static void bucket_set_dib(HashmapBase
*h
, unsigned idx
, unsigned dib
) {
477 dib_raw_ptr(h
)[idx
] = dib
!= DIB_FREE
? MIN(dib
, DIB_RAW_OVERFLOW
) : DIB_RAW_FREE
;
480 static unsigned skip_free_buckets(HashmapBase
*h
, unsigned idx
) {
483 dibs
= dib_raw_ptr(h
);
485 for ( ; idx
< n_buckets(h
); idx
++)
486 if (dibs
[idx
] != DIB_RAW_FREE
)
492 static void bucket_mark_free(HashmapBase
*h
, unsigned idx
) {
493 memzero(bucket_at(h
, idx
), hashmap_type_info
[h
->type
].entry_size
);
494 bucket_set_dib(h
, idx
, DIB_FREE
);
497 static void bucket_move_entry(HashmapBase
*h
, struct swap_entries
*swap
,
498 unsigned from
, unsigned to
) {
499 struct hashmap_base_entry
*e_from
, *e_to
;
503 e_from
= bucket_at_virtual(h
, swap
, from
);
504 e_to
= bucket_at_virtual(h
, swap
, to
);
506 memcpy(e_to
, e_from
, hashmap_type_info
[h
->type
].entry_size
);
508 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
509 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
510 struct ordered_hashmap_entry
*le
, *le_to
;
512 le_to
= (struct ordered_hashmap_entry
*) e_to
;
514 if (le_to
->iterate_next
!= IDX_NIL
) {
515 le
= (struct ordered_hashmap_entry
*)
516 bucket_at_virtual(h
, swap
, le_to
->iterate_next
);
517 le
->iterate_previous
= to
;
520 if (le_to
->iterate_previous
!= IDX_NIL
) {
521 le
= (struct ordered_hashmap_entry
*)
522 bucket_at_virtual(h
, swap
, le_to
->iterate_previous
);
523 le
->iterate_next
= to
;
526 if (lh
->iterate_list_head
== from
)
527 lh
->iterate_list_head
= to
;
528 if (lh
->iterate_list_tail
== from
)
529 lh
->iterate_list_tail
= to
;
533 static unsigned next_idx(HashmapBase
*h
, unsigned idx
) {
534 return (idx
+ 1U) % n_buckets(h
);
537 static unsigned prev_idx(HashmapBase
*h
, unsigned idx
) {
538 return (n_buckets(h
) + idx
- 1U) % n_buckets(h
);
541 static void *entry_value(HashmapBase
*h
, struct hashmap_base_entry
*e
) {
544 case HASHMAP_TYPE_PLAIN
:
545 case HASHMAP_TYPE_ORDERED
:
546 return ((struct plain_hashmap_entry
*)e
)->value
;
548 case HASHMAP_TYPE_SET
:
549 return (void*) e
->key
;
552 assert_not_reached("Unknown hashmap type");
556 static void base_remove_entry(HashmapBase
*h
, unsigned idx
) {
557 unsigned left
, right
, prev
, dib
;
558 dib_raw_t raw_dib
, *dibs
;
560 dibs
= dib_raw_ptr(h
);
561 assert(dibs
[idx
] != DIB_RAW_FREE
);
563 #ifdef ENABLE_DEBUG_HASHMAP
564 h
->debug
.rem_count
++;
565 h
->debug
.last_rem_idx
= idx
;
569 /* Find the stop bucket ("right"). It is either free or has DIB == 0. */
570 for (right
= next_idx(h
, left
); ; right
= next_idx(h
, right
)) {
571 raw_dib
= dibs
[right
];
572 if (raw_dib
== 0 || raw_dib
== DIB_RAW_FREE
)
575 /* The buckets are not supposed to be all occupied and with DIB > 0.
576 * That would mean we could make everyone better off by shifting them
577 * backward. This scenario is impossible. */
578 assert(left
!= right
);
581 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
582 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
583 struct ordered_hashmap_entry
*le
= ordered_bucket_at(lh
, idx
);
585 if (le
->iterate_next
!= IDX_NIL
)
586 ordered_bucket_at(lh
, le
->iterate_next
)->iterate_previous
= le
->iterate_previous
;
588 lh
->iterate_list_tail
= le
->iterate_previous
;
590 if (le
->iterate_previous
!= IDX_NIL
)
591 ordered_bucket_at(lh
, le
->iterate_previous
)->iterate_next
= le
->iterate_next
;
593 lh
->iterate_list_head
= le
->iterate_next
;
596 /* Now shift all buckets in the interval (left, right) one step backwards */
597 for (prev
= left
, left
= next_idx(h
, left
); left
!= right
;
598 prev
= left
, left
= next_idx(h
, left
)) {
599 dib
= bucket_calculate_dib(h
, left
, dibs
[left
]);
601 bucket_move_entry(h
, NULL
, left
, prev
);
602 bucket_set_dib(h
, prev
, dib
- 1);
605 bucket_mark_free(h
, prev
);
608 #define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)
610 static unsigned hashmap_iterate_in_insertion_order(OrderedHashmap
*h
, Iterator
*i
) {
611 struct ordered_hashmap_entry
*e
;
617 if (i
->idx
== IDX_NIL
)
620 if (i
->idx
== IDX_FIRST
&& h
->iterate_list_head
== IDX_NIL
)
623 if (i
->idx
== IDX_FIRST
) {
624 idx
= h
->iterate_list_head
;
625 e
= ordered_bucket_at(h
, idx
);
628 e
= ordered_bucket_at(h
, idx
);
630 * We allow removing the current entry while iterating, but removal may cause
631 * a backward shift. The next entry may thus move one bucket to the left.
632 * To detect when it happens, we remember the key pointer of the entry we were
633 * going to iterate next. If it does not match, there was a backward shift.
635 if (e
->p
.b
.key
!= i
->next_key
) {
636 idx
= prev_idx(HASHMAP_BASE(h
), idx
);
637 e
= ordered_bucket_at(h
, idx
);
639 assert(e
->p
.b
.key
== i
->next_key
);
642 #ifdef ENABLE_DEBUG_HASHMAP
646 if (e
->iterate_next
!= IDX_NIL
) {
647 struct ordered_hashmap_entry
*n
;
648 i
->idx
= e
->iterate_next
;
649 n
= ordered_bucket_at(h
, i
->idx
);
650 i
->next_key
= n
->p
.b
.key
;
661 static unsigned hashmap_iterate_in_internal_order(HashmapBase
*h
, Iterator
*i
) {
667 if (i
->idx
== IDX_NIL
)
670 if (i
->idx
== IDX_FIRST
) {
671 /* fast forward to the first occupied bucket */
672 if (h
->has_indirect
) {
673 i
->idx
= skip_free_buckets(h
, h
->indirect
.idx_lowest_entry
);
674 h
->indirect
.idx_lowest_entry
= i
->idx
;
676 i
->idx
= skip_free_buckets(h
, 0);
678 if (i
->idx
== IDX_NIL
)
681 struct hashmap_base_entry
*e
;
685 e
= bucket_at(h
, i
->idx
);
687 * We allow removing the current entry while iterating, but removal may cause
688 * a backward shift. The next entry may thus move one bucket to the left.
689 * To detect when it happens, we remember the key pointer of the entry we were
690 * going to iterate next. If it does not match, there was a backward shift.
692 if (e
->key
!= i
->next_key
)
693 e
= bucket_at(h
, --i
->idx
);
695 assert(e
->key
== i
->next_key
);
699 #ifdef ENABLE_DEBUG_HASHMAP
703 i
->idx
= skip_free_buckets(h
, i
->idx
+ 1);
704 if (i
->idx
!= IDX_NIL
)
705 i
->next_key
= bucket_at(h
, i
->idx
)->key
;
716 static unsigned hashmap_iterate_entry(HashmapBase
*h
, Iterator
*i
) {
722 #ifdef ENABLE_DEBUG_HASHMAP
723 if (i
->idx
== IDX_FIRST
) {
724 i
->put_count
= h
->debug
.put_count
;
725 i
->rem_count
= h
->debug
.rem_count
;
727 /* While iterating, must not add any new entries */
728 assert(i
->put_count
== h
->debug
.put_count
);
729 /* ... or remove entries other than the current one */
730 assert(i
->rem_count
== h
->debug
.rem_count
||
731 (i
->rem_count
== h
->debug
.rem_count
- 1 &&
732 i
->prev_idx
== h
->debug
.last_rem_idx
));
733 /* Reset our removals counter */
734 i
->rem_count
= h
->debug
.rem_count
;
738 return h
->type
== HASHMAP_TYPE_ORDERED
? hashmap_iterate_in_insertion_order((OrderedHashmap
*) h
, i
)
739 : hashmap_iterate_in_internal_order(h
, i
);
742 bool internal_hashmap_iterate(HashmapBase
*h
, Iterator
*i
, void **value
, const void **key
) {
743 struct hashmap_base_entry
*e
;
747 idx
= hashmap_iterate_entry(h
, i
);
748 if (idx
== IDX_NIL
) {
757 e
= bucket_at(h
, idx
);
758 data
= entry_value(h
, e
);
767 bool set_iterate(Set
*s
, Iterator
*i
, void **value
) {
768 return internal_hashmap_iterate(HASHMAP_BASE(s
), i
, value
, NULL
);
771 #define HASHMAP_FOREACH_IDX(idx, h, i) \
772 for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \
774 (idx) = hashmap_iterate_entry((h), &(i)))
776 static void reset_direct_storage(HashmapBase
*h
) {
777 const struct hashmap_type_info
*hi
= &hashmap_type_info
[h
->type
];
780 assert(!h
->has_indirect
);
782 p
= mempset(h
->direct
.storage
, 0, hi
->entry_size
* hi
->n_direct_buckets
);
783 memset(p
, DIB_RAW_INIT
, sizeof(dib_raw_t
) * hi
->n_direct_buckets
);
786 static struct HashmapBase
*hashmap_base_new(const struct hash_ops
*hash_ops
, enum HashmapType type HASHMAP_DEBUG_PARAMS
) {
788 const struct hashmap_type_info
*hi
= &hashmap_type_info
[type
];
791 use_pool
= is_main_thread();
793 h
= use_pool
? mempool_alloc0_tile(hi
->mempool
) : malloc0(hi
->head_size
);
799 h
->from_pool
= use_pool
;
800 h
->hash_ops
= hash_ops
? hash_ops
: &trivial_hash_ops
;
802 if (type
== HASHMAP_TYPE_ORDERED
) {
803 OrderedHashmap
*lh
= (OrderedHashmap
*)h
;
804 lh
->iterate_list_head
= lh
->iterate_list_tail
= IDX_NIL
;
807 reset_direct_storage(h
);
809 if (!shared_hash_key_initialized
) {
810 random_bytes(shared_hash_key
, sizeof(shared_hash_key
));
811 shared_hash_key_initialized
= true;
814 #ifdef ENABLE_DEBUG_HASHMAP
815 h
->debug
.func
= func
;
816 h
->debug
.file
= file
;
817 h
->debug
.line
= line
;
818 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex
) == 0);
819 LIST_PREPEND(debug_list
, hashmap_debug_list
, &h
->debug
);
820 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex
) == 0);
826 Hashmap
*internal_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
827 return (Hashmap
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS
);
830 OrderedHashmap
*internal_ordered_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
831 return (OrderedHashmap
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS
);
834 Set
*internal_set_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
835 return (Set
*) hashmap_base_new(hash_ops
, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS
);
838 static int hashmap_base_ensure_allocated(HashmapBase
**h
, const struct hash_ops
*hash_ops
,
839 enum HashmapType type HASHMAP_DEBUG_PARAMS
) {
847 q
= hashmap_base_new(hash_ops
, type HASHMAP_DEBUG_PASS_ARGS
);
855 int internal_hashmap_ensure_allocated(Hashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
856 return hashmap_base_ensure_allocated((HashmapBase
**)h
, hash_ops
, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS
);
859 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
860 return hashmap_base_ensure_allocated((HashmapBase
**)h
, hash_ops
, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS
);
863 int internal_set_ensure_allocated(Set
**s
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
) {
864 return hashmap_base_ensure_allocated((HashmapBase
**)s
, hash_ops
, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS
);
867 static void hashmap_free_no_clear(HashmapBase
*h
) {
868 assert(!h
->has_indirect
);
869 assert(!h
->n_direct_entries
);
871 #ifdef ENABLE_DEBUG_HASHMAP
872 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex
) == 0);
873 LIST_REMOVE(debug_list
, hashmap_debug_list
, &h
->debug
);
874 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex
) == 0);
878 mempool_free_tile(hashmap_type_info
[h
->type
].mempool
, h
);
883 HashmapBase
*internal_hashmap_free(HashmapBase
*h
) {
885 /* Free the hashmap, but nothing in it */
888 internal_hashmap_clear(h
);
889 hashmap_free_no_clear(h
);
895 HashmapBase
*internal_hashmap_free_free(HashmapBase
*h
) {
897 /* Free the hashmap and all data objects in it, but not the
901 internal_hashmap_clear_free(h
);
902 hashmap_free_no_clear(h
);
908 Hashmap
*hashmap_free_free_free(Hashmap
*h
) {
910 /* Free the hashmap and all data and key objects in it */
913 hashmap_clear_free_free(h
);
914 hashmap_free_no_clear(HASHMAP_BASE(h
));
920 void internal_hashmap_clear(HashmapBase
*h
) {
924 if (h
->has_indirect
) {
925 free(h
->indirect
.storage
);
926 h
->has_indirect
= false;
929 h
->n_direct_entries
= 0;
930 reset_direct_storage(h
);
932 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
933 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
934 lh
->iterate_list_head
= lh
->iterate_list_tail
= IDX_NIL
;
938 void internal_hashmap_clear_free(HashmapBase
*h
) {
944 for (idx
= skip_free_buckets(h
, 0); idx
!= IDX_NIL
;
945 idx
= skip_free_buckets(h
, idx
+ 1))
946 free(entry_value(h
, bucket_at(h
, idx
)));
948 internal_hashmap_clear(h
);
951 void hashmap_clear_free_free(Hashmap
*h
) {
957 for (idx
= skip_free_buckets(HASHMAP_BASE(h
), 0); idx
!= IDX_NIL
;
958 idx
= skip_free_buckets(HASHMAP_BASE(h
), idx
+ 1)) {
959 struct plain_hashmap_entry
*e
= plain_bucket_at(h
, idx
);
960 free((void*)e
->b
.key
);
964 internal_hashmap_clear(HASHMAP_BASE(h
));
967 static int resize_buckets(HashmapBase
*h
, unsigned entries_add
);
970 * Finds an empty bucket to put an entry into, starting the scan at 'idx'.
971 * Performs Robin Hood swaps as it goes. The entry to put must be placed
972 * by the caller into swap slot IDX_PUT.
973 * If used for in-place resizing, may leave a displaced entry in swap slot
974 * IDX_PUT. Caller must rehash it next.
975 * Returns: true if it left a displaced entry to rehash next in IDX_PUT,
978 static bool hashmap_put_robin_hood(HashmapBase
*h
, unsigned idx
,
979 struct swap_entries
*swap
) {
980 dib_raw_t raw_dib
, *dibs
;
981 unsigned dib
, distance
;
983 #ifdef ENABLE_DEBUG_HASHMAP
984 h
->debug
.put_count
++;
987 dibs
= dib_raw_ptr(h
);
989 for (distance
= 0; ; distance
++) {
991 if (raw_dib
== DIB_RAW_FREE
|| raw_dib
== DIB_RAW_REHASH
) {
992 if (raw_dib
== DIB_RAW_REHASH
)
993 bucket_move_entry(h
, swap
, idx
, IDX_TMP
);
995 if (h
->has_indirect
&& h
->indirect
.idx_lowest_entry
> idx
)
996 h
->indirect
.idx_lowest_entry
= idx
;
998 bucket_set_dib(h
, idx
, distance
);
999 bucket_move_entry(h
, swap
, IDX_PUT
, idx
);
1000 if (raw_dib
== DIB_RAW_REHASH
) {
1001 bucket_move_entry(h
, swap
, IDX_TMP
, IDX_PUT
);
1008 dib
= bucket_calculate_dib(h
, idx
, raw_dib
);
1010 if (dib
< distance
) {
1011 /* Found a wealthier entry. Go Robin Hood! */
1012 bucket_set_dib(h
, idx
, distance
);
1014 /* swap the entries */
1015 bucket_move_entry(h
, swap
, idx
, IDX_TMP
);
1016 bucket_move_entry(h
, swap
, IDX_PUT
, idx
);
1017 bucket_move_entry(h
, swap
, IDX_TMP
, IDX_PUT
);
1022 idx
= next_idx(h
, idx
);
1027 * Puts an entry into a hashmap, boldly - no check whether key already exists.
1028 * The caller must place the entry (only its key and value, not link indexes)
1029 * in swap slot IDX_PUT.
1030 * Caller must ensure: the key does not exist yet in the hashmap.
1031 * that resize is not needed if !may_resize.
1032 * Returns: 1 if entry was put successfully.
1033 * -ENOMEM if may_resize==true and resize failed with -ENOMEM.
1034 * Cannot return -ENOMEM if !may_resize.
1036 static int hashmap_base_put_boldly(HashmapBase
*h
, unsigned idx
,
1037 struct swap_entries
*swap
, bool may_resize
) {
1038 struct ordered_hashmap_entry
*new_entry
;
1041 assert(idx
< n_buckets(h
));
1043 new_entry
= bucket_at_swap(swap
, IDX_PUT
);
1046 r
= resize_buckets(h
, 1);
1050 idx
= bucket_hash(h
, new_entry
->p
.b
.key
);
1052 assert(n_entries(h
) < n_buckets(h
));
1054 if (h
->type
== HASHMAP_TYPE_ORDERED
) {
1055 OrderedHashmap
*lh
= (OrderedHashmap
*) h
;
1057 new_entry
->iterate_next
= IDX_NIL
;
1058 new_entry
->iterate_previous
= lh
->iterate_list_tail
;
1060 if (lh
->iterate_list_tail
!= IDX_NIL
) {
1061 struct ordered_hashmap_entry
*old_tail
;
1063 old_tail
= ordered_bucket_at(lh
, lh
->iterate_list_tail
);
1064 assert(old_tail
->iterate_next
== IDX_NIL
);
1065 old_tail
->iterate_next
= IDX_PUT
;
1068 lh
->iterate_list_tail
= IDX_PUT
;
1069 if (lh
->iterate_list_head
== IDX_NIL
)
1070 lh
->iterate_list_head
= IDX_PUT
;
1073 assert_se(hashmap_put_robin_hood(h
, idx
, swap
) == false);
1076 #ifdef ENABLE_DEBUG_HASHMAP
1077 h
->debug
.max_entries
= MAX(h
->debug
.max_entries
, n_entries(h
));
1082 #define hashmap_put_boldly(h, idx, swap, may_resize) \
1083 hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
1086 * Returns 0 if resize is not needed.
1087 * 1 if successfully resized.
1088 * -ENOMEM on allocation failure.
1090 static int resize_buckets(HashmapBase
*h
, unsigned entries_add
) {
1091 struct swap_entries swap
;
1093 dib_raw_t
*old_dibs
, *new_dibs
;
1094 const struct hashmap_type_info
*hi
;
1095 unsigned idx
, optimal_idx
;
1096 unsigned old_n_buckets
, new_n_buckets
, n_rehashed
, new_n_entries
;
1102 hi
= &hashmap_type_info
[h
->type
];
1103 new_n_entries
= n_entries(h
) + entries_add
;
1106 if (_unlikely_(new_n_entries
< entries_add
))
1109 /* For direct storage we allow 100% load, because it's tiny. */
1110 if (!h
->has_indirect
&& new_n_entries
<= hi
->n_direct_buckets
)
1114 * Load factor = n/m = 1 - (1/INV_KEEP_FREE).
1115 * From it follows: m = n + n/(INV_KEEP_FREE - 1)
1117 new_n_buckets
= new_n_entries
+ new_n_entries
/ (INV_KEEP_FREE
- 1);
1119 if (_unlikely_(new_n_buckets
< new_n_entries
))
1122 if (_unlikely_(new_n_buckets
> UINT_MAX
/ (hi
->entry_size
+ sizeof(dib_raw_t
))))
1125 old_n_buckets
= n_buckets(h
);
1127 if (_likely_(new_n_buckets
<= old_n_buckets
))
1130 new_shift
= log2u_round_up(MAX(
1131 new_n_buckets
* (hi
->entry_size
+ sizeof(dib_raw_t
)),
1132 2 * sizeof(struct direct_storage
)));
1134 /* Realloc storage (buckets and DIB array). */
1135 new_storage
= realloc(h
->has_indirect
? h
->indirect
.storage
: NULL
,
1140 /* Must upgrade direct to indirect storage. */
1141 if (!h
->has_indirect
) {
1142 memcpy(new_storage
, h
->direct
.storage
,
1143 old_n_buckets
* (hi
->entry_size
+ sizeof(dib_raw_t
)));
1144 h
->indirect
.n_entries
= h
->n_direct_entries
;
1145 h
->indirect
.idx_lowest_entry
= 0;
1146 h
->n_direct_entries
= 0;
1149 /* Get a new hash key. If we've just upgraded to indirect storage,
1150 * allow reusing a previously generated key. It's still a different key
1151 * from the shared one that we used for direct storage. */
1152 get_hash_key(h
->indirect
.hash_key
, !h
->has_indirect
);
1154 h
->has_indirect
= true;
1155 h
->indirect
.storage
= new_storage
;
1156 h
->indirect
.n_buckets
= (1U << new_shift
) /
1157 (hi
->entry_size
+ sizeof(dib_raw_t
));
1159 old_dibs
= (dib_raw_t
*)(new_storage
+ hi
->entry_size
* old_n_buckets
);
1160 new_dibs
= dib_raw_ptr(h
);
1163 * Move the DIB array to the new place, replacing valid DIB values with
1164 * DIB_RAW_REHASH to indicate all of the used buckets need rehashing.
1165 * Note: Overlap is not possible, because we have at least doubled the
1166 * number of buckets and dib_raw_t is smaller than any entry type.
1168 for (idx
= 0; idx
< old_n_buckets
; idx
++) {
1169 assert(old_dibs
[idx
] != DIB_RAW_REHASH
);
1170 new_dibs
[idx
] = old_dibs
[idx
] == DIB_RAW_FREE
? DIB_RAW_FREE
1174 /* Zero the area of newly added entries (including the old DIB area) */
1175 memzero(bucket_at(h
, old_n_buckets
),
1176 (n_buckets(h
) - old_n_buckets
) * hi
->entry_size
);
1178 /* The upper half of the new DIB array needs initialization */
1179 memset(&new_dibs
[old_n_buckets
], DIB_RAW_INIT
,
1180 (n_buckets(h
) - old_n_buckets
) * sizeof(dib_raw_t
));
1182 /* Rehash entries that need it */
1184 for (idx
= 0; idx
< old_n_buckets
; idx
++) {
1185 if (new_dibs
[idx
] != DIB_RAW_REHASH
)
1188 optimal_idx
= bucket_hash(h
, bucket_at(h
, idx
)->key
);
1191 * Not much to do if by luck the entry hashes to its current
1192 * location. Just set its DIB.
1194 if (optimal_idx
== idx
) {
1200 new_dibs
[idx
] = DIB_RAW_FREE
;
1201 bucket_move_entry(h
, &swap
, idx
, IDX_PUT
);
1202 /* bucket_move_entry does not clear the source */
1203 memzero(bucket_at(h
, idx
), hi
->entry_size
);
1207 * Find the new bucket for the current entry. This may make
1208 * another entry homeless and load it into IDX_PUT.
1210 rehash_next
= hashmap_put_robin_hood(h
, optimal_idx
, &swap
);
1213 /* Did the current entry displace another one? */
1215 optimal_idx
= bucket_hash(h
, bucket_at_swap(&swap
, IDX_PUT
)->p
.b
.key
);
1216 } while (rehash_next
);
1219 assert(n_rehashed
== n_entries(h
));
1225 * Finds an entry with a matching key
1226 * Returns: index of the found entry, or IDX_NIL if not found.
1228 static unsigned base_bucket_scan(HashmapBase
*h
, unsigned idx
, const void *key
) {
1229 struct hashmap_base_entry
*e
;
1230 unsigned dib
, distance
;
1231 dib_raw_t
*dibs
= dib_raw_ptr(h
);
1233 assert(idx
< n_buckets(h
));
1235 for (distance
= 0; ; distance
++) {
1236 if (dibs
[idx
] == DIB_RAW_FREE
)
1239 dib
= bucket_calculate_dib(h
, idx
, dibs
[idx
]);
1243 if (dib
== distance
) {
1244 e
= bucket_at(h
, idx
);
1245 if (h
->hash_ops
->compare(e
->key
, key
) == 0)
1249 idx
= next_idx(h
, idx
);
1252 #define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
1254 int hashmap_put(Hashmap
*h
, const void *key
, void *value
) {
1255 struct swap_entries swap
;
1256 struct plain_hashmap_entry
*e
;
1261 hash
= bucket_hash(h
, key
);
1262 idx
= bucket_scan(h
, hash
, key
);
1263 if (idx
!= IDX_NIL
) {
1264 e
= plain_bucket_at(h
, idx
);
1265 if (e
->value
== value
)
1270 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1273 return hashmap_put_boldly(h
, hash
, &swap
, true);
1276 int set_put(Set
*s
, const void *key
) {
1277 struct swap_entries swap
;
1278 struct hashmap_base_entry
*e
;
1283 hash
= bucket_hash(s
, key
);
1284 idx
= bucket_scan(s
, hash
, key
);
1288 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1290 return hashmap_put_boldly(s
, hash
, &swap
, true);
1293 int hashmap_replace(Hashmap
*h
, const void *key
, void *value
) {
1294 struct swap_entries swap
;
1295 struct plain_hashmap_entry
*e
;
1300 hash
= bucket_hash(h
, key
);
1301 idx
= bucket_scan(h
, hash
, key
);
1302 if (idx
!= IDX_NIL
) {
1303 e
= plain_bucket_at(h
, idx
);
1304 #ifdef ENABLE_DEBUG_HASHMAP
1305 /* Although the key is equal, the key pointer may have changed,
1306 * and this would break our assumption for iterating. So count
1307 * this operation as incompatible with iteration. */
1308 if (e
->b
.key
!= key
) {
1309 h
->b
.debug
.put_count
++;
1310 h
->b
.debug
.rem_count
++;
1311 h
->b
.debug
.last_rem_idx
= idx
;
1319 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1322 return hashmap_put_boldly(h
, hash
, &swap
, true);
1325 int hashmap_update(Hashmap
*h
, const void *key
, void *value
) {
1326 struct plain_hashmap_entry
*e
;
1331 hash
= bucket_hash(h
, key
);
1332 idx
= bucket_scan(h
, hash
, key
);
1336 e
= plain_bucket_at(h
, idx
);
1341 void *internal_hashmap_get(HashmapBase
*h
, const void *key
) {
1342 struct hashmap_base_entry
*e
;
1348 hash
= bucket_hash(h
, key
);
1349 idx
= bucket_scan(h
, hash
, key
);
1353 e
= bucket_at(h
, idx
);
1354 return entry_value(h
, e
);
1357 void *hashmap_get2(Hashmap
*h
, const void *key
, void **key2
) {
1358 struct plain_hashmap_entry
*e
;
1364 hash
= bucket_hash(h
, key
);
1365 idx
= bucket_scan(h
, hash
, key
);
1369 e
= plain_bucket_at(h
, idx
);
1371 *key2
= (void*) e
->b
.key
;
1376 bool internal_hashmap_contains(HashmapBase
*h
, const void *key
) {
1382 hash
= bucket_hash(h
, key
);
1383 return bucket_scan(h
, hash
, key
) != IDX_NIL
;
1386 void *internal_hashmap_remove(HashmapBase
*h
, const void *key
) {
1387 struct hashmap_base_entry
*e
;
1394 hash
= bucket_hash(h
, key
);
1395 idx
= bucket_scan(h
, hash
, key
);
1399 e
= bucket_at(h
, idx
);
1400 data
= entry_value(h
, e
);
1401 remove_entry(h
, idx
);
1406 void *hashmap_remove2(Hashmap
*h
, const void *key
, void **rkey
) {
1407 struct plain_hashmap_entry
*e
;
1417 hash
= bucket_hash(h
, key
);
1418 idx
= bucket_scan(h
, hash
, key
);
1419 if (idx
== IDX_NIL
) {
1425 e
= plain_bucket_at(h
, idx
);
1428 *rkey
= (void*) e
->b
.key
;
1430 remove_entry(h
, idx
);
1435 int hashmap_remove_and_put(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
1436 struct swap_entries swap
;
1437 struct plain_hashmap_entry
*e
;
1438 unsigned old_hash
, new_hash
, idx
;
1443 old_hash
= bucket_hash(h
, old_key
);
1444 idx
= bucket_scan(h
, old_hash
, old_key
);
1448 new_hash
= bucket_hash(h
, new_key
);
1449 if (bucket_scan(h
, new_hash
, new_key
) != IDX_NIL
)
1452 remove_entry(h
, idx
);
1454 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1457 assert_se(hashmap_put_boldly(h
, new_hash
, &swap
, false) == 1);
1462 int set_remove_and_put(Set
*s
, const void *old_key
, const void *new_key
) {
1463 struct swap_entries swap
;
1464 struct hashmap_base_entry
*e
;
1465 unsigned old_hash
, new_hash
, idx
;
1470 old_hash
= bucket_hash(s
, old_key
);
1471 idx
= bucket_scan(s
, old_hash
, old_key
);
1475 new_hash
= bucket_hash(s
, new_key
);
1476 if (bucket_scan(s
, new_hash
, new_key
) != IDX_NIL
)
1479 remove_entry(s
, idx
);
1481 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1483 assert_se(hashmap_put_boldly(s
, new_hash
, &swap
, false) == 1);
1488 int hashmap_remove_and_replace(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
1489 struct swap_entries swap
;
1490 struct plain_hashmap_entry
*e
;
1491 unsigned old_hash
, new_hash
, idx_old
, idx_new
;
1496 old_hash
= bucket_hash(h
, old_key
);
1497 idx_old
= bucket_scan(h
, old_hash
, old_key
);
1498 if (idx_old
== IDX_NIL
)
1501 old_key
= bucket_at(HASHMAP_BASE(h
), idx_old
)->key
;
1503 new_hash
= bucket_hash(h
, new_key
);
1504 idx_new
= bucket_scan(h
, new_hash
, new_key
);
1505 if (idx_new
!= IDX_NIL
)
1506 if (idx_old
!= idx_new
) {
1507 remove_entry(h
, idx_new
);
1508 /* Compensate for a possible backward shift. */
1509 if (old_key
!= bucket_at(HASHMAP_BASE(h
), idx_old
)->key
)
1510 idx_old
= prev_idx(HASHMAP_BASE(h
), idx_old
);
1511 assert(old_key
== bucket_at(HASHMAP_BASE(h
), idx_old
)->key
);
1514 remove_entry(h
, idx_old
);
1516 e
= &bucket_at_swap(&swap
, IDX_PUT
)->p
;
1519 assert_se(hashmap_put_boldly(h
, new_hash
, &swap
, false) == 1);
1524 void *hashmap_remove_value(Hashmap
*h
, const void *key
, void *value
) {
1525 struct plain_hashmap_entry
*e
;
1531 hash
= bucket_hash(h
, key
);
1532 idx
= bucket_scan(h
, hash
, key
);
1536 e
= plain_bucket_at(h
, idx
);
1537 if (e
->value
!= value
)
1540 remove_entry(h
, idx
);
1545 static unsigned find_first_entry(HashmapBase
*h
) {
1546 Iterator i
= ITERATOR_FIRST
;
1548 if (!h
|| !n_entries(h
))
1551 return hashmap_iterate_entry(h
, &i
);
1554 void *internal_hashmap_first(HashmapBase
*h
) {
1557 idx
= find_first_entry(h
);
1561 return entry_value(h
, bucket_at(h
, idx
));
1564 void *internal_hashmap_first_key(HashmapBase
*h
) {
1565 struct hashmap_base_entry
*e
;
1568 idx
= find_first_entry(h
);
1572 e
= bucket_at(h
, idx
);
1573 return (void*) e
->key
;
1576 void *internal_hashmap_steal_first(HashmapBase
*h
) {
1577 struct hashmap_base_entry
*e
;
1581 idx
= find_first_entry(h
);
1585 e
= bucket_at(h
, idx
);
1586 data
= entry_value(h
, e
);
1587 remove_entry(h
, idx
);
1592 void *internal_hashmap_steal_first_key(HashmapBase
*h
) {
1593 struct hashmap_base_entry
*e
;
1597 idx
= find_first_entry(h
);
1601 e
= bucket_at(h
, idx
);
1602 key
= (void*) e
->key
;
1603 remove_entry(h
, idx
);
1608 unsigned internal_hashmap_size(HashmapBase
*h
) {
1613 return n_entries(h
);
1616 unsigned internal_hashmap_buckets(HashmapBase
*h
) {
1621 return n_buckets(h
);
1624 int internal_hashmap_merge(Hashmap
*h
, Hashmap
*other
) {
1630 HASHMAP_FOREACH_IDX(idx
, HASHMAP_BASE(other
), i
) {
1631 struct plain_hashmap_entry
*pe
= plain_bucket_at(other
, idx
);
1634 r
= hashmap_put(h
, pe
->b
.key
, pe
->value
);
1635 if (r
< 0 && r
!= -EEXIST
)
1642 int set_merge(Set
*s
, Set
*other
) {
1648 HASHMAP_FOREACH_IDX(idx
, HASHMAP_BASE(other
), i
) {
1649 struct set_entry
*se
= set_bucket_at(other
, idx
);
1652 r
= set_put(s
, se
->b
.key
);
1660 int internal_hashmap_reserve(HashmapBase
*h
, unsigned entries_add
) {
1665 r
= resize_buckets(h
, entries_add
);
1673 * The same as hashmap_merge(), but every new item from other is moved to h.
1674 * Keys already in h are skipped and stay in other.
1675 * Returns: 0 on success.
1676 * -ENOMEM on alloc failure, in which case no move has been done.
1678 int internal_hashmap_move(HashmapBase
*h
, HashmapBase
*other
) {
1679 struct swap_entries swap
;
1680 struct hashmap_base_entry
*e
, *n
;
1690 assert(other
->type
== h
->type
);
1693 * This reserves buckets for the worst case, where none of other's
1694 * entries are yet present in h. This is preferable to risking
1695 * an allocation failure in the middle of the moving and having to
1696 * rollback or return a partial result.
1698 r
= resize_buckets(h
, n_entries(other
));
1702 HASHMAP_FOREACH_IDX(idx
, other
, i
) {
1705 e
= bucket_at(other
, idx
);
1706 h_hash
= bucket_hash(h
, e
->key
);
1707 if (bucket_scan(h
, h_hash
, e
->key
) != IDX_NIL
)
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 assert_se(hashmap_put_boldly(h
, h_hash
, &swap
, false) == 1);
1717 remove_entry(other
, idx
);
1723 int internal_hashmap_move_one(HashmapBase
*h
, HashmapBase
*other
, const void *key
) {
1724 struct swap_entries swap
;
1725 unsigned h_hash
, other_hash
, idx
;
1726 struct hashmap_base_entry
*e
, *n
;
1731 h_hash
= bucket_hash(h
, key
);
1732 if (bucket_scan(h
, h_hash
, key
) != IDX_NIL
)
1738 assert(other
->type
== h
->type
);
1740 other_hash
= bucket_hash(other
, key
);
1741 idx
= bucket_scan(other
, other_hash
, key
);
1745 e
= bucket_at(other
, idx
);
1747 n
= &bucket_at_swap(&swap
, IDX_PUT
)->p
.b
;
1749 if (h
->type
!= HASHMAP_TYPE_SET
)
1750 ((struct plain_hashmap_entry
*) n
)->value
=
1751 ((struct plain_hashmap_entry
*) e
)->value
;
1752 r
= hashmap_put_boldly(h
, h_hash
, &swap
, true);
1756 remove_entry(other
, idx
);
1760 HashmapBase
*internal_hashmap_copy(HashmapBase
*h
) {
1766 copy
= hashmap_base_new(h
->hash_ops
, h
->type HASHMAP_DEBUG_SRC_ARGS
);
1771 case HASHMAP_TYPE_PLAIN
:
1772 case HASHMAP_TYPE_ORDERED
:
1773 r
= hashmap_merge((Hashmap
*)copy
, (Hashmap
*)h
);
1775 case HASHMAP_TYPE_SET
:
1776 r
= set_merge((Set
*)copy
, (Set
*)h
);
1779 assert_not_reached("Unknown hashmap type");
1783 internal_hashmap_free(copy
);
1790 char **internal_hashmap_get_strv(HashmapBase
*h
) {
1795 sv
= new(char*, n_entries(h
)+1);
1800 HASHMAP_FOREACH_IDX(idx
, h
, i
)
1801 sv
[n
++] = entry_value(h
, bucket_at(h
, idx
));
1807 void *ordered_hashmap_next(OrderedHashmap
*h
, const void *key
) {
1808 struct ordered_hashmap_entry
*e
;
1814 hash
= bucket_hash(h
, key
);
1815 idx
= bucket_scan(h
, hash
, key
);
1819 e
= ordered_bucket_at(h
, idx
);
1820 if (e
->iterate_next
== IDX_NIL
)
1822 return ordered_bucket_at(h
, e
->iterate_next
)->p
.value
;
1825 int set_consume(Set
*s
, void *value
) {
1828 r
= set_put(s
, value
);
1835 int set_put_strdup(Set
*s
, const char *p
) {
1846 r
= set_consume(s
, c
);
1853 int set_put_strdupv(Set
*s
, char **l
) {
1857 STRV_FOREACH(i
, l
) {
1858 r
= set_put_strdup(s
, *i
);