]> git.ipfire.org Git - thirdparty/systemd.git/blame_incremental - src/basic/hashmap.c
projects / thirdparty / systemd.git / blame_incremental
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (non-incremental) | history | HEAD
hwdb: add Blue Microphones Yeti X (#43363)
[thirdparty/systemd.git] / src / basic / hashmap.c
... / ...
CommitLineData
1/* SPDX-License-Identifier: LGPL-2.1-or-later */
2
3#include <fnmatch.h>
4#include <pthread.h>
5#include <unistd.h>
6#if HAVE_VALGRIND_VALGRIND_H
7# include <valgrind/valgrind.h>
8#endif
9
10#include "alloc-util.h"
11#include "extract-word.h"
12#include "hashmap.h"
13#include "log.h"
14#include "logarithm.h"
15#include "memory-util.h"
16#include "mempool.h"
17#include "process-util.h"
18#include "random-util.h"
19#include "set.h"
20#include "siphash24.h"
21#include "sort-util.h"
22#include "string-util.h"
23#include "strv.h"
24
25#if ENABLE_DEBUG_HASHMAP
26#include "list.h"
27#endif
28
29/*
30 * Implementation of hashmaps.
31 * Addressing: open
32 * - uses less RAM compared to closed addressing (chaining), because
33 * our entries are small (especially in Sets, which tend to contain
34 * the majority of entries in systemd).
35 * Collision resolution: Robin Hood
36 * - tends to equalize displacement of entries from their optimal buckets.
37 * Probe sequence: linear
38 * - though theoretically worse than random probing/uniform hashing/double
39 * hashing, it is good for cache locality.
40 *
41 * References:
42 * Celis, P. 1986. Robin Hood Hashing.
43 * Ph.D. Dissertation. University of Waterloo, Waterloo, Ont., Canada, Canada.
44 * https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
45 * - The results are derived for random probing. Suggests deletion with
46 * tombstones and two mean-centered search methods. None of that works
47 * well for linear probing.
48 *
49 * Janson, S. 2005. Individual displacements for linear probing hashing with different insertion policies.
50 * ACM Trans. Algorithms 1, 2 (October 2005), 177-213.
51 * DOI=10.1145/1103963.1103964 http://doi.acm.org/10.1145/1103963.1103964
52 * http://www.math.uu.se/~svante/papers/sj157.pdf
53 * - Applies to Robin Hood with linear probing. Contains remarks on
54 * the unsuitability of mean-centered search with linear probing.
55 *
56 * Viola, A. 2005. Exact distribution of individual displacements in linear probing hashing.
57 * ACM Trans. Algorithms 1, 2 (October 2005), 214-242.
58 * DOI=10.1145/1103963.1103965 http://doi.acm.org/10.1145/1103963.1103965
59 * - Similar to Janson. Note that Viola writes about C_{m,n} (number of probes
60 * in a successful search), and Janson writes about displacement. C = d + 1.
61 *
62 * Goossaert, E. 2013. Robin Hood hashing: backward shift deletion.
63 * http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
64 * - Explanation of backward shift deletion with pictures.
65 *
66 * Khuong, P. 2013. The Other Robin Hood Hashing.
67 * http://www.pvk.ca/Blog/2013/11/26/the-other-robin-hood-hashing/
68 * - Short summary of random vs. linear probing, and tombstones vs. backward shift.
69 */
70
71/*
72 * XXX Ideas for improvement:
73 * For unordered hashmaps, randomize iteration order, similarly to Perl:
74 * http://blog.booking.com/hardening-perls-hash-function.html
75 */
76
77/* INV_KEEP_FREE = 1 / (1 - max_load_factor)
78 * e.g. 1 / (1 - 0.8) = 5 ... keep one fifth of the buckets free. */
79#define INV_KEEP_FREE 5U
80
81/* Fields common to entries of all hashmap/set types */
82struct hashmap_base_entry {
83 const void *key;
84};
85
86/* Entry types for specific hashmap/set types
87 * hashmap_base_entry must be at the beginning of each entry struct. */
88
89struct plain_hashmap_entry {
90 struct hashmap_base_entry b;
91 void *value;
92};
93
94struct ordered_hashmap_entry {
95 struct plain_hashmap_entry p;
96 unsigned iterate_next, iterate_previous;
97};
98
99struct set_entry {
100 struct hashmap_base_entry b;
101};
102
103/* In several functions it is advantageous to have the hash table extended
104 * virtually by a couple of additional buckets. We reserve special index values
105 * for these "swap" buckets. */
106#define _IDX_SWAP_BEGIN (UINT_MAX - 3)
107#define IDX_PUT (_IDX_SWAP_BEGIN + 0)
108#define IDX_TMP (_IDX_SWAP_BEGIN + 1)
109#define _IDX_SWAP_END (_IDX_SWAP_BEGIN + 2)
110
111#define IDX_FIRST (UINT_MAX - 1) /* special index for freshly initialized iterators */
112#define IDX_NIL UINT_MAX /* special index value meaning "none" or "end" */
113
114assert_cc(IDX_FIRST == _IDX_SWAP_END);
115assert_cc(IDX_FIRST == _IDX_ITERATOR_FIRST);
116
117/* Storage space for the "swap" buckets.
118 * All entry types can fit into an ordered_hashmap_entry. */
119struct swap_entries {
120 struct ordered_hashmap_entry e[_IDX_SWAP_END - _IDX_SWAP_BEGIN];
121};
122
123/* Distance from Initial Bucket */
124typedef uint8_t dib_raw_t;
125#define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */
126#define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */
127#define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */
128#define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */
129
130#define DIB_FREE UINT_MAX
131
132#if ENABLE_DEBUG_HASHMAP
133struct hashmap_debug_info {
134 LIST_FIELDS(struct hashmap_debug_info, debug_list);
135 unsigned max_entries; /* high watermark of n_entries */
136
137 /* fields to detect modification while iterating */
138 unsigned put_count; /* counts puts into the hashmap */
139 unsigned rem_count; /* counts removals from hashmap */
140 unsigned last_rem_idx; /* remembers last removal index */
141};
142
143/* Tracks all existing hashmaps. Get at it from gdb. See sd_dump_hashmaps.py */
144static LIST_HEAD(struct hashmap_debug_info, hashmap_debug_list);
145static pthread_mutex_t hashmap_debug_list_mutex = PTHREAD_MUTEX_INITIALIZER;
146#endif
147
148enum HashmapType {
149 HASHMAP_TYPE_PLAIN,
150 HASHMAP_TYPE_ORDERED,
151 HASHMAP_TYPE_SET,
152 _HASHMAP_TYPE_MAX
153};
154
155struct _packed_ indirect_storage {
156 void *storage; /* where buckets and DIBs are stored */
157 uint8_t hash_key[HASH_KEY_SIZE]; /* hash key; changes during resize */
158
159 unsigned n_entries; /* number of stored entries */
160 unsigned n_buckets; /* number of buckets */
161
162 unsigned idx_lowest_entry; /* Index below which all buckets are free.
163 Makes "while (hashmap_steal_first())" loops
164 O(n) instead of O(n^2) for unordered hashmaps. */
165 uint8_t _pad[3]; /* padding for the whole HashmapBase */
166 /* The bitfields in HashmapBase complete the alignment of the whole thing. */
167};
168
169struct direct_storage {
170 /* This gives us 39 bytes on 64-bit, or 35 bytes on 32-bit.
171 * That's room for 4 set_entries + 4 DIB bytes + 3 unused bytes on 64-bit,
172 * or 7 set_entries + 7 DIB bytes + 0 unused bytes on 32-bit. */
173 uint8_t storage[sizeof(struct indirect_storage)];
174};
175
176#define DIRECT_BUCKETS(entry_t) \
177 (sizeof(struct direct_storage) / (sizeof(entry_t) + sizeof(dib_raw_t)))
178
179/* We should be able to store at least one entry directly. */
180assert_cc(DIRECT_BUCKETS(struct ordered_hashmap_entry) >= 1);
181
182/* We have 3 bits for n_direct_entries. */
183assert_cc(DIRECT_BUCKETS(struct set_entry) < (1 << 3));
184
185/* Hashmaps with directly stored entries all use this shared hash key.
186 * It's no big deal if the key is guessed, because there can be only
187 * a handful of directly stored entries in a hashmap. When a hashmap
188 * outgrows direct storage, it gets its own key for indirect storage. */
189static uint8_t shared_hash_key[HASH_KEY_SIZE];
190
191/* Fields that all hashmap/set types must have */
192struct HashmapBase {
193 const struct hash_ops *hash_ops; /* hash and compare ops to use */
194
195 union _packed_ {
196 struct indirect_storage indirect; /* if has_indirect */
197 struct direct_storage direct; /* if !has_indirect */
198 };
199
200 enum HashmapType type:2; /* HASHMAP_TYPE_* */
201 bool has_indirect:1; /* whether indirect storage is used */
202 unsigned n_direct_entries:3; /* Number of entries in direct storage.
203 * Only valid if !has_indirect. */
204 bool from_pool:1; /* whether was allocated from mempool */
205 bool dirty:1; /* whether dirtied since last iterated_cache_get() */
206 bool cached:1; /* whether this hashmap is being cached */
207
208#if ENABLE_DEBUG_HASHMAP
209 struct hashmap_debug_info debug;
210#endif
211};
212
213/* Specific hash types
214 * HashmapBase must be at the beginning of each hashmap struct. */
215
216struct Hashmap {
217 struct HashmapBase b;
218};
219
220struct OrderedHashmap {
221 struct HashmapBase b;
222 unsigned iterate_list_head, iterate_list_tail;
223};
224
225struct Set {
226 struct HashmapBase b;
227};
228
229typedef struct CacheMem {
230 const void **ptr;
231 size_t n_populated;
232 bool active:1;
233} CacheMem;
234
235struct IteratedCache {
236 HashmapBase *hashmap;
237 CacheMem keys, values;
238};
239
240DEFINE_MEMPOOL(hashmap_pool, Hashmap, 8);
241DEFINE_MEMPOOL(ordered_hashmap_pool, OrderedHashmap, 8);
242/* No need for a separate Set pool */
243assert_cc(sizeof(Hashmap) == sizeof(Set));
244
245struct hashmap_type_info {
246 size_t head_size;
247 size_t entry_size;
248 struct mempool *mempool;
249 unsigned n_direct_buckets;
250};
251
252static _used_ const struct hashmap_type_info hashmap_type_info[_HASHMAP_TYPE_MAX] = {
253 [HASHMAP_TYPE_PLAIN] = {
254 .head_size = sizeof(Hashmap),
255 .entry_size = sizeof(struct plain_hashmap_entry),
256 .mempool = &hashmap_pool,
257 .n_direct_buckets = DIRECT_BUCKETS(struct plain_hashmap_entry),
258 },
259 [HASHMAP_TYPE_ORDERED] = {
260 .head_size = sizeof(OrderedHashmap),
261 .entry_size = sizeof(struct ordered_hashmap_entry),
262 .mempool = &ordered_hashmap_pool,
263 .n_direct_buckets = DIRECT_BUCKETS(struct ordered_hashmap_entry),
264 },
265 [HASHMAP_TYPE_SET] = {
266 .head_size = sizeof(Set),
267 .entry_size = sizeof(struct set_entry),
268 .mempool = &hashmap_pool,
269 .n_direct_buckets = DIRECT_BUCKETS(struct set_entry),
270 },
271};
272
273void hashmap_trim_pools(void) {
274 int r;
275
276 /* The pool is only allocated by the main thread, but the memory can be passed to other
277 * threads. Let's clean up if we are the main thread and no other threads are live. */
278
279 /* We build our own is_main_thread() here, which doesn't use C11 TLS based caching of the
280 * result. That's because valgrind apparently doesn't like TLS to be used from a GCC destructor. */
281 if (getpid() != gettid())
282 return (void) log_debug("Not cleaning up memory pools, not in main thread.");
283
284 r = get_process_threads(0);
285 if (r < 0)
286 return (void) log_debug_errno(r, "Failed to determine number of threads, not cleaning up memory pools: %m");
287 if (r != 1)
288 return (void) log_debug("Not cleaning up memory pools, running in multi-threaded process.");
289
290 mempool_trim(&hashmap_pool);
291 mempool_trim(&ordered_hashmap_pool);
292}
293
294#if HAVE_VALGRIND_VALGRIND_H
295_destructor_ static void cleanup_pools(void) {
296 /* Be nice to valgrind */
297 if (RUNNING_ON_VALGRIND)
298 hashmap_trim_pools();
299}
300#endif
301
302static unsigned n_buckets(HashmapBase *h) {
303 assert(h);
304 return h->has_indirect ? h->indirect.n_buckets
305 : hashmap_type_info[h->type].n_direct_buckets;
306}
307
308static unsigned n_entries(HashmapBase *h) {
309 assert(h);
310 return h->has_indirect ? h->indirect.n_entries
311 : h->n_direct_entries;
312}
313
314static void n_entries_inc(HashmapBase *h) {
315 assert(h);
316
317 if (h->has_indirect)
318 h->indirect.n_entries++;
319 else
320 h->n_direct_entries++;
321}
322
323static void n_entries_dec(HashmapBase *h) {
324 assert(h);
325
326 if (h->has_indirect)
327 h->indirect.n_entries--;
328 else
329 h->n_direct_entries--;
330}
331
332static void* storage_ptr(HashmapBase *h) {
333 assert(h);
334 return h->has_indirect ? h->indirect.storage
335 : h->direct.storage;
336}
337
338static uint8_t* hash_key(HashmapBase *h) {
339 assert(h);
340 return h->has_indirect ? h->indirect.hash_key
341 : shared_hash_key;
342}
343
344static unsigned base_bucket_hash(HashmapBase *h, const void *p) {
345 struct siphash state;
346 uint64_t hash;
347
348 assert(h);
349
350 siphash24_init(&state, hash_key(h));
351
352 h->hash_ops->hash(p, &state);
353
354 hash = siphash24_finalize(&state);
355
356 return (unsigned) (hash % n_buckets(h));
357}
358#define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p)
359
360static void base_set_dirty(HashmapBase *h) {
361 assert(h);
362
363 h->dirty = true;
364}
365#define hashmap_set_dirty(h) base_set_dirty(HASHMAP_BASE(h))
366
367static void get_hash_key(uint8_t hash_key[HASH_KEY_SIZE], bool reuse_is_ok) {
368 static uint8_t current[HASH_KEY_SIZE];
369 static bool current_initialized = false;
370
371 /* Returns a hash function key to use. In order to keep things
372 * fast we will not generate a new key each time we allocate a
373 * new hash table. Instead, we'll just reuse the most recently
374 * generated one, except if we never generated one or when we
375 * are rehashing an entire hash table because we reached a
376 * fill level */
377
378 if (!current_initialized || !reuse_is_ok) {
379 random_bytes(current, sizeof(current));
380 current_initialized = true;
381 }
382
383 memcpy(hash_key, current, sizeof(current));
384}
385
386static struct hashmap_base_entry* bucket_at(HashmapBase *h, unsigned idx) {
387 assert(h);
388 return CAST_ALIGN_PTR(
389 struct hashmap_base_entry,
390 (uint8_t *) storage_ptr(h) + idx * hashmap_type_info[h->type].entry_size);
391}
392
393static struct plain_hashmap_entry* plain_bucket_at(Hashmap *h, unsigned idx) {
394 return (struct plain_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
395}
396
397static struct ordered_hashmap_entry* ordered_bucket_at(OrderedHashmap *h, unsigned idx) {
398 return (struct ordered_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
399}
400
401static struct set_entry *set_bucket_at(Set *h, unsigned idx) {
402 return (struct set_entry*) bucket_at(HASHMAP_BASE(h), idx);
403}
404
405static struct ordered_hashmap_entry* bucket_at_swap(struct swap_entries *swap, unsigned idx) {
406 assert(swap);
407 return &swap->e[idx - _IDX_SWAP_BEGIN];
408}
409
410/* Returns a pointer to the bucket at index idx.
411 * Understands real indexes and swap indexes, hence "_virtual". */
412static struct hashmap_base_entry* bucket_at_virtual(HashmapBase *h, struct swap_entries *swap,
413 unsigned idx) {
414 if (idx < _IDX_SWAP_BEGIN)
415 return bucket_at(h, idx);
416
417 if (idx < _IDX_SWAP_END)
418 return &bucket_at_swap(swap, idx)->p.b;
419
420 assert_not_reached();
421}
422
423static dib_raw_t* dib_raw_ptr(HashmapBase *h) {
424 assert(h);
425 return (dib_raw_t*)
426 ((uint8_t*) storage_ptr(h) + hashmap_type_info[h->type].entry_size * n_buckets(h));
427}
428
429static unsigned bucket_distance(HashmapBase *h, unsigned idx, unsigned from) {
430 return idx >= from ? idx - from
431 : n_buckets(h) + idx - from;
432}
433
434static unsigned bucket_calculate_dib(HashmapBase *h, unsigned idx, dib_raw_t raw_dib) {
435 unsigned initial_bucket;
436
437 if (raw_dib == DIB_RAW_FREE)
438 return DIB_FREE;
439
440 if (_likely_(raw_dib < DIB_RAW_OVERFLOW))
441 return raw_dib;
442
443 /*
444 * Having an overflow DIB value is very unlikely. The hash function
445 * would have to be bad. For example, in a table of size 2^24 filled
446 * to load factor 0.9 the maximum observed DIB is only about 60.
447 * In theory (assuming I used Maxima correctly), for an infinite size
448 * hash table with load factor 0.8 the probability of a given entry
449 * having DIB > 40 is 1.9e-8.
450 * This returns the correct DIB value by recomputing the hash value in
451 * the unlikely case. XXX Hitting this case could be a hint to rehash.
452 */
453 initial_bucket = bucket_hash(h, bucket_at(h, idx)->key);
454 return bucket_distance(h, idx, initial_bucket);
455}
456
457static void bucket_set_dib(HashmapBase *h, unsigned idx, unsigned dib) {
458 dib_raw_ptr(h)[idx] = dib != DIB_FREE ? MIN(dib, DIB_RAW_OVERFLOW) : DIB_RAW_FREE;
459}
460
461static unsigned skip_free_buckets(HashmapBase *h, unsigned idx) {
462 dib_raw_t *dibs;
463
464 dibs = dib_raw_ptr(h);
465
466 for ( ; idx < n_buckets(h); idx++)
467 if (dibs[idx] != DIB_RAW_FREE)
468 return idx;
469
470 return IDX_NIL;
471}
472
473static void bucket_mark_free(HashmapBase *h, unsigned idx) {
474 assert(h);
475
476 memzero(bucket_at(h, idx), hashmap_type_info[h->type].entry_size);
477 bucket_set_dib(h, idx, DIB_FREE);
478}
479
480static void bucket_move_entry(HashmapBase *h, struct swap_entries *swap,
481 unsigned from, unsigned to) {
482 struct hashmap_base_entry *e_from, *e_to;
483
484 assert(h);
485 assert(from != to);
486
487 e_from = bucket_at_virtual(h, swap, from);
488 e_to = bucket_at_virtual(h, swap, to);
489
490 memcpy(e_to, e_from, hashmap_type_info[h->type].entry_size);
491
492 if (h->type == HASHMAP_TYPE_ORDERED) {
493 OrderedHashmap *lh = (OrderedHashmap*) h;
494 struct ordered_hashmap_entry *le, *le_to;
495
496 le_to = (struct ordered_hashmap_entry*) e_to;
497
498 if (le_to->iterate_next != IDX_NIL) {
499 le = (struct ordered_hashmap_entry*)
500 bucket_at_virtual(h, swap, le_to->iterate_next);
501 le->iterate_previous = to;
502 }
503
504 if (le_to->iterate_previous != IDX_NIL) {
505 le = (struct ordered_hashmap_entry*)
506 bucket_at_virtual(h, swap, le_to->iterate_previous);
507 le->iterate_next = to;
508 }
509
510 if (lh->iterate_list_head == from)
511 lh->iterate_list_head = to;
512 if (lh->iterate_list_tail == from)
513 lh->iterate_list_tail = to;
514 }
515}
516
517static unsigned next_idx(HashmapBase *h, unsigned idx) {
518 return (idx + 1U) % n_buckets(h);
519}
520
521static unsigned prev_idx(HashmapBase *h, unsigned idx) {
522 return (n_buckets(h) + idx - 1U) % n_buckets(h);
523}
524
525static void* entry_value(HashmapBase *h, struct hashmap_base_entry *e) {
526 assert(h);
527 assert(e);
528
529 switch (h->type) {
530
531 case HASHMAP_TYPE_PLAIN:
532 case HASHMAP_TYPE_ORDERED:
533 return ((struct plain_hashmap_entry*)e)->value;
534
535 case HASHMAP_TYPE_SET:
536 return (void*) e->key;
537
538 default:
539 assert_not_reached();
540 }
541}
542
543static void base_remove_entry(HashmapBase *h, unsigned idx) {
544 unsigned left, right, prev, dib;
545 dib_raw_t raw_dib, *dibs;
546
547 dibs = dib_raw_ptr(h);
548 assert(dibs[idx] != DIB_RAW_FREE);
549
550#if ENABLE_DEBUG_HASHMAP
551 assert(h);
552 h->debug.rem_count++;
553 h->debug.last_rem_idx = idx;
554#endif
555
556 left = idx;
557 /* Find the stop bucket ("right"). It is either free or has DIB == 0. */
558 for (right = next_idx(h, left); ; right = next_idx(h, right)) {
559 raw_dib = dibs[right];
560 if (IN_SET(raw_dib, 0, DIB_RAW_FREE))
561 break;
562
563 /* The buckets are not supposed to be all occupied and with DIB > 0.
564 * That would mean we could make everyone better off by shifting them
565 * backward. This scenario is impossible. */
566 assert(left != right);
567 }
568
569 if (h->type == HASHMAP_TYPE_ORDERED) {
570 OrderedHashmap *lh = (OrderedHashmap*) h;
571 struct ordered_hashmap_entry *le = ordered_bucket_at(lh, idx);
572
573 if (le->iterate_next != IDX_NIL)
574 ordered_bucket_at(lh, le->iterate_next)->iterate_previous = le->iterate_previous;
575 else
576 lh->iterate_list_tail = le->iterate_previous;
577
578 if (le->iterate_previous != IDX_NIL)
579 ordered_bucket_at(lh, le->iterate_previous)->iterate_next = le->iterate_next;
580 else
581 lh->iterate_list_head = le->iterate_next;
582 }
583
584 /* Now shift all buckets in the interval (left, right) one step backwards */
585 for (prev = left, left = next_idx(h, left); left != right;
586 prev = left, left = next_idx(h, left)) {
587 dib = bucket_calculate_dib(h, left, dibs[left]);
588 assert(dib != 0);
589 bucket_move_entry(h, NULL, left, prev);
590 bucket_set_dib(h, prev, dib - 1);
591 }
592
593 bucket_mark_free(h, prev);
594 n_entries_dec(h);
595 base_set_dirty(h);
596}
597#define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)
598
599static unsigned hashmap_iterate_in_insertion_order(OrderedHashmap *h, Iterator *i) {
600 struct ordered_hashmap_entry *e;
601 unsigned idx;
602
603 assert(h);
604 assert(i);
605
606 if (i->idx == IDX_NIL)
607 goto at_end;
608
609 if (i->idx == IDX_FIRST && h->iterate_list_head == IDX_NIL)
610 goto at_end;
611
612 if (i->idx == IDX_FIRST) {
613 idx = h->iterate_list_head;
614 e = ordered_bucket_at(h, idx);
615 } else {
616 idx = i->idx;
617 e = ordered_bucket_at(h, idx);
618 /*
619 * We allow removing the current entry while iterating, but removal may cause
620 * a backward shift. The next entry may thus move one bucket to the left.
621 * To detect when it happens, we remember the key pointer of the entry we were
622 * going to iterate next. If it does not match, there was a backward shift.
623 */
624 if (e->p.b.key != i->next_key) {
625 idx = prev_idx(HASHMAP_BASE(h), idx);
626 e = ordered_bucket_at(h, idx);
627 }
628 assert(e->p.b.key == i->next_key);
629 }
630
631#if ENABLE_DEBUG_HASHMAP
632 i->prev_idx = idx;
633#endif
634
635 if (e->iterate_next != IDX_NIL) {
636 struct ordered_hashmap_entry *n;
637 i->idx = e->iterate_next;
638 n = ordered_bucket_at(h, i->idx);
639 i->next_key = n->p.b.key;
640 } else
641 i->idx = IDX_NIL;
642
643 return idx;
644
645at_end:
646 i->idx = IDX_NIL;
647 return IDX_NIL;
648}
649
650static unsigned hashmap_iterate_in_internal_order(HashmapBase *h, Iterator *i) {
651 unsigned idx;
652
653 assert(h);
654 assert(i);
655
656 if (i->idx == IDX_NIL)
657 goto at_end;
658
659 if (i->idx == IDX_FIRST) {
660 /* fast forward to the first occupied bucket */
661 if (h->has_indirect) {
662 i->idx = skip_free_buckets(h, h->indirect.idx_lowest_entry);
663 h->indirect.idx_lowest_entry = i->idx;
664 } else
665 i->idx = skip_free_buckets(h, 0);
666
667 if (i->idx == IDX_NIL)
668 goto at_end;
669 } else {
670 struct hashmap_base_entry *e;
671
672 assert(i->idx > 0);
673
674 e = bucket_at(h, i->idx);
675 /*
676 * We allow removing the current entry while iterating, but removal may cause
677 * a backward shift. The next entry may thus move one bucket to the left.
678 * To detect when it happens, we remember the key pointer of the entry we were
679 * going to iterate next. If it does not match, there was a backward shift.
680 */
681 if (e->key != i->next_key)
682 e = bucket_at(h, --i->idx);
683
684 assert(e->key == i->next_key);
685 }
686
687 idx = i->idx;
688#if ENABLE_DEBUG_HASHMAP
689 i->prev_idx = idx;
690#endif
691
692 i->idx = skip_free_buckets(h, i->idx + 1);
693 if (i->idx != IDX_NIL)
694 i->next_key = bucket_at(h, i->idx)->key;
695 else
696 i->idx = IDX_NIL;
697
698 return idx;
699
700at_end:
701 i->idx = IDX_NIL;
702 return IDX_NIL;
703}
704
705static unsigned hashmap_iterate_entry(HashmapBase *h, Iterator *i) {
706 if (!h) {
707 i->idx = IDX_NIL;
708 return IDX_NIL;
709 }
710
711#if ENABLE_DEBUG_HASHMAP
712 if (i->idx == IDX_FIRST) {
713 i->put_count = h->debug.put_count;
714 i->rem_count = h->debug.rem_count;
715 } else {
716 /* While iterating, must not add any new entries */
717 assert(i->put_count == h->debug.put_count);
718 /* ... or remove entries other than the current one */
719 assert(i->rem_count == h->debug.rem_count ||
720 (i->rem_count == h->debug.rem_count - 1 &&
721 i->prev_idx == h->debug.last_rem_idx));
722 /* Reset our removals counter */
723 i->rem_count = h->debug.rem_count;
724 }
725#endif
726
727 return h->type == HASHMAP_TYPE_ORDERED ? hashmap_iterate_in_insertion_order((OrderedHashmap*) h, i)
728 : hashmap_iterate_in_internal_order(h, i);
729}
730
731bool _hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key) {
732 struct hashmap_base_entry *e;
733 void *data;
734 unsigned idx;
735
736 idx = hashmap_iterate_entry(h, i);
737 if (idx == IDX_NIL) {
738 if (value)
739 *value = NULL;
740 if (key)
741 *key = NULL;
742
743 return false;
744 }
745
746 e = bucket_at(h, idx);
747 data = entry_value(h, e);
748 if (value)
749 *value = data;
750 if (key)
751 *key = e->key;
752
753 return true;
754}
755
756#define HASHMAP_FOREACH_IDX(idx, h, i) \
757 for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \
758 (idx != IDX_NIL); \
759 (idx) = hashmap_iterate_entry((h), &(i)))
760
761IteratedCache* _hashmap_iterated_cache_new(HashmapBase *h) {
762 IteratedCache *cache;
763
764 assert(h);
765 assert(!h->cached);
766
767 if (h->cached)
768 return NULL;
769
770 cache = new0(IteratedCache, 1);
771 if (!cache)
772 return NULL;
773
774 cache->hashmap = h;
775 h->cached = true;
776
777 return cache;
778}
779
780static void reset_direct_storage(HashmapBase *h) {
781 const struct hashmap_type_info *hi = &hashmap_type_info[h->type];
782 void *p;
783
784 assert(!h->has_indirect);
785
786 p = mempset(h->direct.storage, 0, hi->entry_size * hi->n_direct_buckets);
787 memset(p, DIB_RAW_INIT, sizeof(dib_raw_t) * hi->n_direct_buckets);
788}
789
790static void shared_hash_key_initialize(void) {
791 random_bytes(shared_hash_key, sizeof(shared_hash_key));
792}
793
794static struct HashmapBase* hashmap_base_new(const struct hash_ops *hash_ops, enum HashmapType type) {
795 HashmapBase *h;
796 const struct hashmap_type_info *hi = &hashmap_type_info[type];
797
798 bool use_pool = mempool_enabled && mempool_enabled(); /* mempool_enabled is a weak symbol */
799
800 h = use_pool ? mempool_alloc0_tile(hi->mempool) : malloc0(hi->head_size);
801 if (!h)
802 return NULL;
803
804 h->type = type;
805 h->from_pool = use_pool;
806 h->hash_ops = hash_ops ?: &trivial_hash_ops;
807
808 if (type == HASHMAP_TYPE_ORDERED) {
809 OrderedHashmap *lh = (OrderedHashmap*)h;
810 lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;
811 }
812
813 reset_direct_storage(h);
814
815 static pthread_once_t once = PTHREAD_ONCE_INIT;
816 assert_se(pthread_once(&once, shared_hash_key_initialize) == 0);
817
818#if ENABLE_DEBUG_HASHMAP
819 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex) == 0);
820 LIST_PREPEND(debug_list, hashmap_debug_list, &h->debug);
821 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex) == 0);
822#endif
823
824 return h;
825}
826
827Hashmap *hashmap_new(const struct hash_ops *hash_ops) {
828 return (Hashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_PLAIN);
829}
830
831OrderedHashmap *ordered_hashmap_new(const struct hash_ops *hash_ops) {
832 return (OrderedHashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_ORDERED);
833}
834
835Set *set_new(const struct hash_ops *hash_ops) {
836 return (Set*) hashmap_base_new(hash_ops, HASHMAP_TYPE_SET);
837}
838
839static int hashmap_base_ensure_allocated(HashmapBase **h, const struct hash_ops *hash_ops,
840 enum HashmapType type) {
841 HashmapBase *q;
842
843 assert(h);
844
845 if (*h) {
846 assert((*h)->hash_ops == (hash_ops ?: &trivial_hash_ops));
847 return 0;
848 }
849
850 q = hashmap_base_new(hash_ops, type);
851 if (!q)
852 return -ENOMEM;
853
854 *h = q;
855 return 1;
856}
857
858int hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops) {
859 return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_PLAIN);
860}
861
862int ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops) {
863 return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_ORDERED);
864}
865
866int set_ensure_allocated(Set **s, const struct hash_ops *hash_ops) {
867 return hashmap_base_ensure_allocated((HashmapBase**)s, hash_ops, HASHMAP_TYPE_SET);
868}
869
870int hashmap_ensure_put(Hashmap **h, const struct hash_ops *hash_ops, const void *key, void *value) {
871 int r;
872
873 assert(h);
874
875 r = hashmap_ensure_allocated(h, hash_ops);
876 if (r < 0)
877 return r;
878
879 return hashmap_put(*h, key, value);
880}
881
882int ordered_hashmap_ensure_put(OrderedHashmap **h, const struct hash_ops *hash_ops, const void *key, void *value) {
883 int r;
884
885 assert(h);
886
887 r = ordered_hashmap_ensure_allocated(h, hash_ops);
888 if (r < 0)
889 return r;
890
891 return ordered_hashmap_put(*h, key, value);
892}
893
894int ordered_hashmap_ensure_replace(OrderedHashmap **h, const struct hash_ops *hash_ops, const void *key, void *value) {
895 int r;
896
897 assert(h);
898
899 r = ordered_hashmap_ensure_allocated(h, hash_ops);
900 if (r < 0)
901 return r;
902
903 return ordered_hashmap_replace(*h, key, value);
904}
905
906int hashmap_ensure_replace(Hashmap **h, const struct hash_ops *hash_ops, const void *key, void *value) {
907 int r;
908
909 assert(h);
910
911 r = hashmap_ensure_allocated(h, hash_ops);
912 if (r < 0)
913 return r;
914
915 return hashmap_replace(*h, key, value);
916}
917
918static void hashmap_free_no_clear(HashmapBase *h) {
919 assert(!h->has_indirect);
920 assert(h->n_direct_entries == 0);
921
922#if ENABLE_DEBUG_HASHMAP
923 assert_se(pthread_mutex_lock(&hashmap_debug_list_mutex) == 0);
924 LIST_REMOVE(debug_list, hashmap_debug_list, &h->debug);
925 assert_se(pthread_mutex_unlock(&hashmap_debug_list_mutex) == 0);
926#endif
927
928 if (h->from_pool) {
929 /* Ensure that the object didn't get migrated between threads. */
930 assert_se(is_main_thread());
931 mempool_free_tile(hashmap_type_info[h->type].mempool, h);
932 } else
933 free(h);
934}
935
936HashmapBase* _hashmap_free(HashmapBase *h) {
937 if (h) {
938 _hashmap_clear(h);
939 hashmap_free_no_clear(h);
940 }
941
942 return NULL;
943}
944
945void _hashmap_clear(HashmapBase *h) {
946 if (!h)
947 return;
948
949 if (h->hash_ops->free_key || h->hash_ops->free_value) {
950
951 /* If destructor calls are defined, let's destroy things defensively: let's take the item out of the
952 * hash table, and only then call the destructor functions. If these destructors then try to unregister
953 * themselves from our hash table a second time, the entry is already gone. */
954
955 while (_hashmap_size(h) > 0) {
956 void *k = NULL;
957 void *v;
958
959 v = _hashmap_first_key_and_value(h, true, &k);
960
961 if (h->hash_ops->free_key)
962 h->hash_ops->free_key(k);
963
964 if (h->hash_ops->free_value)
965 h->hash_ops->free_value(v);
966 }
967 }
968
969 if (h->has_indirect) {
970 free(h->indirect.storage);
971 h->has_indirect = false;
972 }
973
974 h->n_direct_entries = 0;
975 reset_direct_storage(h);
976
977 if (h->type == HASHMAP_TYPE_ORDERED) {
978 OrderedHashmap *lh = (OrderedHashmap*) h;
979 lh->iterate_list_head = lh->iterate_list_tail = IDX_NIL;
980 }
981
982 base_set_dirty(h);
983}
984
985static int resize_buckets(HashmapBase *h, unsigned entries_add);
986
987/*
988 * Finds an empty bucket to put an entry into, starting the scan at 'idx'.
989 * Performs Robin Hood swaps as it goes. The entry to put must be placed
990 * by the caller into swap slot IDX_PUT.
991 * If used for in-place resizing, may leave a displaced entry in swap slot
992 * IDX_PUT. Caller must rehash it next.
993 * Returns: true if it left a displaced entry to rehash next in IDX_PUT,
994 * false otherwise.
995 */
996static bool hashmap_put_robin_hood(HashmapBase *h, unsigned idx,
997 struct swap_entries *swap) {
998 dib_raw_t raw_dib, *dibs;
999 unsigned dib, distance;
1000
1001#if ENABLE_DEBUG_HASHMAP
1002 assert(h);
1003 h->debug.put_count++;
1004#endif
1005
1006 dibs = dib_raw_ptr(h);
1007
1008 for (distance = 0; ; distance++) {
1009 raw_dib = dibs[idx];
1010 if (IN_SET(raw_dib, DIB_RAW_FREE, DIB_RAW_REHASH)) {
1011 if (raw_dib == DIB_RAW_REHASH)
1012 bucket_move_entry(h, swap, idx, IDX_TMP);
1013
1014 if (h->has_indirect && h->indirect.idx_lowest_entry > idx)
1015 h->indirect.idx_lowest_entry = idx;
1016
1017 bucket_set_dib(h, idx, distance);
1018 bucket_move_entry(h, swap, IDX_PUT, idx);
1019 if (raw_dib == DIB_RAW_REHASH) {
1020 bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
1021 return true;
1022 }
1023
1024 return false;
1025 }
1026
1027 dib = bucket_calculate_dib(h, idx, raw_dib);
1028
1029 if (dib < distance) {
1030 /* Found a wealthier entry. Go Robin Hood! */
1031 bucket_set_dib(h, idx, distance);
1032
1033 /* swap the entries */
1034 bucket_move_entry(h, swap, idx, IDX_TMP);
1035 bucket_move_entry(h, swap, IDX_PUT, idx);
1036 bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
1037
1038 distance = dib;
1039 }
1040
1041 idx = next_idx(h, idx);
1042 }
1043}
1044
1045/*
1046 * Puts an entry into a hashmap, boldly - no check whether key already exists.
1047 * The caller must place the entry (only its key and value, not link indexes)
1048 * in swap slot IDX_PUT.
1049 * Caller must ensure: the key does not exist yet in the hashmap.
1050 * that resize is not needed if !may_resize.
1051 * Returns: 1 if entry was put successfully.
1052 * -ENOMEM if may_resize==true and resize failed with -ENOMEM.
1053 * Cannot return -ENOMEM if !may_resize.
1054 */
1055static int hashmap_base_put_boldly(HashmapBase *h, unsigned idx,
1056 struct swap_entries *swap, bool may_resize) {
1057 struct ordered_hashmap_entry *new_entry;
1058 int r;
1059
1060 assert(idx < n_buckets(h));
1061
1062 new_entry = bucket_at_swap(swap, IDX_PUT);
1063
1064 if (may_resize) {
1065 r = resize_buckets(h, 1);
1066 if (r < 0)
1067 return r;
1068 if (r > 0)
1069 idx = bucket_hash(h, new_entry->p.b.key);
1070 }
1071 assert(n_entries(h) < n_buckets(h));
1072
1073 if (h->type == HASHMAP_TYPE_ORDERED) {
1074 OrderedHashmap *lh = (OrderedHashmap*) h;
1075
1076 new_entry->iterate_next = IDX_NIL;
1077 new_entry->iterate_previous = lh->iterate_list_tail;
1078
1079 if (lh->iterate_list_tail != IDX_NIL) {
1080 struct ordered_hashmap_entry *old_tail;
1081
1082 old_tail = ordered_bucket_at(lh, lh->iterate_list_tail);
1083 assert(old_tail->iterate_next == IDX_NIL);
1084 old_tail->iterate_next = IDX_PUT;
1085 }
1086
1087 lh->iterate_list_tail = IDX_PUT;
1088 if (lh->iterate_list_head == IDX_NIL)
1089 lh->iterate_list_head = IDX_PUT;
1090 }
1091
1092 assert_se(hashmap_put_robin_hood(h, idx, swap) == false);
1093
1094 n_entries_inc(h);
1095#if ENABLE_DEBUG_HASHMAP
1096 h->debug.max_entries = MAX(h->debug.max_entries, n_entries(h));
1097#endif
1098
1099 base_set_dirty(h);
1100
1101 return 1;
1102}
1103#define hashmap_put_boldly(h, idx, swap, may_resize) \
1104 hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
1105
1106/*
1107 * Returns 0 if resize is not needed.
1108 * 1 if successfully resized.
1109 * -ENOMEM on allocation failure.
1110 */
1111static int resize_buckets(HashmapBase *h, unsigned entries_add) {
1112 struct swap_entries swap;
1113 void *new_storage;
1114 dib_raw_t *old_dibs, *new_dibs;
1115 const struct hashmap_type_info *hi;
1116 unsigned idx, optimal_idx;
1117 unsigned old_n_buckets, new_n_buckets, n_rehashed, new_n_entries;
1118 uint8_t new_shift;
1119 bool rehash_next;
1120
1121 assert(h);
1122
1123 hi = &hashmap_type_info[h->type];
1124 new_n_entries = n_entries(h) + entries_add;
1125
1126 /* overflow? */
1127 if (_unlikely_(new_n_entries < entries_add))
1128 return -ENOMEM;
1129
1130 /* For direct storage we allow 100% load, because it's tiny. */
1131 if (!h->has_indirect && new_n_entries <= hi->n_direct_buckets)
1132 return 0;
1133
1134 /*
1135 * Load factor = n/m = 1 - (1/INV_KEEP_FREE).
1136 * From it follows: m = n + n/(INV_KEEP_FREE - 1)
1137 */
1138 new_n_buckets = new_n_entries + new_n_entries / (INV_KEEP_FREE - 1);
1139 /* overflow? */
1140 if (_unlikely_(new_n_buckets < new_n_entries))
1141 return -ENOMEM;
1142
1143 if (_unlikely_(new_n_buckets > UINT_MAX / (hi->entry_size + sizeof(dib_raw_t))))
1144 return -ENOMEM;
1145
1146 old_n_buckets = n_buckets(h);
1147
1148 if (_likely_(new_n_buckets <= old_n_buckets))
1149 return 0;
1150
1151 new_shift = log2u_round_up(MAX(
1152 new_n_buckets * (hi->entry_size + sizeof(dib_raw_t)),
1153 2 * sizeof(struct direct_storage)));
1154
1155 /* Realloc storage (buckets and DIB array). */
1156 new_storage = realloc(h->has_indirect ? h->indirect.storage : NULL,
1157 1U << new_shift);
1158 if (!new_storage)
1159 return -ENOMEM;
1160
1161 /* Must upgrade direct to indirect storage. */
1162 if (!h->has_indirect) {
1163 memcpy(new_storage, h->direct.storage,
1164 old_n_buckets * (hi->entry_size + sizeof(dib_raw_t)));
1165 h->indirect.n_entries = h->n_direct_entries;
1166 h->indirect.idx_lowest_entry = 0;
1167 h->n_direct_entries = 0;
1168 }
1169
1170 /* Get a new hash key. If we've just upgraded to indirect storage,
1171 * allow reusing a previously generated key. It's still a different key
1172 * from the shared one that we used for direct storage. */
1173 get_hash_key(h->indirect.hash_key, !h->has_indirect);
1174
1175 h->has_indirect = true;
1176 h->indirect.storage = new_storage;
1177 h->indirect.n_buckets = (1U << new_shift) /
1178 (hi->entry_size + sizeof(dib_raw_t));
1179
1180 old_dibs = (dib_raw_t*)((uint8_t*) new_storage + hi->entry_size * old_n_buckets);
1181 new_dibs = dib_raw_ptr(h);
1182
1183 /*
1184 * Move the DIB array to the new place, replacing valid DIB values with
1185 * DIB_RAW_REHASH to indicate all of the used buckets need rehashing.
1186 * Note: Overlap is not possible, because we have at least doubled the
1187 * number of buckets and dib_raw_t is smaller than any entry type.
1188 */
1189 for (idx = 0; idx < old_n_buckets; idx++) {
1190 assert(old_dibs[idx] != DIB_RAW_REHASH);
1191 new_dibs[idx] = old_dibs[idx] == DIB_RAW_FREE ? DIB_RAW_FREE
1192 : DIB_RAW_REHASH;
1193 }
1194
1195 /* Zero the area of newly added entries (including the old DIB area) */
1196 memzero(bucket_at(h, old_n_buckets),
1197 (n_buckets(h) - old_n_buckets) * hi->entry_size);
1198
1199 /* The upper half of the new DIB array needs initialization */
1200 memset(&new_dibs[old_n_buckets], DIB_RAW_INIT,
1201 (n_buckets(h) - old_n_buckets) * sizeof(dib_raw_t));
1202
1203 /* Rehash entries that need it */
1204 n_rehashed = 0;
1205 for (idx = 0; idx < old_n_buckets; idx++) {
1206 if (new_dibs[idx] != DIB_RAW_REHASH)
1207 continue;
1208
1209 optimal_idx = bucket_hash(h, bucket_at(h, idx)->key);
1210
1211 /*
1212 * Not much to do if by luck the entry hashes to its current
1213 * location. Just set its DIB.
1214 */
1215 if (optimal_idx == idx) {
1216 new_dibs[idx] = 0;
1217 n_rehashed++;
1218 continue;
1219 }
1220
1221 new_dibs[idx] = DIB_RAW_FREE;
1222 bucket_move_entry(h, &swap, idx, IDX_PUT);
1223 /* bucket_move_entry does not clear the source */
1224 memzero(bucket_at(h, idx), hi->entry_size);
1225
1226 do {
1227 /*
1228 * Find the new bucket for the current entry. This may make
1229 * another entry homeless and load it into IDX_PUT.
1230 */
1231 rehash_next = hashmap_put_robin_hood(h, optimal_idx, &swap);
1232 n_rehashed++;
1233
1234 /* Did the current entry displace another one? */
1235 if (rehash_next)
1236 optimal_idx = bucket_hash(h, bucket_at_swap(&swap, IDX_PUT)->p.b.key);
1237 } while (rehash_next);
1238 }
1239
1240 assert_se(n_rehashed == n_entries(h));
1241
1242 return 1;
1243}
1244
1245/*
1246 * Finds an entry with a matching key
1247 * Returns: index of the found entry, or IDX_NIL if not found.
1248 */
1249static unsigned base_bucket_scan(HashmapBase *h, unsigned idx, const void *key) {
1250 struct hashmap_base_entry *e;
1251 unsigned dib, distance;
1252 dib_raw_t *dibs = dib_raw_ptr(h);
1253
1254 assert(idx < n_buckets(h));
1255
1256 for (distance = 0; ; distance++) {
1257 if (dibs[idx] == DIB_RAW_FREE)
1258 return IDX_NIL;
1259
1260 dib = bucket_calculate_dib(h, idx, dibs[idx]);
1261
1262 if (dib < distance)
1263 return IDX_NIL;
1264 if (dib == distance) {
1265 e = bucket_at(h, idx);
1266 if (h->hash_ops->compare(e->key, key) == 0)
1267 return idx;
1268 }
1269
1270 idx = next_idx(h, idx);
1271 }
1272}
1273#define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
1274
1275int hashmap_put(Hashmap *h, const void *key, void *value) {
1276 struct swap_entries swap;
1277 struct plain_hashmap_entry *e;
1278 unsigned hash, idx;
1279
1280 assert(h);
1281
1282 hash = bucket_hash(h, key);
1283 idx = bucket_scan(h, hash, key);
1284 if (idx != IDX_NIL) {
1285 e = plain_bucket_at(h, idx);
1286 if (e->value == value)
1287 return 0;
1288 return -EEXIST;
1289 }
1290
1291 e = &bucket_at_swap(&swap, IDX_PUT)->p;
1292 e->b.key = key;
1293 e->value = value;
1294 return hashmap_put_boldly(h, hash, &swap, true);
1295}
1296
1297int set_put(Set *s, const void *key) {
1298 struct swap_entries swap;
1299 struct hashmap_base_entry *e;
1300 unsigned hash, idx;
1301
1302 assert(s);
1303
1304 hash = bucket_hash(s, key);
1305 idx = bucket_scan(s, hash, key);
1306 if (idx != IDX_NIL)
1307 return 0;
1308
1309 e = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1310 e->key = key;
1311 return hashmap_put_boldly(s, hash, &swap, true);
1312}
1313
1314int set_ensure_put(Set **s, const struct hash_ops *hash_ops, const void *key) {
1315 int r;
1316
1317 assert(s);
1318
1319 r = set_ensure_allocated(s, hash_ops);
1320 if (r < 0)
1321 return r;
1322
1323 return set_put(*s, key);
1324}
1325
1326int set_ensure_consume(Set **s, const struct hash_ops *hash_ops, void *key) {
1327 int r;
1328
1329 r = set_ensure_put(s, hash_ops, key);
1330 if (r <= 0) {
1331 if (hash_ops && hash_ops->free_key)
1332 hash_ops->free_key(key);
1333 else if (hash_ops && hash_ops->free_value)
1334 /* Sets store their element in the key slot but may carry a value destructor. */
1335 hash_ops->free_value(key);
1336 else
1337 free(key);
1338 }
1339
1340 return r;
1341}
1342
1343int hashmap_replace(Hashmap *h, const void *key, void *value) {
1344 struct swap_entries swap;
1345 struct plain_hashmap_entry *e;
1346 unsigned hash, idx;
1347
1348 assert(h);
1349
1350 hash = bucket_hash(h, key);
1351 idx = bucket_scan(h, hash, key);
1352 if (idx != IDX_NIL) {
1353 e = plain_bucket_at(h, idx);
1354#if ENABLE_DEBUG_HASHMAP
1355 /* Although the key is equal, the key pointer may have changed,
1356 * and this would break our assumption for iterating. So count
1357 * this operation as incompatible with iteration. */
1358 if (e->b.key != key) {
1359 h->b.debug.put_count++;
1360 h->b.debug.rem_count++;
1361 h->b.debug.last_rem_idx = idx;
1362 }
1363#endif
1364 e->b.key = key;
1365 e->value = value;
1366 hashmap_set_dirty(h);
1367
1368 return 0;
1369 }
1370
1371 e = &bucket_at_swap(&swap, IDX_PUT)->p;
1372 e->b.key = key;
1373 e->value = value;
1374 return hashmap_put_boldly(h, hash, &swap, true);
1375}
1376
1377int hashmap_update(Hashmap *h, const void *key, void *value) {
1378 struct plain_hashmap_entry *e;
1379 unsigned hash, idx;
1380
1381 assert(h);
1382
1383 hash = bucket_hash(h, key);
1384 idx = bucket_scan(h, hash, key);
1385 if (idx == IDX_NIL)
1386 return -ENOENT;
1387
1388 e = plain_bucket_at(h, idx);
1389 e->value = value;
1390 hashmap_set_dirty(h);
1391
1392 return 0;
1393}
1394
1395void* _hashmap_get(HashmapBase *h, const void *key) {
1396 struct hashmap_base_entry *e;
1397 unsigned hash, idx;
1398
1399 if (!h)
1400 return NULL;
1401
1402 hash = bucket_hash(h, key);
1403 idx = bucket_scan(h, hash, key);
1404 if (idx == IDX_NIL)
1405 return NULL;
1406
1407 e = bucket_at(h, idx);
1408 return entry_value(h, e);
1409}
1410
1411void* hashmap_get2(Hashmap *h, const void *key, void **ret) {
1412 struct plain_hashmap_entry *e;
1413 unsigned hash, idx;
1414
1415 if (!h)
1416 return NULL;
1417
1418 hash = bucket_hash(h, key);
1419 idx = bucket_scan(h, hash, key);
1420 if (idx == IDX_NIL)
1421 return NULL;
1422
1423 e = plain_bucket_at(h, idx);
1424 if (ret)
1425 *ret = (void*) e->b.key;
1426
1427 return e->value;
1428}
1429
1430bool _hashmap_contains(HashmapBase *h, const void *key) {
1431 unsigned hash;
1432
1433 if (!h)
1434 return false;
1435
1436 hash = bucket_hash(h, key);
1437 return bucket_scan(h, hash, key) != IDX_NIL;
1438}
1439
1440void* _hashmap_remove(HashmapBase *h, const void *key) {
1441 struct hashmap_base_entry *e;
1442 unsigned hash, idx;
1443 void *data;
1444
1445 if (!h)
1446 return NULL;
1447
1448 hash = bucket_hash(h, key);
1449 idx = bucket_scan(h, hash, key);
1450 if (idx == IDX_NIL)
1451 return NULL;
1452
1453 e = bucket_at(h, idx);
1454 data = entry_value(h, e);
1455 remove_entry(h, idx);
1456
1457 return data;
1458}
1459
1460void* hashmap_remove2(Hashmap *h, const void *key, void **ret) {
1461 struct plain_hashmap_entry *e;
1462 unsigned hash, idx;
1463 void *data;
1464
1465 if (!h) {
1466 if (ret)
1467 *ret = NULL;
1468 return NULL;
1469 }
1470
1471 hash = bucket_hash(h, key);
1472 idx = bucket_scan(h, hash, key);
1473 if (idx == IDX_NIL) {
1474 if (ret)
1475 *ret = NULL;
1476 return NULL;
1477 }
1478
1479 e = plain_bucket_at(h, idx);
1480 data = e->value;
1481 if (ret)
1482 *ret = (void*) e->b.key;
1483
1484 remove_entry(h, idx);
1485
1486 return data;
1487}
1488
1489int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
1490 struct swap_entries swap;
1491 struct plain_hashmap_entry *e;
1492 unsigned old_hash, new_hash, idx;
1493
1494 if (!h)
1495 return -ENOENT;
1496
1497 old_hash = bucket_hash(h, old_key);
1498 idx = bucket_scan(h, old_hash, old_key);
1499 if (idx == IDX_NIL)
1500 return -ENOENT;
1501
1502 new_hash = bucket_hash(h, new_key);
1503 if (bucket_scan(h, new_hash, new_key) != IDX_NIL)
1504 return -EEXIST;
1505
1506 remove_entry(h, idx);
1507
1508 e = &bucket_at_swap(&swap, IDX_PUT)->p;
1509 e->b.key = new_key;
1510 e->value = value;
1511 assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
1512
1513 return 0;
1514}
1515
1516int set_remove_and_put(Set *s, const void *old_key, const void *new_key) {
1517 struct swap_entries swap;
1518 struct hashmap_base_entry *e;
1519 unsigned old_hash, new_hash, idx;
1520
1521 if (!s)
1522 return -ENOENT;
1523
1524 old_hash = bucket_hash(s, old_key);
1525 idx = bucket_scan(s, old_hash, old_key);
1526 if (idx == IDX_NIL)
1527 return -ENOENT;
1528
1529 new_hash = bucket_hash(s, new_key);
1530 if (bucket_scan(s, new_hash, new_key) != IDX_NIL)
1531 return -EEXIST;
1532
1533 remove_entry(s, idx);
1534
1535 e = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1536 e->key = new_key;
1537 assert_se(hashmap_put_boldly(s, new_hash, &swap, false) == 1);
1538
1539 return 0;
1540}
1541
1542int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
1543 struct swap_entries swap;
1544 struct plain_hashmap_entry *e;
1545 unsigned old_hash, new_hash, idx_old, idx_new;
1546
1547 if (!h)
1548 return -ENOENT;
1549
1550 old_hash = bucket_hash(h, old_key);
1551 idx_old = bucket_scan(h, old_hash, old_key);
1552 if (idx_old == IDX_NIL)
1553 return -ENOENT;
1554
1555 old_key = bucket_at(HASHMAP_BASE(h), idx_old)->key;
1556
1557 new_hash = bucket_hash(h, new_key);
1558 idx_new = bucket_scan(h, new_hash, new_key);
1559 if (idx_new != IDX_NIL)
1560 if (idx_old != idx_new) {
1561 remove_entry(h, idx_new);
1562 /* Compensate for a possible backward shift. */
1563 if (old_key != bucket_at(HASHMAP_BASE(h), idx_old)->key)
1564 idx_old = prev_idx(HASHMAP_BASE(h), idx_old);
1565 assert(old_key == bucket_at(HASHMAP_BASE(h), idx_old)->key);
1566 }
1567
1568 remove_entry(h, idx_old);
1569
1570 e = &bucket_at_swap(&swap, IDX_PUT)->p;
1571 e->b.key = new_key;
1572 e->value = value;
1573 assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
1574
1575 return 0;
1576}
1577
1578void* _hashmap_remove_value(HashmapBase *h, const void *key, void *value) {
1579 struct hashmap_base_entry *e;
1580 unsigned hash, idx;
1581
1582 if (!h)
1583 return NULL;
1584
1585 hash = bucket_hash(h, key);
1586 idx = bucket_scan(h, hash, key);
1587 if (idx == IDX_NIL)
1588 return NULL;
1589
1590 e = bucket_at(h, idx);
1591 if (entry_value(h, e) != value)
1592 return NULL;
1593
1594 remove_entry(h, idx);
1595
1596 return value;
1597}
1598
1599static unsigned find_first_entry(HashmapBase *h) {
1600 Iterator i = ITERATOR_FIRST;
1601
1602 if (!h || !n_entries(h))
1603 return IDX_NIL;
1604
1605 return hashmap_iterate_entry(h, &i);
1606}
1607
1608void* _hashmap_first_key_and_value(HashmapBase *h, bool remove, void **ret_key) {
1609 struct hashmap_base_entry *e;
1610 void *key, *data;
1611 unsigned idx;
1612
1613 idx = find_first_entry(h);
1614 if (idx == IDX_NIL) {
1615 if (ret_key)
1616 *ret_key = NULL;
1617 return NULL;
1618 }
1619
1620 e = bucket_at(h, idx);
1621 key = (void*) e->key;
1622 data = entry_value(h, e);
1623
1624 if (remove)
1625 remove_entry(h, idx);
1626
1627 if (ret_key)
1628 *ret_key = key;
1629
1630 return data;
1631}
1632
1633unsigned _hashmap_size(HashmapBase *h) {
1634 if (!h)
1635 return 0;
1636
1637 return n_entries(h);
1638}
1639
1640unsigned _hashmap_buckets(HashmapBase *h) {
1641 if (!h)
1642 return 0;
1643
1644 return n_buckets(h);
1645}
1646
1647int _hashmap_merge(Hashmap *h, Hashmap *other) {
1648 Iterator i;
1649 unsigned idx;
1650
1651 assert(h);
1652
1653 HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1654 struct plain_hashmap_entry *pe = plain_bucket_at(other, idx);
1655 int r;
1656
1657 r = hashmap_put(h, pe->b.key, pe->value);
1658 if (r < 0 && r != -EEXIST)
1659 return r;
1660 }
1661
1662 return 0;
1663}
1664
1665int set_merge(Set *s, Set *other) {
1666 Iterator i;
1667 unsigned idx;
1668
1669 assert(s);
1670
1671 HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1672 struct set_entry *se = set_bucket_at(other, idx);
1673 int r;
1674
1675 r = set_put(s, se->b.key);
1676 if (r < 0)
1677 return r;
1678 }
1679
1680 return 0;
1681}
1682
1683int _hashmap_reserve(HashmapBase *h, unsigned entries_add) {
1684 int r;
1685
1686 assert(h);
1687
1688 r = resize_buckets(h, entries_add);
1689 if (r < 0)
1690 return r;
1691
1692 return 0;
1693}
1694
1695/*
1696 * The same as hashmap_merge(), but every new item from other is moved to h.
1697 * Keys already in h are skipped and stay in other.
1698 * Returns: 0 on success.
1699 * -ENOMEM on alloc failure, in which case no move has been done.
1700 */
1701int _hashmap_move(HashmapBase *h, HashmapBase *other) {
1702 struct swap_entries swap;
1703 struct hashmap_base_entry *e, *n;
1704 Iterator i;
1705 unsigned idx;
1706 int r;
1707
1708 assert(h);
1709
1710 if (!other)
1711 return 0;
1712
1713 assert(other->type == h->type);
1714
1715 /*
1716 * This reserves buckets for the worst case, where none of other's
1717 * entries are yet present in h. This is preferable to risking
1718 * an allocation failure in the middle of the moving and having to
1719 * rollback or return a partial result.
1720 */
1721 r = resize_buckets(h, n_entries(other));
1722 if (r < 0)
1723 return r;
1724
1725 HASHMAP_FOREACH_IDX(idx, other, i) {
1726 unsigned h_hash;
1727
1728 e = bucket_at(other, idx);
1729 h_hash = bucket_hash(h, e->key);
1730 if (bucket_scan(h, h_hash, e->key) != IDX_NIL)
1731 continue;
1732
1733 n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1734 n->key = e->key;
1735 if (h->type != HASHMAP_TYPE_SET)
1736 ((struct plain_hashmap_entry*) n)->value =
1737 ((struct plain_hashmap_entry*) e)->value;
1738 assert_se(hashmap_put_boldly(h, h_hash, &swap, false) == 1);
1739
1740 remove_entry(other, idx);
1741 }
1742
1743 return 0;
1744}
1745
1746int _hashmap_move_one(HashmapBase *h, HashmapBase *other, const void *key) {
1747 struct swap_entries swap;
1748 unsigned h_hash, other_hash, idx;
1749 struct hashmap_base_entry *e, *n;
1750 int r;
1751
1752 assert(h);
1753
1754 h_hash = bucket_hash(h, key);
1755 if (bucket_scan(h, h_hash, key) != IDX_NIL)
1756 return -EEXIST;
1757
1758 if (!other)
1759 return -ENOENT;
1760
1761 assert(other->type == h->type);
1762
1763 other_hash = bucket_hash(other, key);
1764 idx = bucket_scan(other, other_hash, key);
1765 if (idx == IDX_NIL)
1766 return -ENOENT;
1767
1768 e = bucket_at(other, idx);
1769
1770 n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
1771 n->key = e->key;
1772 if (h->type != HASHMAP_TYPE_SET)
1773 ((struct plain_hashmap_entry*) n)->value =
1774 ((struct plain_hashmap_entry*) e)->value;
1775 r = hashmap_put_boldly(h, h_hash, &swap, true);
1776 if (r < 0)
1777 return r;
1778
1779 remove_entry(other, idx);
1780 return 0;
1781}
1782
1783HashmapBase* _hashmap_copy(HashmapBase *h) {
1784 HashmapBase *copy;
1785 int r;
1786
1787 assert(h);
1788
1789 copy = hashmap_base_new(h->hash_ops, h->type);
1790 if (!copy)
1791 return NULL;
1792
1793 switch (h->type) {
1794 case HASHMAP_TYPE_PLAIN:
1795 case HASHMAP_TYPE_ORDERED:
1796 r = hashmap_merge((Hashmap*)copy, (Hashmap*)h);
1797 break;
1798 case HASHMAP_TYPE_SET:
1799 r = set_merge((Set*)copy, (Set*)h);
1800 break;
1801 default:
1802 assert_not_reached();
1803 }
1804
1805 if (r < 0)
1806 return _hashmap_free(copy);
1807
1808 return copy;
1809}
1810
1811char** _hashmap_get_strv(HashmapBase *h) {
1812 char **sv;
1813 Iterator i;
1814 unsigned idx, n;
1815
1816 if (!h)
1817 return new0(char*, 1);
1818
1819 sv = new(char*, n_entries(h)+1);
1820 if (!sv)
1821 return NULL;
1822
1823 n = 0;
1824 HASHMAP_FOREACH_IDX(idx, h, i)
1825 sv[n++] = entry_value(h, bucket_at(h, idx));
1826 sv[n] = NULL;
1827
1828 return sv;
1829}
1830
1831char** set_to_strv(Set **s) {
1832 assert(s);
1833
1834 /* This is similar to set_get_strv(), but invalidates the set on success. */
1835
1836 char **v = new(char*, set_size(*s) + 1);
1837 if (!v)
1838 return NULL;
1839
1840 for (char **p = v; (*p = set_steal_first(*s)); p++)
1841 ;
1842
1843 assert(set_isempty(*s));
1844 *s = set_free(*s);
1845 return v;
1846}
1847
1848void* ordered_hashmap_next(OrderedHashmap *h, const void *key) {
1849 struct ordered_hashmap_entry *e;
1850 unsigned hash, idx;
1851
1852 if (!h)
1853 return NULL;
1854
1855 hash = bucket_hash(h, key);
1856 idx = bucket_scan(h, hash, key);
1857 if (idx == IDX_NIL)
1858 return NULL;
1859
1860 e = ordered_bucket_at(h, idx);
1861 if (e->iterate_next == IDX_NIL)
1862 return NULL;
1863 return ordered_bucket_at(h, e->iterate_next)->p.value;
1864}
1865
1866int set_consume(Set *s, void *value) {
1867 int r;
1868
1869 assert(s);
1870 assert(value);
1871
1872 r = set_put(s, value);
1873 if (r <= 0)
1874 free(value);
1875
1876 return r;
1877}
1878
1879int hashmap_put_strdup_full(Hashmap **h, const struct hash_ops *hash_ops, const char *k, const char *v) {
1880 int r;
1881
1882 assert(h);
1883
1884 r = hashmap_ensure_allocated(h, hash_ops);
1885 if (r < 0)
1886 return r;
1887
1888 _cleanup_free_ char *kdup = NULL, *vdup = NULL;
1889
1890 kdup = strdup(k);
1891 if (!kdup)
1892 return -ENOMEM;
1893
1894 if (v) {
1895 vdup = strdup(v);
1896 if (!vdup)
1897 return -ENOMEM;
1898 }
1899
1900 r = hashmap_put(*h, kdup, vdup);
1901 if (r < 0) {
1902 if (r == -EEXIST && streq_ptr(v, hashmap_get(*h, kdup)))
1903 return 0;
1904 return r;
1905 }
1906
1907 /* 0 with non-null vdup would mean vdup is already in the hashmap, which cannot be */
1908 assert(vdup == NULL || r > 0);
1909 if (r > 0)
1910 kdup = vdup = NULL;
1911
1912 return r;
1913}
1914
1915int set_put_strndup_full(Set **s, const struct hash_ops *hash_ops, const char *p, size_t n) {
1916 char *c;
1917 int r;
1918
1919 assert(s);
1920 assert(p);
1921
1922 r = set_ensure_allocated(s, hash_ops);
1923 if (r < 0)
1924 return r;
1925
1926 if (n == SIZE_MAX) {
1927 if (set_contains(*s, (char*) p))
1928 return 0;
1929
1930 c = strdup(p);
1931 } else
1932 c = strndup(p, n);
1933 if (!c)
1934 return -ENOMEM;
1935
1936 return set_consume(*s, c);
1937}
1938
1939int set_put_strdupv_full(Set **s, const struct hash_ops *hash_ops, char **l) {
1940 int n = 0, r;
1941
1942 assert(s);
1943
1944 STRV_FOREACH(i, l) {
1945 r = set_put_strndup_full(s, hash_ops, *i, SIZE_MAX);
1946 if (r < 0)
1947 return r;
1948
1949 n += r;
1950 }
1951
1952 return n;
1953}
1954
1955int set_put_strsplit(Set *s, const char *v, const char *separators, ExtractFlags flags) {
1956 const char *p = ASSERT_PTR(v);
1957 int r;
1958
1959 assert(s);
1960
1961 for (;;) {
1962 char *word;
1963
1964 r = extract_first_word(&p, &word, separators, flags);
1965 if (r <= 0)
1966 return r;
1967
1968 r = set_consume(s, word);
1969 if (r < 0)
1970 return r;
1971 }
1972}
1973
1974/* expand the cachemem if needed, return true if newly (re)activated. */
1975static int cachemem_maintain(CacheMem *mem, size_t size) {
1976 assert(mem);
1977
1978 if (!GREEDY_REALLOC(mem->ptr, size)) {
1979 if (size > 0)
1980 return -ENOMEM;
1981 }
1982
1983 if (!mem->active) {
1984 mem->active = true;
1985 return true;
1986 }
1987
1988 return false;
1989}
1990
1991int iterated_cache_get(IteratedCache *cache, const void ***res_keys, const void ***res_values, unsigned *res_n_entries) {
1992 bool sync_keys = false, sync_values = false;
1993 size_t size;
1994 int r;
1995
1996 assert(cache);
1997 assert(cache->hashmap);
1998
1999 size = n_entries(cache->hashmap);
2000
2001 if (res_keys) {
2002 r = cachemem_maintain(&cache->keys, size);
2003 if (r < 0)
2004 return r;
2005
2006 sync_keys = r;
2007 } else
2008 cache->keys.active = false;
2009
2010 if (res_values) {
2011 r = cachemem_maintain(&cache->values, size);
2012 if (r < 0)
2013 return r;
2014
2015 sync_values = r;
2016 } else
2017 cache->values.active = false;
2018
2019 if (cache->hashmap->dirty) {
2020 if (cache->keys.active)
2021 sync_keys = true;
2022 if (cache->values.active)
2023 sync_values = true;
2024
2025 cache->hashmap->dirty = false;
2026 }
2027
2028 if (sync_keys || sync_values) {
2029 unsigned i, idx;
2030 Iterator iter;
2031
2032 i = 0;
2033 HASHMAP_FOREACH_IDX(idx, cache->hashmap, iter) {
2034 struct hashmap_base_entry *e;
2035
2036 e = bucket_at(cache->hashmap, idx);
2037
2038 if (sync_keys)
2039 cache->keys.ptr[i] = e->key;
2040 if (sync_values)
2041 cache->values.ptr[i] = entry_value(cache->hashmap, e);
2042 i++;
2043 }
2044 }
2045
2046 if (res_keys)
2047 *res_keys = cache->keys.ptr;
2048 if (res_values)
2049 *res_values = cache->values.ptr;
2050 if (res_n_entries)
2051 *res_n_entries = size;
2052
2053 return 0;
2054}
2055
2056IteratedCache* iterated_cache_free(IteratedCache *cache) {
2057 if (cache) {
2058 free(cache->keys.ptr);
2059 free(cache->values.ptr);
2060 }
2061
2062 return mfree(cache);
2063}
2064
2065int set_strjoin(Set *s, const char *separator, bool wrap_with_separator, char **ret) {
2066 _cleanup_free_ char *str = NULL;
2067 size_t separator_len, len = 0;
2068 const char *value;
2069 bool first;
2070
2071 assert(ret);
2072
2073 if (set_isempty(s)) {
2074 *ret = NULL;
2075 return 0;
2076 }
2077
2078 separator_len = strlen_ptr(separator);
2079
2080 if (separator_len == 0)
2081 wrap_with_separator = false;
2082
2083 first = !wrap_with_separator;
2084
2085 SET_FOREACH(value, s) {
2086 size_t l = strlen_ptr(value);
2087
2088 if (l == 0)
2089 continue;
2090
2091 if (!GREEDY_REALLOC(str, len + l + (first ? 0 : separator_len) + (wrap_with_separator ? separator_len : 0) + 1))
2092 return -ENOMEM;
2093
2094 if (separator_len > 0 && !first) {
2095 memcpy(str + len, separator, separator_len);
2096 len += separator_len;
2097 }
2098
2099 memcpy(str + len, value, l);
2100 len += l;
2101 first = false;
2102 }
2103
2104 if (wrap_with_separator) {
2105 memcpy(str + len, separator, separator_len);
2106 len += separator_len;
2107 }
2108
2109 str[len] = '\0';
2110
2111 *ret = TAKE_PTR(str);
2112 return 0;
2113}
2114
2115bool set_equal(Set *a, Set *b) {
2116 void *p;
2117
2118 /* Checks whether each entry of 'a' is also in 'b' and vice versa, i.e. the two sets contain the same
2119 * entries */
2120
2121 if (a == b)
2122 return true;
2123
2124 if (set_isempty(a) && set_isempty(b))
2125 return true;
2126
2127 if (set_size(a) != set_size(b)) /* Cheap check that hopefully catches a lot of inequality cases
2128 * already */
2129 return false;
2130
2131 SET_FOREACH(p, a)
2132 if (!set_contains(b, p))
2133 return false;
2134
2135 /* If we have the same hashops, then we don't need to check things backwards given we compared the
2136 * size and that all of a is in b. */
2137 if (a->b.hash_ops == b->b.hash_ops)
2138 return true;
2139
2140 SET_FOREACH(p, b)
2141 if (!set_contains(a, p))
2142 return false;
2143
2144 return true;
2145}
2146
2147static bool set_fnmatch_one(Set *patterns, const char *needle) {
2148 const char *p;
2149
2150 assert(needle);
2151
2152 /* Any failure of fnmatch() is treated as equivalent to FNM_NOMATCH, i.e. as non-matching pattern */
2153
2154 SET_FOREACH(p, patterns)
2155 if (fnmatch(p, needle, 0) == 0)
2156 return true;
2157
2158 return false;
2159}
2160
2161bool set_fnmatch(Set *include_patterns, Set *exclude_patterns, const char *needle) {
2162 assert(needle);
2163
2164 if (set_fnmatch_one(exclude_patterns, needle))
2165 return false;
2166
2167 if (set_isempty(include_patterns))
2168 return true;
2169
2170 return set_fnmatch_one(include_patterns, needle);
2171}
2172
2173static int hashmap_entry_compare(
2174 struct hashmap_base_entry * const *a,
2175 struct hashmap_base_entry * const *b,
2176 compare_func_t compare) {
2177
2178 assert(a && *a);
2179 assert(b && *b);
2180 assert(compare);
2181
2182 return compare((*a)->key, (*b)->key);
2183}
2184
2185static int _hashmap_dump_entries_sorted(
2186 HashmapBase *h,
2187 void ***ret,
2188 size_t *ret_n) {
2189 _cleanup_free_ void **entries = NULL;
2190 Iterator iter;
2191 unsigned idx;
2192 size_t n = 0;
2193
2194 assert(ret);
2195 assert(ret_n);
2196
2197 if (_hashmap_size(h) == 0) {
2198 *ret = NULL;
2199 *ret_n = 0;
2200 return 0;
2201 }
2202
2203 /* We append one more element than needed so that the resulting array can be used as a strv. We
2204 * don't count this entry in the returned size. */
2205 entries = new(void*, _hashmap_size(h) + 1);
2206 if (!entries)
2207 return -ENOMEM;
2208
2209 HASHMAP_FOREACH_IDX(idx, h, iter)
2210 entries[n++] = bucket_at(h, idx);
2211
2212 assert(n == _hashmap_size(h));
2213 entries[n] = NULL;
2214
2215 typesafe_qsort_r((struct hashmap_base_entry**) entries, n,
2216 hashmap_entry_compare, h->hash_ops->compare);
2217
2218 *ret = TAKE_PTR(entries);
2219 *ret_n = n;
2220 return 0;
2221}
2222
2223int _hashmap_dump_keys_sorted(HashmapBase *h, void ***ret, size_t *ret_n) {
2224 _cleanup_free_ void **entries = NULL;
2225 size_t n;
2226 int r;
2227
2228 assert(ret);
2229
2230 r = _hashmap_dump_entries_sorted(h, &entries, &n);
2231 if (r < 0)
2232 return r;
2233
2234 /* Reuse the array. */
2235 FOREACH_ARRAY(e, entries, n)
2236 *e = (void*) (*(struct hashmap_base_entry**) e)->key;
2237
2238 *ret = TAKE_PTR(entries);
2239 if (ret_n)
2240 *ret_n = n;
2241 return 0;
2242}
2243
2244int _hashmap_dump_sorted(HashmapBase *h, void ***ret, size_t *ret_n) {
2245 _cleanup_free_ void **entries = NULL;
2246 size_t n;
2247 int r;
2248
2249 assert(ret);
2250
2251 r = _hashmap_dump_entries_sorted(h, &entries, &n);
2252 if (r < 0)
2253 return r;
2254
2255 /* Reuse the array. */
2256 FOREACH_ARRAY(e, entries, n)
2257 *e = entry_value(h, *(struct hashmap_base_entry**) e);
2258
2259 *ret = TAKE_PTR(entries);
2260 if (ret_n)
2261 *ret_n = n;
2262 return 0;
2263}
Unnamed repository; edit this file 'description' to name the repository.