map.c (21504B)
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 }