1 /* Copyright (c) 2007-2018 Dovecot authors, see the included COPYING file */
2
3 #include "test-lib.h"
4 #include "array.h"
5
6
7 struct foo {
8 unsigned int a, b, c;
9 };
10
test_array_elem(void)11 static void test_array_elem(void)
12 {
13 ARRAY(struct foo *) foos;
14 struct foo *nfoo;
15 struct foo *foo;
16 struct foo local_foo;
17 unsigned int i;
18
19 test_begin("array elem");
20 t_array_init(&foos, 32);
21
22 foo = &local_foo;
23 array_foreach_elem(&foos, foo)
24 test_assert(FALSE);
25 test_assert(foo == &local_foo);
26
27 for (i = 1; i <= 3; i++) {
28 nfoo = t_new(struct foo, 1);
29 nfoo->a = i;
30 array_push_back(&foos, &nfoo);
31 }
32
33 struct foo *const *foo_p = array_idx(&foos, 1);
34 unsigned int idx = 1;
35 foo = array_idx_elem(&foos, idx++);
36 /* make sure idx isn't expanded multiple times in the macro */
37 test_assert(idx == 2);
38 test_assert(*foo_p == foo);
39
40 i = 1;
41 array_foreach_elem(&foos, foo) {
42 test_assert(foo->a == i);
43 i++;
44 }
45 test_assert(foo->a == i-1);
46 test_end();
47 }
48
test_array_count(void)49 static void test_array_count(void)
50 {
51 ARRAY(struct foo) foos;
52 struct foo nfoo;
53
54 test_begin("array count/empty");
55 t_array_init(&foos, 32);
56
57 test_assert(array_count(&foos) == 0);
58 test_assert(array_is_empty(&foos));
59 test_assert(!array_not_empty(&foos));
60 nfoo.a = nfoo.b = nfoo.c = 9;
61 array_push_back(&foos, &nfoo);
62 test_assert(array_count(&foos) == 1);
63 test_assert(!array_is_empty(&foos));
64 test_assert(array_not_empty(&foos));
65
66 test_end();
67 }
test_array_foreach(void)68 static void test_array_foreach(void)
69 {
70 ARRAY(struct foo) foos;
71 const struct foo *foo;
72 struct foo nfoo;
73 unsigned int i;
74
75 test_begin("array foreach");
76 t_array_init(&foos, 32);
77 for (i = 0; i < 10; i++) {
78 nfoo.a = nfoo.b = nfoo.c = i;
79 array_push_back(&foos, &nfoo);
80 }
81
82 array_foreach(&foos, foo) {
83 i = array_foreach_idx(&foos, foo);
84 test_assert(foo->a == i);
85 test_assert(foo->b == i);
86 test_assert(foo->c == i);
87 }
88 /* points past the last element */
89 test_assert(foo == array_idx(&foos, i)+1);
90 test_end();
91 }
92
test_array_foreach_reverse(void)93 static void test_array_foreach_reverse(void)
94 {
95 ARRAY(unsigned int) arr;
96 const unsigned int *i_p;
97 unsigned int i, i2, *imod_p;
98
99 test_begin("array foreach reverse");
100 t_array_init(&arr, 32);
101
102 /* first test that array_foreach() + array_delete() doesn't really
103 work as we might hope.. */
104 for (i = 1; i <= 5; i++)
105 array_push_back(&arr, &i);
106 array_foreach(&arr, i_p) {
107 i = array_foreach_idx(&arr, i_p);
108 array_delete(&arr, i, 1);
109 }
110 test_assert(array_count(&arr) == 2);
111
112 /* but using array_foreach_reverse() + array_delete() does work: */
113 array_clear(&arr);
114 i2 = 5;
115 for (i = 1; i <= i2; i++)
116 array_push_back(&arr, &i);
117 array_foreach_reverse(&arr, i_p) {
118 i = array_foreach_idx(&arr, i_p);
119 test_assert(*i_p == i2);
120 test_assert(*i_p == i + 1);
121 array_delete(&arr, i, 1);
122 i2--;
123 }
124 test_assert(array_count(&arr) == 0);
125
126 /* also array_foreach_reverse_modifiable() + array_delete() works: */
127 i2 = 5;
128 for (i = 1; i <= i2; i++)
129 array_push_back(&arr, &i);
130 array_foreach_reverse_modifiable(&arr, imod_p) {
131 i = array_foreach_idx(&arr, imod_p);
132 test_assert(*imod_p == i2);
133 test_assert(*imod_p == i + 1);
134 array_delete(&arr, i, 1);
135 i2--;
136 }
137 test_assert(array_count(&arr) == 0);
138
139 test_end();
140 }
141
test_array_foreach_elem_string(void)142 static void test_array_foreach_elem_string(void)
143 {
144 ARRAY(char *) blurbs;
145 ARRAY(const char *) cblurbs;
146 char *string;
147 const char *cstring;
148 int i;
149
150 test_begin("array foreach_elem ro/rw strings");
151 t_array_init(&blurbs, 32);
152 t_array_init(&cblurbs, 32);
153 for (i = 0; i < 10; i++) {
154 cstring = t_strdup_printf("x%iy", i);
155 string = t_strdup_noconst(cstring);
156 array_push_back(&blurbs, &string);
157 array_push_back(&cblurbs, &cstring);
158 }
159
160 i = 0;
161 array_foreach_elem(&blurbs, string) {
162 test_assert_idx(string[0] == 'x' && string[1]-'0' == i && string[2] == 'y', i);
163 i++;
164 }
165 i = 0;
166 array_foreach_elem(&cblurbs, cstring) {
167 test_assert_idx(cstring[0] == 'x' && cstring[1]-'0' == i && cstring[2] == 'y', i);
168 i++;
169 }
170 test_end();
171 }
172
test_int_compare(const int * key,const int * elem)173 static int test_int_compare(const int *key, const int *elem)
174 {
175 return (*key < *elem) ? -1 :
176 (*key > *elem) ? 1 :
177 0;
178 }
test_array_reverse(void)179 static void test_array_reverse(void)
180 {
181 ARRAY(int) intarr;
182 int input[] = { -1234567890, -272585721, 272485922, 824725652 };
183 const int tmpi = 999, *output;
184 unsigned int i, j;
185
186 test_begin("array reverse");
187 t_array_init(&intarr, 5);
188 for (i = 0; i <= N_ELEMENTS(input); i++) {
189 array_clear(&intarr);
190 array_append(&intarr, input, i);
191 array_reverse(&intarr);
192
193 output = i == 0 ? NULL : array_front(&intarr);
194 for (j = 0; j < i; j++)
195 test_assert(input[i-j-1] == output[j]);
196 }
197 test_end();
198
199 test_begin("array_lsearch");
200 for (i = 0; i < N_ELEMENTS(input); i++) {
201 output = array_lsearch(&intarr, &input[i], test_int_compare);
202 test_assert(output != NULL);
203 j = array_ptr_to_idx(&intarr, output);
204 test_assert_idx(j == N_ELEMENTS(input) - 1 - i, i);
205 }
206 output = array_lsearch(&intarr, &tmpi, test_int_compare);
207 test_assert(output == NULL);
208 test_end();
209 }
test_compare_ushort(const unsigned short * c1,const unsigned short * c2)210 static int test_compare_ushort(const unsigned short *c1, const unsigned short *c2)
211 {
212 return *c1 > *c2 ? 1
213 : *c1 < *c2 ? -1
214 : 0;
215 }
test_compare_ushort_fuzz(const unsigned short * c1,const unsigned short * c2,const int * pfuzz)216 static int test_compare_ushort_fuzz(const unsigned short *c1, const unsigned short *c2, const int *pfuzz)
217 {
218 int d = (int)*c1 - (int)*c2;
219 if (d <= *pfuzz && -d <= *pfuzz)
220 return 0;
221 return d;
222 }
test_array_cmp(void)223 static void test_array_cmp(void)
224 {
225 static const unsigned short deltas[] = {
226 0x8000, 0xc000, 0xfe00, 0xff00, 0xff80, 0xffc0, 0xfffe, 0xffff,
227 0, 1, 2, 64, 128, 256, 512, 16384, 32768
228 };
229
230 #define NELEMS 5u
231 ARRAY(unsigned short) arr1, arr2;
232 unsigned short elems[NELEMS+1];
233 unsigned int i;
234 int fuzz;
235
236 test_begin("array compare (ushort)");
237 t_array_init(&arr1, NELEMS);
238 t_array_init(&arr2, NELEMS);
239 for (i = 0; i < NELEMS; i++) {
240 elems[i] = i_rand_ushort();
241 array_push_back(&arr2, &elems[i]);
242 }
243 array_append(&arr1, elems, NELEMS);
244 test_assert(array_cmp(&arr1, &arr2) == TRUE);
245 test_assert(array_equal_fn(&arr1, &arr2, test_compare_ushort) == TRUE);
246 fuzz = 0;
247 test_assert(array_equal_fn_ctx(&arr1, &arr2, test_compare_ushort_fuzz, &fuzz) == TRUE);
248
249 for (i = 0; i < 256; i++) {
250 unsigned int j = i_rand_limit(NELEMS);
251 const unsigned short *ptmp = array_idx(&arr2, j);
252 unsigned short tmp = *ptmp;
253 unsigned short repl = ((unsigned int)tmp +
254 deltas[i_rand_limit(N_ELEMENTS(deltas))]) & 0xffff;
255
256 array_idx_set(&arr2, j, &repl);
257 test_assert_idx(array_cmp(&arr1, &arr2) == (tmp == repl), i);
258 test_assert_idx(array_equal_fn(&arr1, &arr2, test_compare_ushort) == (tmp == repl), i);
259 fuzz = (int)tmp - (int)repl;
260 if (fuzz < 0)
261 fuzz = -fuzz;
262 test_assert_idx(array_equal_fn_ctx(&arr1, &arr2, test_compare_ushort_fuzz, &fuzz) == TRUE, i);
263 if (fuzz > 0) {
264 fuzz--;
265 test_assert_idx(array_equal_fn_ctx(&arr1, &arr2, test_compare_ushort_fuzz, &fuzz) == FALSE, i);
266 }
267 array_idx_set(&arr2, j, &tmp);
268 test_assert_idx(array_cmp(&arr1, &arr2) == TRUE, i);
269 test_assert_idx(array_equal_fn(&arr1, &arr2, test_compare_ushort) == TRUE, i);
270 fuzz = 0;
271 test_assert_idx(array_equal_fn_ctx(&arr1, &arr2, test_compare_ushort_fuzz, &fuzz) == TRUE, i);
272 }
273 elems[NELEMS] = 0;
274 array_push_back(&arr2, &elems[NELEMS]);
275 test_assert(array_cmp(&arr1, &arr2) == FALSE);
276 test_assert(array_equal_fn(&arr1, &arr2, test_compare_ushort) == FALSE);
277 test_assert_idx(array_equal_fn_ctx(&arr1, &arr2, test_compare_ushort_fuzz, &fuzz) == FALSE, i);
278
279 test_end();
280 }
281
test_array_cmp_str(void)282 static void test_array_cmp_str(void)
283 {
284 #define NELEMS 5u
285 ARRAY(const char *) arr1, arr2;
286 const char *elemstrs[NELEMS+1];
287 unsigned int i;
288
289 test_begin("array compare (char*)");
290 t_array_init(&arr1, NELEMS);
291 t_array_init(&arr2, NELEMS);
292 for (i = 0; i < NELEMS; i++) {
293 elemstrs[i] = t_strdup_printf("%x", i_rand()); /* never 0-length */
294 array_push_back(&arr2, &elemstrs[i]);
295 }
296 array_append(&arr1, elemstrs, NELEMS);
297 test_assert(array_cmp(&arr1, &arr2) == TRUE); /* pointers shared, so identical */
298 test_assert(array_equal_fn(&arr1, &arr2, i_strcmp_p) == TRUE); /* therefore value same */
299 for (i = 0; i < 2560; i++) {
300 unsigned int j = i_rand_limit(NELEMS);
301 const char *const *ostr_p = array_idx(&arr2, j);
302 const char *ostr = *ostr_p;
303 unsigned int olen = strlen(ostr);
304 unsigned int rc = i_rand_limit(olen + 1);
305 char ochar = ostr[rc];
306 char buf[12];
307 const char *bufp = buf;
308 memcpy(buf, ostr, olen+1);
309 buf[rc] = (int32_t)i_rand_limit(CHAR_MAX + 1 - CHAR_MIN) + CHAR_MIN;
310 if(rc == olen)
311 buf[rc+1] = '\0';
312 array_idx_set(&arr2, j, &bufp);
313 test_assert(array_cmp(&arr1, &arr2) == FALSE); /* pointers now differ */
314 test_assert_idx(array_equal_fn(&arr1, &arr2, i_strcmp_p)
315 == (strcmp(ostr, buf) == 0), i); /* sometimes still the same */
316 test_assert_idx(array_equal_fn(&arr1, &arr2, i_strcmp_p)
317 == (ochar == buf[rc]), i); /* ditto */
318 array_idx_set(&arr2, j, &ostr);
319 test_assert(array_cmp(&arr1, &arr2) == TRUE); /* pointers now same again */
320 test_assert_idx(array_equal_fn(&arr1, &arr2, i_strcmp_p) == TRUE, i); /* duh! */
321 }
322 /* length differences being detected are tested in other tests */
323 test_end();
324 }
325
326 static void
test_array_free_case(bool keep)327 test_array_free_case(bool keep)
328 {
329 pool_t pool = pool_allocfree_create("array test");
330 ARRAY(int) r;
331 int *p;
332
333 test_begin(keep ? "array_free" : "array_free_without_data");
334
335 p_array_init(&r, pool, 100);
336 array_append_zero(&r);
337 if (keep) {
338 p = array_free_without_data(&r);
339 test_assert(pool_allocfree_get_total_used_size(pool)>=400);
340 p_free(pool, p);
341 } else {
342 array_free(&r);
343 test_assert(pool_allocfree_get_total_used_size(pool)==0);
344 }
345 pool_unref(&pool);
346 test_end();
347 }
348 static void
test_array_free(void)349 test_array_free(void)
350 {
351 test_array_free_case(FALSE);
352 test_array_free_case(TRUE);
353 }
354
test_array(void)355 void test_array(void)
356 {
357 test_array_elem();
358 test_array_count();
359 test_array_foreach();
360 test_array_foreach_reverse();
361 test_array_foreach_elem_string();
362 test_array_reverse();
363 test_array_cmp();
364 test_array_cmp_str();
365 test_array_free();
366 }
367
fatal_array(unsigned int stage)368 enum fatal_test_state fatal_array(unsigned int stage)
369 {
370 double tmpd[2] = { 42., -42. };
371 short tmps[8] = {1,2,3,4,5,6,7,8};
372 static const void *useless_ptr; /* persuade gcc to not optimise the tests */
373
374 switch(stage) {
375 case 0: {
376 ARRAY(double) ad;
377 test_begin("fatal_array");
378 t_array_init(&ad, 3);
379 /* allocation big enough, but memory not initialised */
380 test_expect_fatal_string("(array_idx_i): assertion failed: (idx < array->buffer->used / array->element_size)");
381 useless_ptr = array_front(&ad);
382 return FATAL_TEST_FAILURE;
383 }
384
385 case 1: {
386 ARRAY(double) ad;
387 t_array_init(&ad, 2);
388 array_append(&ad, tmpd, 2);
389 /* actual out of range address requested */
390 test_expect_fatal_string("(array_idx_i): assertion failed: (idx < array->buffer->used / array->element_size)");
391 useless_ptr = array_idx(&ad, 2);
392 return FATAL_TEST_FAILURE;
393 }
394
395 case 2: {
396 ARRAY(double) ad;
397 ARRAY(short) as;
398 t_array_init(&ad, 2);
399 t_array_init(&as, 8);
400 array_append(&as, tmps, 2);
401 /* can't copy different array sizes */
402 test_expect_fatal_string("(array_copy): assertion failed: (dest->element_size == src->element_size)");
403 array_copy(&ad.arr, 1, &as.arr, 0, 4);
404 return FATAL_TEST_FAILURE;
405 }
406 case 3: {
407 ARRAY(uint8_t) arr;
408 /* Allocate value dynamically, so compiler won't know the
409 allocated memory size and output a warning that it's too
410 small for array_append(). */
411 uint8_t *value = t_malloc0(1);
412
413 t_array_init(&arr, 2);
414 array_push_back(&arr, value);
415 test_expect_fatal_string("Buffer write out of range");
416 /* this is supposed to assert-crash before it even attempts to
417 access value */
418 array_append(&arr, value, UINT_MAX);
419 return FATAL_TEST_FAILURE;
420 }
421 case 4: {
422 ARRAY(uint32_t) arr;
423 /* Allocate value dynamically (see above for reasoning). */
424 uint32_t *value = t_malloc0(1);
425
426 t_array_init(&arr, 2);
427 array_push_back(&arr, value);
428 test_expect_fatal_string("Buffer write out of range");
429 /* this is supposed to assert-crash before it even attempts to
430 access value */
431 array_append(&arr, value, UINT_MAX);
432 return FATAL_TEST_FAILURE;
433 }
434 }
435 test_end();
436 /* Forces the compiler to check the value of useless_ptr, so that it
437 must call array_idx (which is marked as pure, and gcc was desperate
438 to optimise out. Of course, gcc is unaware stage is never UINT_MAX.*/
439 return (useless_ptr != NULL && stage == UINT_MAX)
440 ? FATAL_TEST_FAILURE : FATAL_TEST_FINISHED;
441 }
442