Tor 0.4.9.0-alpha-dev
map.c
Go to the documentation of this file.
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
40DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
41DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
42DEFINE_MAP_STRUCTS(digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_);
43
44/** Helper: compare strmap_entry_t objects by key value. */
45static inline int
46strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
47{
48 return !strcmp(a->key, b->key);
49}
50
51/** Helper: return a hash value for a strmap_entry_t. */
52static inline unsigned int
53strmap_entry_hash(const strmap_entry_t *a)
54{
55 return (unsigned) siphash24g(a->key, strlen(a->key));
56}
57
58/** Helper: compare digestmap_entry_t objects by key value. */
59static inline int
60digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
61{
62 return tor_memeq(a->key, b->key, DIGEST_LEN);
63}
64
65/** Helper: return a hash value for a digest_map_t. */
66static inline unsigned int
67digestmap_entry_hash(const digestmap_entry_t *a)
68{
69 return (unsigned) siphash24g(a->key, DIGEST_LEN);
70}
71
72/** Helper: compare digestmap_entry_t objects by key value. */
73static inline int
74digest256map_entries_eq(const digest256map_entry_t *a,
75 const digest256map_entry_t *b)
76{
77 return tor_memeq(a->key, b->key, DIGEST256_LEN);
78}
79
80/** Helper: return a hash value for a digest_map_t. */
81static inline unsigned int
82digest256map_entry_hash(const digest256map_entry_t *a)
83{
84 return (unsigned) siphash24g(a->key, DIGEST256_LEN);
85}
86
87HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
88 strmap_entries_eq);
89HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
90 strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_);
91
92HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
93 digestmap_entries_eq);
94HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
95 digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_);
96
97HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node,
98 digest256map_entry_hash,
99 digest256map_entries_eq);
100HT_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
111static inline void
112strmap_entry_free_(strmap_entry_t *ent)
113{
114 tor_free(ent->key);
115 tor_free(ent);
116}
117static inline void
118digestmap_entry_free_(digestmap_entry_t *ent)
119{
120 tor_free(ent);
121}
122static inline void
123digest256map_entry_free_(digest256map_entry_t *ent)
124{
125 tor_free(ent);
126}
127
128static inline void
129strmap_assign_tmp_key(strmap_entry_t *ent, const char *key)
130{
131 ent->key = (char*)key;
132}
133static inline void
134digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key)
135{
136 memcpy(ent->key, key, DIGEST_LEN);
137}
138static inline void
139digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key)
140{
141 memcpy(ent->key, key, DIGEST256_LEN);
142}
143static inline void
144strmap_assign_key(strmap_entry_t *ent, const char *key)
145{
146 ent->key = tor_strdup(key);
147}
148static inline void
149digestmap_assign_key(digestmap_entry_t *ent, const char *key)
150{
151 memcpy(ent->key, key, DIGEST_LEN);
152}
153static inline void
154digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key)
155{
156 memcpy(ent->key, key, DIGEST256_LEN);
157}
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
373IMPLEMENT_MAP_FNS(strmap_t, char *, strmap)
374IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap)
375IMPLEMENT_MAP_FNS(digest256map_t, uint8_t *, digest256map)
376
377/** Same as strmap_set, but first converts <b>key</b> to lowercase. */
378void *
379strmap_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 void *v;
384 char *lc_key = tor_strdup(key);
385 tor_strlower(lc_key);
386 v = strmap_set(map,lc_key,val);
387 tor_free(lc_key);
388 return v;
389}
390
391/** Same as strmap_get, but first converts <b>key</b> to lowercase. */
392void *
393strmap_get_lc(const strmap_t *map, const char *key)
394{
395 void *v;
396 char *lc_key = tor_strdup(key);
397 tor_strlower(lc_key);
398 v = strmap_get(map,lc_key);
399 tor_free(lc_key);
400 return v;
401}
402
403/** Same as strmap_remove, but first converts <b>key</b> to lowercase */
404void *
405strmap_remove_lc(strmap_t *map, const char *key)
406{
407 void *v;
408 char *lc_key = tor_strdup(key);
409 tor_strlower(lc_key);
410 v = strmap_remove(map,lc_key);
411 tor_free(lc_key);
412 return v;
413}
tor_memeq
int tor_memeq(const void *a, const void *b, size_t sz)
Definition: di_ops.c:107
di_ops.h
Headers for di_ops.c.
digest_sizes.h
Definitions for common sizes of cryptographic digests.
DIGEST_LEN
#define DIGEST_LEN
Definition: digest_sizes.h:20
DIGEST256_LEN
#define DIGEST256_LEN
Definition: digest_sizes.h:23
HT_PROTOTYPE
HT_PROTOTYPE(hs_circuitmap_ht, circuit_t, hs_circuitmap_node, hs_circuit_hash_token, hs_circuits_have_same_token)
tor_reallocarray_
void * tor_reallocarray_(void *ptr, size_t sz1, size_t sz2)
Definition: malloc.c:146
tor_free_
void tor_free_(void *mem)
Definition: malloc.c:227
malloc.h
Headers for util_malloc.c.
tor_free
#define tor_free(p)
Definition: malloc.h:56
strmap_entries_eq
static int strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
Definition: map.c:46
strmap_entry_hash
static unsigned int strmap_entry_hash(const strmap_entry_t *a)
Definition: map.c:53
digest256map_entries_eq
static int digest256map_entries_eq(const digest256map_entry_t *a, const digest256map_entry_t *b)
Definition: map.c:74
IMPLEMENT_MAP_FNS
#define IMPLEMENT_MAP_FNS(maptype, keytype, prefix)
Definition: map.c:167
digest256map_entry_hash
static unsigned int digest256map_entry_hash(const digest256map_entry_t *a)
Definition: map.c:82
digestmap_entries_eq
static int digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
Definition: map.c:60
DEFINE_MAP_STRUCTS
#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)
Definition: map.c:30
strmap_get_lc
void * strmap_get_lc(const strmap_t *map, const char *key)
Definition: map.c:360
strmap_remove_lc
void * strmap_remove_lc(strmap_t *map, const char *key)
Definition: map.c:372
digestmap_entry_hash
static unsigned int digestmap_entry_hash(const digestmap_entry_t *a)
Definition: map.c:67
strmap_set_lc
void * strmap_set_lc(strmap_t *map, const char *key, void *val)
Definition: map.c:346
map.h
Headers for map.c.
util_bug.h
Macros to manage assertions, fatal and non-fatal.
tor_strlower
void tor_strlower(char *s)
Definition: util_string.c:129
util_string.h
Header for util_string.c.
Generated by doxygen 1.9.4