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