container.c 52 KB

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