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