test_containers.c 40 KB

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