test_containers.c 41 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326
  1. /* Copyright (c) 2001-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. #include "orconfig.h"
  6. #include "core/or/or.h"
  7. #include "lib/crypt_ops/crypto_rand.h"
  8. #include "feature/dircommon/fp_pair.h"
  9. #include "test/test.h"
  10. #include "lib/container/bitarray.h"
  11. #include "lib/container/order.h"
  12. #include "lib/crypt_ops/digestset.h"
  13. /** Helper: return a tristate based on comparing the strings in *<b>a</b> and
  14. * *<b>b</b>. */
  15. static int
  16. compare_strs_(const void **a, const void **b)
  17. {
  18. const char *s1 = *a, *s2 = *b;
  19. return strcmp(s1, s2);
  20. }
  21. /** Helper: return a tristate based on comparing the strings in <b>a</b> and
  22. * *<b>b</b>. */
  23. static int
  24. compare_strs_for_bsearch_(const void *a, const void **b)
  25. {
  26. const char *s1 = a, *s2 = *b;
  27. return strcmp(s1, s2);
  28. }
  29. /** Helper: return a tristate based on comparing the strings in *<b>a</b> and
  30. * *<b>b</b>, excluding a's first character, and ignoring case. */
  31. static int
  32. cmp_without_first_(const void *a, const void **b)
  33. {
  34. const char *s1 = a, *s2 = *b;
  35. return strcasecmp(s1+1, s2);
  36. }
  37. /** Run unit tests for basic dynamic-sized array functionality. */
  38. static void
  39. test_container_smartlist_basic(void *arg)
  40. {
  41. smartlist_t *sl;
  42. char *v0 = tor_strdup("v0");
  43. char *v1 = tor_strdup("v1");
  44. char *v2 = tor_strdup("v2");
  45. char *v3 = tor_strdup("v3");
  46. char *v4 = tor_strdup("v4");
  47. char *v22 = tor_strdup("v22");
  48. char *v99 = tor_strdup("v99");
  49. char *v555 = tor_strdup("v555");
  50. /* XXXX test sort_digests, uniq_strings, uniq_digests */
  51. /* Test smartlist add, del_keeporder, insert, get. */
  52. (void)arg;
  53. sl = smartlist_new();
  54. smartlist_add(sl, v1);
  55. smartlist_add(sl, v2);
  56. smartlist_add(sl, v3);
  57. smartlist_add(sl, v4);
  58. smartlist_del_keeporder(sl, 1);
  59. smartlist_insert(sl, 1, v22);
  60. smartlist_insert(sl, 0, v0);
  61. smartlist_insert(sl, 5, v555);
  62. tt_ptr_op(v0,OP_EQ, smartlist_get(sl,0));
  63. tt_ptr_op(v1,OP_EQ, smartlist_get(sl,1));
  64. tt_ptr_op(v22,OP_EQ, smartlist_get(sl,2));
  65. tt_ptr_op(v3,OP_EQ, smartlist_get(sl,3));
  66. tt_ptr_op(v4,OP_EQ, smartlist_get(sl,4));
  67. tt_ptr_op(v555,OP_EQ, smartlist_get(sl,5));
  68. /* Try deleting in the middle. */
  69. smartlist_del(sl, 1);
  70. tt_ptr_op(v555,OP_EQ, smartlist_get(sl, 1));
  71. /* Try deleting at the end. */
  72. smartlist_del(sl, 4);
  73. tt_int_op(4,OP_EQ, smartlist_len(sl));
  74. /* test isin. */
  75. tt_assert(smartlist_contains(sl, v3));
  76. tt_assert(!smartlist_contains(sl, v99));
  77. done:
  78. smartlist_free(sl);
  79. tor_free(v0);
  80. tor_free(v1);
  81. tor_free(v2);
  82. tor_free(v3);
  83. tor_free(v4);
  84. tor_free(v22);
  85. tor_free(v99);
  86. tor_free(v555);
  87. }
  88. /** Test SMARTLIST_FOREACH_REVERSE_BEGIN loop macro */
  89. static void
  90. test_container_smartlist_foreach_reverse(void *arg)
  91. {
  92. smartlist_t *sl = smartlist_new();
  93. int i;
  94. (void) arg;
  95. /* Add integers to smartlist in increasing order */
  96. for (i=0;i<100;i++) {
  97. smartlist_add(sl, (void*)(uintptr_t)i);
  98. }
  99. /* Pop them out in reverse and test their value */
  100. SMARTLIST_FOREACH_REVERSE_BEGIN(sl, void*, k) {
  101. i--;
  102. tt_ptr_op(k, OP_EQ, (void*)(uintptr_t)i);
  103. } SMARTLIST_FOREACH_END(k);
  104. done:
  105. smartlist_free(sl);
  106. }
  107. /** Run unit tests for smartlist-of-strings functionality. */
  108. static void
  109. test_container_smartlist_strings(void *arg)
  110. {
  111. smartlist_t *sl = smartlist_new();
  112. char *cp=NULL, *cp_alloc=NULL;
  113. size_t sz;
  114. /* Test split and join */
  115. (void)arg;
  116. tt_int_op(0,OP_EQ, smartlist_len(sl));
  117. smartlist_split_string(sl, "abc", ":", 0, 0);
  118. tt_int_op(1,OP_EQ, smartlist_len(sl));
  119. tt_str_op("abc",OP_EQ, smartlist_get(sl, 0));
  120. smartlist_split_string(sl, "a::bc::", "::", 0, 0);
  121. tt_int_op(4,OP_EQ, smartlist_len(sl));
  122. tt_str_op("a",OP_EQ, smartlist_get(sl, 1));
  123. tt_str_op("bc",OP_EQ, smartlist_get(sl, 2));
  124. tt_str_op("",OP_EQ, smartlist_get(sl, 3));
  125. cp_alloc = smartlist_join_strings(sl, "", 0, NULL);
  126. tt_str_op(cp_alloc,OP_EQ, "abcabc");
  127. tor_free(cp_alloc);
  128. cp_alloc = smartlist_join_strings(sl, "!", 0, NULL);
  129. tt_str_op(cp_alloc,OP_EQ, "abc!a!bc!");
  130. tor_free(cp_alloc);
  131. cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL);
  132. tt_str_op(cp_alloc,OP_EQ, "abcXYaXYbcXY");
  133. tor_free(cp_alloc);
  134. cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL);
  135. tt_str_op(cp_alloc,OP_EQ, "abcXYaXYbcXYXY");
  136. tor_free(cp_alloc);
  137. cp_alloc = smartlist_join_strings(sl, "", 1, NULL);
  138. tt_str_op(cp_alloc,OP_EQ, "abcabc");
  139. tor_free(cp_alloc);
  140. smartlist_split_string(sl, "/def/ /ghijk", "/", 0, 0);
  141. tt_int_op(8,OP_EQ, smartlist_len(sl));
  142. tt_str_op("",OP_EQ, smartlist_get(sl, 4));
  143. tt_str_op("def",OP_EQ, smartlist_get(sl, 5));
  144. tt_str_op(" ",OP_EQ, smartlist_get(sl, 6));
  145. tt_str_op("ghijk",OP_EQ, smartlist_get(sl, 7));
  146. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  147. smartlist_clear(sl);
  148. smartlist_split_string(sl, "a,bbd,cdef", ",", SPLIT_SKIP_SPACE, 0);
  149. tt_int_op(3,OP_EQ, smartlist_len(sl));
  150. tt_str_op("a",OP_EQ, smartlist_get(sl,0));
  151. tt_str_op("bbd",OP_EQ, smartlist_get(sl,1));
  152. tt_str_op("cdef",OP_EQ, smartlist_get(sl,2));
  153. smartlist_split_string(sl, " z <> zhasd <> <> bnud<> ", "<>",
  154. SPLIT_SKIP_SPACE, 0);
  155. tt_int_op(8,OP_EQ, smartlist_len(sl));
  156. tt_str_op("z",OP_EQ, smartlist_get(sl,3));
  157. tt_str_op("zhasd",OP_EQ, smartlist_get(sl,4));
  158. tt_str_op("",OP_EQ, smartlist_get(sl,5));
  159. tt_str_op("bnud",OP_EQ, smartlist_get(sl,6));
  160. tt_str_op("",OP_EQ, smartlist_get(sl,7));
  161. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  162. smartlist_clear(sl);
  163. smartlist_split_string(sl, " ab\tc \td ef ", NULL,
  164. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  165. tt_int_op(4,OP_EQ, smartlist_len(sl));
  166. tt_str_op("ab",OP_EQ, smartlist_get(sl,0));
  167. tt_str_op("c",OP_EQ, smartlist_get(sl,1));
  168. tt_str_op("d",OP_EQ, smartlist_get(sl,2));
  169. tt_str_op("ef",OP_EQ, smartlist_get(sl,3));
  170. smartlist_split_string(sl, "ghi\tj", NULL,
  171. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  172. tt_int_op(6,OP_EQ, smartlist_len(sl));
  173. tt_str_op("ghi",OP_EQ, smartlist_get(sl,4));
  174. tt_str_op("j",OP_EQ, smartlist_get(sl,5));
  175. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  176. smartlist_clear(sl);
  177. cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL);
  178. tt_str_op(cp_alloc,OP_EQ, "");
  179. tor_free(cp_alloc);
  180. cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL);
  181. tt_str_op(cp_alloc,OP_EQ, "XY");
  182. tor_free(cp_alloc);
  183. smartlist_split_string(sl, " z <> zhasd <> <> bnud<> ", "<>",
  184. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  185. tt_int_op(3,OP_EQ, smartlist_len(sl));
  186. tt_str_op("z",OP_EQ, smartlist_get(sl, 0));
  187. tt_str_op("zhasd",OP_EQ, smartlist_get(sl, 1));
  188. tt_str_op("bnud",OP_EQ, smartlist_get(sl, 2));
  189. smartlist_split_string(sl, " z <> zhasd <> <> bnud<> ", "<>",
  190. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 2);
  191. tt_int_op(5,OP_EQ, smartlist_len(sl));
  192. tt_str_op("z",OP_EQ, smartlist_get(sl, 3));
  193. tt_str_op("zhasd <> <> bnud<>",OP_EQ, smartlist_get(sl, 4));
  194. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  195. smartlist_clear(sl);
  196. smartlist_split_string(sl, "abcd\n", "\n",
  197. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  198. tt_int_op(1,OP_EQ, smartlist_len(sl));
  199. tt_str_op("abcd",OP_EQ, smartlist_get(sl, 0));
  200. smartlist_split_string(sl, "efgh", "\n",
  201. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  202. tt_int_op(2,OP_EQ, smartlist_len(sl));
  203. tt_str_op("efgh",OP_EQ, smartlist_get(sl, 1));
  204. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  205. smartlist_clear(sl);
  206. /* Test swapping, shuffling, and sorting. */
  207. smartlist_split_string(sl, "the,onion,router,by,arma,and,nickm", ",", 0, 0);
  208. tt_int_op(7,OP_EQ, smartlist_len(sl));
  209. smartlist_sort(sl, compare_strs_);
  210. cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
  211. tt_str_op(cp_alloc,OP_EQ, "and,arma,by,nickm,onion,router,the");
  212. tor_free(cp_alloc);
  213. smartlist_swap(sl, 1, 5);
  214. cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
  215. tt_str_op(cp_alloc,OP_EQ, "and,router,by,nickm,onion,arma,the");
  216. tor_free(cp_alloc);
  217. smartlist_shuffle(sl);
  218. tt_int_op(7,OP_EQ, smartlist_len(sl));
  219. tt_assert(smartlist_contains_string(sl, "and"));
  220. tt_assert(smartlist_contains_string(sl, "router"));
  221. tt_assert(smartlist_contains_string(sl, "by"));
  222. tt_assert(smartlist_contains_string(sl, "nickm"));
  223. tt_assert(smartlist_contains_string(sl, "onion"));
  224. tt_assert(smartlist_contains_string(sl, "arma"));
  225. tt_assert(smartlist_contains_string(sl, "the"));
  226. /* Test bsearch. */
  227. smartlist_sort(sl, compare_strs_);
  228. tt_str_op("nickm",OP_EQ, smartlist_bsearch(sl, "zNicKM",
  229. cmp_without_first_));
  230. tt_str_op("and",OP_EQ,
  231. smartlist_bsearch(sl, " AND", cmp_without_first_));
  232. tt_ptr_op(NULL,OP_EQ, smartlist_bsearch(sl, " ANz", cmp_without_first_));
  233. /* Test bsearch_idx */
  234. {
  235. int f;
  236. smartlist_t *tmp = NULL;
  237. tt_int_op(0,OP_EQ,smartlist_bsearch_idx(sl," aaa",cmp_without_first_,&f));
  238. tt_int_op(f,OP_EQ, 0);
  239. tt_int_op(0,OP_EQ, smartlist_bsearch_idx(sl," and",cmp_without_first_,&f));
  240. tt_int_op(f,OP_EQ, 1);
  241. tt_int_op(1,OP_EQ, smartlist_bsearch_idx(sl," arm",cmp_without_first_,&f));
  242. tt_int_op(f,OP_EQ, 0);
  243. tt_int_op(1,OP_EQ,
  244. smartlist_bsearch_idx(sl," arma",cmp_without_first_,&f));
  245. tt_int_op(f,OP_EQ, 1);
  246. tt_int_op(2,OP_EQ,
  247. smartlist_bsearch_idx(sl," armb",cmp_without_first_,&f));
  248. tt_int_op(f,OP_EQ, 0);
  249. tt_int_op(7,OP_EQ,
  250. smartlist_bsearch_idx(sl," zzzz",cmp_without_first_,&f));
  251. tt_int_op(f,OP_EQ, 0);
  252. /* Test trivial cases for list of length 0 or 1 */
  253. tmp = smartlist_new();
  254. tt_int_op(0,OP_EQ, smartlist_bsearch_idx(tmp, "foo",
  255. compare_strs_for_bsearch_, &f));
  256. tt_int_op(f,OP_EQ, 0);
  257. smartlist_insert(tmp, 0, (void *)("bar"));
  258. tt_int_op(1,OP_EQ, smartlist_bsearch_idx(tmp, "foo",
  259. compare_strs_for_bsearch_, &f));
  260. tt_int_op(f,OP_EQ, 0);
  261. tt_int_op(0,OP_EQ, smartlist_bsearch_idx(tmp, "aaa",
  262. compare_strs_for_bsearch_, &f));
  263. tt_int_op(f,OP_EQ, 0);
  264. tt_int_op(0,OP_EQ, smartlist_bsearch_idx(tmp, "bar",
  265. compare_strs_for_bsearch_, &f));
  266. tt_int_op(f,OP_EQ, 1);
  267. /* ... and one for length 2 */
  268. smartlist_insert(tmp, 1, (void *)("foo"));
  269. tt_int_op(1,OP_EQ, smartlist_bsearch_idx(tmp, "foo",
  270. compare_strs_for_bsearch_, &f));
  271. tt_int_op(f,OP_EQ, 1);
  272. tt_int_op(2,OP_EQ, smartlist_bsearch_idx(tmp, "goo",
  273. compare_strs_for_bsearch_, &f));
  274. tt_int_op(f,OP_EQ, 0);
  275. smartlist_free(tmp);
  276. }
  277. /* Test reverse() and pop_last() */
  278. smartlist_reverse(sl);
  279. cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
  280. tt_str_op(cp_alloc,OP_EQ, "the,router,onion,nickm,by,arma,and");
  281. tor_free(cp_alloc);
  282. cp_alloc = smartlist_pop_last(sl);
  283. tt_str_op(cp_alloc,OP_EQ, "and");
  284. tor_free(cp_alloc);
  285. tt_int_op(smartlist_len(sl),OP_EQ, 6);
  286. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  287. smartlist_clear(sl);
  288. cp_alloc = smartlist_pop_last(sl);
  289. tt_ptr_op(cp_alloc,OP_EQ, NULL);
  290. /* Test uniq() */
  291. smartlist_split_string(sl,
  292. "50,noon,radar,a,man,a,plan,a,canal,panama,radar,noon,50",
  293. ",", 0, 0);
  294. smartlist_sort(sl, compare_strs_);
  295. smartlist_uniq(sl, compare_strs_, tor_free_);
  296. cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
  297. tt_str_op(cp_alloc,OP_EQ, "50,a,canal,man,noon,panama,plan,radar");
  298. tor_free(cp_alloc);
  299. /* Test contains_string, contains_string_case and contains_int_as_string */
  300. tt_assert(smartlist_contains_string(sl, "noon"));
  301. tt_assert(!smartlist_contains_string(sl, "noonoon"));
  302. tt_assert(smartlist_contains_string_case(sl, "nOOn"));
  303. tt_assert(!smartlist_contains_string_case(sl, "nooNooN"));
  304. tt_assert(smartlist_contains_int_as_string(sl, 50));
  305. tt_assert(!smartlist_contains_int_as_string(sl, 60));
  306. /* Test smartlist_choose */
  307. {
  308. int i;
  309. int allsame = 1;
  310. int allin = 1;
  311. void *first = smartlist_choose(sl);
  312. tt_assert(smartlist_contains(sl, first));
  313. for (i = 0; i < 100; ++i) {
  314. void *second = smartlist_choose(sl);
  315. if (second != first)
  316. allsame = 0;
  317. if (!smartlist_contains(sl, second))
  318. allin = 0;
  319. }
  320. tt_assert(!allsame);
  321. tt_assert(allin);
  322. }
  323. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  324. smartlist_clear(sl);
  325. /* Test string_remove and remove and join_strings2 */
  326. smartlist_split_string(sl,
  327. "Some say the Earth will end in ice and some in fire",
  328. " ", 0, 0);
  329. cp = smartlist_get(sl, 4);
  330. tt_str_op(cp,OP_EQ, "will");
  331. smartlist_add(sl, cp);
  332. smartlist_remove(sl, cp);
  333. tor_free(cp);
  334. cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
  335. tt_str_op(cp_alloc,OP_EQ, "Some,say,the,Earth,fire,end,in,ice,and,some,in");
  336. tor_free(cp_alloc);
  337. smartlist_string_remove(sl, "in");
  338. cp_alloc = smartlist_join_strings2(sl, "+XX", 1, 0, &sz);
  339. tt_str_op(cp_alloc,OP_EQ, "Some+say+the+Earth+fire+end+some+ice+and");
  340. tt_int_op((int)sz,OP_EQ, 40);
  341. done:
  342. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  343. smartlist_free(sl);
  344. tor_free(cp_alloc);
  345. }
  346. /** Run unit tests for smartlist set manipulation functions. */
  347. static void
  348. test_container_smartlist_overlap(void *arg)
  349. {
  350. smartlist_t *sl = smartlist_new();
  351. smartlist_t *ints = smartlist_new();
  352. smartlist_t *odds = smartlist_new();
  353. smartlist_t *evens = smartlist_new();
  354. smartlist_t *primes = smartlist_new();
  355. int i;
  356. (void)arg;
  357. for (i=1; i < 10; i += 2)
  358. smartlist_add(odds, (void*)(uintptr_t)i);
  359. for (i=0; i < 10; i += 2)
  360. smartlist_add(evens, (void*)(uintptr_t)i);
  361. /* add_all */
  362. smartlist_add_all(ints, odds);
  363. smartlist_add_all(ints, evens);
  364. tt_int_op(smartlist_len(ints),OP_EQ, 10);
  365. smartlist_add(primes, (void*)2);
  366. smartlist_add(primes, (void*)3);
  367. smartlist_add(primes, (void*)5);
  368. smartlist_add(primes, (void*)7);
  369. /* overlap */
  370. tt_assert(smartlist_overlap(ints, odds));
  371. tt_assert(smartlist_overlap(odds, primes));
  372. tt_assert(smartlist_overlap(evens, primes));
  373. tt_assert(!smartlist_overlap(odds, evens));
  374. /* intersect */
  375. smartlist_add_all(sl, odds);
  376. smartlist_intersect(sl, primes);
  377. tt_int_op(smartlist_len(sl),OP_EQ, 3);
  378. tt_assert(smartlist_contains(sl, (void*)3));
  379. tt_assert(smartlist_contains(sl, (void*)5));
  380. tt_assert(smartlist_contains(sl, (void*)7));
  381. /* subtract */
  382. smartlist_add_all(sl, primes);
  383. smartlist_subtract(sl, odds);
  384. tt_int_op(smartlist_len(sl),OP_EQ, 1);
  385. tt_assert(smartlist_contains(sl, (void*)2));
  386. done:
  387. smartlist_free(odds);
  388. smartlist_free(evens);
  389. smartlist_free(ints);
  390. smartlist_free(primes);
  391. smartlist_free(sl);
  392. }
  393. /** Run unit tests for smartlist-of-digests functions. */
  394. static void
  395. test_container_smartlist_digests(void *arg)
  396. {
  397. smartlist_t *sl = smartlist_new();
  398. /* contains_digest */
  399. (void)arg;
  400. smartlist_add(sl, tor_memdup("AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN));
  401. smartlist_add(sl, tor_memdup("\00090AAB2AAAAaasdAAAAA", DIGEST_LEN));
  402. smartlist_add(sl, tor_memdup("\00090AAB2AAAAaasdAAAAA", DIGEST_LEN));
  403. tt_int_op(0,OP_EQ, smartlist_contains_digest(NULL, "AAAAAAAAAAAAAAAAAAAA"));
  404. tt_assert(smartlist_contains_digest(sl, "AAAAAAAAAAAAAAAAAAAA"));
  405. tt_assert(smartlist_contains_digest(sl, "\00090AAB2AAAAaasdAAAAA"));
  406. tt_int_op(0,OP_EQ, smartlist_contains_digest(sl, "\00090AAB2AAABaasdAAAAA"));
  407. /* sort digests */
  408. smartlist_sort_digests(sl);
  409. tt_mem_op(smartlist_get(sl, 0),OP_EQ, "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
  410. tt_mem_op(smartlist_get(sl, 1),OP_EQ, "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
  411. tt_mem_op(smartlist_get(sl, 2),OP_EQ, "AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN);
  412. tt_int_op(3,OP_EQ, smartlist_len(sl));
  413. /* uniq_digests */
  414. smartlist_uniq_digests(sl);
  415. tt_int_op(2,OP_EQ, smartlist_len(sl));
  416. tt_mem_op(smartlist_get(sl, 0),OP_EQ, "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
  417. tt_mem_op(smartlist_get(sl, 1),OP_EQ, "AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN);
  418. done:
  419. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  420. smartlist_free(sl);
  421. }
  422. /** Run unit tests for concatenate-a-smartlist-of-strings functions. */
  423. static void
  424. test_container_smartlist_join(void *arg)
  425. {
  426. smartlist_t *sl = smartlist_new();
  427. smartlist_t *sl2 = smartlist_new(), *sl3 = smartlist_new(),
  428. *sl4 = smartlist_new();
  429. char *joined=NULL;
  430. /* unique, sorted. */
  431. (void)arg;
  432. smartlist_split_string(sl,
  433. "Abashments Ambush Anchorman Bacon Banks Borscht "
  434. "Bunks Inhumane Insurance Knish Know Manners "
  435. "Maraschinos Stamina Sunbonnets Unicorns Wombats",
  436. " ", 0, 0);
  437. /* non-unique, sorted. */
  438. smartlist_split_string(sl2,
  439. "Ambush Anchorman Anchorman Anemias Anemias Bacon "
  440. "Crossbowmen Inhumane Insurance Knish Know Manners "
  441. "Manners Maraschinos Wombats Wombats Work",
  442. " ", 0, 0);
  443. SMARTLIST_FOREACH_JOIN(sl, char *, cp1,
  444. sl2, char *, cp2,
  445. strcmp(cp1,cp2),
  446. smartlist_add(sl3, cp2)) {
  447. tt_str_op(cp1,OP_EQ, cp2);
  448. smartlist_add(sl4, cp1);
  449. } SMARTLIST_FOREACH_JOIN_END(cp1, cp2);
  450. SMARTLIST_FOREACH(sl3, const char *, cp,
  451. tt_assert(smartlist_contains(sl2, cp) &&
  452. !smartlist_contains_string(sl, cp)));
  453. SMARTLIST_FOREACH(sl4, const char *, cp,
  454. tt_assert(smartlist_contains(sl, cp) &&
  455. smartlist_contains_string(sl2, cp)));
  456. joined = smartlist_join_strings(sl3, ",", 0, NULL);
  457. tt_str_op(joined,OP_EQ, "Anemias,Anemias,Crossbowmen,Work");
  458. tor_free(joined);
  459. joined = smartlist_join_strings(sl4, ",", 0, NULL);
  460. tt_str_op(joined,OP_EQ,
  461. "Ambush,Anchorman,Anchorman,Bacon,Inhumane,Insurance,"
  462. "Knish,Know,Manners,Manners,Maraschinos,Wombats,Wombats");
  463. tor_free(joined);
  464. done:
  465. smartlist_free(sl4);
  466. smartlist_free(sl3);
  467. SMARTLIST_FOREACH(sl2, char *, cp, tor_free(cp));
  468. smartlist_free(sl2);
  469. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  470. smartlist_free(sl);
  471. tor_free(joined);
  472. }
  473. static void
  474. test_container_smartlist_pos(void *arg)
  475. {
  476. (void) arg;
  477. smartlist_t *sl = smartlist_new();
  478. smartlist_add_strdup(sl, "This");
  479. smartlist_add_strdup(sl, "is");
  480. smartlist_add_strdup(sl, "a");
  481. smartlist_add_strdup(sl, "test");
  482. smartlist_add_strdup(sl, "for");
  483. smartlist_add_strdup(sl, "a");
  484. smartlist_add_strdup(sl, "function");
  485. /* Test string_pos */
  486. tt_int_op(smartlist_string_pos(NULL, "Fred"), OP_EQ, -1);
  487. tt_int_op(smartlist_string_pos(sl, "Fred"), OP_EQ, -1);
  488. tt_int_op(smartlist_string_pos(sl, "This"), OP_EQ, 0);
  489. tt_int_op(smartlist_string_pos(sl, "a"), OP_EQ, 2);
  490. tt_int_op(smartlist_string_pos(sl, "function"), OP_EQ, 6);
  491. /* Test pos */
  492. tt_int_op(smartlist_pos(NULL, "Fred"), OP_EQ, -1);
  493. tt_int_op(smartlist_pos(sl, "Fred"), OP_EQ, -1);
  494. tt_int_op(smartlist_pos(sl, "This"), OP_EQ, -1);
  495. tt_int_op(smartlist_pos(sl, "a"), OP_EQ, -1);
  496. tt_int_op(smartlist_pos(sl, "function"), OP_EQ, -1);
  497. tt_int_op(smartlist_pos(sl, smartlist_get(sl,0)), OP_EQ, 0);
  498. tt_int_op(smartlist_pos(sl, smartlist_get(sl,2)), OP_EQ, 2);
  499. tt_int_op(smartlist_pos(sl, smartlist_get(sl,5)), OP_EQ, 5);
  500. tt_int_op(smartlist_pos(sl, smartlist_get(sl,6)), OP_EQ, 6);
  501. done:
  502. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  503. smartlist_free(sl);
  504. }
  505. static void
  506. test_container_smartlist_ints_eq(void *arg)
  507. {
  508. smartlist_t *sl1 = NULL, *sl2 = NULL;
  509. int x;
  510. (void)arg;
  511. tt_assert(smartlist_ints_eq(NULL, NULL));
  512. sl1 = smartlist_new();
  513. tt_assert(!smartlist_ints_eq(sl1, NULL));
  514. tt_assert(!smartlist_ints_eq(NULL, sl1));
  515. sl2 = smartlist_new();
  516. tt_assert(smartlist_ints_eq(sl1, sl2));
  517. x = 5;
  518. smartlist_add(sl1, tor_memdup(&x, sizeof(int)));
  519. smartlist_add(sl2, tor_memdup(&x, sizeof(int)));
  520. x = 90;
  521. smartlist_add(sl1, tor_memdup(&x, sizeof(int)));
  522. smartlist_add(sl2, tor_memdup(&x, sizeof(int)));
  523. tt_assert(smartlist_ints_eq(sl1, sl2));
  524. x = -50;
  525. smartlist_add(sl1, tor_memdup(&x, sizeof(int)));
  526. tt_assert(! smartlist_ints_eq(sl1, sl2));
  527. tt_assert(! smartlist_ints_eq(sl2, sl1));
  528. smartlist_add(sl2, tor_memdup(&x, sizeof(int)));
  529. tt_assert(smartlist_ints_eq(sl1, sl2));
  530. *(int*)smartlist_get(sl1, 1) = 101010;
  531. tt_assert(! smartlist_ints_eq(sl2, sl1));
  532. *(int*)smartlist_get(sl2, 1) = 101010;
  533. tt_assert(smartlist_ints_eq(sl1, sl2));
  534. done:
  535. if (sl1)
  536. SMARTLIST_FOREACH(sl1, int *, ip, tor_free(ip));
  537. if (sl2)
  538. SMARTLIST_FOREACH(sl2, int *, ip, tor_free(ip));
  539. smartlist_free(sl1);
  540. smartlist_free(sl2);
  541. }
  542. /** Run unit tests for bitarray code */
  543. static void
  544. test_container_bitarray(void *arg)
  545. {
  546. bitarray_t *ba = NULL;
  547. int i, j, ok=1;
  548. (void)arg;
  549. ba = bitarray_init_zero(1);
  550. tt_assert(ba);
  551. tt_assert(! bitarray_is_set(ba, 0));
  552. bitarray_set(ba, 0);
  553. tt_assert(bitarray_is_set(ba, 0));
  554. bitarray_clear(ba, 0);
  555. tt_assert(! bitarray_is_set(ba, 0));
  556. bitarray_free(ba);
  557. ba = bitarray_init_zero(1023);
  558. for (i = 1; i < 64; ) {
  559. for (j = 0; j < 1023; ++j) {
  560. if (j % i)
  561. bitarray_set(ba, j);
  562. else
  563. bitarray_clear(ba, j);
  564. }
  565. for (j = 0; j < 1023; ++j) {
  566. if (!bool_eq(bitarray_is_set(ba, j), j%i))
  567. ok = 0;
  568. }
  569. tt_assert(ok);
  570. if (i < 7)
  571. ++i;
  572. else if (i == 28)
  573. i = 32;
  574. else
  575. i += 7;
  576. }
  577. done:
  578. if (ba)
  579. bitarray_free(ba);
  580. }
  581. /** Run unit tests for digest set code (implemented as a hashtable or as a
  582. * bloom filter) */
  583. static void
  584. test_container_digestset(void *arg)
  585. {
  586. smartlist_t *included = smartlist_new();
  587. char d[DIGEST_LEN];
  588. int i;
  589. int ok = 1;
  590. int false_positives = 0;
  591. digestset_t *set = NULL;
  592. (void)arg;
  593. for (i = 0; i < 1000; ++i) {
  594. crypto_rand(d, DIGEST_LEN);
  595. smartlist_add(included, tor_memdup(d, DIGEST_LEN));
  596. }
  597. set = digestset_new(1000);
  598. SMARTLIST_FOREACH(included, const char *, cp,
  599. if (digestset_probably_contains(set, cp))
  600. ok = 0);
  601. tt_assert(ok);
  602. SMARTLIST_FOREACH(included, const char *, cp,
  603. digestset_add(set, cp));
  604. SMARTLIST_FOREACH(included, const char *, cp,
  605. if (!digestset_probably_contains(set, cp))
  606. ok = 0);
  607. tt_assert(ok);
  608. for (i = 0; i < 1000; ++i) {
  609. crypto_rand(d, DIGEST_LEN);
  610. if (digestset_probably_contains(set, d))
  611. ++false_positives;
  612. }
  613. tt_int_op(50, OP_GT, false_positives); /* Should be far lower. */
  614. done:
  615. if (set)
  616. digestset_free(set);
  617. SMARTLIST_FOREACH(included, char *, cp, tor_free(cp));
  618. smartlist_free(included);
  619. }
  620. typedef struct pq_entry_t {
  621. const char *val;
  622. int idx;
  623. } pq_entry_t;
  624. /** Helper: return a tristate based on comparing two pq_entry_t values. */
  625. static int
  626. compare_strings_for_pqueue_(const void *p1, const void *p2)
  627. {
  628. const pq_entry_t *e1=p1, *e2=p2;
  629. return strcmp(e1->val, e2->val);
  630. }
  631. /** Run unit tests for heap-based priority queue functions. */
  632. static void
  633. test_container_pqueue(void *arg)
  634. {
  635. smartlist_t *sl = smartlist_new();
  636. int (*cmp)(const void *, const void*);
  637. const int offset = offsetof(pq_entry_t, idx);
  638. #define ENTRY(s) pq_entry_t s = { #s, -1 }
  639. ENTRY(cows);
  640. ENTRY(zebras);
  641. ENTRY(fish);
  642. ENTRY(frogs);
  643. ENTRY(apples);
  644. ENTRY(squid);
  645. ENTRY(daschunds);
  646. ENTRY(eggplants);
  647. ENTRY(weissbier);
  648. ENTRY(lobsters);
  649. ENTRY(roquefort);
  650. ENTRY(chinchillas);
  651. ENTRY(fireflies);
  652. #define OK() smartlist_pqueue_assert_ok(sl, cmp, offset)
  653. (void)arg;
  654. cmp = compare_strings_for_pqueue_;
  655. smartlist_pqueue_add(sl, cmp, offset, &cows);
  656. smartlist_pqueue_add(sl, cmp, offset, &zebras);
  657. smartlist_pqueue_add(sl, cmp, offset, &fish);
  658. smartlist_pqueue_add(sl, cmp, offset, &frogs);
  659. smartlist_pqueue_add(sl, cmp, offset, &apples);
  660. smartlist_pqueue_add(sl, cmp, offset, &squid);
  661. smartlist_pqueue_add(sl, cmp, offset, &daschunds);
  662. smartlist_pqueue_add(sl, cmp, offset, &eggplants);
  663. smartlist_pqueue_add(sl, cmp, offset, &weissbier);
  664. smartlist_pqueue_add(sl, cmp, offset, &lobsters);
  665. smartlist_pqueue_add(sl, cmp, offset, &roquefort);
  666. OK();
  667. tt_int_op(smartlist_len(sl),OP_EQ, 11);
  668. tt_ptr_op(smartlist_get(sl, 0),OP_EQ, &apples);
  669. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &apples);
  670. tt_int_op(smartlist_len(sl),OP_EQ, 10);
  671. OK();
  672. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &cows);
  673. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &daschunds);
  674. smartlist_pqueue_add(sl, cmp, offset, &chinchillas);
  675. OK();
  676. smartlist_pqueue_add(sl, cmp, offset, &fireflies);
  677. OK();
  678. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &chinchillas);
  679. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &eggplants);
  680. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &fireflies);
  681. OK();
  682. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &fish);
  683. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &frogs);
  684. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &lobsters);
  685. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &roquefort);
  686. OK();
  687. tt_int_op(smartlist_len(sl),OP_EQ, 3);
  688. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &squid);
  689. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &weissbier);
  690. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &zebras);
  691. tt_int_op(smartlist_len(sl),OP_EQ, 0);
  692. OK();
  693. /* Now test remove. */
  694. smartlist_pqueue_add(sl, cmp, offset, &cows);
  695. smartlist_pqueue_add(sl, cmp, offset, &fish);
  696. smartlist_pqueue_add(sl, cmp, offset, &frogs);
  697. smartlist_pqueue_add(sl, cmp, offset, &apples);
  698. smartlist_pqueue_add(sl, cmp, offset, &squid);
  699. smartlist_pqueue_add(sl, cmp, offset, &zebras);
  700. tt_int_op(smartlist_len(sl),OP_EQ, 6);
  701. OK();
  702. smartlist_pqueue_remove(sl, cmp, offset, &zebras);
  703. tt_int_op(smartlist_len(sl),OP_EQ, 5);
  704. OK();
  705. smartlist_pqueue_remove(sl, cmp, offset, &cows);
  706. tt_int_op(smartlist_len(sl),OP_EQ, 4);
  707. OK();
  708. smartlist_pqueue_remove(sl, cmp, offset, &apples);
  709. tt_int_op(smartlist_len(sl),OP_EQ, 3);
  710. OK();
  711. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &fish);
  712. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &frogs);
  713. tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset),OP_EQ, &squid);
  714. tt_int_op(smartlist_len(sl),OP_EQ, 0);
  715. OK();
  716. #undef OK
  717. done:
  718. smartlist_free(sl);
  719. }
  720. /** Run unit tests for string-to-void* map functions */
  721. static void
  722. test_container_strmap(void *arg)
  723. {
  724. strmap_t *map;
  725. strmap_iter_t *iter;
  726. const char *k;
  727. void *v;
  728. char *visited = NULL;
  729. smartlist_t *found_keys = NULL;
  730. char *v1 = tor_strdup("v1");
  731. char *v99 = tor_strdup("v99");
  732. char *v100 = tor_strdup("v100");
  733. char *v101 = tor_strdup("v101");
  734. char *v102 = tor_strdup("v102");
  735. char *v103 = tor_strdup("v103");
  736. char *v104 = tor_strdup("v104");
  737. char *v105 = tor_strdup("v105");
  738. (void)arg;
  739. map = strmap_new();
  740. tt_assert(map);
  741. tt_int_op(strmap_size(map),OP_EQ, 0);
  742. tt_assert(strmap_isempty(map));
  743. v = strmap_set(map, "K1", v99);
  744. tt_ptr_op(v,OP_EQ, NULL);
  745. tt_assert(!strmap_isempty(map));
  746. v = strmap_set(map, "K2", v101);
  747. tt_ptr_op(v,OP_EQ, NULL);
  748. v = strmap_set(map, "K1", v100);
  749. tt_ptr_op(v,OP_EQ, v99);
  750. tt_ptr_op(strmap_get(map,"K1"),OP_EQ, v100);
  751. tt_ptr_op(strmap_get(map,"K2"),OP_EQ, v101);
  752. tt_ptr_op(strmap_get(map,"K-not-there"),OP_EQ, NULL);
  753. strmap_assert_ok(map);
  754. v = strmap_remove(map,"K2");
  755. strmap_assert_ok(map);
  756. tt_ptr_op(v,OP_EQ, v101);
  757. tt_ptr_op(strmap_get(map,"K2"),OP_EQ, NULL);
  758. tt_ptr_op(strmap_remove(map,"K2"),OP_EQ, NULL);
  759. strmap_set(map, "K2", v101);
  760. strmap_set(map, "K3", v102);
  761. strmap_set(map, "K4", v103);
  762. tt_int_op(strmap_size(map),OP_EQ, 4);
  763. strmap_assert_ok(map);
  764. strmap_set(map, "K5", v104);
  765. strmap_set(map, "K6", v105);
  766. strmap_assert_ok(map);
  767. /* Test iterator. */
  768. iter = strmap_iter_init(map);
  769. found_keys = smartlist_new();
  770. while (!strmap_iter_done(iter)) {
  771. strmap_iter_get(iter,&k,&v);
  772. smartlist_add_strdup(found_keys, k);
  773. tt_ptr_op(v,OP_EQ, strmap_get(map, k));
  774. if (!strcmp(k, "K2")) {
  775. iter = strmap_iter_next_rmv(map,iter);
  776. } else {
  777. iter = strmap_iter_next(map,iter);
  778. }
  779. }
  780. /* Make sure we removed K2, but not the others. */
  781. tt_ptr_op(strmap_get(map, "K2"),OP_EQ, NULL);
  782. tt_ptr_op(strmap_get(map, "K5"),OP_EQ, v104);
  783. /* Make sure we visited everyone once */
  784. smartlist_sort_strings(found_keys);
  785. visited = smartlist_join_strings(found_keys, ":", 0, NULL);
  786. tt_str_op(visited,OP_EQ, "K1:K2:K3:K4:K5:K6");
  787. strmap_assert_ok(map);
  788. /* Clean up after ourselves. */
  789. strmap_free(map, NULL);
  790. map = NULL;
  791. /* Now try some lc functions. */
  792. map = strmap_new();
  793. strmap_set_lc(map,"Ab.C", v1);
  794. tt_ptr_op(strmap_get(map,"ab.c"),OP_EQ, v1);
  795. strmap_assert_ok(map);
  796. tt_ptr_op(strmap_get_lc(map,"AB.C"),OP_EQ, v1);
  797. tt_ptr_op(strmap_get(map,"AB.C"),OP_EQ, NULL);
  798. tt_ptr_op(strmap_remove_lc(map,"aB.C"),OP_EQ, v1);
  799. strmap_assert_ok(map);
  800. tt_ptr_op(strmap_get_lc(map,"AB.C"),OP_EQ, NULL);
  801. done:
  802. if (map)
  803. strmap_free(map,NULL);
  804. if (found_keys) {
  805. SMARTLIST_FOREACH(found_keys, char *, cp, tor_free(cp));
  806. smartlist_free(found_keys);
  807. }
  808. tor_free(visited);
  809. tor_free(v1);
  810. tor_free(v99);
  811. tor_free(v100);
  812. tor_free(v101);
  813. tor_free(v102);
  814. tor_free(v103);
  815. tor_free(v104);
  816. tor_free(v105);
  817. }
  818. static void
  819. test_container_smartlist_remove(void *arg)
  820. {
  821. (void) arg;
  822. int array[5];
  823. smartlist_t *sl = smartlist_new();
  824. int i,j;
  825. for (j=0; j < 2; ++j)
  826. for (i=0; i < 5; ++i)
  827. smartlist_add(sl, &array[i]);
  828. smartlist_remove(sl, &array[0]);
  829. smartlist_remove(sl, &array[3]);
  830. smartlist_remove(sl, &array[4]);
  831. tt_assert(! smartlist_contains(sl, &array[0]));
  832. tt_assert(smartlist_contains(sl, &array[1]));
  833. tt_assert(smartlist_contains(sl, &array[2]));
  834. tt_assert(! smartlist_contains(sl, &array[3]));
  835. tt_assert(! smartlist_contains(sl, &array[4]));
  836. tt_int_op(smartlist_len(sl), OP_EQ, 4);
  837. smartlist_clear(sl);
  838. for (j=0; j < 2; ++j)
  839. for (i=0; i < 5; ++i)
  840. smartlist_add(sl, &array[i]);
  841. smartlist_remove_keeporder(sl, &array[0]);
  842. smartlist_remove_keeporder(sl, &array[3]);
  843. smartlist_remove_keeporder(sl, &array[4]);
  844. tt_int_op(smartlist_len(sl), OP_EQ, 4);
  845. tt_ptr_op(smartlist_get(sl, 0), OP_EQ, &array[1]);
  846. tt_ptr_op(smartlist_get(sl, 1), OP_EQ, &array[2]);
  847. tt_ptr_op(smartlist_get(sl, 2), OP_EQ, &array[1]);
  848. tt_ptr_op(smartlist_get(sl, 3), OP_EQ, &array[2]);
  849. done:
  850. smartlist_free(sl);
  851. }
  852. /** Run unit tests for getting the median of a list. */
  853. static void
  854. test_container_order_functions(void *arg)
  855. {
  856. int lst[25], n = 0;
  857. uint32_t lst_2[25];
  858. // int a=12,b=24,c=25,d=60,e=77;
  859. #define median() median_int(lst, n)
  860. (void)arg;
  861. lst[n++] = 12;
  862. tt_int_op(12,OP_EQ, median()); /* 12 */
  863. lst[n++] = 77;
  864. //smartlist_shuffle(sl);
  865. tt_int_op(12,OP_EQ, median()); /* 12, 77 */
  866. lst[n++] = 77;
  867. //smartlist_shuffle(sl);
  868. tt_int_op(77,OP_EQ, median()); /* 12, 77, 77 */
  869. lst[n++] = 24;
  870. tt_int_op(24,OP_EQ, median()); /* 12,24,77,77 */
  871. lst[n++] = 60;
  872. lst[n++] = 12;
  873. lst[n++] = 25;
  874. //smartlist_shuffle(sl);
  875. tt_int_op(25,OP_EQ, median()); /* 12,12,24,25,60,77,77 */
  876. #undef median
  877. #define third_quartile() third_quartile_uint32(lst_2, n)
  878. n = 0;
  879. lst_2[n++] = 1;
  880. tt_int_op(1,OP_EQ, third_quartile()); /* ~1~ */
  881. lst_2[n++] = 2;
  882. tt_int_op(2,OP_EQ, third_quartile()); /* 1, ~2~ */
  883. lst_2[n++] = 3;
  884. lst_2[n++] = 4;
  885. lst_2[n++] = 5;
  886. tt_int_op(4,OP_EQ, third_quartile()); /* 1, 2, 3, ~4~, 5 */
  887. lst_2[n++] = 6;
  888. lst_2[n++] = 7;
  889. lst_2[n++] = 8;
  890. lst_2[n++] = 9;
  891. tt_int_op(7,OP_EQ, third_quartile()); /* 1, 2, 3, 4, 5, 6, ~7~, 8, 9 */
  892. lst_2[n++] = 10;
  893. lst_2[n++] = 11;
  894. /* 1, 2, 3, 4, 5, 6, 7, 8, ~9~, 10, 11 */
  895. tt_int_op(9,OP_EQ, third_quartile());
  896. #undef third_quartile
  897. double dbls[] = { 1.0, 10.0, 100.0, 1e4, 1e5, 1e6 };
  898. tt_double_eq(1.0, median_double(dbls, 1));
  899. tt_double_eq(1.0, median_double(dbls, 2));
  900. tt_double_eq(10.0, median_double(dbls, 3));
  901. tt_double_eq(10.0, median_double(dbls, 4));
  902. tt_double_eq(100.0, median_double(dbls, 5));
  903. tt_double_eq(100.0, median_double(dbls, 6));
  904. time_t times[] = { 5, 10, 20, 25, 15 };
  905. tt_assert(5 == median_time(times, 1));
  906. tt_assert(5 == median_time(times, 2));
  907. tt_assert(10 == median_time(times, 3));
  908. tt_assert(10 == median_time(times, 4));
  909. tt_assert(15 == median_time(times, 5));
  910. int32_t int32s[] = { -5, -10, -50, 100 };
  911. tt_int_op(-5, OP_EQ, median_int32(int32s, 1));
  912. tt_int_op(-10, OP_EQ, median_int32(int32s, 2));
  913. tt_int_op(-10, OP_EQ, median_int32(int32s, 3));
  914. tt_int_op(-10, OP_EQ, median_int32(int32s, 4));
  915. long longs[] = { -30, 30, 100, -100, 7 };
  916. tt_int_op(7, OP_EQ, find_nth_long(longs, 5, 2));
  917. done:
  918. ;
  919. }
  920. static void
  921. test_container_di_map(void *arg)
  922. {
  923. di_digest256_map_t *map = NULL;
  924. const uint8_t key1[] = "In view of the fact that it was ";
  925. const uint8_t key2[] = "superficially convincing, being ";
  926. const uint8_t key3[] = "properly enciphered in a one-tim";
  927. const uint8_t key4[] = "e cipher scheduled for use today";
  928. char *v1 = tor_strdup(", it came close to causing a disaster...");
  929. char *v2 = tor_strdup("I regret to have to advise you that the mission");
  930. char *v3 = tor_strdup("was actually initiated...");
  931. /* -- John Brunner, _The Shockwave Rider_ */
  932. (void)arg;
  933. /* Try searching on an empty map. */
  934. tt_ptr_op(NULL, OP_EQ, dimap_search(map, key1, NULL));
  935. tt_ptr_op(NULL, OP_EQ, dimap_search(map, key2, NULL));
  936. tt_ptr_op(v3, OP_EQ, dimap_search(map, key2, v3));
  937. dimap_free(map, NULL);
  938. map = NULL;
  939. /* Add a single entry. */
  940. dimap_add_entry(&map, key1, v1);
  941. tt_ptr_op(NULL, OP_EQ, dimap_search(map, key2, NULL));
  942. tt_ptr_op(v3, OP_EQ, dimap_search(map, key2, v3));
  943. tt_ptr_op(v1, OP_EQ, dimap_search(map, key1, NULL));
  944. /* Now try it with three entries in the map. */
  945. dimap_add_entry(&map, key2, v2);
  946. dimap_add_entry(&map, key3, v3);
  947. tt_ptr_op(v1, OP_EQ, dimap_search(map, key1, NULL));
  948. tt_ptr_op(v2, OP_EQ, dimap_search(map, key2, NULL));
  949. tt_ptr_op(v3, OP_EQ, dimap_search(map, key3, NULL));
  950. tt_ptr_op(NULL, OP_EQ, dimap_search(map, key4, NULL));
  951. tt_ptr_op(v1, OP_EQ, dimap_search(map, key4, v1));
  952. done:
  953. tor_free(v1);
  954. tor_free(v2);
  955. tor_free(v3);
  956. dimap_free(map, NULL);
  957. }
  958. /** Run unit tests for fp_pair-to-void* map functions */
  959. static void
  960. test_container_fp_pair_map(void *arg)
  961. {
  962. fp_pair_map_t *map;
  963. fp_pair_t fp1, fp2, fp3, fp4, fp5, fp6;
  964. void *v;
  965. fp_pair_map_iter_t *iter;
  966. fp_pair_t k;
  967. char *v99 = tor_strdup("99");
  968. char *v100 = tor_strdup("v100");
  969. char *v101 = tor_strdup("v101");
  970. char *v102 = tor_strdup("v102");
  971. char *v103 = tor_strdup("v103");
  972. char *v104 = tor_strdup("v104");
  973. char *v105 = tor_strdup("v105");
  974. (void)arg;
  975. map = fp_pair_map_new();
  976. tt_assert(map);
  977. tt_int_op(fp_pair_map_size(map),OP_EQ, 0);
  978. tt_assert(fp_pair_map_isempty(map));
  979. memset(fp1.first, 0x11, DIGEST_LEN);
  980. memset(fp1.second, 0x12, DIGEST_LEN);
  981. memset(fp2.first, 0x21, DIGEST_LEN);
  982. memset(fp2.second, 0x22, DIGEST_LEN);
  983. memset(fp3.first, 0x31, DIGEST_LEN);
  984. memset(fp3.second, 0x32, DIGEST_LEN);
  985. memset(fp4.first, 0x41, DIGEST_LEN);
  986. memset(fp4.second, 0x42, DIGEST_LEN);
  987. memset(fp5.first, 0x51, DIGEST_LEN);
  988. memset(fp5.second, 0x52, DIGEST_LEN);
  989. memset(fp6.first, 0x61, DIGEST_LEN);
  990. memset(fp6.second, 0x62, DIGEST_LEN);
  991. v = fp_pair_map_set(map, &fp1, v99);
  992. tt_ptr_op(v, OP_EQ, NULL);
  993. tt_assert(!fp_pair_map_isempty(map));
  994. v = fp_pair_map_set(map, &fp2, v101);
  995. tt_ptr_op(v, OP_EQ, NULL);
  996. v = fp_pair_map_set(map, &fp1, v100);
  997. tt_ptr_op(v, OP_EQ, v99);
  998. tt_ptr_op(fp_pair_map_get(map, &fp1),OP_EQ, v100);
  999. tt_ptr_op(fp_pair_map_get(map, &fp2),OP_EQ, v101);
  1000. tt_ptr_op(fp_pair_map_get(map, &fp3),OP_EQ, NULL);
  1001. fp_pair_map_assert_ok(map);
  1002. v = fp_pair_map_remove(map, &fp2);
  1003. fp_pair_map_assert_ok(map);
  1004. tt_ptr_op(v,OP_EQ, v101);
  1005. tt_ptr_op(fp_pair_map_get(map, &fp2),OP_EQ, NULL);
  1006. tt_ptr_op(fp_pair_map_remove(map, &fp2),OP_EQ, NULL);
  1007. fp_pair_map_set(map, &fp2, v101);
  1008. fp_pair_map_set(map, &fp3, v102);
  1009. fp_pair_map_set(map, &fp4, v103);
  1010. tt_int_op(fp_pair_map_size(map),OP_EQ, 4);
  1011. fp_pair_map_assert_ok(map);
  1012. fp_pair_map_set(map, &fp5, v104);
  1013. fp_pair_map_set_by_digests(map, fp6.first, fp6.second, v105);
  1014. fp_pair_map_assert_ok(map);
  1015. /* Test iterator. */
  1016. iter = fp_pair_map_iter_init(map);
  1017. while (!fp_pair_map_iter_done(iter)) {
  1018. fp_pair_map_iter_get(iter, &k, &v);
  1019. tt_ptr_op(v,OP_EQ, fp_pair_map_get(map, &k));
  1020. if (tor_memeq(&fp2, &k, sizeof(fp2))) {
  1021. iter = fp_pair_map_iter_next_rmv(map, iter);
  1022. } else {
  1023. iter = fp_pair_map_iter_next(map, iter);
  1024. }
  1025. }
  1026. /* Make sure we removed fp2, but not the others. */
  1027. tt_ptr_op(fp_pair_map_get(map, &fp2),OP_EQ, NULL);
  1028. tt_ptr_op(fp_pair_map_get_by_digests(map, fp5.first, fp5.second),
  1029. OP_EQ, v104);
  1030. fp_pair_map_assert_ok(map);
  1031. /* Clean up after ourselves. */
  1032. fp_pair_map_free(map, NULL);
  1033. map = NULL;
  1034. done:
  1035. if (map)
  1036. fp_pair_map_free(map, NULL);
  1037. tor_free(v99);
  1038. tor_free(v100);
  1039. tor_free(v101);
  1040. tor_free(v102);
  1041. tor_free(v103);
  1042. tor_free(v104);
  1043. tor_free(v105);
  1044. }
  1045. static void
  1046. test_container_smartlist_most_frequent(void *arg)
  1047. {
  1048. (void) arg;
  1049. smartlist_t *sl = smartlist_new();
  1050. int count = -1;
  1051. const char *cp;
  1052. cp = smartlist_get_most_frequent_string_(sl, &count);
  1053. tt_int_op(count, OP_EQ, 0);
  1054. tt_ptr_op(cp, OP_EQ, NULL);
  1055. /* String must be sorted before we call get_most_frequent */
  1056. smartlist_split_string(sl, "abc:def:ghi", ":", 0, 0);
  1057. cp = smartlist_get_most_frequent_string_(sl, &count);
  1058. tt_int_op(count, OP_EQ, 1);
  1059. tt_str_op(cp, OP_EQ, "ghi"); /* Ties broken in favor of later element */
  1060. smartlist_split_string(sl, "def:ghi", ":", 0, 0);
  1061. smartlist_sort_strings(sl);
  1062. cp = smartlist_get_most_frequent_string_(sl, &count);
  1063. tt_int_op(count, OP_EQ, 2);
  1064. tt_ptr_op(cp, OP_NE, NULL);
  1065. tt_str_op(cp, OP_EQ, "ghi"); /* Ties broken in favor of later element */
  1066. smartlist_split_string(sl, "def:abc:qwop", ":", 0, 0);
  1067. smartlist_sort_strings(sl);
  1068. cp = smartlist_get_most_frequent_string_(sl, &count);
  1069. tt_int_op(count, OP_EQ, 3);
  1070. tt_ptr_op(cp, OP_NE, NULL);
  1071. tt_str_op(cp, OP_EQ, "def"); /* No tie */
  1072. done:
  1073. SMARTLIST_FOREACH(sl, char *, str, tor_free(str));
  1074. smartlist_free(sl);
  1075. }
  1076. static void
  1077. test_container_smartlist_sort_ptrs(void *arg)
  1078. {
  1079. (void)arg;
  1080. int array[10];
  1081. int *arrayptrs[11];
  1082. smartlist_t *sl = smartlist_new();
  1083. unsigned i=0, j;
  1084. for (j = 0; j < ARRAY_LENGTH(array); ++j) {
  1085. smartlist_add(sl, &array[j]);
  1086. arrayptrs[i++] = &array[j];
  1087. if (j == 5) {
  1088. smartlist_add(sl, &array[j]);
  1089. arrayptrs[i++] = &array[j];
  1090. }
  1091. }
  1092. for (i = 0; i < 10; ++i) {
  1093. smartlist_shuffle(sl);
  1094. smartlist_sort_pointers(sl);
  1095. for (j = 0; j < ARRAY_LENGTH(arrayptrs); ++j) {
  1096. tt_ptr_op(smartlist_get(sl, j), OP_EQ, arrayptrs[j]);
  1097. }
  1098. }
  1099. done:
  1100. smartlist_free(sl);
  1101. }
  1102. static void
  1103. test_container_smartlist_strings_eq(void *arg)
  1104. {
  1105. (void)arg;
  1106. smartlist_t *sl1 = smartlist_new();
  1107. smartlist_t *sl2 = smartlist_new();
  1108. #define EQ_SHOULD_SAY(s1,s2,val) \
  1109. do { \
  1110. SMARTLIST_FOREACH(sl1, char *, cp, tor_free(cp)); \
  1111. SMARTLIST_FOREACH(sl2, char *, cp, tor_free(cp)); \
  1112. smartlist_clear(sl1); \
  1113. smartlist_clear(sl2); \
  1114. smartlist_split_string(sl1, (s1), ":", 0, 0); \
  1115. smartlist_split_string(sl2, (s2), ":", 0, 0); \
  1116. tt_int_op((val), OP_EQ, smartlist_strings_eq(sl1, sl2)); \
  1117. } while (0)
  1118. /* Both NULL, so equal */
  1119. tt_int_op(1, OP_EQ, smartlist_strings_eq(NULL, NULL));
  1120. /* One NULL, not equal. */
  1121. tt_int_op(0, OP_EQ, smartlist_strings_eq(NULL, sl1));
  1122. tt_int_op(0, OP_EQ, smartlist_strings_eq(sl1, NULL));
  1123. /* Both empty, both equal. */
  1124. EQ_SHOULD_SAY("", "", 1);
  1125. /* One empty, not equal */
  1126. EQ_SHOULD_SAY("", "ab", 0);
  1127. EQ_SHOULD_SAY("", "xy:z", 0);
  1128. EQ_SHOULD_SAY("abc", "", 0);
  1129. EQ_SHOULD_SAY("abc:cd", "", 0);
  1130. /* Different lengths, not equal. */
  1131. EQ_SHOULD_SAY("hello:world", "hello", 0);
  1132. EQ_SHOULD_SAY("hello", "hello:friends", 0);
  1133. /* Same lengths, not equal */
  1134. EQ_SHOULD_SAY("Hello:world", "goodbye:world", 0);
  1135. EQ_SHOULD_SAY("Hello:world", "Hello:stars", 0);
  1136. /* Actually equal */
  1137. EQ_SHOULD_SAY("ABC", "ABC", 1);
  1138. EQ_SHOULD_SAY(" ab : cd : e", " ab : cd : e", 1);
  1139. done:
  1140. SMARTLIST_FOREACH(sl1, char *, cp, tor_free(cp));
  1141. SMARTLIST_FOREACH(sl2, char *, cp, tor_free(cp));
  1142. smartlist_free(sl1);
  1143. smartlist_free(sl2);
  1144. }
  1145. #define CONTAINER_LEGACY(name) \
  1146. { #name, test_container_ ## name , 0, NULL, NULL }
  1147. #define CONTAINER(name, flags) \
  1148. { #name, test_container_ ## name, (flags), NULL, NULL }
  1149. struct testcase_t container_tests[] = {
  1150. CONTAINER_LEGACY(smartlist_basic),
  1151. CONTAINER_LEGACY(smartlist_strings),
  1152. CONTAINER_LEGACY(smartlist_foreach_reverse),
  1153. CONTAINER_LEGACY(smartlist_overlap),
  1154. CONTAINER_LEGACY(smartlist_digests),
  1155. CONTAINER_LEGACY(smartlist_join),
  1156. CONTAINER_LEGACY(smartlist_pos),
  1157. CONTAINER(smartlist_remove, 0),
  1158. CONTAINER(smartlist_ints_eq, 0),
  1159. CONTAINER_LEGACY(bitarray),
  1160. CONTAINER_LEGACY(digestset),
  1161. CONTAINER_LEGACY(strmap),
  1162. CONTAINER_LEGACY(pqueue),
  1163. CONTAINER_LEGACY(order_functions),
  1164. CONTAINER(di_map, 0),
  1165. CONTAINER_LEGACY(fp_pair_map),
  1166. CONTAINER(smartlist_most_frequent, 0),
  1167. CONTAINER(smartlist_sort_ptrs, 0),
  1168. CONTAINER(smartlist_strings_eq, 0),
  1169. END_OF_TESTCASES
  1170. };