Line data Source code
1 : /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
2 :
3 : #pragma once
4 :
5 : /***
6 : This file is part of systemd.
7 :
8 : Copyright 2010 Lennart Poettering
9 : Copyright 2014 Michal Schmidt
10 :
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.
15 :
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.
20 :
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/>.
23 : ***/
24 :
25 : #include <stdbool.h>
26 :
27 : #include "macro.h"
28 : #include "util.h"
29 :
30 : /*
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.
34 : *
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
39 : */
40 :
41 : #define HASH_KEY_SIZE 16
42 :
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;
48 :
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 */
53 :
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
56 : * directly. */
57 : typedef struct {
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 */
64 : #endif
65 : } Iterator;
66 :
67 : #define _IDX_ITERATOR_FIRST (UINT_MAX - 1)
68 : #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL })
69 :
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);
72 :
73 : struct hash_ops {
74 : hash_func_t hash;
75 : compare_func_t compare;
76 : };
77 :
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;
81 :
82 : /* This will compare the passed pointers directly, and will not
83 : * dereference them. This is hence not useful for strings or
84 : * suchlike. */
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;
88 :
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;
95 :
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! */
98 : #if SIZEOF_DEV_T != 8
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
104 : };
105 : #else
106 : #define devt_hash_func uint64_hash_func
107 : #define devt_compare_func uint64_compare_func
108 : #define devt_hash_ops uint64_hash_ops
109 : #endif
110 :
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*))
117 :
118 : #define PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h) \
119 : (__builtin_types_compatible_p(typeof(h), Hashmap*) || \
120 : __builtin_types_compatible_p(typeof(h), OrderedHashmap*)) \
121 :
122 : #define HASHMAP_BASE(h) \
123 : __builtin_choose_expr(PTR_COMPATIBLE_WITH_HASHMAP_BASE(h), \
124 : (HashmapBase*)(h), \
125 : (void)0)
126 :
127 : #define PLAIN_HASHMAP(h) \
128 : __builtin_choose_expr(PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h), \
129 : (Hashmap*)(h), \
130 : (void)0)
131 :
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
136 : #else
137 : # define HASHMAP_DEBUG_PARAMS
138 : # define HASHMAP_DEBUG_SRC_ARGS
139 : # define HASHMAP_DEBUG_PASS_ARGS
140 : #endif
141 :
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)
146 :
147 : HashmapBase *internal_hashmap_free(HashmapBase *h);
148 2045 : static inline Hashmap *hashmap_free(Hashmap *h) {
149 2045 : return (void*)internal_hashmap_free(HASHMAP_BASE(h));
150 : }
151 507 : static inline OrderedHashmap *ordered_hashmap_free(OrderedHashmap *h) {
152 507 : return (void*)internal_hashmap_free(HASHMAP_BASE(h));
153 : }
154 :
155 : HashmapBase *internal_hashmap_free_free(HashmapBase *h);
156 213 : static inline Hashmap *hashmap_free_free(Hashmap *h) {
157 213 : return (void*)internal_hashmap_free_free(HASHMAP_BASE(h));
158 : }
159 1470 : static inline OrderedHashmap *ordered_hashmap_free_free(OrderedHashmap *h) {
160 1470 : return (void*)internal_hashmap_free_free(HASHMAP_BASE(h));
161 : }
162 :
163 : Hashmap *hashmap_free_free_free(Hashmap *h);
164 878 : static inline OrderedHashmap *ordered_hashmap_free_free_free(OrderedHashmap *h) {
165 878 : return (void*)hashmap_free_free_free(PLAIN_HASHMAP(h));
166 : }
167 :
168 : HashmapBase *internal_hashmap_copy(HashmapBase *h);
169 1 : static inline Hashmap *hashmap_copy(Hashmap *h) {
170 1 : return (Hashmap*) internal_hashmap_copy(HASHMAP_BASE(h));
171 : }
172 1 : static inline OrderedHashmap *ordered_hashmap_copy(OrderedHashmap *h) {
173 1 : return (OrderedHashmap*) internal_hashmap_copy(HASHMAP_BASE(h));
174 : }
175 :
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)
180 :
181 : int hashmap_put(Hashmap *h, const void *key, void *value);
182 1051649 : static inline int ordered_hashmap_put(OrderedHashmap *h, const void *key, void *value) {
183 1051649 : return hashmap_put(PLAIN_HASHMAP(h), key, value);
184 : }
185 :
186 : int hashmap_update(Hashmap *h, const void *key, void *value);
187 2 : static inline int ordered_hashmap_update(OrderedHashmap *h, const void *key, void *value) {
188 2 : return hashmap_update(PLAIN_HASHMAP(h), key, value);
189 : }
190 :
191 : int hashmap_replace(Hashmap *h, const void *key, void *value);
192 5378 : static inline int ordered_hashmap_replace(OrderedHashmap *h, const void *key, void *value) {
193 5378 : return hashmap_replace(PLAIN_HASHMAP(h), key, value);
194 : }
195 :
196 : void *internal_hashmap_get(HashmapBase *h, const void *key);
197 1184951 : static inline void *hashmap_get(Hashmap *h, const void *key) {
198 1184951 : return internal_hashmap_get(HASHMAP_BASE(h), key);
199 : }
200 1076206 : static inline void *ordered_hashmap_get(OrderedHashmap *h, const void *key) {
201 1076206 : return internal_hashmap_get(HASHMAP_BASE(h), key);
202 : }
203 :
204 : void *hashmap_get2(Hashmap *h, const void *key, void **rkey);
205 5379 : static inline void *ordered_hashmap_get2(OrderedHashmap *h, const void *key, void **rkey) {
206 5379 : return hashmap_get2(PLAIN_HASHMAP(h), key, rkey);
207 : }
208 :
209 : bool internal_hashmap_contains(HashmapBase *h, const void *key);
210 3153691 : static inline bool hashmap_contains(Hashmap *h, const void *key) {
211 3153691 : return internal_hashmap_contains(HASHMAP_BASE(h), key);
212 : }
213 3151874 : static inline bool ordered_hashmap_contains(OrderedHashmap *h, const void *key) {
214 3151874 : return internal_hashmap_contains(HASHMAP_BASE(h), key);
215 : }
216 :
217 : void *internal_hashmap_remove(HashmapBase *h, const void *key);
218 1053844 : static inline void *hashmap_remove(Hashmap *h, const void *key) {
219 1053844 : return internal_hashmap_remove(HASHMAP_BASE(h), key);
220 : }
221 1050631 : static inline void *ordered_hashmap_remove(OrderedHashmap *h, const void *key) {
222 1050631 : return internal_hashmap_remove(HASHMAP_BASE(h), key);
223 : }
224 :
225 : void *hashmap_remove2(Hashmap *h, const void *key, void **rkey);
226 23 : static inline void *ordered_hashmap_remove2(OrderedHashmap *h, const void *key, void **rkey) {
227 23 : return hashmap_remove2(PLAIN_HASHMAP(h), key, rkey);
228 : }
229 :
230 : void *hashmap_remove_value(Hashmap *h, const void *key, void *value);
231 4 : static inline void *ordered_hashmap_remove_value(OrderedHashmap *h, const void *key, void *value) {
232 4 : return hashmap_remove_value(PLAIN_HASHMAP(h), key, value);
233 : }
234 :
235 : int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);
236 4 : static inline int ordered_hashmap_remove_and_put(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
237 4 : return hashmap_remove_and_put(PLAIN_HASHMAP(h), old_key, new_key, value);
238 : }
239 :
240 : int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value);
241 24 : static inline int ordered_hashmap_remove_and_replace(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
242 24 : return hashmap_remove_and_replace(PLAIN_HASHMAP(h), old_key, new_key, value);
243 : }
244 :
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)
250 :
251 : int internal_hashmap_reserve(HashmapBase *h, unsigned entries_add);
252 4 : static inline int hashmap_reserve(Hashmap *h, unsigned entries_add) {
253 4 : return internal_hashmap_reserve(HASHMAP_BASE(h), entries_add);
254 : }
255 4 : static inline int ordered_hashmap_reserve(OrderedHashmap *h, unsigned entries_add) {
256 4 : return internal_hashmap_reserve(HASHMAP_BASE(h), entries_add);
257 : }
258 :
259 : int internal_hashmap_move(HashmapBase *h, HashmapBase *other);
260 : /* Unlike hashmap_merge, hashmap_move does not allow mixing the types. */
261 2 : static inline int hashmap_move(Hashmap *h, Hashmap *other) {
262 2 : return internal_hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
263 : }
264 2 : static inline int ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
265 2 : return internal_hashmap_move(HASHMAP_BASE(h), HASHMAP_BASE(other));
266 : }
267 :
268 : int internal_hashmap_move_one(HashmapBase *h, HashmapBase *other, const void *key);
269 5 : static inline int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
270 5 : return internal_hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
271 : }
272 5 : static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) {
273 5 : return internal_hashmap_move_one(HASHMAP_BASE(h), HASHMAP_BASE(other), key);
274 : }
275 :
276 : unsigned internal_hashmap_size(HashmapBase *h) _pure_;
277 1067472 : static inline unsigned hashmap_size(Hashmap *h) {
278 1067472 : return internal_hashmap_size(HASHMAP_BASE(h));
279 : }
280 1051995 : static inline unsigned ordered_hashmap_size(OrderedHashmap *h) {
281 1051995 : return internal_hashmap_size(HASHMAP_BASE(h));
282 : }
283 :
284 1066656 : static inline bool hashmap_isempty(Hashmap *h) {
285 1066656 : return hashmap_size(h) == 0;
286 : }
287 1050632 : static inline bool ordered_hashmap_isempty(OrderedHashmap *h) {
288 1050632 : return ordered_hashmap_size(h) == 0;
289 : }
290 :
291 : unsigned internal_hashmap_buckets(HashmapBase *h) _pure_;
292 10 : static inline unsigned hashmap_buckets(Hashmap *h) {
293 10 : return internal_hashmap_buckets(HASHMAP_BASE(h));
294 : }
295 10 : static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) {
296 10 : return internal_hashmap_buckets(HASHMAP_BASE(h));
297 : }
298 :
299 : bool internal_hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key);
300 7599 : static inline bool hashmap_iterate(Hashmap *h, Iterator *i, void **value, const void **key) {
301 7599 : return internal_hashmap_iterate(HASHMAP_BASE(h), i, value, key);
302 : }
303 63074 : static inline bool ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, void **value, const void **key) {
304 63074 : return internal_hashmap_iterate(HASHMAP_BASE(h), i, value, key);
305 : }
306 :
307 : void internal_hashmap_clear(HashmapBase *h);
308 20 : static inline void hashmap_clear(Hashmap *h) {
309 20 : internal_hashmap_clear(HASHMAP_BASE(h));
310 20 : }
311 20 : static inline void ordered_hashmap_clear(OrderedHashmap *h) {
312 20 : internal_hashmap_clear(HASHMAP_BASE(h));
313 20 : }
314 :
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));
318 : }
319 : static inline void ordered_hashmap_clear_free(OrderedHashmap *h) {
320 : internal_hashmap_clear_free(HASHMAP_BASE(h));
321 : }
322 :
323 : void hashmap_clear_free_free(Hashmap *h);
324 1 : static inline void ordered_hashmap_clear_free_free(OrderedHashmap *h) {
325 1 : hashmap_clear_free_free(PLAIN_HASHMAP(h));
326 1 : }
327 :
328 : /*
329 : * Note about all *_first*() functions
330 : *
331 : * For plain Hashmaps and Sets the order of entries is undefined.
332 : * The functions find whatever entry is first in the implementation
333 : * internal order.
334 : *
335 : * Only for OrderedHashmaps the order is well defined and finding
336 : * the first entry is O(1).
337 : */
338 :
339 : void *internal_hashmap_steal_first(HashmapBase *h);
340 472 : static inline void *hashmap_steal_first(Hashmap *h) {
341 472 : return internal_hashmap_steal_first(HASHMAP_BASE(h));
342 : }
343 1310 : static inline void *ordered_hashmap_steal_first(OrderedHashmap *h) {
344 1310 : return internal_hashmap_steal_first(HASHMAP_BASE(h));
345 : }
346 :
347 : void *internal_hashmap_steal_first_key(HashmapBase *h);
348 2 : static inline void *hashmap_steal_first_key(Hashmap *h) {
349 2 : return internal_hashmap_steal_first_key(HASHMAP_BASE(h));
350 : }
351 2 : static inline void *ordered_hashmap_steal_first_key(OrderedHashmap *h) {
352 2 : return internal_hashmap_steal_first_key(HASHMAP_BASE(h));
353 : }
354 :
355 : void *internal_hashmap_first_key(HashmapBase *h) _pure_;
356 1050626 : static inline void *hashmap_first_key(Hashmap *h) {
357 1050626 : return internal_hashmap_first_key(HASHMAP_BASE(h));
358 : }
359 1050628 : static inline void *ordered_hashmap_first_key(OrderedHashmap *h) {
360 1050628 : return internal_hashmap_first_key(HASHMAP_BASE(h));
361 : }
362 :
363 : void *internal_hashmap_first(HashmapBase *h) _pure_;
364 1807 : static inline void *hashmap_first(Hashmap *h) {
365 1807 : return internal_hashmap_first(HASHMAP_BASE(h));
366 : }
367 281 : static inline void *ordered_hashmap_first(OrderedHashmap *h) {
368 281 : return internal_hashmap_first(HASHMAP_BASE(h));
369 : }
370 :
371 : /* no hashmap_next */
372 : void *ordered_hashmap_next(OrderedHashmap *h, const void *key);
373 :
374 : char **internal_hashmap_get_strv(HashmapBase *h);
375 11 : static inline char **hashmap_get_strv(Hashmap *h) {
376 11 : return internal_hashmap_get_strv(HASHMAP_BASE(h));
377 : }
378 1 : static inline char **ordered_hashmap_get_strv(OrderedHashmap *h) {
379 1 : return internal_hashmap_get_strv(HASHMAP_BASE(h));
380 : }
381 :
382 : /*
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.
387 : */
388 : #define HASHMAP_FOREACH(e, h, i) \
389 : for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), NULL); )
390 :
391 : #define ORDERED_HASHMAP_FOREACH(e, h, i) \
392 : for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), NULL); )
393 :
394 : #define HASHMAP_FOREACH_KEY(e, k, h, i) \
395 : for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
396 :
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)); )
399 :
400 20 : DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
401 3 : DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free);
402 1 : DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free_free);
403 11 : DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free);
404 : DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free);
405 1 : DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free_free);
406 :
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)
|
