From f7548d6d28c313cf80e6f3ef89aed16a19815df1 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 11:51:24 +0200 Subject: Adding upstream version 1:2.3.19.1+dfsg1. Signed-off-by: Daniel Baumann --- src/lib/test-seq-range-array.c | 419 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 419 insertions(+) create mode 100644 src/lib/test-seq-range-array.c (limited to 'src/lib/test-seq-range-array.c') 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; +} -- cgit v1.2.3