1 /* SPDX-License-Identifier: LGPL-2.1+ */
5 This file is part of systemd.
7 Copyright 2010 Lennart Poettering
8 Copyright 2014 Michal Schmidt
10 systemd is free software; you can redistribute it and/or modify it
11 under the terms of the GNU Lesser General Public License as published by
12 the Free Software Foundation; either version 2.1 of the License, or
13 (at your option) any later version.
15 systemd is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 Lesser General Public License for more details.
20 You should have received a copy of the GNU Lesser General Public License
21 along with systemd; If not, see <http://www.gnu.org/licenses/>.
28 #include "hash-funcs.h"
33 * A hash table implementation. As a minor optimization a NULL hashmap object
34 * will be treated as empty hashmap for all read operations. That way it is not
35 * necessary to instantiate an object for each Hashmap use.
37 * If ENABLE_DEBUG_HASHMAP is defined (by configuring with --enable-debug=hashmap),
38 * the implemention will:
39 * - store extra data for debugging and statistics (see tools/gdb-sd_dump_hashmaps.py)
40 * - perform extra checks for invalid use of iterators
43 #define HASH_KEY_SIZE 16
45 /* The base type for all hashmap and set types. Many functions in the
46 * implementation take (HashmapBase*) parameters and are run-time polymorphic,
47 * though the API is not meant to be polymorphic (do not call functions
48 * internal_*() directly). */
49 typedef struct HashmapBase HashmapBase
;
51 /* Specific hashmap/set types */
52 typedef struct Hashmap Hashmap
; /* Maps keys to values */
53 typedef struct OrderedHashmap OrderedHashmap
; /* Like Hashmap, but also remembers entry insertion order */
54 typedef struct Set Set
; /* Stores just keys */
56 /* Ideally the Iterator would be an opaque struct, but it is instantiated
57 * by hashmap users, so the definition has to be here. Do not use its fields
60 unsigned idx
; /* index of an entry to be iterated next */
61 const void *next_key
; /* expected value of that entry's key pointer */
62 #if ENABLE_DEBUG_HASHMAP
63 unsigned put_count
; /* hashmap's put_count recorded at start of iteration */
64 unsigned rem_count
; /* hashmap's rem_count in previous iteration */
65 unsigned prev_idx
; /* idx in previous iteration */
69 #define _IDX_ITERATOR_FIRST (UINT_MAX - 1)
70 #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL })
72 /* Macros for type checking */
73 #define PTR_COMPATIBLE_WITH_HASHMAP_BASE(h) \
74 (__builtin_types_compatible_p(typeof(h), HashmapBase*) || \
75 __builtin_types_compatible_p(typeof(h), Hashmap*) || \
76 __builtin_types_compatible_p(typeof(h), OrderedHashmap*) || \
77 __builtin_types_compatible_p(typeof(h), Set*))
79 #define PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h) \
80 (__builtin_types_compatible_p(typeof(h), Hashmap*) || \
81 __builtin_types_compatible_p(typeof(h), OrderedHashmap*)) \
83 #define HASHMAP_BASE(h) \
84 __builtin_choose_expr(PTR_COMPATIBLE_WITH_HASHMAP_BASE(h), \
88 #define PLAIN_HASHMAP(h) \
89 __builtin_choose_expr(PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h), \
93 #if ENABLE_DEBUG_HASHMAP
94 # define HASHMAP_DEBUG_PARAMS , const char *func, const char *file, int line
95 # define HASHMAP_DEBUG_SRC_ARGS , __func__, __FILE__, __LINE__
96 # define HASHMAP_DEBUG_PASS_ARGS , func, file, line
98 # define HASHMAP_DEBUG_PARAMS
99 # define HASHMAP_DEBUG_SRC_ARGS
100 # define HASHMAP_DEBUG_PASS_ARGS
103 Hashmap
*internal_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
104 OrderedHashmap
*internal_ordered_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
105 #define hashmap_new(ops) internal_hashmap_new(ops HASHMAP_DEBUG_SRC_ARGS)
106 #define ordered_hashmap_new(ops) internal_ordered_hashmap_new(ops HASHMAP_DEBUG_SRC_ARGS)
108 HashmapBase
*internal_hashmap_free(HashmapBase
*h
);
109 static inline Hashmap
*hashmap_free(Hashmap
*h
) {
110 return (void*)internal_hashmap_free(HASHMAP_BASE(h
));
112 static inline OrderedHashmap
*ordered_hashmap_free(OrderedHashmap
*h
) {
113 return (void*)internal_hashmap_free(HASHMAP_BASE(h
));
116 HashmapBase
*internal_hashmap_free_free(HashmapBase
*h
);
117 static inline Hashmap
*hashmap_free_free(Hashmap
*h
) {
118 return (void*)internal_hashmap_free_free(HASHMAP_BASE(h
));
120 static inline OrderedHashmap
*ordered_hashmap_free_free(OrderedHashmap
*h
) {
121 return (void*)internal_hashmap_free_free(HASHMAP_BASE(h
));
124 Hashmap
*hashmap_free_free_free(Hashmap
*h
);
125 static inline OrderedHashmap
*ordered_hashmap_free_free_free(OrderedHashmap
*h
) {
126 return (void*)hashmap_free_free_free(PLAIN_HASHMAP(h
));
129 HashmapBase
*internal_hashmap_copy(HashmapBase
*h
);
130 static inline Hashmap
*hashmap_copy(Hashmap
*h
) {
131 return (Hashmap
*) internal_hashmap_copy(HASHMAP_BASE(h
));
133 static inline OrderedHashmap
*ordered_hashmap_copy(OrderedHashmap
*h
) {
134 return (OrderedHashmap
*) internal_hashmap_copy(HASHMAP_BASE(h
));
137 int internal_hashmap_ensure_allocated(Hashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
138 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
139 #define hashmap_ensure_allocated(h, ops) internal_hashmap_ensure_allocated(h, ops HASHMAP_DEBUG_SRC_ARGS)
140 #define ordered_hashmap_ensure_allocated(h, ops) internal_ordered_hashmap_ensure_allocated(h, ops HASHMAP_DEBUG_SRC_ARGS)
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
);
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
);
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
);
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
);
161 static inline void *ordered_hashmap_get(OrderedHashmap
*h
, const void *key
) {
162 return internal_hashmap_get(HASHMAP_BASE(h
), key
);
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
);
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
);
174 static inline bool ordered_hashmap_contains(OrderedHashmap
*h
, const void *key
) {
175 return internal_hashmap_contains(HASHMAP_BASE(h
), key
);
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
);
182 static inline void *ordered_hashmap_remove(OrderedHashmap
*h
, const void *key
) {
183 return internal_hashmap_remove(HASHMAP_BASE(h
), key
);
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
);
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
);
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
);
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
);
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)
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
);
216 static inline int ordered_hashmap_reserve(OrderedHashmap
*h
, unsigned entries_add
) {
217 return internal_hashmap_reserve(HASHMAP_BASE(h
), entries_add
);
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
));
225 static inline int ordered_hashmap_move(OrderedHashmap
*h
, OrderedHashmap
*other
) {
226 return internal_hashmap_move(HASHMAP_BASE(h
), HASHMAP_BASE(other
));
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
);
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
);
237 unsigned internal_hashmap_size(HashmapBase
*h
) _pure_
;
238 static inline unsigned hashmap_size(Hashmap
*h
) {
239 return internal_hashmap_size(HASHMAP_BASE(h
));
241 static inline unsigned ordered_hashmap_size(OrderedHashmap
*h
) {
242 return internal_hashmap_size(HASHMAP_BASE(h
));
245 static inline bool hashmap_isempty(Hashmap
*h
) {
246 return hashmap_size(h
) == 0;
248 static inline bool ordered_hashmap_isempty(OrderedHashmap
*h
) {
249 return ordered_hashmap_size(h
) == 0;
252 unsigned internal_hashmap_buckets(HashmapBase
*h
) _pure_
;
253 static inline unsigned hashmap_buckets(Hashmap
*h
) {
254 return internal_hashmap_buckets(HASHMAP_BASE(h
));
256 static inline unsigned ordered_hashmap_buckets(OrderedHashmap
*h
) {
257 return internal_hashmap_buckets(HASHMAP_BASE(h
));
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
);
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
);
268 void internal_hashmap_clear(HashmapBase
*h
);
269 static inline void hashmap_clear(Hashmap
*h
) {
270 internal_hashmap_clear(HASHMAP_BASE(h
));
272 static inline void ordered_hashmap_clear(OrderedHashmap
*h
) {
273 internal_hashmap_clear(HASHMAP_BASE(h
));
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
));
280 static inline void ordered_hashmap_clear_free(OrderedHashmap
*h
) {
281 internal_hashmap_clear_free(HASHMAP_BASE(h
));
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
));
290 * Note about all *_first*() functions
292 * For plain Hashmaps and Sets the order of entries is undefined.
293 * The functions find whatever entry is first in the implementation
296 * Only for OrderedHashmaps the order is well defined and finding
297 * the first entry is O(1).
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
));
304 static inline void *ordered_hashmap_steal_first(OrderedHashmap
*h
) {
305 return internal_hashmap_steal_first(HASHMAP_BASE(h
));
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
));
312 static inline void *ordered_hashmap_steal_first_key(OrderedHashmap
*h
) {
313 return internal_hashmap_steal_first_key(HASHMAP_BASE(h
));
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
));
320 static inline void *ordered_hashmap_first_key(OrderedHashmap
*h
) {
321 return internal_hashmap_first_key(HASHMAP_BASE(h
));
324 void *internal_hashmap_first(HashmapBase
*h
) _pure_
;
325 static inline void *hashmap_first(Hashmap
*h
) {
326 return internal_hashmap_first(HASHMAP_BASE(h
));
328 static inline void *ordered_hashmap_first(OrderedHashmap
*h
) {
329 return internal_hashmap_first(HASHMAP_BASE(h
));
332 /* no hashmap_next */
333 void *ordered_hashmap_next(OrderedHashmap
*h
, const void *key
);
335 char **internal_hashmap_get_strv(HashmapBase
*h
);
336 static inline char **hashmap_get_strv(Hashmap
*h
) {
337 return internal_hashmap_get_strv(HASHMAP_BASE(h
));
339 static inline char **ordered_hashmap_get_strv(OrderedHashmap
*h
) {
340 return internal_hashmap_get_strv(HASHMAP_BASE(h
));
344 * Hashmaps are iterated in unpredictable order.
345 * OrderedHashmaps are an exception to this. They are iterated in the order
346 * the entries were inserted.
347 * It is safe to remove the current entry.
349 #define HASHMAP_FOREACH(e, h, i) \
350 for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), NULL); )
352 #define ORDERED_HASHMAP_FOREACH(e, h, i) \
353 for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), NULL); )
355 #define HASHMAP_FOREACH_KEY(e, k, h, i) \
356 for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
358 #define ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \
359 for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
361 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap
*, hashmap_free
);
362 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap
*, hashmap_free_free
);
363 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap
*, hashmap_free_free_free
);
364 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap
*, ordered_hashmap_free
);
365 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap
*, ordered_hashmap_free_free
);
366 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap
*, ordered_hashmap_free_free_free
);
368 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
369 #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
370 #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)
371 #define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep)
372 #define _cleanup_ordered_hashmap_free_free_ _cleanup_(ordered_hashmap_free_freep)
373 #define _cleanup_ordered_hashmap_free_free_free_ _cleanup_(ordered_hashmap_free_free_freep)