Tor  0.4.7.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 
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 strmap_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. */
52 static inline unsigned int
53 strmap_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. */
59 static inline int
60 digestmap_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. */
66 static inline unsigned int
67 digestmap_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. */
73 static inline int
74 digest256map_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. */
81 static inline unsigned int
82 digest256map_entry_hash(const digest256map_entry_t *a)
83 {
84  return (unsigned) siphash24g(a->key, DIGEST256_LEN);
85 }
86 
87 HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
88  strmap_entries_eq);
89 HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
90  strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_);
91 
92 HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
93  digestmap_entries_eq);
94 HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
95  digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_);
96 
97 HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node,
98  digest256map_entry_hash,
99  digest256map_entries_eq);
100 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 strmap_entry_free_(strmap_entry_t *ent)
113 {
114  tor_free(ent->key);
115  tor_free(ent);
116 }
117 static inline void
118 digestmap_entry_free_(digestmap_entry_t *ent)
119 {
120  tor_free(ent);
121 }
122 static inline void
123 digest256map_entry_free_(digest256map_entry_t *ent)
124 {
125  tor_free(ent);
126 }
127 
128 static inline void
129 strmap_assign_tmp_key(strmap_entry_t *ent, const char *key)
130 {
131  ent->key = (char*)key;
132 }
133 static inline void
134 digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key)
135 {
136  memcpy(ent->key, key, DIGEST_LEN);
137 }
138 static inline void
139 digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key)
140 {
141  memcpy(ent->key, key, DIGEST256_LEN);
142 }
143 static inline void
144 strmap_assign_key(strmap_entry_t *ent, const char *key)
145 {
146  ent->key = tor_strdup(key);
147 }
148 static inline void
149 digestmap_assign_key(digestmap_entry_t *ent, const char *key)
150 {
151  memcpy(ent->key, key, DIGEST_LEN);
152 }
153 static inline void
154 digest256map_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 
373 IMPLEMENT_MAP_FNS(strmap_t, char *, strmap)
374 IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap)
375 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 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  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. */
392 void *
393 strmap_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 */
404 void *
405 strmap_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_free_
void tor_free_(void *mem)
Definition: malloc.c:227
tor_reallocarray_
void * tor_reallocarray_(void *ptr, size_t sz1, size_t sz2)
Definition: malloc.c:146
malloc.h
Headers for util_malloc.c.
tor_free
#define tor_free(p)
Definition: malloc.h:52
strmap_entries_eq
static int strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
Definition: map.c:46
strmap_get_lc
void * strmap_get_lc(const strmap_t *map, const char *key)
Definition: map.c:360
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
strmap_remove_lc
void * strmap_remove_lc(strmap_t *map, const char *key)
Definition: map.c:372
DEFINE_MAP_STRUCTS
#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)
Definition: map.c:30
strmap_set_lc
void * strmap_set_lc(strmap_t *map, const char *key, void *val)
Definition: map.c:346
digestmap_entry_hash
static unsigned int digestmap_entry_hash(const digestmap_entry_t *a)
Definition: map.c:67
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:127
util_string.h
Header for util_string.c.
Generated by doxygen 1.9.1