container.c 52 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517
  1. /* Copyright (c) 2003-2004, Roger Dingledine
  2. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  3. * Copyright (c) 2007-2016, 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 count of 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. /* MAX_PARENT_IDX is the largest IDX in the smartlist which might have
  769. * children whose indices fit inside an int.
  770. * LEFT_CHILD(MAX_PARENT_IDX) == INT_MAX-2;
  771. * RIGHT_CHILD(MAX_PARENT_IDX) == INT_MAX-1;
  772. * LEFT_CHILD(MAX_PARENT_IDX + 1) == INT_MAX // impossible, see max list size.
  773. */
  774. #define MAX_PARENT_IDX ((INT_MAX - 2) / 2)
  775. /* If this is true, then i is small enough to potentially have children
  776. * in the smartlist, and it is save to use LEFT_CHILD/RIGHT_CHILD on it. */
  777. #define IDX_MAY_HAVE_CHILDREN(i) ((i) <= MAX_PARENT_IDX)
  778. #define LEFT_CHILD(i) ( 2*(i) + 1 )
  779. #define RIGHT_CHILD(i) ( 2*(i) + 2 )
  780. #define PARENT(i) ( ((i)-1) / 2 )
  781. /** }@ */
  782. /** @{ */
  783. /** Helper macros for heaps: Given a local variable <b>idx_field_offset</b>
  784. * set to the offset of an integer index within the heap element structure,
  785. * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to
  786. * where p's index is stored. Given additionally a local smartlist <b>sl</b>,
  787. * UPDATE_IDX(i) sets the index of the element at <b>i</b> to the correct
  788. * value (that is, to <b>i</b>).
  789. */
  790. #define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset))
  791. #define UPDATE_IDX(i) do { \
  792. void *updated = sl->list[i]; \
  793. *IDXP(updated) = i; \
  794. } while (0)
  795. #define IDX_OF_ITEM(p) (*IDXP(p))
  796. /** @} */
  797. /** Helper. <b>sl</b> may have at most one violation of the heap property:
  798. * the item at <b>idx</b> may be greater than one or both of its children.
  799. * Restore the heap property. */
  800. static inline void
  801. smartlist_heapify(smartlist_t *sl,
  802. int (*compare)(const void *a, const void *b),
  803. int idx_field_offset,
  804. int idx)
  805. {
  806. while (1) {
  807. if (! IDX_MAY_HAVE_CHILDREN(idx)) {
  808. /* idx is so large that it cannot have any children, since doing so
  809. * would mean the smartlist was over-capacity. Therefore it cannot
  810. * violate the heap property by being greater than a child (since it
  811. * doesn't have any). */
  812. return;
  813. }
  814. int left_idx = LEFT_CHILD(idx);
  815. int best_idx;
  816. if (left_idx >= sl->num_used)
  817. return;
  818. if (compare(sl->list[idx],sl->list[left_idx]) < 0)
  819. best_idx = idx;
  820. else
  821. best_idx = left_idx;
  822. if (left_idx+1 < sl->num_used &&
  823. compare(sl->list[left_idx+1],sl->list[best_idx]) < 0)
  824. best_idx = left_idx + 1;
  825. if (best_idx == idx) {
  826. return;
  827. } else {
  828. void *tmp = sl->list[idx];
  829. sl->list[idx] = sl->list[best_idx];
  830. sl->list[best_idx] = tmp;
  831. UPDATE_IDX(idx);
  832. UPDATE_IDX(best_idx);
  833. idx = best_idx;
  834. }
  835. }
  836. }
  837. /** Insert <b>item</b> into the heap stored in <b>sl</b>, where order is
  838. * determined by <b>compare</b> and the offset of the item in the heap is
  839. * stored in an int-typed field at position <b>idx_field_offset</b> within
  840. * item.
  841. */
  842. void
  843. smartlist_pqueue_add(smartlist_t *sl,
  844. int (*compare)(const void *a, const void *b),
  845. int idx_field_offset,
  846. void *item)
  847. {
  848. int idx;
  849. smartlist_add(sl,item);
  850. UPDATE_IDX(sl->num_used-1);
  851. for (idx = sl->num_used - 1; idx; ) {
  852. int parent = PARENT(idx);
  853. if (compare(sl->list[idx], sl->list[parent]) < 0) {
  854. void *tmp = sl->list[parent];
  855. sl->list[parent] = sl->list[idx];
  856. sl->list[idx] = tmp;
  857. UPDATE_IDX(parent);
  858. UPDATE_IDX(idx);
  859. idx = parent;
  860. } else {
  861. return;
  862. }
  863. }
  864. }
  865. /** Remove and return the top-priority item from the heap stored in <b>sl</b>,
  866. * where order is determined by <b>compare</b> and the item's position is
  867. * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must
  868. * not be empty. */
  869. void *
  870. smartlist_pqueue_pop(smartlist_t *sl,
  871. int (*compare)(const void *a, const void *b),
  872. int idx_field_offset)
  873. {
  874. void *top;
  875. tor_assert(sl->num_used);
  876. top = sl->list[0];
  877. *IDXP(top)=-1;
  878. if (--sl->num_used) {
  879. sl->list[0] = sl->list[sl->num_used];
  880. sl->list[sl->num_used] = NULL;
  881. UPDATE_IDX(0);
  882. smartlist_heapify(sl, compare, idx_field_offset, 0);
  883. }
  884. sl->list[sl->num_used] = NULL;
  885. return top;
  886. }
  887. /** Remove the item <b>item</b> from the heap stored in <b>sl</b>,
  888. * where order is determined by <b>compare</b> and the item's position is
  889. * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must
  890. * not be empty. */
  891. void
  892. smartlist_pqueue_remove(smartlist_t *sl,
  893. int (*compare)(const void *a, const void *b),
  894. int idx_field_offset,
  895. void *item)
  896. {
  897. int idx = IDX_OF_ITEM(item);
  898. tor_assert(idx >= 0);
  899. tor_assert(sl->list[idx] == item);
  900. --sl->num_used;
  901. *IDXP(item) = -1;
  902. if (idx == sl->num_used) {
  903. sl->list[sl->num_used] = NULL;
  904. return;
  905. } else {
  906. sl->list[idx] = sl->list[sl->num_used];
  907. sl->list[sl->num_used] = NULL;
  908. UPDATE_IDX(idx);
  909. smartlist_heapify(sl, compare, idx_field_offset, idx);
  910. }
  911. }
  912. /** Assert that the heap property is correctly maintained by the heap stored
  913. * in <b>sl</b>, where order is determined by <b>compare</b>. */
  914. void
  915. smartlist_pqueue_assert_ok(smartlist_t *sl,
  916. int (*compare)(const void *a, const void *b),
  917. int idx_field_offset)
  918. {
  919. int i;
  920. for (i = sl->num_used - 1; i >= 0; --i) {
  921. if (i>0)
  922. tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
  923. tor_assert(IDX_OF_ITEM(sl->list[i]) == i);
  924. }
  925. }
  926. /** Helper: compare two DIGEST_LEN digests. */
  927. static int
  928. compare_digests_(const void **_a, const void **_b)
  929. {
  930. return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
  931. }
  932. /** Sort the list of DIGEST_LEN-byte digests into ascending order. */
  933. void
  934. smartlist_sort_digests(smartlist_t *sl)
  935. {
  936. smartlist_sort(sl, compare_digests_);
  937. }
  938. /** Remove duplicate digests from a sorted list, and free them with tor_free().
  939. */
  940. void
  941. smartlist_uniq_digests(smartlist_t *sl)
  942. {
  943. smartlist_uniq(sl, compare_digests_, tor_free_);
  944. }
  945. /** Helper: compare two DIGEST256_LEN digests. */
  946. static int
  947. compare_digests256_(const void **_a, const void **_b)
  948. {
  949. return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN);
  950. }
  951. /** Sort the list of DIGEST256_LEN-byte digests into ascending order. */
  952. void
  953. smartlist_sort_digests256(smartlist_t *sl)
  954. {
  955. smartlist_sort(sl, compare_digests256_);
  956. }
  957. /** Return the most frequent member of the sorted list of DIGEST256_LEN
  958. * digests in <b>sl</b> */
  959. const uint8_t *
  960. smartlist_get_most_frequent_digest256(smartlist_t *sl)
  961. {
  962. return smartlist_get_most_frequent(sl, compare_digests256_);
  963. }
  964. /** Remove duplicate 256-bit digests from a sorted list, and free them with
  965. * tor_free().
  966. */
  967. void
  968. smartlist_uniq_digests256(smartlist_t *sl)
  969. {
  970. smartlist_uniq(sl, compare_digests256_, tor_free_);
  971. }
  972. /** Helper: Declare an entry type and a map type to implement a mapping using
  973. * ht.h. The map type will be called <b>maptype</b>. The key part of each
  974. * entry is declared using the C declaration <b>keydecl</b>. All functions
  975. * and types associated with the map get prefixed with <b>prefix</b> */
  976. #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \
  977. typedef struct prefix ## entry_t { \
  978. HT_ENTRY(prefix ## entry_t) node; \
  979. void *val; \
  980. keydecl; \
  981. } prefix ## entry_t; \
  982. struct maptype { \
  983. HT_HEAD(prefix ## impl, prefix ## entry_t) head; \
  984. }
  985. DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
  986. DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
  987. DEFINE_MAP_STRUCTS(digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_);
  988. /** Helper: compare strmap_entry_t objects by key value. */
  989. static inline int
  990. strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
  991. {
  992. return !strcmp(a->key, b->key);
  993. }
  994. /** Helper: return a hash value for a strmap_entry_t. */
  995. static inline unsigned int
  996. strmap_entry_hash(const strmap_entry_t *a)
  997. {
  998. return (unsigned) siphash24g(a->key, strlen(a->key));
  999. }
  1000. /** Helper: compare digestmap_entry_t objects by key value. */
  1001. static inline int
  1002. digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
  1003. {
  1004. return tor_memeq(a->key, b->key, DIGEST_LEN);
  1005. }
  1006. /** Helper: return a hash value for a digest_map_t. */
  1007. static inline unsigned int
  1008. digestmap_entry_hash(const digestmap_entry_t *a)
  1009. {
  1010. return (unsigned) siphash24g(a->key, DIGEST_LEN);
  1011. }
  1012. /** Helper: compare digestmap_entry_t objects by key value. */
  1013. static inline int
  1014. digest256map_entries_eq(const digest256map_entry_t *a,
  1015. const digest256map_entry_t *b)
  1016. {
  1017. return tor_memeq(a->key, b->key, DIGEST256_LEN);
  1018. }
  1019. /** Helper: return a hash value for a digest_map_t. */
  1020. static inline unsigned int
  1021. digest256map_entry_hash(const digest256map_entry_t *a)
  1022. {
  1023. return (unsigned) siphash24g(a->key, DIGEST256_LEN);
  1024. }
  1025. HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
  1026. strmap_entries_eq)
  1027. HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
  1028. strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_)
  1029. HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
  1030. digestmap_entries_eq)
  1031. HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
  1032. digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_)
  1033. HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node,
  1034. digest256map_entry_hash,
  1035. digest256map_entries_eq)
  1036. HT_GENERATE2(digest256map_impl, digest256map_entry_t, node,
  1037. digest256map_entry_hash,
  1038. digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_)
  1039. static inline void
  1040. strmap_entry_free(strmap_entry_t *ent)
  1041. {
  1042. tor_free(ent->key);
  1043. tor_free(ent);
  1044. }
  1045. static inline void
  1046. digestmap_entry_free(digestmap_entry_t *ent)
  1047. {
  1048. tor_free(ent);
  1049. }
  1050. static inline void
  1051. digest256map_entry_free(digest256map_entry_t *ent)
  1052. {
  1053. tor_free(ent);
  1054. }
  1055. static inline void
  1056. strmap_assign_tmp_key(strmap_entry_t *ent, const char *key)
  1057. {
  1058. ent->key = (char*)key;
  1059. }
  1060. static inline void
  1061. digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key)
  1062. {
  1063. memcpy(ent->key, key, DIGEST_LEN);
  1064. }
  1065. static inline void
  1066. digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key)
  1067. {
  1068. memcpy(ent->key, key, DIGEST256_LEN);
  1069. }
  1070. static inline void
  1071. strmap_assign_key(strmap_entry_t *ent, const char *key)
  1072. {
  1073. ent->key = tor_strdup(key);
  1074. }
  1075. static inline void
  1076. digestmap_assign_key(digestmap_entry_t *ent, const char *key)
  1077. {
  1078. memcpy(ent->key, key, DIGEST_LEN);
  1079. }
  1080. static inline void
  1081. digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key)
  1082. {
  1083. memcpy(ent->key, key, DIGEST256_LEN);
  1084. }
  1085. /**
  1086. * Macro: implement all the functions for a map that are declared in
  1087. * container.h by the DECLARE_MAP_FNS() macro. You must additionally define a
  1088. * prefix_entry_free_() function to free entries (and their keys), a
  1089. * prefix_assign_tmp_key() function to temporarily set a stack-allocated
  1090. * entry to hold a key, and a prefix_assign_key() function to set a
  1091. * heap-allocated entry to hold a key.
  1092. */
  1093. #define IMPLEMENT_MAP_FNS(maptype, keytype, prefix) \
  1094. /** Create and return a new empty map. */ \
  1095. MOCK_IMPL(maptype *, \
  1096. prefix##_new,(void)) \
  1097. { \
  1098. maptype *result; \
  1099. result = tor_malloc(sizeof(maptype)); \
  1100. HT_INIT(prefix##_impl, &result->head); \
  1101. return result; \
  1102. } \
  1103. \
  1104. /** Return the item from <b>map</b> whose key matches <b>key</b>, or \
  1105. * NULL if no such value exists. */ \
  1106. void * \
  1107. prefix##_get(const maptype *map, const keytype key) \
  1108. { \
  1109. prefix ##_entry_t *resolve; \
  1110. prefix ##_entry_t search; \
  1111. tor_assert(map); \
  1112. tor_assert(key); \
  1113. prefix ##_assign_tmp_key(&search, key); \
  1114. resolve = HT_FIND(prefix ##_impl, &map->head, &search); \
  1115. if (resolve) { \
  1116. return resolve->val; \
  1117. } else { \
  1118. return NULL; \
  1119. } \
  1120. } \
  1121. \
  1122. /** Add an entry to <b>map</b> mapping <b>key</b> to <b>val</b>; \
  1123. * return the previous value, or NULL if no such value existed. */ \
  1124. void * \
  1125. prefix##_set(maptype *map, const keytype key, void *val) \
  1126. { \
  1127. prefix##_entry_t search; \
  1128. void *oldval; \
  1129. tor_assert(map); \
  1130. tor_assert(key); \
  1131. tor_assert(val); \
  1132. prefix##_assign_tmp_key(&search, key); \
  1133. /* We a lot of our time in this function, so the code below is */ \
  1134. /* meant to optimize the check/alloc/set cycle by avoiding the two */\
  1135. /* trips to the hash table that we would do in the unoptimized */ \
  1136. /* version of this code. (Each of HT_INSERT and HT_FIND calls */ \
  1137. /* HT_SET_HASH and HT_FIND_P.) */ \
  1138. HT_FIND_OR_INSERT_(prefix##_impl, node, prefix##_entry_hash, \
  1139. &(map->head), \
  1140. prefix##_entry_t, &search, ptr, \
  1141. { \
  1142. /* we found an entry. */ \
  1143. oldval = (*ptr)->val; \
  1144. (*ptr)->val = val; \
  1145. return oldval; \
  1146. }, \
  1147. { \
  1148. /* We didn't find the entry. */ \
  1149. prefix##_entry_t *newent = \
  1150. tor_malloc_zero(sizeof(prefix##_entry_t)); \
  1151. prefix##_assign_key(newent, key); \
  1152. newent->val = val; \
  1153. HT_FOI_INSERT_(node, &(map->head), \
  1154. &search, newent, ptr); \
  1155. return NULL; \
  1156. }); \
  1157. } \
  1158. \
  1159. /** Remove the value currently associated with <b>key</b> from the map. \
  1160. * Return the value if one was set, or NULL if there was no entry for \
  1161. * <b>key</b>. \
  1162. * \
  1163. * Note: you must free any storage associated with the returned value. \
  1164. */ \
  1165. void * \
  1166. prefix##_remove(maptype *map, const keytype key) \
  1167. { \
  1168. prefix##_entry_t *resolve; \
  1169. prefix##_entry_t search; \
  1170. void *oldval; \
  1171. tor_assert(map); \
  1172. tor_assert(key); \
  1173. prefix##_assign_tmp_key(&search, key); \
  1174. resolve = HT_REMOVE(prefix##_impl, &map->head, &search); \
  1175. if (resolve) { \
  1176. oldval = resolve->val; \
  1177. prefix##_entry_free(resolve); \
  1178. return oldval; \
  1179. } else { \
  1180. return NULL; \
  1181. } \
  1182. } \
  1183. \
  1184. /** Return the number of elements in <b>map</b>. */ \
  1185. int \
  1186. prefix##_size(const maptype *map) \
  1187. { \
  1188. return HT_SIZE(&map->head); \
  1189. } \
  1190. \
  1191. /** Return true iff <b>map</b> has no entries. */ \
  1192. int \
  1193. prefix##_isempty(const maptype *map) \
  1194. { \
  1195. return HT_EMPTY(&map->head); \
  1196. } \
  1197. \
  1198. /** Assert that <b>map</b> is not corrupt. */ \
  1199. void \
  1200. prefix##_assert_ok(const maptype *map) \
  1201. { \
  1202. tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head)); \
  1203. } \
  1204. \
  1205. /** Remove all entries from <b>map</b>, and deallocate storage for \
  1206. * those entries. If free_val is provided, invoked it every value in \
  1207. * <b>map</b>. */ \
  1208. MOCK_IMPL(void, \
  1209. prefix##_free, (maptype *map, void (*free_val)(void*))) \
  1210. { \
  1211. prefix##_entry_t **ent, **next, *this; \
  1212. if (!map) \
  1213. return; \
  1214. for (ent = HT_START(prefix##_impl, &map->head); ent != NULL; \
  1215. ent = next) { \
  1216. this = *ent; \
  1217. next = HT_NEXT_RMV(prefix##_impl, &map->head, ent); \
  1218. if (free_val) \
  1219. free_val(this->val); \
  1220. prefix##_entry_free(this); \
  1221. } \
  1222. tor_assert(HT_EMPTY(&map->head)); \
  1223. HT_CLEAR(prefix##_impl, &map->head); \
  1224. tor_free(map); \
  1225. } \
  1226. \
  1227. /** return an <b>iterator</b> pointer to the front of a map. \
  1228. * \
  1229. * Iterator example: \
  1230. * \
  1231. * \code \
  1232. * // uppercase values in "map", removing empty values. \
  1233. * \
  1234. * strmap_iter_t *iter; \
  1235. * const char *key; \
  1236. * void *val; \
  1237. * char *cp; \
  1238. * \
  1239. * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) { \
  1240. * strmap_iter_get(iter, &key, &val); \
  1241. * cp = (char*)val; \
  1242. * if (!*cp) { \
  1243. * iter = strmap_iter_next_rmv(map,iter); \
  1244. * free(val); \
  1245. * } else { \
  1246. * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp); \
  1247. */ \
  1248. prefix##_iter_t * \
  1249. prefix##_iter_init(maptype *map) \
  1250. { \
  1251. tor_assert(map); \
  1252. return HT_START(prefix##_impl, &map->head); \
  1253. } \
  1254. \
  1255. /** Advance <b>iter</b> a single step to the next entry, and return \
  1256. * its new value. */ \
  1257. prefix##_iter_t * \
  1258. prefix##_iter_next(maptype *map, prefix##_iter_t *iter) \
  1259. { \
  1260. tor_assert(map); \
  1261. tor_assert(iter); \
  1262. return HT_NEXT(prefix##_impl, &map->head, iter); \
  1263. } \
  1264. /** Advance <b>iter</b> a single step to the next entry, removing the \
  1265. * current entry, and return its new value. */ \
  1266. prefix##_iter_t * \
  1267. prefix##_iter_next_rmv(maptype *map, prefix##_iter_t *iter) \
  1268. { \
  1269. prefix##_entry_t *rmv; \
  1270. tor_assert(map); \
  1271. tor_assert(iter); \
  1272. tor_assert(*iter); \
  1273. rmv = *iter; \
  1274. iter = HT_NEXT_RMV(prefix##_impl, &map->head, iter); \
  1275. prefix##_entry_free(rmv); \
  1276. return iter; \
  1277. } \
  1278. /** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed \
  1279. * to by iter. */ \
  1280. void \
  1281. prefix##_iter_get(prefix##_iter_t *iter, const keytype *keyp, \
  1282. void **valp) \
  1283. { \
  1284. tor_assert(iter); \
  1285. tor_assert(*iter); \
  1286. tor_assert(keyp); \
  1287. tor_assert(valp); \
  1288. *keyp = (*iter)->key; \
  1289. *valp = (*iter)->val; \
  1290. } \
  1291. /** Return true iff <b>iter</b> has advanced past the last entry of \
  1292. * <b>map</b>. */ \
  1293. int \
  1294. prefix##_iter_done(prefix##_iter_t *iter) \
  1295. { \
  1296. return iter == NULL; \
  1297. }
  1298. IMPLEMENT_MAP_FNS(strmap_t, char *, strmap)
  1299. IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap)
  1300. IMPLEMENT_MAP_FNS(digest256map_t, uint8_t *, digest256map)
  1301. /** Same as strmap_set, but first converts <b>key</b> to lowercase. */
  1302. void *
  1303. strmap_set_lc(strmap_t *map, const char *key, void *val)
  1304. {
  1305. /* We could be a little faster by using strcasecmp instead, and a separate
  1306. * type, but I don't think it matters. */
  1307. void *v;
  1308. char *lc_key = tor_strdup(key);
  1309. tor_strlower(lc_key);
  1310. v = strmap_set(map,lc_key,val);
  1311. tor_free(lc_key);
  1312. return v;
  1313. }
  1314. /** Same as strmap_get, but first converts <b>key</b> to lowercase. */
  1315. void *
  1316. strmap_get_lc(const strmap_t *map, const char *key)
  1317. {
  1318. void *v;
  1319. char *lc_key = tor_strdup(key);
  1320. tor_strlower(lc_key);
  1321. v = strmap_get(map,lc_key);
  1322. tor_free(lc_key);
  1323. return v;
  1324. }
  1325. /** Same as strmap_remove, but first converts <b>key</b> to lowercase */
  1326. void *
  1327. strmap_remove_lc(strmap_t *map, const char *key)
  1328. {
  1329. void *v;
  1330. char *lc_key = tor_strdup(key);
  1331. tor_strlower(lc_key);
  1332. v = strmap_remove(map,lc_key);
  1333. tor_free(lc_key);
  1334. return v;
  1335. }
  1336. /** Declare a function called <b>funcname</b> that acts as a find_nth_FOO
  1337. * function for an array of type <b>elt_t</b>*.
  1338. *
  1339. * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding
  1340. * the kth element of an n-element list can be done in O(n). Then again, this
  1341. * implementation is not in critical path, and it is obviously correct. */
  1342. #define IMPLEMENT_ORDER_FUNC(funcname, elt_t) \
  1343. static int \
  1344. _cmp_ ## elt_t(const void *_a, const void *_b) \
  1345. { \
  1346. const elt_t *a = _a, *b = _b; \
  1347. if (*a<*b) \
  1348. return -1; \
  1349. else if (*a>*b) \
  1350. return 1; \
  1351. else \
  1352. return 0; \
  1353. } \
  1354. elt_t \
  1355. funcname(elt_t *array, int n_elements, int nth) \
  1356. { \
  1357. tor_assert(nth >= 0); \
  1358. tor_assert(nth < n_elements); \
  1359. qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t); \
  1360. return array[nth]; \
  1361. }
  1362. IMPLEMENT_ORDER_FUNC(find_nth_int, int)
  1363. IMPLEMENT_ORDER_FUNC(find_nth_time, time_t)
  1364. IMPLEMENT_ORDER_FUNC(find_nth_double, double)
  1365. IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t)
  1366. IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t)
  1367. IMPLEMENT_ORDER_FUNC(find_nth_long, long)
  1368. /** Return a newly allocated digestset_t, optimized to hold a total of
  1369. * <b>max_elements</b> digests with a reasonably low false positive weight. */
  1370. digestset_t *
  1371. digestset_new(int max_elements)
  1372. {
  1373. /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k
  1374. * is the number of hash functions per entry, m is the bits in the array,
  1375. * and n is the number of elements inserted. For us, k==4, n<=max_elements,
  1376. * and m==n_bits= approximately max_elements*32. This gives
  1377. * P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019
  1378. *
  1379. * It would be more optimal in space vs false positives to get this false
  1380. * positive rate by going for k==13, and m==18.5n, but we also want to
  1381. * conserve CPU, and k==13 is pretty big.
  1382. */
  1383. int n_bits = 1u << (tor_log2(max_elements)+5);
  1384. digestset_t *r = tor_malloc(sizeof(digestset_t));
  1385. r->mask = n_bits - 1;
  1386. r->ba = bitarray_init_zero(n_bits);
  1387. return r;
  1388. }
  1389. /** Free all storage held in <b>set</b>. */
  1390. void
  1391. digestset_free(digestset_t *set)
  1392. {
  1393. if (!set)
  1394. return;
  1395. bitarray_free(set->ba);
  1396. tor_free(set);
  1397. }