test_containers.c 40 KB

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