container.h 32 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742
  1. /* Copyright (c) 2003-2004, Roger Dingledine
  2. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  3. * Copyright (c) 2007-2017, The Tor Project, Inc. */
  4. /* See LICENSE for licensing information */
  5. #ifndef TOR_CONTAINER_H
  6. #define TOR_CONTAINER_H
  7. #include "util.h"
  8. #include "siphash.h"
  9. /** A resizeable list of pointers, with associated helpful functionality.
  10. *
  11. * The members of this struct are exposed only so that macros and inlines can
  12. * use them; all access to smartlist internals should go through the functions
  13. * and macros defined here.
  14. **/
  15. typedef struct smartlist_t {
  16. /** @{ */
  17. /** <b>list</b> has enough capacity to store exactly <b>capacity</b> elements
  18. * before it needs to be resized. Only the first <b>num_used</b> (\<=
  19. * capacity) elements point to valid data.
  20. */
  21. void **list;
  22. int num_used;
  23. int capacity;
  24. /** @} */
  25. } smartlist_t;
  26. MOCK_DECL(smartlist_t *, smartlist_new, (void));
  27. MOCK_DECL(void, smartlist_free_, (smartlist_t *sl));
  28. #define smartlist_free(sl) FREE_AND_NULL(smartlist, (sl))
  29. void smartlist_clear(smartlist_t *sl);
  30. void smartlist_add(smartlist_t *sl, void *element);
  31. void smartlist_add_all(smartlist_t *sl, const smartlist_t *s2);
  32. void smartlist_remove(smartlist_t *sl, const void *element);
  33. void smartlist_remove_keeporder(smartlist_t *sl, const void *element);
  34. void *smartlist_pop_last(smartlist_t *sl);
  35. void smartlist_reverse(smartlist_t *sl);
  36. void smartlist_string_remove(smartlist_t *sl, const char *element);
  37. int smartlist_contains(const smartlist_t *sl, const void *element);
  38. int smartlist_contains_string(const smartlist_t *sl, const char *element);
  39. int smartlist_pos(const smartlist_t *sl, const void *element);
  40. int smartlist_string_pos(const smartlist_t *, const char *elt);
  41. int smartlist_contains_string_case(const smartlist_t *sl, const char *element);
  42. int smartlist_contains_int_as_string(const smartlist_t *sl, int num);
  43. int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2);
  44. int smartlist_contains_digest(const smartlist_t *sl, const char *element);
  45. int smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2);
  46. int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2);
  47. void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2);
  48. void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2);
  49. /* smartlist_choose() is defined in crypto.[ch] */
  50. #ifdef DEBUG_SMARTLIST
  51. /** Return the number of items in sl.
  52. */
  53. static inline int smartlist_len(const smartlist_t *sl);
  54. static inline int smartlist_len(const smartlist_t *sl) {
  55. tor_assert(sl);
  56. return (sl)->num_used;
  57. }
  58. /** Return the <b>idx</b>th element of sl.
  59. */
  60. static inline void *smartlist_get(const smartlist_t *sl, int idx);
  61. static inline void *smartlist_get(const smartlist_t *sl, int idx) {
  62. tor_assert(sl);
  63. tor_assert(idx>=0);
  64. tor_assert(sl->num_used > idx);
  65. return sl->list[idx];
  66. }
  67. static inline void smartlist_set(smartlist_t *sl, int idx, void *val) {
  68. tor_assert(sl);
  69. tor_assert(idx>=0);
  70. tor_assert(sl->num_used > idx);
  71. sl->list[idx] = val;
  72. }
  73. #else /* !(defined(DEBUG_SMARTLIST)) */
  74. #define smartlist_len(sl) ((sl)->num_used)
  75. #define smartlist_get(sl, idx) ((sl)->list[idx])
  76. #define smartlist_set(sl, idx, val) ((sl)->list[idx] = (val))
  77. #endif /* defined(DEBUG_SMARTLIST) */
  78. /** Exchange the elements at indices <b>idx1</b> and <b>idx2</b> of the
  79. * smartlist <b>sl</b>. */
  80. static inline void smartlist_swap(smartlist_t *sl, int idx1, int idx2)
  81. {
  82. if (idx1 != idx2) {
  83. void *elt = smartlist_get(sl, idx1);
  84. smartlist_set(sl, idx1, smartlist_get(sl, idx2));
  85. smartlist_set(sl, idx2, elt);
  86. }
  87. }
  88. void smartlist_del(smartlist_t *sl, int idx);
  89. void smartlist_del_keeporder(smartlist_t *sl, int idx);
  90. void smartlist_insert(smartlist_t *sl, int idx, void *val);
  91. void smartlist_sort(smartlist_t *sl,
  92. int (*compare)(const void **a, const void **b));
  93. void *smartlist_get_most_frequent_(const smartlist_t *sl,
  94. int (*compare)(const void **a, const void **b),
  95. int *count_out);
  96. #define smartlist_get_most_frequent(sl, compare) \
  97. smartlist_get_most_frequent_((sl), (compare), NULL)
  98. void smartlist_uniq(smartlist_t *sl,
  99. int (*compare)(const void **a, const void **b),
  100. void (*free_fn)(void *elt));
  101. void smartlist_sort_strings(smartlist_t *sl);
  102. void smartlist_sort_digests(smartlist_t *sl);
  103. void smartlist_sort_digests256(smartlist_t *sl);
  104. void smartlist_sort_pointers(smartlist_t *sl);
  105. const char *smartlist_get_most_frequent_string(smartlist_t *sl);
  106. const char *smartlist_get_most_frequent_string_(smartlist_t *sl,
  107. int *count_out);
  108. const uint8_t *smartlist_get_most_frequent_digest256(smartlist_t *sl);
  109. void smartlist_uniq_strings(smartlist_t *sl);
  110. void smartlist_uniq_digests(smartlist_t *sl);
  111. void smartlist_uniq_digests256(smartlist_t *sl);
  112. void *smartlist_bsearch(smartlist_t *sl, const void *key,
  113. int (*compare)(const void *key, const void **member));
  114. int smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
  115. int (*compare)(const void *key, const void **member),
  116. int *found_out);
  117. void smartlist_pqueue_add(smartlist_t *sl,
  118. int (*compare)(const void *a, const void *b),
  119. int idx_field_offset,
  120. void *item);
  121. void *smartlist_pqueue_pop(smartlist_t *sl,
  122. int (*compare)(const void *a, const void *b),
  123. int idx_field_offset);
  124. void smartlist_pqueue_remove(smartlist_t *sl,
  125. int (*compare)(const void *a, const void *b),
  126. int idx_field_offset,
  127. void *item);
  128. void smartlist_pqueue_assert_ok(smartlist_t *sl,
  129. int (*compare)(const void *a, const void *b),
  130. int idx_field_offset);
  131. #define SPLIT_SKIP_SPACE 0x01
  132. #define SPLIT_IGNORE_BLANK 0x02
  133. #define SPLIT_STRIP_SPACE 0x04
  134. int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,
  135. int flags, int max);
  136. char *smartlist_join_strings(smartlist_t *sl, const char *join, int terminate,
  137. size_t *len_out) ATTR_MALLOC;
  138. char *smartlist_join_strings2(smartlist_t *sl, const char *join,
  139. size_t join_len, int terminate, size_t *len_out)
  140. ATTR_MALLOC;
  141. /** Iterate over the items in a smartlist <b>sl</b>, in order. For each item,
  142. * assign it to a new local variable of type <b>type</b> named <b>var</b>, and
  143. * execute the statements inside the loop body. Inside the loop, the loop
  144. * index can be accessed as <b>var</b>_sl_idx and the length of the list can
  145. * be accessed as <b>var</b>_sl_len.
  146. *
  147. * NOTE: Do not change the length of the list while the loop is in progress,
  148. * unless you adjust the _sl_len variable correspondingly. See second example
  149. * below.
  150. *
  151. * Example use:
  152. * <pre>
  153. * smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
  154. * SMARTLIST_FOREACH_BEGIN(list, char *, cp) {
  155. * printf("%d: %s\n", cp_sl_idx, cp);
  156. * tor_free(cp);
  157. * } SMARTLIST_FOREACH_END(cp);
  158. * smartlist_free(list);
  159. * </pre>
  160. *
  161. * Example use (advanced):
  162. * <pre>
  163. * SMARTLIST_FOREACH_BEGIN(list, char *, cp) {
  164. * if (!strcmp(cp, "junk")) {
  165. * tor_free(cp);
  166. * SMARTLIST_DEL_CURRENT(list, cp);
  167. * }
  168. * } SMARTLIST_FOREACH_END(cp);
  169. * </pre>
  170. */
  171. /* Note: these macros use token pasting, and reach into smartlist internals.
  172. * This can make them a little daunting. Here's the approximate unpacking of
  173. * the above examples, for entertainment value:
  174. *
  175. * <pre>
  176. * smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
  177. * {
  178. * int cp_sl_idx, cp_sl_len = smartlist_len(list);
  179. * char *cp;
  180. * for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) {
  181. * cp = smartlist_get(list, cp_sl_idx);
  182. * printf("%d: %s\n", cp_sl_idx, cp);
  183. * tor_free(cp);
  184. * }
  185. * }
  186. * smartlist_free(list);
  187. * </pre>
  188. *
  189. * <pre>
  190. * {
  191. * int cp_sl_idx, cp_sl_len = smartlist_len(list);
  192. * char *cp;
  193. * for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) {
  194. * cp = smartlist_get(list, cp_sl_idx);
  195. * if (!strcmp(cp, "junk")) {
  196. * tor_free(cp);
  197. * smartlist_del(list, cp_sl_idx);
  198. * --cp_sl_idx;
  199. * --cp_sl_len;
  200. * }
  201. * }
  202. * }
  203. * </pre>
  204. */
  205. #define SMARTLIST_FOREACH_BEGIN(sl, type, var) \
  206. STMT_BEGIN \
  207. int var ## _sl_idx, var ## _sl_len=(sl)->num_used; \
  208. type var; \
  209. for (var ## _sl_idx = 0; var ## _sl_idx < var ## _sl_len; \
  210. ++var ## _sl_idx) { \
  211. var = (sl)->list[var ## _sl_idx];
  212. #define SMARTLIST_FOREACH_END(var) \
  213. var = NULL; \
  214. (void) var ## _sl_idx; \
  215. } STMT_END
  216. /**
  217. * An alias for SMARTLIST_FOREACH_BEGIN and SMARTLIST_FOREACH_END, using
  218. * <b>cmd</b> as the loop body. This wrapper is here for convenience with
  219. * very short loops.
  220. *
  221. * By convention, we do not use this for loops which nest, or for loops over
  222. * 10 lines or so. Use SMARTLIST_FOREACH_{BEGIN,END} for those.
  223. */
  224. #define SMARTLIST_FOREACH(sl, type, var, cmd) \
  225. SMARTLIST_FOREACH_BEGIN(sl,type,var) { \
  226. cmd; \
  227. } SMARTLIST_FOREACH_END(var)
  228. /** Helper: While in a SMARTLIST_FOREACH loop over the list <b>sl</b> indexed
  229. * with the variable <b>var</b>, remove the current element in a way that
  230. * won't confuse the loop. */
  231. #define SMARTLIST_DEL_CURRENT(sl, var) \
  232. STMT_BEGIN \
  233. smartlist_del(sl, var ## _sl_idx); \
  234. --var ## _sl_idx; \
  235. --var ## _sl_len; \
  236. STMT_END
  237. /** Helper: While in a SMARTLIST_FOREACH loop over the list <b>sl</b> indexed
  238. * with the variable <b>var</b>, remove the current element in a way that
  239. * won't confuse the loop. */
  240. #define SMARTLIST_DEL_CURRENT_KEEPORDER(sl, var) \
  241. STMT_BEGIN \
  242. smartlist_del_keeporder(sl, var ## _sl_idx); \
  243. --var ## _sl_idx; \
  244. --var ## _sl_len; \
  245. STMT_END
  246. /** Helper: While in a SMARTLIST_FOREACH loop over the list <b>sl</b> indexed
  247. * with the variable <b>var</b>, replace the current element with <b>val</b>.
  248. * Does not deallocate the current value of <b>var</b>.
  249. */
  250. #define SMARTLIST_REPLACE_CURRENT(sl, var, val) \
  251. STMT_BEGIN \
  252. smartlist_set(sl, var ## _sl_idx, val); \
  253. STMT_END
  254. /* Helper: Given two lists of items, possibly of different types, such that
  255. * both lists are sorted on some common field (as determined by a comparison
  256. * expression <b>cmpexpr</b>), and such that one list (<b>sl1</b>) has no
  257. * duplicates on the common field, loop through the lists in lockstep, and
  258. * execute <b>unmatched_var2</b> on items in var2 that do not appear in
  259. * var1.
  260. *
  261. * WARNING: It isn't safe to add remove elements from either list while the
  262. * loop is in progress.
  263. *
  264. * Example use:
  265. * SMARTLIST_FOREACH_JOIN(routerstatus_list, routerstatus_t *, rs,
  266. * routerinfo_list, routerinfo_t *, ri,
  267. * tor_memcmp(rs->identity_digest, ri->identity_digest, 20),
  268. * log_info(LD_GENERAL,"No match for %s", ri->nickname)) {
  269. * log_info(LD_GENERAL, "%s matches routerstatus %p", ri->nickname, rs);
  270. * } SMARTLIST_FOREACH_JOIN_END(rs, ri);
  271. **/
  272. /* The example above unpacks (approximately) to:
  273. * int rs_sl_idx = 0, rs_sl_len = smartlist_len(routerstatus_list);
  274. * int ri_sl_idx, ri_sl_len = smartlist_len(routerinfo_list);
  275. * int rs_ri_cmp;
  276. * routerstatus_t *rs;
  277. * routerinfo_t *ri;
  278. * for (; ri_sl_idx < ri_sl_len; ++ri_sl_idx) {
  279. * ri = smartlist_get(routerinfo_list, ri_sl_idx);
  280. * while (rs_sl_idx < rs_sl_len) {
  281. * rs = smartlist_get(routerstatus_list, rs_sl_idx);
  282. * rs_ri_cmp = tor_memcmp(rs->identity_digest, ri->identity_digest, 20);
  283. * if (rs_ri_cmp > 0) {
  284. * break;
  285. * } else if (rs_ri_cmp == 0) {
  286. * goto matched_ri;
  287. * } else {
  288. * ++rs_sl_idx;
  289. * }
  290. * }
  291. * log_info(LD_GENERAL,"No match for %s", ri->nickname);
  292. * continue;
  293. * matched_ri: {
  294. * log_info(LD_GENERAL,"%s matches with routerstatus %p",ri->nickname,rs);
  295. * }
  296. * }
  297. */
  298. #define SMARTLIST_FOREACH_JOIN(sl1, type1, var1, sl2, type2, var2, \
  299. cmpexpr, unmatched_var2) \
  300. STMT_BEGIN \
  301. int var1 ## _sl_idx = 0, var1 ## _sl_len=(sl1)->num_used; \
  302. int var2 ## _sl_idx = 0, var2 ## _sl_len=(sl2)->num_used; \
  303. int var1 ## _ ## var2 ## _cmp; \
  304. type1 var1; \
  305. type2 var2; \
  306. for (; var2##_sl_idx < var2##_sl_len; ++var2##_sl_idx) { \
  307. var2 = (sl2)->list[var2##_sl_idx]; \
  308. while (var1##_sl_idx < var1##_sl_len) { \
  309. var1 = (sl1)->list[var1##_sl_idx]; \
  310. var1##_##var2##_cmp = (cmpexpr); \
  311. if (var1##_##var2##_cmp > 0) { \
  312. break; \
  313. } else if (var1##_##var2##_cmp == 0) { \
  314. goto matched_##var2; \
  315. } else { \
  316. ++var1##_sl_idx; \
  317. } \
  318. } \
  319. /* Ran out of v1, or no match for var2. */ \
  320. unmatched_var2; \
  321. continue; \
  322. matched_##var2: ; \
  323. #define SMARTLIST_FOREACH_JOIN_END(var1, var2) \
  324. } \
  325. STMT_END
  326. #define DECLARE_MAP_FNS(maptype, keytype, prefix) \
  327. typedef struct maptype maptype; \
  328. typedef struct prefix##entry_t *prefix##iter_t; \
  329. MOCK_DECL(maptype*, prefix##new, (void)); \
  330. void* prefix##set(maptype *map, keytype key, void *val); \
  331. void* prefix##get(const maptype *map, keytype key); \
  332. void* prefix##remove(maptype *map, keytype key); \
  333. MOCK_DECL(void, prefix##free_, (maptype *map, void (*free_val)(void*))); \
  334. int prefix##isempty(const maptype *map); \
  335. int prefix##size(const maptype *map); \
  336. prefix##iter_t *prefix##iter_init(maptype *map); \
  337. prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter); \
  338. prefix##iter_t *prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter); \
  339. void prefix##iter_get(prefix##iter_t *iter, keytype *keyp, void **valp); \
  340. int prefix##iter_done(prefix##iter_t *iter); \
  341. void prefix##assert_ok(const maptype *map)
  342. /* Map from const char * to void *. Implemented with a hash table. */
  343. DECLARE_MAP_FNS(strmap_t, const char *, strmap_);
  344. /* Map from const char[DIGEST_LEN] to void *. Implemented with a hash table. */
  345. DECLARE_MAP_FNS(digestmap_t, const char *, digestmap_);
  346. /* Map from const uint8_t[DIGEST256_LEN] to void *. Implemented with a hash
  347. * table. */
  348. DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map_);
  349. #define MAP_FREE_AND_NULL(maptype, map, fn) \
  350. do { \
  351. maptype ## _free_((map), (fn)); \
  352. (map) = NULL; \
  353. } while (0)
  354. #define strmap_free(map, fn) MAP_FREE_AND_NULL(strmap, (map), (fn))
  355. #define digestmap_free(map, fn) MAP_FREE_AND_NULL(digestmap, (map), (fn))
  356. #define digest256map_free(map, fn) MAP_FREE_AND_NULL(digest256map, (map), (fn))
  357. #undef DECLARE_MAP_FNS
  358. /** Iterates over the key-value pairs in a map <b>map</b> in order.
  359. * <b>prefix</b> is as for DECLARE_MAP_FNS (i.e., strmap_ or digestmap_).
  360. * The map's keys and values are of type keytype and valtype respectively;
  361. * each iteration assigns them to keyvar and valvar.
  362. *
  363. * Example use:
  364. * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) {
  365. * // use k and r
  366. * } MAP_FOREACH_END.
  367. */
  368. /* Unpacks to, approximately:
  369. * {
  370. * digestmap_iter_t *k_iter;
  371. * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter);
  372. * k_iter = digestmap_iter_next(m, k_iter)) {
  373. * const char *k;
  374. * void *r_voidp;
  375. * routerinfo_t *r;
  376. * digestmap_iter_get(k_iter, &k, &r_voidp);
  377. * r = r_voidp;
  378. * // use k and r
  379. * }
  380. * }
  381. */
  382. #define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar) \
  383. STMT_BEGIN \
  384. prefix##iter_t *keyvar##_iter; \
  385. for (keyvar##_iter = prefix##iter_init(map); \
  386. !prefix##iter_done(keyvar##_iter); \
  387. keyvar##_iter = prefix##iter_next(map, keyvar##_iter)) { \
  388. keytype keyvar; \
  389. void *valvar##_voidp; \
  390. valtype valvar; \
  391. prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \
  392. valvar = valvar##_voidp;
  393. /** As MAP_FOREACH, except allows members to be removed from the map
  394. * during the iteration via MAP_DEL_CURRENT. Example use:
  395. *
  396. * Example use:
  397. * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) {
  398. * if (is_very_old(r))
  399. * MAP_DEL_CURRENT(k);
  400. * } MAP_FOREACH_END.
  401. **/
  402. /* Unpacks to, approximately:
  403. * {
  404. * digestmap_iter_t *k_iter;
  405. * int k_del=0;
  406. * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter);
  407. * k_iter = k_del ? digestmap_iter_next(m, k_iter)
  408. * : digestmap_iter_next_rmv(m, k_iter)) {
  409. * const char *k;
  410. * void *r_voidp;
  411. * routerinfo_t *r;
  412. * k_del=0;
  413. * digestmap_iter_get(k_iter, &k, &r_voidp);
  414. * r = r_voidp;
  415. * if (is_very_old(r)) {
  416. * k_del = 1;
  417. * }
  418. * }
  419. * }
  420. */
  421. #define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar) \
  422. STMT_BEGIN \
  423. prefix##iter_t *keyvar##_iter; \
  424. int keyvar##_del=0; \
  425. for (keyvar##_iter = prefix##iter_init(map); \
  426. !prefix##iter_done(keyvar##_iter); \
  427. keyvar##_iter = keyvar##_del ? \
  428. prefix##iter_next_rmv(map, keyvar##_iter) : \
  429. prefix##iter_next(map, keyvar##_iter)) { \
  430. keytype keyvar; \
  431. void *valvar##_voidp; \
  432. valtype valvar; \
  433. keyvar##_del=0; \
  434. prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \
  435. valvar = valvar##_voidp;
  436. /** Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon
  437. * member of the map. */
  438. #define MAP_DEL_CURRENT(keyvar) \
  439. STMT_BEGIN \
  440. keyvar##_del = 1; \
  441. STMT_END
  442. /** Used to end a MAP_FOREACH() block. */
  443. #define MAP_FOREACH_END } STMT_END ;
  444. /** As MAP_FOREACH, but does not require declaration of prefix or keytype.
  445. * Example use:
  446. * DIGESTMAP_FOREACH(m, k, routerinfo_t *, r) {
  447. * // use k and r
  448. * } DIGESTMAP_FOREACH_END.
  449. */
  450. #define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar) \
  451. MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar)
  452. /** As MAP_FOREACH_MODIFY, but does not require declaration of prefix or
  453. * keytype.
  454. * Example use:
  455. * DIGESTMAP_FOREACH_MODIFY(m, k, routerinfo_t *, r) {
  456. * if (is_very_old(r))
  457. * MAP_DEL_CURRENT(k);
  458. * } DIGESTMAP_FOREACH_END.
  459. */
  460. #define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \
  461. MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar)
  462. /** Used to end a DIGESTMAP_FOREACH() block. */
  463. #define DIGESTMAP_FOREACH_END MAP_FOREACH_END
  464. #define DIGEST256MAP_FOREACH(map, keyvar, valtype, valvar) \
  465. MAP_FOREACH(digest256map_, map, const uint8_t *, keyvar, valtype, valvar)
  466. #define DIGEST256MAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \
  467. MAP_FOREACH_MODIFY(digest256map_, map, const uint8_t *, \
  468. keyvar, valtype, valvar)
  469. #define DIGEST256MAP_FOREACH_END MAP_FOREACH_END
  470. #define STRMAP_FOREACH(map, keyvar, valtype, valvar) \
  471. MAP_FOREACH(strmap_, map, const char *, keyvar, valtype, valvar)
  472. #define STRMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \
  473. MAP_FOREACH_MODIFY(strmap_, map, const char *, keyvar, valtype, valvar)
  474. #define STRMAP_FOREACH_END MAP_FOREACH_END
  475. void* strmap_set_lc(strmap_t *map, const char *key, void *val);
  476. void* strmap_get_lc(const strmap_t *map, const char *key);
  477. void* strmap_remove_lc(strmap_t *map, const char *key);
  478. #define DECLARE_TYPED_DIGESTMAP_FNS(prefix, maptype, valtype) \
  479. typedef struct maptype maptype; \
  480. typedef struct prefix##iter_t *prefix##iter_t; \
  481. ATTR_UNUSED static inline maptype* \
  482. prefix##new(void) \
  483. { \
  484. return (maptype*)digestmap_new(); \
  485. } \
  486. ATTR_UNUSED static inline digestmap_t* \
  487. prefix##to_digestmap(maptype *map) \
  488. { \
  489. return (digestmap_t*)map; \
  490. } \
  491. ATTR_UNUSED static inline valtype* \
  492. prefix##get(maptype *map, const char *key) \
  493. { \
  494. return (valtype*)digestmap_get((digestmap_t*)map, key); \
  495. } \
  496. ATTR_UNUSED static inline valtype* \
  497. prefix##set(maptype *map, const char *key, valtype *val) \
  498. { \
  499. return (valtype*)digestmap_set((digestmap_t*)map, key, val); \
  500. } \
  501. ATTR_UNUSED static inline valtype* \
  502. prefix##remove(maptype *map, const char *key) \
  503. { \
  504. return (valtype*)digestmap_remove((digestmap_t*)map, key); \
  505. } \
  506. ATTR_UNUSED static inline void \
  507. prefix##f##ree_(maptype *map, void (*free_val)(void*)) \
  508. { \
  509. digestmap_free_((digestmap_t*)map, free_val); \
  510. } \
  511. ATTR_UNUSED static inline int \
  512. prefix##isempty(maptype *map) \
  513. { \
  514. return digestmap_isempty((digestmap_t*)map); \
  515. } \
  516. ATTR_UNUSED static inline int \
  517. prefix##size(maptype *map) \
  518. { \
  519. return digestmap_size((digestmap_t*)map); \
  520. } \
  521. ATTR_UNUSED static inline \
  522. prefix##iter_t *prefix##iter_init(maptype *map) \
  523. { \
  524. return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map); \
  525. } \
  526. ATTR_UNUSED static inline \
  527. prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter) \
  528. { \
  529. return (prefix##iter_t*) digestmap_iter_next( \
  530. (digestmap_t*)map, (digestmap_iter_t*)iter); \
  531. } \
  532. ATTR_UNUSED static inline prefix##iter_t* \
  533. prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter) \
  534. { \
  535. return (prefix##iter_t*) digestmap_iter_next_rmv( \
  536. (digestmap_t*)map, (digestmap_iter_t*)iter); \
  537. } \
  538. ATTR_UNUSED static inline void \
  539. prefix##iter_get(prefix##iter_t *iter, \
  540. const char **keyp, \
  541. valtype **valp) \
  542. { \
  543. void *v; \
  544. digestmap_iter_get((digestmap_iter_t*) iter, keyp, &v); \
  545. *valp = v; \
  546. } \
  547. ATTR_UNUSED static inline int \
  548. prefix##iter_done(prefix##iter_t *iter) \
  549. { \
  550. return digestmap_iter_done((digestmap_iter_t*)iter); \
  551. }
  552. #if SIZEOF_INT == 4
  553. #define BITARRAY_SHIFT 5
  554. #elif SIZEOF_INT == 8
  555. #define BITARRAY_SHIFT 6
  556. #else
  557. #error "int is neither 4 nor 8 bytes. I can't deal with that."
  558. #endif /* SIZEOF_INT == 4 || ... */
  559. #define BITARRAY_MASK ((1u<<BITARRAY_SHIFT)-1)
  560. /** A random-access array of one-bit-wide elements. */
  561. typedef unsigned int bitarray_t;
  562. /** Create a new bit array that can hold <b>n_bits</b> bits. */
  563. static inline bitarray_t *
  564. bitarray_init_zero(unsigned int n_bits)
  565. {
  566. /* round up to the next int. */
  567. size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT;
  568. return tor_calloc(sz, sizeof(unsigned int));
  569. }
  570. /** Expand <b>ba</b> from holding <b>n_bits_old</b> to <b>n_bits_new</b>,
  571. * clearing all new bits. Returns a possibly changed pointer to the
  572. * bitarray. */
  573. static inline bitarray_t *
  574. bitarray_expand(bitarray_t *ba,
  575. unsigned int n_bits_old, unsigned int n_bits_new)
  576. {
  577. size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT;
  578. size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT;
  579. char *ptr;
  580. if (sz_new <= sz_old)
  581. return ba;
  582. ptr = tor_reallocarray(ba, sz_new, sizeof(unsigned int));
  583. /* This memset does nothing to the older excess bytes. But they were
  584. * already set to 0 by bitarry_init_zero. */
  585. memset(ptr+sz_old*sizeof(unsigned int), 0,
  586. (sz_new-sz_old)*sizeof(unsigned int));
  587. return (bitarray_t*) ptr;
  588. }
  589. /** Free the bit array <b>ba</b>. */
  590. static inline void
  591. bitarray_free_(bitarray_t *ba)
  592. {
  593. tor_free(ba);
  594. }
  595. #define bitarray_free(ba) FREE_AND_NULL(bitarray, (ba))
  596. /** Set the <b>bit</b>th bit in <b>b</b> to 1. */
  597. static inline void
  598. bitarray_set(bitarray_t *b, int bit)
  599. {
  600. b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK));
  601. }
  602. /** Set the <b>bit</b>th bit in <b>b</b> to 0. */
  603. static inline void
  604. bitarray_clear(bitarray_t *b, int bit)
  605. {
  606. b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK));
  607. }
  608. /** Return true iff <b>bit</b>th bit in <b>b</b> is nonzero. NOTE: does
  609. * not necessarily return 1 on true. */
  610. static inline unsigned int
  611. bitarray_is_set(bitarray_t *b, int bit)
  612. {
  613. return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK));
  614. }
  615. /** A set of digests, implemented as a Bloom filter. */
  616. typedef struct {
  617. int mask; /**< One less than the number of bits in <b>ba</b>; always one less
  618. * than a power of two. */
  619. bitarray_t *ba; /**< A bit array to implement the Bloom filter. */
  620. } digestset_t;
  621. #define BIT(n) ((n) & set->mask)
  622. /** Add the digest <b>digest</b> to <b>set</b>. */
  623. static inline void
  624. digestset_add(digestset_t *set, const char *digest)
  625. {
  626. const uint64_t x = siphash24g(digest, 20);
  627. const uint32_t d1 = (uint32_t) x;
  628. const uint32_t d2 = (uint32_t)( (x>>16) + x);
  629. const uint32_t d3 = (uint32_t)( (x>>32) + x);
  630. const uint32_t d4 = (uint32_t)( (x>>48) + x);
  631. bitarray_set(set->ba, BIT(d1));
  632. bitarray_set(set->ba, BIT(d2));
  633. bitarray_set(set->ba, BIT(d3));
  634. bitarray_set(set->ba, BIT(d4));
  635. }
  636. /** If <b>digest</b> is in <b>set</b>, return nonzero. Otherwise,
  637. * <em>probably</em> return zero. */
  638. static inline int
  639. digestset_contains(const digestset_t *set, const char *digest)
  640. {
  641. const uint64_t x = siphash24g(digest, 20);
  642. const uint32_t d1 = (uint32_t) x;
  643. const uint32_t d2 = (uint32_t)( (x>>16) + x);
  644. const uint32_t d3 = (uint32_t)( (x>>32) + x);
  645. const uint32_t d4 = (uint32_t)( (x>>48) + x);
  646. return bitarray_is_set(set->ba, BIT(d1)) &&
  647. bitarray_is_set(set->ba, BIT(d2)) &&
  648. bitarray_is_set(set->ba, BIT(d3)) &&
  649. bitarray_is_set(set->ba, BIT(d4));
  650. }
  651. #undef BIT
  652. digestset_t *digestset_new(int max_elements);
  653. void digestset_free_(digestset_t* set);
  654. #define digestset_free(set) FREE_AND_NULL(digestset, (set))
  655. /* These functions, given an <b>array</b> of <b>n_elements</b>, return the
  656. * <b>nth</b> lowest element. <b>nth</b>=0 gives the lowest element;
  657. * <b>n_elements</b>-1 gives the highest; and (<b>n_elements</b>-1) / 2 gives
  658. * the median. As a side effect, the elements of <b>array</b> are sorted. */
  659. int find_nth_int(int *array, int n_elements, int nth);
  660. time_t find_nth_time(time_t *array, int n_elements, int nth);
  661. double find_nth_double(double *array, int n_elements, int nth);
  662. int32_t find_nth_int32(int32_t *array, int n_elements, int nth);
  663. uint32_t find_nth_uint32(uint32_t *array, int n_elements, int nth);
  664. long find_nth_long(long *array, int n_elements, int nth);
  665. static inline int
  666. median_int(int *array, int n_elements)
  667. {
  668. return find_nth_int(array, n_elements, (n_elements-1)/2);
  669. }
  670. static inline time_t
  671. median_time(time_t *array, int n_elements)
  672. {
  673. return find_nth_time(array, n_elements, (n_elements-1)/2);
  674. }
  675. static inline double
  676. median_double(double *array, int n_elements)
  677. {
  678. return find_nth_double(array, n_elements, (n_elements-1)/2);
  679. }
  680. static inline uint32_t
  681. median_uint32(uint32_t *array, int n_elements)
  682. {
  683. return find_nth_uint32(array, n_elements, (n_elements-1)/2);
  684. }
  685. static inline int32_t
  686. median_int32(int32_t *array, int n_elements)
  687. {
  688. return find_nth_int32(array, n_elements, (n_elements-1)/2);
  689. }
  690. static inline uint32_t
  691. third_quartile_uint32(uint32_t *array, int n_elements)
  692. {
  693. return find_nth_uint32(array, n_elements, (n_elements*3)/4);
  694. }
  695. #endif /* !defined(TOR_CONTAINER_H) */