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 6254666 : static unsigned n_buckets(HashmapBase *h) {
306 6254666 : return h->has_indirect ? h->indirect.n_buckets
307 6254666 : : hashmap_type_info[h->type].n_direct_buckets;
308 : }
309 :
310 475397 : static unsigned n_entries(HashmapBase *h) {
311 475397 : return h->has_indirect ? h->indirect.n_entries
312 475397 : : h->n_direct_entries;
313 : }
314 :
315 119283 : static void n_entries_inc(HashmapBase *h) {
316 119283 : if (h->has_indirect)
317 93037 : h->indirect.n_entries++;
318 : else
319 26246 : h->n_direct_entries++;
320 119283 : }
321 :
322 103699 : static void n_entries_dec(HashmapBase *h) {
323 103699 : if (h->has_indirect)
324 91971 : h->indirect.n_entries--;
325 : else
326 11728 : h->n_direct_entries--;
327 103699 : }
328 :
329 7411881 : static void *storage_ptr(HashmapBase *h) {
330 7411881 : return h->has_indirect ? h->indirect.storage
331 7411881 : : h->direct.storage;
332 : }
333 :
334 489125 : static uint8_t *hash_key(HashmapBase *h) {
335 489125 : return h->has_indirect ? h->indirect.hash_key
336 489125 : : shared_hash_key;
337 : }
338 :
339 489125 : static unsigned base_bucket_hash(HashmapBase *h, const void *p) {
340 : struct siphash state;
341 : uint64_t hash;
342 :
343 489125 : siphash24_init(&state, hash_key(h));
344 :
345 489125 : h->hash_ops->hash(p, &state);
346 :
347 489125 : hash = siphash24_finalize(&state);
348 :
349 489125 : return (unsigned) (hash % n_buckets(h));
350 : }
351 : #define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p)
352 :
353 258603 : static void base_set_dirty(HashmapBase *h) {
354 258603 : h->dirty = true;
355 258603 : }
356 : #define hashmap_set_dirty(h) base_set_dirty(HASHMAP_BASE(h))
357 :
358 18331 : 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 18331 : if (!current_initialized || !reuse_is_ok) {
370 7797 : random_bytes(current, sizeof(current));
371 7797 : current_initialized = true;
372 : }
373 :
374 18331 : memcpy(hash_key, current, sizeof(current));
375 18331 : }
376 :
377 5166848 : static struct hashmap_base_entry *bucket_at(HashmapBase *h, unsigned idx) {
378 10333696 : return (struct hashmap_base_entry*)
379 5166848 : ((uint8_t*) storage_ptr(h) + idx * hashmap_type_info[h->type].entry_size);
380 : }
381 :
382 2796 : static struct plain_hashmap_entry *plain_bucket_at(Hashmap *h, unsigned idx) {
383 2796 : return (struct plain_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
384 : }
385 :
386 344091 : static struct ordered_hashmap_entry *ordered_bucket_at(OrderedHashmap *h, unsigned idx) {
387 344091 : 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 938481 : static struct ordered_hashmap_entry *bucket_at_swap(struct swap_entries *swap, unsigned idx) {
395 938481 : 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 1733257 : static struct hashmap_base_entry *bucket_at_virtual(HashmapBase *h, struct swap_entries *swap,
401 : unsigned idx) {
402 1733257 : if (idx < _IDX_SWAP_BEGIN)
403 1054398 : return bucket_at(h, idx);
404 :
405 678859 : if (idx < _IDX_SWAP_END)
406 678859 : return &bucket_at_swap(swap, idx)->p.b;
407 :
408 0 : assert_not_reached("Invalid index");
409 : }
410 :
411 2245033 : static dib_raw_t *dib_raw_ptr(HashmapBase *h) {
412 4490066 : return (dib_raw_t*)
413 2245033 : ((uint8_t*) storage_ptr(h) + hashmap_type_info[h->type].entry_size * n_buckets(h));
414 : }
415 :
416 0 : static unsigned bucket_distance(HashmapBase *h, unsigned idx, unsigned from) {
417 : return idx >= from ? idx - from
418 0 : : n_buckets(h) + idx - from;
419 : }
420 :
421 641097 : static unsigned bucket_calculate_dib(HashmapBase *h, unsigned idx, dib_raw_t raw_dib) {
422 : unsigned initial_bucket;
423 :
424 641097 : if (raw_dib == DIB_RAW_FREE)
425 0 : return DIB_FREE;
426 :
427 641097 : if (_likely_(raw_dib < DIB_RAW_OVERFLOW))
428 641097 : 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 0 : initial_bucket = bucket_hash(h, bucket_at(h, idx)->key);
441 0 : return bucket_distance(h, idx, initial_bucket);
442 : }
443 :
444 452959 : static void bucket_set_dib(HashmapBase *h, unsigned idx, unsigned dib) {
445 452959 : dib_raw_ptr(h)[idx] = dib != DIB_FREE ? MIN(dib, DIB_RAW_OVERFLOW) : DIB_RAW_FREE;
446 452959 : }
447 :
448 1084147 : static unsigned skip_free_buckets(HashmapBase *h, unsigned idx) {
449 : dib_raw_t *dibs;
450 :
451 1084147 : dibs = dib_raw_ptr(h);
452 :
453 2073903 : for ( ; idx < n_buckets(h); idx++)
454 2039855 : if (dibs[idx] != DIB_RAW_FREE)
455 1050099 : return idx;
456 :
457 34048 : return IDX_NIL;
458 : }
459 :
460 103699 : static void bucket_mark_free(HashmapBase *h, unsigned idx) {
461 103699 : memzero(bucket_at(h, idx), hashmap_type_info[h->type].entry_size);
462 103699 : bucket_set_dib(h, idx, DIB_FREE);
463 103699 : }
464 :
465 623168 : 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 623168 : assert(from != to);
470 :
471 623168 : e_from = bucket_at_virtual(h, swap, from);
472 623168 : e_to = bucket_at_virtual(h, swap, to);
473 :
474 623168 : memcpy(e_to, e_from, hashmap_type_info[h->type].entry_size);
475 :
476 623168 : if (h->type == HASHMAP_TYPE_ORDERED) {
477 322128 : OrderedHashmap *lh = (OrderedHashmap*) h;
478 : struct ordered_hashmap_entry *le, *le_to;
479 :
480 322128 : le_to = (struct ordered_hashmap_entry*) e_to;
481 :
482 322128 : if (le_to->iterate_next != IDX_NIL) {
483 : le = (struct ordered_hashmap_entry*)
484 217791 : bucket_at_virtual(h, swap, le_to->iterate_next);
485 217791 : le->iterate_previous = to;
486 : }
487 :
488 322128 : if (le_to->iterate_previous != IDX_NIL) {
489 : le = (struct ordered_hashmap_entry*)
490 269130 : bucket_at_virtual(h, swap, le_to->iterate_previous);
491 269130 : le->iterate_next = to;
492 : }
493 :
494 322128 : if (lh->iterate_list_head == from)
495 52998 : lh->iterate_list_head = to;
496 322128 : if (lh->iterate_list_tail == from)
497 104337 : lh->iterate_list_tail = to;
498 : }
499 623168 : }
500 :
501 718754 : static unsigned next_idx(HashmapBase *h, unsigned idx) {
502 718754 : return (idx + 1U) % n_buckets(h);
503 : }
504 :
505 5 : static unsigned prev_idx(HashmapBase *h, unsigned idx) {
506 5 : return (n_buckets(h) + idx - 1U) % n_buckets(h);
507 : }
508 :
509 1218392 : static void *entry_value(HashmapBase *h, struct hashmap_base_entry *e) {
510 1218392 : switch (h->type) {
511 :
512 1182706 : case HASHMAP_TYPE_PLAIN:
513 : case HASHMAP_TYPE_ORDERED:
514 1182706 : return ((struct plain_hashmap_entry*)e)->value;
515 :
516 35686 : case HASHMAP_TYPE_SET:
517 35686 : return (void*) e->key;
518 :
519 0 : default:
520 0 : assert_not_reached("Unknown hashmap type");
521 : }
522 : }
523 :
524 103699 : static void base_remove_entry(HashmapBase *h, unsigned idx) {
525 : unsigned left, right, prev, dib;
526 : dib_raw_t raw_dib, *dibs;
527 :
528 103699 : dibs = dib_raw_ptr(h);
529 103699 : 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 103699 : left = idx;
537 : /* Find the stop bucket ("right"). It is either free or has DIB == 0. */
538 154178 : for (right = next_idx(h, left); ; right = next_idx(h, right)) {
539 50479 : raw_dib = dibs[right];
540 154178 : if (IN_SET(raw_dib, 0, DIB_RAW_FREE))
541 103699 : 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 50479 : assert(left != right);
547 : }
548 :
549 103699 : if (h->type == HASHMAP_TYPE_ORDERED) {
550 68833 : OrderedHashmap *lh = (OrderedHashmap*) h;
551 68833 : struct ordered_hashmap_entry *le = ordered_bucket_at(lh, idx);
552 :
553 68833 : if (le->iterate_next != IDX_NIL)
554 57390 : ordered_bucket_at(lh, le->iterate_next)->iterate_previous = le->iterate_previous;
555 : else
556 11443 : lh->iterate_list_tail = le->iterate_previous;
557 :
558 68833 : if (le->iterate_previous != IDX_NIL)
559 27 : ordered_bucket_at(lh, le->iterate_previous)->iterate_next = le->iterate_next;
560 : else
561 68806 : lh->iterate_list_head = le->iterate_next;
562 : }
563 :
564 : /* Now shift all buckets in the interval (left, right) one step backwards */
565 154178 : for (prev = left, left = next_idx(h, left); left != right;
566 50479 : prev = left, left = next_idx(h, left)) {
567 50479 : dib = bucket_calculate_dib(h, left, dibs[left]);
568 50479 : assert(dib != 0);
569 50479 : bucket_move_entry(h, NULL, left, prev);
570 50479 : bucket_set_dib(h, prev, dib - 1);
571 : }
572 :
573 103699 : bucket_mark_free(h, prev);
574 103699 : n_entries_dec(h);
575 103699 : base_set_dirty(h);
576 103699 : }
577 : #define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)
578 :
579 87809 : static unsigned hashmap_iterate_in_insertion_order(OrderedHashmap *h, Iterator *i) {
580 : struct ordered_hashmap_entry *e;
581 : unsigned idx;
582 :
583 87809 : assert(h);
584 87809 : assert(i);
585 :
586 87809 : if (i->idx == IDX_NIL)
587 1008 : goto at_end;
588 :
589 86801 : if (i->idx == IDX_FIRST && h->iterate_list_head == IDX_NIL)
590 457 : goto at_end;
591 :
592 86344 : if (i->idx == IDX_FIRST) {
593 70010 : idx = h->iterate_list_head;
594 70010 : e = ordered_bucket_at(h, idx);
595 : } else {
596 16334 : idx = i->idx;
597 16334 : 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 16334 : 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 16334 : assert(e->p.b.key == i->next_key);
609 : }
610 :
611 : #if ENABLE_DEBUG_HASHMAP
612 : i->prev_idx = idx;
613 : #endif
614 :
615 86344 : if (e->iterate_next != IDX_NIL) {
616 : struct ordered_hashmap_entry *n;
617 73926 : i->idx = e->iterate_next;
618 73926 : n = ordered_bucket_at(h, i->idx);
619 73926 : i->next_key = n->p.b.key;
620 : } else
621 12418 : i->idx = IDX_NIL;
622 :
623 86344 : return idx;
624 :
625 1465 : at_end:
626 1465 : i->idx = IDX_NIL;
627 1465 : return IDX_NIL;
628 : }
629 :
630 1067519 : static unsigned hashmap_iterate_in_internal_order(HashmapBase *h, Iterator *i) {
631 : unsigned idx;
632 :
633 1067519 : assert(h);
634 1067519 : assert(i);
635 :
636 1067519 : if (i->idx == IDX_NIL)
637 24494 : goto at_end;
638 :
639 1043025 : if (i->idx == IDX_FIRST) {
640 : /* fast forward to the first occupied bucket */
641 42690 : if (h->has_indirect) {
642 10241 : i->idx = skip_free_buckets(h, h->indirect.idx_lowest_entry);
643 10241 : h->indirect.idx_lowest_entry = i->idx;
644 : } else
645 32449 : i->idx = skip_free_buckets(h, 0);
646 :
647 42690 : if (i->idx == IDX_NIL)
648 1568 : goto at_end;
649 : } else {
650 : struct hashmap_base_entry *e;
651 :
652 1000335 : assert(i->idx > 0);
653 :
654 1000335 : 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 1000335 : if (e->key != i->next_key)
662 0 : e = bucket_at(h, --i->idx);
663 :
664 1000335 : assert(e->key == i->next_key);
665 : }
666 :
667 1041457 : idx = i->idx;
668 : #if ENABLE_DEBUG_HASHMAP
669 : i->prev_idx = idx;
670 : #endif
671 :
672 1041457 : i->idx = skip_free_buckets(h, i->idx + 1);
673 1041457 : if (i->idx != IDX_NIL)
674 1008977 : i->next_key = bucket_at(h, i->idx)->key;
675 : else
676 32480 : i->idx = IDX_NIL;
677 :
678 1041457 : return idx;
679 :
680 26062 : at_end:
681 26062 : i->idx = IDX_NIL;
682 26062 : return IDX_NIL;
683 : }
684 :
685 1328951 : static unsigned hashmap_iterate_entry(HashmapBase *h, Iterator *i) {
686 1328951 : if (!h) {
687 173623 : i->idx = IDX_NIL;
688 173623 : 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 87809 : return h->type == HASHMAP_TYPE_ORDERED ? hashmap_iterate_in_insertion_order((OrderedHashmap*) h, i)
708 1243137 : : hashmap_iterate_in_internal_order(h, i);
709 : }
710 :
711 749447 : 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 749447 : idx = hashmap_iterate_entry(h, i);
717 749447 : if (idx == IDX_NIL) {
718 200031 : if (value)
719 200031 : *value = NULL;
720 200031 : if (key)
721 110098 : *key = NULL;
722 :
723 200031 : return false;
724 : }
725 :
726 549416 : e = bucket_at(h, idx);
727 549416 : data = entry_value(h, e);
728 549416 : if (value)
729 549416 : *value = data;
730 549416 : if (key)
731 512273 : *key = e->key;
732 :
733 549416 : return true;
734 : }
735 :
736 111487 : bool set_iterate(const Set *s, Iterator *i, void **value) {
737 111487 : 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 213 : IteratedCache *internal_hashmap_iterated_cache_new(HashmapBase *h) {
746 : IteratedCache *cache;
747 :
748 213 : assert(h);
749 213 : assert(!h->cached);
750 :
751 213 : if (h->cached)
752 0 : return NULL;
753 :
754 213 : cache = new0(IteratedCache, 1);
755 213 : if (!cache)
756 0 : return NULL;
757 :
758 213 : cache->hashmap = h;
759 213 : h->cached = true;
760 :
761 213 : return cache;
762 : }
763 :
764 67698 : static void reset_direct_storage(HashmapBase *h) {
765 67698 : const struct hashmap_type_info *hi = &hashmap_type_info[h->type];
766 : void *p;
767 :
768 67698 : assert(!h->has_indirect);
769 :
770 67698 : p = mempset(h->direct.storage, 0, hi->entry_size * hi->n_direct_buckets);
771 67698 : memset(p, DIB_RAW_INIT, sizeof(dib_raw_t) * hi->n_direct_buckets);
772 67698 : }
773 :
774 33819 : static struct HashmapBase *hashmap_base_new(const struct hash_ops *hash_ops, enum HashmapType type HASHMAP_DEBUG_PARAMS) {
775 : HashmapBase *h;
776 33819 : const struct hashmap_type_info *hi = &hashmap_type_info[type];
777 : bool up;
778 :
779 33819 : up = mempool_enabled();
780 :
781 33819 : h = up ? mempool_alloc0_tile(hi->mempool) : malloc0(hi->head_size);
782 33819 : if (!h)
783 0 : return NULL;
784 :
785 33819 : h->type = type;
786 33819 : h->from_pool = up;
787 33819 : h->hash_ops = hash_ops ?: &trivial_hash_ops;
788 :
789 33819 : if (type == HASHMAP_TYPE_ORDERED) {
790 21476 : OrderedHashmap *lh = (OrderedHashmap*)h;
791 21476 : lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;
792 : }
793 :
794 33819 : reset_direct_storage(h);
795 :
796 33819 : if (!shared_hash_key_initialized) {
797 175 : random_bytes(shared_hash_key, sizeof(shared_hash_key));
798 175 : 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 33819 : return h;
811 : }
812 :
813 1460 : Hashmap *internal_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
814 1460 : return (Hashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
815 : }
816 :
817 10262 : OrderedHashmap *internal_ordered_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
818 10262 : return (OrderedHashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
819 : }
820 :
821 5493 : Set *internal_set_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
822 5493 : return (Set*) hashmap_base_new(hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
823 : }
824 :
825 83471 : 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 83471 : assert(h);
830 :
831 83471 : if (*h)
832 66869 : return 0;
833 :
834 16602 : q = hashmap_base_new(hash_ops, type HASHMAP_DEBUG_PASS_ARGS);
835 16602 : if (!q)
836 0 : return -ENOMEM;
837 :
838 16602 : *h = q;
839 16602 : return 0;
840 : }
841 :
842 22541 : int internal_hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
843 22541 : return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
844 : }
845 :
846 58164 : int internal_ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
847 58164 : return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
848 : }
849 :
850 2766 : int internal_set_ensure_allocated(Set **s, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
851 2766 : return hashmap_base_ensure_allocated((HashmapBase**)s, hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
852 : }
853 :
854 33818 : static void hashmap_free_no_clear(HashmapBase *h) {
855 33818 : assert(!h->has_indirect);
856 33818 : 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 33818 : if (h->from_pool) {
865 : /* Ensure that the object didn't get migrated between threads. */
866 33789 : assert_se(is_main_thread());
867 33789 : mempool_free_tile(hashmap_type_info[h->type].mempool, h);
868 : } else
869 29 : free(h);
870 33818 : }
871 :
872 140695 : HashmapBase *internal_hashmap_free(HashmapBase *h, free_func_t default_free_key, free_func_t default_free_value) {
873 140695 : if (h) {
874 33818 : internal_hashmap_clear(h, default_free_key, default_free_value);
875 33818 : hashmap_free_no_clear(h);
876 : }
877 :
878 140695 : return NULL;
879 : }
880 :
881 33882 : 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 33882 : if (!h)
884 3 : return;
885 :
886 33879 : free_key = h->hash_ops->free_key ?: default_free_key;
887 33879 : free_value = h->hash_ops->free_value ?: default_free_value;
888 :
889 33879 : 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 94302 : while (internal_hashmap_size(h) > 0) {
896 66532 : void *k = NULL;
897 : void *v;
898 :
899 66532 : v = internal_hashmap_first_key_and_value(h, true, &k);
900 :
901 66532 : if (free_key)
902 66279 : free_key(k);
903 :
904 66532 : if (free_value)
905 61065 : free_value(v);
906 : }
907 : }
908 :
909 33879 : if (h->has_indirect) {
910 10583 : free(h->indirect.storage);
911 10583 : h->has_indirect = false;
912 : }
913 :
914 33879 : h->n_direct_entries = 0;
915 33879 : reset_direct_storage(h);
916 :
917 33879 : if (h->type == HASHMAP_TYPE_ORDERED) {
918 21501 : OrderedHashmap *lh = (OrderedHashmap*) h;
919 21501 : lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;
920 : }
921 :
922 33879 : 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 225427 : 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 225427 : dibs = dib_raw_ptr(h);
946 :
947 225427 : for (distance = 0; ; distance++) {
948 191128 : raw_dib = dibs[idx];
949 416555 : if (IN_SET(raw_dib, DIB_RAW_FREE, DIB_RAW_REHASH)) {
950 225427 : if (raw_dib == DIB_RAW_REHASH)
951 21056 : bucket_move_entry(h, swap, idx, IDX_TMP);
952 :
953 225427 : if (h->has_indirect && h->indirect.idx_lowest_entry > idx)
954 33 : h->indirect.idx_lowest_entry = idx;
955 :
956 225427 : bucket_set_dib(h, idx, distance);
957 225427 : bucket_move_entry(h, swap, IDX_PUT, idx);
958 225427 : if (raw_dib == DIB_RAW_REHASH) {
959 21056 : bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
960 21056 : return true;
961 : }
962 :
963 204371 : return false;
964 : }
965 :
966 191128 : dib = bucket_calculate_dib(h, idx, raw_dib);
967 :
968 191128 : if (dib < distance) {
969 : /* Found a wealthier entry. Go Robin Hood! */
970 73354 : bucket_set_dib(h, idx, distance);
971 :
972 : /* swap the entries */
973 73354 : bucket_move_entry(h, swap, idx, IDX_TMP);
974 73354 : bucket_move_entry(h, swap, IDX_PUT, idx);
975 73354 : bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
976 :
977 73354 : distance = dib;
978 : }
979 :
980 191128 : 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 119283 : 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 119283 : assert(idx < n_buckets(h));
1000 :
1001 119283 : new_entry = bucket_at_swap(swap, IDX_PUT);
1002 :
1003 119283 : if (may_resize) {
1004 118345 : r = resize_buckets(h, 1);
1005 118345 : if (r < 0)
1006 0 : return r;
1007 118345 : if (r > 0)
1008 18327 : idx = bucket_hash(h, new_entry->p.b.key);
1009 : }
1010 119283 : assert(n_entries(h) < n_buckets(h));
1011 :
1012 119283 : if (h->type == HASHMAP_TYPE_ORDERED) {
1013 69037 : OrderedHashmap *lh = (OrderedHashmap*) h;
1014 :
1015 69037 : new_entry->iterate_next = IDX_NIL;
1016 69037 : new_entry->iterate_previous = lh->iterate_list_tail;
1017 :
1018 69037 : if (lh->iterate_list_tail != IDX_NIL) {
1019 : struct ordered_hashmap_entry *old_tail;
1020 :
1021 57557 : old_tail = ordered_bucket_at(lh, lh->iterate_list_tail);
1022 57557 : assert(old_tail->iterate_next == IDX_NIL);
1023 57557 : old_tail->iterate_next = IDX_PUT;
1024 : }
1025 :
1026 69037 : lh->iterate_list_tail = IDX_PUT;
1027 69037 : if (lh->iterate_list_head == IDX_NIL)
1028 11480 : lh->iterate_list_head = IDX_PUT;
1029 : }
1030 :
1031 119283 : assert_se(hashmap_put_robin_hood(h, idx, swap) == false);
1032 :
1033 119283 : 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 119283 : base_set_dirty(h);
1039 :
1040 119283 : 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 118382 : 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 118382 : assert(h);
1061 :
1062 118382 : hi = &hashmap_type_info[h->type];
1063 118382 : new_n_entries = n_entries(h) + entries_add;
1064 :
1065 : /* overflow? */
1066 118382 : if (_unlikely_(new_n_entries < entries_add))
1067 2 : return -ENOMEM;
1068 :
1069 : /* For direct storage we allow 100% load, because it's tiny. */
1070 118380 : if (!h->has_indirect && new_n_entries <= hi->n_direct_buckets)
1071 26253 : 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 92127 : new_n_buckets = new_n_entries + new_n_entries / (INV_KEEP_FREE - 1);
1078 : /* overflow? */
1079 92127 : if (_unlikely_(new_n_buckets < new_n_entries))
1080 2 : return -ENOMEM;
1081 :
1082 92125 : if (_unlikely_(new_n_buckets > UINT_MAX / (hi->entry_size + sizeof(dib_raw_t))))
1083 0 : return -ENOMEM;
1084 :
1085 92125 : old_n_buckets = n_buckets(h);
1086 :
1087 92125 : if (_likely_(new_n_buckets <= old_n_buckets))
1088 73794 : return 0;
1089 :
1090 18331 : 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 18331 : new_storage = realloc(h->has_indirect ? h->indirect.storage : NULL,
1096 18331 : 1U << new_shift);
1097 18331 : if (!new_storage)
1098 0 : return -ENOMEM;
1099 :
1100 : /* Must upgrade direct to indirect storage. */
1101 18331 : if (!h->has_indirect) {
1102 21166 : memcpy(new_storage, h->direct.storage,
1103 10583 : old_n_buckets * (hi->entry_size + sizeof(dib_raw_t)));
1104 10583 : h->indirect.n_entries = h->n_direct_entries;
1105 10583 : h->indirect.idx_lowest_entry = 0;
1106 10583 : 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 18331 : get_hash_key(h->indirect.hash_key, !h->has_indirect);
1113 :
1114 18331 : h->has_indirect = true;
1115 18331 : h->indirect.storage = new_storage;
1116 36662 : h->indirect.n_buckets = (1U << new_shift) /
1117 18331 : (hi->entry_size + sizeof(dib_raw_t));
1118 :
1119 18331 : old_dibs = (dib_raw_t*)((uint8_t*) new_storage + hi->entry_size * old_n_buckets);
1120 18331 : 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 152867 : for (idx = 0; idx < old_n_buckets; idx++) {
1129 134536 : assert(old_dibs[idx] != DIB_RAW_REHASH);
1130 134536 : 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 18331 : 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 18331 : memset(&new_dibs[old_n_buckets], DIB_RAW_INIT,
1140 18331 : (n_buckets(h) - old_n_buckets) * sizeof(dib_raw_t));
1141 :
1142 : /* Rehash entries that need it */
1143 18331 : n_rehashed = 0;
1144 152867 : for (idx = 0; idx < old_n_buckets; idx++) {
1145 134536 : if (new_dibs[idx] != DIB_RAW_REHASH)
1146 45264 : continue;
1147 :
1148 89272 : 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 89272 : if (optimal_idx == idx) {
1155 4184 : new_dibs[idx] = 0;
1156 4184 : n_rehashed++;
1157 4184 : continue;
1158 : }
1159 :
1160 85088 : new_dibs[idx] = DIB_RAW_FREE;
1161 85088 : bucket_move_entry(h, &swap, idx, IDX_PUT);
1162 : /* bucket_move_entry does not clear the source */
1163 85088 : 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 106144 : rehash_next = hashmap_put_robin_hood(h, optimal_idx, &swap);
1171 106144 : n_rehashed++;
1172 :
1173 : /* Did the current entry displace another one? */
1174 106144 : if (rehash_next)
1175 21056 : optimal_idx = bucket_hash(h, bucket_at_swap(&swap, IDX_PUT)->p.b.key);
1176 106144 : } while (rehash_next);
1177 : }
1178 :
1179 18331 : assert(n_rehashed == n_entries(h));
1180 :
1181 18331 : 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 360470 : static unsigned base_bucket_scan(HashmapBase *h, unsigned idx, const void *key) {
1189 : struct hashmap_base_entry *e;
1190 : unsigned dib, distance;
1191 360470 : dib_raw_t *dibs = dib_raw_ptr(h);
1192 :
1193 360470 : assert(idx < n_buckets(h));
1194 :
1195 360470 : for (distance = 0; ; distance++) {
1196 579740 : if (dibs[idx] == DIB_RAW_FREE)
1197 180250 : return IDX_NIL;
1198 :
1199 399490 : dib = bucket_calculate_dib(h, idx, dibs[idx]);
1200 :
1201 399490 : if (dib < distance)
1202 83556 : return IDX_NIL;
1203 315934 : if (dib == distance) {
1204 240369 : e = bucket_at(h, idx);
1205 240369 : if (h->hash_ops->compare(e->key, key) == 0)
1206 96664 : return idx;
1207 : }
1208 :
1209 219270 : idx = next_idx(h, idx);
1210 : }
1211 : }
1212 : #define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
1213 :
1214 47271 : 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 47271 : assert(h);
1220 :
1221 47271 : hash = bucket_hash(h, key);
1222 47271 : idx = bucket_scan(h, hash, key);
1223 47271 : if (idx != IDX_NIL) {
1224 18 : e = plain_bucket_at(h, idx);
1225 18 : if (e->value == value)
1226 7 : return 0;
1227 11 : return -EEXIST;
1228 : }
1229 :
1230 47253 : e = &bucket_at_swap(&swap, IDX_PUT)->p;
1231 47253 : e->b.key = key;
1232 47253 : e->value = value;
1233 47253 : return hashmap_put_boldly(h, hash, &swap, true);
1234 : }
1235 :
1236 13500 : 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 13500 : assert(s);
1242 :
1243 13500 : hash = bucket_hash(s, key);
1244 13500 : idx = bucket_scan(s, hash, key);
1245 13500 : if (idx != IDX_NIL)
1246 89 : return 0;
1247 :
1248 13411 : e = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1249 13411 : e->key = key;
1250 13411 : return hashmap_put_boldly(s, hash, &swap, true);
1251 : }
1252 :
1253 59091 : 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 59091 : assert(h);
1259 :
1260 59091 : hash = bucket_hash(h, key);
1261 59091 : idx = bucket_scan(h, hash, key);
1262 59091 : if (idx != IDX_NIL) {
1263 1488 : 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 1488 : e->b.key = key;
1275 1488 : e->value = value;
1276 1488 : hashmap_set_dirty(h);
1277 :
1278 1488 : return 0;
1279 : }
1280 :
1281 57603 : e = &bucket_at_swap(&swap, IDX_PUT)->p;
1282 57603 : e->b.key = key;
1283 57603 : e->value = value;
1284 57603 : return hashmap_put_boldly(h, hash, &swap, true);
1285 : }
1286 :
1287 256 : int hashmap_update(Hashmap *h, const void *key, void *value) {
1288 : struct plain_hashmap_entry *e;
1289 : unsigned hash, idx;
1290 :
1291 256 : assert(h);
1292 :
1293 256 : hash = bucket_hash(h, key);
1294 256 : idx = bucket_scan(h, hash, key);
1295 256 : if (idx == IDX_NIL)
1296 2 : return -ENOENT;
1297 :
1298 254 : e = plain_bucket_at(h, idx);
1299 254 : e->value = value;
1300 254 : hashmap_set_dirty(h);
1301 :
1302 254 : return 0;
1303 : }
1304 :
1305 138922 : void *internal_hashmap_get(HashmapBase *h, const void *key) {
1306 : struct hashmap_base_entry *e;
1307 : unsigned hash, idx;
1308 :
1309 138922 : if (!h)
1310 2516 : return NULL;
1311 :
1312 136406 : hash = bucket_hash(h, key);
1313 136406 : idx = bucket_scan(h, hash, key);
1314 136406 : if (idx == IDX_NIL)
1315 66668 : return NULL;
1316 :
1317 69738 : e = bucket_at(h, idx);
1318 69738 : return entry_value(h, e);
1319 : }
1320 :
1321 58915 : void *hashmap_get2(Hashmap *h, const void *key, void **key2) {
1322 : struct plain_hashmap_entry *e;
1323 : unsigned hash, idx;
1324 :
1325 58915 : if (!h)
1326 1129 : return NULL;
1327 :
1328 57786 : hash = bucket_hash(h, key);
1329 57786 : idx = bucket_scan(h, hash, key);
1330 57786 : if (idx == IDX_NIL)
1331 56764 : return NULL;
1332 :
1333 1022 : e = plain_bucket_at(h, idx);
1334 1022 : if (key2)
1335 1022 : *key2 = (void*) e->b.key;
1336 :
1337 1022 : return e->value;
1338 : }
1339 :
1340 14261 : bool internal_hashmap_contains(HashmapBase *h, const void *key) {
1341 : unsigned hash;
1342 :
1343 14261 : if (!h)
1344 14 : return false;
1345 :
1346 14247 : hash = bucket_hash(h, key);
1347 14247 : return bucket_scan(h, hash, key) != IDX_NIL;
1348 : }
1349 :
1350 70149 : void *internal_hashmap_remove(HashmapBase *h, const void *key) {
1351 : struct hashmap_base_entry *e;
1352 : unsigned hash, idx;
1353 : void *data;
1354 :
1355 70149 : if (!h)
1356 45606 : return NULL;
1357 :
1358 24543 : hash = bucket_hash(h, key);
1359 24543 : idx = bucket_scan(h, hash, key);
1360 24543 : if (idx == IDX_NIL)
1361 7504 : return NULL;
1362 :
1363 17039 : e = bucket_at(h, idx);
1364 17039 : data = entry_value(h, e);
1365 17039 : remove_entry(h, idx);
1366 :
1367 17039 : return data;
1368 : }
1369 :
1370 1458 : 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 1458 : if (!h) {
1376 53 : if (rkey)
1377 53 : *rkey = NULL;
1378 53 : return NULL;
1379 : }
1380 :
1381 1405 : hash = bucket_hash(h, key);
1382 1405 : idx = bucket_scan(h, hash, key);
1383 1405 : if (idx == IDX_NIL) {
1384 1403 : if (rkey)
1385 1403 : *rkey = NULL;
1386 1403 : return NULL;
1387 : }
1388 :
1389 2 : e = plain_bucket_at(h, idx);
1390 2 : data = e->value;
1391 2 : if (rkey)
1392 2 : *rkey = (void*) e->b.key;
1393 :
1394 2 : remove_entry(h, idx);
1395 :
1396 2 : return data;
1397 : }
1398 :
1399 8 : 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 8 : if (!h)
1405 2 : return -ENOENT;
1406 :
1407 6 : old_hash = bucket_hash(h, old_key);
1408 6 : idx = bucket_scan(h, old_hash, old_key);
1409 6 : if (idx == IDX_NIL)
1410 2 : return -ENOENT;
1411 :
1412 4 : new_hash = bucket_hash(h, new_key);
1413 4 : if (bucket_scan(h, new_hash, new_key) != IDX_NIL)
1414 2 : return -EEXIST;
1415 :
1416 2 : remove_entry(h, idx);
1417 :
1418 2 : e = &bucket_at_swap(&swap, IDX_PUT)->p;
1419 2 : e->b.key = new_key;
1420 2 : e->value = value;
1421 2 : assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
1422 :
1423 2 : 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 917 : 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 917 : if (!h)
1458 2 : return -ENOENT;
1459 :
1460 915 : old_hash = bucket_hash(h, old_key);
1461 915 : idx_old = bucket_scan(h, old_hash, old_key);
1462 915 : if (idx_old == IDX_NIL)
1463 2 : return -ENOENT;
1464 :
1465 913 : old_key = bucket_at(HASHMAP_BASE(h), idx_old)->key;
1466 :
1467 913 : new_hash = bucket_hash(h, new_key);
1468 913 : idx_new = bucket_scan(h, new_hash, new_key);
1469 913 : if (idx_new != IDX_NIL)
1470 911 : if (idx_old != idx_new) {
1471 42 : remove_entry(h, idx_new);
1472 : /* Compensate for a possible backward shift. */
1473 42 : if (old_key != bucket_at(HASHMAP_BASE(h), idx_old)->key)
1474 5 : idx_old = prev_idx(HASHMAP_BASE(h), idx_old);
1475 42 : assert(old_key == bucket_at(HASHMAP_BASE(h), idx_old)->key);
1476 : }
1477 :
1478 913 : remove_entry(h, idx_old);
1479 :
1480 913 : e = &bucket_at_swap(&swap, IDX_PUT)->p;
1481 913 : e->b.key = new_key;
1482 913 : e->value = value;
1483 913 : assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
1484 :
1485 913 : return 0;
1486 : }
1487 :
1488 3931 : void *internal_hashmap_remove_value(HashmapBase *h, const void *key, void *value) {
1489 : struct hashmap_base_entry *e;
1490 : unsigned hash, idx;
1491 :
1492 3931 : if (!h)
1493 2 : return NULL;
1494 :
1495 3929 : hash = bucket_hash(h, key);
1496 3929 : idx = bucket_scan(h, hash, key);
1497 3929 : if (idx == IDX_NIL)
1498 78 : return NULL;
1499 :
1500 3851 : e = bucket_at(h, idx);
1501 3851 : if (entry_value(h, e) != value)
1502 2 : return NULL;
1503 :
1504 3849 : remove_entry(h, idx);
1505 :
1506 3849 : return value;
1507 : }
1508 :
1509 110869 : static unsigned find_first_entry(HashmapBase *h) {
1510 110869 : Iterator i = ITERATOR_FIRST;
1511 :
1512 110869 : if (!h || !n_entries(h))
1513 25718 : return IDX_NIL;
1514 :
1515 85151 : return hashmap_iterate_entry(h, &i);
1516 : }
1517 :
1518 110869 : 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 110869 : idx = find_first_entry(h);
1524 110869 : if (idx == IDX_NIL) {
1525 25718 : if (ret_key)
1526 3425 : *ret_key = NULL;
1527 25718 : return NULL;
1528 : }
1529 :
1530 85151 : e = bucket_at(h, idx);
1531 85151 : key = (void*) e->key;
1532 85151 : data = entry_value(h, e);
1533 :
1534 85151 : if (remove)
1535 81751 : remove_entry(h, idx);
1536 :
1537 85151 : if (ret_key)
1538 67633 : *ret_key = key;
1539 :
1540 85151 : return data;
1541 : }
1542 :
1543 155695 : unsigned internal_hashmap_size(HashmapBase *h) {
1544 155695 : if (!h)
1545 36796 : return 0;
1546 :
1547 118899 : return n_entries(h);
1548 : }
1549 :
1550 20 : unsigned internal_hashmap_buckets(HashmapBase *h) {
1551 20 : if (!h)
1552 2 : return 0;
1553 :
1554 18 : return n_buckets(h);
1555 : }
1556 :
1557 4 : int internal_hashmap_merge(Hashmap *h, Hashmap *other) {
1558 : Iterator i;
1559 : unsigned idx;
1560 :
1561 4 : assert(h);
1562 :
1563 16 : HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1564 12 : struct plain_hashmap_entry *pe = plain_bucket_at(other, idx);
1565 : int r;
1566 :
1567 12 : r = hashmap_put(h, pe->b.key, pe->value);
1568 12 : if (r < 0 && r != -EEXIST)
1569 0 : return r;
1570 : }
1571 :
1572 4 : 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 8 : int internal_hashmap_reserve(HashmapBase *h, unsigned entries_add) {
1594 : int r;
1595 :
1596 8 : assert(h);
1597 :
1598 8 : r = resize_buckets(h, entries_add);
1599 8 : if (r < 0)
1600 4 : return r;
1601 :
1602 4 : 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 31 : 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 31 : assert(h);
1619 :
1620 31 : if (!other)
1621 2 : return 0;
1622 :
1623 29 : 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 29 : r = resize_buckets(h, n_entries(other));
1632 29 : if (r < 0)
1633 0 : return r;
1634 :
1635 54 : HASHMAP_FOREACH_IDX(idx, other, i) {
1636 : unsigned h_hash;
1637 :
1638 25 : e = bucket_at(other, idx);
1639 25 : h_hash = bucket_hash(h, e->key);
1640 25 : if (bucket_scan(h, h_hash, e->key) != IDX_NIL)
1641 2 : continue;
1642 :
1643 23 : n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1644 23 : n->key = e->key;
1645 23 : if (h->type != HASHMAP_TYPE_SET)
1646 6 : ((struct plain_hashmap_entry*) n)->value =
1647 6 : ((struct plain_hashmap_entry*) e)->value;
1648 23 : assert_se(hashmap_put_boldly(h, h_hash, &swap, false) == 1);
1649 :
1650 23 : remove_entry(other, idx);
1651 : }
1652 :
1653 29 : return 0;
1654 : }
1655 :
1656 84 : 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 84 : assert(h);
1663 :
1664 84 : h_hash = bucket_hash(h, key);
1665 84 : if (bucket_scan(h, h_hash, key) != IDX_NIL)
1666 2 : return -EEXIST;
1667 :
1668 82 : if (!other)
1669 2 : return -ENOENT;
1670 :
1671 80 : assert(other->type == h->type);
1672 :
1673 80 : other_hash = bucket_hash(other, key);
1674 80 : idx = bucket_scan(other, other_hash, key);
1675 80 : if (idx == IDX_NIL)
1676 2 : return -ENOENT;
1677 :
1678 78 : e = bucket_at(other, idx);
1679 :
1680 78 : n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1681 78 : n->key = e->key;
1682 78 : if (h->type != HASHMAP_TYPE_SET)
1683 78 : ((struct plain_hashmap_entry*) n)->value =
1684 78 : ((struct plain_hashmap_entry*) e)->value;
1685 78 : r = hashmap_put_boldly(h, h_hash, &swap, true);
1686 78 : if (r < 0)
1687 0 : return r;
1688 :
1689 78 : remove_entry(other, idx);
1690 78 : return 0;
1691 : }
1692 :
1693 2 : HashmapBase *internal_hashmap_copy(HashmapBase *h) {
1694 : HashmapBase *copy;
1695 : int r;
1696 :
1697 2 : assert(h);
1698 :
1699 2 : copy = hashmap_base_new(h->hash_ops, h->type HASHMAP_DEBUG_SRC_ARGS);
1700 2 : if (!copy)
1701 0 : return NULL;
1702 :
1703 2 : switch (h->type) {
1704 2 : case HASHMAP_TYPE_PLAIN:
1705 : case HASHMAP_TYPE_ORDERED:
1706 2 : r = hashmap_merge((Hashmap*)copy, (Hashmap*)h);
1707 2 : 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 2 : if (r < 0) {
1716 0 : internal_hashmap_free(copy, false, false);
1717 0 : return NULL;
1718 : }
1719 :
1720 2 : return copy;
1721 : }
1722 :
1723 963 : char **internal_hashmap_get_strv(HashmapBase *h) {
1724 : char **sv;
1725 : Iterator i;
1726 : unsigned idx, n;
1727 :
1728 963 : sv = new(char*, n_entries(h)+1);
1729 963 : if (!sv)
1730 0 : return NULL;
1731 :
1732 963 : n = 0;
1733 2445 : HASHMAP_FOREACH_IDX(idx, h, i)
1734 1482 : sv[n++] = entry_value(h, bucket_at(h, idx));
1735 963 : sv[n] = NULL;
1736 :
1737 963 : return sv;
1738 : }
1739 :
1740 10 : void *ordered_hashmap_next(OrderedHashmap *h, const void *key) {
1741 : struct ordered_hashmap_entry *e;
1742 : unsigned hash, idx;
1743 :
1744 10 : if (!h)
1745 1 : return NULL;
1746 :
1747 9 : hash = bucket_hash(h, key);
1748 9 : idx = bucket_scan(h, hash, key);
1749 9 : if (idx == IDX_NIL)
1750 1 : return NULL;
1751 :
1752 8 : e = ordered_bucket_at(h, idx);
1753 8 : if (e->iterate_next == IDX_NIL)
1754 2 : return NULL;
1755 6 : return ordered_bucket_at(h, e->iterate_next)->p.value;
1756 : }
1757 :
1758 7885 : int set_consume(Set *s, void *value) {
1759 : int r;
1760 :
1761 7885 : assert(s);
1762 7885 : assert(value);
1763 :
1764 7885 : r = set_put(s, value);
1765 7885 : if (r <= 0)
1766 59 : free(value);
1767 :
1768 7885 : return r;
1769 : }
1770 :
1771 825 : int hashmap_put_strdup(Hashmap **h, const char *k, const char *v) {
1772 : int r;
1773 :
1774 825 : r = hashmap_ensure_allocated(h, &string_hash_ops_free_free);
1775 825 : if (r < 0)
1776 0 : return r;
1777 :
1778 825 : _cleanup_free_ char *kdup = NULL, *vdup = NULL;
1779 825 : kdup = strdup(k);
1780 825 : vdup = strdup(v);
1781 825 : if (!kdup || !vdup)
1782 0 : return -ENOMEM;
1783 :
1784 825 : r = hashmap_put(*h, kdup, vdup);
1785 825 : 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 825 : assert(r > 0); /* 0 would mean vdup is already in the hashmap, which cannot be */
1792 825 : kdup = vdup = NULL;
1793 :
1794 825 : return 0;
1795 : }
1796 :
1797 4876 : int set_put_strdup(Set *s, const char *p) {
1798 : char *c;
1799 :
1800 4876 : assert(s);
1801 4876 : assert(p);
1802 :
1803 4876 : if (set_contains(s, (char*) p))
1804 88 : return 0;
1805 :
1806 4788 : c = strdup(p);
1807 4788 : if (!c)
1808 0 : return -ENOMEM;
1809 :
1810 4788 : 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 10613 : static int cachemem_maintain(CacheMem *mem, unsigned size) {
1852 10613 : assert(mem);
1853 :
1854 10613 : if (!GREEDY_REALLOC(mem->ptr, mem->n_allocated, size)) {
1855 2 : if (size > 0)
1856 0 : return -ENOMEM;
1857 : }
1858 :
1859 10613 : if (!mem->active) {
1860 13 : mem->active = true;
1861 13 : return true;
1862 : }
1863 :
1864 10600 : return false;
1865 : }
1866 :
1867 10501 : int iterated_cache_get(IteratedCache *cache, const void ***res_keys, const void ***res_values, unsigned *res_n_entries) {
1868 10501 : bool sync_keys = false, sync_values = false;
1869 : unsigned size;
1870 : int r;
1871 :
1872 10501 : assert(cache);
1873 10501 : assert(cache->hashmap);
1874 :
1875 10501 : size = n_entries(cache->hashmap);
1876 :
1877 10501 : if (res_keys) {
1878 112 : r = cachemem_maintain(&cache->keys, size);
1879 112 : if (r < 0)
1880 0 : return r;
1881 :
1882 112 : sync_keys = r;
1883 : } else
1884 10389 : cache->keys.active = false;
1885 :
1886 10501 : if (res_values) {
1887 10501 : r = cachemem_maintain(&cache->values, size);
1888 10501 : if (r < 0)
1889 0 : return r;
1890 :
1891 10501 : sync_values = r;
1892 : } else
1893 0 : cache->values.active = false;
1894 :
1895 10501 : if (cache->hashmap->dirty) {
1896 122 : if (cache->keys.active)
1897 111 : sync_keys = true;
1898 122 : if (cache->values.active)
1899 122 : sync_values = true;
1900 :
1901 122 : cache->hashmap->dirty = false;
1902 : }
1903 :
1904 10501 : if (sync_keys || sync_values) {
1905 : unsigned i, idx;
1906 : Iterator iter;
1907 :
1908 123 : i = 0;
1909 491838 : HASHMAP_FOREACH_IDX(idx, cache->hashmap, iter) {
1910 : struct hashmap_base_entry *e;
1911 :
1912 491715 : e = bucket_at(cache->hashmap, idx);
1913 :
1914 491715 : if (sync_keys)
1915 491500 : cache->keys.ptr[i] = e->key;
1916 491715 : if (sync_values)
1917 491715 : cache->values.ptr[i] = entry_value(cache->hashmap, e);
1918 491715 : i++;
1919 : }
1920 : }
1921 :
1922 10501 : if (res_keys)
1923 112 : *res_keys = cache->keys.ptr;
1924 10501 : if (res_values)
1925 10501 : *res_values = cache->values.ptr;
1926 10501 : if (res_n_entries)
1927 10501 : *res_n_entries = size;
1928 :
1929 10501 : return 0;
1930 : }
1931 :
1932 213 : IteratedCache *iterated_cache_free(IteratedCache *cache) {
1933 213 : if (cache) {
1934 213 : free(cache->keys.ptr);
1935 213 : free(cache->values.ptr);
1936 : }
1937 :
1938 213 : return mfree(cache);
1939 : }
|
