1 /* Copyright (c) 2007-2018 Dovecot authors, see the included COPYING file */
2
3 #include "test-lib.h"
4 #include "array.h"
5 #include "seq-range-array.h"
6
7
8 static void
boundaries_permute(uint32_t * input,unsigned int i,unsigned int count)9 boundaries_permute(uint32_t *input, unsigned int i, unsigned int count)
10 {
11 ARRAY_TYPE(seq_range) range;
12 const struct seq_range *seqs;
13 unsigned int seqs_count;
14 uint32_t tmp;
15 unsigned int j;
16
17 if (i+1 < count) {
18 for (j = i; j < count; j++) {
19 tmp = input[i]; input[i] = input[j]; input[j] = tmp;
20 boundaries_permute(input, i+1, count);
21 tmp = input[i]; input[i] = input[j]; input[j] = tmp;
22 }
23 return;
24 }
25 t_array_init(&range, 4);
26 for (i = 0; i < count; i++)
27 seq_range_array_add(&range, input[i]);
28 seqs = array_get(&range, &seqs_count);
29 test_assert(seqs_count == 2);
30 test_assert(seqs[0].seq1 == 0);
31 test_assert(seqs[0].seq2 == 1);
32 test_assert(seqs[1].seq1 == (uint32_t)-2);
33 test_assert(seqs[1].seq2 == (uint32_t)-1);
34 }
35
test_seq_range_array_add_boundaries(void)36 static void test_seq_range_array_add_boundaries(void)
37 {
38 static uint32_t input[] = { 0, 1, (uint32_t)-2, (uint32_t)-1 };
39
40 boundaries_permute(input, 0, N_ELEMENTS(input));
41 }
42
test_seq_range_array_add_merge(void)43 static void test_seq_range_array_add_merge(void)
44 {
45 ARRAY_TYPE(seq_range) range;
46
47 test_begin("seq_range_array_add() merging");
48 t_array_init(&range, 8);
49 seq_range_array_add(&range, 4);
50 seq_range_array_add(&range, 1);
51 seq_range_array_add(&range, 2);
52 test_assert(array_count(&range) == 2);
53
54 seq_range_array_add_range(&range, 1, (uint32_t)-1);
55 test_assert(array_count(&range) == 1);
56 seq_range_array_add_range(&range, 1, (uint32_t)-1);
57 test_assert(array_count(&range) == 1);
58 test_end();
59 }
60
test_seq_range_array_merge_n(void)61 static void test_seq_range_array_merge_n(void)
62 {
63 ARRAY_TYPE(seq_range) src, dest, dest2;
64 struct seq_range_iter iter;
65 const uint32_t seqs[] = { 4, 5, 7, 8, 9, 11 };
66 uint32_t seq;
67
68 test_begin("seq_range_array_merge_n()");
69 t_array_init(&src, 16);
70 t_array_init(&dest, 16);
71 t_array_init(&dest2, 16);
72 for (unsigned int i = 0; i < N_ELEMENTS(seqs); i++)
73 seq_range_array_add(&src, seqs[i]);
74
75 for (unsigned int i = 0; i <= N_ELEMENTS(seqs); i++) {
76 array_clear(&dest);
77 array_clear(&dest2);
78 seq_range_array_merge_n(&dest, &src, i);
79 test_assert_idx(seq_range_count(&dest) == I_MIN(i, N_ELEMENTS(seqs)), i);
80
81 seq_range_array_iter_init(&iter, &src);
82 for (unsigned int j = 0; j < i; j++) {
83 test_assert_idx(seq_range_array_iter_nth(&iter, j, &seq), i);
84 seq_range_array_add(&dest2, seq);
85 }
86 seq_range_array_invert(&dest2, 1, UINT32_MAX);
87 seq_range_array_intersect(&dest2, &dest);
88 test_assert_idx(array_count(&dest2) == 0, i);
89 }
90 test_end();
91 }
92
test_seq_range_array_remove_nth(void)93 static void test_seq_range_array_remove_nth(void)
94 {
95 ARRAY_TYPE(seq_range) range;
96 const struct seq_range *r;
97
98 test_begin("seq_range_array_remove_nth()");
99 t_array_init(&range, 8);
100 seq_range_array_add_range(&range, 1, 5);
101 seq_range_array_add(&range, 7);
102 seq_range_array_add_range(&range, 10,20);
103 test_assert(array_count(&range) == 3);
104
105 seq_range_array_remove_nth(&range, 0, 2);
106 r = array_front(&range); test_assert(r->seq1 == 3 && r->seq2 == 5);
107
108 seq_range_array_remove_nth(&range, 1, 4);
109 r = array_front(&range); test_assert(r->seq1 == 3 && r->seq2 == 3);
110 r = array_idx(&range, 1); test_assert(r->seq1 == 11 && r->seq2 == 20);
111
112 seq_range_array_remove_nth(&range, 5, (uint32_t)-1);
113 r = array_idx(&range, 1); test_assert(r->seq1 == 11 && r->seq2 == 14);
114
115 test_assert(array_count(&range) == 2);
116 test_end();
117 }
118
test_seq_range_array_remove_range(void)119 static void test_seq_range_array_remove_range(void)
120 {
121 ARRAY_TYPE(seq_range) range;
122 const struct seq_range *r;
123
124 test_begin("seq_range_array_remove_range()");
125 t_array_init(&range, 8);
126
127 seq_range_array_add_range(&range, 0, (uint32_t)-2);
128 test_assert(seq_range_array_remove_range(&range, 0, 2) == 3);
129 r = array_front(&range); test_assert(r->seq1 == 3 && r->seq2 == (uint32_t)-2);
130
131 seq_range_array_add_range(&range, 0, (uint32_t)-2);
132 test_assert(array_count(&range) == 1);
133 test_assert(seq_range_array_remove_range(&range, 0, (uint32_t)-2) == UINT_MAX);
134 test_assert(array_count(&range) == 0);
135
136 seq_range_array_add_range(&range, (uint32_t)-1, (uint32_t)-1);
137 test_assert(seq_range_array_remove_range(&range, (uint32_t)-1, (uint32_t)-1) == 1);
138 test_assert(array_count(&range) == 0);
139
140 seq_range_array_add_range(&range, (uint32_t)-1, (uint32_t)-1);
141 test_assert(seq_range_array_remove_range(&range, 1, (uint32_t)-1) == 1);
142 test_assert(array_count(&range) == 0);
143
144 seq_range_array_add_range(&range, 1, 10);
145 test_assert(seq_range_array_remove_range(&range, 5, 6) == 2);
146 test_assert(seq_range_array_remove_range(&range, 4, 7) == 2);
147 test_assert(seq_range_array_remove_range(&range, 1, 4) == 3);
148 test_assert(seq_range_array_remove_range(&range, 8, 10) == 3);
149 test_assert(array_count(&range) == 0);
150
151 test_end();
152 }
153
test_seq_range_array_random(void)154 static void test_seq_range_array_random(void)
155 {
156 #define SEQ_RANGE_TEST_BUFSIZE 100
157 #define SEQ_RANGE_TEST_COUNT 20000
158 unsigned char shadowbuf[SEQ_RANGE_TEST_BUFSIZE];
159 ARRAY_TYPE(seq_range) range;
160 const struct seq_range *seqs;
161 uint32_t seq1, seq2;
162 unsigned int i, j, ret, ret2, count;
163 int test = -1;
164
165 ret = ret2 = 0;
166 i_array_init(&range, 1);
167 memset(shadowbuf, 0, sizeof(shadowbuf));
168 for (i = 0; i < SEQ_RANGE_TEST_COUNT; i++) {
169 seq1 = i_rand_limit(SEQ_RANGE_TEST_BUFSIZE);
170 seq2 = seq1 + i_rand_limit(SEQ_RANGE_TEST_BUFSIZE - seq1);
171 test = i_rand_limit(4);
172 switch (test) {
173 case 0:
174 ret = seq_range_array_add(&range, seq1) ? 0 : 1; /* FALSE == added */
175 ret2 = shadowbuf[seq1] == 0 ? 1 : 0;
176 shadowbuf[seq1] = 1;
177 break;
178 case 1:
179 ret = seq_range_array_add_range_count(&range, seq1, seq2);
180 for (ret2 = 0; seq1 <= seq2; seq1++) {
181 if (shadowbuf[seq1] == 0) {
182 ret2++;
183 shadowbuf[seq1] = 1;
184 }
185 }
186 break;
187 case 2:
188 ret = seq_range_array_remove(&range, seq1) ? 1 : 0;
189 ret2 = shadowbuf[seq1] != 0 ? 1 : 0;
190 shadowbuf[seq1] = 0;
191 break;
192 case 3:
193 ret = seq_range_array_remove_range(&range, seq1, seq2);
194 for (ret2 = 0; seq1 <= seq2; seq1++) {
195 if (shadowbuf[seq1] != 0) {
196 ret2++;
197 shadowbuf[seq1] = 0;
198 }
199 }
200 break;
201 }
202 if (ret != ret2)
203 break;
204
205 seqs = array_get(&range, &count);
206 for (j = 0, seq1 = 0; j < count; j++) {
207 if (j > 0 && seqs[j-1].seq2+1 >= seqs[j].seq1)
208 goto fail;
209 for (; seq1 < seqs[j].seq1; seq1++) {
210 if (shadowbuf[seq1] != 0)
211 goto fail;
212 }
213 for (; seq1 <= seqs[j].seq2; seq1++) {
214 if (shadowbuf[seq1] == 0)
215 goto fail;
216 }
217 }
218 i_assert(seq1 <= SEQ_RANGE_TEST_BUFSIZE);
219 for (; seq1 < SEQ_RANGE_TEST_BUFSIZE; seq1++) {
220 if (shadowbuf[seq1] != 0)
221 goto fail;
222 }
223 }
224 fail:
225 if (i == SEQ_RANGE_TEST_COUNT)
226 test_out("seq_range_array random", TRUE);
227 else {
228 test_out_reason("seq_range_array random", FALSE,
229 t_strdup_printf("round %u test %d failed", i, test));
230 }
231 array_free(&range);
232 }
233
test_seq_range_array_invert_minmax(uint32_t min,uint32_t max)234 static void test_seq_range_array_invert_minmax(uint32_t min, uint32_t max)
235 {
236 ARRAY_TYPE(seq_range) range = ARRAY_INIT;
237 struct seq_range_iter iter;
238 unsigned int n, inverse_mask, mask_inside, mask_size = max-min+1;
239 uint32_t seq;
240
241 i_assert(mask_size <= sizeof(unsigned int)*8);
242 t_array_init(&range, 16);
243 for (unsigned int mask = 0; mask < mask_size; mask++) {
244 array_clear(&range);
245 for (unsigned int i = 0; i < mask_size; i++) {
246 if ((mask & (1 << i)) != 0)
247 seq_range_array_add(&range, min+i);
248 }
249 seq_range_array_invert(&range, min, max);
250
251 inverse_mask = 0;
252 seq_range_array_iter_init(&iter, &range); n = 0;
253 while (seq_range_array_iter_nth(&iter, n++, &seq)) {
254 test_assert(seq >= min && seq <= max);
255 inverse_mask |= 1 << (seq-min);
256 }
257 mask_inside = ((1 << mask_size)-1);
258 test_assert_idx((inverse_mask & ~mask_inside) == 0, mask);
259 test_assert_idx(inverse_mask == (mask ^ mask_inside), mask);
260 }
261 }
262
test_seq_range_array_invert(void)263 static void test_seq_range_array_invert(void)
264 {
265 test_begin("seq_range_array_invert()");
266 /* first numbers */
267 for (unsigned int min = 0; min <= 7; min++) {
268 for (unsigned int max = min; max <= 7; max++) T_BEGIN {
269 test_seq_range_array_invert_minmax(min, max);
270 } T_END;
271 }
272 /* last numbers */
273 for (uint64_t min = 0xffffffff-7; min <= 0xffffffff; min++) {
274 for (uint64_t max = min; max <= 0xffffffff; max++) T_BEGIN {
275 test_seq_range_array_invert_minmax(min, max);
276 } T_END;
277 }
278 test_end();
279 }
280
test_seq_range_array_invert_edges(void)281 static void test_seq_range_array_invert_edges(void)
282 {
283 static const struct {
284 int64_t a_seq1, a_seq2, b_seq1, b_seq2;
285 int64_t resa_seq1, resa_seq2, resb_seq1, resb_seq2;
286 } tests[] = {
287 { -1, -1, -1, -1,
288 0, 0xffffffff, -1, -1 },
289 /*{ 0, 0xffffffff, -1, -1, too large, will assert-crash
290 -1, -1, -1, -1 }, */
291 { 0, 0xfffffffe, -1, -1,
292 0xffffffff, 0xffffffff, -1, -1 },
293 { 1, 0xfffffffe, -1, -1,
294 0, 0, 0xffffffff, 0xffffffff },
295 { 1, 0xffffffff, -1, -1,
296 0, 0, -1, -1 },
297 { 0, 0, 0xffffffff, 0xffffffff,
298 1, 0xfffffffe, -1, -1 },
299 { 0xffffffff, 0xffffffff, -1, -1,
300 0, 0xfffffffe, -1, -1 },
301 };
302 ARRAY_TYPE(seq_range) range = ARRAY_INIT;
303 const struct seq_range *result;
304 unsigned int count;
305
306 test_begin("seq_range_array_invert() edges");
307 for (unsigned int i = 0; i < N_ELEMENTS(tests); i++) T_BEGIN {
308 t_array_init(&range, 10);
309 if (tests[i].a_seq1 != -1)
310 seq_range_array_add_range(&range, tests[i].a_seq1, tests[i].a_seq2);
311 if (tests[i].b_seq1 != -1)
312 seq_range_array_add_range(&range, tests[i].b_seq1, tests[i].b_seq2);
313 seq_range_array_invert(&range, 0, 0xffffffff);
314
315 result = array_get(&range, &count);
316 if (tests[i].resa_seq1 == -1)
317 test_assert_idx(count == 0, i);
318 else {
319 test_assert(result[0].seq1 == tests[i].resa_seq1);
320 test_assert(result[0].seq2 == tests[i].resa_seq2);
321 if (tests[i].resb_seq1 == -1)
322 test_assert_idx(count == 1, i);
323 else {
324 test_assert(result[1].seq1 == tests[i].resb_seq1);
325 test_assert(result[1].seq2 == tests[i].resb_seq2);
326 }
327 }
328 } T_END;
329 test_end();
330 }
331
test_seq_range_create(ARRAY_TYPE (seq_range)* array,uint8_t byte)332 static void test_seq_range_create(ARRAY_TYPE(seq_range) *array, uint8_t byte)
333 {
334 unsigned int i;
335
336 array_clear(array);
337 for (i = 0; i < 8; i++) {
338 if ((byte & (1 << i)) != 0)
339 seq_range_array_add(array, i + 1);
340 }
341 }
342
test_seq_range_array_have_common(void)343 static void test_seq_range_array_have_common(void)
344 {
345 ARRAY_TYPE(seq_range) arr1, arr2;
346 unsigned int i, j;
347 bool ret1, ret2, success = TRUE;
348
349 t_array_init(&arr1, 8);
350 t_array_init(&arr2, 8);
351 for (i = 0; i < 256; i++) {
352 test_seq_range_create(&arr1, i);
353 for (j = 0; j < 256; j++) {
354 test_seq_range_create(&arr2, j);
355 ret1 = seq_range_array_have_common(&arr1, &arr2);
356 ret2 = (i & j) != 0;
357 if (ret1 != ret2)
358 success = FALSE;
359 }
360 }
361 test_out("seq_range_array_have_common()", success);
362 }
363
test_seq_range_array(void)364 void test_seq_range_array(void)
365 {
366 test_seq_range_array_add_boundaries();
367 test_seq_range_array_add_merge();
368 test_seq_range_array_merge_n();
369 test_seq_range_array_remove_nth();
370 test_seq_range_array_remove_range();
371 test_seq_range_array_invert();
372 test_seq_range_array_invert_edges();
373 test_seq_range_array_have_common();
374 test_seq_range_array_random();
375 }
376
fatal_seq_range_array(unsigned int stage)377 enum fatal_test_state fatal_seq_range_array(unsigned int stage)
378 {
379 ARRAY_TYPE(seq_range) arr;
380 struct seq_range *range;
381
382 t_array_init(&arr, 2);
383 switch (stage) {
384 case 0:
385 test_begin("seq_range_array fatals");
386 test_expect_fatal_string("!seq_range_is_overflowed(array)");
387 seq_range_array_add_range(&arr, 0, (uint32_t)-1);
388 return FATAL_TEST_FAILURE;
389 case 1:
390 seq_range_array_add_range(&arr, 1, (uint32_t)-1);
391 test_expect_fatal_string("!seq_range_is_overflowed(array)");
392 seq_range_array_add(&arr, 0);
393 return FATAL_TEST_FAILURE;
394 case 2:
395 seq_range_array_add_range(&arr, 0, (uint32_t)-2);
396 test_expect_fatal_string("!seq_range_is_overflowed(array)");
397 seq_range_array_add(&arr, (uint32_t)-1);
398 return FATAL_TEST_FAILURE;
399 case 3:
400 range = array_append_space(&arr);
401 range->seq2 = (uint32_t)-1;
402 test_expect_fatal_string("range->seq1 > 0 || range->seq2 < (uint32_t)-1");
403 i_error("This shouldn't return: %u", seq_range_count(&arr));
404 return FATAL_TEST_FAILURE;
405 case 4:
406 range = array_append_space(&arr);
407 range->seq2 = (uint32_t)-2;
408 test_assert(seq_range_count(&arr) == (uint32_t)-1);
409
410 range = array_append_space(&arr);
411 range->seq1 = (uint32_t)-2;
412 range->seq2 = (uint32_t)-1;
413 test_expect_fatal_string("UINT_MAX - seq_count >= seq_range_length(range)");
414 i_error("This shouldn't return: %u", seq_range_count(&arr));
415 return FATAL_TEST_FAILURE;
416 }
417 test_end();
418 return FATAL_TEST_FINISHED;
419 }
420