Tor  0.4.7.0-alpha-dev
map.h
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 #ifndef TOR_MAP_H
7 #define TOR_MAP_H
8 
9 /**
10  * \file map.h
11  *
12  * \brief Headers for map.c.
13  **/
14 
16 #include "lib/cc/torint.h"
17 
18 #include "ext/siphash.h"
19 
20 #define DECLARE_MAP_FNS(mapname_t, keytype, prefix) \
21  typedef struct mapname_t mapname_t; \
22  typedef struct prefix##_entry_t *prefix##_iter_t; \
23  MOCK_DECL(mapname_t*, prefix##_new, (void)); \
24  void* prefix##_set(mapname_t *map, keytype key, void *val); \
25  void* prefix##_get(const mapname_t *map, keytype key); \
26  void* prefix##_remove(mapname_t *map, keytype key); \
27  MOCK_DECL(void, prefix##_free_, (mapname_t *map, void (*free_val)(void*))); \
28  int prefix##_isempty(const mapname_t *map); \
29  int prefix##_size(const mapname_t *map); \
30  prefix##_iter_t *prefix##_iter_init(mapname_t *map); \
31  prefix##_iter_t *prefix##_iter_next(mapname_t *map, prefix##_iter_t *iter); \
32  prefix##_iter_t *prefix##_iter_next_rmv(mapname_t *map, \
33  prefix##_iter_t *iter); \
34  void prefix##_iter_get(prefix##_iter_t *iter, keytype *keyp, void **valp); \
35  int prefix##_iter_done(prefix##_iter_t *iter); \
36  void prefix##_assert_ok(const mapname_t *map)
37 
38 /* Map from const char * to void *. Implemented with a hash table. */
39 DECLARE_MAP_FNS(strmap_t, const char *, strmap);
40 /* Map from const char[DIGEST_LEN] to void *. Implemented with a hash table. */
41 DECLARE_MAP_FNS(digestmap_t, const char *, digestmap);
42 /* Map from const uint8_t[DIGEST256_LEN] to void *. Implemented with a hash
43  * table. */
44 DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map);
45 
46 #define MAP_FREE_AND_NULL(mapname_t, map, fn) \
47  do { \
48  mapname_t ## _free_((map), (fn)); \
49  (map) = NULL; \
50  } while (0)
51 
52 #define strmap_free(map, fn) MAP_FREE_AND_NULL(strmap, (map), (fn))
53 #define digestmap_free(map, fn) MAP_FREE_AND_NULL(digestmap, (map), (fn))
54 #define digest256map_free(map, fn) MAP_FREE_AND_NULL(digest256map, (map), (fn))
55 
56 #undef DECLARE_MAP_FNS
57 
58 /** Iterates over the key-value pairs in a map <b>map</b> in order.
59  * <b>prefix</b> is as for DECLARE_MAP_FNS (i.e., strmap or digestmap).
60  * The map's keys and values are of type keytype and valtype respectively;
61  * each iteration assigns them to keyvar and valvar.
62  *
63  * Example use:
64  * MAP_FOREACH(digestmap, m, const char *, k, routerinfo_t *, r) {
65  * // use k and r
66  * } MAP_FOREACH_END.
67  */
68 /* Unpacks to, approximately:
69  * {
70  * digestmap_iter_t *k_iter;
71  * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter);
72  * k_iter = digestmap_iter_next(m, k_iter)) {
73  * const char *k;
74  * void *r_voidp;
75  * routerinfo_t *r;
76  * digestmap_iter_get(k_iter, &k, &r_voidp);
77  * r = r_voidp;
78  * // use k and r
79  * }
80  * }
81  */
82 #define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar) \
83  STMT_BEGIN \
84  prefix##_iter_t *keyvar##_iter; \
85  for (keyvar##_iter = prefix##_iter_init(map); \
86  !prefix##_iter_done(keyvar##_iter); \
87  keyvar##_iter = prefix##_iter_next(map, keyvar##_iter)) { \
88  keytype keyvar; \
89  void *valvar##_voidp; \
90  valtype valvar; \
91  prefix##_iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \
92  valvar = valvar##_voidp;
93 
94 /** As MAP_FOREACH, except allows members to be removed from the map
95  * during the iteration via MAP_DEL_CURRENT. Example use:
96  *
97  * Example use:
98  * MAP_FOREACH(digestmap, m, const char *, k, routerinfo_t *, r) {
99  * if (is_very_old(r))
100  * MAP_DEL_CURRENT(k);
101  * } MAP_FOREACH_END.
102  **/
103 /* Unpacks to, approximately:
104  * {
105  * digestmap_iter_t *k_iter;
106  * int k_del=0;
107  * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter);
108  * k_iter = k_del ? digestmap_iter_next(m, k_iter)
109  * : digestmap_iter_next_rmv(m, k_iter)) {
110  * const char *k;
111  * void *r_voidp;
112  * routerinfo_t *r;
113  * k_del=0;
114  * digestmap_iter_get(k_iter, &k, &r_voidp);
115  * r = r_voidp;
116  * if (is_very_old(r)) {
117  * k_del = 1;
118  * }
119  * }
120  * }
121  */
122 #define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar) \
123  STMT_BEGIN \
124  prefix##_iter_t *keyvar##_iter; \
125  int keyvar##_del=0; \
126  for (keyvar##_iter = prefix##_iter_init(map); \
127  !prefix##_iter_done(keyvar##_iter); \
128  keyvar##_iter = keyvar##_del ? \
129  prefix##_iter_next_rmv(map, keyvar##_iter) : \
130  prefix##_iter_next(map, keyvar##_iter)) { \
131  keytype keyvar; \
132  void *valvar##_voidp; \
133  valtype valvar; \
134  keyvar##_del=0; \
135  prefix##_iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \
136  valvar = valvar##_voidp;
137 
138 /** Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon
139  * member of the map. */
140 #define MAP_DEL_CURRENT(keyvar) \
141  STMT_BEGIN \
142  keyvar##_del = 1; \
143  STMT_END
144 
145 /** Used to end a MAP_FOREACH() block. */
146 #define MAP_FOREACH_END } STMT_END ;
147 
148 /** As MAP_FOREACH, but does not require declaration of prefix or keytype.
149  * Example use:
150  * DIGESTMAP_FOREACH(m, k, routerinfo_t *, r) {
151  * // use k and r
152  * } DIGESTMAP_FOREACH_END.
153  */
154 #define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar) \
155  MAP_FOREACH(digestmap, map, const char *, keyvar, valtype, valvar)
156 
157 /** As MAP_FOREACH_MODIFY, but does not require declaration of prefix or
158  * keytype.
159  * Example use:
160  * DIGESTMAP_FOREACH_MODIFY(m, k, routerinfo_t *, r) {
161  * if (is_very_old(r))
162  * MAP_DEL_CURRENT(k);
163  * } DIGESTMAP_FOREACH_END.
164  */
165 #define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \
166  MAP_FOREACH_MODIFY(digestmap, map, const char *, keyvar, valtype, valvar)
167 /** Used to end a DIGESTMAP_FOREACH() block. */
168 #define DIGESTMAP_FOREACH_END MAP_FOREACH_END
169 
170 #define DIGEST256MAP_FOREACH(map, keyvar, valtype, valvar) \
171  MAP_FOREACH(digest256map, map, const uint8_t *, keyvar, valtype, valvar)
172 #define DIGEST256MAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \
173  MAP_FOREACH_MODIFY(digest256map, map, const uint8_t *, \
174  keyvar, valtype, valvar)
175 #define DIGEST256MAP_FOREACH_END MAP_FOREACH_END
176 
177 #define STRMAP_FOREACH(map, keyvar, valtype, valvar) \
178  MAP_FOREACH(strmap, map, const char *, keyvar, valtype, valvar)
179 #define STRMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \
180  MAP_FOREACH_MODIFY(strmap, map, const char *, keyvar, valtype, valvar)
181 #define STRMAP_FOREACH_END MAP_FOREACH_END
182 
183 void* strmap_set_lc(strmap_t *map, const char *key, void *val);
184 void* strmap_get_lc(const strmap_t *map, const char *key);
185 void* strmap_remove_lc(strmap_t *map, const char *key);
186 
187 #define DECLARE_TYPED_DIGESTMAP_FNS(prefix, mapname_t, valtype) \
188  typedef struct mapname_t mapname_t; \
189  typedef struct prefix##_iter_t *prefix##_iter_t; \
190  ATTR_UNUSED static inline mapname_t* \
191  prefix##_new(void) \
192  { \
193  return (mapname_t*)digestmap_new(); \
194  } \
195  ATTR_UNUSED static inline digestmap_t* \
196  prefix##_to_digestmap(mapname_t *map) \
197  { \
198  return (digestmap_t*)map; \
199  } \
200  ATTR_UNUSED static inline valtype* \
201  prefix##_get(mapname_t *map, const char *key) \
202  { \
203  return (valtype*)digestmap_get((digestmap_t*)map, key); \
204  } \
205  ATTR_UNUSED static inline valtype* \
206  prefix##_set(mapname_t *map, const char *key, valtype *val) \
207  { \
208  return (valtype*)digestmap_set((digestmap_t*)map, key, val); \
209  } \
210  ATTR_UNUSED static inline valtype* \
211  prefix##_remove(mapname_t *map, const char *key) \
212  { \
213  return (valtype*)digestmap_remove((digestmap_t*)map, key); \
214  } \
215  ATTR_UNUSED static inline void \
216  prefix##_f##ree_(mapname_t *map, void (*free_val)(void*)) \
217  { \
218  digestmap_free_((digestmap_t*)map, free_val); \
219  } \
220  ATTR_UNUSED static inline int \
221  prefix##_isempty(mapname_t *map) \
222  { \
223  return digestmap_isempty((digestmap_t*)map); \
224  } \
225  ATTR_UNUSED static inline int \
226  prefix##_size(mapname_t *map) \
227  { \
228  return digestmap_size((digestmap_t*)map); \
229  } \
230  ATTR_UNUSED static inline \
231  prefix##_iter_t *prefix##_iter_init(mapname_t *map) \
232  { \
233  return (prefix##_iter_t*) digestmap_iter_init((digestmap_t*)map); \
234  } \
235  ATTR_UNUSED static inline \
236  prefix##_iter_t *prefix##_iter_next(mapname_t *map, prefix##_iter_t *iter) \
237  { \
238  return (prefix##_iter_t*) digestmap_iter_next( \
239  (digestmap_t*)map, (digestmap_iter_t*)iter); \
240  } \
241  ATTR_UNUSED static inline prefix##_iter_t* \
242  prefix##_iter_next_rmv(mapname_t *map, prefix##_iter_t *iter) \
243  { \
244  return (prefix##_iter_t*) digestmap_iter_next_rmv( \
245  (digestmap_t*)map, (digestmap_iter_t*)iter); \
246  } \
247  ATTR_UNUSED static inline void \
248  prefix##_iter_get(prefix##_iter_t *iter, \
249  const char **keyp, \
250  valtype **valp) \
251  { \
252  void *v; \
253  digestmap_iter_get((digestmap_iter_t*) iter, keyp, &v); \
254  *valp = v; \
255  } \
256  ATTR_UNUSED static inline int \
257  prefix##_iter_done(prefix##_iter_t *iter) \
258  { \
259  return digestmap_iter_done((digestmap_iter_t*)iter); \
260  }
261 
262 #endif /* !defined(TOR_MAP_H) */
void * strmap_get_lc(const strmap_t *map, const char *key)
Definition: map.c:360
void * strmap_remove_lc(strmap_t *map, const char *key)
Definition: map.c:372
void * strmap_set_lc(strmap_t *map, const char *key, void *val)
Definition: map.c:346
Macros to implement mocking and selective exposure for the test code.
Integer definitions used throughout Tor.