map.c 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413
  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. /**
  6. * \file map.c
  7. *
  8. * \brief Hash-table implementations of a string-to-void* map, and of
  9. * a digest-to-void* map.
  10. **/
  11. #include "lib/container/map.h"
  12. #include "lib/ctime/di_ops.h"
  13. #include "lib/defs/digest_sizes.h"
  14. #include "lib/string/util_string.h"
  15. #include "lib/malloc/malloc.h"
  16. #include "lib/log/util_bug.h"
  17. #include <stdlib.h>
  18. #include <string.h>
  19. #include "ext/ht.h"
  20. /** Helper: Declare an entry type and a map type to implement a mapping using
  21. * ht.h. The map type will be called <b>maptype</b>. The key part of each
  22. * entry is declared using the C declaration <b>keydecl</b>. All functions
  23. * and types associated with the map get prefixed with <b>prefix</b> */
  24. #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \
  25. typedef struct prefix ## entry_t { \
  26. HT_ENTRY(prefix ## entry_t) node; \
  27. void *val; \
  28. keydecl; \
  29. } prefix ## entry_t; \
  30. struct maptype { \
  31. HT_HEAD(prefix ## impl, prefix ## entry_t) head; \
  32. }
  33. DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
  34. DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
  35. DEFINE_MAP_STRUCTS(digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_);
  36. /** Helper: compare strmap_entry_t objects by key value. */
  37. static inline int
  38. strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
  39. {
  40. return !strcmp(a->key, b->key);
  41. }
  42. /** Helper: return a hash value for a strmap_entry_t. */
  43. static inline unsigned int
  44. strmap_entry_hash(const strmap_entry_t *a)
  45. {
  46. return (unsigned) siphash24g(a->key, strlen(a->key));
  47. }
  48. /** Helper: compare digestmap_entry_t objects by key value. */
  49. static inline int
  50. digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
  51. {
  52. return tor_memeq(a->key, b->key, DIGEST_LEN);
  53. }
  54. /** Helper: return a hash value for a digest_map_t. */
  55. static inline unsigned int
  56. digestmap_entry_hash(const digestmap_entry_t *a)
  57. {
  58. return (unsigned) siphash24g(a->key, DIGEST_LEN);
  59. }
  60. /** Helper: compare digestmap_entry_t objects by key value. */
  61. static inline int
  62. digest256map_entries_eq(const digest256map_entry_t *a,
  63. const digest256map_entry_t *b)
  64. {
  65. return tor_memeq(a->key, b->key, DIGEST256_LEN);
  66. }
  67. /** Helper: return a hash value for a digest_map_t. */
  68. static inline unsigned int
  69. digest256map_entry_hash(const digest256map_entry_t *a)
  70. {
  71. return (unsigned) siphash24g(a->key, DIGEST256_LEN);
  72. }
  73. HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
  74. strmap_entries_eq)
  75. HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
  76. strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_)
  77. HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
  78. digestmap_entries_eq)
  79. HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
  80. digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_)
  81. HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node,
  82. digest256map_entry_hash,
  83. digest256map_entries_eq)
  84. HT_GENERATE2(digest256map_impl, digest256map_entry_t, node,
  85. digest256map_entry_hash,
  86. digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_)
  87. #define strmap_entry_free(ent) \
  88. FREE_AND_NULL(strmap_entry_t, strmap_entry_free_, (ent))
  89. #define digestmap_entry_free(ent) \
  90. FREE_AND_NULL(digestmap_entry_t, digestmap_entry_free_, (ent))
  91. #define digest256map_entry_free(ent) \
  92. FREE_AND_NULL(digest256map_entry_t, digest256map_entry_free_, (ent))
  93. static inline void
  94. strmap_entry_free_(strmap_entry_t *ent)
  95. {
  96. tor_free(ent->key);
  97. tor_free(ent);
  98. }
  99. static inline void
  100. digestmap_entry_free_(digestmap_entry_t *ent)
  101. {
  102. tor_free(ent);
  103. }
  104. static inline void
  105. digest256map_entry_free_(digest256map_entry_t *ent)
  106. {
  107. tor_free(ent);
  108. }
  109. static inline void
  110. strmap_assign_tmp_key(strmap_entry_t *ent, const char *key)
  111. {
  112. ent->key = (char*)key;
  113. }
  114. static inline void
  115. digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key)
  116. {
  117. memcpy(ent->key, key, DIGEST_LEN);
  118. }
  119. static inline void
  120. digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key)
  121. {
  122. memcpy(ent->key, key, DIGEST256_LEN);
  123. }
  124. static inline void
  125. strmap_assign_key(strmap_entry_t *ent, const char *key)
  126. {
  127. ent->key = tor_strdup(key);
  128. }
  129. static inline void
  130. digestmap_assign_key(digestmap_entry_t *ent, const char *key)
  131. {
  132. memcpy(ent->key, key, DIGEST_LEN);
  133. }
  134. static inline void
  135. digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key)
  136. {
  137. memcpy(ent->key, key, DIGEST256_LEN);
  138. }
  139. /**
  140. * Macro: implement all the functions for a map that are declared in
  141. * map.h by the DECLARE_MAP_FNS() macro. You must additionally define a
  142. * prefix_entry_free_() function to free entries (and their keys), a
  143. * prefix_assign_tmp_key() function to temporarily set a stack-allocated
  144. * entry to hold a key, and a prefix_assign_key() function to set a
  145. * heap-allocated entry to hold a key.
  146. */
  147. #define IMPLEMENT_MAP_FNS(maptype, keytype, prefix) \
  148. /** Create and return a new empty map. */ \
  149. MOCK_IMPL(maptype *, \
  150. prefix##_new,(void)) \
  151. { \
  152. maptype *result; \
  153. result = tor_malloc(sizeof(maptype)); \
  154. HT_INIT(prefix##_impl, &result->head); \
  155. return result; \
  156. } \
  157. \
  158. /** Return the item from <b>map</b> whose key matches <b>key</b>, or \
  159. * NULL if no such value exists. */ \
  160. void * \
  161. prefix##_get(const maptype *map, const keytype key) \
  162. { \
  163. prefix ##_entry_t *resolve; \
  164. prefix ##_entry_t search; \
  165. tor_assert(map); \
  166. tor_assert(key); \
  167. prefix ##_assign_tmp_key(&search, key); \
  168. resolve = HT_FIND(prefix ##_impl, &map->head, &search); \
  169. if (resolve) { \
  170. return resolve->val; \
  171. } else { \
  172. return NULL; \
  173. } \
  174. } \
  175. \
  176. /** Add an entry to <b>map</b> mapping <b>key</b> to <b>val</b>; \
  177. * return the previous value, or NULL if no such value existed. */ \
  178. void * \
  179. prefix##_set(maptype *map, const keytype key, void *val) \
  180. { \
  181. prefix##_entry_t search; \
  182. void *oldval; \
  183. tor_assert(map); \
  184. tor_assert(key); \
  185. tor_assert(val); \
  186. prefix##_assign_tmp_key(&search, key); \
  187. /* We a lot of our time in this function, so the code below is */ \
  188. /* meant to optimize the check/alloc/set cycle by avoiding the two */\
  189. /* trips to the hash table that we would do in the unoptimized */ \
  190. /* version of this code. (Each of HT_INSERT and HT_FIND calls */ \
  191. /* HT_SET_HASH and HT_FIND_P.) */ \
  192. HT_FIND_OR_INSERT_(prefix##_impl, node, prefix##_entry_hash, \
  193. &(map->head), \
  194. prefix##_entry_t, &search, ptr, \
  195. { \
  196. /* we found an entry. */ \
  197. oldval = (*ptr)->val; \
  198. (*ptr)->val = val; \
  199. return oldval; \
  200. }, \
  201. { \
  202. /* We didn't find the entry. */ \
  203. prefix##_entry_t *newent = \
  204. tor_malloc_zero(sizeof(prefix##_entry_t)); \
  205. prefix##_assign_key(newent, key); \
  206. newent->val = val; \
  207. HT_FOI_INSERT_(node, &(map->head), \
  208. &search, newent, ptr); \
  209. return NULL; \
  210. }); \
  211. } \
  212. \
  213. /** Remove the value currently associated with <b>key</b> from the map. \
  214. * Return the value if one was set, or NULL if there was no entry for \
  215. * <b>key</b>. \
  216. * \
  217. * Note: you must free any storage associated with the returned value. \
  218. */ \
  219. void * \
  220. prefix##_remove(maptype *map, const keytype key) \
  221. { \
  222. prefix##_entry_t *resolve; \
  223. prefix##_entry_t search; \
  224. void *oldval; \
  225. tor_assert(map); \
  226. tor_assert(key); \
  227. prefix##_assign_tmp_key(&search, key); \
  228. resolve = HT_REMOVE(prefix##_impl, &map->head, &search); \
  229. if (resolve) { \
  230. oldval = resolve->val; \
  231. prefix##_entry_free(resolve); \
  232. return oldval; \
  233. } else { \
  234. return NULL; \
  235. } \
  236. } \
  237. \
  238. /** Return the number of elements in <b>map</b>. */ \
  239. int \
  240. prefix##_size(const maptype *map) \
  241. { \
  242. return HT_SIZE(&map->head); \
  243. } \
  244. \
  245. /** Return true iff <b>map</b> has no entries. */ \
  246. int \
  247. prefix##_isempty(const maptype *map) \
  248. { \
  249. return HT_EMPTY(&map->head); \
  250. } \
  251. \
  252. /** Assert that <b>map</b> is not corrupt. */ \
  253. void \
  254. prefix##_assert_ok(const maptype *map) \
  255. { \
  256. tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head)); \
  257. } \
  258. \
  259. /** Remove all entries from <b>map</b>, and deallocate storage for \
  260. * those entries. If free_val is provided, invoked it every value in \
  261. * <b>map</b>. */ \
  262. MOCK_IMPL(void, \
  263. prefix##_free_, (maptype *map, void (*free_val)(void*))) \
  264. { \
  265. prefix##_entry_t **ent, **next, *this; \
  266. if (!map) \
  267. return; \
  268. for (ent = HT_START(prefix##_impl, &map->head); ent != NULL; \
  269. ent = next) { \
  270. this = *ent; \
  271. next = HT_NEXT_RMV(prefix##_impl, &map->head, ent); \
  272. if (free_val) \
  273. free_val(this->val); \
  274. prefix##_entry_free(this); \
  275. } \
  276. tor_assert(HT_EMPTY(&map->head)); \
  277. HT_CLEAR(prefix##_impl, &map->head); \
  278. tor_free(map); \
  279. } \
  280. \
  281. /** return an <b>iterator</b> pointer to the front of a map. \
  282. * \
  283. * Iterator example: \
  284. * \
  285. * \code \
  286. * // uppercase values in "map", removing empty values. \
  287. * \
  288. * strmap_iter_t *iter; \
  289. * const char *key; \
  290. * void *val; \
  291. * char *cp; \
  292. * \
  293. * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) { \
  294. * strmap_iter_get(iter, &key, &val); \
  295. * cp = (char*)val; \
  296. * if (!*cp) { \
  297. * iter = strmap_iter_next_rmv(map,iter); \
  298. * free(val); \
  299. * } else { \
  300. * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp); \
  301. */ \
  302. prefix##_iter_t * \
  303. prefix##_iter_init(maptype *map) \
  304. { \
  305. tor_assert(map); \
  306. return HT_START(prefix##_impl, &map->head); \
  307. } \
  308. \
  309. /** Advance <b>iter</b> a single step to the next entry, and return \
  310. * its new value. */ \
  311. prefix##_iter_t * \
  312. prefix##_iter_next(maptype *map, prefix##_iter_t *iter) \
  313. { \
  314. tor_assert(map); \
  315. tor_assert(iter); \
  316. return HT_NEXT(prefix##_impl, &map->head, iter); \
  317. } \
  318. /** Advance <b>iter</b> a single step to the next entry, removing the \
  319. * current entry, and return its new value. */ \
  320. prefix##_iter_t * \
  321. prefix##_iter_next_rmv(maptype *map, prefix##_iter_t *iter) \
  322. { \
  323. prefix##_entry_t *rmv; \
  324. tor_assert(map); \
  325. tor_assert(iter); \
  326. tor_assert(*iter); \
  327. rmv = *iter; \
  328. iter = HT_NEXT_RMV(prefix##_impl, &map->head, iter); \
  329. prefix##_entry_free(rmv); \
  330. return iter; \
  331. } \
  332. /** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed \
  333. * to by iter. */ \
  334. void \
  335. prefix##_iter_get(prefix##_iter_t *iter, const keytype *keyp, \
  336. void **valp) \
  337. { \
  338. tor_assert(iter); \
  339. tor_assert(*iter); \
  340. tor_assert(keyp); \
  341. tor_assert(valp); \
  342. *keyp = (*iter)->key; \
  343. *valp = (*iter)->val; \
  344. } \
  345. /** Return true iff <b>iter</b> has advanced past the last entry of \
  346. * <b>map</b>. */ \
  347. int \
  348. prefix##_iter_done(prefix##_iter_t *iter) \
  349. { \
  350. return iter == NULL; \
  351. }
  352. IMPLEMENT_MAP_FNS(strmap_t, char *, strmap)
  353. IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap)
  354. IMPLEMENT_MAP_FNS(digest256map_t, uint8_t *, digest256map)
  355. /** Same as strmap_set, but first converts <b>key</b> to lowercase. */
  356. void *
  357. strmap_set_lc(strmap_t *map, const char *key, void *val)
  358. {
  359. /* We could be a little faster by using strcasecmp instead, and a separate
  360. * type, but I don't think it matters. */
  361. void *v;
  362. char *lc_key = tor_strdup(key);
  363. tor_strlower(lc_key);
  364. v = strmap_set(map,lc_key,val);
  365. tor_free(lc_key);
  366. return v;
  367. }
  368. /** Same as strmap_get, but first converts <b>key</b> to lowercase. */
  369. void *
  370. strmap_get_lc(const strmap_t *map, const char *key)
  371. {
  372. void *v;
  373. char *lc_key = tor_strdup(key);
  374. tor_strlower(lc_key);
  375. v = strmap_get(map,lc_key);
  376. tor_free(lc_key);
  377. return v;
  378. }
  379. /** Same as strmap_remove, but first converts <b>key</b> to lowercase */
  380. void *
  381. strmap_remove_lc(strmap_t *map, const char *key)
  382. {
  383. void *v;
  384. char *lc_key = tor_strdup(key);
  385. tor_strlower(lc_key);
  386. v = strmap_remove(map,lc_key);
  387. tor_free(lc_key);
  388. return v;
  389. }