src/basic/hashmap.h

   1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
   2 #pragma once
   3
   4 #include "forward.h"
   5 #include "hash-funcs.h"
   6 #include "iterator.h"
   7
   8 /*
   9  * A hash table implementation. As a minor optimization a NULL hashmap object
  10  * will be treated as empty hashmap for all read operations. That way it is not
  11  * necessary to instantiate an object for each Hashmap use.
  12  *
  13  * If ENABLE_DEBUG_HASHMAP is defined (by configuring with -Ddebug-extra=hashmap),
  14  * the implementation will:
  15  * - store extra data for debugging and statistics (see tools/gdb-sd_dump_hashmaps.py)
  16  * - perform extra checks for invalid use of iterators
  17  */
  18
  19 #define HASH_KEY_SIZE 16
  20
  21
  22 /* The base type for all hashmap and set types. Many functions in the implementation take (HashmapBase*)
  23  * parameters and are run-time polymorphic, though the API is not meant to be polymorphic (do not call
  24  * underscore-prefixed functions directly). */
  25 typedef struct HashmapBase HashmapBase;
  26
  27 /* Specific hashmap/set types */
  28 typedef struct Hashmap Hashmap;               /* Maps keys to values */
  29 typedef struct OrderedHashmap OrderedHashmap; /* Like Hashmap, but also remembers entry insertion order */
  30 typedef struct Set Set;                       /* Stores just keys */
  31
  32 typedef struct IteratedCache IteratedCache;   /* Caches the iterated order of one of the above */
  33
  34 /* Macros for type checking */
  35 #define PTR_COMPATIBLE_WITH_HASHMAP_BASE(h) \
  36         (__builtin_types_compatible_p(typeof(h), HashmapBase*) || \
  37          __builtin_types_compatible_p(typeof(h), Hashmap*) || \
  38          __builtin_types_compatible_p(typeof(h), OrderedHashmap*) || \
  39          __builtin_types_compatible_p(typeof(h), Set*))
  40
  41 #define PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h) \
  42         (__builtin_types_compatible_p(typeof(h), Hashmap*) || \
  43          __builtin_types_compatible_p(typeof(h), OrderedHashmap*)) \
  44
  45 #define HASHMAP_BASE(h) \
  46         __builtin_choose_expr(PTR_COMPATIBLE_WITH_HASHMAP_BASE(h), \
  47                 (HashmapBase*)(h), \
  48                 (void)0)
  49
  50 #define PLAIN_HASHMAP(h) \
  51         __builtin_choose_expr(PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h), \
  52                 (Hashmap*)(h), \
  53                 (void)0)
  54
  55 Hashmap* hashmap_new(const struct hash_ops *hash_ops);
  56 OrderedHashmap* ordered_hashmap_new(const struct hash_ops *hash_ops);
  57
  58 #define hashmap_free_and_replace(a, b)                          \
  59         free_and_replace_full(a, b, hashmap_free)
  60 #define ordered_hashmap_free_and_replace(a, b)                  \
  61         free_and_replace_full(a, b, ordered_hashmap_free)
  62
  63 HashmapBase* _hashmap_free(HashmapBase *h);
  64 static inline Hashmap* hashmap_free(Hashmap *h) {
  65         return (void*) _hashmap_free(HASHMAP_BASE(h));
  66 }
  67 static inline OrderedHashmap* ordered_hashmap_free(OrderedHashmap *h) {
  68         return (void*) _hashmap_free(HASHMAP_BASE(h));
  69 }
  70
  71 IteratedCache* iterated_cache_free(IteratedCache *cache);
  72 int iterated_cache_get(IteratedCache *cache, const void ***res_keys, const void ***res_values, unsigned *res_n_entries);
  73
  74 HashmapBase* _hashmap_copy(HashmapBase *h);
  75 static inline Hashmap* hashmap_copy(Hashmap *h) {
  76         return (Hashmap*) _hashmap_copy(HASHMAP_BASE(h));
  77 }
  78 static inline OrderedHashmap* ordered_hashmap_copy(OrderedHashmap *h) {
  79         return (OrderedHashmap*) _hashmap_copy(HASHMAP_BASE(h));
  80 }
  81
  82 int hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops);
  83 int hashmap_ensure_put(Hashmap **h, const struct hash_ops *hash_ops, const void *key, void *value);
  84 int ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops);
  85 int hashmap_ensure_replace(Hashmap **h, const struct hash_ops *hash_ops, const void *key, void *value);
  86
  87 int ordered_hashmap_ensure_put(OrderedHashmap **h, const struct hash_ops *hash_ops, const void *key, void *value);
  88 int ordered_hashmap_ensure_replace(OrderedHashmap **h, const struct hash_ops *hash_ops, const void *key, void *value);
  89
  90 IteratedCache* _hashmap_iterated_cache_new(HashmapBase *h);
  91 static inline IteratedCache* hashmap_iterated_cache_new(Hashmap *h) {
  92         return (IteratedCache*) _hashmap_iterated_cache_new(HASHMAP_BASE(h));
  93 }
  94 static inline IteratedCache* ordered_hashmap_iterated_cache_new(OrderedHashmap *h) {
  95         return (IteratedCache*) _hashmap_iterated_cache_new(HASHMAP_BASE(h));
  96 }
  97
  98 int hashmap_put(Hashmap *h, const void *key, void *value);
  99 static inline int ordered_hashmap_put(OrderedHashmap *h, const void *key, void *value) {
 100         return hashmap_put(PLAIN_HASHMAP(h), key, value);
 101 }
 102
 103 int hashmap_put_strdup_full(Hashmap **h, const struct hash_ops *hash_ops, const char *k, const char *v);
 104 static inline int hashmap_put_strdup(Hashmap **h, const char *k, const char *v) {
 105         return hashmap_put_strdup_full(h, &string_hash_ops_free_free, k, v);
 106 }
 107
 108 int hashmap_update(Hashmap *h, const void *key, void *value);
 109 static inline int ordered_hashmap_update(OrderedHashmap *h, const void *key, void *value) {
 110         return hashmap_update(PLAIN_HASHMAP(h), key, value);
 111 }
 112
 113 int hashmap_replace(Hashmap *h, const void *key, void *value);
 114 static inline int ordered_hashmap_replace(OrderedHashmap *h, const void *key, void *value) {
 115         return hashmap_replace(PLAIN_HASHMAP(h), key, value);
 116 }
 117
 118 void* _hashmap_get(HashmapBase *h, const void *key);
 119 static inline void *hashmap_get(Hashmap *h, const void *key) {
 120         return _hashmap_get(HASHMAP_BASE(h), key);
 121 }
 122 static inline void *ordered_hashmap_get(OrderedHashmap *h, const void *key) {
 123         return _hashmap_get(HASHMAP_BASE(h), key);
 124 }
 125
 126 void* hashmap_get2(Hashmap *h, const void *key, void **rkey);
 127 static inline void *ordered_hashmap_get2(OrderedHashmap *h, const void *key, void **rkey) {
 128         return hashmap_get2(PLAIN_HASHMAP(h), key, rkey);
 129 }
 130
 131 bool _hashmap_contains(HashmapBase *h, const void *key);
 132 static inline bool hashmap_contains(Hashmap *h, const void *key) {
 133         return _hashmap_contains(HASHMAP_BASE(h), key);
 134 }
 135 static inline bool ordered_hashmap_contains(OrderedHashmap *h, const void *key) {
 136         return _hashmap_contains(HASHMAP_BASE(h), key);
 137 }
 138
 139 void* _hashmap_remove(HashmapBase *h, const void *key);
 140 static inline void *hashmap_remove(Hashmap *h, const void *key) {
 141         return _hashmap_remove(HASHMAP_BASE(h), key);
 142 }
 143 static inline void *ordered_hashmap_remove(OrderedHashmap *h, const void *key) {
 144         return _hashmap_remove(HASHMAP_BASE(h), key);
 145 }
 146
 147 void* hashmap_remove2(Hashmap *h, const void *key, void **rkey);
 148 static inline void *ordered_hashmap_remove2(OrderedHashmap *h, const void *key, void **rkey) {
 149         return hashmap_remove2(PLAIN_HASHMAP(h), key, rkey);
 150 }
 151
 152 void* _hashmap_remove_value(HashmapBase *h, const void *key, void *value);
 153 static inline void *hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 154         return _hashmap_remove_value(HASHMAP_BASE(h), key, value);
 155 }
 156
 157 static inline void* ordered_hashmap_remove_value(OrderedHashmap *h, const void *key, void *value) {
 158         return hashmap_remove_value(PLAIN_HASHMAP(h), key, value);
 159 }
 160
 161 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);
 162 static inline int ordered_hashmap_remove_and_put(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
 163         return hashmap_remove_and_put(PLAIN_HASHMAP(h), old_key, new_key, value);
 164 }
 165
 166 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value);
 167 static inline int ordered_hashmap_remove_and_replace(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
 168         return hashmap_remove_and_replace(PLAIN_HASHMAP(h), old_key, new_key, value);
 169 }
 170
 171 /* Since merging data from an OrderedHashmap into a Hashmap or vice-versa
 172  * should just work, allow this by having looser type-checking here. */
 173 int _hashmap_merge(Hashmap *h, Hashmap *other);
 174 #define hashmap_merge(h, other) _hashmap_merge(PLAIN_HASHMAP(h), PLAIN_HASHMAP(other))
 175 #define ordered_hashmap_merge(h, other) hashmap_merge(h, other)
 176
 177 int _hashmap_reserve(HashmapBase *h, unsigned entries_add);
 178 static inline int hashmap_reserve(Hashmap *h, unsigned entries_add) {
 179         return _hashmap_reserve(HASHMAP_BASE(h), entries_add);
 180 }
 181 static inline int ordered_hashmap_reserve(OrderedHashmap *h, unsigned entries_add) {
 182         return _hashmap_reserve(HASHMAP_BASE(h), entries_add);
 183 }
 184
 185 int _hashmap_move(HashmapBase *h, HashmapBase *other);
 186 /* Unlike hashmap_merge, hashmap_move does not allow mixing the types. */
 187 static inline int hashmap_move(Hashmap *h, Hashmap *other) {
 188         return _hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
 189 }
 190 static inline int ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
 191         return _hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
 192 }
 193
 194 int _hashmap_move_one(HashmapBase *h, HashmapBase *other, const void *key);
 195 static inline int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 196         return _hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
 197 }
 198 static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) {
 199         return _hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
 200 }
 201
 202 unsigned _hashmap_size(HashmapBase *h) _pure_;
 203 static inline unsigned hashmap_size(Hashmap *h) {
 204         return _hashmap_size(HASHMAP_BASE(h));
 205 }
 206 static inline unsigned ordered_hashmap_size(OrderedHashmap *h) {
 207         return _hashmap_size(HASHMAP_BASE(h));
 208 }
 209
 210 static inline bool hashmap_isempty(Hashmap *h) {
 211         return hashmap_size(h) == 0;
 212 }
 213 static inline bool ordered_hashmap_isempty(OrderedHashmap *h) {
 214         return ordered_hashmap_size(h) == 0;
 215 }
 216
 217 unsigned _hashmap_buckets(HashmapBase *h) _pure_;
 218 static inline unsigned hashmap_buckets(Hashmap *h) {
 219         return _hashmap_buckets(HASHMAP_BASE(h));
 220 }
 221 static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) {
 222         return _hashmap_buckets(HASHMAP_BASE(h));
 223 }
 224
 225 bool _hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key);
 226 static inline bool hashmap_iterate(Hashmap *h, Iterator *i, void **value, const void **key) {
 227         return _hashmap_iterate(HASHMAP_BASE(h), i, value, key);
 228 }
 229 static inline bool ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, void **value, const void **key) {
 230         return _hashmap_iterate(HASHMAP_BASE(h), i, value, key);
 231 }
 232
 233 void _hashmap_clear(HashmapBase *h);
 234 static inline void hashmap_clear(Hashmap *h) {
 235         _hashmap_clear(HASHMAP_BASE(h));
 236 }
 237 static inline void ordered_hashmap_clear(OrderedHashmap *h) {
 238         _hashmap_clear(HASHMAP_BASE(h));
 239 }
 240
 241 /*
 242  * Note about all *_first*() functions
 243  *
 244  * For plain Hashmaps and Sets the order of entries is undefined.
 245  * The functions find whatever entry is first in the implementation
 246  * internal order.
 247  *
 248  * Only for OrderedHashmaps the order is well defined and finding
 249  * the first entry is O(1).
 250  */
 251
 252 void *_hashmap_first_key_and_value(HashmapBase *h, bool remove, void **ret_key);
 253 static inline void *hashmap_steal_first_key_and_value(Hashmap *h, void **ret) {
 254         return _hashmap_first_key_and_value(HASHMAP_BASE(h), true, ret);
 255 }
 256 static inline void *ordered_hashmap_steal_first_key_and_value(OrderedHashmap *h, void **ret) {
 257         return _hashmap_first_key_and_value(HASHMAP_BASE(h), true, ret);
 258 }
 259 static inline void *hashmap_first_key_and_value(Hashmap *h, void **ret) {
 260         return _hashmap_first_key_and_value(HASHMAP_BASE(h), false, ret);
 261 }
 262 static inline void *ordered_hashmap_first_key_and_value(OrderedHashmap *h, void **ret) {
 263         return _hashmap_first_key_and_value(HASHMAP_BASE(h), false, ret);
 264 }
 265
 266 static inline void *hashmap_steal_first(Hashmap *h) {
 267         return _hashmap_first_key_and_value(HASHMAP_BASE(h), true, NULL);
 268 }
 269 static inline void *ordered_hashmap_steal_first(OrderedHashmap *h) {
 270         return _hashmap_first_key_and_value(HASHMAP_BASE(h), true, NULL);
 271 }
 272 static inline void *hashmap_first(Hashmap *h) {
 273         return _hashmap_first_key_and_value(HASHMAP_BASE(h), false, NULL);
 274 }
 275 static inline void *ordered_hashmap_first(OrderedHashmap *h) {
 276         return _hashmap_first_key_and_value(HASHMAP_BASE(h), false, NULL);
 277 }
 278
 279 static inline void *_hashmap_first_key(HashmapBase *h, bool remove) {
 280         void *key = NULL;
 281
 282         (void) _hashmap_first_key_and_value(HASHMAP_BASE(h), remove, &key);
 283         return key;
 284 }
 285 static inline void *hashmap_steal_first_key(Hashmap *h) {
 286         return _hashmap_first_key(HASHMAP_BASE(h), true);
 287 }
 288 static inline void *ordered_hashmap_steal_first_key(OrderedHashmap *h) {
 289         return _hashmap_first_key(HASHMAP_BASE(h), true);
 290 }
 291 static inline void *hashmap_first_key(Hashmap *h) {
 292         return _hashmap_first_key(HASHMAP_BASE(h), false);
 293 }
 294 static inline void *ordered_hashmap_first_key(OrderedHashmap *h) {
 295         return _hashmap_first_key(HASHMAP_BASE(h), false);
 296 }
 297
 298 /* no hashmap_next */
 299 void* ordered_hashmap_next(OrderedHashmap *h, const void *key);
 300
 301 char** _hashmap_get_strv(HashmapBase *h);
 302 static inline char** hashmap_get_strv(Hashmap *h) {
 303         return _hashmap_get_strv(HASHMAP_BASE(h));
 304 }
 305 static inline char** ordered_hashmap_get_strv(OrderedHashmap *h) {
 306         return _hashmap_get_strv(HASHMAP_BASE(h));
 307 }
 308
 309 int _hashmap_dump_sorted(HashmapBase *h, void ***ret, size_t *ret_n);
 310 static inline int hashmap_dump_sorted(Hashmap *h, void ***ret, size_t *ret_n) {
 311         return _hashmap_dump_sorted(HASHMAP_BASE(h), ret, ret_n);
 312 }
 313 static inline int ordered_hashmap_dump_sorted(OrderedHashmap *h, void ***ret, size_t *ret_n) {
 314         return _hashmap_dump_sorted(HASHMAP_BASE(h), ret, ret_n);
 315 }
 316 static inline int set_dump_sorted(Set *h, void ***ret, size_t *ret_n) {
 317         return _hashmap_dump_sorted(HASHMAP_BASE(h), ret, ret_n);
 318 }
 319
 320 int _hashmap_dump_keys_sorted(HashmapBase *h, void ***ret, size_t *ret_n);
 321 static inline int hashmap_dump_keys_sorted(Hashmap *h, void ***ret, size_t *ret_n) {
 322         return _hashmap_dump_keys_sorted(HASHMAP_BASE(h), ret, ret_n);
 323 }
 324 static inline int ordered_hashmap_dump_keys_sorted(OrderedHashmap *h, void ***ret, size_t *ret_n) {
 325         return _hashmap_dump_keys_sorted(HASHMAP_BASE(h), ret, ret_n);
 326 }
 327
 328 /*
 329  * Hashmaps are iterated in unpredictable order.
 330  * OrderedHashmaps are an exception to this. They are iterated in the order
 331  * the entries were inserted.
 332  * It is safe to remove the current entry.
 333  */
 334 #define _HASHMAP_BASE_FOREACH(e, h, i) \
 335         for (Iterator i = ITERATOR_FIRST; _hashmap_iterate((h), &i, (void**)&(e), NULL); )
 336 #define HASHMAP_BASE_FOREACH(e, h) \
 337         _HASHMAP_BASE_FOREACH(e, h, UNIQ_T(i, UNIQ))
 338
 339 #define _HASHMAP_FOREACH(e, h, i) \
 340         for (Iterator i = ITERATOR_FIRST; hashmap_iterate((h), &i, (void**)&(e), NULL); )
 341 #define HASHMAP_FOREACH(e, h) \
 342         _HASHMAP_FOREACH(e, h, UNIQ_T(i, UNIQ))
 343
 344 #define _ORDERED_HASHMAP_FOREACH(e, h, i) \
 345         for (Iterator i = ITERATOR_FIRST; ordered_hashmap_iterate((h), &i, (void**)&(e), NULL); )
 346 #define ORDERED_HASHMAP_FOREACH(e, h) \
 347         _ORDERED_HASHMAP_FOREACH(e, h, UNIQ_T(i, UNIQ))
 348
 349 #define _HASHMAP_BASE_FOREACH_KEY(e, k, h, i) \
 350         for (Iterator i = ITERATOR_FIRST; _hashmap_iterate((h), &i, (void**)&(e), (const void**) &(k)); )
 351 #define HASHMAP_BASE_FOREACH_KEY(e, k, h) \
 352         _HASHMAP_BASE_FOREACH_KEY(e, k, h, UNIQ_T(i, UNIQ))
 353
 354 #define _HASHMAP_FOREACH_KEY(e, k, h, i) \
 355         for (Iterator i = ITERATOR_FIRST; hashmap_iterate((h), &i, (void**)&(e), (const void**) &(k)); )
 356 #define HASHMAP_FOREACH_KEY(e, k, h) \
 357         _HASHMAP_FOREACH_KEY(e, k, h, UNIQ_T(i, UNIQ))
 358
 359 #define _ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \
 360         for (Iterator i = ITERATOR_FIRST; ordered_hashmap_iterate((h), &i, (void**)&(e), (const void**) &(k)); )
 361 #define ORDERED_HASHMAP_FOREACH_KEY(e, k, h) \
 362         _ORDERED_HASHMAP_FOREACH_KEY(e, k, h, UNIQ_T(i, UNIQ))
 363
 364 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
 365 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free);
 366
 367 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
 368 #define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep)
 369
 370 DEFINE_TRIVIAL_CLEANUP_FUNC(IteratedCache*, iterated_cache_free);
 371
 372 #define _cleanup_iterated_cache_free_ _cleanup_(iterated_cache_freep)
 373
 374 void hashmap_trim_pools(void);