1 /* SPDX-License-Identifier: LGPL-2.1+ */
5 Copyright © 2014 Michal Schmidt
12 #include "hash-funcs.h"
17 * A hash table implementation. As a minor optimization a NULL hashmap object
18 * will be treated as empty hashmap for all read operations. That way it is not
19 * necessary to instantiate an object for each Hashmap use.
21 * If ENABLE_DEBUG_HASHMAP is defined (by configuring with --enable-debug=hashmap),
22 * the implemention will:
23 * - store extra data for debugging and statistics (see tools/gdb-sd_dump_hashmaps.py)
24 * - perform extra checks for invalid use of iterators
27 #define HASH_KEY_SIZE 16
29 /* The base type for all hashmap and set types. Many functions in the
30 * implementation take (HashmapBase*) parameters and are run-time polymorphic,
31 * though the API is not meant to be polymorphic (do not call functions
32 * internal_*() directly). */
33 typedef struct HashmapBase HashmapBase
;
35 /* Specific hashmap/set types */
36 typedef struct Hashmap Hashmap
; /* Maps keys to values */
37 typedef struct OrderedHashmap OrderedHashmap
; /* Like Hashmap, but also remembers entry insertion order */
38 typedef struct Set Set
; /* Stores just keys */
40 typedef struct IteratedCache IteratedCache
; /* Caches the iterated order of one of the above */
42 /* Ideally the Iterator would be an opaque struct, but it is instantiated
43 * by hashmap users, so the definition has to be here. Do not use its fields
46 unsigned idx
; /* index of an entry to be iterated next */
47 const void *next_key
; /* expected value of that entry's key pointer */
48 #if ENABLE_DEBUG_HASHMAP
49 unsigned put_count
; /* hashmap's put_count recorded at start of iteration */
50 unsigned rem_count
; /* hashmap's rem_count in previous iteration */
51 unsigned prev_idx
; /* idx in previous iteration */
55 #define _IDX_ITERATOR_FIRST (UINT_MAX - 1)
56 #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL })
58 /* Macros for type checking */
59 #define PTR_COMPATIBLE_WITH_HASHMAP_BASE(h) \
60 (__builtin_types_compatible_p(typeof(h), HashmapBase*) || \
61 __builtin_types_compatible_p(typeof(h), Hashmap*) || \
62 __builtin_types_compatible_p(typeof(h), OrderedHashmap*) || \
63 __builtin_types_compatible_p(typeof(h), Set*))
65 #define PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h) \
66 (__builtin_types_compatible_p(typeof(h), Hashmap*) || \
67 __builtin_types_compatible_p(typeof(h), OrderedHashmap*)) \
69 #define HASHMAP_BASE(h) \
70 __builtin_choose_expr(PTR_COMPATIBLE_WITH_HASHMAP_BASE(h), \
74 #define PLAIN_HASHMAP(h) \
75 __builtin_choose_expr(PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h), \
79 #if ENABLE_DEBUG_HASHMAP
80 # define HASHMAP_DEBUG_PARAMS , const char *func, const char *file, int line
81 # define HASHMAP_DEBUG_SRC_ARGS , __func__, __FILE__, __LINE__
82 # define HASHMAP_DEBUG_PASS_ARGS , func, file, line
84 # define HASHMAP_DEBUG_PARAMS
85 # define HASHMAP_DEBUG_SRC_ARGS
86 # define HASHMAP_DEBUG_PASS_ARGS
89 Hashmap
*internal_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
90 OrderedHashmap
*internal_ordered_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
91 #define hashmap_new(ops) internal_hashmap_new(ops HASHMAP_DEBUG_SRC_ARGS)
92 #define ordered_hashmap_new(ops) internal_ordered_hashmap_new(ops HASHMAP_DEBUG_SRC_ARGS)
94 HashmapBase
*internal_hashmap_free(HashmapBase
*h
);
95 static inline Hashmap
*hashmap_free(Hashmap
*h
) {
96 return (void*)internal_hashmap_free(HASHMAP_BASE(h
));
98 static inline OrderedHashmap
*ordered_hashmap_free(OrderedHashmap
*h
) {
99 return (void*)internal_hashmap_free(HASHMAP_BASE(h
));
102 HashmapBase
*internal_hashmap_free_free(HashmapBase
*h
);
103 static inline Hashmap
*hashmap_free_free(Hashmap
*h
) {
104 return (void*)internal_hashmap_free_free(HASHMAP_BASE(h
));
106 static inline OrderedHashmap
*ordered_hashmap_free_free(OrderedHashmap
*h
) {
107 return (void*)internal_hashmap_free_free(HASHMAP_BASE(h
));
110 Hashmap
*hashmap_free_free_free(Hashmap
*h
);
111 static inline OrderedHashmap
*ordered_hashmap_free_free_free(OrderedHashmap
*h
) {
112 return (void*)hashmap_free_free_free(PLAIN_HASHMAP(h
));
115 IteratedCache
*iterated_cache_free(IteratedCache
*cache
);
116 int iterated_cache_get(IteratedCache
*cache
, const void ***res_keys
, const void ***res_values
, unsigned *res_n_entries
);
118 HashmapBase
*internal_hashmap_copy(HashmapBase
*h
);
119 static inline Hashmap
*hashmap_copy(Hashmap
*h
) {
120 return (Hashmap
*) internal_hashmap_copy(HASHMAP_BASE(h
));
122 static inline OrderedHashmap
*ordered_hashmap_copy(OrderedHashmap
*h
) {
123 return (OrderedHashmap
*) internal_hashmap_copy(HASHMAP_BASE(h
));
126 int internal_hashmap_ensure_allocated(Hashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
127 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
128 #define hashmap_ensure_allocated(h, ops) internal_hashmap_ensure_allocated(h, ops HASHMAP_DEBUG_SRC_ARGS)
129 #define ordered_hashmap_ensure_allocated(h, ops) internal_ordered_hashmap_ensure_allocated(h, ops HASHMAP_DEBUG_SRC_ARGS)
131 IteratedCache
*internal_hashmap_iterated_cache_new(HashmapBase
*h
);
132 static inline IteratedCache
*hashmap_iterated_cache_new(Hashmap
*h
) {
133 return (IteratedCache
*) internal_hashmap_iterated_cache_new(HASHMAP_BASE(h
));
135 static inline IteratedCache
*ordered_hashmap_iterated_cache_new(OrderedHashmap
*h
) {
136 return (IteratedCache
*) internal_hashmap_iterated_cache_new(HASHMAP_BASE(h
));
139 int hashmap_put(Hashmap
*h
, const void *key
, void *value
);
140 static inline int ordered_hashmap_put(OrderedHashmap
*h
, const void *key
, void *value
) {
141 return hashmap_put(PLAIN_HASHMAP(h
), key
, value
);
144 int hashmap_update(Hashmap
*h
, const void *key
, void *value
);
145 static inline int ordered_hashmap_update(OrderedHashmap
*h
, const void *key
, void *value
) {
146 return hashmap_update(PLAIN_HASHMAP(h
), key
, value
);
149 int hashmap_replace(Hashmap
*h
, const void *key
, void *value
);
150 static inline int ordered_hashmap_replace(OrderedHashmap
*h
, const void *key
, void *value
) {
151 return hashmap_replace(PLAIN_HASHMAP(h
), key
, value
);
154 void *internal_hashmap_get(HashmapBase
*h
, const void *key
);
155 static inline void *hashmap_get(Hashmap
*h
, const void *key
) {
156 return internal_hashmap_get(HASHMAP_BASE(h
), key
);
158 static inline void *ordered_hashmap_get(OrderedHashmap
*h
, const void *key
) {
159 return internal_hashmap_get(HASHMAP_BASE(h
), key
);
162 void *hashmap_get2(Hashmap
*h
, const void *key
, void **rkey
);
163 static inline void *ordered_hashmap_get2(OrderedHashmap
*h
, const void *key
, void **rkey
) {
164 return hashmap_get2(PLAIN_HASHMAP(h
), key
, rkey
);
167 bool internal_hashmap_contains(HashmapBase
*h
, const void *key
);
168 static inline bool hashmap_contains(Hashmap
*h
, const void *key
) {
169 return internal_hashmap_contains(HASHMAP_BASE(h
), key
);
171 static inline bool ordered_hashmap_contains(OrderedHashmap
*h
, const void *key
) {
172 return internal_hashmap_contains(HASHMAP_BASE(h
), key
);
175 void *internal_hashmap_remove(HashmapBase
*h
, const void *key
);
176 static inline void *hashmap_remove(Hashmap
*h
, const void *key
) {
177 return internal_hashmap_remove(HASHMAP_BASE(h
), key
);
179 static inline void *ordered_hashmap_remove(OrderedHashmap
*h
, const void *key
) {
180 return internal_hashmap_remove(HASHMAP_BASE(h
), key
);
183 void *hashmap_remove2(Hashmap
*h
, const void *key
, void **rkey
);
184 static inline void *ordered_hashmap_remove2(OrderedHashmap
*h
, const void *key
, void **rkey
) {
185 return hashmap_remove2(PLAIN_HASHMAP(h
), key
, rkey
);
188 void *hashmap_remove_value(Hashmap
*h
, const void *key
, void *value
);
189 static inline void *ordered_hashmap_remove_value(OrderedHashmap
*h
, const void *key
, void *value
) {
190 return hashmap_remove_value(PLAIN_HASHMAP(h
), key
, value
);
193 int hashmap_remove_and_put(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
);
194 static inline int ordered_hashmap_remove_and_put(OrderedHashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
195 return hashmap_remove_and_put(PLAIN_HASHMAP(h
), old_key
, new_key
, value
);
198 int hashmap_remove_and_replace(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
);
199 static inline int ordered_hashmap_remove_and_replace(OrderedHashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
200 return hashmap_remove_and_replace(PLAIN_HASHMAP(h
), old_key
, new_key
, value
);
203 /* Since merging data from a OrderedHashmap into a Hashmap or vice-versa
204 * should just work, allow this by having looser type-checking here. */
205 int internal_hashmap_merge(Hashmap
*h
, Hashmap
*other
);
206 #define hashmap_merge(h, other) internal_hashmap_merge(PLAIN_HASHMAP(h), PLAIN_HASHMAP(other))
207 #define ordered_hashmap_merge(h, other) hashmap_merge(h, other)
209 int internal_hashmap_reserve(HashmapBase
*h
, unsigned entries_add
);
210 static inline int hashmap_reserve(Hashmap
*h
, unsigned entries_add
) {
211 return internal_hashmap_reserve(HASHMAP_BASE(h
), entries_add
);
213 static inline int ordered_hashmap_reserve(OrderedHashmap
*h
, unsigned entries_add
) {
214 return internal_hashmap_reserve(HASHMAP_BASE(h
), entries_add
);
217 int internal_hashmap_move(HashmapBase
*h
, HashmapBase
*other
);
218 /* Unlike hashmap_merge, hashmap_move does not allow mixing the types. */
219 static inline int hashmap_move(Hashmap
*h
, Hashmap
*other
) {
220 return internal_hashmap_move(HASHMAP_BASE(h
), HASHMAP_BASE(other
));
222 static inline int ordered_hashmap_move(OrderedHashmap
*h
, OrderedHashmap
*other
) {
223 return internal_hashmap_move(HASHMAP_BASE(h
), HASHMAP_BASE(other
));
226 int internal_hashmap_move_one(HashmapBase
*h
, HashmapBase
*other
, const void *key
);
227 static inline int hashmap_move_one(Hashmap
*h
, Hashmap
*other
, const void *key
) {
228 return internal_hashmap_move_one(HASHMAP_BASE(h
), HASHMAP_BASE(other
), key
);
230 static inline int ordered_hashmap_move_one(OrderedHashmap
*h
, OrderedHashmap
*other
, const void *key
) {
231 return internal_hashmap_move_one(HASHMAP_BASE(h
), HASHMAP_BASE(other
), key
);
234 unsigned internal_hashmap_size(HashmapBase
*h
) _pure_
;
235 static inline unsigned hashmap_size(Hashmap
*h
) {
236 return internal_hashmap_size(HASHMAP_BASE(h
));
238 static inline unsigned ordered_hashmap_size(OrderedHashmap
*h
) {
239 return internal_hashmap_size(HASHMAP_BASE(h
));
242 static inline bool hashmap_isempty(Hashmap
*h
) {
243 return hashmap_size(h
) == 0;
245 static inline bool ordered_hashmap_isempty(OrderedHashmap
*h
) {
246 return ordered_hashmap_size(h
) == 0;
249 unsigned internal_hashmap_buckets(HashmapBase
*h
) _pure_
;
250 static inline unsigned hashmap_buckets(Hashmap
*h
) {
251 return internal_hashmap_buckets(HASHMAP_BASE(h
));
253 static inline unsigned ordered_hashmap_buckets(OrderedHashmap
*h
) {
254 return internal_hashmap_buckets(HASHMAP_BASE(h
));
257 bool internal_hashmap_iterate(HashmapBase
*h
, Iterator
*i
, void **value
, const void **key
);
258 static inline bool hashmap_iterate(Hashmap
*h
, Iterator
*i
, void **value
, const void **key
) {
259 return internal_hashmap_iterate(HASHMAP_BASE(h
), i
, value
, key
);
261 static inline bool ordered_hashmap_iterate(OrderedHashmap
*h
, Iterator
*i
, void **value
, const void **key
) {
262 return internal_hashmap_iterate(HASHMAP_BASE(h
), i
, value
, key
);
265 void internal_hashmap_clear(HashmapBase
*h
);
266 static inline void hashmap_clear(Hashmap
*h
) {
267 internal_hashmap_clear(HASHMAP_BASE(h
));
269 static inline void ordered_hashmap_clear(OrderedHashmap
*h
) {
270 internal_hashmap_clear(HASHMAP_BASE(h
));
273 void internal_hashmap_clear_free(HashmapBase
*h
);
274 static inline void hashmap_clear_free(Hashmap
*h
) {
275 internal_hashmap_clear_free(HASHMAP_BASE(h
));
277 static inline void ordered_hashmap_clear_free(OrderedHashmap
*h
) {
278 internal_hashmap_clear_free(HASHMAP_BASE(h
));
281 void hashmap_clear_free_free(Hashmap
*h
);
282 static inline void ordered_hashmap_clear_free_free(OrderedHashmap
*h
) {
283 hashmap_clear_free_free(PLAIN_HASHMAP(h
));
287 * Note about all *_first*() functions
289 * For plain Hashmaps and Sets the order of entries is undefined.
290 * The functions find whatever entry is first in the implementation
293 * Only for OrderedHashmaps the order is well defined and finding
294 * the first entry is O(1).
297 void *internal_hashmap_steal_first(HashmapBase
*h
);
298 static inline void *hashmap_steal_first(Hashmap
*h
) {
299 return internal_hashmap_steal_first(HASHMAP_BASE(h
));
301 static inline void *ordered_hashmap_steal_first(OrderedHashmap
*h
) {
302 return internal_hashmap_steal_first(HASHMAP_BASE(h
));
305 void *internal_hashmap_steal_first_key(HashmapBase
*h
);
306 static inline void *hashmap_steal_first_key(Hashmap
*h
) {
307 return internal_hashmap_steal_first_key(HASHMAP_BASE(h
));
309 static inline void *ordered_hashmap_steal_first_key(OrderedHashmap
*h
) {
310 return internal_hashmap_steal_first_key(HASHMAP_BASE(h
));
313 void *internal_hashmap_first_key(HashmapBase
*h
) _pure_
;
314 static inline void *hashmap_first_key(Hashmap
*h
) {
315 return internal_hashmap_first_key(HASHMAP_BASE(h
));
317 static inline void *ordered_hashmap_first_key(OrderedHashmap
*h
) {
318 return internal_hashmap_first_key(HASHMAP_BASE(h
));
321 void *internal_hashmap_first(HashmapBase
*h
) _pure_
;
322 static inline void *hashmap_first(Hashmap
*h
) {
323 return internal_hashmap_first(HASHMAP_BASE(h
));
325 static inline void *ordered_hashmap_first(OrderedHashmap
*h
) {
326 return internal_hashmap_first(HASHMAP_BASE(h
));
329 #define hashmap_clear_with_destructor(_s, _f) \
332 while ((_item = hashmap_steal_first(_s))) \
335 #define hashmap_free_with_destructor(_s, _f) \
337 hashmap_clear_with_destructor(_s, _f); \
340 #define ordered_hashmap_clear_with_destructor(_s, _f) \
343 while ((_item = ordered_hashmap_steal_first(_s))) \
346 #define ordered_hashmap_free_with_destructor(_s, _f) \
348 ordered_hashmap_clear_with_destructor(_s, _f); \
349 ordered_hashmap_free(_s); \
352 /* no hashmap_next */
353 void *ordered_hashmap_next(OrderedHashmap
*h
, const void *key
);
355 char **internal_hashmap_get_strv(HashmapBase
*h
);
356 static inline char **hashmap_get_strv(Hashmap
*h
) {
357 return internal_hashmap_get_strv(HASHMAP_BASE(h
));
359 static inline char **ordered_hashmap_get_strv(OrderedHashmap
*h
) {
360 return internal_hashmap_get_strv(HASHMAP_BASE(h
));
364 * Hashmaps are iterated in unpredictable order.
365 * OrderedHashmaps are an exception to this. They are iterated in the order
366 * the entries were inserted.
367 * It is safe to remove the current entry.
369 #define HASHMAP_FOREACH(e, h, i) \
370 for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), NULL); )
372 #define ORDERED_HASHMAP_FOREACH(e, h, i) \
373 for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), NULL); )
375 #define HASHMAP_FOREACH_KEY(e, k, h, i) \
376 for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
378 #define ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \
379 for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
381 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap
*, hashmap_free
);
382 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap
*, hashmap_free_free
);
383 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap
*, hashmap_free_free_free
);
384 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap
*, ordered_hashmap_free
);
385 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap
*, ordered_hashmap_free_free
);
386 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap
*, ordered_hashmap_free_free_free
);
388 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
389 #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
390 #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)
391 #define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep)
392 #define _cleanup_ordered_hashmap_free_free_ _cleanup_(ordered_hashmap_free_freep)
393 #define _cleanup_ordered_hashmap_free_free_free_ _cleanup_(ordered_hashmap_free_free_freep)
395 DEFINE_TRIVIAL_CLEANUP_FUNC(IteratedCache
*, iterated_cache_free
);
397 #define _cleanup_iterated_cache_free_ _cleanup_(iterated_cache_freep)