1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
6 This file is part of systemd.
8 Copyright 2010 Lennart Poettering
9 Copyright 2014 Michal Schmidt
11 systemd is free software; you can redistribute it and/or modify it
12 under the terms of the GNU Lesser General Public License as published by
13 the Free Software Foundation; either version 2.1 of the License, or
14 (at your option) any later version.
16 systemd is distributed in the hope that it will be useful, but
17 WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 Lesser General Public License for more details.
21 You should have received a copy of the GNU Lesser General Public License
22 along with systemd; If not, see <http://www.gnu.org/licenses/>.
31 * A hash table implementation. As a minor optimization a NULL hashmap object
32 * will be treated as empty hashmap for all read operations. That way it is not
33 * necessary to instantiate an object for each Hashmap use.
35 * If ENABLE_DEBUG_HASHMAP is defined (by configuring with --enable-debug=hashmap),
36 * the implemention will:
37 * - store extra data for debugging and statistics (see tools/gdb-sd_dump_hashmaps.py)
38 * - perform extra checks for invalid use of iterators
41 #define HASH_KEY_SIZE 16
43 /* The base type for all hashmap and set types. Many functions in the
44 * implementation take (HashmapBase*) parameters and are run-time polymorphic,
45 * though the API is not meant to be polymorphic (do not call functions
46 * internal_*() directly). */
47 typedef struct HashmapBase HashmapBase;
49 /* Specific hashmap/set types */
50 typedef struct Hashmap Hashmap; /* Maps keys to values */
51 typedef struct OrderedHashmap OrderedHashmap; /* Like Hashmap, but also remembers entry insertion order */
52 typedef struct Set Set; /* Stores just keys */
54 /* Ideally the Iterator would be an opaque struct, but it is instantiated
55 * by hashmap users, so the definition has to be here. Do not use its fields
58 unsigned idx; /* index of an entry to be iterated next */
59 const void *next_key; /* expected value of that entry's key pointer */
60 #ifdef ENABLE_DEBUG_HASHMAP
61 unsigned put_count; /* hashmap's put_count recorded at start of iteration */
62 unsigned rem_count; /* hashmap's rem_count in previous iteration */
63 unsigned prev_idx; /* idx in previous iteration */
67 #define _IDX_ITERATOR_FIRST (UINT_MAX - 1)
68 #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL })
70 typedef unsigned long (*hash_func_t)(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]);
71 typedef int (*compare_func_t)(const void *a, const void *b);
75 compare_func_t compare;
78 unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
79 int string_compare_func(const void *a, const void *b) _pure_;
80 extern const struct hash_ops string_hash_ops;
82 /* This will compare the passed pointers directly, and will not
83 * dereference them. This is hence not useful for strings or
85 unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
86 int trivial_compare_func(const void *a, const void *b) _const_;
87 extern const struct hash_ops trivial_hash_ops;
89 /* 32bit values we can always just embedd in the pointer itself, but
90 * in order to support 32bit archs we need store 64bit values
91 * indirectly, since they don't fit in a pointer. */
92 unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
93 int uint64_compare_func(const void *a, const void *b) _pure_;
94 extern const struct hash_ops uint64_hash_ops;
96 /* On some archs dev_t is 32bit, and on others 64bit. And sometimes
97 * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */
99 unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
100 int devt_compare_func(const void *a, const void *b) _pure_;
101 extern const struct hash_ops devt_hash_ops = {
102 .hash = devt_hash_func,
103 .compare = devt_compare_func
106 #define devt_hash_func uint64_hash_func
107 #define devt_compare_func uint64_compare_func
108 #define devt_hash_ops uint64_hash_ops
111 /* Macros for type checking */
112 #define PTR_COMPATIBLE_WITH_HASHMAP_BASE(h) \
113 (__builtin_types_compatible_p(typeof(h), HashmapBase*) || \
114 __builtin_types_compatible_p(typeof(h), Hashmap*) || \
115 __builtin_types_compatible_p(typeof(h), OrderedHashmap*) || \
116 __builtin_types_compatible_p(typeof(h), Set*))
118 #define PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h) \
119 (__builtin_types_compatible_p(typeof(h), Hashmap*) || \
120 __builtin_types_compatible_p(typeof(h), OrderedHashmap*)) \
122 #define HASHMAP_BASE(h) \
123 __builtin_choose_expr(PTR_COMPATIBLE_WITH_HASHMAP_BASE(h), \
127 #define PLAIN_HASHMAP(h) \
128 __builtin_choose_expr(PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h), \
132 #ifdef ENABLE_DEBUG_HASHMAP
133 # define HASHMAP_DEBUG_PARAMS , const char *func, const char *file, int line
134 # define HASHMAP_DEBUG_SRC_ARGS , __func__, __FILE__, __LINE__
135 # define HASHMAP_DEBUG_PASS_ARGS , func, file, line
137 # define HASHMAP_DEBUG_PARAMS
138 # define HASHMAP_DEBUG_SRC_ARGS
139 # define HASHMAP_DEBUG_PASS_ARGS
142 Hashmap *internal_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS);
143 OrderedHashmap *internal_ordered_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS);
144 #define hashmap_new(ops) internal_hashmap_new(ops HASHMAP_DEBUG_SRC_ARGS)
145 #define ordered_hashmap_new(ops) internal_ordered_hashmap_new(ops HASHMAP_DEBUG_SRC_ARGS)
147 HashmapBase *internal_hashmap_free(HashmapBase *h);
148 static inline Hashmap *hashmap_free(Hashmap *h) {
149 return (void*)internal_hashmap_free(HASHMAP_BASE(h));
151 static inline OrderedHashmap *ordered_hashmap_free(OrderedHashmap *h) {
152 return (void*)internal_hashmap_free(HASHMAP_BASE(h));
155 HashmapBase *internal_hashmap_free_free(HashmapBase *h);
156 static inline Hashmap *hashmap_free_free(Hashmap *h) {
157 return (void*)internal_hashmap_free_free(HASHMAP_BASE(h));
159 static inline OrderedHashmap *ordered_hashmap_free_free(OrderedHashmap *h) {
160 return (void*)internal_hashmap_free_free(HASHMAP_BASE(h));
163 Hashmap *hashmap_free_free_free(Hashmap *h);
164 static inline OrderedHashmap *ordered_hashmap_free_free_free(OrderedHashmap *h) {
165 return (void*)hashmap_free_free_free(PLAIN_HASHMAP(h));
168 HashmapBase *internal_hashmap_copy(HashmapBase *h);
169 static inline Hashmap *hashmap_copy(Hashmap *h) {
170 return (Hashmap*) internal_hashmap_copy(HASHMAP_BASE(h));
172 static inline OrderedHashmap *ordered_hashmap_copy(OrderedHashmap *h) {
173 return (OrderedHashmap*) internal_hashmap_copy(HASHMAP_BASE(h));
176 int internal_hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS);
177 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS);
178 #define hashmap_ensure_allocated(h, ops) internal_hashmap_ensure_allocated(h, ops HASHMAP_DEBUG_SRC_ARGS)
179 #define ordered_hashmap_ensure_allocated(h, ops) internal_ordered_hashmap_ensure_allocated(h, ops HASHMAP_DEBUG_SRC_ARGS)
181 int hashmap_put(Hashmap *h, const void *key, void *value);
182 static inline int ordered_hashmap_put(OrderedHashmap *h, const void *key, void *value) {
183 return hashmap_put(PLAIN_HASHMAP(h), key, value);
186 int hashmap_update(Hashmap *h, const void *key, void *value);
187 static inline int ordered_hashmap_update(OrderedHashmap *h, const void *key, void *value) {
188 return hashmap_update(PLAIN_HASHMAP(h), key, value);
191 int hashmap_replace(Hashmap *h, const void *key, void *value);
192 static inline int ordered_hashmap_replace(OrderedHashmap *h, const void *key, void *value) {
193 return hashmap_replace(PLAIN_HASHMAP(h), key, value);
196 void *internal_hashmap_get(HashmapBase *h, const void *key);
197 static inline void *hashmap_get(Hashmap *h, const void *key) {
198 return internal_hashmap_get(HASHMAP_BASE(h), key);
200 static inline void *ordered_hashmap_get(OrderedHashmap *h, const void *key) {
201 return internal_hashmap_get(HASHMAP_BASE(h), key);
204 void *hashmap_get2(Hashmap *h, const void *key, void **rkey);
205 static inline void *ordered_hashmap_get2(OrderedHashmap *h, const void *key, void **rkey) {
206 return hashmap_get2(PLAIN_HASHMAP(h), key, rkey);
209 bool internal_hashmap_contains(HashmapBase *h, const void *key);
210 static inline bool hashmap_contains(Hashmap *h, const void *key) {
211 return internal_hashmap_contains(HASHMAP_BASE(h), key);
213 static inline bool ordered_hashmap_contains(OrderedHashmap *h, const void *key) {
214 return internal_hashmap_contains(HASHMAP_BASE(h), key);
217 void *internal_hashmap_remove(HashmapBase *h, const void *key);
218 static inline void *hashmap_remove(Hashmap *h, const void *key) {
219 return internal_hashmap_remove(HASHMAP_BASE(h), key);
221 static inline void *ordered_hashmap_remove(OrderedHashmap *h, const void *key) {
222 return internal_hashmap_remove(HASHMAP_BASE(h), key);
225 void *hashmap_remove2(Hashmap *h, const void *key, void **rkey);
226 static inline void *ordered_hashmap_remove2(OrderedHashmap *h, const void *key, void **rkey) {
227 return hashmap_remove2(PLAIN_HASHMAP(h), key, rkey);
230 void *hashmap_remove_value(Hashmap *h, const void *key, void *value);
231 static inline void *ordered_hashmap_remove_value(OrderedHashmap *h, const void *key, void *value) {
232 return hashmap_remove_value(PLAIN_HASHMAP(h), key, value);
235 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);
236 static inline int ordered_hashmap_remove_and_put(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
237 return hashmap_remove_and_put(PLAIN_HASHMAP(h), old_key, new_key, value);
240 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value);
241 static inline int ordered_hashmap_remove_and_replace(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
242 return hashmap_remove_and_replace(PLAIN_HASHMAP(h), old_key, new_key, value);
245 /* Since merging data from a OrderedHashmap into a Hashmap or vice-versa
246 * should just work, allow this by having looser type-checking here. */
247 int internal_hashmap_merge(Hashmap *h, Hashmap *other);
248 #define hashmap_merge(h, other) internal_hashmap_merge(PLAIN_HASHMAP(h), PLAIN_HASHMAP(other))
249 #define ordered_hashmap_merge(h, other) hashmap_merge(h, other)
251 int internal_hashmap_reserve(HashmapBase *h, unsigned entries_add);
252 static inline int hashmap_reserve(Hashmap *h, unsigned entries_add) {
253 return internal_hashmap_reserve(HASHMAP_BASE(h), entries_add);
255 static inline int ordered_hashmap_reserve(OrderedHashmap *h, unsigned entries_add) {
256 return internal_hashmap_reserve(HASHMAP_BASE(h), entries_add);
259 int internal_hashmap_move(HashmapBase *h, HashmapBase *other);
260 /* Unlike hashmap_merge, hashmap_move does not allow mixing the types. */
261 static inline int hashmap_move(Hashmap *h, Hashmap *other) {
262 return internal_hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
264 static inline int ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
265 return internal_hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
268 int internal_hashmap_move_one(HashmapBase *h, HashmapBase *other, const void *key);
269 static inline int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
270 return internal_hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
272 static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) {
273 return internal_hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
276 unsigned internal_hashmap_size(HashmapBase *h) _pure_;
277 static inline unsigned hashmap_size(Hashmap *h) {
278 return internal_hashmap_size(HASHMAP_BASE(h));
280 static inline unsigned ordered_hashmap_size(OrderedHashmap *h) {
281 return internal_hashmap_size(HASHMAP_BASE(h));
284 static inline bool hashmap_isempty(Hashmap *h) {
285 return hashmap_size(h) == 0;
287 static inline bool ordered_hashmap_isempty(OrderedHashmap *h) {
288 return ordered_hashmap_size(h) == 0;
291 unsigned internal_hashmap_buckets(HashmapBase *h) _pure_;
292 static inline unsigned hashmap_buckets(Hashmap *h) {
293 return internal_hashmap_buckets(HASHMAP_BASE(h));
295 static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) {
296 return internal_hashmap_buckets(HASHMAP_BASE(h));
299 bool internal_hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key);
300 static inline bool hashmap_iterate(Hashmap *h, Iterator *i, void **value, const void **key) {
301 return internal_hashmap_iterate(HASHMAP_BASE(h), i, value, key);
303 static inline bool ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, void **value, const void **key) {
304 return internal_hashmap_iterate(HASHMAP_BASE(h), i, value, key);
307 void internal_hashmap_clear(HashmapBase *h);
308 static inline void hashmap_clear(Hashmap *h) {
309 internal_hashmap_clear(HASHMAP_BASE(h));
311 static inline void ordered_hashmap_clear(OrderedHashmap *h) {
312 internal_hashmap_clear(HASHMAP_BASE(h));
315 void internal_hashmap_clear_free(HashmapBase *h);
316 static inline void hashmap_clear_free(Hashmap *h) {
317 internal_hashmap_clear_free(HASHMAP_BASE(h));
319 static inline void ordered_hashmap_clear_free(OrderedHashmap *h) {
320 internal_hashmap_clear_free(HASHMAP_BASE(h));
323 void hashmap_clear_free_free(Hashmap *h);
324 static inline void ordered_hashmap_clear_free_free(OrderedHashmap *h) {
325 hashmap_clear_free_free(PLAIN_HASHMAP(h));
329 * Note about all *_first*() functions
331 * For plain Hashmaps and Sets the order of entries is undefined.
332 * The functions find whatever entry is first in the implementation
335 * Only for OrderedHashmaps the order is well defined and finding
336 * the first entry is O(1).
339 void *internal_hashmap_steal_first(HashmapBase *h);
340 static inline void *hashmap_steal_first(Hashmap *h) {
341 return internal_hashmap_steal_first(HASHMAP_BASE(h));
343 static inline void *ordered_hashmap_steal_first(OrderedHashmap *h) {
344 return internal_hashmap_steal_first(HASHMAP_BASE(h));
347 void *internal_hashmap_steal_first_key(HashmapBase *h);
348 static inline void *hashmap_steal_first_key(Hashmap *h) {
349 return internal_hashmap_steal_first_key(HASHMAP_BASE(h));
351 static inline void *ordered_hashmap_steal_first_key(OrderedHashmap *h) {
352 return internal_hashmap_steal_first_key(HASHMAP_BASE(h));
355 void *internal_hashmap_first_key(HashmapBase *h) _pure_;
356 static inline void *hashmap_first_key(Hashmap *h) {
357 return internal_hashmap_first_key(HASHMAP_BASE(h));
359 static inline void *ordered_hashmap_first_key(OrderedHashmap *h) {
360 return internal_hashmap_first_key(HASHMAP_BASE(h));
363 void *internal_hashmap_first(HashmapBase *h) _pure_;
364 static inline void *hashmap_first(Hashmap *h) {
365 return internal_hashmap_first(HASHMAP_BASE(h));
367 static inline void *ordered_hashmap_first(OrderedHashmap *h) {
368 return internal_hashmap_first(HASHMAP_BASE(h));
371 /* no hashmap_next */
372 // UNNEEDED void *ordered_hashmap_next(OrderedHashmap *h, const void *key);
374 char **internal_hashmap_get_strv(HashmapBase *h);
375 static inline char **hashmap_get_strv(Hashmap *h) {
376 return internal_hashmap_get_strv(HASHMAP_BASE(h));
378 static inline char **ordered_hashmap_get_strv(OrderedHashmap *h) {
379 return internal_hashmap_get_strv(HASHMAP_BASE(h));
383 * Hashmaps are iterated in unpredictable order.
384 * OrderedHashmaps are an exception to this. They are iterated in the order
385 * the entries were inserted.
386 * It is safe to remove the current entry.
388 #define HASHMAP_FOREACH(e, h, i) \
389 for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), NULL); )
391 #define ORDERED_HASHMAP_FOREACH(e, h, i) \
392 for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), NULL); )
394 #define HASHMAP_FOREACH_KEY(e, k, h, i) \
395 for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
397 #define ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \
398 for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
400 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
401 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free);
402 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free_free);
403 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free);
404 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free);
405 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free_free);
407 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
408 #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
409 #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)
410 #define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep)
411 #define _cleanup_ordered_hashmap_free_free_ _cleanup_(ordered_hashmap_free_freep)
412 #define _cleanup_ordered_hashmap_free_free_free_ _cleanup_(ordered_hashmap_free_free_freep)