map.h (13515B)
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 15 #include "lib/testsupport/testsupport.h" 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) */