src/basic/hashmap.h

   1 /* SPDX-License-Identifier: LGPL-2.1+ */
   2 #pragma once
   3
   4 /***
   5   This file is part of systemd.
   6
   7   Copyright 2010 Lennart Poettering
   8   Copyright 2014 Michal Schmidt
   9 ***/
  10
  11 #include <limits.h>
  12 #include <stdbool.h>
  13 #include <stddef.h>
  14
  15 #include "hash-funcs.h"
  16 #include "macro.h"
  17 #include "util.h"
  18
  19 /*
  20  * A hash table implementation. As a minor optimization a NULL hashmap object
  21  * will be treated as empty hashmap for all read operations. That way it is not
  22  * necessary to instantiate an object for each Hashmap use.
  23  *
  24  * If ENABLE_DEBUG_HASHMAP is defined (by configuring with --enable-debug=hashmap),
  25  * the implemention will:
  26  * - store extra data for debugging and statistics (see tools/gdb-sd_dump_hashmaps.py)
  27  * - perform extra checks for invalid use of iterators
  28  */
  29
  30 #define HASH_KEY_SIZE 16
  31
  32 /* The base type for all hashmap and set types. Many functions in the
  33  * implementation take (HashmapBase*) parameters and are run-time polymorphic,
  34  * though the API is not meant to be polymorphic (do not call functions
  35  * internal_*() directly). */
  36 typedef struct HashmapBase HashmapBase;
  37
  38 /* Specific hashmap/set types */
  39 typedef struct Hashmap Hashmap;               /* Maps keys to values */
  40 typedef struct OrderedHashmap OrderedHashmap; /* Like Hashmap, but also remembers entry insertion order */
  41 typedef struct Set Set;                       /* Stores just keys */
  42
  43 typedef struct IteratedCache IteratedCache;   /* Caches the iterated order of one of the above */
  44
  45 /* Ideally the Iterator would be an opaque struct, but it is instantiated
  46  * by hashmap users, so the definition has to be here. Do not use its fields
  47  * directly. */
  48 typedef struct {
  49         unsigned idx;         /* index of an entry to be iterated next */
  50         const void *next_key; /* expected value of that entry's key pointer */
  51 #if ENABLE_DEBUG_HASHMAP
  52         unsigned put_count;   /* hashmap's put_count recorded at start of iteration */
  53         unsigned rem_count;   /* hashmap's rem_count in previous iteration */
  54         unsigned prev_idx;    /* idx in previous iteration */
  55 #endif
  56 } Iterator;
  57
  58 #define _IDX_ITERATOR_FIRST (UINT_MAX - 1)
  59 #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL })
  60
  61 /* Macros for type checking */
  62 #define PTR_COMPATIBLE_WITH_HASHMAP_BASE(h) \
  63         (__builtin_types_compatible_p(typeof(h), HashmapBase*) || \
  64          __builtin_types_compatible_p(typeof(h), Hashmap*) || \
  65          __builtin_types_compatible_p(typeof(h), OrderedHashmap*) || \
  66          __builtin_types_compatible_p(typeof(h), Set*))
  67
  68 #define PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h) \
  69         (__builtin_types_compatible_p(typeof(h), Hashmap*) || \
  70          __builtin_types_compatible_p(typeof(h), OrderedHashmap*)) \
  71
  72 #define HASHMAP_BASE(h) \
  73         __builtin_choose_expr(PTR_COMPATIBLE_WITH_HASHMAP_BASE(h), \
  74                 (HashmapBase*)(h), \
  75                 (void)0)
  76
  77 #define PLAIN_HASHMAP(h) \
  78         __builtin_choose_expr(PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h), \
  79                 (Hashmap*)(h), \
  80                 (void)0)
  81
  82 #if ENABLE_DEBUG_HASHMAP
  83 # define HASHMAP_DEBUG_PARAMS , const char *func, const char *file, int line
  84 # define HASHMAP_DEBUG_SRC_ARGS   , __func__, __FILE__, __LINE__
  85 # define HASHMAP_DEBUG_PASS_ARGS   , func, file, line
  86 #else
  87 # define HASHMAP_DEBUG_PARAMS
  88 # define HASHMAP_DEBUG_SRC_ARGS
  89 # define HASHMAP_DEBUG_PASS_ARGS
  90 #endif
  91
  92 Hashmap *internal_hashmap_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
  93 OrderedHashmap *internal_ordered_hashmap_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
  94 #define hashmap_new(ops) internal_hashmap_new(ops  HASHMAP_DEBUG_SRC_ARGS)
  95 #define ordered_hashmap_new(ops) internal_ordered_hashmap_new(ops  HASHMAP_DEBUG_SRC_ARGS)
  96
  97 HashmapBase *internal_hashmap_free(HashmapBase *h);
  98 static inline Hashmap *hashmap_free(Hashmap *h) {
  99         return (void*)internal_hashmap_free(HASHMAP_BASE(h));
 100 }
 101 static inline OrderedHashmap *ordered_hashmap_free(OrderedHashmap *h) {
 102         return (void*)internal_hashmap_free(HASHMAP_BASE(h));
 103 }
 104
 105 HashmapBase *internal_hashmap_free_free(HashmapBase *h);
 106 static inline Hashmap *hashmap_free_free(Hashmap *h) {
 107         return (void*)internal_hashmap_free_free(HASHMAP_BASE(h));
 108 }
 109 static inline OrderedHashmap *ordered_hashmap_free_free(OrderedHashmap *h) {
 110         return (void*)internal_hashmap_free_free(HASHMAP_BASE(h));
 111 }
 112
 113 Hashmap *hashmap_free_free_free(Hashmap *h);
 114 static inline OrderedHashmap *ordered_hashmap_free_free_free(OrderedHashmap *h) {
 115         return (void*)hashmap_free_free_free(PLAIN_HASHMAP(h));
 116 }
 117
 118 IteratedCache *iterated_cache_free(IteratedCache *cache);
 119 int iterated_cache_get(IteratedCache *cache, const void ***res_keys, const void ***res_values, unsigned *res_n_entries);
 120
 121 HashmapBase *internal_hashmap_copy(HashmapBase *h);
 122 static inline Hashmap *hashmap_copy(Hashmap *h) {
 123         return (Hashmap*) internal_hashmap_copy(HASHMAP_BASE(h));
 124 }
 125 static inline OrderedHashmap *ordered_hashmap_copy(OrderedHashmap *h) {
 126         return (OrderedHashmap*) internal_hashmap_copy(HASHMAP_BASE(h));
 127 }
 128
 129 int internal_hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
 130 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS);
 131 #define hashmap_ensure_allocated(h, ops) internal_hashmap_ensure_allocated(h, ops  HASHMAP_DEBUG_SRC_ARGS)
 132 #define ordered_hashmap_ensure_allocated(h, ops) internal_ordered_hashmap_ensure_allocated(h, ops  HASHMAP_DEBUG_SRC_ARGS)
 133
 134 IteratedCache *internal_hashmap_iterated_cache_new(HashmapBase *h);
 135 static inline IteratedCache *hashmap_iterated_cache_new(Hashmap *h) {
 136         return (IteratedCache*) internal_hashmap_iterated_cache_new(HASHMAP_BASE(h));
 137 }
 138 static inline IteratedCache *ordered_hashmap_iterated_cache_new(OrderedHashmap *h) {
 139         return (IteratedCache*) internal_hashmap_iterated_cache_new(HASHMAP_BASE(h));
 140 }
 141
 142 int hashmap_put(Hashmap *h, const void *key, void *value);
 143 static inline int ordered_hashmap_put(OrderedHashmap *h, const void *key, void *value) {
 144         return hashmap_put(PLAIN_HASHMAP(h), key, value);
 145 }
 146
 147 int hashmap_update(Hashmap *h, const void *key, void *value);
 148 static inline int ordered_hashmap_update(OrderedHashmap *h, const void *key, void *value) {
 149         return hashmap_update(PLAIN_HASHMAP(h), key, value);
 150 }
 151
 152 int hashmap_replace(Hashmap *h, const void *key, void *value);
 153 static inline int ordered_hashmap_replace(OrderedHashmap *h, const void *key, void *value) {
 154         return hashmap_replace(PLAIN_HASHMAP(h), key, value);
 155 }
 156
 157 void *internal_hashmap_get(HashmapBase *h, const void *key);
 158 static inline void *hashmap_get(Hashmap *h, const void *key) {
 159         return internal_hashmap_get(HASHMAP_BASE(h), key);
 160 }
 161 static inline void *ordered_hashmap_get(OrderedHashmap *h, const void *key) {
 162         return internal_hashmap_get(HASHMAP_BASE(h), key);
 163 }
 164
 165 void *hashmap_get2(Hashmap *h, const void *key, void **rkey);
 166 static inline void *ordered_hashmap_get2(OrderedHashmap *h, const void *key, void **rkey) {
 167         return hashmap_get2(PLAIN_HASHMAP(h), key, rkey);
 168 }
 169
 170 bool internal_hashmap_contains(HashmapBase *h, const void *key);
 171 static inline bool hashmap_contains(Hashmap *h, const void *key) {
 172         return internal_hashmap_contains(HASHMAP_BASE(h), key);
 173 }
 174 static inline bool ordered_hashmap_contains(OrderedHashmap *h, const void *key) {
 175         return internal_hashmap_contains(HASHMAP_BASE(h), key);
 176 }
 177
 178 void *internal_hashmap_remove(HashmapBase *h, const void *key);
 179 static inline void *hashmap_remove(Hashmap *h, const void *key) {
 180         return internal_hashmap_remove(HASHMAP_BASE(h), key);
 181 }
 182 static inline void *ordered_hashmap_remove(OrderedHashmap *h, const void *key) {
 183         return internal_hashmap_remove(HASHMAP_BASE(h), key);
 184 }
 185
 186 void *hashmap_remove2(Hashmap *h, const void *key, void **rkey);
 187 static inline void *ordered_hashmap_remove2(OrderedHashmap *h, const void *key, void **rkey) {
 188         return hashmap_remove2(PLAIN_HASHMAP(h), key, rkey);
 189 }
 190
 191 void *hashmap_remove_value(Hashmap *h, const void *key, void *value);
 192 static inline void *ordered_hashmap_remove_value(OrderedHashmap *h, const void *key, void *value) {
 193         return hashmap_remove_value(PLAIN_HASHMAP(h), key, value);
 194 }
 195
 196 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);
 197 static inline int ordered_hashmap_remove_and_put(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
 198         return hashmap_remove_and_put(PLAIN_HASHMAP(h), old_key, new_key, value);
 199 }
 200
 201 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value);
 202 static inline int ordered_hashmap_remove_and_replace(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
 203         return hashmap_remove_and_replace(PLAIN_HASHMAP(h), old_key, new_key, value);
 204 }
 205
 206 /* Since merging data from a OrderedHashmap into a Hashmap or vice-versa
 207  * should just work, allow this by having looser type-checking here. */
 208 int internal_hashmap_merge(Hashmap *h, Hashmap *other);
 209 #define hashmap_merge(h, other) internal_hashmap_merge(PLAIN_HASHMAP(h), PLAIN_HASHMAP(other))
 210 #define ordered_hashmap_merge(h, other) hashmap_merge(h, other)
 211
 212 int internal_hashmap_reserve(HashmapBase *h, unsigned entries_add);
 213 static inline int hashmap_reserve(Hashmap *h, unsigned entries_add) {
 214         return internal_hashmap_reserve(HASHMAP_BASE(h), entries_add);
 215 }
 216 static inline int ordered_hashmap_reserve(OrderedHashmap *h, unsigned entries_add) {
 217         return internal_hashmap_reserve(HASHMAP_BASE(h), entries_add);
 218 }
 219
 220 int internal_hashmap_move(HashmapBase *h, HashmapBase *other);
 221 /* Unlike hashmap_merge, hashmap_move does not allow mixing the types. */
 222 static inline int hashmap_move(Hashmap *h, Hashmap *other) {
 223         return internal_hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
 224 }
 225 static inline int ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
 226         return internal_hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
 227 }
 228
 229 int internal_hashmap_move_one(HashmapBase *h, HashmapBase *other, const void *key);
 230 static inline int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 231         return internal_hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
 232 }
 233 static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) {
 234         return internal_hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
 235 }
 236
 237 unsigned internal_hashmap_size(HashmapBase *h) _pure_;
 238 static inline unsigned hashmap_size(Hashmap *h) {
 239         return internal_hashmap_size(HASHMAP_BASE(h));
 240 }
 241 static inline unsigned ordered_hashmap_size(OrderedHashmap *h) {
 242         return internal_hashmap_size(HASHMAP_BASE(h));
 243 }
 244
 245 static inline bool hashmap_isempty(Hashmap *h) {
 246         return hashmap_size(h) == 0;
 247 }
 248 static inline bool ordered_hashmap_isempty(OrderedHashmap *h) {
 249         return ordered_hashmap_size(h) == 0;
 250 }
 251
 252 unsigned internal_hashmap_buckets(HashmapBase *h) _pure_;
 253 static inline unsigned hashmap_buckets(Hashmap *h) {
 254         return internal_hashmap_buckets(HASHMAP_BASE(h));
 255 }
 256 static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) {
 257         return internal_hashmap_buckets(HASHMAP_BASE(h));
 258 }
 259
 260 bool internal_hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key);
 261 static inline bool hashmap_iterate(Hashmap *h, Iterator *i, void **value, const void **key) {
 262         return internal_hashmap_iterate(HASHMAP_BASE(h), i, value, key);
 263 }
 264 static inline bool ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, void **value, const void **key) {
 265         return internal_hashmap_iterate(HASHMAP_BASE(h), i, value, key);
 266 }
 267
 268 void internal_hashmap_clear(HashmapBase *h);
 269 static inline void hashmap_clear(Hashmap *h) {
 270         internal_hashmap_clear(HASHMAP_BASE(h));
 271 }
 272 static inline void ordered_hashmap_clear(OrderedHashmap *h) {
 273         internal_hashmap_clear(HASHMAP_BASE(h));
 274 }
 275
 276 void internal_hashmap_clear_free(HashmapBase *h);
 277 static inline void hashmap_clear_free(Hashmap *h) {
 278         internal_hashmap_clear_free(HASHMAP_BASE(h));
 279 }
 280 static inline void ordered_hashmap_clear_free(OrderedHashmap *h) {
 281         internal_hashmap_clear_free(HASHMAP_BASE(h));
 282 }
 283
 284 void hashmap_clear_free_free(Hashmap *h);
 285 static inline void ordered_hashmap_clear_free_free(OrderedHashmap *h) {
 286         hashmap_clear_free_free(PLAIN_HASHMAP(h));
 287 }
 288
 289 /*
 290  * Note about all *_first*() functions
 291  *
 292  * For plain Hashmaps and Sets the order of entries is undefined.
 293  * The functions find whatever entry is first in the implementation
 294  * internal order.
 295  *
 296  * Only for OrderedHashmaps the order is well defined and finding
 297  * the first entry is O(1).
 298  */
 299
 300 void *internal_hashmap_steal_first(HashmapBase *h);
 301 static inline void *hashmap_steal_first(Hashmap *h) {
 302         return internal_hashmap_steal_first(HASHMAP_BASE(h));
 303 }
 304 static inline void *ordered_hashmap_steal_first(OrderedHashmap *h) {
 305         return internal_hashmap_steal_first(HASHMAP_BASE(h));
 306 }
 307
 308 void *internal_hashmap_steal_first_key(HashmapBase *h);
 309 static inline void *hashmap_steal_first_key(Hashmap *h) {
 310         return internal_hashmap_steal_first_key(HASHMAP_BASE(h));
 311 }
 312 static inline void *ordered_hashmap_steal_first_key(OrderedHashmap *h) {
 313         return internal_hashmap_steal_first_key(HASHMAP_BASE(h));
 314 }
 315
 316 void *internal_hashmap_first_key(HashmapBase *h) _pure_;
 317 static inline void *hashmap_first_key(Hashmap *h) {
 318         return internal_hashmap_first_key(HASHMAP_BASE(h));
 319 }
 320 static inline void *ordered_hashmap_first_key(OrderedHashmap *h) {
 321         return internal_hashmap_first_key(HASHMAP_BASE(h));
 322 }
 323
 324 void *internal_hashmap_first(HashmapBase *h) _pure_;
 325 static inline void *hashmap_first(Hashmap *h) {
 326         return internal_hashmap_first(HASHMAP_BASE(h));
 327 }
 328 static inline void *ordered_hashmap_first(OrderedHashmap *h) {
 329         return internal_hashmap_first(HASHMAP_BASE(h));
 330 }
 331
 332 #define hashmap_clear_with_destructor(_s, _f)                   \
 333         ({                                                      \
 334                 void *_item;                                    \
 335                 while ((_item = hashmap_steal_first(_s)))       \
 336                         _f(_item);                              \
 337         })
 338 #define hashmap_free_with_destructor(_s, _f)                    \
 339         ({                                                      \
 340                 hashmap_clear_with_destructor(_s, _f);          \
 341                 hashmap_free(_s);                               \
 342         })
 343 #define ordered_hashmap_clear_with_destructor(_s, _f)                   \
 344         ({                                                              \
 345                 void *_item;                                            \
 346                 while ((_item = ordered_hashmap_steal_first(_s)))       \
 347                         _f(_item);                                      \
 348         })
 349 #define ordered_hashmap_free_with_destructor(_s, _f)                    \
 350         ({                                                              \
 351                 ordered_hashmap_clear_with_destructor(_s, _f);          \
 352                 ordered_hashmap_free(_s);                               \
 353         })
 354
 355 /* no hashmap_next */
 356 void *ordered_hashmap_next(OrderedHashmap *h, const void *key);
 357
 358 char **internal_hashmap_get_strv(HashmapBase *h);
 359 static inline char **hashmap_get_strv(Hashmap *h) {
 360         return internal_hashmap_get_strv(HASHMAP_BASE(h));
 361 }
 362 static inline char **ordered_hashmap_get_strv(OrderedHashmap *h) {
 363         return internal_hashmap_get_strv(HASHMAP_BASE(h));
 364 }
 365
 366 /*
 367  * Hashmaps are iterated in unpredictable order.
 368  * OrderedHashmaps are an exception to this. They are iterated in the order
 369  * the entries were inserted.
 370  * It is safe to remove the current entry.
 371  */
 372 #define HASHMAP_FOREACH(e, h, i) \
 373         for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), NULL); )
 374
 375 #define ORDERED_HASHMAP_FOREACH(e, h, i) \
 376         for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), NULL); )
 377
 378 #define HASHMAP_FOREACH_KEY(e, k, h, i) \
 379         for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
 380
 381 #define ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \
 382         for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
 383
 384 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
 385 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free);
 386 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free_free);
 387 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free);
 388 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free);
 389 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free_free);
 390
 391 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
 392 #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
 393 #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)
 394 #define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep)
 395 #define _cleanup_ordered_hashmap_free_free_ _cleanup_(ordered_hashmap_free_freep)
 396 #define _cleanup_ordered_hashmap_free_free_free_ _cleanup_(ordered_hashmap_free_free_freep)
 397
 398 DEFINE_TRIVIAL_CLEANUP_FUNC(IteratedCache*, iterated_cache_free);
 399
 400 #define _cleanup_iterated_cache_free_ _cleanup_(iterated_cache_freep)