smartlist.c 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866
  1. /* Copyright (c) 2003-2004, Roger Dingledine
  2. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  3. * Copyright (c) 2007-2019, The Tor Project, Inc. */
  4. /* See LICENSE for licensing information */
  5. /**
  6. * \file smartlist.c
  7. *
  8. * \brief Higher-level functions for the "smartlist" resizeable array
  9. * abstraction.
  10. *
  11. * The functions declared here use higher-level functionality than those in
  12. * smartlist_core.c, and handle things like smartlists of different types,
  13. * sorting, searching, heap-structured smartlists, and other convenience
  14. * functions.
  15. **/
  16. #include "lib/container/smartlist.h"
  17. #include "lib/err/torerr.h"
  18. #include "lib/malloc/malloc.h"
  19. #include "lib/defs/digest_sizes.h"
  20. #include "lib/ctime/di_ops.h"
  21. #include "lib/string/compat_ctype.h"
  22. #include "lib/string/compat_string.h"
  23. #include "lib/string/util_string.h"
  24. #include "lib/string/printf.h"
  25. #include "lib/log/util_bug.h"
  26. #include <stdlib.h>
  27. #include <string.h>
  28. /** Append the string produced by tor_asprintf(<b>pattern</b>, <b>...</b>)
  29. * to <b>sl</b>. */
  30. void
  31. smartlist_add_asprintf(struct smartlist_t *sl, const char *pattern, ...)
  32. {
  33. va_list ap;
  34. va_start(ap, pattern);
  35. smartlist_add_vasprintf(sl, pattern, ap);
  36. va_end(ap);
  37. }
  38. /** va_list-based backend of smartlist_add_asprintf. */
  39. void
  40. smartlist_add_vasprintf(struct smartlist_t *sl, const char *pattern,
  41. va_list args)
  42. {
  43. char *str = NULL;
  44. tor_vasprintf(&str, pattern, args);
  45. tor_assert(str != NULL);
  46. smartlist_add(sl, str);
  47. }
  48. /** Reverse the order of the items in <b>sl</b>. */
  49. void
  50. smartlist_reverse(smartlist_t *sl)
  51. {
  52. int i, j;
  53. void *tmp;
  54. tor_assert(sl);
  55. for (i = 0, j = sl->num_used-1; i < j; ++i, --j) {
  56. tmp = sl->list[i];
  57. sl->list[i] = sl->list[j];
  58. sl->list[j] = tmp;
  59. }
  60. }
  61. /** If there are any strings in sl equal to element, remove and free them.
  62. * Does not preserve order. */
  63. void
  64. smartlist_string_remove(smartlist_t *sl, const char *element)
  65. {
  66. int i;
  67. tor_assert(sl);
  68. tor_assert(element);
  69. for (i = 0; i < sl->num_used; ++i) {
  70. if (!strcmp(element, sl->list[i])) {
  71. tor_free(sl->list[i]);
  72. sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
  73. i--; /* so we process the new i'th element */
  74. sl->list[sl->num_used] = NULL;
  75. }
  76. }
  77. }
  78. /** Return true iff <b>sl</b> has some element E such that
  79. * !strcmp(E,<b>element</b>)
  80. */
  81. int
  82. smartlist_contains_string(const smartlist_t *sl, const char *element)
  83. {
  84. int i;
  85. if (!sl) return 0;
  86. for (i=0; i < sl->num_used; i++)
  87. if (strcmp((const char*)sl->list[i],element)==0)
  88. return 1;
  89. return 0;
  90. }
  91. /** If <b>element</b> is equal to an element of <b>sl</b>, return that
  92. * element's index. Otherwise, return -1. */
  93. int
  94. smartlist_string_pos(const smartlist_t *sl, const char *element)
  95. {
  96. int i;
  97. if (!sl) return -1;
  98. for (i=0; i < sl->num_used; i++)
  99. if (strcmp((const char*)sl->list[i],element)==0)
  100. return i;
  101. return -1;
  102. }
  103. /** If <b>element</b> is the same pointer as an element of <b>sl</b>, return
  104. * that element's index. Otherwise, return -1. */
  105. int
  106. smartlist_pos(const smartlist_t *sl, const void *element)
  107. {
  108. int i;
  109. if (!sl) return -1;
  110. for (i=0; i < sl->num_used; i++)
  111. if (element == sl->list[i])
  112. return i;
  113. return -1;
  114. }
  115. /** Return true iff <b>sl</b> has some element E such that
  116. * !strcasecmp(E,<b>element</b>)
  117. */
  118. int
  119. smartlist_contains_string_case(const smartlist_t *sl, const char *element)
  120. {
  121. int i;
  122. if (!sl) return 0;
  123. for (i=0; i < sl->num_used; i++)
  124. if (strcasecmp((const char*)sl->list[i],element)==0)
  125. return 1;
  126. return 0;
  127. }
  128. /** Return true iff <b>sl</b> has some element E such that E is equal
  129. * to the decimal encoding of <b>num</b>.
  130. */
  131. int
  132. smartlist_contains_int_as_string(const smartlist_t *sl, int num)
  133. {
  134. char buf[32]; /* long enough for 64-bit int, and then some. */
  135. tor_snprintf(buf,sizeof(buf),"%d", num);
  136. return smartlist_contains_string(sl, buf);
  137. }
  138. /** Return true iff the two lists contain the same strings in the same
  139. * order, or if they are both NULL. */
  140. int
  141. smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2)
  142. {
  143. if (sl1 == NULL)
  144. return sl2 == NULL;
  145. if (sl2 == NULL)
  146. return 0;
  147. if (smartlist_len(sl1) != smartlist_len(sl2))
  148. return 0;
  149. SMARTLIST_FOREACH(sl1, const char *, cp1, {
  150. const char *cp2 = smartlist_get(sl2, cp1_sl_idx);
  151. if (strcmp(cp1, cp2))
  152. return 0;
  153. });
  154. return 1;
  155. }
  156. /** Return true iff the two lists contain the same int pointer values in
  157. * the same order, or if they are both NULL. */
  158. int
  159. smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2)
  160. {
  161. if (sl1 == NULL)
  162. return sl2 == NULL;
  163. if (sl2 == NULL)
  164. return 0;
  165. if (smartlist_len(sl1) != smartlist_len(sl2))
  166. return 0;
  167. SMARTLIST_FOREACH(sl1, int *, cp1, {
  168. int *cp2 = smartlist_get(sl2, cp1_sl_idx);
  169. if (*cp1 != *cp2)
  170. return 0;
  171. });
  172. return 1;
  173. }
  174. /**
  175. * Return true if there is shallow equality between smartlists -
  176. * i.e. all indices correspond to exactly same object (pointer
  177. * values are matching). Otherwise, return false.
  178. */
  179. int
  180. smartlist_ptrs_eq(const smartlist_t *s1, const smartlist_t *s2)
  181. {
  182. if (s1 == s2)
  183. return 1;
  184. // Note: pointers cannot both be NULL at this point, because
  185. // above check.
  186. if (s1 == NULL || s2 == NULL)
  187. return 0;
  188. if (smartlist_len(s1) != smartlist_len(s2))
  189. return 0;
  190. for (int i = 0; i < smartlist_len(s1); i++) {
  191. if (smartlist_get(s1, i) != smartlist_get(s2, i))
  192. return 0;
  193. }
  194. return 1;
  195. }
  196. /** Return true iff <b>sl</b> has some element E such that
  197. * tor_memeq(E,<b>element</b>,DIGEST_LEN)
  198. */
  199. int
  200. smartlist_contains_digest(const smartlist_t *sl, const char *element)
  201. {
  202. int i;
  203. if (!sl) return 0;
  204. for (i=0; i < sl->num_used; i++)
  205. if (tor_memeq((const char*)sl->list[i],element,DIGEST_LEN))
  206. return 1;
  207. return 0;
  208. }
  209. /** Return true iff some element E of sl2 has smartlist_contains(sl1,E).
  210. */
  211. int
  212. smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
  213. {
  214. int i;
  215. for (i=0; i < sl2->num_used; i++)
  216. if (smartlist_contains(sl1, sl2->list[i]))
  217. return 1;
  218. return 0;
  219. }
  220. /** Remove every element E of sl1 such that !smartlist_contains(sl2,E).
  221. * Does not preserve the order of sl1.
  222. */
  223. void
  224. smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
  225. {
  226. int i;
  227. for (i=0; i < sl1->num_used; i++)
  228. if (!smartlist_contains(sl2, sl1->list[i])) {
  229. sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */
  230. i--; /* so we process the new i'th element */
  231. sl1->list[sl1->num_used] = NULL;
  232. }
  233. }
  234. /** Remove every element E of sl1 such that smartlist_contains(sl2,E).
  235. * Does not preserve the order of sl1.
  236. */
  237. void
  238. smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
  239. {
  240. int i;
  241. for (i=0; i < sl2->num_used; i++)
  242. smartlist_remove(sl1, sl2->list[i]);
  243. }
  244. /** Allocate and return a new string containing the concatenation of
  245. * the elements of <b>sl</b>, in order, separated by <b>join</b>. If
  246. * <b>terminate</b> is true, also terminate the string with <b>join</b>.
  247. * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of
  248. * the returned string. Requires that every element of <b>sl</b> is
  249. * NUL-terminated string.
  250. */
  251. char *
  252. smartlist_join_strings(smartlist_t *sl, const char *join,
  253. int terminate, size_t *len_out)
  254. {
  255. return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out);
  256. }
  257. /** As smartlist_join_strings, but instead of separating/terminated with a
  258. * NUL-terminated string <b>join</b>, uses the <b>join_len</b>-byte sequence
  259. * at <b>join</b>. (Useful for generating a sequence of NUL-terminated
  260. * strings.)
  261. */
  262. char *
  263. smartlist_join_strings2(smartlist_t *sl, const char *join,
  264. size_t join_len, int terminate, size_t *len_out)
  265. {
  266. int i;
  267. size_t n = 0;
  268. char *r = NULL, *dst, *src;
  269. tor_assert(sl);
  270. tor_assert(join);
  271. if (terminate)
  272. n = join_len;
  273. for (i = 0; i < sl->num_used; ++i) {
  274. n += strlen(sl->list[i]);
  275. if (i+1 < sl->num_used) /* avoid double-counting the last one */
  276. n += join_len;
  277. }
  278. dst = r = tor_malloc(n+1);
  279. for (i = 0; i < sl->num_used; ) {
  280. for (src = sl->list[i]; *src; )
  281. *dst++ = *src++;
  282. if (++i < sl->num_used) {
  283. memcpy(dst, join, join_len);
  284. dst += join_len;
  285. }
  286. }
  287. if (terminate) {
  288. memcpy(dst, join, join_len);
  289. dst += join_len;
  290. }
  291. *dst = '\0';
  292. if (len_out)
  293. *len_out = dst-r;
  294. return r;
  295. }
  296. /** Sort the members of <b>sl</b> into an order defined by
  297. * the ordering function <b>compare</b>, which returns less then 0 if a
  298. * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.
  299. */
  300. void
  301. smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
  302. {
  303. if (!sl->num_used)
  304. return;
  305. qsort(sl->list, sl->num_used, sizeof(void*),
  306. (int (*)(const void *,const void*))compare);
  307. }
  308. /** Given a smartlist <b>sl</b> sorted with the function <b>compare</b>,
  309. * return the most frequent member in the list. Break ties in favor of
  310. * later elements. If the list is empty, return NULL. If count_out is
  311. * non-null, set it to the count of the most frequent member.
  312. */
  313. void *
  314. smartlist_get_most_frequent_(const smartlist_t *sl,
  315. int (*compare)(const void **a, const void **b),
  316. int *count_out)
  317. {
  318. const void *most_frequent = NULL;
  319. int most_frequent_count = 0;
  320. const void *cur = NULL;
  321. int i, count=0;
  322. if (!sl->num_used) {
  323. if (count_out)
  324. *count_out = 0;
  325. return NULL;
  326. }
  327. for (i = 0; i < sl->num_used; ++i) {
  328. const void *item = sl->list[i];
  329. if (cur && 0 == compare(&cur, &item)) {
  330. ++count;
  331. } else {
  332. if (cur && count >= most_frequent_count) {
  333. most_frequent = cur;
  334. most_frequent_count = count;
  335. }
  336. cur = item;
  337. count = 1;
  338. }
  339. }
  340. if (cur && count >= most_frequent_count) {
  341. most_frequent = cur;
  342. most_frequent_count = count;
  343. }
  344. if (count_out)
  345. *count_out = most_frequent_count;
  346. return (void*)most_frequent;
  347. }
  348. /** Given a sorted smartlist <b>sl</b> and the comparison function used to
  349. * sort it, remove all duplicate members. If free_fn is provided, calls
  350. * free_fn on each duplicate. Otherwise, just removes them. Preserves order.
  351. */
  352. void
  353. smartlist_uniq(smartlist_t *sl,
  354. int (*compare)(const void **a, const void **b),
  355. void (*free_fn)(void *a))
  356. {
  357. int i;
  358. for (i=1; i < sl->num_used; ++i) {
  359. if (compare((const void **)&(sl->list[i-1]),
  360. (const void **)&(sl->list[i])) == 0) {
  361. if (free_fn)
  362. free_fn(sl->list[i]);
  363. smartlist_del_keeporder(sl, i--);
  364. }
  365. }
  366. }
  367. /** Assuming the members of <b>sl</b> are in order, return a pointer to the
  368. * member that matches <b>key</b>. Ordering and matching are defined by a
  369. * <b>compare</b> function that returns 0 on a match; less than 0 if key is
  370. * less than member, and greater than 0 if key is greater then member.
  371. */
  372. void *
  373. smartlist_bsearch(const smartlist_t *sl, const void *key,
  374. int (*compare)(const void *key, const void **member))
  375. {
  376. int found, idx;
  377. idx = smartlist_bsearch_idx(sl, key, compare, &found);
  378. return found ? smartlist_get(sl, idx) : NULL;
  379. }
  380. /** Assuming the members of <b>sl</b> are in order, return the index of the
  381. * member that matches <b>key</b>. If no member matches, return the index of
  382. * the first member greater than <b>key</b>, or smartlist_len(sl) if no member
  383. * is greater than <b>key</b>. Set <b>found_out</b> to true on a match, to
  384. * false otherwise. Ordering and matching are defined by a <b>compare</b>
  385. * function that returns 0 on a match; less than 0 if key is less than member,
  386. * and greater than 0 if key is greater then member.
  387. */
  388. int
  389. smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
  390. int (*compare)(const void *key, const void **member),
  391. int *found_out)
  392. {
  393. int hi, lo, cmp, mid, len, diff;
  394. tor_assert(sl);
  395. tor_assert(compare);
  396. tor_assert(found_out);
  397. len = smartlist_len(sl);
  398. /* Check for the trivial case of a zero-length list */
  399. if (len == 0) {
  400. *found_out = 0;
  401. /* We already know smartlist_len(sl) is 0 in this case */
  402. return 0;
  403. }
  404. /* Okay, we have a real search to do */
  405. tor_assert(len > 0);
  406. lo = 0;
  407. hi = len - 1;
  408. /*
  409. * These invariants are always true:
  410. *
  411. * For all i such that 0 <= i < lo, sl[i] < key
  412. * For all i such that hi < i <= len, sl[i] > key
  413. */
  414. while (lo <= hi) {
  415. diff = hi - lo;
  416. /*
  417. * We want mid = (lo + hi) / 2, but that could lead to overflow, so
  418. * instead diff = hi - lo (non-negative because of loop condition), and
  419. * then hi = lo + diff, mid = (lo + lo + diff) / 2 = lo + (diff / 2).
  420. */
  421. mid = lo + (diff / 2);
  422. cmp = compare(key, (const void**) &(sl->list[mid]));
  423. if (cmp == 0) {
  424. /* sl[mid] == key; we found it */
  425. *found_out = 1;
  426. return mid;
  427. } else if (cmp > 0) {
  428. /*
  429. * key > sl[mid] and an index i such that sl[i] == key must
  430. * have i > mid if it exists.
  431. */
  432. /*
  433. * Since lo <= mid <= hi, hi can only decrease on each iteration (by
  434. * being set to mid - 1) and hi is initially len - 1, mid < len should
  435. * always hold, and this is not symmetric with the left end of list
  436. * mid > 0 test below. A key greater than the right end of the list
  437. * should eventually lead to lo == hi == mid == len - 1, and then
  438. * we set lo to len below and fall out to the same exit we hit for
  439. * a key in the middle of the list but not matching. Thus, we just
  440. * assert for consistency here rather than handle a mid == len case.
  441. */
  442. tor_assert(mid < len);
  443. /* Move lo to the element immediately after sl[mid] */
  444. lo = mid + 1;
  445. } else {
  446. /* This should always be true in this case */
  447. tor_assert(cmp < 0);
  448. /*
  449. * key < sl[mid] and an index i such that sl[i] == key must
  450. * have i < mid if it exists.
  451. */
  452. if (mid > 0) {
  453. /* Normal case, move hi to the element immediately before sl[mid] */
  454. hi = mid - 1;
  455. } else {
  456. /* These should always be true in this case */
  457. tor_assert(mid == lo);
  458. tor_assert(mid == 0);
  459. /*
  460. * We were at the beginning of the list and concluded that every
  461. * element e compares e > key.
  462. */
  463. *found_out = 0;
  464. return 0;
  465. }
  466. }
  467. }
  468. /*
  469. * lo > hi; we have no element matching key but we have elements falling
  470. * on both sides of it. The lo index points to the first element > key.
  471. */
  472. tor_assert(lo == hi + 1); /* All other cases should have been handled */
  473. tor_assert(lo >= 0);
  474. tor_assert(lo <= len);
  475. tor_assert(hi >= 0);
  476. tor_assert(hi <= len);
  477. if (lo < len) {
  478. cmp = compare(key, (const void **) &(sl->list[lo]));
  479. tor_assert(cmp < 0);
  480. } else {
  481. cmp = compare(key, (const void **) &(sl->list[len-1]));
  482. tor_assert(cmp > 0);
  483. }
  484. *found_out = 0;
  485. return lo;
  486. }
  487. /** Helper: compare two const char **s. */
  488. static int
  489. compare_string_ptrs_(const void **_a, const void **_b)
  490. {
  491. return strcmp((const char*)*_a, (const char*)*_b);
  492. }
  493. /** Sort a smartlist <b>sl</b> containing strings into lexically ascending
  494. * order. */
  495. void
  496. smartlist_sort_strings(smartlist_t *sl)
  497. {
  498. smartlist_sort(sl, compare_string_ptrs_);
  499. }
  500. /** Return the most frequent string in the sorted list <b>sl</b> */
  501. const char *
  502. smartlist_get_most_frequent_string(smartlist_t *sl)
  503. {
  504. return smartlist_get_most_frequent(sl, compare_string_ptrs_);
  505. }
  506. /** Return the most frequent string in the sorted list <b>sl</b>.
  507. * If <b>count_out</b> is provided, set <b>count_out</b> to the
  508. * number of times that string appears.
  509. */
  510. const char *
  511. smartlist_get_most_frequent_string_(smartlist_t *sl, int *count_out)
  512. {
  513. return smartlist_get_most_frequent_(sl, compare_string_ptrs_, count_out);
  514. }
  515. /** Remove duplicate strings from a sorted list, and free them with tor_free().
  516. */
  517. void
  518. smartlist_uniq_strings(smartlist_t *sl)
  519. {
  520. smartlist_uniq(sl, compare_string_ptrs_, tor_free_);
  521. }
  522. /** Helper: compare two pointers. */
  523. static int
  524. compare_ptrs_(const void **_a, const void **_b)
  525. {
  526. const void *a = *_a, *b = *_b;
  527. if (a<b)
  528. return -1;
  529. else if (a==b)
  530. return 0;
  531. else
  532. return 1;
  533. }
  534. /** Sort <b>sl</b> in ascending order of the pointers it contains. */
  535. void
  536. smartlist_sort_pointers(smartlist_t *sl)
  537. {
  538. smartlist_sort(sl, compare_ptrs_);
  539. }
  540. /* Heap-based priority queue implementation for O(lg N) insert and remove.
  541. * Recall that the heap property is that, for every index I, h[I] <
  542. * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
  543. *
  544. * For us to remove items other than the topmost item, each item must store
  545. * its own index within the heap. When calling the pqueue functions, tell
  546. * them about the offset of the field that stores the index within the item.
  547. *
  548. * Example:
  549. *
  550. * typedef struct timer_t {
  551. * struct timeval tv;
  552. * int heap_index;
  553. * } timer_t;
  554. *
  555. * static int compare(const void *p1, const void *p2) {
  556. * const timer_t *t1 = p1, *t2 = p2;
  557. * if (t1->tv.tv_sec < t2->tv.tv_sec) {
  558. * return -1;
  559. * } else if (t1->tv.tv_sec > t2->tv.tv_sec) {
  560. * return 1;
  561. * } else {
  562. * return t1->tv.tv_usec - t2->tv_usec;
  563. * }
  564. * }
  565. *
  566. * void timer_heap_insert(smartlist_t *heap, timer_t *timer) {
  567. * smartlist_pqueue_add(heap, compare, offsetof(timer_t, heap_index),
  568. * timer);
  569. * }
  570. *
  571. * void timer_heap_pop(smartlist_t *heap) {
  572. * return smartlist_pqueue_pop(heap, compare,
  573. * offsetof(timer_t, heap_index));
  574. * }
  575. */
  576. /** @{ */
  577. /** Functions to manipulate heap indices to find a node's parent and children.
  578. *
  579. * For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x]
  580. * = 2*x + 1. But this is C, so we have to adjust a little. */
  581. /* MAX_PARENT_IDX is the largest IDX in the smartlist which might have
  582. * children whose indices fit inside an int.
  583. * LEFT_CHILD(MAX_PARENT_IDX) == INT_MAX-2;
  584. * RIGHT_CHILD(MAX_PARENT_IDX) == INT_MAX-1;
  585. * LEFT_CHILD(MAX_PARENT_IDX + 1) == INT_MAX // impossible, see max list size.
  586. */
  587. #define MAX_PARENT_IDX ((INT_MAX - 2) / 2)
  588. /* If this is true, then i is small enough to potentially have children
  589. * in the smartlist, and it is save to use LEFT_CHILD/RIGHT_CHILD on it. */
  590. #define IDX_MAY_HAVE_CHILDREN(i) ((i) <= MAX_PARENT_IDX)
  591. #define LEFT_CHILD(i) ( 2*(i) + 1 )
  592. #define RIGHT_CHILD(i) ( 2*(i) + 2 )
  593. #define PARENT(i) ( ((i)-1) / 2 )
  594. /** }@ */
  595. /** @{ */
  596. /** Helper macros for heaps: Given a local variable <b>idx_field_offset</b>
  597. * set to the offset of an integer index within the heap element structure,
  598. * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to
  599. * where p's index is stored. Given additionally a local smartlist <b>sl</b>,
  600. * UPDATE_IDX(i) sets the index of the element at <b>i</b> to the correct
  601. * value (that is, to <b>i</b>).
  602. */
  603. #define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset))
  604. #define UPDATE_IDX(i) do { \
  605. void *updated = sl->list[i]; \
  606. *IDXP(updated) = i; \
  607. } while (0)
  608. #define IDX_OF_ITEM(p) (*IDXP(p))
  609. /** @} */
  610. /** Helper. <b>sl</b> may have at most one violation of the heap property:
  611. * the item at <b>idx</b> may be greater than one or both of its children.
  612. * Restore the heap property. */
  613. static inline void
  614. smartlist_heapify(smartlist_t *sl,
  615. int (*compare)(const void *a, const void *b),
  616. int idx_field_offset,
  617. int idx)
  618. {
  619. while (1) {
  620. if (! IDX_MAY_HAVE_CHILDREN(idx)) {
  621. /* idx is so large that it cannot have any children, since doing so
  622. * would mean the smartlist was over-capacity. Therefore it cannot
  623. * violate the heap property by being greater than a child (since it
  624. * doesn't have any). */
  625. return;
  626. }
  627. int left_idx = LEFT_CHILD(idx);
  628. int best_idx;
  629. if (left_idx >= sl->num_used)
  630. return;
  631. if (compare(sl->list[idx],sl->list[left_idx]) < 0)
  632. best_idx = idx;
  633. else
  634. best_idx = left_idx;
  635. if (left_idx+1 < sl->num_used &&
  636. compare(sl->list[left_idx+1],sl->list[best_idx]) < 0)
  637. best_idx = left_idx + 1;
  638. if (best_idx == idx) {
  639. return;
  640. } else {
  641. void *tmp = sl->list[idx];
  642. sl->list[idx] = sl->list[best_idx];
  643. sl->list[best_idx] = tmp;
  644. UPDATE_IDX(idx);
  645. UPDATE_IDX(best_idx);
  646. idx = best_idx;
  647. }
  648. }
  649. }
  650. /** Insert <b>item</b> into the heap stored in <b>sl</b>, where order is
  651. * determined by <b>compare</b> and the offset of the item in the heap is
  652. * stored in an int-typed field at position <b>idx_field_offset</b> within
  653. * item.
  654. */
  655. void
  656. smartlist_pqueue_add(smartlist_t *sl,
  657. int (*compare)(const void *a, const void *b),
  658. int idx_field_offset,
  659. void *item)
  660. {
  661. int idx;
  662. smartlist_add(sl,item);
  663. UPDATE_IDX(sl->num_used-1);
  664. for (idx = sl->num_used - 1; idx; ) {
  665. int parent = PARENT(idx);
  666. if (compare(sl->list[idx], sl->list[parent]) < 0) {
  667. void *tmp = sl->list[parent];
  668. sl->list[parent] = sl->list[idx];
  669. sl->list[idx] = tmp;
  670. UPDATE_IDX(parent);
  671. UPDATE_IDX(idx);
  672. idx = parent;
  673. } else {
  674. return;
  675. }
  676. }
  677. }
  678. /** Remove and return the top-priority item from the heap stored in <b>sl</b>,
  679. * where order is determined by <b>compare</b> and the item's position is
  680. * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must
  681. * not be empty. */
  682. void *
  683. smartlist_pqueue_pop(smartlist_t *sl,
  684. int (*compare)(const void *a, const void *b),
  685. int idx_field_offset)
  686. {
  687. void *top;
  688. tor_assert(sl->num_used);
  689. top = sl->list[0];
  690. *IDXP(top)=-1;
  691. if (--sl->num_used) {
  692. sl->list[0] = sl->list[sl->num_used];
  693. sl->list[sl->num_used] = NULL;
  694. UPDATE_IDX(0);
  695. smartlist_heapify(sl, compare, idx_field_offset, 0);
  696. }
  697. sl->list[sl->num_used] = NULL;
  698. return top;
  699. }
  700. /** Remove the item <b>item</b> from the heap stored in <b>sl</b>,
  701. * where order is determined by <b>compare</b> and the item's position is
  702. * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must
  703. * not be empty. */
  704. void
  705. smartlist_pqueue_remove(smartlist_t *sl,
  706. int (*compare)(const void *a, const void *b),
  707. int idx_field_offset,
  708. void *item)
  709. {
  710. int idx = IDX_OF_ITEM(item);
  711. tor_assert(idx >= 0);
  712. tor_assert(sl->list[idx] == item);
  713. --sl->num_used;
  714. *IDXP(item) = -1;
  715. if (idx == sl->num_used) {
  716. sl->list[sl->num_used] = NULL;
  717. return;
  718. } else {
  719. sl->list[idx] = sl->list[sl->num_used];
  720. sl->list[sl->num_used] = NULL;
  721. UPDATE_IDX(idx);
  722. smartlist_heapify(sl, compare, idx_field_offset, idx);
  723. }
  724. }
  725. /** Assert that the heap property is correctly maintained by the heap stored
  726. * in <b>sl</b>, where order is determined by <b>compare</b>. */
  727. void
  728. smartlist_pqueue_assert_ok(smartlist_t *sl,
  729. int (*compare)(const void *a, const void *b),
  730. int idx_field_offset)
  731. {
  732. int i;
  733. for (i = sl->num_used - 1; i >= 0; --i) {
  734. if (i>0)
  735. tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
  736. tor_assert(IDX_OF_ITEM(sl->list[i]) == i);
  737. }
  738. }
  739. /** Helper: compare two DIGEST_LEN digests. */
  740. static int
  741. compare_digests_(const void **_a, const void **_b)
  742. {
  743. return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
  744. }
  745. /** Sort the list of DIGEST_LEN-byte digests into ascending order. */
  746. void
  747. smartlist_sort_digests(smartlist_t *sl)
  748. {
  749. smartlist_sort(sl, compare_digests_);
  750. }
  751. /** Remove duplicate digests from a sorted list, and free them with tor_free().
  752. */
  753. void
  754. smartlist_uniq_digests(smartlist_t *sl)
  755. {
  756. smartlist_uniq(sl, compare_digests_, tor_free_);
  757. }
  758. /** Helper: compare two DIGEST256_LEN digests. */
  759. static int
  760. compare_digests256_(const void **_a, const void **_b)
  761. {
  762. return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN);
  763. }
  764. /** Sort the list of DIGEST256_LEN-byte digests into ascending order. */
  765. void
  766. smartlist_sort_digests256(smartlist_t *sl)
  767. {
  768. smartlist_sort(sl, compare_digests256_);
  769. }
  770. /** Return the most frequent member of the sorted list of DIGEST256_LEN
  771. * digests in <b>sl</b> */
  772. const uint8_t *
  773. smartlist_get_most_frequent_digest256(smartlist_t *sl)
  774. {
  775. return smartlist_get_most_frequent(sl, compare_digests256_);
  776. }
  777. /** Remove duplicate 256-bit digests from a sorted list, and free them with
  778. * tor_free().
  779. */
  780. void
  781. smartlist_uniq_digests256(smartlist_t *sl)
  782. {
  783. smartlist_uniq(sl, compare_digests256_, tor_free_);
  784. }