test-seq-range-array.c revision 461ffead9720d1e516b959d5e41f049c73d38c7c
5a580c3a38ced62d4bcc95b8ac7c4f2935b5d294Timo Sirainen/* Copyright (c) 2007-2012 Dovecot authors, see the included COPYING file */
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen#include "test-lib.h"
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen#include "array.h"
6967fa47dde9f2726bd86019a50627dacf2d7509Timo Sirainen#include "seq-range-array.h"
34830cefe1757de0ffca67acdc529d5bc8b06b66Timo Sirainen
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen#include <stdlib.h>
6967fa47dde9f2726bd86019a50627dacf2d7509Timo Sirainen
0536ccb51d41e3078c3a9fa33e509fb4b2420f95Timo Sirainenstatic void test_seq_range_array_add_merge(void)
4499995f7029bafd85094694b6a14752ea34c9b3Timo Sirainen{
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen ARRAY_TYPE(seq_range) range;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen
34830cefe1757de0ffca67acdc529d5bc8b06b66Timo Sirainen test_begin("seq_range_array_add() merging");
34830cefe1757de0ffca67acdc529d5bc8b06b66Timo Sirainen t_array_init(&range, 8);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen seq_range_array_add(&range, 4);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen seq_range_array_add(&range, 1);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen seq_range_array_add(&range, 2);
252db51b6c0a605163326b3ea5d09e9936ca3b29Timo Sirainen test_assert(array_count(&range) == 2);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen test_end();
fcca16701767c6b92227a9ee125de69d257882f6Timo Sirainen}
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen
d10cb4d7a80571af21f776c65604442bf09b1765Timo Sirainenstatic void test_seq_range_array_random(void)
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen{
fcca16701767c6b92227a9ee125de69d257882f6Timo Sirainen#define SEQ_RANGE_TEST_BUFSIZE 20
fcca16701767c6b92227a9ee125de69d257882f6Timo Sirainen#define SEQ_RANGE_TEST_COUNT 10000
fcca16701767c6b92227a9ee125de69d257882f6Timo Sirainen unsigned char shadowbuf[SEQ_RANGE_TEST_BUFSIZE];
5702c81e2d788449c3bc207eb9c19e539458ad9eTimo Sirainen ARRAY_TYPE(seq_range) range;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen const struct seq_range *seqs;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen uint32_t seq1, seq2;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen unsigned int i, j, ret, ret2, count;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen int test = -1;
6967fa47dde9f2726bd86019a50627dacf2d7509Timo Sirainen
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen ret = ret2 = 0;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen i_array_init(&range, 1);
e2ce8d4a6ac5d82a906178148453e7613fab9ba0Timo Sirainen memset(shadowbuf, 0, sizeof(shadowbuf));
e2ce8d4a6ac5d82a906178148453e7613fab9ba0Timo Sirainen for (i = 0; i < SEQ_RANGE_TEST_COUNT; i++) {
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen seq1 = rand() % SEQ_RANGE_TEST_BUFSIZE;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen seq2 = seq1 + rand() % (SEQ_RANGE_TEST_BUFSIZE - seq1);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen test = rand() % 4;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen switch (test) {
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen case 0:
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen seq_range_array_add(&range, seq1);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen shadowbuf[seq1] = 1;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen break;
a6f281d078ed03d555802c1a8e15fefce80132dcTimo Sirainen case 1:
a6f281d078ed03d555802c1a8e15fefce80132dcTimo Sirainen seq_range_array_add_range(&range, seq1, seq2);
a6f281d078ed03d555802c1a8e15fefce80132dcTimo Sirainen memset(shadowbuf + seq1, 1, seq2 - seq1 + 1);
a6f281d078ed03d555802c1a8e15fefce80132dcTimo Sirainen break;
a6f281d078ed03d555802c1a8e15fefce80132dcTimo Sirainen case 2:
a6f281d078ed03d555802c1a8e15fefce80132dcTimo Sirainen ret = seq_range_array_remove(&range, seq1) ? 1 : 0;
a6f281d078ed03d555802c1a8e15fefce80132dcTimo Sirainen ret2 = shadowbuf[seq1] != 0 ? 1 : 0;
a6f281d078ed03d555802c1a8e15fefce80132dcTimo Sirainen shadowbuf[seq1] = 0;
a94936bafd127680184da114c6a177b37ff656e5Timo Sirainen break;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen case 3:
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen ret = seq_range_array_remove_range(&range, seq1, seq2);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen for (ret2 = 0; seq1 <= seq2; seq1++) {
5702c81e2d788449c3bc207eb9c19e539458ad9eTimo Sirainen if (shadowbuf[seq1] != 0) {
5702c81e2d788449c3bc207eb9c19e539458ad9eTimo Sirainen ret2++;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen shadowbuf[seq1] = 0;
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen }
a6f281d078ed03d555802c1a8e15fefce80132dcTimo Sirainen }
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen break;
6967fa47dde9f2726bd86019a50627dacf2d7509Timo Sirainen }
6967fa47dde9f2726bd86019a50627dacf2d7509Timo Sirainen if (ret != ret2)
fcca16701767c6b92227a9ee125de69d257882f6Timo Sirainen break;
c1d4780bc0c9017e8e5d366b81e4fad31174c0adTimo Sirainen
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen seqs = array_get(&range, &count);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen for (j = 0, seq1 = 0; j < count; j++) {
252db51b6c0a605163326b3ea5d09e9936ca3b29Timo Sirainen if (j > 0 && seqs[j-1].seq2+1 >= seqs[j].seq1)
a94936bafd127680184da114c6a177b37ff656e5Timo Sirainen goto fail;
a94936bafd127680184da114c6a177b37ff656e5Timo Sirainen for (; seq1 < seqs[j].seq1; seq1++) {
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen if (shadowbuf[seq1] != 0)
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen goto fail;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen }
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen for (; seq1 <= seqs[j].seq2; seq1++) {
597dba3488c648ffb375ee4a552bd52ac4346979Timo Sirainen if (shadowbuf[seq1] == 0)
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen goto fail;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen }
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen }
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen i_assert(seq1 <= SEQ_RANGE_TEST_BUFSIZE);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen for (; seq1 < SEQ_RANGE_TEST_BUFSIZE; seq1++) {
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen if (shadowbuf[seq1] != 0)
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen goto fail;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen }
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen }
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainenfail:
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen if (i == SEQ_RANGE_TEST_COUNT)
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen test_out("seq_range_array random", TRUE);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen else {
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen test_out_reason("seq_range_array random", FALSE,
fcca16701767c6b92227a9ee125de69d257882f6Timo Sirainen t_strdup_printf("round %u test %d failed", i, test));
fcca16701767c6b92227a9ee125de69d257882f6Timo Sirainen }
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen}
fcca16701767c6b92227a9ee125de69d257882f6Timo Sirainen
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainenstatic void test_seq_range_array_invert(void)
5702c81e2d788449c3bc207eb9c19e539458ad9eTimo Sirainen{
34830cefe1757de0ffca67acdc529d5bc8b06b66Timo Sirainen static const unsigned int input_min = 1, input_max = 5;
34830cefe1757de0ffca67acdc529d5bc8b06b66Timo Sirainen static const unsigned int input[] = {
4307c886579381dbb1897ea1388ae6978c96f560Timo Sirainen 1, 2, 3, 4, 5, -1U,
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen 2, 3, 4, -1U,
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen 1, 2, 4, 5, -1U,
34830cefe1757de0ffca67acdc529d5bc8b06b66Timo Sirainen 1, 3, 5, -1U,
5702c81e2d788449c3bc207eb9c19e539458ad9eTimo Sirainen 1, -1U,
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen 5, -1U,
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen -1U
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen };
597dba3488c648ffb375ee4a552bd52ac4346979Timo Sirainen ARRAY_TYPE(seq_range) range = ARRAY_INIT;
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen unsigned int i, j, seq, start, num;
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen bool old_exists, success;
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen for (i = num = 0; input[i] != -1U; num++, i++) {
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen success = TRUE;
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen start = i;
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen for (; input[i] != -1U; i++) {
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen seq_range_array_add_with_init(&range, 32, input[i]);
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen for (j = start; j < i; j++) {
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen if (!seq_range_exists(&range, input[j]))
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen success = FALSE;
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen }
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen }
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen seq_range_array_invert(&range, input_min, input_max);
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen for (seq = input_min; seq <= input_max; seq++) {
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen for (j = start; input[j] != -1U; j++) {
7bcb308d0e13dfa48b483b0addccd889a77bb598Timo Sirainen if (input[j] == seq)
5702c81e2d788449c3bc207eb9c19e539458ad9eTimo Sirainen break;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen }
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen old_exists = input[j] != -1U;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen if (seq_range_exists(&range, seq) == old_exists)
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen success = FALSE;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen }
5069adb2f5b3609fff9a0a705c6edeae56e0030aTimo Sirainen test_out(t_strdup_printf("seq_range_array_invert(%u)", num),
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen success);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen array_free(&range);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen }
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen}
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainenstatic void test_seq_range_create(ARRAY_TYPE(seq_range) *array, uint8_t byte)
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen{
8d56f3334e22619abf56833d290bb1f49ac6722cTimo Sirainen unsigned int i;
8d56f3334e22619abf56833d290bb1f49ac6722cTimo Sirainen
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen array_clear(array);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen for (i = 0; i < 8; i++) {
156736910057b280cb9999d4c6c7221c4c80f5c2Timo Sirainen if ((byte & (1 << i)) != 0)
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen seq_range_array_add(array, i + 1);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen }
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen}
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainenstatic void test_seq_range_array_have_common(void)
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen{
d10cb4d7a80571af21f776c65604442bf09b1765Timo Sirainen ARRAY_TYPE(seq_range) arr1, arr2;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen unsigned int i, j;
81b1d14891415fef0c2f37ef1ef3680cdcc600f1Timo Sirainen bool ret1, ret2, success = TRUE;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen t_array_init(&arr1, 8);
5069adb2f5b3609fff9a0a705c6edeae56e0030aTimo Sirainen t_array_init(&arr2, 8);
5069adb2f5b3609fff9a0a705c6edeae56e0030aTimo Sirainen for (i = 0; i < 256; i++) {
3785910c303507db5f629684e6dde2cc7f83668eTimo Sirainen test_seq_range_create(&arr1, i);
5069adb2f5b3609fff9a0a705c6edeae56e0030aTimo Sirainen for (j = 0; j < 256; j++) {
5069adb2f5b3609fff9a0a705c6edeae56e0030aTimo Sirainen test_seq_range_create(&arr2, j);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen ret1 = seq_range_array_have_common(&arr1, &arr2);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen ret2 = (i & j) != 0;
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen if (ret1 != ret2)
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen success = FALSE;
c09f9f95db314e7482c95e502e1c56ed6c555797Timo Sirainen }
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen }
252db51b6c0a605163326b3ea5d09e9936ca3b29Timo Sirainen test_out("seq_range_array_have_common()", success);
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen}
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainenvoid test_seq_range_array(void)
f2b95f63ebdf77dba4dac938cf8c65c839f1067dTimo Sirainen{
f2b95f63ebdf77dba4dac938cf8c65c839f1067dTimo Sirainen test_seq_range_array_add_merge();
5702c81e2d788449c3bc207eb9c19e539458ad9eTimo Sirainen test_seq_range_array_invert();
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen test_seq_range_array_have_common();
5702c81e2d788449c3bc207eb9c19e539458ad9eTimo Sirainen test_seq_range_array_random();
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen}
2201e2cc1b3f744dac61c2bf8095bcb6b5719540Timo Sirainen