container.c 40 KB

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