]>
Commit | Line | Data |
---|---|---|
03467c88 | 1 | /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ |
60918275 | 2 | |
c2f1db8f | 3 | #pragma once |
60918275 | 4 | |
a7334b09 LP |
5 | /*** |
6 | This file is part of systemd. | |
7 | ||
8 | Copyright 2010 Lennart Poettering | |
9 | ||
10 | systemd is free software; you can redistribute it and/or modify it | |
5430f7f2 LP |
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 | |
a7334b09 LP |
13 | (at your option) any later version. |
14 | ||
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 | |
5430f7f2 | 18 | Lesser General Public License for more details. |
a7334b09 | 19 | |
5430f7f2 | 20 | You should have received a copy of the GNU Lesser General Public License |
a7334b09 LP |
21 | along with systemd; If not, see <http://www.gnu.org/licenses/>. |
22 | ***/ | |
23 | ||
60918275 LP |
24 | #include <stdbool.h> |
25 | ||
44a6b1b6 | 26 | #include "macro.h" |
5e2f14e6 | 27 | #include "util.h" |
44a6b1b6 | 28 | |
60918275 LP |
29 | /* Pretty straightforward hash table implementation. As a minor |
30 | * optimization a NULL hashmap object will be treated as empty hashmap | |
31 | * for all read operations. That way it is not necessary to | |
32 | * instantiate an object for each Hashmap use. */ | |
33 | ||
9bf3b535 LP |
34 | #define HASH_KEY_SIZE 16 |
35 | ||
60918275 | 36 | typedef struct Hashmap Hashmap; |
5ba43716 | 37 | typedef struct OrderedHashmap OrderedHashmap; |
034c6ed7 LP |
38 | typedef struct _IteratorStruct _IteratorStruct; |
39 | typedef _IteratorStruct* Iterator; | |
40 | ||
41 | #define ITERATOR_FIRST ((Iterator) 0) | |
42 | #define ITERATOR_LAST ((Iterator) -1) | |
60918275 | 43 | |
9bf3b535 | 44 | typedef unsigned long (*hash_func_t)(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]); |
60918275 LP |
45 | typedef int (*compare_func_t)(const void *a, const void *b); |
46 | ||
d5099efc MS |
47 | struct hash_ops { |
48 | hash_func_t hash; | |
49 | compare_func_t compare; | |
50 | }; | |
51 | ||
9bf3b535 | 52 | unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; |
44a6b1b6 | 53 | int string_compare_func(const void *a, const void *b) _pure_; |
d5099efc | 54 | extern const struct hash_ops string_hash_ops; |
60918275 | 55 | |
1210bc66 LP |
56 | /* This will compare the passed pointers directly, and will not |
57 | * dereference them. This is hence not useful for strings or | |
58 | * suchlike. */ | |
9bf3b535 | 59 | unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; |
44a6b1b6 | 60 | int trivial_compare_func(const void *a, const void *b) _const_; |
d5099efc | 61 | extern const struct hash_ops trivial_hash_ops; |
60918275 | 62 | |
de99c9dc LP |
63 | /* 32bit values we can always just embedd in the pointer itself, but |
64 | * in order to support 32bit archs we need store 64bit values | |
65 | * indirectly, since they don't fit in a pointer. */ | |
9bf3b535 | 66 | unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; |
44a6b1b6 | 67 | int uint64_compare_func(const void *a, const void *b) _pure_; |
d5099efc | 68 | extern const struct hash_ops uint64_hash_ops; |
a4bcff5b | 69 | |
de99c9dc LP |
70 | /* On some archs dev_t is 32bit, and on others 64bit. And sometimes |
71 | * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */ | |
72 | #if SIZEOF_DEV_T != 8 | |
73 | unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; | |
74 | int devt_compare_func(const void *a, const void *b) _pure_; | |
d5099efc MS |
75 | extern const struct hash_ops devt_hash_ops = { |
76 | .hash = devt_hash_func, | |
77 | .compare = devt_compare_func | |
78 | }; | |
de99c9dc | 79 | #else |
de99c9dc LP |
80 | #define devt_hash_func uint64_hash_func |
81 | #define devt_compare_func uint64_compare_func | |
d5099efc | 82 | #define devt_hash_ops uint64_hash_ops |
de99c9dc LP |
83 | #endif |
84 | ||
d5099efc | 85 | Hashmap *hashmap_new(const struct hash_ops *hash_ops); |
5ba43716 MS |
86 | static inline OrderedHashmap *ordered_hashmap_new(const struct hash_ops *hash_ops) { |
87 | return (OrderedHashmap*) hashmap_new(hash_ops); | |
88 | } | |
91cdde8a | 89 | void hashmap_free(Hashmap *h); |
5ba43716 MS |
90 | static inline void ordered_hashmap_free(OrderedHashmap *h) { |
91 | hashmap_free((Hashmap*) h); | |
92 | } | |
449ddb2d | 93 | void hashmap_free_free(Hashmap *h); |
5ba43716 MS |
94 | static inline void ordered_hashmap_free_free(OrderedHashmap *h) { |
95 | hashmap_free_free((Hashmap*) h); | |
96 | } | |
fabe5c0e | 97 | void hashmap_free_free_free(Hashmap *h); |
5ba43716 MS |
98 | static inline void ordered_hashmap_free_free_free(OrderedHashmap *h) { |
99 | hashmap_free_free_free((Hashmap*) h); | |
100 | } | |
91cdde8a | 101 | Hashmap *hashmap_copy(Hashmap *h); |
5ba43716 MS |
102 | static inline OrderedHashmap *ordered_hashmap_copy(OrderedHashmap *h) { |
103 | return (OrderedHashmap*) hashmap_copy((Hashmap*) h); | |
104 | } | |
d5099efc | 105 | int hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops); |
5ba43716 MS |
106 | static inline int ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops) { |
107 | return hashmap_ensure_allocated((Hashmap**) h, hash_ops); | |
108 | } | |
60918275 LP |
109 | |
110 | int hashmap_put(Hashmap *h, const void *key, void *value); | |
5ba43716 MS |
111 | static inline int ordered_hashmap_put(OrderedHashmap *h, const void *key, void *value) { |
112 | return hashmap_put((Hashmap*) h, key, value); | |
113 | } | |
d99ae53a | 114 | int hashmap_update(Hashmap *h, const void *key, void *value); |
5ba43716 MS |
115 | static inline int ordered_hashmap_update(OrderedHashmap *h, const void *key, void *value) { |
116 | return hashmap_update((Hashmap*) h, key, value); | |
117 | } | |
3158713e | 118 | int hashmap_replace(Hashmap *h, const void *key, void *value); |
5ba43716 MS |
119 | static inline int ordered_hashmap_replace(OrderedHashmap *h, const void *key, void *value) { |
120 | return hashmap_replace((Hashmap*) h, key, value); | |
121 | } | |
2f79c10e | 122 | void *hashmap_get(Hashmap *h, const void *key); |
5ba43716 MS |
123 | static inline void *ordered_hashmap_get(OrderedHashmap *h, const void *key) { |
124 | return hashmap_get((Hashmap*) h, key); | |
125 | } | |
2f79c10e | 126 | void *hashmap_get2(Hashmap *h, const void *key, void **rkey); |
5ba43716 MS |
127 | static inline void *ordered_hashmap_get2(OrderedHashmap *h, const void *key, void **rkey) { |
128 | return hashmap_get2((Hashmap*) h, key, rkey); | |
129 | } | |
96342de6 | 130 | bool hashmap_contains(Hashmap *h, const void *key); |
5ba43716 MS |
131 | static inline bool ordered_hashmap_contains(OrderedHashmap *h, const void *key) { |
132 | return hashmap_contains((Hashmap*) h, key); | |
133 | } | |
2f79c10e | 134 | void *hashmap_remove(Hashmap *h, const void *key); |
5ba43716 MS |
135 | static inline void *ordered_hashmap_remove(OrderedHashmap *h, const void *key) { |
136 | return hashmap_remove((Hashmap*) h, key); | |
137 | } | |
c582a3b3 | 138 | void *hashmap_remove2(Hashmap *h, const void *key, void **rkey); |
5ba43716 MS |
139 | static inline void *ordered_hashmap_remove2(OrderedHashmap *h, const void *key, void **rkey) { |
140 | return hashmap_remove2((Hashmap*) h, key, rkey); | |
141 | } | |
2f79c10e | 142 | void *hashmap_remove_value(Hashmap *h, const void *key, void *value); |
5ba43716 MS |
143 | static inline void *ordered_hashmap_remove_value(OrderedHashmap *h, const void *key, void *value) { |
144 | return hashmap_remove_value((Hashmap*) h, key, value); | |
145 | } | |
101d8e63 | 146 | int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value); |
5ba43716 MS |
147 | static inline int ordered_hashmap_remove_and_put(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) { |
148 | return hashmap_remove_and_put((Hashmap*) h, old_key, new_key, value); | |
149 | } | |
8fe914ec | 150 | int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value); |
5ba43716 MS |
151 | static inline int ordered_hashmap_remove_and_replace(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) { |
152 | return hashmap_remove_and_replace((Hashmap*) h, old_key, new_key, value); | |
153 | } | |
60918275 | 154 | |
91cdde8a | 155 | int hashmap_merge(Hashmap *h, Hashmap *other); |
5ba43716 MS |
156 | static inline int ordered_hashmap_merge(OrderedHashmap *h, OrderedHashmap *other) { |
157 | return hashmap_merge((Hashmap*) h, (Hashmap*) other); | |
158 | } | |
e4c691b5 MS |
159 | int hashmap_reserve(Hashmap *h, unsigned entries_add); |
160 | static inline int ordered_hashmap_reserve(OrderedHashmap *h, unsigned entries_add) { | |
161 | return hashmap_reserve((Hashmap*) h, entries_add); | |
162 | } | |
7ad63f57 MS |
163 | int hashmap_move(Hashmap *h, Hashmap *other); |
164 | static inline int ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) { | |
165 | return hashmap_move((Hashmap*) h, (Hashmap*) other); | |
5ba43716 | 166 | } |
101d8e63 | 167 | int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key); |
5ba43716 MS |
168 | static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) { |
169 | return hashmap_move_one((Hashmap*) h, (Hashmap*) other, key); | |
170 | } | |
91cdde8a | 171 | |
44a6b1b6 | 172 | unsigned hashmap_size(Hashmap *h) _pure_; |
5ba43716 MS |
173 | static inline unsigned ordered_hashmap_size(OrderedHashmap *h) { |
174 | return hashmap_size((Hashmap*) h); | |
175 | } | |
44a6b1b6 | 176 | bool hashmap_isempty(Hashmap *h) _pure_; |
5ba43716 MS |
177 | static inline bool ordered_hashmap_isempty(OrderedHashmap *h) { |
178 | return hashmap_isempty((Hashmap*) h); | |
179 | } | |
45fa9e29 | 180 | unsigned hashmap_buckets(Hashmap *h) _pure_; |
5ba43716 MS |
181 | static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) { |
182 | return hashmap_buckets((Hashmap*) h); | |
183 | } | |
60918275 | 184 | |
034c6ed7 | 185 | void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key); |
5ba43716 MS |
186 | static inline void *ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, const void **key) { |
187 | return hashmap_iterate((Hashmap*) h, i, key); | |
188 | } | |
60918275 | 189 | |
11dd41ce | 190 | void hashmap_clear(Hashmap *h); |
5ba43716 MS |
191 | static inline void ordered_hashmap_clear(OrderedHashmap *h) { |
192 | hashmap_clear((Hashmap*) h); | |
193 | } | |
9946996c | 194 | void hashmap_clear_free(Hashmap *h); |
5ba43716 MS |
195 | static inline void ordered_hashmap_clear_free(OrderedHashmap *h) { |
196 | hashmap_clear_free((Hashmap*) h); | |
197 | } | |
fabe5c0e | 198 | void hashmap_clear_free_free(Hashmap *h); |
5ba43716 MS |
199 | static inline void ordered_hashmap_clear_free_free(OrderedHashmap *h) { |
200 | hashmap_clear_free_free((Hashmap*) h); | |
201 | } | |
9946996c | 202 | |
60918275 | 203 | void *hashmap_steal_first(Hashmap *h); |
5ba43716 MS |
204 | static inline void *ordered_hashmap_steal_first(OrderedHashmap *h) { |
205 | return hashmap_steal_first((Hashmap*) h); | |
206 | } | |
22be093f | 207 | void *hashmap_steal_first_key(Hashmap *h); |
5ba43716 MS |
208 | static inline void *ordered_hashmap_steal_first_key(OrderedHashmap *h) { |
209 | return hashmap_steal_first_key((Hashmap*) h); | |
210 | } | |
44a6b1b6 | 211 | void *hashmap_first(Hashmap *h) _pure_; |
5ba43716 MS |
212 | static inline void *ordered_hashmap_first(OrderedHashmap *h) { |
213 | return hashmap_first((Hashmap*) h); | |
214 | } | |
44a6b1b6 | 215 | void *hashmap_first_key(Hashmap *h) _pure_; |
5ba43716 MS |
216 | static inline void *ordered_hashmap_first_key(OrderedHashmap *h) { |
217 | return hashmap_first_key((Hashmap*) h); | |
218 | } | |
60918275 | 219 | |
3c1668da | 220 | void *hashmap_next(Hashmap *h, const void *key); |
5ba43716 MS |
221 | static inline void *ordered_hashmap_next(OrderedHashmap *h, const void *key) { |
222 | return hashmap_next((Hashmap*) h, key); | |
223 | } | |
3c1668da | 224 | |
db1413d7 | 225 | char **hashmap_get_strv(Hashmap *h); |
5ba43716 MS |
226 | static inline char **ordered_hashmap_get_strv(OrderedHashmap *h) { |
227 | return hashmap_get_strv((Hashmap*) h); | |
228 | } | |
db1413d7 | 229 | |
034c6ed7 | 230 | #define HASHMAP_FOREACH(e, h, i) \ |
aed5e44d | 231 | for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), NULL); (e); (e) = hashmap_iterate((h), &(i), NULL)) |
60918275 | 232 | |
5ba43716 MS |
233 | #define ORDERED_HASHMAP_FOREACH(e, h, i) \ |
234 | for ((i) = ITERATOR_FIRST, (e) = ordered_hashmap_iterate((h), &(i), NULL); \ | |
235 | (e); \ | |
236 | (e) = ordered_hashmap_iterate((h), &(i), NULL)) | |
237 | ||
034c6ed7 | 238 | #define HASHMAP_FOREACH_KEY(e, k, h, i) \ |
aed5e44d | 239 | for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), (const void**) &(k)); (e); (e) = hashmap_iterate((h), &(i), (const void**) &(k))) |
11dd41ce | 240 | |
5ba43716 MS |
241 | #define ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \ |
242 | for ((i) = ITERATOR_FIRST, (e) = ordered_hashmap_iterate((h), &(i), (const void**) &(k)); \ | |
243 | (e); \ | |
244 | (e) = ordered_hashmap_iterate((h), &(i), (const void**) &(k))) | |
245 | ||
5e2f14e6 LP |
246 | DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free); |
247 | DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free); | |
248 | DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free_free); | |
5ba43716 MS |
249 | DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free); |
250 | DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free); | |
251 | DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free_free); | |
5e2f14e6 LP |
252 | #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep) |
253 | #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep) | |
254 | #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep) | |
5ba43716 MS |
255 | #define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep) |
256 | #define _cleanup_ordered_hashmap_free_free_ _cleanup_(ordered_hashmap_free_freep) | |
257 | #define _cleanup_ordered_hashmap_free_free_free_ _cleanup_(ordered_hashmap_free_free_freep) |