src/lib/test-seq-range-array.c

	test-seq-range-array.c revision b7324e421e2132cbbf753e6fdbe675bbaecdf929
/* Copyright (c) 2007-2016 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_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_idx(&range, 0); test_assert(r->seq1 == 3 && r->seq2 == 5);

    seq_range_array_remove_nth(&range, 1, 4);
    r = array_idx(&range, 0); 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_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 = rand() % SEQ_RANGE_TEST_BUFSIZE;
        seq2 = seq1 + rand() % (SEQ_RANGE_TEST_BUFSIZE - seq1);
        test = rand() % 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,
          -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_remove_nth();
    test_seq_range_array_invert();
    test_seq_range_array_invert_edges();
    test_seq_range_array_have_common();
    test_seq_range_array_random();
}