Branch data Line data Source code
1 : : /* SPDX-License-Identifier: LGPL-2.1+ */
2 : :
3 : : #include <errno.h>
4 : : #include <stdint.h>
5 : : #include <stdlib.h>
6 : : #include <string.h>
7 : :
8 : : #include "alloc-util.h"
9 : : #include "fileio.h"
10 : : #include "hashmap.h"
11 : : #include "macro.h"
12 : : #include "memory-util.h"
13 : : #include "mempool.h"
14 : : #include "missing.h"
15 : : #include "process-util.h"
16 : : #include "random-util.h"
17 : : #include "set.h"
18 : : #include "siphash24.h"
19 : : #include "string-util.h"
20 : : #include "strv.h"
21 : :
22 : : #if ENABLE_DEBUG_HASHMAP
23 : : #include <pthread.h>
24 : : #include "list.h"
25 : : #endif
26 : :
27 : : /*
28 : : * Implementation of hashmaps.
29 : : * Addressing: open
30 : : * - uses less RAM compared to closed addressing (chaining), because
31 : : * our entries are small (especially in Sets, which tend to contain
32 : : * the majority of entries in systemd).
33 : : * Collision resolution: Robin Hood
34 : : * - tends to equalize displacement of entries from their optimal buckets.
35 : : * Probe sequence: linear
36 : : * - though theoretically worse than random probing/uniform hashing/double
37 : : * hashing, it is good for cache locality.
38 : : *
39 : : * References:
40 : : * Celis, P. 1986. Robin Hood Hashing.
41 : : * Ph.D. Dissertation. University of Waterloo, Waterloo, Ont., Canada, Canada.
42 : : * https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
43 : : * - The results are derived for random probing. Suggests deletion with
44 : : * tombstones and two mean-centered search methods. None of that works
45 : : * well for linear probing.
46 : : *
47 : : * Janson, S. 2005. Individual displacements for linear probing hashing with different insertion policies.
48 : : * ACM Trans. Algorithms 1, 2 (October 2005), 177-213.
49 : : * DOI=10.1145/1103963.1103964 http://doi.acm.org/10.1145/1103963.1103964
50 : : * http://www.math.uu.se/~svante/papers/sj157.pdf
51 : : * - Applies to Robin Hood with linear probing. Contains remarks on
52 : : * the unsuitability of mean-centered search with linear probing.
53 : : *
54 : : * Viola, A. 2005. Exact distribution of individual displacements in linear probing hashing.
55 : : * ACM Trans. Algorithms 1, 2 (October 2005), 214-242.
56 : : * DOI=10.1145/1103963.1103965 http://doi.acm.org/10.1145/1103963.1103965
57 : : * - Similar to Janson. Note that Viola writes about C_{m,n} (number of probes
58 : : * in a successful search), and Janson writes about displacement. C = d + 1.
59 : : *
60 : : * Goossaert, E. 2013. Robin Hood hashing: backward shift deletion.
61 : : * http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
62 : : * - Explanation of backward shift deletion with pictures.
63 : : *
64 : : * Khuong, P. 2013. The Other Robin Hood Hashing.
65 : : * http://www.pvk.ca/Blog/2013/11/26/the-other-robin-hood-hashing/
66 : : * - Short summary of random vs. linear probing, and tombstones vs. backward shift.
67 : : */
68 : :
69 : : /*
70 : : * XXX Ideas for improvement:
71 : : * For unordered hashmaps, randomize iteration order, similarly to Perl:
72 : : * http://blog.booking.com/hardening-perls-hash-function.html
73 : : */
74 : :
75 : : /* INV_KEEP_FREE = 1 / (1 - max_load_factor)
76 : : * e.g. 1 / (1 - 0.8) = 5 ... keep one fifth of the buckets free. */
77 : : #define INV_KEEP_FREE 5U
78 : :
79 : : /* Fields common to entries of all hashmap/set types */
80 : : struct hashmap_base_entry {
81 : : const void *key;
82 : : };
83 : :
84 : : /* Entry types for specific hashmap/set types
85 : : * hashmap_base_entry must be at the beginning of each entry struct. */
86 : :
87 : : struct plain_hashmap_entry {
88 : : struct hashmap_base_entry b;
89 : : void *value;
90 : : };
91 : :
92 : : struct ordered_hashmap_entry {
93 : : struct plain_hashmap_entry p;
94 : : unsigned iterate_next, iterate_previous;
95 : : };
96 : :
97 : : struct set_entry {
98 : : struct hashmap_base_entry b;
99 : : };
100 : :
101 : : /* In several functions it is advantageous to have the hash table extended
102 : : * virtually by a couple of additional buckets. We reserve special index values
103 : : * for these "swap" buckets. */
104 : : #define _IDX_SWAP_BEGIN (UINT_MAX - 3)
105 : : #define IDX_PUT (_IDX_SWAP_BEGIN + 0)
106 : : #define IDX_TMP (_IDX_SWAP_BEGIN + 1)
107 : : #define _IDX_SWAP_END (_IDX_SWAP_BEGIN + 2)
108 : :
109 : : #define IDX_FIRST (UINT_MAX - 1) /* special index for freshly initialized iterators */
110 : : #define IDX_NIL UINT_MAX /* special index value meaning "none" or "end" */
111 : :
112 : : assert_cc(IDX_FIRST == _IDX_SWAP_END);
113 : : assert_cc(IDX_FIRST == _IDX_ITERATOR_FIRST);
114 : :
115 : : /* Storage space for the "swap" buckets.
116 : : * All entry types can fit into a ordered_hashmap_entry. */
117 : : struct swap_entries {
118 : : struct ordered_hashmap_entry e[_IDX_SWAP_END - _IDX_SWAP_BEGIN];
119 : : };
120 : :
121 : : /* Distance from Initial Bucket */
122 : : typedef uint8_t dib_raw_t;
123 : : #define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */
124 : : #define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */
125 : : #define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */
126 : : #define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */
127 : :
128 : : #define DIB_FREE UINT_MAX
129 : :
130 : : #if ENABLE_DEBUG_HASHMAP
131 : : struct hashmap_debug_info {
132 : : LIST_FIELDS(struct hashmap_debug_info, debug_list);
133 : : unsigned max_entries; /* high watermark of n_entries */
134 : :
135 : : /* who allocated this hashmap */
136 : : int line;
137 : : const char *file;
138 : : const char *func;
139 : :
140 : : /* fields to detect modification while iterating */
141 : : unsigned put_count; /* counts puts into the hashmap */
142 : : unsigned rem_count; /* counts removals from hashmap */
143 : : unsigned last_rem_idx; /* remembers last removal index */
144 : : };
145 : :
146 : : /* Tracks all existing hashmaps. Get at it from gdb. See sd_dump_hashmaps.py */
147 : : static LIST_HEAD(struct hashmap_debug_info, hashmap_debug_list);
148 : : static pthread_mutex_t hashmap_debug_list_mutex = PTHREAD_MUTEX_INITIALIZER;
149 : :
150 : : #define HASHMAP_DEBUG_FIELDS struct hashmap_debug_info debug;
151 : :
152 : : #else /* !ENABLE_DEBUG_HASHMAP */
153 : : #define HASHMAP_DEBUG_FIELDS
154 : : #endif /* ENABLE_DEBUG_HASHMAP */
155 : :
156 : : enum HashmapType {
157 : : HASHMAP_TYPE_PLAIN,
158 : : HASHMAP_TYPE_ORDERED,
159 : : HASHMAP_TYPE_SET,
160 : : _HASHMAP_TYPE_MAX
161 : : };
162 : :
163 : : struct _packed_ indirect_storage {
164 : : void *storage; /* where buckets and DIBs are stored */
165 : : uint8_t hash_key[HASH_KEY_SIZE]; /* hash key; changes during resize */
166 : :
167 : : unsigned n_entries; /* number of stored entries */
168 : : unsigned n_buckets; /* number of buckets */
169 : :
170 : : unsigned idx_lowest_entry; /* Index below which all buckets are free.
171 : : Makes "while(hashmap_steal_first())" loops
172 : : O(n) instead of O(n^2) for unordered hashmaps. */
173 : : uint8_t _pad[3]; /* padding for the whole HashmapBase */
174 : : /* The bitfields in HashmapBase complete the alignment of the whole thing. */
175 : : };
176 : :
177 : : struct direct_storage {
178 : : /* This gives us 39 bytes on 64bit, or 35 bytes on 32bit.
179 : : * That's room for 4 set_entries + 4 DIB bytes + 3 unused bytes on 64bit,
180 : : * or 7 set_entries + 7 DIB bytes + 0 unused bytes on 32bit. */
181 : : uint8_t storage[sizeof(struct indirect_storage)];
182 : : };
183 : :
184 : : #define DIRECT_BUCKETS(entry_t) \
185 : : (sizeof(struct direct_storage) / (sizeof(entry_t) + sizeof(dib_raw_t)))
186 : :
187 : : /* We should be able to store at least one entry directly. */
188 : : assert_cc(DIRECT_BUCKETS(struct ordered_hashmap_entry) >= 1);
189 : :
190 : : /* We have 3 bits for n_direct_entries. */
191 : : assert_cc(DIRECT_BUCKETS(struct set_entry) < (1 << 3));
192 : :
193 : : /* Hashmaps with directly stored entries all use this shared hash key.
194 : : * It's no big deal if the key is guessed, because there can be only
195 : : * a handful of directly stored entries in a hashmap. When a hashmap
196 : : * outgrows direct storage, it gets its own key for indirect storage. */
197 : : static uint8_t shared_hash_key[HASH_KEY_SIZE];
198 : : static bool shared_hash_key_initialized;
199 : :
200 : : /* Fields that all hashmap/set types must have */
201 : : struct HashmapBase {
202 : : const struct hash_ops *hash_ops; /* hash and compare ops to use */
203 : :
204 : : union _packed_ {
205 : : struct indirect_storage indirect; /* if has_indirect */
206 : : struct direct_storage direct; /* if !has_indirect */
207 : : };
208 : :
209 : : enum HashmapType type:2; /* HASHMAP_TYPE_* */
210 : : bool has_indirect:1; /* whether indirect storage is used */
211 : : unsigned n_direct_entries:3; /* Number of entries in direct storage.
212 : : * Only valid if !has_indirect. */
213 : : bool from_pool:1; /* whether was allocated from mempool */
214 : : bool dirty:1; /* whether dirtied since last iterated_cache_get() */
215 : : bool cached:1; /* whether this hashmap is being cached */
216 : : HASHMAP_DEBUG_FIELDS /* optional hashmap_debug_info */
217 : : };
218 : :
219 : : /* Specific hash types
220 : : * HashmapBase must be at the beginning of each hashmap struct. */
221 : :
222 : : struct Hashmap {
223 : : struct HashmapBase b;
224 : : };
225 : :
226 : : struct OrderedHashmap {
227 : : struct HashmapBase b;
228 : : unsigned iterate_list_head, iterate_list_tail;
229 : : };
230 : :
231 : : struct Set {
232 : : struct HashmapBase b;
233 : : };
234 : :
235 : : typedef struct CacheMem {
236 : : const void **ptr;
237 : : size_t n_populated, n_allocated;
238 : : bool active:1;
239 : : } CacheMem;
240 : :
241 : : struct IteratedCache {
242 : : HashmapBase *hashmap;
243 : : CacheMem keys, values;
244 : : };
245 : :
246 : : DEFINE_MEMPOOL(hashmap_pool, Hashmap, 8);
247 : : DEFINE_MEMPOOL(ordered_hashmap_pool, OrderedHashmap, 8);
248 : : /* No need for a separate Set pool */
249 : : assert_cc(sizeof(Hashmap) == sizeof(Set));
250 : :
251 : : struct hashmap_type_info {
252 : : size_t head_size;
253 : : size_t entry_size;
254 : : struct mempool *mempool;
255 : : unsigned n_direct_buckets;
256 : : };
257 : :
258 : : static const struct hashmap_type_info hashmap_type_info[_HASHMAP_TYPE_MAX] = {
259 : : [HASHMAP_TYPE_PLAIN] = {
260 : : .head_size = sizeof(Hashmap),
261 : : .entry_size = sizeof(struct plain_hashmap_entry),
262 : : .mempool = &hashmap_pool,
263 : : .n_direct_buckets = DIRECT_BUCKETS(struct plain_hashmap_entry),
264 : : },
265 : : [HASHMAP_TYPE_ORDERED] = {
266 : : .head_size = sizeof(OrderedHashmap),
267 : : .entry_size = sizeof(struct ordered_hashmap_entry),
268 : : .mempool = &ordered_hashmap_pool,
269 : : .n_direct_buckets = DIRECT_BUCKETS(struct ordered_hashmap_entry),
270 : : },
271 : : [HASHMAP_TYPE_SET] = {
272 : : .head_size = sizeof(Set),
273 : : .entry_size = sizeof(struct set_entry),
274 : : .mempool = &hashmap_pool,
275 : : .n_direct_buckets = DIRECT_BUCKETS(struct set_entry),
276 : : },
277 : : };
278 : :
279 : : #if VALGRIND
280 : : _destructor_ static void cleanup_pools(void) {
281 : : _cleanup_free_ char *t = NULL;
282 : : int r;
283 : :
284 : : /* Be nice to valgrind */
285 : :
286 : : /* The pool is only allocated by the main thread, but the memory can
287 : : * be passed to other threads. Let's clean up if we are the main thread
288 : : * and no other threads are live. */
289 : : /* We build our own is_main_thread() here, which doesn't use C11
290 : : * TLS based caching of the result. That's because valgrind apparently
291 : : * doesn't like malloc() (which C11 TLS internally uses) to be called
292 : : * from a GCC destructors. */
293 : : if (getpid() != gettid())
294 : : return;
295 : :
296 : : r = get_proc_field("/proc/self/status", "Threads", WHITESPACE, &t);
297 : : if (r < 0 || !streq(t, "1"))
298 : : return;
299 : :
300 : : mempool_drop(&hashmap_pool);
301 : : mempool_drop(&ordered_hashmap_pool);
302 : : }
303 : : #endif
304 : :
305 : 819005486 : static unsigned n_buckets(HashmapBase *h) {
306 : 819005486 : return h->has_indirect ? h->indirect.n_buckets
307 [ + + ]: 819005486 : : hashmap_type_info[h->type].n_direct_buckets;
308 : : }
309 : :
310 : 77703441 : static unsigned n_entries(HashmapBase *h) {
311 : 77703441 : return h->has_indirect ? h->indirect.n_entries
312 [ + + ]: 77703441 : : h->n_direct_entries;
313 : : }
314 : :
315 : 19423003 : static void n_entries_inc(HashmapBase *h) {
316 [ + + ]: 19423003 : if (h->has_indirect)
317 : 19318808 : h->indirect.n_entries++;
318 : : else
319 : 104195 : h->n_direct_entries++;
320 : 19423003 : }
321 : :
322 : 19369892 : static void n_entries_dec(HashmapBase *h) {
323 [ + + ]: 19369892 : if (h->has_indirect)
324 : 19322177 : h->indirect.n_entries--;
325 : : else
326 : 47715 : h->n_direct_entries--;
327 : 19369892 : }
328 : :
329 : 890998706 : static void *storage_ptr(HashmapBase *h) {
330 : 890998706 : return h->has_indirect ? h->indirect.storage
331 [ + + ]: 890998706 : : h->direct.storage;
332 : : }
333 : :
334 : 94724025 : static uint8_t *hash_key(HashmapBase *h) {
335 : 94724025 : return h->has_indirect ? h->indirect.hash_key
336 [ + + ]: 94724025 : : shared_hash_key;
337 : : }
338 : :
339 : 94724025 : static unsigned base_bucket_hash(HashmapBase *h, const void *p) {
340 : : struct siphash state;
341 : : uint64_t hash;
342 : :
343 : 94724025 : siphash24_init(&state, hash_key(h));
344 : :
345 : 94724025 : h->hash_ops->hash(p, &state);
346 : :
347 : 94724025 : hash = siphash24_finalize(&state);
348 : :
349 : 94724025 : return (unsigned) (hash % n_buckets(h));
350 : : }
351 : : #define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p)
352 : :
353 : 38934660 : static void base_set_dirty(HashmapBase *h) {
354 : 38934660 : h->dirty = true;
355 : 38934660 : }
356 : : #define hashmap_set_dirty(h) base_set_dirty(HASHMAP_BASE(h))
357 : :
358 : 71465 : static void get_hash_key(uint8_t hash_key[HASH_KEY_SIZE], bool reuse_is_ok) {
359 : : static uint8_t current[HASH_KEY_SIZE];
360 : : static bool current_initialized = false;
361 : :
362 : : /* Returns a hash function key to use. In order to keep things
363 : : * fast we will not generate a new key each time we allocate a
364 : : * new hash table. Instead, we'll just reuse the most recently
365 : : * generated one, except if we never generated one or when we
366 : : * are rehashing an entire hash table because we reached a
367 : : * fill level */
368 : :
369 [ + + + + ]: 71465 : if (!current_initialized || !reuse_is_ok) {
370 : 30142 : random_bytes(current, sizeof(current));
371 : 30142 : current_initialized = true;
372 : : }
373 : :
374 : 71465 : memcpy(hash_key, current, sizeof(current));
375 : 71465 : }
376 : :
377 : 628913547 : static struct hashmap_base_entry *bucket_at(HashmapBase *h, unsigned idx) {
378 : 1257827094 : return (struct hashmap_base_entry*)
379 : 628913547 : ((uint8_t*) storage_ptr(h) + idx * hashmap_type_info[h->type].entry_size);
380 : : }
381 : :
382 : 11120 : static struct plain_hashmap_entry *plain_bucket_at(Hashmap *h, unsigned idx) {
383 : 11120 : return (struct plain_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
384 : : }
385 : :
386 : 48741704 : static struct ordered_hashmap_entry *ordered_bucket_at(OrderedHashmap *h, unsigned idx) {
387 : 48741704 : return (struct ordered_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
388 : : }
389 : :
390 : 0 : static struct set_entry *set_bucket_at(Set *h, unsigned idx) {
391 : 0 : return (struct set_entry*) bucket_at(HASHMAP_BASE(h), idx);
392 : : }
393 : :
394 : 254203074 : static struct ordered_hashmap_entry *bucket_at_swap(struct swap_entries *swap, unsigned idx) {
395 : 254203074 : return &swap->e[idx - _IDX_SWAP_BEGIN];
396 : : }
397 : :
398 : : /* Returns a pointer to the bucket at index idx.
399 : : * Understands real indexes and swap indexes, hence "_virtual". */
400 : 595743886 : static struct hashmap_base_entry *bucket_at_virtual(HashmapBase *h, struct swap_entries *swap,
401 : : unsigned idx) {
402 [ + + ]: 595743886 : if (idx < _IDX_SWAP_BEGIN)
403 : 386076929 : return bucket_at(h, idx);
404 : :
405 [ + - ]: 209666957 : if (idx < _IDX_SWAP_END)
406 : 209666957 : return &bucket_at_swap(swap, idx)->p.b;
407 : :
408 : 0 : assert_not_reached("Invalid index");
409 : : }
410 : :
411 : 262085159 : static dib_raw_t *dib_raw_ptr(HashmapBase *h) {
412 : 524170318 : return (dib_raw_t*)
413 : 262085159 : ((uint8_t*) storage_ptr(h) + hashmap_type_info[h->type].entry_size * n_buckets(h));
414 : : }
415 : :
416 : 17931548 : static unsigned bucket_distance(HashmapBase *h, unsigned idx, unsigned from) {
417 : : return idx >= from ? idx - from
418 [ + + ]: 17931548 : : n_buckets(h) + idx - from;
419 : : }
420 : :
421 : 262719549 : static unsigned bucket_calculate_dib(HashmapBase *h, unsigned idx, dib_raw_t raw_dib) {
422 : : unsigned initial_bucket;
423 : :
424 [ - + ]: 262719549 : if (raw_dib == DIB_RAW_FREE)
425 : 0 : return DIB_FREE;
426 : :
427 [ + + ]: 262719549 : if (_likely_(raw_dib < DIB_RAW_OVERFLOW))
428 : 244788001 : return raw_dib;
429 : :
430 : : /*
431 : : * Having an overflow DIB value is very unlikely. The hash function
432 : : * would have to be bad. For example, in a table of size 2^24 filled
433 : : * to load factor 0.9 the maximum observed DIB is only about 60.
434 : : * In theory (assuming I used Maxima correctly), for an infinite size
435 : : * hash table with load factor 0.8 the probability of a given entry
436 : : * having DIB > 40 is 1.9e-8.
437 : : * This returns the correct DIB value by recomputing the hash value in
438 : : * the unlikely case. XXX Hitting this case could be a hint to rehash.
439 : : */
440 : 17931548 : initial_bucket = bucket_hash(h, bucket_at(h, idx)->key);
441 : 17931548 : return bucket_distance(h, idx, initial_bucket);
442 : : }
443 : :
444 : 124195567 : static void bucket_set_dib(HashmapBase *h, unsigned idx, unsigned dib) {
445 [ + + ]: 124195567 : dib_raw_ptr(h)[idx] = dib != DIB_FREE ? MIN(dib, DIB_RAW_OVERFLOW) : DIB_RAW_FREE;
446 : 124195567 : }
447 : :
448 : 22321884 : static unsigned skip_free_buckets(HashmapBase *h, unsigned idx) {
449 : : dib_raw_t *dibs;
450 : :
451 : 22321884 : dibs = dib_raw_ptr(h);
452 : :
453 [ + + ]: 53803109 : for ( ; idx < n_buckets(h); idx++)
454 [ + + ]: 53666060 : if (dibs[idx] != DIB_RAW_FREE)
455 : 22184835 : return idx;
456 : :
457 : 137049 : return IDX_NIL;
458 : : }
459 : :
460 : 19369892 : static void bucket_mark_free(HashmapBase *h, unsigned idx) {
461 [ + - ]: 19369892 : memzero(bucket_at(h, idx), hashmap_type_info[h->type].entry_size);
462 : 19369892 : bucket_set_dib(h, idx, DIB_FREE);
463 : 19369892 : }
464 : :
465 : 199924995 : static void bucket_move_entry(HashmapBase *h, struct swap_entries *swap,
466 : : unsigned from, unsigned to) {
467 : : struct hashmap_base_entry *e_from, *e_to;
468 : :
469 [ - + ]: 199924995 : assert(from != to);
470 : :
471 : 199924995 : e_from = bucket_at_virtual(h, swap, from);
472 : 199924995 : e_to = bucket_at_virtual(h, swap, to);
473 : :
474 : 199924995 : memcpy(e_to, e_from, hashmap_type_info[h->type].entry_size);
475 : :
476 [ + + ]: 199924995 : if (h->type == HASHMAP_TYPE_ORDERED) {
477 : 102991339 : OrderedHashmap *lh = (OrderedHashmap*) h;
478 : : struct ordered_hashmap_entry *le, *le_to;
479 : :
480 : 102991339 : le_to = (struct ordered_hashmap_entry*) e_to;
481 : :
482 [ + + ]: 102991339 : if (le_to->iterate_next != IDX_NIL) {
483 : : le = (struct ordered_hashmap_entry*)
484 : 93107397 : bucket_at_virtual(h, swap, le_to->iterate_next);
485 : 93107397 : le->iterate_previous = to;
486 : : }
487 : :
488 [ + + ]: 102991339 : if (le_to->iterate_previous != IDX_NIL) {
489 : : le = (struct ordered_hashmap_entry*)
490 : 102786499 : bucket_at_virtual(h, swap, le_to->iterate_previous);
491 : 102786499 : le->iterate_next = to;
492 : : }
493 : :
494 [ + + ]: 102991339 : if (lh->iterate_list_head == from)
495 : 204840 : lh->iterate_list_head = to;
496 [ + + ]: 102991339 : if (lh->iterate_list_tail == from)
497 : 9883942 : lh->iterate_list_tail = to;
498 : : }
499 : 199924995 : }
500 : :
501 : 297767119 : static unsigned next_idx(HashmapBase *h, unsigned idx) {
502 : 297767119 : return (idx + 1U) % n_buckets(h);
503 : : }
504 : :
505 : 30 : static unsigned prev_idx(HashmapBase *h, unsigned idx) {
506 : 30 : return (n_buckets(h) + idx - 1U) % n_buckets(h);
507 : : }
508 : :
509 : 35619676 : static void *entry_value(HashmapBase *h, struct hashmap_base_entry *e) {
510 [ + + - ]: 35619676 : switch (h->type) {
511 : :
512 : 35475620 : case HASHMAP_TYPE_PLAIN:
513 : : case HASHMAP_TYPE_ORDERED:
514 : 35475620 : return ((struct plain_hashmap_entry*)e)->value;
515 : :
516 : 144056 : case HASHMAP_TYPE_SET:
517 : 144056 : return (void*) e->key;
518 : :
519 : 0 : default:
520 : 0 : assert_not_reached("Unknown hashmap type");
521 : : }
522 : : }
523 : :
524 : 19369892 : static void base_remove_entry(HashmapBase *h, unsigned idx) {
525 : : unsigned left, right, prev, dib;
526 : : dib_raw_t raw_dib, *dibs;
527 : :
528 : 19369892 : dibs = dib_raw_ptr(h);
529 [ - + ]: 19369892 : assert(dibs[idx] != DIB_RAW_FREE);
530 : :
531 : : #if ENABLE_DEBUG_HASHMAP
532 : : h->debug.rem_count++;
533 : : h->debug.last_rem_idx = idx;
534 : : #endif
535 : :
536 : 19369892 : left = idx;
537 : : /* Find the stop bucket ("right"). It is either free or has DIB == 0. */
538 : 47873289 : for (right = next_idx(h, left); ; right = next_idx(h, right)) {
539 : 28503397 : raw_dib = dibs[right];
540 [ + + + + ]: 47873289 : if (IN_SET(raw_dib, 0, DIB_RAW_FREE))
541 : 19369892 : break;
542 : :
543 : : /* The buckets are not supposed to be all occupied and with DIB > 0.
544 : : * That would mean we could make everyone better off by shifting them
545 : : * backward. This scenario is impossible. */
546 [ - + ]: 28503397 : assert(left != right);
547 : : }
548 : :
549 [ + + ]: 19369892 : if (h->type == HASHMAP_TYPE_ORDERED) {
550 : 9748471 : OrderedHashmap *lh = (OrderedHashmap*) h;
551 : 9748471 : struct ordered_hashmap_entry *le = ordered_bucket_at(lh, idx);
552 : :
553 [ + + ]: 9748471 : if (le->iterate_next != IDX_NIL)
554 : 9703341 : ordered_bucket_at(lh, le->iterate_next)->iterate_previous = le->iterate_previous;
555 : : else
556 : 45130 : lh->iterate_list_tail = le->iterate_previous;
557 : :
558 [ + + ]: 9748471 : if (le->iterate_previous != IDX_NIL)
559 : 83 : ordered_bucket_at(lh, le->iterate_previous)->iterate_next = le->iterate_next;
560 : : else
561 : 9748388 : lh->iterate_list_head = le->iterate_next;
562 : : }
563 : :
564 : : /* Now shift all buckets in the interval (left, right) one step backwards */
565 [ + + ]: 47873289 : for (prev = left, left = next_idx(h, left); left != right;
566 : 28503397 : prev = left, left = next_idx(h, left)) {
567 : 28503397 : dib = bucket_calculate_dib(h, left, dibs[left]);
568 [ - + ]: 28503397 : assert(dib != 0);
569 : 28503397 : bucket_move_entry(h, NULL, left, prev);
570 : 28503397 : bucket_set_dib(h, prev, dib - 1);
571 : : }
572 : :
573 : 19369892 : bucket_mark_free(h, prev);
574 : 19369892 : n_entries_dec(h);
575 : 19369892 : base_set_dirty(h);
576 : 19369892 : }
577 : : #define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)
578 : :
579 : 9823186 : static unsigned hashmap_iterate_in_insertion_order(OrderedHashmap *h, Iterator *i) {
580 : : struct ordered_hashmap_entry *e;
581 : : unsigned idx;
582 : :
583 [ - + ]: 9823186 : assert(h);
584 [ - + ]: 9823186 : assert(i);
585 : :
586 [ + + ]: 9823186 : if (i->idx == IDX_NIL)
587 : 3954 : goto at_end;
588 : :
589 [ + + + + ]: 9819232 : if (i->idx == IDX_FIRST && h->iterate_list_head == IDX_NIL)
590 : 1827 : goto at_end;
591 : :
592 [ + + ]: 9817405 : if (i->idx == IDX_FIRST) {
593 : 9753149 : idx = h->iterate_list_head;
594 : 9753149 : e = ordered_bucket_at(h, idx);
595 : : } else {
596 : 64256 : idx = i->idx;
597 : 64256 : e = ordered_bucket_at(h, idx);
598 : : /*
599 : : * We allow removing the current entry while iterating, but removal may cause
600 : : * a backward shift. The next entry may thus move one bucket to the left.
601 : : * To detect when it happens, we remember the key pointer of the entry we were
602 : : * going to iterate next. If it does not match, there was a backward shift.
603 : : */
604 [ - + ]: 64256 : if (e->p.b.key != i->next_key) {
605 : 0 : idx = prev_idx(HASHMAP_BASE(h), idx);
606 : 0 : e = ordered_bucket_at(h, idx);
607 : : }
608 [ - + ]: 64256 : assert(e->p.b.key == i->next_key);
609 : : }
610 : :
611 : : #if ENABLE_DEBUG_HASHMAP
612 : : i->prev_idx = idx;
613 : : #endif
614 : :
615 [ + + ]: 9817405 : if (e->iterate_next != IDX_NIL) {
616 : : struct ordered_hashmap_entry *n;
617 : 9768452 : i->idx = e->iterate_next;
618 : 9768452 : n = ordered_bucket_at(h, i->idx);
619 : 9768452 : i->next_key = n->p.b.key;
620 : : } else
621 : 48953 : i->idx = IDX_NIL;
622 : :
623 : 9817405 : return idx;
624 : :
625 : 5781 : at_end:
626 : 5781 : i->idx = IDX_NIL;
627 : 5781 : return IDX_NIL;
628 : : }
629 : :
630 : 12772470 : static unsigned hashmap_iterate_in_internal_order(HashmapBase *h, Iterator *i) {
631 : : unsigned idx;
632 : :
633 [ - + ]: 12772470 : assert(h);
634 [ - + ]: 12772470 : assert(i);
635 : :
636 [ + + ]: 12772470 : if (i->idx == IDX_NIL)
637 : 98298 : goto at_end;
638 : :
639 [ + + ]: 12674172 : if (i->idx == IDX_FIRST) {
640 : : /* fast forward to the first occupied bucket */
641 [ + + ]: 9654559 : if (h->has_indirect) {
642 : 9523703 : i->idx = skip_free_buckets(h, h->indirect.idx_lowest_entry);
643 : 9523703 : h->indirect.idx_lowest_entry = i->idx;
644 : : } else
645 : 130856 : i->idx = skip_free_buckets(h, 0);
646 : :
647 [ + + ]: 9654559 : if (i->idx == IDX_NIL)
648 : 6847 : goto at_end;
649 : : } else {
650 : : struct hashmap_base_entry *e;
651 : :
652 [ - + ]: 3019613 : assert(i->idx > 0);
653 : :
654 : 3019613 : e = bucket_at(h, i->idx);
655 : : /*
656 : : * We allow removing the current entry while iterating, but removal may cause
657 : : * a backward shift. The next entry may thus move one bucket to the left.
658 : : * To detect when it happens, we remember the key pointer of the entry we were
659 : : * going to iterate next. If it does not match, there was a backward shift.
660 : : */
661 [ + + ]: 3019613 : if (e->key != i->next_key)
662 : 6 : e = bucket_at(h, --i->idx);
663 : :
664 [ - + ]: 3019613 : assert(e->key == i->next_key);
665 : : }
666 : :
667 : 12667325 : idx = i->idx;
668 : : #if ENABLE_DEBUG_HASHMAP
669 : : i->prev_idx = idx;
670 : : #endif
671 : :
672 : 12667325 : i->idx = skip_free_buckets(h, i->idx + 1);
673 [ + + ]: 12667325 : if (i->idx != IDX_NIL)
674 : 12537123 : i->next_key = bucket_at(h, i->idx)->key;
675 : : else
676 : 130202 : i->idx = IDX_NIL;
677 : :
678 : 12667325 : return idx;
679 : :
680 : 105145 : at_end:
681 : 105145 : i->idx = IDX_NIL;
682 : 105145 : return IDX_NIL;
683 : : }
684 : :
685 : 23293627 : static unsigned hashmap_iterate_entry(HashmapBase *h, Iterator *i) {
686 [ + + ]: 23293627 : if (!h) {
687 : 697971 : i->idx = IDX_NIL;
688 : 697971 : return IDX_NIL;
689 : : }
690 : :
691 : : #if ENABLE_DEBUG_HASHMAP
692 : : if (i->idx == IDX_FIRST) {
693 : : i->put_count = h->debug.put_count;
694 : : i->rem_count = h->debug.rem_count;
695 : : } else {
696 : : /* While iterating, must not add any new entries */
697 : : assert(i->put_count == h->debug.put_count);
698 : : /* ... or remove entries other than the current one */
699 : : assert(i->rem_count == h->debug.rem_count ||
700 : : (i->rem_count == h->debug.rem_count - 1 &&
701 : : i->prev_idx == h->debug.last_rem_idx));
702 : : /* Reset our removals counter */
703 : : i->rem_count = h->debug.rem_count;
704 : : }
705 : : #endif
706 : :
707 : 9823186 : return h->type == HASHMAP_TYPE_ORDERED ? hashmap_iterate_in_insertion_order((OrderedHashmap*) h, i)
708 [ + + ]: 32418842 : : hashmap_iterate_in_internal_order(h, i);
709 : : }
710 : :
711 : 2511181 : bool internal_hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key) {
712 : : struct hashmap_base_entry *e;
713 : : void *data;
714 : : unsigned idx;
715 : :
716 : 2511181 : idx = hashmap_iterate_entry(h, i);
717 [ + + ]: 2511181 : if (idx == IDX_NIL) {
718 [ + - ]: 804541 : if (value)
719 : 804541 : *value = NULL;
720 [ + + ]: 804541 : if (key)
721 : 443578 : *key = NULL;
722 : :
723 : 804541 : return false;
724 : : }
725 : :
726 : 1706640 : e = bucket_at(h, idx);
727 : 1706640 : data = entry_value(h, e);
728 [ + - ]: 1706640 : if (value)
729 : 1706640 : *value = data;
730 [ + + ]: 1706640 : if (key)
731 : 1556649 : *key = e->key;
732 : :
733 : 1706640 : return true;
734 : : }
735 : :
736 : 448389 : bool set_iterate(const Set *s, Iterator *i, void **value) {
737 : 448389 : return internal_hashmap_iterate(HASHMAP_BASE((Set*) s), i, value, NULL);
738 : : }
739 : :
740 : : #define HASHMAP_FOREACH_IDX(idx, h, i) \
741 : : for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \
742 : : (idx != IDX_NIL); \
743 : : (idx) = hashmap_iterate_entry((h), &(i)))
744 : :
745 : 851 : IteratedCache *internal_hashmap_iterated_cache_new(HashmapBase *h) {
746 : : IteratedCache *cache;
747 : :
748 [ - + ]: 851 : assert(h);
749 [ - + ]: 851 : assert(!h->cached);
750 : :
751 [ - + ]: 851 : if (h->cached)
752 : 0 : return NULL;
753 : :
754 : 851 : cache = new0(IteratedCache, 1);
755 [ - + ]: 851 : if (!cache)
756 : 0 : return NULL;
757 : :
758 : 851 : cache->hashmap = h;
759 : 851 : h->cached = true;
760 : :
761 : 851 : return cache;
762 : : }
763 : :
764 : 269403 : static void reset_direct_storage(HashmapBase *h) {
765 : 269403 : const struct hashmap_type_info *hi = &hashmap_type_info[h->type];
766 : : void *p;
767 : :
768 [ - + ]: 269403 : assert(!h->has_indirect);
769 : :
770 : 269403 : p = mempset(h->direct.storage, 0, hi->entry_size * hi->n_direct_buckets);
771 : 269403 : memset(p, DIB_RAW_INIT, sizeof(dib_raw_t) * hi->n_direct_buckets);
772 : 269403 : }
773 : :
774 : 134606 : static struct HashmapBase *hashmap_base_new(const struct hash_ops *hash_ops, enum HashmapType type HASHMAP_DEBUG_PARAMS) {
775 : : HashmapBase *h;
776 : 134606 : const struct hashmap_type_info *hi = &hashmap_type_info[type];
777 : : bool up;
778 : :
779 : 134606 : up = mempool_enabled();
780 : :
781 [ + + ]: 134606 : h = up ? mempool_alloc0_tile(hi->mempool) : malloc0(hi->head_size);
782 [ - + ]: 134606 : if (!h)
783 : 0 : return NULL;
784 : :
785 : 134606 : h->type = type;
786 : 134606 : h->from_pool = up;
787 [ + + ]: 134606 : h->hash_ops = hash_ops ?: &trivial_hash_ops;
788 : :
789 [ + + ]: 134606 : if (type == HASHMAP_TYPE_ORDERED) {
790 : 85251 : OrderedHashmap *lh = (OrderedHashmap*)h;
791 : 85251 : lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;
792 : : }
793 : :
794 : 134606 : reset_direct_storage(h);
795 : :
796 [ + + ]: 134606 : if (!shared_hash_key_initialized) {
797 : 699 : random_bytes(shared_hash_key, sizeof(shared_hash_key));
798 : 699 : shared_hash_key_initialized= true;
799 : : }
800 : :
801 : : #if ENABLE_DEBUG_HASHMAP
802 : : h->debug.func = func;
803 : : h->debug.file = file;
804 : : h->debug.line = line;
805 : : assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex) == 0);
806 : : LIST_PREPEND(debug_list, hashmap_debug_list, &h->debug);
807 : : assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex) == 0);
808 : : #endif
809 : :
810 : 134606 : return h;
811 : : }
812 : :
813 : 5806 : Hashmap *internal_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
814 : 5806 : return (Hashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
815 : : }
816 : :
817 : 41010 : OrderedHashmap *internal_ordered_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
818 : 41010 : return (OrderedHashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
819 : : }
820 : :
821 : 22196 : Set *internal_set_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
822 : 22196 : return (Set*) hashmap_base_new(hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
823 : : }
824 : :
825 : 324132 : static int hashmap_base_ensure_allocated(HashmapBase **h, const struct hash_ops *hash_ops,
826 : : enum HashmapType type HASHMAP_DEBUG_PARAMS) {
827 : : HashmapBase *q;
828 : :
829 [ - + ]: 324132 : assert(h);
830 : :
831 [ + + ]: 324132 : if (*h)
832 : 258544 : return 0;
833 : :
834 : 65588 : q = hashmap_base_new(hash_ops, type HASHMAP_DEBUG_PASS_ARGS);
835 [ - + ]: 65588 : if (!q)
836 : 0 : return -ENOMEM;
837 : :
838 : 65588 : *h = q;
839 : 65588 : return 0;
840 : : }
841 : :
842 : 90268 : int internal_hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
843 : 90268 : return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
844 : : }
845 : :
846 : 222956 : int internal_ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
847 : 222956 : return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
848 : : }
849 : :
850 : 10908 : int internal_set_ensure_allocated(Set **s, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
851 : 10908 : return hashmap_base_ensure_allocated((HashmapBase**)s, hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
852 : : }
853 : :
854 : 134602 : static void hashmap_free_no_clear(HashmapBase *h) {
855 [ - + ]: 134602 : assert(!h->has_indirect);
856 [ - + ]: 134602 : assert(h->n_direct_entries == 0);
857 : :
858 : : #if ENABLE_DEBUG_HASHMAP
859 : : assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex) == 0);
860 : : LIST_REMOVE(debug_list, hashmap_debug_list, &h->debug);
861 : : assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex) == 0);
862 : : #endif
863 : :
864 [ + + ]: 134602 : if (h->from_pool) {
865 : : /* Ensure that the object didn't get migrated between threads. */
866 [ - + ]: 134486 : assert_se(is_main_thread());
867 : 134486 : mempool_free_tile(hashmap_type_info[h->type].mempool, h);
868 : : } else
869 : 116 : free(h);
870 : 134602 : }
871 : :
872 : 562010 : HashmapBase *internal_hashmap_free(HashmapBase *h, free_func_t default_free_key, free_func_t default_free_value) {
873 [ + + ]: 562010 : if (h) {
874 : 134602 : internal_hashmap_clear(h, default_free_key, default_free_value);
875 : 134602 : hashmap_free_no_clear(h);
876 : : }
877 : :
878 : 562010 : return NULL;
879 : : }
880 : :
881 : 134809 : void internal_hashmap_clear(HashmapBase *h, free_func_t default_free_key, free_func_t default_free_value) {
882 : : free_func_t free_key, free_value;
883 [ + + ]: 134809 : if (!h)
884 : 12 : return;
885 : :
886 [ + + ]: 134797 : free_key = h->hash_ops->free_key ?: default_free_key;
887 [ + + ]: 134797 : free_value = h->hash_ops->free_value ?: default_free_value;
888 : :
889 [ + + + + ]: 134797 : if (free_key || free_value) {
890 : :
891 : : /* If destructor calls are defined, let's destroy things defensively: let's take the item out of the
892 : : * hash table, and only then call the destructor functions. If these destructors then try to unregister
893 : : * themselves from our hash table a second time, the entry is already gone. */
894 : :
895 [ + + ]: 12945716 : while (internal_hashmap_size(h) > 0) {
896 : 12835320 : void *k = NULL;
897 : : void *v;
898 : :
899 : 12835320 : v = internal_hashmap_first_key_and_value(h, true, &k);
900 : :
901 [ + + ]: 12835320 : if (free_key)
902 : 12834364 : free_key(k);
903 : :
904 [ + + ]: 12835320 : if (free_value)
905 : 12813524 : free_value(v);
906 : : }
907 : : }
908 : :
909 [ + + ]: 134797 : if (h->has_indirect) {
910 : 41518 : free(h->indirect.storage);
911 : 41518 : h->has_indirect = false;
912 : : }
913 : :
914 : 134797 : h->n_direct_entries = 0;
915 : 134797 : reset_direct_storage(h);
916 : :
917 [ + + ]: 134797 : if (h->type == HASHMAP_TYPE_ORDERED) {
918 : 85327 : OrderedHashmap *lh = (OrderedHashmap*) h;
919 : 85327 : lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;
920 : : }
921 : :
922 : 134797 : base_set_dirty(h);
923 : : }
924 : :
925 : : static int resize_buckets(HashmapBase *h, unsigned entries_add);
926 : :
927 : : /*
928 : : * Finds an empty bucket to put an entry into, starting the scan at 'idx'.
929 : : * Performs Robin Hood swaps as it goes. The entry to put must be placed
930 : : * by the caller into swap slot IDX_PUT.
931 : : * If used for in-place resizing, may leave a displaced entry in swap slot
932 : : * IDX_PUT. Caller must rehash it next.
933 : : * Returns: true if it left a displaced entry to rehash next in IDX_PUT,
934 : : * false otherwise.
935 : : */
936 : 43812344 : static bool hashmap_put_robin_hood(HashmapBase *h, unsigned idx,
937 : : struct swap_entries *swap) {
938 : : dib_raw_t raw_dib, *dibs;
939 : : unsigned dib, distance;
940 : :
941 : : #if ENABLE_DEBUG_HASHMAP
942 : : h->debug.put_count++;
943 : : #endif
944 : :
945 : 43812344 : dibs = dib_raw_ptr(h);
946 : :
947 : 43812344 : for (distance = 0; ; distance++) {
948 : 91206969 : raw_dib = dibs[idx];
949 [ + + + + ]: 135019313 : if (IN_SET(raw_dib, DIB_RAW_FREE, DIB_RAW_REHASH)) {
950 [ + + ]: 43812344 : if (raw_dib == DIB_RAW_REHASH)
951 : 5690111 : bucket_move_entry(h, swap, idx, IDX_TMP);
952 : :
953 [ + + + + ]: 43812344 : if (h->has_indirect && h->indirect.idx_lowest_entry > idx)
954 : 83 : h->indirect.idx_lowest_entry = idx;
955 : :
956 : 43812344 : bucket_set_dib(h, idx, distance);
957 : 43812344 : bucket_move_entry(h, swap, IDX_PUT, idx);
958 [ + + ]: 43812344 : if (raw_dib == DIB_RAW_REHASH) {
959 : 5690111 : bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
960 : 5690111 : return true;
961 : : }
962 : :
963 : 38122233 : return false;
964 : : }
965 : :
966 : 91206969 : dib = bucket_calculate_dib(h, idx, raw_dib);
967 : :
968 [ + + ]: 91206969 : if (dib < distance) {
969 : : /* Found a wealthier entry. Go Robin Hood! */
970 : 32509934 : bucket_set_dib(h, idx, distance);
971 : :
972 : : /* swap the entries */
973 : 32509934 : bucket_move_entry(h, swap, idx, IDX_TMP);
974 : 32509934 : bucket_move_entry(h, swap, IDX_PUT, idx);
975 : 32509934 : bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
976 : :
977 : 32509934 : distance = dib;
978 : : }
979 : :
980 : 91206969 : idx = next_idx(h, idx);
981 : : }
982 : : }
983 : :
984 : : /*
985 : : * Puts an entry into a hashmap, boldly - no check whether key already exists.
986 : : * The caller must place the entry (only its key and value, not link indexes)
987 : : * in swap slot IDX_PUT.
988 : : * Caller must ensure: the key does not exist yet in the hashmap.
989 : : * that resize is not needed if !may_resize.
990 : : * Returns: 1 if entry was put successfully.
991 : : * -ENOMEM if may_resize==true and resize failed with -ENOMEM.
992 : : * Cannot return -ENOMEM if !may_resize.
993 : : */
994 : 19423003 : static int hashmap_base_put_boldly(HashmapBase *h, unsigned idx,
995 : : struct swap_entries *swap, bool may_resize) {
996 : : struct ordered_hashmap_entry *new_entry;
997 : : int r;
998 : :
999 [ - + ]: 19423003 : assert(idx < n_buckets(h));
1000 : :
1001 : 19423003 : new_entry = bucket_at_swap(swap, IDX_PUT);
1002 : :
1003 [ + + ]: 19423003 : if (may_resize) {
1004 : 19419259 : r = resize_buckets(h, 1);
1005 [ - + ]: 19419259 : if (r < 0)
1006 : 0 : return r;
1007 [ + + ]: 19419259 : if (r > 0)
1008 : 71453 : idx = bucket_hash(h, new_entry->p.b.key);
1009 : : }
1010 [ - + ]: 19423003 : assert(n_entries(h) < n_buckets(h));
1011 : :
1012 [ + + ]: 19423003 : if (h->type == HASHMAP_TYPE_ORDERED) {
1013 : 9749149 : OrderedHashmap *lh = (OrderedHashmap*) h;
1014 : :
1015 : 9749149 : new_entry->iterate_next = IDX_NIL;
1016 : 9749149 : new_entry->iterate_previous = lh->iterate_list_tail;
1017 : :
1018 [ + + ]: 9749149 : if (lh->iterate_list_tail != IDX_NIL) {
1019 : : struct ordered_hashmap_entry *old_tail;
1020 : :
1021 : 9703905 : old_tail = ordered_bucket_at(lh, lh->iterate_list_tail);
1022 [ - + ]: 9703905 : assert(old_tail->iterate_next == IDX_NIL);
1023 : 9703905 : old_tail->iterate_next = IDX_PUT;
1024 : : }
1025 : :
1026 : 9749149 : lh->iterate_list_tail = IDX_PUT;
1027 [ + + ]: 9749149 : if (lh->iterate_list_head == IDX_NIL)
1028 : 45244 : lh->iterate_list_head = IDX_PUT;
1029 : : }
1030 : :
1031 [ - + ]: 19423003 : assert_se(hashmap_put_robin_hood(h, idx, swap) == false);
1032 : :
1033 : 19423003 : n_entries_inc(h);
1034 : : #if ENABLE_DEBUG_HASHMAP
1035 : : h->debug.max_entries = MAX(h->debug.max_entries, n_entries(h));
1036 : : #endif
1037 : :
1038 : 19423003 : base_set_dirty(h);
1039 : :
1040 : 19423003 : return 1;
1041 : : }
1042 : : #define hashmap_put_boldly(h, idx, swap, may_resize) \
1043 : : hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
1044 : :
1045 : : /*
1046 : : * Returns 0 if resize is not needed.
1047 : : * 1 if successfully resized.
1048 : : * -ENOMEM on allocation failure.
1049 : : */
1050 : 19419397 : static int resize_buckets(HashmapBase *h, unsigned entries_add) {
1051 : : struct swap_entries swap;
1052 : : void *new_storage;
1053 : : dib_raw_t *old_dibs, *new_dibs;
1054 : : const struct hashmap_type_info *hi;
1055 : : unsigned idx, optimal_idx;
1056 : : unsigned old_n_buckets, new_n_buckets, n_rehashed, new_n_entries;
1057 : : uint8_t new_shift;
1058 : : bool rehash_next;
1059 : :
1060 [ - + ]: 19419397 : assert(h);
1061 : :
1062 : 19419397 : hi = &hashmap_type_info[h->type];
1063 : 19419397 : new_n_entries = n_entries(h) + entries_add;
1064 : :
1065 : : /* overflow? */
1066 [ + + ]: 19419397 : if (_unlikely_(new_n_entries < entries_add))
1067 : 6 : return -ENOMEM;
1068 : :
1069 : : /* For direct storage we allow 100% load, because it's tiny. */
1070 [ + + + + ]: 19419391 : if (!h->has_indirect && new_n_entries <= hi->n_direct_buckets)
1071 : 104226 : return 0;
1072 : :
1073 : : /*
1074 : : * Load factor = n/m = 1 - (1/INV_KEEP_FREE).
1075 : : * From it follows: m = n + n/(INV_KEEP_FREE - 1)
1076 : : */
1077 : 19315165 : new_n_buckets = new_n_entries + new_n_entries / (INV_KEEP_FREE - 1);
1078 : : /* overflow? */
1079 [ + + ]: 19315165 : if (_unlikely_(new_n_buckets < new_n_entries))
1080 : 6 : return -ENOMEM;
1081 : :
1082 [ - + ]: 19315159 : if (_unlikely_(new_n_buckets > UINT_MAX / (hi->entry_size + sizeof(dib_raw_t))))
1083 : 0 : return -ENOMEM;
1084 : :
1085 : 19315159 : old_n_buckets = n_buckets(h);
1086 : :
1087 [ + + ]: 19315159 : if (_likely_(new_n_buckets <= old_n_buckets))
1088 : 19243694 : return 0;
1089 : :
1090 : 71465 : new_shift = log2u_round_up(MAX(
1091 : : new_n_buckets * (hi->entry_size + sizeof(dib_raw_t)),
1092 : : 2 * sizeof(struct direct_storage)));
1093 : :
1094 : : /* Realloc storage (buckets and DIB array). */
1095 : 71465 : new_storage = realloc(h->has_indirect ? h->indirect.storage : NULL,
1096 [ + + ]: 71465 : 1U << new_shift);
1097 [ - + ]: 71465 : if (!new_storage)
1098 : 0 : return -ENOMEM;
1099 : :
1100 : : /* Must upgrade direct to indirect storage. */
1101 [ + + ]: 71465 : if (!h->has_indirect) {
1102 : 83036 : memcpy(new_storage, h->direct.storage,
1103 : 41518 : old_n_buckets * (hi->entry_size + sizeof(dib_raw_t)));
1104 : 41518 : h->indirect.n_entries = h->n_direct_entries;
1105 : 41518 : h->indirect.idx_lowest_entry = 0;
1106 : 41518 : h->n_direct_entries = 0;
1107 : : }
1108 : :
1109 : : /* Get a new hash key. If we've just upgraded to indirect storage,
1110 : : * allow reusing a previously generated key. It's still a different key
1111 : : * from the shared one that we used for direct storage. */
1112 : 71465 : get_hash_key(h->indirect.hash_key, !h->has_indirect);
1113 : :
1114 : 71465 : h->has_indirect = true;
1115 : 71465 : h->indirect.storage = new_storage;
1116 : 142930 : h->indirect.n_buckets = (1U << new_shift) /
1117 : 71465 : (hi->entry_size + sizeof(dib_raw_t));
1118 : :
1119 : 71465 : old_dibs = (dib_raw_t*)((uint8_t*) new_storage + hi->entry_size * old_n_buckets);
1120 : 71465 : new_dibs = dib_raw_ptr(h);
1121 : :
1122 : : /*
1123 : : * Move the DIB array to the new place, replacing valid DIB values with
1124 : : * DIB_RAW_REHASH to indicate all of the used buckets need rehashing.
1125 : : * Note: Overlap is not possible, because we have at least doubled the
1126 : : * number of buckets and dib_raw_t is smaller than any entry type.
1127 : : */
1128 [ + + ]: 30566887 : for (idx = 0; idx < old_n_buckets; idx++) {
1129 [ - + ]: 30495422 : assert(old_dibs[idx] != DIB_RAW_REHASH);
1130 [ + + ]: 30495422 : new_dibs[idx] = old_dibs[idx] == DIB_RAW_FREE ? DIB_RAW_FREE
1131 : : : DIB_RAW_REHASH;
1132 : : }
1133 : :
1134 : : /* Zero the area of newly added entries (including the old DIB area) */
1135 [ + - ]: 71465 : memzero(bucket_at(h, old_n_buckets),
1136 : : (n_buckets(h) - old_n_buckets) * hi->entry_size);
1137 : :
1138 : : /* The upper half of the new DIB array needs initialization */
1139 : 71465 : memset(&new_dibs[old_n_buckets], DIB_RAW_INIT,
1140 : 71465 : (n_buckets(h) - old_n_buckets) * sizeof(dib_raw_t));
1141 : :
1142 : : /* Rehash entries that need it */
1143 : 71465 : n_rehashed = 0;
1144 [ + + ]: 30566887 : for (idx = 0; idx < old_n_buckets; idx++) {
1145 [ + + ]: 30495422 : if (new_dibs[idx] != DIB_RAW_REHASH)
1146 : 11778516 : continue;
1147 : :
1148 : 18716906 : optimal_idx = bucket_hash(h, bucket_at(h, idx)->key);
1149 : :
1150 : : /*
1151 : : * Not much to do if by luck the entry hashes to its current
1152 : : * location. Just set its DIB.
1153 : : */
1154 [ + + ]: 18716906 : if (optimal_idx == idx) {
1155 : 17676 : new_dibs[idx] = 0;
1156 : 17676 : n_rehashed++;
1157 : 17676 : continue;
1158 : : }
1159 : :
1160 : 18699230 : new_dibs[idx] = DIB_RAW_FREE;
1161 : 18699230 : bucket_move_entry(h, &swap, idx, IDX_PUT);
1162 : : /* bucket_move_entry does not clear the source */
1163 [ + - ]: 18699230 : memzero(bucket_at(h, idx), hi->entry_size);
1164 : :
1165 : : do {
1166 : : /*
1167 : : * Find the new bucket for the current entry. This may make
1168 : : * another entry homeless and load it into IDX_PUT.
1169 : : */
1170 : 24389341 : rehash_next = hashmap_put_robin_hood(h, optimal_idx, &swap);
1171 : 24389341 : n_rehashed++;
1172 : :
1173 : : /* Did the current entry displace another one? */
1174 [ + + ]: 24389341 : if (rehash_next)
1175 : 5690111 : optimal_idx = bucket_hash(h, bucket_at_swap(&swap, IDX_PUT)->p.b.key);
1176 [ + + ]: 24389341 : } while (rehash_next);
1177 : : }
1178 : :
1179 [ - + ]: 71465 : assert(n_rehashed == n_entries(h));
1180 : :
1181 : 71465 : return 1;
1182 : : }
1183 : :
1184 : : /*
1185 : : * Finds an entry with a matching key
1186 : : * Returns: index of the found entry, or IDX_NIL if not found.
1187 : : */
1188 : 52314007 : static unsigned base_bucket_scan(HashmapBase *h, unsigned idx, const void *key) {
1189 : : struct hashmap_base_entry *e;
1190 : : unsigned dib, distance;
1191 : 52314007 : dib_raw_t *dibs = dib_raw_ptr(h);
1192 : :
1193 [ - + ]: 52314007 : assert(idx < n_buckets(h));
1194 : :
1195 : 52314007 : for (distance = 0; ; distance++) {
1196 [ + + ]: 163127579 : if (dibs[idx] == DIB_RAW_FREE)
1197 : 20118396 : return IDX_NIL;
1198 : :
1199 : 143009183 : dib = bucket_calculate_dib(h, idx, dibs[idx]);
1200 : :
1201 [ + + ]: 143009183 : if (dib < distance)
1202 : 12649748 : return IDX_NIL;
1203 [ + + ]: 130359435 : if (dib == distance) {
1204 : 68114031 : e = bucket_at(h, idx);
1205 [ + + ]: 68114031 : if (h->hash_ops->compare(e->key, key) == 0)
1206 : 19545863 : return idx;
1207 : : }
1208 : :
1209 : 110813572 : idx = next_idx(h, idx);
1210 : : }
1211 : : }
1212 : : #define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
1213 : :
1214 : 19144495 : int hashmap_put(Hashmap *h, const void *key, void *value) {
1215 : : struct swap_entries swap;
1216 : : struct plain_hashmap_entry *e;
1217 : : unsigned hash, idx;
1218 : :
1219 [ - + ]: 19144495 : assert(h);
1220 : :
1221 : 19144495 : hash = bucket_hash(h, key);
1222 : 19144495 : idx = bucket_scan(h, hash, key);
1223 [ + + ]: 19144495 : if (idx != IDX_NIL) {
1224 : 58 : e = plain_bucket_at(h, idx);
1225 [ + + ]: 58 : if (e->value == value)
1226 : 24 : return 0;
1227 : 34 : return -EEXIST;
1228 : : }
1229 : :
1230 : 19144437 : e = &bucket_at_swap(&swap, IDX_PUT)->p;
1231 : 19144437 : e->b.key = key;
1232 : 19144437 : e->value = value;
1233 : 19144437 : return hashmap_put_boldly(h, hash, &swap, true);
1234 : : }
1235 : :
1236 : 54068 : int set_put(Set *s, const void *key) {
1237 : : struct swap_entries swap;
1238 : : struct hashmap_base_entry *e;
1239 : : unsigned hash, idx;
1240 : :
1241 [ - + ]: 54068 : assert(s);
1242 : :
1243 : 54068 : hash = bucket_hash(s, key);
1244 : 54068 : idx = bucket_scan(s, hash, key);
1245 [ + + ]: 54068 : if (idx != IDX_NIL)
1246 : 356 : return 0;
1247 : :
1248 : 53712 : e = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1249 : 53712 : e->key = key;
1250 : 53712 : return hashmap_put_boldly(s, hash, &swap, true);
1251 : : }
1252 : :
1253 : 226760 : int hashmap_replace(Hashmap *h, const void *key, void *value) {
1254 : : struct swap_entries swap;
1255 : : struct plain_hashmap_entry *e;
1256 : : unsigned hash, idx;
1257 : :
1258 [ - + ]: 226760 : assert(h);
1259 : :
1260 : 226760 : hash = bucket_hash(h, key);
1261 : 226760 : idx = bucket_scan(h, hash, key);
1262 [ + + ]: 226760 : if (idx != IDX_NIL) {
1263 : 5958 : e = plain_bucket_at(h, idx);
1264 : : #if ENABLE_DEBUG_HASHMAP
1265 : : /* Although the key is equal, the key pointer may have changed,
1266 : : * and this would break our assumption for iterating. So count
1267 : : * this operation as incompatible with iteration. */
1268 : : if (e->b.key != key) {
1269 : : h->b.debug.put_count++;
1270 : : h->b.debug.rem_count++;
1271 : : h->b.debug.last_rem_idx = idx;
1272 : : }
1273 : : #endif
1274 : 5958 : e->b.key = key;
1275 : 5958 : e->value = value;
1276 : 5958 : hashmap_set_dirty(h);
1277 : :
1278 : 5958 : return 0;
1279 : : }
1280 : :
1281 : 220802 : e = &bucket_at_swap(&swap, IDX_PUT)->p;
1282 : 220802 : e->b.key = key;
1283 : 220802 : e->value = value;
1284 : 220802 : return hashmap_put_boldly(h, hash, &swap, true);
1285 : : }
1286 : :
1287 : 1016 : int hashmap_update(Hashmap *h, const void *key, void *value) {
1288 : : struct plain_hashmap_entry *e;
1289 : : unsigned hash, idx;
1290 : :
1291 [ - + ]: 1016 : assert(h);
1292 : :
1293 : 1016 : hash = bucket_hash(h, key);
1294 : 1016 : idx = bucket_scan(h, hash, key);
1295 [ + + ]: 1016 : if (idx == IDX_NIL)
1296 : 6 : return -ENOENT;
1297 : :
1298 : 1010 : e = plain_bucket_at(h, idx);
1299 : 1010 : e->value = value;
1300 : 1010 : hashmap_set_dirty(h);
1301 : :
1302 : 1010 : return 0;
1303 : : }
1304 : :
1305 : 6944499 : void *internal_hashmap_get(HashmapBase *h, const void *key) {
1306 : : struct hashmap_base_entry *e;
1307 : : unsigned hash, idx;
1308 : :
1309 [ + + ]: 6944499 : if (!h)
1310 : 10082 : return NULL;
1311 : :
1312 : 6934417 : hash = bucket_hash(h, key);
1313 : 6934417 : idx = bucket_scan(h, hash, key);
1314 [ + + ]: 6934417 : if (idx == IDX_NIL)
1315 : 268775 : return NULL;
1316 : :
1317 : 6665642 : e = bucket_at(h, idx);
1318 : 6665642 : return entry_value(h, e);
1319 : : }
1320 : :
1321 : 225902 : void *hashmap_get2(Hashmap *h, const void *key, void **key2) {
1322 : : struct plain_hashmap_entry *e;
1323 : : unsigned hash, idx;
1324 : :
1325 [ + + ]: 225902 : if (!h)
1326 : 4450 : return NULL;
1327 : :
1328 : 221452 : hash = bucket_hash(h, key);
1329 : 221452 : idx = bucket_scan(h, hash, key);
1330 [ + + ]: 221452 : if (idx == IDX_NIL)
1331 : 217400 : return NULL;
1332 : :
1333 : 4052 : e = plain_bucket_at(h, idx);
1334 [ + - ]: 4052 : if (key2)
1335 : 4052 : *key2 = (void*) e->b.key;
1336 : :
1337 : 4052 : return e->value;
1338 : : }
1339 : :
1340 : 19217300 : bool internal_hashmap_contains(HashmapBase *h, const void *key) {
1341 : : unsigned hash;
1342 : :
1343 [ + + ]: 19217300 : if (!h)
1344 : 54 : return false;
1345 : :
1346 : 19217246 : hash = bucket_hash(h, key);
1347 : 19217246 : return bucket_scan(h, hash, key) != IDX_NIL;
1348 : : }
1349 : :
1350 : 6666558 : void *internal_hashmap_remove(HashmapBase *h, const void *key) {
1351 : : struct hashmap_base_entry *e;
1352 : : unsigned hash, idx;
1353 : : void *data;
1354 : :
1355 [ + + ]: 6666558 : if (!h)
1356 : 181541 : return NULL;
1357 : :
1358 : 6485017 : hash = bucket_hash(h, key);
1359 : 6485017 : idx = bucket_scan(h, hash, key);
1360 [ + + ]: 6485017 : if (idx == IDX_NIL)
1361 : 31161 : return NULL;
1362 : :
1363 : 6453856 : e = bucket_at(h, idx);
1364 : 6453856 : data = entry_value(h, e);
1365 : 6453856 : remove_entry(h, idx);
1366 : :
1367 : 6453856 : return data;
1368 : : }
1369 : :
1370 : 5758 : void *hashmap_remove2(Hashmap *h, const void *key, void **rkey) {
1371 : : struct plain_hashmap_entry *e;
1372 : : unsigned hash, idx;
1373 : : void *data;
1374 : :
1375 [ + + ]: 5758 : if (!h) {
1376 [ + - ]: 210 : if (rkey)
1377 : 210 : *rkey = NULL;
1378 : 210 : return NULL;
1379 : : }
1380 : :
1381 : 5548 : hash = bucket_hash(h, key);
1382 : 5548 : idx = bucket_scan(h, hash, key);
1383 [ + + ]: 5548 : if (idx == IDX_NIL) {
1384 [ + - ]: 5542 : if (rkey)
1385 : 5542 : *rkey = NULL;
1386 : 5542 : return NULL;
1387 : : }
1388 : :
1389 : 6 : e = plain_bucket_at(h, idx);
1390 : 6 : data = e->value;
1391 [ + - ]: 6 : if (rkey)
1392 : 6 : *rkey = (void*) e->b.key;
1393 : :
1394 : 6 : remove_entry(h, idx);
1395 : :
1396 : 6 : return data;
1397 : : }
1398 : :
1399 : 24 : 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;
1403 : :
1404 [ + + ]: 24 : if (!h)
1405 : 6 : return -ENOENT;
1406 : :
1407 : 18 : old_hash = bucket_hash(h, old_key);
1408 : 18 : idx = bucket_scan(h, old_hash, old_key);
1409 [ + + ]: 18 : if (idx == IDX_NIL)
1410 : 6 : return -ENOENT;
1411 : :
1412 : 12 : new_hash = bucket_hash(h, new_key);
1413 [ + + ]: 12 : if (bucket_scan(h, new_hash, new_key) != IDX_NIL)
1414 : 6 : return -EEXIST;
1415 : :
1416 : 6 : remove_entry(h, idx);
1417 : :
1418 : 6 : e = &bucket_at_swap(&swap, IDX_PUT)->p;
1419 : 6 : e->b.key = new_key;
1420 : 6 : e->value = value;
1421 [ - + ]: 6 : assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
1422 : :
1423 : 6 : return 0;
1424 : : }
1425 : :
1426 : 0 : 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;
1430 : :
1431 [ # # ]: 0 : if (!s)
1432 : 0 : return -ENOENT;
1433 : :
1434 : 0 : old_hash = bucket_hash(s, old_key);
1435 : 0 : idx = bucket_scan(s, old_hash, old_key);
1436 [ # # ]: 0 : if (idx == IDX_NIL)
1437 : 0 : return -ENOENT;
1438 : :
1439 : 0 : new_hash = bucket_hash(s, new_key);
1440 [ # # ]: 0 : if (bucket_scan(s, new_hash, new_key) != IDX_NIL)
1441 : 0 : return -EEXIST;
1442 : :
1443 : 0 : remove_entry(s, idx);
1444 : :
1445 : 0 : e = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1446 : 0 : e->key = new_key;
1447 [ # # ]: 0 : assert_se(hashmap_put_boldly(s, new_hash, &swap, false) == 1);
1448 : :
1449 : 0 : return 0;
1450 : : }
1451 : :
1452 : 3664 : 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;
1456 : :
1457 [ + + ]: 3664 : if (!h)
1458 : 6 : return -ENOENT;
1459 : :
1460 : 3658 : old_hash = bucket_hash(h, old_key);
1461 : 3658 : idx_old = bucket_scan(h, old_hash, old_key);
1462 [ + + ]: 3658 : if (idx_old == IDX_NIL)
1463 : 6 : return -ENOENT;
1464 : :
1465 : 3652 : old_key = bucket_at(HASHMAP_BASE(h), idx_old)->key;
1466 : :
1467 : 3652 : new_hash = bucket_hash(h, new_key);
1468 : 3652 : idx_new = bucket_scan(h, new_hash, new_key);
1469 [ + + ]: 3652 : if (idx_new != IDX_NIL)
1470 [ + + ]: 3646 : if (idx_old != idx_new) {
1471 : 126 : remove_entry(h, idx_new);
1472 : : /* Compensate for a possible backward shift. */
1473 [ + + ]: 126 : if (old_key != bucket_at(HASHMAP_BASE(h), idx_old)->key)
1474 : 30 : idx_old = prev_idx(HASHMAP_BASE(h), idx_old);
1475 [ - + ]: 126 : assert(old_key == bucket_at(HASHMAP_BASE(h), idx_old)->key);
1476 : : }
1477 : :
1478 : 3652 : remove_entry(h, idx_old);
1479 : :
1480 : 3652 : e = &bucket_at_swap(&swap, IDX_PUT)->p;
1481 : 3652 : e->b.key = new_key;
1482 : 3652 : e->value = value;
1483 [ - + ]: 3652 : assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
1484 : :
1485 : 3652 : return 0;
1486 : : }
1487 : :
1488 : 15892 : void *internal_hashmap_remove_value(HashmapBase *h, const void *key, void *value) {
1489 : : struct hashmap_base_entry *e;
1490 : : unsigned hash, idx;
1491 : :
1492 [ + + ]: 15892 : if (!h)
1493 : 6 : return NULL;
1494 : :
1495 : 15886 : hash = bucket_hash(h, key);
1496 : 15886 : idx = bucket_scan(h, hash, key);
1497 [ + + ]: 15886 : if (idx == IDX_NIL)
1498 : 310 : return NULL;
1499 : :
1500 : 15576 : e = bucket_at(h, idx);
1501 [ + + ]: 15576 : if (entry_value(h, e) != value)
1502 : 6 : return NULL;
1503 : :
1504 : 15570 : remove_entry(h, idx);
1505 : :
1506 : 15570 : return value;
1507 : : }
1508 : :
1509 : 19399252 : static unsigned find_first_entry(HashmapBase *h) {
1510 : 19399252 : Iterator i = ITERATOR_FIRST;
1511 : :
1512 [ + + + + ]: 19399252 : if (!h || !n_entries(h))
1513 : 102570 : return IDX_NIL;
1514 : :
1515 : 19296682 : return hashmap_iterate_entry(h, &i);
1516 : : }
1517 : :
1518 : 19399252 : void *internal_hashmap_first_key_and_value(HashmapBase *h, bool remove, void **ret_key) {
1519 : : struct hashmap_base_entry *e;
1520 : : void *key, *data;
1521 : : unsigned idx;
1522 : :
1523 : 19399252 : idx = find_first_entry(h);
1524 [ + + ]: 19399252 : if (idx == IDX_NIL) {
1525 [ + + ]: 102570 : if (ret_key)
1526 : 13784 : *ret_key = NULL;
1527 : 102570 : return NULL;
1528 : : }
1529 : :
1530 : 19296682 : e = bucket_at(h, idx);
1531 : 19296682 : key = (void*) e->key;
1532 : 19296682 : data = entry_value(h, e);
1533 : :
1534 [ + + ]: 19296682 : if (remove)
1535 : 12896282 : remove_entry(h, idx);
1536 : :
1537 [ + + ]: 19296682 : if (ret_key)
1538 : 19226442 : *ret_key = key;
1539 : :
1540 : 19296682 : return data;
1541 : : }
1542 : :
1543 : 19578500 : unsigned internal_hashmap_size(HashmapBase *h) {
1544 [ + + ]: 19578500 : if (!h)
1545 : 146972 : return 0;
1546 : :
1547 : 19431528 : return n_entries(h);
1548 : : }
1549 : :
1550 : 60 : unsigned internal_hashmap_buckets(HashmapBase *h) {
1551 [ + + ]: 60 : if (!h)
1552 : 6 : return 0;
1553 : :
1554 : 54 : return n_buckets(h);
1555 : : }
1556 : :
1557 : 12 : int internal_hashmap_merge(Hashmap *h, Hashmap *other) {
1558 : : Iterator i;
1559 : : unsigned idx;
1560 : :
1561 [ - + ]: 12 : assert(h);
1562 : :
1563 [ + + ]: 48 : HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1564 : 36 : struct plain_hashmap_entry *pe = plain_bucket_at(other, idx);
1565 : : int r;
1566 : :
1567 : 36 : r = hashmap_put(h, pe->b.key, pe->value);
1568 [ - + # # ]: 36 : if (r < 0 && r != -EEXIST)
1569 : 0 : return r;
1570 : : }
1571 : :
1572 : 12 : return 0;
1573 : : }
1574 : :
1575 : 0 : int set_merge(Set *s, Set *other) {
1576 : : Iterator i;
1577 : : unsigned idx;
1578 : :
1579 [ # # ]: 0 : assert(s);
1580 : :
1581 [ # # ]: 0 : HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1582 : 0 : struct set_entry *se = set_bucket_at(other, idx);
1583 : : int r;
1584 : :
1585 : 0 : r = set_put(s, se->b.key);
1586 [ # # ]: 0 : if (r < 0)
1587 : 0 : return r;
1588 : : }
1589 : :
1590 : 0 : return 0;
1591 : : }
1592 : :
1593 : 24 : int internal_hashmap_reserve(HashmapBase *h, unsigned entries_add) {
1594 : : int r;
1595 : :
1596 [ - + ]: 24 : assert(h);
1597 : :
1598 : 24 : r = resize_buckets(h, entries_add);
1599 [ + + ]: 24 : if (r < 0)
1600 : 12 : return r;
1601 : :
1602 : 12 : return 0;
1603 : : }
1604 : :
1605 : : /*
1606 : : * The same as hashmap_merge(), but every new item from other is moved to h.
1607 : : * Keys already in h are skipped and stay in other.
1608 : : * Returns: 0 on success.
1609 : : * -ENOMEM on alloc failure, in which case no move has been done.
1610 : : */
1611 : 120 : int internal_hashmap_move(HashmapBase *h, HashmapBase *other) {
1612 : : struct swap_entries swap;
1613 : : struct hashmap_base_entry *e, *n;
1614 : : Iterator i;
1615 : : unsigned idx;
1616 : : int r;
1617 : :
1618 [ - + ]: 120 : assert(h);
1619 : :
1620 [ + + ]: 120 : if (!other)
1621 : 6 : return 0;
1622 : :
1623 [ - + ]: 114 : assert(other->type == h->type);
1624 : :
1625 : : /*
1626 : : * This reserves buckets for the worst case, where none of other's
1627 : : * entries are yet present in h. This is preferable to risking
1628 : : * an allocation failure in the middle of the moving and having to
1629 : : * rollback or return a partial result.
1630 : : */
1631 : 114 : r = resize_buckets(h, n_entries(other));
1632 [ - + ]: 114 : if (r < 0)
1633 : 0 : return r;
1634 : :
1635 [ + + ]: 206 : HASHMAP_FOREACH_IDX(idx, other, i) {
1636 : : unsigned h_hash;
1637 : :
1638 : 92 : e = bucket_at(other, idx);
1639 : 92 : h_hash = bucket_hash(h, e->key);
1640 [ + + ]: 92 : if (bucket_scan(h, h_hash, e->key) != IDX_NIL)
1641 : 6 : continue;
1642 : :
1643 : 86 : n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1644 : 86 : n->key = e->key;
1645 [ + + ]: 86 : if (h->type != HASHMAP_TYPE_SET)
1646 : 18 : ((struct plain_hashmap_entry*) n)->value =
1647 : 18 : ((struct plain_hashmap_entry*) e)->value;
1648 [ - + ]: 86 : assert_se(hashmap_put_boldly(h, h_hash, &swap, false) == 1);
1649 : :
1650 : 86 : remove_entry(other, idx);
1651 : : }
1652 : :
1653 : 114 : return 0;
1654 : : }
1655 : :
1656 : 326 : int internal_hashmap_move_one(HashmapBase *h, HashmapBase *other, const void *key) {
1657 : : struct swap_entries swap;
1658 : : unsigned h_hash, other_hash, idx;
1659 : : struct hashmap_base_entry *e, *n;
1660 : : int r;
1661 : :
1662 [ - + ]: 326 : assert(h);
1663 : :
1664 : 326 : h_hash = bucket_hash(h, key);
1665 [ + + ]: 326 : if (bucket_scan(h, h_hash, key) != IDX_NIL)
1666 : 6 : return -EEXIST;
1667 : :
1668 [ + + ]: 320 : if (!other)
1669 : 6 : return -ENOENT;
1670 : :
1671 [ - + ]: 314 : assert(other->type == h->type);
1672 : :
1673 : 314 : other_hash = bucket_hash(other, key);
1674 : 314 : idx = bucket_scan(other, other_hash, key);
1675 [ + + ]: 314 : if (idx == IDX_NIL)
1676 : 6 : return -ENOENT;
1677 : :
1678 : 308 : e = bucket_at(other, idx);
1679 : :
1680 : 308 : n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1681 : 308 : n->key = e->key;
1682 [ + - ]: 308 : if (h->type != HASHMAP_TYPE_SET)
1683 : 308 : ((struct plain_hashmap_entry*) n)->value =
1684 : 308 : ((struct plain_hashmap_entry*) e)->value;
1685 : 308 : r = hashmap_put_boldly(h, h_hash, &swap, true);
1686 [ - + ]: 308 : if (r < 0)
1687 : 0 : return r;
1688 : :
1689 : 308 : remove_entry(other, idx);
1690 : 308 : return 0;
1691 : : }
1692 : :
1693 : 6 : HashmapBase *internal_hashmap_copy(HashmapBase *h) {
1694 : : HashmapBase *copy;
1695 : : int r;
1696 : :
1697 [ - + ]: 6 : assert(h);
1698 : :
1699 : 6 : copy = hashmap_base_new(h->hash_ops, h->type HASHMAP_DEBUG_SRC_ARGS);
1700 [ - + ]: 6 : if (!copy)
1701 : 0 : return NULL;
1702 : :
1703 [ + - - ]: 6 : switch (h->type) {
1704 : 6 : case HASHMAP_TYPE_PLAIN:
1705 : : case HASHMAP_TYPE_ORDERED:
1706 : 6 : r = hashmap_merge((Hashmap*)copy, (Hashmap*)h);
1707 : 6 : break;
1708 : 0 : case HASHMAP_TYPE_SET:
1709 : 0 : r = set_merge((Set*)copy, (Set*)h);
1710 : 0 : break;
1711 : 0 : default:
1712 : 0 : assert_not_reached("Unknown hashmap type");
1713 : : }
1714 : :
1715 [ - + ]: 6 : if (r < 0) {
1716 : 0 : internal_hashmap_free(copy, false, false);
1717 : 0 : return NULL;
1718 : : }
1719 : :
1720 : 6 : return copy;
1721 : : }
1722 : :
1723 : 3850 : char **internal_hashmap_get_strv(HashmapBase *h) {
1724 : : char **sv;
1725 : : Iterator i;
1726 : : unsigned idx, n;
1727 : :
1728 : 3850 : sv = new(char*, n_entries(h)+1);
1729 [ - + ]: 3850 : if (!sv)
1730 : 0 : return NULL;
1731 : :
1732 : 3850 : n = 0;
1733 [ + + ]: 9770 : HASHMAP_FOREACH_IDX(idx, h, i)
1734 : 5920 : sv[n++] = entry_value(h, bucket_at(h, idx));
1735 : 3850 : sv[n] = NULL;
1736 : :
1737 : 3850 : return sv;
1738 : : }
1739 : :
1740 : 33 : void *ordered_hashmap_next(OrderedHashmap *h, const void *key) {
1741 : : struct ordered_hashmap_entry *e;
1742 : : unsigned hash, idx;
1743 : :
1744 [ + + ]: 33 : if (!h)
1745 : 3 : return NULL;
1746 : :
1747 : 30 : hash = bucket_hash(h, key);
1748 : 30 : idx = bucket_scan(h, hash, key);
1749 [ + + ]: 30 : if (idx == IDX_NIL)
1750 : 3 : return NULL;
1751 : :
1752 : 27 : e = ordered_bucket_at(h, idx);
1753 [ + + ]: 27 : if (e->iterate_next == IDX_NIL)
1754 : 7 : return NULL;
1755 : 20 : return ordered_bucket_at(h, e->iterate_next)->p.value;
1756 : : }
1757 : :
1758 : 31468 : int set_consume(Set *s, void *value) {
1759 : : int r;
1760 : :
1761 [ - + ]: 31468 : assert(s);
1762 [ - + ]: 31468 : assert(value);
1763 : :
1764 : 31468 : r = set_put(s, value);
1765 [ + + ]: 31468 : if (r <= 0)
1766 : 236 : free(value);
1767 : :
1768 : 31468 : return r;
1769 : : }
1770 : :
1771 : 3300 : int hashmap_put_strdup(Hashmap **h, const char *k, const char *v) {
1772 : : int r;
1773 : :
1774 : 3300 : r = hashmap_ensure_allocated(h, &string_hash_ops_free_free);
1775 [ - + ]: 3300 : if (r < 0)
1776 : 0 : return r;
1777 : :
1778 : 3300 : _cleanup_free_ char *kdup = NULL, *vdup = NULL;
1779 : 3300 : kdup = strdup(k);
1780 : 3300 : vdup = strdup(v);
1781 [ + - - + ]: 3300 : if (!kdup || !vdup)
1782 : 0 : return -ENOMEM;
1783 : :
1784 : 3300 : r = hashmap_put(*h, kdup, vdup);
1785 [ - + ]: 3300 : if (r < 0) {
1786 [ # # # # ]: 0 : if (r == -EEXIST && streq(v, hashmap_get(*h, kdup)))
1787 : 0 : return 0;
1788 : 0 : return r;
1789 : : }
1790 : :
1791 [ - + ]: 3300 : assert(r > 0); /* 0 would mean vdup is already in the hashmap, which cannot be */
1792 : 3300 : kdup = vdup = NULL;
1793 : :
1794 : 3300 : return 0;
1795 : : }
1796 : :
1797 : 19432 : int set_put_strdup(Set *s, const char *p) {
1798 : : char *c;
1799 : :
1800 [ - + ]: 19432 : assert(s);
1801 [ - + ]: 19432 : assert(p);
1802 : :
1803 [ + + ]: 19432 : if (set_contains(s, (char*) p))
1804 : 352 : return 0;
1805 : :
1806 : 19080 : c = strdup(p);
1807 [ - + ]: 19080 : if (!c)
1808 : 0 : return -ENOMEM;
1809 : :
1810 : 19080 : return set_consume(s, c);
1811 : : }
1812 : :
1813 : 0 : int set_put_strdupv(Set *s, char **l) {
1814 : 0 : int n = 0, r;
1815 : : char **i;
1816 : :
1817 [ # # ]: 0 : assert(s);
1818 : :
1819 [ # # # # ]: 0 : STRV_FOREACH(i, l) {
1820 : 0 : r = set_put_strdup(s, *i);
1821 [ # # ]: 0 : if (r < 0)
1822 : 0 : return r;
1823 : :
1824 : 0 : n += r;
1825 : : }
1826 : :
1827 : 0 : return n;
1828 : : }
1829 : :
1830 : 0 : int set_put_strsplit(Set *s, const char *v, const char *separators, ExtractFlags flags) {
1831 : 0 : const char *p = v;
1832 : : int r;
1833 : :
1834 [ # # ]: 0 : assert(s);
1835 [ # # ]: 0 : assert(v);
1836 : :
1837 : 0 : for (;;) {
1838 : : char *word;
1839 : :
1840 : 0 : r = extract_first_word(&p, &word, separators, flags);
1841 [ # # ]: 0 : if (r <= 0)
1842 : 0 : return r;
1843 : :
1844 : 0 : r = set_consume(s, word);
1845 [ # # ]: 0 : if (r < 0)
1846 : 0 : return r;
1847 : : }
1848 : : }
1849 : :
1850 : : /* expand the cachemem if needed, return true if newly (re)activated. */
1851 : 42228 : static int cachemem_maintain(CacheMem *mem, unsigned size) {
1852 [ - + ]: 42228 : assert(mem);
1853 : :
1854 [ + + ]: 42228 : if (!GREEDY_REALLOC(mem->ptr, mem->n_allocated, size)) {
1855 [ - + ]: 6 : if (size > 0)
1856 : 0 : return -ENOMEM;
1857 : : }
1858 : :
1859 [ + + ]: 42228 : if (!mem->active) {
1860 : 50 : mem->active = true;
1861 : 50 : return true;
1862 : : }
1863 : :
1864 : 42178 : return false;
1865 : : }
1866 : :
1867 : 41892 : int iterated_cache_get(IteratedCache *cache, const void ***res_keys, const void ***res_values, unsigned *res_n_entries) {
1868 : 41892 : bool sync_keys = false, sync_values = false;
1869 : : unsigned size;
1870 : : int r;
1871 : :
1872 [ - + ]: 41892 : assert(cache);
1873 [ - + ]: 41892 : assert(cache->hashmap);
1874 : :
1875 : 41892 : size = n_entries(cache->hashmap);
1876 : :
1877 [ + + ]: 41892 : if (res_keys) {
1878 : 336 : r = cachemem_maintain(&cache->keys, size);
1879 [ - + ]: 336 : if (r < 0)
1880 : 0 : return r;
1881 : :
1882 : 336 : sync_keys = r;
1883 : : } else
1884 : 41556 : cache->keys.active = false;
1885 : :
1886 [ + - ]: 41892 : if (res_values) {
1887 : 41892 : r = cachemem_maintain(&cache->values, size);
1888 [ - + ]: 41892 : if (r < 0)
1889 : 0 : return r;
1890 : :
1891 : 41892 : sync_values = r;
1892 : : } else
1893 : 0 : cache->values.active = false;
1894 : :
1895 [ + + ]: 41892 : if (cache->hashmap->dirty) {
1896 [ + + ]: 377 : if (cache->keys.active)
1897 : 333 : sync_keys = true;
1898 [ + - ]: 377 : if (cache->values.active)
1899 : 377 : sync_values = true;
1900 : :
1901 : 377 : cache->hashmap->dirty = false;
1902 : : }
1903 : :
1904 [ + + + + ]: 41892 : if (sync_keys || sync_values) {
1905 : : unsigned i, idx;
1906 : : Iterator iter;
1907 : :
1908 : 380 : i = 0;
1909 [ + + ]: 1475740 : HASHMAP_FOREACH_IDX(idx, cache->hashmap, iter) {
1910 : : struct hashmap_base_entry *e;
1911 : :
1912 : 1475360 : e = bucket_at(cache->hashmap, idx);
1913 : :
1914 [ + + ]: 1475360 : if (sync_keys)
1915 : 1474500 : cache->keys.ptr[i] = e->key;
1916 [ + - ]: 1475360 : if (sync_values)
1917 : 1475360 : cache->values.ptr[i] = entry_value(cache->hashmap, e);
1918 : 1475360 : i++;
1919 : : }
1920 : : }
1921 : :
1922 [ + + ]: 41892 : if (res_keys)
1923 : 336 : *res_keys = cache->keys.ptr;
1924 [ + - ]: 41892 : if (res_values)
1925 : 41892 : *res_values = cache->values.ptr;
1926 [ + - ]: 41892 : if (res_n_entries)
1927 : 41892 : *res_n_entries = size;
1928 : :
1929 : 41892 : return 0;
1930 : : }
1931 : :
1932 : 851 : IteratedCache *iterated_cache_free(IteratedCache *cache) {
1933 [ + - ]: 851 : if (cache) {
1934 : 851 : free(cache->keys.ptr);
1935 : 851 : free(cache->values.ptr);
1936 : : }
1937 : :
1938 : 851 : return mfree(cache);
1939 : : }
|
