src/basic/hashmap.h

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