1 files changed, 419 insertions, 0 deletions

diff --git a/src/lib/test-seq-range-array.c b/src/lib/test-seq-range-array.c
new file mode 100644
index 0000000..ca0178a
--- /dev/null
+++ b/src/lib/test-seq-range-array.c
@@ -0,0 +1,419 @@
+/* Copyright (c) 2007-2018 Dovecot authors, see the included COPYING file */
+
+#include "test-lib.h"
+#include "array.h"
+#include "seq-range-array.h"
+
+
+static void
+boundaries_permute(uint32_t *input, unsigned int i, unsigned int count)
+{
+	ARRAY_TYPE(seq_range) range;
+	const struct seq_range *seqs;
+	unsigned int seqs_count;
+	uint32_t tmp;
+	unsigned int j;
+
+	if (i+1 < count) {
+		for (j = i; j < count; j++) {
+			tmp = input[i]; input[i] = input[j]; input[j] = tmp;
+			boundaries_permute(input, i+1, count);
+			tmp = input[i]; input[i] = input[j]; input[j] = tmp;
+		}
+		return;
+	}
+	t_array_init(&range, 4);
+	for (i = 0; i < count; i++)
+		seq_range_array_add(&range, input[i]);
+	seqs = array_get(&range, &seqs_count);
+	test_assert(seqs_count == 2);
+	test_assert(seqs[0].seq1 == 0);
+	test_assert(seqs[0].seq2 == 1);
+	test_assert(seqs[1].seq1 == (uint32_t)-2);
+	test_assert(seqs[1].seq2 == (uint32_t)-1);
+}
+
+static void test_seq_range_array_add_boundaries(void)
+{
+	static uint32_t input[] = { 0, 1, (uint32_t)-2, (uint32_t)-1 };
+
+	boundaries_permute(input, 0, N_ELEMENTS(input));
+}
+
+static void test_seq_range_array_add_merge(void)
+{
+	ARRAY_TYPE(seq_range) range;
+
+	test_begin("seq_range_array_add() merging");
+	t_array_init(&range, 8);
+	seq_range_array_add(&range, 4);
+	seq_range_array_add(&range, 1);
+	seq_range_array_add(&range, 2);
+	test_assert(array_count(&range) == 2);
+
+	seq_range_array_add_range(&range, 1, (uint32_t)-1);
+	test_assert(array_count(&range) == 1);
+	seq_range_array_add_range(&range, 1, (uint32_t)-1);
+	test_assert(array_count(&range) == 1);
+	test_end();
+}
+
+static void test_seq_range_array_merge_n(void)
+{
+	ARRAY_TYPE(seq_range) src, dest, dest2;
+	struct seq_range_iter iter;
+	const uint32_t seqs[] = { 4, 5, 7, 8, 9, 11 };
+	uint32_t seq;
+
+	test_begin("seq_range_array_merge_n()");
+	t_array_init(&src, 16);
+	t_array_init(&dest, 16);
+	t_array_init(&dest2, 16);
+	for (unsigned int i = 0; i < N_ELEMENTS(seqs); i++)
+		seq_range_array_add(&src, seqs[i]);
+
+	for (unsigned int i = 0; i <= N_ELEMENTS(seqs); i++) {
+		array_clear(&dest);
+		array_clear(&dest2);
+		seq_range_array_merge_n(&dest, &src, i);
+		test_assert_idx(seq_range_count(&dest) == I_MIN(i, N_ELEMENTS(seqs)), i);
+
+		seq_range_array_iter_init(&iter, &src);
+		for (unsigned int j = 0; j < i; j++) {
+			test_assert_idx(seq_range_array_iter_nth(&iter, j, &seq), i);
+			seq_range_array_add(&dest2, seq);
+		}
+		seq_range_array_invert(&dest2, 1, UINT32_MAX);
+		seq_range_array_intersect(&dest2, &dest);
+		test_assert_idx(array_count(&dest2) == 0, i);
+	}
+	test_end();
+}
+
+static void test_seq_range_array_remove_nth(void)
+{
+	ARRAY_TYPE(seq_range) range;
+	const struct seq_range *r;
+
+	test_begin("seq_range_array_remove_nth()");
+	t_array_init(&range, 8);
+	seq_range_array_add_range(&range, 1, 5);
+	seq_range_array_add(&range, 7);
+	seq_range_array_add_range(&range, 10,20);
+	test_assert(array_count(&range) == 3);
+
+	seq_range_array_remove_nth(&range, 0, 2);
+	r = array_front(&range); test_assert(r->seq1 == 3 && r->seq2 == 5);
+
+	seq_range_array_remove_nth(&range, 1, 4);
+	r = array_front(&range); test_assert(r->seq1 == 3 && r->seq2 == 3);
+	r = array_idx(&range, 1); test_assert(r->seq1 == 11 && r->seq2 == 20);
+
+	seq_range_array_remove_nth(&range, 5, (uint32_t)-1);
+	r = array_idx(&range, 1); test_assert(r->seq1 == 11 && r->seq2 == 14);
+
+	test_assert(array_count(&range) == 2);
+	test_end();
+}
+
+static void test_seq_range_array_remove_range(void)
+{
+	ARRAY_TYPE(seq_range) range;
+	const struct seq_range *r;
+
+	test_begin("seq_range_array_remove_range()");
+	t_array_init(&range, 8);
+
+	seq_range_array_add_range(&range, 0, (uint32_t)-2);
+	test_assert(seq_range_array_remove_range(&range, 0, 2) == 3);
+	r = array_front(&range); test_assert(r->seq1 == 3 && r->seq2 == (uint32_t)-2);
+
+	seq_range_array_add_range(&range, 0, (uint32_t)-2);
+	test_assert(array_count(&range) == 1);
+	test_assert(seq_range_array_remove_range(&range, 0, (uint32_t)-2) == UINT_MAX);
+	test_assert(array_count(&range) == 0);
+
+	seq_range_array_add_range(&range, (uint32_t)-1, (uint32_t)-1);
+	test_assert(seq_range_array_remove_range(&range, (uint32_t)-1, (uint32_t)-1) == 1);
+	test_assert(array_count(&range) == 0);
+
+	seq_range_array_add_range(&range, (uint32_t)-1, (uint32_t)-1);
+	test_assert(seq_range_array_remove_range(&range, 1, (uint32_t)-1) == 1);
+	test_assert(array_count(&range) == 0);
+
+	seq_range_array_add_range(&range, 1, 10);
+	test_assert(seq_range_array_remove_range(&range, 5, 6) == 2);
+	test_assert(seq_range_array_remove_range(&range, 4, 7) == 2);
+	test_assert(seq_range_array_remove_range(&range, 1, 4) == 3);
+	test_assert(seq_range_array_remove_range(&range, 8, 10) == 3);
+	test_assert(array_count(&range) == 0);
+
+	test_end();
+}
+
+static void test_seq_range_array_random(void)
+{
+#define SEQ_RANGE_TEST_BUFSIZE 100
+#define SEQ_RANGE_TEST_COUNT 20000
+	unsigned char shadowbuf[SEQ_RANGE_TEST_BUFSIZE];
+	ARRAY_TYPE(seq_range) range;
+	const struct seq_range *seqs;
+	uint32_t seq1, seq2;
+	unsigned int i, j, ret, ret2, count;
+	int test = -1;
+
+	ret = ret2 = 0;
+	i_array_init(&range, 1);
+	memset(shadowbuf, 0, sizeof(shadowbuf));
+	for (i = 0; i < SEQ_RANGE_TEST_COUNT; i++) {
+		seq1 = i_rand_limit(SEQ_RANGE_TEST_BUFSIZE);
+		seq2 = seq1 + i_rand_limit(SEQ_RANGE_TEST_BUFSIZE - seq1);
+		test = i_rand_limit(4);
+		switch (test) {
+		case 0:
+			ret = seq_range_array_add(&range, seq1) ? 0 : 1; /* FALSE == added */
+			ret2 = shadowbuf[seq1] == 0 ? 1 : 0;
+			shadowbuf[seq1] = 1;
+			break;
+		case 1:
+			ret = seq_range_array_add_range_count(&range, seq1, seq2);
+			for (ret2 = 0; seq1 <= seq2; seq1++) {
+				if (shadowbuf[seq1] == 0) {
+					ret2++;
+					shadowbuf[seq1] = 1;
+				}
+			}
+			break;
+		case 2:
+			ret = seq_range_array_remove(&range, seq1) ? 1 : 0;
+			ret2 = shadowbuf[seq1] != 0 ? 1 : 0;
+			shadowbuf[seq1] = 0;
+			break;
+		case 3:
+			ret = seq_range_array_remove_range(&range, seq1, seq2);
+			for (ret2 = 0; seq1 <= seq2; seq1++) {
+				if (shadowbuf[seq1] != 0) {
+					ret2++;
+					shadowbuf[seq1] = 0;
+				}
+			}
+			break;
+		}
+		if (ret != ret2)
+			break;
+
+		seqs = array_get(&range, &count);
+		for (j = 0, seq1 = 0; j < count; j++) {
+			if (j > 0 && seqs[j-1].seq2+1 >= seqs[j].seq1)
+				goto fail;
+			for (; seq1 < seqs[j].seq1; seq1++) {
+				if (shadowbuf[seq1] != 0)
+					goto fail;
+			}
+			for (; seq1 <= seqs[j].seq2; seq1++) {
+				if (shadowbuf[seq1] == 0)
+					goto fail;
+			}
+		}
+		i_assert(seq1 <= SEQ_RANGE_TEST_BUFSIZE);
+		for (; seq1 < SEQ_RANGE_TEST_BUFSIZE; seq1++) {
+			if (shadowbuf[seq1] != 0)
+				goto fail;
+		}
+	}
+fail:
+	if (i == SEQ_RANGE_TEST_COUNT)
+		test_out("seq_range_array random", TRUE);
+	else {
+		test_out_reason("seq_range_array random", FALSE,
+			t_strdup_printf("round %u test %d failed", i, test));
+	}
+	array_free(&range);
+}
+
+static void test_seq_range_array_invert_minmax(uint32_t min, uint32_t max)
+{
+	ARRAY_TYPE(seq_range) range = ARRAY_INIT;
+	struct seq_range_iter iter;
+	unsigned int n, inverse_mask, mask_inside, mask_size = max-min+1;
+	uint32_t seq;
+
+	i_assert(mask_size <= sizeof(unsigned int)*8);
+	t_array_init(&range, 16);
+	for (unsigned int mask = 0; mask < mask_size; mask++) {
+		array_clear(&range);
+		for (unsigned int i = 0; i < mask_size; i++) {
+			if ((mask & (1 << i)) != 0)
+				seq_range_array_add(&range, min+i);
+		}
+		seq_range_array_invert(&range, min, max);
+
+		inverse_mask = 0;
+		seq_range_array_iter_init(&iter, &range); n = 0;
+		while (seq_range_array_iter_nth(&iter, n++, &seq)) {
+			test_assert(seq >= min && seq <= max);
+			inverse_mask |= 1 << (seq-min);
+		}
+		mask_inside = ((1 << mask_size)-1);
+		test_assert_idx((inverse_mask & ~mask_inside) == 0, mask);
+		test_assert_idx(inverse_mask == (mask ^ mask_inside), mask);
+	}
+}
+
+static void test_seq_range_array_invert(void)
+{
+	test_begin("seq_range_array_invert()");
+	/* first numbers */
+	for (unsigned int min = 0; min <= 7; min++) {
+		for (unsigned int max = min; max <= 7; max++) T_BEGIN {
+			test_seq_range_array_invert_minmax(min, max);
+		} T_END;
+	}
+	/* last numbers */
+	for (uint64_t min = 0xffffffff-7; min <= 0xffffffff; min++) {
+		for (uint64_t max = min; max <= 0xffffffff; max++) T_BEGIN {
+			test_seq_range_array_invert_minmax(min, max);
+		} T_END;
+	}
+	test_end();
+}
+
+static void test_seq_range_array_invert_edges(void)
+{
+	static const struct {
+		int64_t a_seq1, a_seq2, b_seq1, b_seq2;
+		int64_t resa_seq1, resa_seq2, resb_seq1, resb_seq2;
+	} tests[] = {
+		{ -1, -1, -1, -1,
+		  0, 0xffffffff, -1, -1 },
+		/*{ 0, 0xffffffff, -1, -1, too large, will assert-crash
+		  -1, -1, -1, -1 }, */
+		{ 0, 0xfffffffe, -1, -1,
+		  0xffffffff, 0xffffffff, -1, -1 },
+		{ 1, 0xfffffffe, -1, -1,
+		  0, 0, 0xffffffff, 0xffffffff },
+		{ 1, 0xffffffff, -1, -1,
+		  0, 0, -1, -1 },
+		{ 0, 0, 0xffffffff, 0xffffffff,
+		  1, 0xfffffffe, -1, -1 },
+		{ 0xffffffff, 0xffffffff, -1, -1,
+		  0, 0xfffffffe, -1, -1 },
+	};
+	ARRAY_TYPE(seq_range) range = ARRAY_INIT;
+	const struct seq_range *result;
+	unsigned int count;
+
+	test_begin("seq_range_array_invert() edges");
+	for (unsigned int i = 0; i < N_ELEMENTS(tests); i++) T_BEGIN {
+		t_array_init(&range, 10);
+		if (tests[i].a_seq1 != -1)
+			seq_range_array_add_range(&range, tests[i].a_seq1, tests[i].a_seq2);
+		if (tests[i].b_seq1 != -1)
+			seq_range_array_add_range(&range, tests[i].b_seq1, tests[i].b_seq2);
+		seq_range_array_invert(&range, 0, 0xffffffff);
+
+		result = array_get(&range, &count);
+		if (tests[i].resa_seq1 == -1)
+			test_assert_idx(count == 0, i);
+		else {
+			test_assert(result[0].seq1 == tests[i].resa_seq1);
+			test_assert(result[0].seq2 == tests[i].resa_seq2);
+			if (tests[i].resb_seq1 == -1)
+				test_assert_idx(count == 1, i);
+			else {
+				test_assert(result[1].seq1 == tests[i].resb_seq1);
+				test_assert(result[1].seq2 == tests[i].resb_seq2);
+			}
+		}
+	} T_END;
+	test_end();
+}
+
+static void test_seq_range_create(ARRAY_TYPE(seq_range) *array, uint8_t byte)
+{
+	unsigned int i;
+
+	array_clear(array);
+	for (i = 0; i < 8; i++) {
+		if ((byte & (1 << i)) != 0)
+			seq_range_array_add(array, i + 1);
+	}
+}
+
+static void test_seq_range_array_have_common(void)
+{
+	ARRAY_TYPE(seq_range) arr1, arr2;
+	unsigned int i, j;
+	bool ret1, ret2, success = TRUE;
+
+	t_array_init(&arr1, 8);
+	t_array_init(&arr2, 8);
+	for (i = 0; i < 256; i++) {
+		test_seq_range_create(&arr1, i);
+		for (j = 0; j < 256; j++) {
+			test_seq_range_create(&arr2, j);
+			ret1 = seq_range_array_have_common(&arr1, &arr2);
+			ret2 = (i & j) != 0;
+			if (ret1 != ret2)
+				success = FALSE;
+		}
+	}
+	test_out("seq_range_array_have_common()", success);
+}
+
+void test_seq_range_array(void)
+{
+	test_seq_range_array_add_boundaries();
+	test_seq_range_array_add_merge();
+	test_seq_range_array_merge_n();
+	test_seq_range_array_remove_nth();
+	test_seq_range_array_remove_range();
+	test_seq_range_array_invert();
+	test_seq_range_array_invert_edges();
+	test_seq_range_array_have_common();
+	test_seq_range_array_random();
+}
+
+enum fatal_test_state fatal_seq_range_array(unsigned int stage)
+{
+	ARRAY_TYPE(seq_range) arr;
+	struct seq_range *range;
+
+	t_array_init(&arr, 2);
+	switch (stage) {
+	case 0:
+		test_begin("seq_range_array fatals");
+		test_expect_fatal_string("!seq_range_is_overflowed(array)");
+		seq_range_array_add_range(&arr, 0, (uint32_t)-1);
+		return FATAL_TEST_FAILURE;
+	case 1:
+		seq_range_array_add_range(&arr, 1, (uint32_t)-1);
+		test_expect_fatal_string("!seq_range_is_overflowed(array)");
+		seq_range_array_add(&arr, 0);
+		return FATAL_TEST_FAILURE;
+	case 2:
+		seq_range_array_add_range(&arr, 0, (uint32_t)-2);
+		test_expect_fatal_string("!seq_range_is_overflowed(array)");
+		seq_range_array_add(&arr, (uint32_t)-1);
+		return FATAL_TEST_FAILURE;
+	case 3:
+		range = array_append_space(&arr);
+		range->seq2 = (uint32_t)-1;
+		test_expect_fatal_string("range->seq1 > 0 || range->seq2 < (uint32_t)-1");
+		i_error("This shouldn't return: %u", seq_range_count(&arr));
+		return FATAL_TEST_FAILURE;
+	case 4:
+		range = array_append_space(&arr);
+		range->seq2 = (uint32_t)-2;
+		test_assert(seq_range_count(&arr) == (uint32_t)-1);
+
+		range = array_append_space(&arr);
+		range->seq1 = (uint32_t)-2;
+		range->seq2 = (uint32_t)-1;
+		test_expect_fatal_string("UINT_MAX - seq_count >= seq_range_length(range)");
+		i_error("This shouldn't return: %u", seq_range_count(&arr));
+		return FATAL_TEST_FAILURE;
+	}
+	test_end();
+	return FATAL_TEST_FINISHED;
+}