tor  0.4.1.1-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-2019, The Tor Project, Inc. */
4 /* See LICENSE for licensing information */
5 
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 
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 
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 
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 
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 
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 
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 
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,
89 HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
91 
92 HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
94 HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
96 
97 HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node,
100 HT_GENERATE2(digest256map_impl, digest256map_entry_t, node,
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 
167 #define IMPLEMENT_MAP_FNS(maptype, keytype, prefix) \
168  \
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  \
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  \
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  \
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  \
259  int \
260  prefix##_size(const maptype *map) \
261  { \
262  return HT_SIZE(&map->head); \
263  } \
264  \
265  \
266  int \
267  prefix##_isempty(const maptype *map) \
268  { \
269  return HT_EMPTY(&map->head); \
270  } \
271  \
272  \
273  void \
274  prefix##_assert_ok(const maptype *map) \
275  { \
276  tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head)); \
277  } \
278  \
279  \
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  \
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  \
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  \
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  \
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  \
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 
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 
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 
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 }
#define IMPLEMENT_MAP_FNS(maptype, keytype, prefix)
Definition: map.c:167
void * strmap_get_lc(const strmap_t *map, const char *key)
Definition: map.c:393
Headers for di_ops.c.
HT_PROTOTYPE(HT_GENERATE2(strmap_impl, HT_GENERATE2(strmap_entry_t, HT_GENERATE2(node, HT_GENERATE2(strmap_entry_hash, HT_GENERATE2(strmap_entries_eq)
Definition: map.c:87
#define tor_free(p)
Definition: malloc.h:52
Header for util_string.c.
Headers for util_malloc.c.
void * strmap_set_lc(strmap_t *map, const char *key, void *val)
Definition: map.c:379
void * tor_reallocarray_(void *ptr, size_t sz1, size_t sz2)
Definition: malloc.c:146
static unsigned int strmap_entry_hash(const strmap_entry_t *a)
Definition: map.c:53
static unsigned int digest256map_entry_hash(const digest256map_entry_t *a)
Definition: map.c:82
static unsigned int digestmap_entry_hash(const digestmap_entry_t *a)
Definition: map.c:67
#define DIGEST256_LEN
Definition: digest_sizes.h:23
static int strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
Definition: map.c:46
static int digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
Definition: map.c:60
int tor_memeq(const void *a, const void *b, size_t sz)
Definition: di_ops.c:107
#define DIGEST_LEN
Definition: digest_sizes.h:20
static int digest256map_entries_eq(const digest256map_entry_t *a, const digest256map_entry_t *b)
Definition: map.c:74
void * strmap_remove_lc(strmap_t *map, const char *key)
Definition: map.c:405
void tor_free_(void *mem)
Definition: malloc.c:227
void tor_strlower(char *s)
Definition: util_string.c:127
#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)
Definition: map.c:30
Headers for map.c.
Definitions for common sizes of cryptographic digests.
Macros to manage assertions, fatal and non-fatal.