container.c 53 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542
  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. /**
  6. * \file container.c
  7. * \brief Implements a smartlist (a resizable array) along
  8. * with helper functions to use smartlists. Also includes
  9. * hash table implementations of a string-to-void* map, and of
  10. * a digest-to-void* map.
  11. **/
  12. #include "compat.h"
  13. #include "util.h"
  14. #include "torlog.h"
  15. #include "container.h"
  16. #include "crypto.h"
  17. #include <stdlib.h>
  18. #include <string.h>
  19. #include <assert.h>
  20. #include "ht.h"
  21. /** All newly allocated smartlists have this capacity. */
  22. #define SMARTLIST_DEFAULT_CAPACITY 16
  23. /** Allocate and return an empty smartlist.
  24. */
  25. MOCK_IMPL(smartlist_t *,
  26. smartlist_new,(void))
  27. {
  28. smartlist_t *sl = tor_malloc(sizeof(smartlist_t));
  29. sl->num_used = 0;
  30. sl->capacity = SMARTLIST_DEFAULT_CAPACITY;
  31. sl->list = tor_calloc(sizeof(void *), sl->capacity);
  32. return sl;
  33. }
  34. /** Deallocate a smartlist. Does not release storage associated with the
  35. * list's elements.
  36. */
  37. MOCK_IMPL(void,
  38. smartlist_free_,(smartlist_t *sl))
  39. {
  40. if (!sl)
  41. return;
  42. tor_free(sl->list);
  43. tor_free(sl);
  44. }
  45. /** Remove all elements from the list.
  46. */
  47. void
  48. smartlist_clear(smartlist_t *sl)
  49. {
  50. memset(sl->list, 0, sizeof(void *) * sl->num_used);
  51. sl->num_used = 0;
  52. }
  53. #if SIZE_MAX < INT_MAX
  54. #error "We don't support systems where size_t is smaller than int."
  55. #endif
  56. /** Make sure that <b>sl</b> can hold at least <b>size</b> entries. */
  57. static inline void
  58. smartlist_ensure_capacity(smartlist_t *sl, size_t size)
  59. {
  60. /* Set MAX_CAPACITY to MIN(INT_MAX, SIZE_MAX / sizeof(void*)) */
  61. #if (SIZE_MAX/SIZEOF_VOID_P) > INT_MAX
  62. #define MAX_CAPACITY (INT_MAX)
  63. #else
  64. #define MAX_CAPACITY (int)((SIZE_MAX / (sizeof(void*))))
  65. #endif
  66. tor_assert(size <= MAX_CAPACITY);
  67. if (size > (size_t) sl->capacity) {
  68. size_t higher = (size_t) sl->capacity;
  69. if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) {
  70. higher = MAX_CAPACITY;
  71. } else {
  72. while (size > higher)
  73. higher *= 2;
  74. }
  75. sl->list = tor_reallocarray(sl->list, sizeof(void *),
  76. ((size_t)higher));
  77. memset(sl->list + sl->capacity, 0,
  78. sizeof(void *) * (higher - sl->capacity));
  79. sl->capacity = (int) higher;
  80. }
  81. #undef ASSERT_CAPACITY
  82. #undef MAX_CAPACITY
  83. }
  84. /** Append element to the end of the list. */
  85. void
  86. smartlist_add(smartlist_t *sl, void *element)
  87. {
  88. smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1);
  89. sl->list[sl->num_used++] = element;
  90. }
  91. /** Append each element from S2 to the end of S1. */
  92. void
  93. smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
  94. {
  95. size_t new_size = (size_t)s1->num_used + (size_t)s2->num_used;
  96. tor_assert(new_size >= (size_t) s1->num_used); /* check for overflow. */
  97. smartlist_ensure_capacity(s1, new_size);
  98. memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*));
  99. tor_assert(new_size <= INT_MAX); /* redundant. */
  100. s1->num_used = (int) new_size;
  101. }
  102. /** Remove all elements E from sl such that E==element. Preserve
  103. * the order of any elements before E, but elements after E can be
  104. * rearranged.
  105. */
  106. void
  107. smartlist_remove(smartlist_t *sl, const void *element)
  108. {
  109. int i;
  110. if (element == NULL)
  111. return;
  112. for (i=0; i < sl->num_used; i++)
  113. if (sl->list[i] == element) {
  114. sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
  115. i--; /* so we process the new i'th element */
  116. sl->list[sl->num_used] = NULL;
  117. }
  118. }
  119. /** As <b>smartlist_remove</b>, but do not change the order of
  120. * any elements not removed */
  121. void
  122. smartlist_remove_keeporder(smartlist_t *sl, const void *element)
  123. {
  124. int i, j, num_used_orig = sl->num_used;
  125. if (element == NULL)
  126. return;
  127. for (i=j=0; j < num_used_orig; ++j) {
  128. if (sl->list[j] == element) {
  129. --sl->num_used;
  130. } else {
  131. sl->list[i++] = sl->list[j];
  132. }
  133. }
  134. }
  135. /** If <b>sl</b> is nonempty, remove and return the final element. Otherwise,
  136. * return NULL. */
  137. void *
  138. smartlist_pop_last(smartlist_t *sl)
  139. {
  140. tor_assert(sl);
  141. if (sl->num_used) {
  142. void *tmp = sl->list[--sl->num_used];
  143. sl->list[sl->num_used] = NULL;
  144. return tmp;
  145. } else
  146. return NULL;
  147. }
  148. /** Reverse the order of the items in <b>sl</b>. */
  149. void
  150. smartlist_reverse(smartlist_t *sl)
  151. {
  152. int i, j;
  153. void *tmp;
  154. tor_assert(sl);
  155. for (i = 0, j = sl->num_used-1; i < j; ++i, --j) {
  156. tmp = sl->list[i];
  157. sl->list[i] = sl->list[j];
  158. sl->list[j] = tmp;
  159. }
  160. }
  161. /** If there are any strings in sl equal to element, remove and free them.
  162. * Does not preserve order. */
  163. void
  164. smartlist_string_remove(smartlist_t *sl, const char *element)
  165. {
  166. int i;
  167. tor_assert(sl);
  168. tor_assert(element);
  169. for (i = 0; i < sl->num_used; ++i) {
  170. if (!strcmp(element, sl->list[i])) {
  171. tor_free(sl->list[i]);
  172. sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
  173. i--; /* so we process the new i'th element */
  174. sl->list[sl->num_used] = NULL;
  175. }
  176. }
  177. }
  178. /** Return true iff some element E of sl has E==element.
  179. */
  180. int
  181. smartlist_contains(const smartlist_t *sl, const void *element)
  182. {
  183. int i;
  184. for (i=0; i < sl->num_used; i++)
  185. if (sl->list[i] == element)
  186. return 1;
  187. return 0;
  188. }
  189. /** Return true iff <b>sl</b> has some element E such that
  190. * !strcmp(E,<b>element</b>)
  191. */
  192. int
  193. smartlist_contains_string(const smartlist_t *sl, const char *element)
  194. {
  195. int i;
  196. if (!sl) return 0;
  197. for (i=0; i < sl->num_used; i++)
  198. if (strcmp((const char*)sl->list[i],element)==0)
  199. return 1;
  200. return 0;
  201. }
  202. /** If <b>element</b> is equal to an element of <b>sl</b>, return that
  203. * element's index. Otherwise, return -1. */
  204. int
  205. smartlist_string_pos(const smartlist_t *sl, const char *element)
  206. {
  207. int i;
  208. if (!sl) return -1;
  209. for (i=0; i < sl->num_used; i++)
  210. if (strcmp((const char*)sl->list[i],element)==0)
  211. return i;
  212. return -1;
  213. }
  214. /** If <b>element</b> is the same pointer as an element of <b>sl</b>, return
  215. * that element's index. Otherwise, return -1. */
  216. int
  217. smartlist_pos(const smartlist_t *sl, const void *element)
  218. {
  219. int i;
  220. if (!sl) return -1;
  221. for (i=0; i < sl->num_used; i++)
  222. if (element == sl->list[i])
  223. return i;
  224. return -1;
  225. }
  226. /** Return true iff <b>sl</b> has some element E such that
  227. * !strcasecmp(E,<b>element</b>)
  228. */
  229. int
  230. smartlist_contains_string_case(const smartlist_t *sl, const char *element)
  231. {
  232. int i;
  233. if (!sl) return 0;
  234. for (i=0; i < sl->num_used; i++)
  235. if (strcasecmp((const char*)sl->list[i],element)==0)
  236. return 1;
  237. return 0;
  238. }
  239. /** Return true iff <b>sl</b> has some element E such that E is equal
  240. * to the decimal encoding of <b>num</b>.
  241. */
  242. int
  243. smartlist_contains_int_as_string(const smartlist_t *sl, int num)
  244. {
  245. char buf[32]; /* long enough for 64-bit int, and then some. */
  246. tor_snprintf(buf,sizeof(buf),"%d", num);
  247. return smartlist_contains_string(sl, buf);
  248. }
  249. /** Return true iff the two lists contain the same strings in the same
  250. * order, or if they are both NULL. */
  251. int
  252. smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2)
  253. {
  254. if (sl1 == NULL)
  255. return sl2 == NULL;
  256. if (sl2 == NULL)
  257. return 0;
  258. if (smartlist_len(sl1) != smartlist_len(sl2))
  259. return 0;
  260. SMARTLIST_FOREACH(sl1, const char *, cp1, {
  261. const char *cp2 = smartlist_get(sl2, cp1_sl_idx);
  262. if (strcmp(cp1, cp2))
  263. return 0;
  264. });
  265. return 1;
  266. }
  267. /** Return true iff the two lists contain the same int pointer values in
  268. * the same order, or if they are both NULL. */
  269. int
  270. smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2)
  271. {
  272. if (sl1 == NULL)
  273. return sl2 == NULL;
  274. if (sl2 == NULL)
  275. return 0;
  276. if (smartlist_len(sl1) != smartlist_len(sl2))
  277. return 0;
  278. SMARTLIST_FOREACH(sl1, int *, cp1, {
  279. int *cp2 = smartlist_get(sl2, cp1_sl_idx);
  280. if (*cp1 != *cp2)
  281. return 0;
  282. });
  283. return 1;
  284. }
  285. /** Return true iff <b>sl</b> has some element E such that
  286. * tor_memeq(E,<b>element</b>,DIGEST_LEN)
  287. */
  288. int
  289. smartlist_contains_digest(const smartlist_t *sl, const char *element)
  290. {
  291. int i;
  292. if (!sl) return 0;
  293. for (i=0; i < sl->num_used; i++)
  294. if (tor_memeq((const char*)sl->list[i],element,DIGEST_LEN))
  295. return 1;
  296. return 0;
  297. }
  298. /** Return true iff some element E of sl2 has smartlist_contains(sl1,E).
  299. */
  300. int
  301. smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
  302. {
  303. int i;
  304. for (i=0; i < sl2->num_used; i++)
  305. if (smartlist_contains(sl1, sl2->list[i]))
  306. return 1;
  307. return 0;
  308. }
  309. /** Remove every element E of sl1 such that !smartlist_contains(sl2,E).
  310. * Does not preserve the order of sl1.
  311. */
  312. void
  313. smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
  314. {
  315. int i;
  316. for (i=0; i < sl1->num_used; i++)
  317. if (!smartlist_contains(sl2, sl1->list[i])) {
  318. sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */
  319. i--; /* so we process the new i'th element */
  320. sl1->list[sl1->num_used] = NULL;
  321. }
  322. }
  323. /** Remove every element E of sl1 such that smartlist_contains(sl2,E).
  324. * Does not preserve the order of sl1.
  325. */
  326. void
  327. smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
  328. {
  329. int i;
  330. for (i=0; i < sl2->num_used; i++)
  331. smartlist_remove(sl1, sl2->list[i]);
  332. }
  333. /** Remove the <b>idx</b>th element of sl; if idx is not the last
  334. * element, swap the last element of sl into the <b>idx</b>th space.
  335. */
  336. void
  337. smartlist_del(smartlist_t *sl, int idx)
  338. {
  339. tor_assert(sl);
  340. tor_assert(idx>=0);
  341. tor_assert(idx < sl->num_used);
  342. sl->list[idx] = sl->list[--sl->num_used];
  343. sl->list[sl->num_used] = NULL;
  344. }
  345. /** Remove the <b>idx</b>th element of sl; if idx is not the last element,
  346. * moving all subsequent elements back one space. Return the old value
  347. * of the <b>idx</b>th element.
  348. */
  349. void
  350. smartlist_del_keeporder(smartlist_t *sl, int idx)
  351. {
  352. tor_assert(sl);
  353. tor_assert(idx>=0);
  354. tor_assert(idx < sl->num_used);
  355. --sl->num_used;
  356. if (idx < sl->num_used)
  357. memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx));
  358. sl->list[sl->num_used] = NULL;
  359. }
  360. /** Insert the value <b>val</b> as the new <b>idx</b>th element of
  361. * <b>sl</b>, moving all items previously at <b>idx</b> or later
  362. * forward one space.
  363. */
  364. void
  365. smartlist_insert(smartlist_t *sl, int idx, void *val)
  366. {
  367. tor_assert(sl);
  368. tor_assert(idx>=0);
  369. tor_assert(idx <= sl->num_used);
  370. if (idx == sl->num_used) {
  371. smartlist_add(sl, val);
  372. } else {
  373. smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1);
  374. /* Move other elements away */
  375. if (idx < sl->num_used)
  376. memmove(sl->list + idx + 1, sl->list + idx,
  377. sizeof(void*)*(sl->num_used-idx));
  378. sl->num_used++;
  379. sl->list[idx] = val;
  380. }
  381. }
  382. /**
  383. * Split a string <b>str</b> along all occurrences of <b>sep</b>,
  384. * appending the (newly allocated) split strings, in order, to
  385. * <b>sl</b>. Return the number of strings added to <b>sl</b>.
  386. *
  387. * If <b>flags</b>&amp;SPLIT_SKIP_SPACE is true, remove initial and
  388. * trailing space from each entry.
  389. * If <b>flags</b>&amp;SPLIT_IGNORE_BLANK is true, remove any entries
  390. * of length 0.
  391. * If <b>flags</b>&amp;SPLIT_STRIP_SPACE is true, strip spaces from each
  392. * split string.
  393. *
  394. * If <b>max</b>\>0, divide the string into no more than <b>max</b> pieces. If
  395. * <b>sep</b> is NULL, split on any sequence of horizontal space.
  396. */
  397. int
  398. smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,
  399. int flags, int max)
  400. {
  401. const char *cp, *end, *next;
  402. int n = 0;
  403. tor_assert(sl);
  404. tor_assert(str);
  405. cp = str;
  406. while (1) {
  407. if (flags&SPLIT_SKIP_SPACE) {
  408. while (TOR_ISSPACE(*cp)) ++cp;
  409. }
  410. if (max>0 && n == max-1) {
  411. end = strchr(cp,'\0');
  412. } else if (sep) {
  413. end = strstr(cp,sep);
  414. if (!end)
  415. end = strchr(cp,'\0');
  416. } else {
  417. for (end = cp; *end && *end != '\t' && *end != ' '; ++end)
  418. ;
  419. }
  420. tor_assert(end);
  421. if (!*end) {
  422. next = NULL;
  423. } else if (sep) {
  424. next = end+strlen(sep);
  425. } else {
  426. next = end+1;
  427. while (*next == '\t' || *next == ' ')
  428. ++next;
  429. }
  430. if (flags&SPLIT_SKIP_SPACE) {
  431. while (end > cp && TOR_ISSPACE(*(end-1)))
  432. --end;
  433. }
  434. if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) {
  435. char *string = tor_strndup(cp, end-cp);
  436. if (flags&SPLIT_STRIP_SPACE)
  437. tor_strstrip(string, " ");
  438. smartlist_add(sl, string);
  439. ++n;
  440. }
  441. if (!next)
  442. break;
  443. cp = next;
  444. }
  445. return n;
  446. }
  447. /** Allocate and return a new string containing the concatenation of
  448. * the elements of <b>sl</b>, in order, separated by <b>join</b>. If
  449. * <b>terminate</b> is true, also terminate the string with <b>join</b>.
  450. * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of
  451. * the returned string. Requires that every element of <b>sl</b> is
  452. * NUL-terminated string.
  453. */
  454. char *
  455. smartlist_join_strings(smartlist_t *sl, const char *join,
  456. int terminate, size_t *len_out)
  457. {
  458. return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out);
  459. }
  460. /** As smartlist_join_strings, but instead of separating/terminated with a
  461. * NUL-terminated string <b>join</b>, uses the <b>join_len</b>-byte sequence
  462. * at <b>join</b>. (Useful for generating a sequence of NUL-terminated
  463. * strings.)
  464. */
  465. char *
  466. smartlist_join_strings2(smartlist_t *sl, const char *join,
  467. size_t join_len, int terminate, size_t *len_out)
  468. {
  469. int i;
  470. size_t n = 0;
  471. char *r = NULL, *dst, *src;
  472. tor_assert(sl);
  473. tor_assert(join);
  474. if (terminate)
  475. n = join_len;
  476. for (i = 0; i < sl->num_used; ++i) {
  477. n += strlen(sl->list[i]);
  478. if (i+1 < sl->num_used) /* avoid double-counting the last one */
  479. n += join_len;
  480. }
  481. dst = r = tor_malloc(n+1);
  482. for (i = 0; i < sl->num_used; ) {
  483. for (src = sl->list[i]; *src; )
  484. *dst++ = *src++;
  485. if (++i < sl->num_used) {
  486. memcpy(dst, join, join_len);
  487. dst += join_len;
  488. }
  489. }
  490. if (terminate) {
  491. memcpy(dst, join, join_len);
  492. dst += join_len;
  493. }
  494. *dst = '\0';
  495. if (len_out)
  496. *len_out = dst-r;
  497. return r;
  498. }
  499. /** Sort the members of <b>sl</b> into an order defined by
  500. * the ordering function <b>compare</b>, which returns less then 0 if a
  501. * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.
  502. */
  503. void
  504. smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
  505. {
  506. if (!sl->num_used)
  507. return;
  508. qsort(sl->list, sl->num_used, sizeof(void*),
  509. (int (*)(const void *,const void*))compare);
  510. }
  511. /** Given a smartlist <b>sl</b> sorted with the function <b>compare</b>,
  512. * return the most frequent member in the list. Break ties in favor of
  513. * later elements. If the list is empty, return NULL. If count_out is
  514. * non-null, set it to the count of the most frequent member.
  515. */
  516. void *
  517. smartlist_get_most_frequent_(const smartlist_t *sl,
  518. int (*compare)(const void **a, const void **b),
  519. int *count_out)
  520. {
  521. const void *most_frequent = NULL;
  522. int most_frequent_count = 0;
  523. const void *cur = NULL;
  524. int i, count=0;
  525. if (!sl->num_used) {
  526. if (count_out)
  527. *count_out = 0;
  528. return NULL;
  529. }
  530. for (i = 0; i < sl->num_used; ++i) {
  531. const void *item = sl->list[i];
  532. if (cur && 0 == compare(&cur, &item)) {
  533. ++count;
  534. } else {
  535. if (cur && count >= most_frequent_count) {
  536. most_frequent = cur;
  537. most_frequent_count = count;
  538. }
  539. cur = item;
  540. count = 1;
  541. }
  542. }
  543. if (cur && count >= most_frequent_count) {
  544. most_frequent = cur;
  545. most_frequent_count = count;
  546. }
  547. if (count_out)
  548. *count_out = most_frequent_count;
  549. return (void*)most_frequent;
  550. }
  551. /** Given a sorted smartlist <b>sl</b> and the comparison function used to
  552. * sort it, remove all duplicate members. If free_fn is provided, calls
  553. * free_fn on each duplicate. Otherwise, just removes them. Preserves order.
  554. */
  555. void
  556. smartlist_uniq(smartlist_t *sl,
  557. int (*compare)(const void **a, const void **b),
  558. void (*free_fn)(void *a))
  559. {
  560. int i;
  561. for (i=1; i < sl->num_used; ++i) {
  562. if (compare((const void **)&(sl->list[i-1]),
  563. (const void **)&(sl->list[i])) == 0) {
  564. if (free_fn)
  565. free_fn(sl->list[i]);
  566. smartlist_del_keeporder(sl, i--);
  567. }
  568. }
  569. }
  570. /** Assuming the members of <b>sl</b> are in order, return a pointer to the
  571. * member that matches <b>key</b>. Ordering and matching are defined by a
  572. * <b>compare</b> function that returns 0 on a match; less than 0 if key is
  573. * less than member, and greater than 0 if key is greater then member.
  574. */
  575. void *
  576. smartlist_bsearch(smartlist_t *sl, const void *key,
  577. int (*compare)(const void *key, const void **member))
  578. {
  579. int found, idx;
  580. idx = smartlist_bsearch_idx(sl, key, compare, &found);
  581. return found ? smartlist_get(sl, idx) : NULL;
  582. }
  583. /** Assuming the members of <b>sl</b> are in order, return the index of the
  584. * member that matches <b>key</b>. If no member matches, return the index of
  585. * the first member greater than <b>key</b>, or smartlist_len(sl) if no member
  586. * is greater than <b>key</b>. Set <b>found_out</b> to true on a match, to
  587. * false otherwise. Ordering and matching are defined by a <b>compare</b>
  588. * function that returns 0 on a match; less than 0 if key is less than member,
  589. * and greater than 0 if key is greater then member.
  590. */
  591. int
  592. smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
  593. int (*compare)(const void *key, const void **member),
  594. int *found_out)
  595. {
  596. int hi, lo, cmp, mid, len, diff;
  597. tor_assert(sl);
  598. tor_assert(compare);
  599. tor_assert(found_out);
  600. len = smartlist_len(sl);
  601. /* Check for the trivial case of a zero-length list */
  602. if (len == 0) {
  603. *found_out = 0;
  604. /* We already know smartlist_len(sl) is 0 in this case */
  605. return 0;
  606. }
  607. /* Okay, we have a real search to do */
  608. tor_assert(len > 0);
  609. lo = 0;
  610. hi = len - 1;
  611. /*
  612. * These invariants are always true:
  613. *
  614. * For all i such that 0 <= i < lo, sl[i] < key
  615. * For all i such that hi < i <= len, sl[i] > key
  616. */
  617. while (lo <= hi) {
  618. diff = hi - lo;
  619. /*
  620. * We want mid = (lo + hi) / 2, but that could lead to overflow, so
  621. * instead diff = hi - lo (non-negative because of loop condition), and
  622. * then hi = lo + diff, mid = (lo + lo + diff) / 2 = lo + (diff / 2).
  623. */
  624. mid = lo + (diff / 2);
  625. cmp = compare(key, (const void**) &(sl->list[mid]));
  626. if (cmp == 0) {
  627. /* sl[mid] == key; we found it */
  628. *found_out = 1;
  629. return mid;
  630. } else if (cmp > 0) {
  631. /*
  632. * key > sl[mid] and an index i such that sl[i] == key must
  633. * have i > mid if it exists.
  634. */
  635. /*
  636. * Since lo <= mid <= hi, hi can only decrease on each iteration (by
  637. * being set to mid - 1) and hi is initially len - 1, mid < len should
  638. * always hold, and this is not symmetric with the left end of list
  639. * mid > 0 test below. A key greater than the right end of the list
  640. * should eventually lead to lo == hi == mid == len - 1, and then
  641. * we set lo to len below and fall out to the same exit we hit for
  642. * a key in the middle of the list but not matching. Thus, we just
  643. * assert for consistency here rather than handle a mid == len case.
  644. */
  645. tor_assert(mid < len);
  646. /* Move lo to the element immediately after sl[mid] */
  647. lo = mid + 1;
  648. } else {
  649. /* This should always be true in this case */
  650. tor_assert(cmp < 0);
  651. /*
  652. * key < sl[mid] and an index i such that sl[i] == key must
  653. * have i < mid if it exists.
  654. */
  655. if (mid > 0) {
  656. /* Normal case, move hi to the element immediately before sl[mid] */
  657. hi = mid - 1;
  658. } else {
  659. /* These should always be true in this case */
  660. tor_assert(mid == lo);
  661. tor_assert(mid == 0);
  662. /*
  663. * We were at the beginning of the list and concluded that every
  664. * element e compares e > key.
  665. */
  666. *found_out = 0;
  667. return 0;
  668. }
  669. }
  670. }
  671. /*
  672. * lo > hi; we have no element matching key but we have elements falling
  673. * on both sides of it. The lo index points to the first element > key.
  674. */
  675. tor_assert(lo == hi + 1); /* All other cases should have been handled */
  676. tor_assert(lo >= 0);
  677. tor_assert(lo <= len);
  678. tor_assert(hi >= 0);
  679. tor_assert(hi <= len);
  680. if (lo < len) {
  681. cmp = compare(key, (const void **) &(sl->list[lo]));
  682. tor_assert(cmp < 0);
  683. } else {
  684. cmp = compare(key, (const void **) &(sl->list[len-1]));
  685. tor_assert(cmp > 0);
  686. }
  687. *found_out = 0;
  688. return lo;
  689. }
  690. /** Helper: compare two const char **s. */
  691. static int
  692. compare_string_ptrs_(const void **_a, const void **_b)
  693. {
  694. return strcmp((const char*)*_a, (const char*)*_b);
  695. }
  696. /** Sort a smartlist <b>sl</b> containing strings into lexically ascending
  697. * order. */
  698. void
  699. smartlist_sort_strings(smartlist_t *sl)
  700. {
  701. smartlist_sort(sl, compare_string_ptrs_);
  702. }
  703. /** Return the most frequent string in the sorted list <b>sl</b> */
  704. const char *
  705. smartlist_get_most_frequent_string(smartlist_t *sl)
  706. {
  707. return smartlist_get_most_frequent(sl, compare_string_ptrs_);
  708. }
  709. /** Return the most frequent string in the sorted list <b>sl</b>.
  710. * If <b>count_out</b> is provided, set <b>count_out</b> to the
  711. * number of times that string appears.
  712. */
  713. const char *
  714. smartlist_get_most_frequent_string_(smartlist_t *sl, int *count_out)
  715. {
  716. return smartlist_get_most_frequent_(sl, compare_string_ptrs_, count_out);
  717. }
  718. /** Remove duplicate strings from a sorted list, and free them with tor_free().
  719. */
  720. void
  721. smartlist_uniq_strings(smartlist_t *sl)
  722. {
  723. smartlist_uniq(sl, compare_string_ptrs_, tor_free_);
  724. }
  725. /** Helper: compare two pointers. */
  726. static int
  727. compare_ptrs_(const void **_a, const void **_b)
  728. {
  729. const void *a = *_a, *b = *_b;
  730. if (a<b)
  731. return -1;
  732. else if (a==b)
  733. return 0;
  734. else
  735. return 1;
  736. }
  737. /** Sort <b>sl</b> in ascending order of the pointers it contains. */
  738. void
  739. smartlist_sort_pointers(smartlist_t *sl)
  740. {
  741. smartlist_sort(sl, compare_ptrs_);
  742. }
  743. /* Heap-based priority queue implementation for O(lg N) insert and remove.
  744. * Recall that the heap property is that, for every index I, h[I] <
  745. * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
  746. *
  747. * For us to remove items other than the topmost item, each item must store
  748. * its own index within the heap. When calling the pqueue functions, tell
  749. * them about the offset of the field that stores the index within the item.
  750. *
  751. * Example:
  752. *
  753. * typedef struct timer_t {
  754. * struct timeval tv;
  755. * int heap_index;
  756. * } timer_t;
  757. *
  758. * static int compare(const void *p1, const void *p2) {
  759. * const timer_t *t1 = p1, *t2 = p2;
  760. * if (t1->tv.tv_sec < t2->tv.tv_sec) {
  761. * return -1;
  762. * } else if (t1->tv.tv_sec > t2->tv.tv_sec) {
  763. * return 1;
  764. * } else {
  765. * return t1->tv.tv_usec - t2->tv_usec;
  766. * }
  767. * }
  768. *
  769. * void timer_heap_insert(smartlist_t *heap, timer_t *timer) {
  770. * smartlist_pqueue_add(heap, compare, offsetof(timer_t, heap_index),
  771. * timer);
  772. * }
  773. *
  774. * void timer_heap_pop(smartlist_t *heap) {
  775. * return smartlist_pqueue_pop(heap, compare,
  776. * offsetof(timer_t, heap_index));
  777. * }
  778. */
  779. /** @{ */
  780. /** Functions to manipulate heap indices to find a node's parent and children.
  781. *
  782. * For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x]
  783. * = 2*x + 1. But this is C, so we have to adjust a little. */
  784. /* MAX_PARENT_IDX is the largest IDX in the smartlist which might have
  785. * children whose indices fit inside an int.
  786. * LEFT_CHILD(MAX_PARENT_IDX) == INT_MAX-2;
  787. * RIGHT_CHILD(MAX_PARENT_IDX) == INT_MAX-1;
  788. * LEFT_CHILD(MAX_PARENT_IDX + 1) == INT_MAX // impossible, see max list size.
  789. */
  790. #define MAX_PARENT_IDX ((INT_MAX - 2) / 2)
  791. /* If this is true, then i is small enough to potentially have children
  792. * in the smartlist, and it is save to use LEFT_CHILD/RIGHT_CHILD on it. */
  793. #define IDX_MAY_HAVE_CHILDREN(i) ((i) <= MAX_PARENT_IDX)
  794. #define LEFT_CHILD(i) ( 2*(i) + 1 )
  795. #define RIGHT_CHILD(i) ( 2*(i) + 2 )
  796. #define PARENT(i) ( ((i)-1) / 2 )
  797. /** }@ */
  798. /** @{ */
  799. /** Helper macros for heaps: Given a local variable <b>idx_field_offset</b>
  800. * set to the offset of an integer index within the heap element structure,
  801. * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to
  802. * where p's index is stored. Given additionally a local smartlist <b>sl</b>,
  803. * UPDATE_IDX(i) sets the index of the element at <b>i</b> to the correct
  804. * value (that is, to <b>i</b>).
  805. */
  806. #define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset))
  807. #define UPDATE_IDX(i) do { \
  808. void *updated = sl->list[i]; \
  809. *IDXP(updated) = i; \
  810. } while (0)
  811. #define IDX_OF_ITEM(p) (*IDXP(p))
  812. /** @} */
  813. /** Helper. <b>sl</b> may have at most one violation of the heap property:
  814. * the item at <b>idx</b> may be greater than one or both of its children.
  815. * Restore the heap property. */
  816. static inline void
  817. smartlist_heapify(smartlist_t *sl,
  818. int (*compare)(const void *a, const void *b),
  819. int idx_field_offset,
  820. int idx)
  821. {
  822. while (1) {
  823. if (! IDX_MAY_HAVE_CHILDREN(idx)) {
  824. /* idx is so large that it cannot have any children, since doing so
  825. * would mean the smartlist was over-capacity. Therefore it cannot
  826. * violate the heap property by being greater than a child (since it
  827. * doesn't have any). */
  828. return;
  829. }
  830. int left_idx = LEFT_CHILD(idx);
  831. int best_idx;
  832. if (left_idx >= sl->num_used)
  833. return;
  834. if (compare(sl->list[idx],sl->list[left_idx]) < 0)
  835. best_idx = idx;
  836. else
  837. best_idx = left_idx;
  838. if (left_idx+1 < sl->num_used &&
  839. compare(sl->list[left_idx+1],sl->list[best_idx]) < 0)
  840. best_idx = left_idx + 1;
  841. if (best_idx == idx) {
  842. return;
  843. } else {
  844. void *tmp = sl->list[idx];
  845. sl->list[idx] = sl->list[best_idx];
  846. sl->list[best_idx] = tmp;
  847. UPDATE_IDX(idx);
  848. UPDATE_IDX(best_idx);
  849. idx = best_idx;
  850. }
  851. }
  852. }
  853. /** Insert <b>item</b> into the heap stored in <b>sl</b>, where order is
  854. * determined by <b>compare</b> and the offset of the item in the heap is
  855. * stored in an int-typed field at position <b>idx_field_offset</b> within
  856. * item.
  857. */
  858. void
  859. smartlist_pqueue_add(smartlist_t *sl,
  860. int (*compare)(const void *a, const void *b),
  861. int idx_field_offset,
  862. void *item)
  863. {
  864. int idx;
  865. smartlist_add(sl,item);
  866. UPDATE_IDX(sl->num_used-1);
  867. for (idx = sl->num_used - 1; idx; ) {
  868. int parent = PARENT(idx);
  869. if (compare(sl->list[idx], sl->list[parent]) < 0) {
  870. void *tmp = sl->list[parent];
  871. sl->list[parent] = sl->list[idx];
  872. sl->list[idx] = tmp;
  873. UPDATE_IDX(parent);
  874. UPDATE_IDX(idx);
  875. idx = parent;
  876. } else {
  877. return;
  878. }
  879. }
  880. }
  881. /** Remove and return the top-priority item from the heap stored in <b>sl</b>,
  882. * where order is determined by <b>compare</b> and the item's position is
  883. * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must
  884. * not be empty. */
  885. void *
  886. smartlist_pqueue_pop(smartlist_t *sl,
  887. int (*compare)(const void *a, const void *b),
  888. int idx_field_offset)
  889. {
  890. void *top;
  891. tor_assert(sl->num_used);
  892. top = sl->list[0];
  893. *IDXP(top)=-1;
  894. if (--sl->num_used) {
  895. sl->list[0] = sl->list[sl->num_used];
  896. sl->list[sl->num_used] = NULL;
  897. UPDATE_IDX(0);
  898. smartlist_heapify(sl, compare, idx_field_offset, 0);
  899. }
  900. sl->list[sl->num_used] = NULL;
  901. return top;
  902. }
  903. /** Remove the item <b>item</b> from the heap stored in <b>sl</b>,
  904. * where order is determined by <b>compare</b> and the item's position is
  905. * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must
  906. * not be empty. */
  907. void
  908. smartlist_pqueue_remove(smartlist_t *sl,
  909. int (*compare)(const void *a, const void *b),
  910. int idx_field_offset,
  911. void *item)
  912. {
  913. int idx = IDX_OF_ITEM(item);
  914. tor_assert(idx >= 0);
  915. tor_assert(sl->list[idx] == item);
  916. --sl->num_used;
  917. *IDXP(item) = -1;
  918. if (idx == sl->num_used) {
  919. sl->list[sl->num_used] = NULL;
  920. return;
  921. } else {
  922. sl->list[idx] = sl->list[sl->num_used];
  923. sl->list[sl->num_used] = NULL;
  924. UPDATE_IDX(idx);
  925. smartlist_heapify(sl, compare, idx_field_offset, idx);
  926. }
  927. }
  928. /** Assert that the heap property is correctly maintained by the heap stored
  929. * in <b>sl</b>, where order is determined by <b>compare</b>. */
  930. void
  931. smartlist_pqueue_assert_ok(smartlist_t *sl,
  932. int (*compare)(const void *a, const void *b),
  933. int idx_field_offset)
  934. {
  935. int i;
  936. for (i = sl->num_used - 1; i >= 0; --i) {
  937. if (i>0)
  938. tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
  939. tor_assert(IDX_OF_ITEM(sl->list[i]) == i);
  940. }
  941. }
  942. /** Helper: compare two DIGEST_LEN digests. */
  943. static int
  944. compare_digests_(const void **_a, const void **_b)
  945. {
  946. return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
  947. }
  948. /** Sort the list of DIGEST_LEN-byte digests into ascending order. */
  949. void
  950. smartlist_sort_digests(smartlist_t *sl)
  951. {
  952. smartlist_sort(sl, compare_digests_);
  953. }
  954. /** Remove duplicate digests from a sorted list, and free them with tor_free().
  955. */
  956. void
  957. smartlist_uniq_digests(smartlist_t *sl)
  958. {
  959. smartlist_uniq(sl, compare_digests_, tor_free_);
  960. }
  961. /** Helper: compare two DIGEST256_LEN digests. */
  962. static int
  963. compare_digests256_(const void **_a, const void **_b)
  964. {
  965. return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN);
  966. }
  967. /** Sort the list of DIGEST256_LEN-byte digests into ascending order. */
  968. void
  969. smartlist_sort_digests256(smartlist_t *sl)
  970. {
  971. smartlist_sort(sl, compare_digests256_);
  972. }
  973. /** Return the most frequent member of the sorted list of DIGEST256_LEN
  974. * digests in <b>sl</b> */
  975. const uint8_t *
  976. smartlist_get_most_frequent_digest256(smartlist_t *sl)
  977. {
  978. return smartlist_get_most_frequent(sl, compare_digests256_);
  979. }
  980. /** Remove duplicate 256-bit digests from a sorted list, and free them with
  981. * tor_free().
  982. */
  983. void
  984. smartlist_uniq_digests256(smartlist_t *sl)
  985. {
  986. smartlist_uniq(sl, compare_digests256_, tor_free_);
  987. }
  988. /** Helper: Declare an entry type and a map type to implement a mapping using
  989. * ht.h. The map type will be called <b>maptype</b>. The key part of each
  990. * entry is declared using the C declaration <b>keydecl</b>. All functions
  991. * and types associated with the map get prefixed with <b>prefix</b> */
  992. #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \
  993. typedef struct prefix ## entry_t { \
  994. HT_ENTRY(prefix ## entry_t) node; \
  995. void *val; \
  996. keydecl; \
  997. } prefix ## entry_t; \
  998. struct maptype { \
  999. HT_HEAD(prefix ## impl, prefix ## entry_t) head; \
  1000. }
  1001. DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
  1002. DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
  1003. DEFINE_MAP_STRUCTS(digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_);
  1004. /** Helper: compare strmap_entry_t objects by key value. */
  1005. static inline int
  1006. strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
  1007. {
  1008. return !strcmp(a->key, b->key);
  1009. }
  1010. /** Helper: return a hash value for a strmap_entry_t. */
  1011. static inline unsigned int
  1012. strmap_entry_hash(const strmap_entry_t *a)
  1013. {
  1014. return (unsigned) siphash24g(a->key, strlen(a->key));
  1015. }
  1016. /** Helper: compare digestmap_entry_t objects by key value. */
  1017. static inline int
  1018. digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
  1019. {
  1020. return tor_memeq(a->key, b->key, DIGEST_LEN);
  1021. }
  1022. /** Helper: return a hash value for a digest_map_t. */
  1023. static inline unsigned int
  1024. digestmap_entry_hash(const digestmap_entry_t *a)
  1025. {
  1026. return (unsigned) siphash24g(a->key, DIGEST_LEN);
  1027. }
  1028. /** Helper: compare digestmap_entry_t objects by key value. */
  1029. static inline int
  1030. digest256map_entries_eq(const digest256map_entry_t *a,
  1031. const digest256map_entry_t *b)
  1032. {
  1033. return tor_memeq(a->key, b->key, DIGEST256_LEN);
  1034. }
  1035. /** Helper: return a hash value for a digest_map_t. */
  1036. static inline unsigned int
  1037. digest256map_entry_hash(const digest256map_entry_t *a)
  1038. {
  1039. return (unsigned) siphash24g(a->key, DIGEST256_LEN);
  1040. }
  1041. HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
  1042. strmap_entries_eq)
  1043. HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
  1044. strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_)
  1045. HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
  1046. digestmap_entries_eq)
  1047. HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
  1048. digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_)
  1049. HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node,
  1050. digest256map_entry_hash,
  1051. digest256map_entries_eq)
  1052. HT_GENERATE2(digest256map_impl, digest256map_entry_t, node,
  1053. digest256map_entry_hash,
  1054. digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_)
  1055. #define strmap_entry_free(ent) \
  1056. FREE_AND_NULL(strmap_entry_t, strmap_entry_free_, (ent))
  1057. #define digestmap_entry_free(ent) \
  1058. FREE_AND_NULL(digestmap_entry_t, digestmap_entry_free_, (ent))
  1059. #define digest256map_entry_free(ent) \
  1060. FREE_AND_NULL(digest256map_entry_t, digest256map_entry_free_, (ent))
  1061. static inline void
  1062. strmap_entry_free_(strmap_entry_t *ent)
  1063. {
  1064. tor_free(ent->key);
  1065. tor_free(ent);
  1066. }
  1067. static inline void
  1068. digestmap_entry_free_(digestmap_entry_t *ent)
  1069. {
  1070. tor_free(ent);
  1071. }
  1072. static inline void
  1073. digest256map_entry_free_(digest256map_entry_t *ent)
  1074. {
  1075. tor_free(ent);
  1076. }
  1077. static inline void
  1078. strmap_assign_tmp_key(strmap_entry_t *ent, const char *key)
  1079. {
  1080. ent->key = (char*)key;
  1081. }
  1082. static inline void
  1083. digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key)
  1084. {
  1085. memcpy(ent->key, key, DIGEST_LEN);
  1086. }
  1087. static inline void
  1088. digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key)
  1089. {
  1090. memcpy(ent->key, key, DIGEST256_LEN);
  1091. }
  1092. static inline void
  1093. strmap_assign_key(strmap_entry_t *ent, const char *key)
  1094. {
  1095. ent->key = tor_strdup(key);
  1096. }
  1097. static inline void
  1098. digestmap_assign_key(digestmap_entry_t *ent, const char *key)
  1099. {
  1100. memcpy(ent->key, key, DIGEST_LEN);
  1101. }
  1102. static inline void
  1103. digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key)
  1104. {
  1105. memcpy(ent->key, key, DIGEST256_LEN);
  1106. }
  1107. /**
  1108. * Macro: implement all the functions for a map that are declared in
  1109. * container.h by the DECLARE_MAP_FNS() macro. You must additionally define a
  1110. * prefix_entry_free_() function to free entries (and their keys), a
  1111. * prefix_assign_tmp_key() function to temporarily set a stack-allocated
  1112. * entry to hold a key, and a prefix_assign_key() function to set a
  1113. * heap-allocated entry to hold a key.
  1114. */
  1115. #define IMPLEMENT_MAP_FNS(maptype, keytype, prefix) \
  1116. /** Create and return a new empty map. */ \
  1117. MOCK_IMPL(maptype *, \
  1118. prefix##_new,(void)) \
  1119. { \
  1120. maptype *result; \
  1121. result = tor_malloc(sizeof(maptype)); \
  1122. HT_INIT(prefix##_impl, &result->head); \
  1123. return result; \
  1124. } \
  1125. \
  1126. /** Return the item from <b>map</b> whose key matches <b>key</b>, or \
  1127. * NULL if no such value exists. */ \
  1128. void * \
  1129. prefix##_get(const maptype *map, const keytype key) \
  1130. { \
  1131. prefix ##_entry_t *resolve; \
  1132. prefix ##_entry_t search; \
  1133. tor_assert(map); \
  1134. tor_assert(key); \
  1135. prefix ##_assign_tmp_key(&search, key); \
  1136. resolve = HT_FIND(prefix ##_impl, &map->head, &search); \
  1137. if (resolve) { \
  1138. return resolve->val; \
  1139. } else { \
  1140. return NULL; \
  1141. } \
  1142. } \
  1143. \
  1144. /** Add an entry to <b>map</b> mapping <b>key</b> to <b>val</b>; \
  1145. * return the previous value, or NULL if no such value existed. */ \
  1146. void * \
  1147. prefix##_set(maptype *map, const keytype key, void *val) \
  1148. { \
  1149. prefix##_entry_t search; \
  1150. void *oldval; \
  1151. tor_assert(map); \
  1152. tor_assert(key); \
  1153. tor_assert(val); \
  1154. prefix##_assign_tmp_key(&search, key); \
  1155. /* We a lot of our time in this function, so the code below is */ \
  1156. /* meant to optimize the check/alloc/set cycle by avoiding the two */\
  1157. /* trips to the hash table that we would do in the unoptimized */ \
  1158. /* version of this code. (Each of HT_INSERT and HT_FIND calls */ \
  1159. /* HT_SET_HASH and HT_FIND_P.) */ \
  1160. HT_FIND_OR_INSERT_(prefix##_impl, node, prefix##_entry_hash, \
  1161. &(map->head), \
  1162. prefix##_entry_t, &search, ptr, \
  1163. { \
  1164. /* we found an entry. */ \
  1165. oldval = (*ptr)->val; \
  1166. (*ptr)->val = val; \
  1167. return oldval; \
  1168. }, \
  1169. { \
  1170. /* We didn't find the entry. */ \
  1171. prefix##_entry_t *newent = \
  1172. tor_malloc_zero(sizeof(prefix##_entry_t)); \
  1173. prefix##_assign_key(newent, key); \
  1174. newent->val = val; \
  1175. HT_FOI_INSERT_(node, &(map->head), \
  1176. &search, newent, ptr); \
  1177. return NULL; \
  1178. }); \
  1179. } \
  1180. \
  1181. /** Remove the value currently associated with <b>key</b> from the map. \
  1182. * Return the value if one was set, or NULL if there was no entry for \
  1183. * <b>key</b>. \
  1184. * \
  1185. * Note: you must free any storage associated with the returned value. \
  1186. */ \
  1187. void * \
  1188. prefix##_remove(maptype *map, const keytype key) \
  1189. { \
  1190. prefix##_entry_t *resolve; \
  1191. prefix##_entry_t search; \
  1192. void *oldval; \
  1193. tor_assert(map); \
  1194. tor_assert(key); \
  1195. prefix##_assign_tmp_key(&search, key); \
  1196. resolve = HT_REMOVE(prefix##_impl, &map->head, &search); \
  1197. if (resolve) { \
  1198. oldval = resolve->val; \
  1199. prefix##_entry_free(resolve); \
  1200. return oldval; \
  1201. } else { \
  1202. return NULL; \
  1203. } \
  1204. } \
  1205. \
  1206. /** Return the number of elements in <b>map</b>. */ \
  1207. int \
  1208. prefix##_size(const maptype *map) \
  1209. { \
  1210. return HT_SIZE(&map->head); \
  1211. } \
  1212. \
  1213. /** Return true iff <b>map</b> has no entries. */ \
  1214. int \
  1215. prefix##_isempty(const maptype *map) \
  1216. { \
  1217. return HT_EMPTY(&map->head); \
  1218. } \
  1219. \
  1220. /** Assert that <b>map</b> is not corrupt. */ \
  1221. void \
  1222. prefix##_assert_ok(const maptype *map) \
  1223. { \
  1224. tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head)); \
  1225. } \
  1226. \
  1227. /** Remove all entries from <b>map</b>, and deallocate storage for \
  1228. * those entries. If free_val is provided, invoked it every value in \
  1229. * <b>map</b>. */ \
  1230. MOCK_IMPL(void, \
  1231. prefix##_free_, (maptype *map, void (*free_val)(void*))) \
  1232. { \
  1233. prefix##_entry_t **ent, **next, *this; \
  1234. if (!map) \
  1235. return; \
  1236. for (ent = HT_START(prefix##_impl, &map->head); ent != NULL; \
  1237. ent = next) { \
  1238. this = *ent; \
  1239. next = HT_NEXT_RMV(prefix##_impl, &map->head, ent); \
  1240. if (free_val) \
  1241. free_val(this->val); \
  1242. prefix##_entry_free(this); \
  1243. } \
  1244. tor_assert(HT_EMPTY(&map->head)); \
  1245. HT_CLEAR(prefix##_impl, &map->head); \
  1246. tor_free(map); \
  1247. } \
  1248. \
  1249. /** return an <b>iterator</b> pointer to the front of a map. \
  1250. * \
  1251. * Iterator example: \
  1252. * \
  1253. * \code \
  1254. * // uppercase values in "map", removing empty values. \
  1255. * \
  1256. * strmap_iter_t *iter; \
  1257. * const char *key; \
  1258. * void *val; \
  1259. * char *cp; \
  1260. * \
  1261. * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) { \
  1262. * strmap_iter_get(iter, &key, &val); \
  1263. * cp = (char*)val; \
  1264. * if (!*cp) { \
  1265. * iter = strmap_iter_next_rmv(map,iter); \
  1266. * free(val); \
  1267. * } else { \
  1268. * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp); \
  1269. */ \
  1270. prefix##_iter_t * \
  1271. prefix##_iter_init(maptype *map) \
  1272. { \
  1273. tor_assert(map); \
  1274. return HT_START(prefix##_impl, &map->head); \
  1275. } \
  1276. \
  1277. /** Advance <b>iter</b> a single step to the next entry, and return \
  1278. * its new value. */ \
  1279. prefix##_iter_t * \
  1280. prefix##_iter_next(maptype *map, prefix##_iter_t *iter) \
  1281. { \
  1282. tor_assert(map); \
  1283. tor_assert(iter); \
  1284. return HT_NEXT(prefix##_impl, &map->head, iter); \
  1285. } \
  1286. /** Advance <b>iter</b> a single step to the next entry, removing the \
  1287. * current entry, and return its new value. */ \
  1288. prefix##_iter_t * \
  1289. prefix##_iter_next_rmv(maptype *map, prefix##_iter_t *iter) \
  1290. { \
  1291. prefix##_entry_t *rmv; \
  1292. tor_assert(map); \
  1293. tor_assert(iter); \
  1294. tor_assert(*iter); \
  1295. rmv = *iter; \
  1296. iter = HT_NEXT_RMV(prefix##_impl, &map->head, iter); \
  1297. prefix##_entry_free(rmv); \
  1298. return iter; \
  1299. } \
  1300. /** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed \
  1301. * to by iter. */ \
  1302. void \
  1303. prefix##_iter_get(prefix##_iter_t *iter, const keytype *keyp, \
  1304. void **valp) \
  1305. { \
  1306. tor_assert(iter); \
  1307. tor_assert(*iter); \
  1308. tor_assert(keyp); \
  1309. tor_assert(valp); \
  1310. *keyp = (*iter)->key; \
  1311. *valp = (*iter)->val; \
  1312. } \
  1313. /** Return true iff <b>iter</b> has advanced past the last entry of \
  1314. * <b>map</b>. */ \
  1315. int \
  1316. prefix##_iter_done(prefix##_iter_t *iter) \
  1317. { \
  1318. return iter == NULL; \
  1319. }
  1320. IMPLEMENT_MAP_FNS(strmap_t, char *, strmap)
  1321. IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap)
  1322. IMPLEMENT_MAP_FNS(digest256map_t, uint8_t *, digest256map)
  1323. /** Same as strmap_set, but first converts <b>key</b> to lowercase. */
  1324. void *
  1325. strmap_set_lc(strmap_t *map, const char *key, void *val)
  1326. {
  1327. /* We could be a little faster by using strcasecmp instead, and a separate
  1328. * type, but I don't think it matters. */
  1329. void *v;
  1330. char *lc_key = tor_strdup(key);
  1331. tor_strlower(lc_key);
  1332. v = strmap_set(map,lc_key,val);
  1333. tor_free(lc_key);
  1334. return v;
  1335. }
  1336. /** Same as strmap_get, but first converts <b>key</b> to lowercase. */
  1337. void *
  1338. strmap_get_lc(const strmap_t *map, const char *key)
  1339. {
  1340. void *v;
  1341. char *lc_key = tor_strdup(key);
  1342. tor_strlower(lc_key);
  1343. v = strmap_get(map,lc_key);
  1344. tor_free(lc_key);
  1345. return v;
  1346. }
  1347. /** Same as strmap_remove, but first converts <b>key</b> to lowercase */
  1348. void *
  1349. strmap_remove_lc(strmap_t *map, const char *key)
  1350. {
  1351. void *v;
  1352. char *lc_key = tor_strdup(key);
  1353. tor_strlower(lc_key);
  1354. v = strmap_remove(map,lc_key);
  1355. tor_free(lc_key);
  1356. return v;
  1357. }
  1358. /** Declare a function called <b>funcname</b> that acts as a find_nth_FOO
  1359. * function for an array of type <b>elt_t</b>*.
  1360. *
  1361. * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding
  1362. * the kth element of an n-element list can be done in O(n). Then again, this
  1363. * implementation is not in critical path, and it is obviously correct. */
  1364. #define IMPLEMENT_ORDER_FUNC(funcname, elt_t) \
  1365. static int \
  1366. _cmp_ ## elt_t(const void *_a, const void *_b) \
  1367. { \
  1368. const elt_t *a = _a, *b = _b; \
  1369. if (*a<*b) \
  1370. return -1; \
  1371. else if (*a>*b) \
  1372. return 1; \
  1373. else \
  1374. return 0; \
  1375. } \
  1376. elt_t \
  1377. funcname(elt_t *array, int n_elements, int nth) \
  1378. { \
  1379. tor_assert(nth >= 0); \
  1380. tor_assert(nth < n_elements); \
  1381. qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t); \
  1382. return array[nth]; \
  1383. }
  1384. IMPLEMENT_ORDER_FUNC(find_nth_int, int)
  1385. IMPLEMENT_ORDER_FUNC(find_nth_time, time_t)
  1386. IMPLEMENT_ORDER_FUNC(find_nth_double, double)
  1387. IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t)
  1388. IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t)
  1389. IMPLEMENT_ORDER_FUNC(find_nth_long, long)
  1390. /** Return a newly allocated digestset_t, optimized to hold a total of
  1391. * <b>max_elements</b> digests with a reasonably low false positive weight. */
  1392. digestset_t *
  1393. digestset_new(int max_elements)
  1394. {
  1395. /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k
  1396. * is the number of hash functions per entry, m is the bits in the array,
  1397. * and n is the number of elements inserted. For us, k==4, n<=max_elements,
  1398. * and m==n_bits= approximately max_elements*32. This gives
  1399. * P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019
  1400. *
  1401. * It would be more optimal in space vs false positives to get this false
  1402. * positive rate by going for k==13, and m==18.5n, but we also want to
  1403. * conserve CPU, and k==13 is pretty big.
  1404. */
  1405. int n_bits = 1u << (tor_log2(max_elements)+5);
  1406. digestset_t *r = tor_malloc(sizeof(digestset_t));
  1407. r->mask = n_bits - 1;
  1408. r->ba = bitarray_init_zero(n_bits);
  1409. return r;
  1410. }
  1411. /** Free all storage held in <b>set</b>. */
  1412. void
  1413. digestset_free_(digestset_t *set)
  1414. {
  1415. if (!set)
  1416. return;
  1417. bitarray_free(set->ba);
  1418. tor_free(set);
  1419. }