Line data Source code
1 : /* Copyright (c) 2003-2004, Roger Dingledine
2 : * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3 : * Copyright (c) 2007-2021, The Tor Project, Inc. */
4 : /* See LICENSE for licensing information */
5 :
6 : /**
7 : * \file map.c
8 : *
9 : * \brief Hash-table implementations of a string-to-void* map, and of
10 : * a digest-to-void* map.
11 : **/
12 :
13 : #include "lib/container/map.h"
14 : #include "lib/ctime/di_ops.h"
15 : #include "lib/defs/digest_sizes.h"
16 : #include "lib/string/util_string.h"
17 : #include "lib/malloc/malloc.h"
18 :
19 : #include "lib/log/util_bug.h"
20 :
21 : #include <stdlib.h>
22 : #include <string.h>
23 :
24 : #include "ext/ht.h"
25 :
26 : /** Helper: Declare an entry type and a map type to implement a mapping using
27 : * ht.h. The map type will be called <b>maptype</b>. The key part of each
28 : * entry is declared using the C declaration <b>keydecl</b>. All functions
29 : * and types associated with the map get prefixed with <b>prefix</b> */
30 : #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \
31 : typedef struct prefix ## entry_t { \
32 : HT_ENTRY(prefix ## entry_t) node; \
33 : void *val; \
34 : keydecl; \
35 : } prefix ## entry_t; \
36 : struct maptype { \
37 : HT_HEAD(prefix ## impl, prefix ## entry_t) head; \
38 : }
39 :
40 : DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
41 : DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
42 : DEFINE_MAP_STRUCTS(digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_);
43 :
44 : /** Helper: compare strmap_entry_t objects by key value. */
45 : static inline int
46 23279 : strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
47 : {
48 23279 : return !strcmp(a->key, b->key);
49 : }
50 :
51 : /** Helper: return a hash value for a strmap_entry_t. */
52 : static inline unsigned int
53 27416 : strmap_entry_hash(const strmap_entry_t *a)
54 : {
55 27416 : return (unsigned) siphash24g(a->key, strlen(a->key));
56 : }
57 :
58 : /** Helper: compare digestmap_entry_t objects by key value. */
59 : static inline int
60 12325 : digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
61 : {
62 12325 : return tor_memeq(a->key, b->key, DIGEST_LEN);
63 : }
64 :
65 : /** Helper: return a hash value for a digest_map_t. */
66 : static inline unsigned int
67 19126 : digestmap_entry_hash(const digestmap_entry_t *a)
68 : {
69 19126 : return (unsigned) siphash24g(a->key, DIGEST_LEN);
70 : }
71 :
72 : /** Helper: compare digestmap_entry_t objects by key value. */
73 : static inline int
74 596 : digest256map_entries_eq(const digest256map_entry_t *a,
75 : const digest256map_entry_t *b)
76 : {
77 596 : return tor_memeq(a->key, b->key, DIGEST256_LEN);
78 : }
79 :
80 : /** Helper: return a hash value for a digest_map_t. */
81 : static inline unsigned int
82 983 : digest256map_entry_hash(const digest256map_entry_t *a)
83 : {
84 983 : return (unsigned) siphash24g(a->key, DIGEST256_LEN);
85 : }
86 :
87 50300 : HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
88 : strmap_entries_eq);
89 1987 : HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
90 : strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_);
91 :
92 90225 : HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
93 : digestmap_entries_eq);
94 29434 : HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
95 : digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_);
96 :
97 19547 : HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node,
98 : digest256map_entry_hash,
99 : digest256map_entries_eq);
100 1689 : HT_GENERATE2(digest256map_impl, digest256map_entry_t, node,
101 : digest256map_entry_hash,
102 : digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_);
103 :
104 : #define strmap_entry_free(ent) \
105 : FREE_AND_NULL(strmap_entry_t, strmap_entry_free_, (ent))
106 : #define digestmap_entry_free(ent) \
107 : FREE_AND_NULL(digestmap_entry_t, digestmap_entry_free_, (ent))
108 : #define digest256map_entry_free(ent) \
109 : FREE_AND_NULL(digest256map_entry_t, digest256map_entry_free_, (ent))
110 :
111 : static inline void
112 1327 : strmap_entry_free_(strmap_entry_t *ent)
113 : {
114 1327 : tor_free(ent->key);
115 1327 : tor_free(ent);
116 1327 : }
117 : static inline void
118 7508 : digestmap_entry_free_(digestmap_entry_t *ent)
119 : {
120 7508 : tor_free(ent);
121 7508 : }
122 : static inline void
123 97 : digest256map_entry_free_(digest256map_entry_t *ent)
124 : {
125 97 : tor_free(ent);
126 97 : }
127 :
128 : static inline void
129 27394 : strmap_assign_tmp_key(strmap_entry_t *ent, const char *key)
130 : {
131 27394 : ent->key = (char*)key;
132 27394 : }
133 : static inline void
134 19126 : digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key)
135 : {
136 19126 : memcpy(ent->key, key, DIGEST_LEN);
137 19126 : }
138 : static inline void
139 983 : digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key)
140 : {
141 983 : memcpy(ent->key, key, DIGEST256_LEN);
142 983 : }
143 : static inline void
144 1484 : strmap_assign_key(strmap_entry_t *ent, const char *key)
145 : {
146 1484 : ent->key = tor_strdup(key);
147 1484 : }
148 : static inline void
149 7712 : digestmap_assign_key(digestmap_entry_t *ent, const char *key)
150 : {
151 7712 : memcpy(ent->key, key, DIGEST_LEN);
152 7712 : }
153 : static inline void
154 108 : digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key)
155 : {
156 108 : memcpy(ent->key, key, DIGEST256_LEN);
157 108 : }
158 :
159 : /**
160 : * Macro: implement all the functions for a map that are declared in
161 : * map.h by the DECLARE_MAP_FNS() macro. You must additionally define a
162 : * prefix_entry_free_() function to free entries (and their keys), a
163 : * prefix_assign_tmp_key() function to temporarily set a stack-allocated
164 : * entry to hold a key, and a prefix_assign_key() function to set a
165 : * heap-allocated entry to hold a key.
166 : */
167 : #define IMPLEMENT_MAP_FNS(maptype, keytype, prefix) \
168 : /** Create and return a new empty map. */ \
169 : MOCK_IMPL(maptype *, \
170 : prefix##_new,(void)) \
171 : { \
172 : maptype *result; \
173 : result = tor_malloc(sizeof(maptype)); \
174 : HT_INIT(prefix##_impl, &result->head); \
175 : return result; \
176 : } \
177 : \
178 : /** Return the item from <b>map</b> whose key matches <b>key</b>, or \
179 : * NULL if no such value exists. */ \
180 : void * \
181 : prefix##_get(const maptype *map, const keytype key) \
182 : { \
183 : prefix ##_entry_t *resolve; \
184 : prefix ##_entry_t search; \
185 : tor_assert(map); \
186 : tor_assert(key); \
187 : prefix ##_assign_tmp_key(&search, key); \
188 : resolve = HT_FIND(prefix ##_impl, &map->head, &search); \
189 : if (resolve) { \
190 : return resolve->val; \
191 : } else { \
192 : return NULL; \
193 : } \
194 : } \
195 : \
196 : /** Add an entry to <b>map</b> mapping <b>key</b> to <b>val</b>; \
197 : * return the previous value, or NULL if no such value existed. */ \
198 : void * \
199 : prefix##_set(maptype *map, const keytype key, void *val) \
200 : { \
201 : prefix##_entry_t search; \
202 : void *oldval; \
203 : tor_assert(map); \
204 : tor_assert(key); \
205 : tor_assert(val); \
206 : prefix##_assign_tmp_key(&search, key); \
207 : /* We a lot of our time in this function, so the code below is */ \
208 : /* meant to optimize the check/alloc/set cycle by avoiding the two */\
209 : /* trips to the hash table that we would do in the unoptimized */ \
210 : /* version of this code. (Each of HT_INSERT and HT_FIND calls */ \
211 : /* HT_SET_HASH and HT_FIND_P.) */ \
212 : HT_FIND_OR_INSERT_(prefix##_impl, node, prefix##_entry_hash, \
213 : &(map->head), \
214 : prefix##_entry_t, &search, ptr, \
215 : { \
216 : /* we found an entry. */ \
217 : oldval = (*ptr)->val; \
218 : (*ptr)->val = val; \
219 : return oldval; \
220 : }, \
221 : { \
222 : /* We didn't find the entry. */ \
223 : prefix##_entry_t *newent = \
224 : tor_malloc_zero(sizeof(prefix##_entry_t)); \
225 : prefix##_assign_key(newent, key); \
226 : newent->val = val; \
227 : HT_FOI_INSERT_(node, &(map->head), \
228 : &search, newent, ptr); \
229 : return NULL; \
230 : }); \
231 : } \
232 : \
233 : /** Remove the value currently associated with <b>key</b> from the map. \
234 : * Return the value if one was set, or NULL if there was no entry for \
235 : * <b>key</b>. \
236 : * \
237 : * Note: you must free any storage associated with the returned value. \
238 : */ \
239 : void * \
240 : prefix##_remove(maptype *map, const keytype key) \
241 : { \
242 : prefix##_entry_t *resolve; \
243 : prefix##_entry_t search; \
244 : void *oldval; \
245 : tor_assert(map); \
246 : tor_assert(key); \
247 : prefix##_assign_tmp_key(&search, key); \
248 : resolve = HT_REMOVE(prefix##_impl, &map->head, &search); \
249 : if (resolve) { \
250 : oldval = resolve->val; \
251 : prefix##_entry_free(resolve); \
252 : return oldval; \
253 : } else { \
254 : return NULL; \
255 : } \
256 : } \
257 : \
258 : /** Return the number of elements in <b>map</b>. */ \
259 : int \
260 : prefix##_size(const maptype *map) \
261 : { \
262 : return HT_SIZE(&map->head); \
263 : } \
264 : \
265 : /** Return true iff <b>map</b> has no entries. */ \
266 : int \
267 : prefix##_isempty(const maptype *map) \
268 : { \
269 : return HT_EMPTY(&map->head); \
270 : } \
271 : \
272 : /** Assert that <b>map</b> is not corrupt. */ \
273 : void \
274 : prefix##_assert_ok(const maptype *map) \
275 : { \
276 : tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head)); \
277 : } \
278 : \
279 : /** Remove all entries from <b>map</b>, and deallocate storage for \
280 : * those entries. If free_val is provided, invoked it every value in \
281 : * <b>map</b>. */ \
282 : MOCK_IMPL(void, \
283 : prefix##_free_, (maptype *map, void (*free_val)(void*))) \
284 : { \
285 : prefix##_entry_t **ent, **next, *this; \
286 : if (!map) \
287 : return; \
288 : for (ent = HT_START(prefix##_impl, &map->head); ent != NULL; \
289 : ent = next) { \
290 : this = *ent; \
291 : next = HT_NEXT_RMV(prefix##_impl, &map->head, ent); \
292 : if (free_val) \
293 : free_val(this->val); \
294 : prefix##_entry_free(this); \
295 : } \
296 : tor_assert(HT_EMPTY(&map->head)); \
297 : HT_CLEAR(prefix##_impl, &map->head); \
298 : tor_free(map); \
299 : } \
300 : \
301 : /** return an <b>iterator</b> pointer to the front of a map. \
302 : * \
303 : * Iterator example: \
304 : * \
305 : * \code \
306 : * // uppercase values in "map", removing empty values. \
307 : * \
308 : * strmap_iter_t *iter; \
309 : * const char *key; \
310 : * void *val; \
311 : * char *cp; \
312 : * \
313 : * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) { \
314 : * strmap_iter_get(iter, &key, &val); \
315 : * cp = (char*)val; \
316 : * if (!*cp) { \
317 : * iter = strmap_iter_next_rmv(map,iter); \
318 : * free(val); \
319 : * } else { \
320 : * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp); \
321 : */ \
322 : prefix##_iter_t * \
323 : prefix##_iter_init(maptype *map) \
324 : { \
325 : tor_assert(map); \
326 : return HT_START(prefix##_impl, &map->head); \
327 : } \
328 : \
329 : /** Advance <b>iter</b> a single step to the next entry, and return \
330 : * its new value. */ \
331 : prefix##_iter_t * \
332 : prefix##_iter_next(maptype *map, prefix##_iter_t *iter) \
333 : { \
334 : tor_assert(map); \
335 : tor_assert(iter); \
336 : return HT_NEXT(prefix##_impl, &map->head, iter); \
337 : } \
338 : /** Advance <b>iter</b> a single step to the next entry, removing the \
339 : * current entry, and return its new value. */ \
340 : prefix##_iter_t * \
341 : prefix##_iter_next_rmv(maptype *map, prefix##_iter_t *iter) \
342 : { \
343 : prefix##_entry_t *rmv; \
344 : tor_assert(map); \
345 : tor_assert(iter); \
346 : tor_assert(*iter); \
347 : rmv = *iter; \
348 : iter = HT_NEXT_RMV(prefix##_impl, &map->head, iter); \
349 : prefix##_entry_free(rmv); \
350 : return iter; \
351 : } \
352 : /** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed \
353 : * to by iter. */ \
354 : void \
355 : prefix##_iter_get(prefix##_iter_t *iter, const keytype *keyp, \
356 : void **valp) \
357 : { \
358 : tor_assert(iter); \
359 : tor_assert(*iter); \
360 : tor_assert(keyp); \
361 : tor_assert(valp); \
362 : *keyp = (*iter)->key; \
363 : *valp = (*iter)->val; \
364 : } \
365 : /** Return true iff <b>iter</b> has advanced past the last entry of \
366 : * <b>map</b>. */ \
367 : int \
368 : prefix##_iter_done(prefix##_iter_t *iter) \
369 : { \
370 : return iter == NULL; \
371 : }
372 :
373 35362 : IMPLEMENT_MAP_FNS(strmap_t, char *, strmap)
374 33806 : IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap)
375 5336 : IMPLEMENT_MAP_FNS(digest256map_t, uint8_t *, digest256map)
376 :
377 : /** Same as strmap_set, but first converts <b>key</b> to lowercase. */
378 : void *
379 249 : strmap_set_lc(strmap_t *map, const char *key, void *val)
380 : {
381 : /* We could be a little faster by using strcasecmp instead, and a separate
382 : * type, but I don't think it matters. */
383 249 : void *v;
384 249 : char *lc_key = tor_strdup(key);
385 249 : tor_strlower(lc_key);
386 249 : v = strmap_set(map,lc_key,val);
387 249 : tor_free(lc_key);
388 249 : return v;
389 : }
390 :
391 : /** Same as strmap_get, but first converts <b>key</b> to lowercase. */
392 : void *
393 2504 : strmap_get_lc(const strmap_t *map, const char *key)
394 : {
395 2504 : void *v;
396 2504 : char *lc_key = tor_strdup(key);
397 2504 : tor_strlower(lc_key);
398 2504 : v = strmap_get(map,lc_key);
399 2504 : tor_free(lc_key);
400 2504 : return v;
401 : }
402 :
403 : /** Same as strmap_remove, but first converts <b>key</b> to lowercase */
404 : void *
405 1 : strmap_remove_lc(strmap_t *map, const char *key)
406 : {
407 1 : void *v;
408 1 : char *lc_key = tor_strdup(key);
409 1 : tor_strlower(lc_key);
410 1 : v = strmap_remove(map,lc_key);
411 1 : tor_free(lc_key);
412 1 : return v;
413 : }
|
