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/>.
30 #include "siphash24.h"
34 * A hash table implementation. As a minor optimization a NULL hashmap object
35 * will be treated as empty hashmap for all read operations. That way it is not
36 * necessary to instantiate an object for each Hashmap use.
38 * If ENABLE_DEBUG_HASHMAP is defined (by configuring with --enable-debug=hashmap),
39 * the implemention will:
40 * - store extra data for debugging and statistics (see tools/gdb-sd_dump_hashmaps.py)
41 * - perform extra checks for invalid use of iterators
44 #define HASH_KEY_SIZE 16
46 /* The base type for all hashmap and set types. Many functions in the
47 * implementation take (HashmapBase*) parameters and are run-time polymorphic,
48 * though the API is not meant to be polymorphic (do not call functions
49 * internal_*() directly). */
50 typedef struct HashmapBase HashmapBase
;
52 /* Specific hashmap/set types */
53 typedef struct Hashmap Hashmap
; /* Maps keys to values */
54 typedef struct OrderedHashmap OrderedHashmap
; /* Like Hashmap, but also remembers entry insertion order */
55 typedef struct Set Set
; /* Stores just keys */
57 /* Ideally the Iterator would be an opaque struct, but it is instantiated
58 * by hashmap users, so the definition has to be here. Do not use its fields
61 unsigned idx
; /* index of an entry to be iterated next */
62 const void *next_key
; /* expected value of that entry's key pointer */
63 #ifdef ENABLE_DEBUG_HASHMAP
64 unsigned put_count
; /* hashmap's put_count recorded at start of iteration */
65 unsigned rem_count
; /* hashmap's rem_count in previous iteration */
66 unsigned prev_idx
; /* idx in previous iteration */
70 #define _IDX_ITERATOR_FIRST (UINT_MAX - 1)
71 #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL })
73 typedef void (*hash_func_t
)(const void *p
, struct siphash
*state
);
74 typedef int (*compare_func_t
)(const void *a
, const void *b
);
78 compare_func_t compare
;
81 void string_hash_func(const void *p
, struct siphash
*state
);
82 int string_compare_func(const void *a
, const void *b
) _pure_
;
83 extern const struct hash_ops string_hash_ops
;
85 /* This will compare the passed pointers directly, and will not
86 * dereference them. This is hence not useful for strings or
88 void trivial_hash_func(const void *p
, struct siphash
*state
);
89 int trivial_compare_func(const void *a
, const void *b
) _const_
;
90 extern const struct hash_ops trivial_hash_ops
;
92 /* 32bit values we can always just embedd in the pointer itself, but
93 * in order to support 32bit archs we need store 64bit values
94 * indirectly, since they don't fit in a pointer. */
95 void uint64_hash_func(const void *p
, struct siphash
*state
);
96 int uint64_compare_func(const void *a
, const void *b
) _pure_
;
97 extern const struct hash_ops uint64_hash_ops
;
99 /* On some archs dev_t is 32bit, and on others 64bit. And sometimes
100 * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */
101 #if SIZEOF_DEV_T != 8
102 void devt_hash_func(const void *p
, struct siphash
*state
) _pure_
;
103 int devt_compare_func(const void *a
, const void *b
) _pure_
;
104 extern const struct hash_ops devt_hash_ops
= {
105 .hash
= devt_hash_func
,
106 .compare
= devt_compare_func
109 #define devt_hash_func uint64_hash_func
110 #define devt_compare_func uint64_compare_func
111 #define devt_hash_ops uint64_hash_ops
114 /* Macros for type checking */
115 #define PTR_COMPATIBLE_WITH_HASHMAP_BASE(h) \
116 (__builtin_types_compatible_p(typeof(h), HashmapBase*) || \
117 __builtin_types_compatible_p(typeof(h), Hashmap*) || \
118 __builtin_types_compatible_p(typeof(h), OrderedHashmap*) || \
119 __builtin_types_compatible_p(typeof(h), Set*))
121 #define PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h) \
122 (__builtin_types_compatible_p(typeof(h), Hashmap*) || \
123 __builtin_types_compatible_p(typeof(h), OrderedHashmap*)) \
125 #define HASHMAP_BASE(h) \
126 __builtin_choose_expr(PTR_COMPATIBLE_WITH_HASHMAP_BASE(h), \
130 #define PLAIN_HASHMAP(h) \
131 __builtin_choose_expr(PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h), \
135 #ifdef ENABLE_DEBUG_HASHMAP
136 # define HASHMAP_DEBUG_PARAMS , const char *func, const char *file, int line
137 # define HASHMAP_DEBUG_SRC_ARGS , __func__, __FILE__, __LINE__
138 # define HASHMAP_DEBUG_PASS_ARGS , func, file, line
140 # define HASHMAP_DEBUG_PARAMS
141 # define HASHMAP_DEBUG_SRC_ARGS
142 # define HASHMAP_DEBUG_PASS_ARGS
145 Hashmap
*internal_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
146 OrderedHashmap
*internal_ordered_hashmap_new(const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
147 #define hashmap_new(ops) internal_hashmap_new(ops HASHMAP_DEBUG_SRC_ARGS)
148 #define ordered_hashmap_new(ops) internal_ordered_hashmap_new(ops HASHMAP_DEBUG_SRC_ARGS)
150 HashmapBase
*internal_hashmap_free(HashmapBase
*h
);
151 static inline Hashmap
*hashmap_free(Hashmap
*h
) {
152 return (void*)internal_hashmap_free(HASHMAP_BASE(h
));
154 static inline OrderedHashmap
*ordered_hashmap_free(OrderedHashmap
*h
) {
155 return (void*)internal_hashmap_free(HASHMAP_BASE(h
));
158 HashmapBase
*internal_hashmap_free_free(HashmapBase
*h
);
159 static inline Hashmap
*hashmap_free_free(Hashmap
*h
) {
160 return (void*)internal_hashmap_free_free(HASHMAP_BASE(h
));
162 static inline OrderedHashmap
*ordered_hashmap_free_free(OrderedHashmap
*h
) {
163 return (void*)internal_hashmap_free_free(HASHMAP_BASE(h
));
166 Hashmap
*hashmap_free_free_free(Hashmap
*h
);
167 static inline OrderedHashmap
*ordered_hashmap_free_free_free(OrderedHashmap
*h
) {
168 return (void*)hashmap_free_free_free(PLAIN_HASHMAP(h
));
171 HashmapBase
*internal_hashmap_copy(HashmapBase
*h
);
172 static inline Hashmap
*hashmap_copy(Hashmap
*h
) {
173 return (Hashmap
*) internal_hashmap_copy(HASHMAP_BASE(h
));
175 static inline OrderedHashmap
*ordered_hashmap_copy(OrderedHashmap
*h
) {
176 return (OrderedHashmap
*) internal_hashmap_copy(HASHMAP_BASE(h
));
179 int internal_hashmap_ensure_allocated(Hashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
180 int internal_ordered_hashmap_ensure_allocated(OrderedHashmap
**h
, const struct hash_ops
*hash_ops HASHMAP_DEBUG_PARAMS
);
181 #define hashmap_ensure_allocated(h, ops) internal_hashmap_ensure_allocated(h, ops HASHMAP_DEBUG_SRC_ARGS)
182 #define ordered_hashmap_ensure_allocated(h, ops) internal_ordered_hashmap_ensure_allocated(h, ops HASHMAP_DEBUG_SRC_ARGS)
184 int hashmap_put(Hashmap
*h
, const void *key
, void *value
);
185 static inline int ordered_hashmap_put(OrderedHashmap
*h
, const void *key
, void *value
) {
186 return hashmap_put(PLAIN_HASHMAP(h
), key
, value
);
189 int hashmap_update(Hashmap
*h
, const void *key
, void *value
);
190 static inline int ordered_hashmap_update(OrderedHashmap
*h
, const void *key
, void *value
) {
191 return hashmap_update(PLAIN_HASHMAP(h
), key
, value
);
194 int hashmap_replace(Hashmap
*h
, const void *key
, void *value
);
195 static inline int ordered_hashmap_replace(OrderedHashmap
*h
, const void *key
, void *value
) {
196 return hashmap_replace(PLAIN_HASHMAP(h
), key
, value
);
199 void *internal_hashmap_get(HashmapBase
*h
, const void *key
);
200 static inline void *hashmap_get(Hashmap
*h
, const void *key
) {
201 return internal_hashmap_get(HASHMAP_BASE(h
), key
);
203 static inline void *ordered_hashmap_get(OrderedHashmap
*h
, const void *key
) {
204 return internal_hashmap_get(HASHMAP_BASE(h
), key
);
207 void *hashmap_get2(Hashmap
*h
, const void *key
, void **rkey
);
208 static inline void *ordered_hashmap_get2(OrderedHashmap
*h
, const void *key
, void **rkey
) {
209 return hashmap_get2(PLAIN_HASHMAP(h
), key
, rkey
);
212 bool internal_hashmap_contains(HashmapBase
*h
, const void *key
);
213 static inline bool hashmap_contains(Hashmap
*h
, const void *key
) {
214 return internal_hashmap_contains(HASHMAP_BASE(h
), key
);
216 static inline bool ordered_hashmap_contains(OrderedHashmap
*h
, const void *key
) {
217 return internal_hashmap_contains(HASHMAP_BASE(h
), key
);
220 void *internal_hashmap_remove(HashmapBase
*h
, const void *key
);
221 static inline void *hashmap_remove(Hashmap
*h
, const void *key
) {
222 return internal_hashmap_remove(HASHMAP_BASE(h
), key
);
224 static inline void *ordered_hashmap_remove(OrderedHashmap
*h
, const void *key
) {
225 return internal_hashmap_remove(HASHMAP_BASE(h
), key
);
228 void *hashmap_remove2(Hashmap
*h
, const void *key
, void **rkey
);
229 static inline void *ordered_hashmap_remove2(OrderedHashmap
*h
, const void *key
, void **rkey
) {
230 return hashmap_remove2(PLAIN_HASHMAP(h
), key
, rkey
);
233 void *hashmap_remove_value(Hashmap
*h
, const void *key
, void *value
);
234 static inline void *ordered_hashmap_remove_value(OrderedHashmap
*h
, const void *key
, void *value
) {
235 return hashmap_remove_value(PLAIN_HASHMAP(h
), key
, value
);
238 int hashmap_remove_and_put(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
);
239 static inline int ordered_hashmap_remove_and_put(OrderedHashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
240 return hashmap_remove_and_put(PLAIN_HASHMAP(h
), old_key
, new_key
, value
);
243 int hashmap_remove_and_replace(Hashmap
*h
, const void *old_key
, const void *new_key
, void *value
);
244 static inline int ordered_hashmap_remove_and_replace(OrderedHashmap
*h
, const void *old_key
, const void *new_key
, void *value
) {
245 return hashmap_remove_and_replace(PLAIN_HASHMAP(h
), old_key
, new_key
, value
);
248 /* Since merging data from a OrderedHashmap into a Hashmap or vice-versa
249 * should just work, allow this by having looser type-checking here. */
250 int internal_hashmap_merge(Hashmap
*h
, Hashmap
*other
);
251 #define hashmap_merge(h, other) internal_hashmap_merge(PLAIN_HASHMAP(h), PLAIN_HASHMAP(other))
252 #define ordered_hashmap_merge(h, other) hashmap_merge(h, other)
254 int internal_hashmap_reserve(HashmapBase
*h
, unsigned entries_add
);
255 static inline int hashmap_reserve(Hashmap
*h
, unsigned entries_add
) {
256 return internal_hashmap_reserve(HASHMAP_BASE(h
), entries_add
);
258 static inline int ordered_hashmap_reserve(OrderedHashmap
*h
, unsigned entries_add
) {
259 return internal_hashmap_reserve(HASHMAP_BASE(h
), entries_add
);
262 int internal_hashmap_move(HashmapBase
*h
, HashmapBase
*other
);
263 /* Unlike hashmap_merge, hashmap_move does not allow mixing the types. */
264 static inline int hashmap_move(Hashmap
*h
, Hashmap
*other
) {
265 return internal_hashmap_move(HASHMAP_BASE(h
), HASHMAP_BASE(other
));
267 static inline int ordered_hashmap_move(OrderedHashmap
*h
, OrderedHashmap
*other
) {
268 return internal_hashmap_move(HASHMAP_BASE(h
), HASHMAP_BASE(other
));
271 int internal_hashmap_move_one(HashmapBase
*h
, HashmapBase
*other
, const void *key
);
272 static inline int hashmap_move_one(Hashmap
*h
, Hashmap
*other
, const void *key
) {
273 return internal_hashmap_move_one(HASHMAP_BASE(h
), HASHMAP_BASE(other
), key
);
275 static inline int ordered_hashmap_move_one(OrderedHashmap
*h
, OrderedHashmap
*other
, const void *key
) {
276 return internal_hashmap_move_one(HASHMAP_BASE(h
), HASHMAP_BASE(other
), key
);
279 unsigned internal_hashmap_size(HashmapBase
*h
) _pure_
;
280 static inline unsigned hashmap_size(Hashmap
*h
) {
281 return internal_hashmap_size(HASHMAP_BASE(h
));
283 static inline unsigned ordered_hashmap_size(OrderedHashmap
*h
) {
284 return internal_hashmap_size(HASHMAP_BASE(h
));
287 static inline bool hashmap_isempty(Hashmap
*h
) {
288 return hashmap_size(h
) == 0;
290 static inline bool ordered_hashmap_isempty(OrderedHashmap
*h
) {
291 return ordered_hashmap_size(h
) == 0;
294 unsigned internal_hashmap_buckets(HashmapBase
*h
) _pure_
;
295 static inline unsigned hashmap_buckets(Hashmap
*h
) {
296 return internal_hashmap_buckets(HASHMAP_BASE(h
));
298 static inline unsigned ordered_hashmap_buckets(OrderedHashmap
*h
) {
299 return internal_hashmap_buckets(HASHMAP_BASE(h
));
302 bool internal_hashmap_iterate(HashmapBase
*h
, Iterator
*i
, void **value
, const void **key
);
303 static inline bool hashmap_iterate(Hashmap
*h
, Iterator
*i
, void **value
, const void **key
) {
304 return internal_hashmap_iterate(HASHMAP_BASE(h
), i
, value
, key
);
306 static inline bool ordered_hashmap_iterate(OrderedHashmap
*h
, Iterator
*i
, void **value
, const void **key
) {
307 return internal_hashmap_iterate(HASHMAP_BASE(h
), i
, value
, key
);
310 void internal_hashmap_clear(HashmapBase
*h
);
311 static inline void hashmap_clear(Hashmap
*h
) {
312 internal_hashmap_clear(HASHMAP_BASE(h
));
314 static inline void ordered_hashmap_clear(OrderedHashmap
*h
) {
315 internal_hashmap_clear(HASHMAP_BASE(h
));
318 void internal_hashmap_clear_free(HashmapBase
*h
);
319 static inline void hashmap_clear_free(Hashmap
*h
) {
320 internal_hashmap_clear_free(HASHMAP_BASE(h
));
322 static inline void ordered_hashmap_clear_free(OrderedHashmap
*h
) {
323 internal_hashmap_clear_free(HASHMAP_BASE(h
));
326 void hashmap_clear_free_free(Hashmap
*h
);
327 static inline void ordered_hashmap_clear_free_free(OrderedHashmap
*h
) {
328 hashmap_clear_free_free(PLAIN_HASHMAP(h
));
332 * Note about all *_first*() functions
334 * For plain Hashmaps and Sets the order of entries is undefined.
335 * The functions find whatever entry is first in the implementation
338 * Only for OrderedHashmaps the order is well defined and finding
339 * the first entry is O(1).
342 void *internal_hashmap_steal_first(HashmapBase
*h
);
343 static inline void *hashmap_steal_first(Hashmap
*h
) {
344 return internal_hashmap_steal_first(HASHMAP_BASE(h
));
346 static inline void *ordered_hashmap_steal_first(OrderedHashmap
*h
) {
347 return internal_hashmap_steal_first(HASHMAP_BASE(h
));
350 void *internal_hashmap_steal_first_key(HashmapBase
*h
);
351 static inline void *hashmap_steal_first_key(Hashmap
*h
) {
352 return internal_hashmap_steal_first_key(HASHMAP_BASE(h
));
354 static inline void *ordered_hashmap_steal_first_key(OrderedHashmap
*h
) {
355 return internal_hashmap_steal_first_key(HASHMAP_BASE(h
));
358 void *internal_hashmap_first_key(HashmapBase
*h
) _pure_
;
359 static inline void *hashmap_first_key(Hashmap
*h
) {
360 return internal_hashmap_first_key(HASHMAP_BASE(h
));
362 static inline void *ordered_hashmap_first_key(OrderedHashmap
*h
) {
363 return internal_hashmap_first_key(HASHMAP_BASE(h
));
366 void *internal_hashmap_first(HashmapBase
*h
) _pure_
;
367 static inline void *hashmap_first(Hashmap
*h
) {
368 return internal_hashmap_first(HASHMAP_BASE(h
));
370 static inline void *ordered_hashmap_first(OrderedHashmap
*h
) {
371 return internal_hashmap_first(HASHMAP_BASE(h
));
374 /* no hashmap_next */
375 void *ordered_hashmap_next(OrderedHashmap
*h
, const void *key
);
377 char **internal_hashmap_get_strv(HashmapBase
*h
);
378 static inline char **hashmap_get_strv(Hashmap
*h
) {
379 return internal_hashmap_get_strv(HASHMAP_BASE(h
));
381 static inline char **ordered_hashmap_get_strv(OrderedHashmap
*h
) {
382 return internal_hashmap_get_strv(HASHMAP_BASE(h
));
386 * Hashmaps are iterated in unpredictable order.
387 * OrderedHashmaps are an exception to this. They are iterated in the order
388 * the entries were inserted.
389 * It is safe to remove the current entry.
391 #define HASHMAP_FOREACH(e, h, i) \
392 for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), NULL); )
394 #define ORDERED_HASHMAP_FOREACH(e, h, i) \
395 for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), NULL); )
397 #define HASHMAP_FOREACH_KEY(e, k, h, i) \
398 for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
400 #define ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \
401 for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
403 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap
*, hashmap_free
);
404 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap
*, hashmap_free_free
);
405 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap
*, hashmap_free_free_free
);
406 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap
*, ordered_hashmap_free
);
407 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap
*, ordered_hashmap_free_free
);
408 DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap
*, ordered_hashmap_free_free_free
);
410 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
411 #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
412 #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)
413 #define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep)
414 #define _cleanup_ordered_hashmap_free_free_ _cleanup_(ordered_hashmap_free_freep)
415 #define _cleanup_ordered_hashmap_free_free_free_ _cleanup_(ordered_hashmap_free_free_freep)