path: root/src/lib/test-seq-range-array.c

/* 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;
}