bcb4e51a409d94ae670de96afb8483a4f7855294Stephan Bosch/* Copyright (c) 2007-2018 Dovecot authors, see the included COPYING file */
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen#include "test-lib.h"
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen#include "array.h"
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen#include "seq-range-array.h"
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainenstatic void
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainenboundaries_permute(uint32_t *input, unsigned int i, unsigned int count)
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen{
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen ARRAY_TYPE(seq_range) range;
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen const struct seq_range *seqs;
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen unsigned int seqs_count;
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen uint32_t tmp;
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen unsigned int j;
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen if (i+1 < count) {
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen for (j = i; j < count; j++) {
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen tmp = input[i]; input[i] = input[j]; input[j] = tmp;
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen boundaries_permute(input, i+1, count);
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen tmp = input[i]; input[i] = input[j]; input[j] = tmp;
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen }
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen return;
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen }
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen t_array_init(&range, 4);
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen for (i = 0; i < count; i++)
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen seq_range_array_add(&range, input[i]);
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen seqs = array_get(&range, &seqs_count);
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen test_assert(seqs_count == 2);
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen test_assert(seqs[0].seq1 == 0);
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen test_assert(seqs[0].seq2 == 1);
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen test_assert(seqs[1].seq1 == (uint32_t)-2);
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen test_assert(seqs[1].seq2 == (uint32_t)-1);
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen}
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainenstatic void test_seq_range_array_add_boundaries(void)
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen{
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen static uint32_t input[] = { 0, 1, (uint32_t)-2, (uint32_t)-1 };
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen boundaries_permute(input, 0, N_ELEMENTS(input));
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen}
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainenstatic void test_seq_range_array_add_merge(void)
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen{
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen ARRAY_TYPE(seq_range) range;
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen test_begin("seq_range_array_add() merging");
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen t_array_init(&range, 8);
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainen seq_range_array_add(&range, 4);
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainen seq_range_array_add(&range, 1);
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainen seq_range_array_add(&range, 2);
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen test_assert(array_count(&range) == 2);
c8bac7666cdc780a3390110e420350fffb62b909Timo Sirainen
c8bac7666cdc780a3390110e420350fffb62b909Timo Sirainen seq_range_array_add_range(&range, 1, (uint32_t)-1);
c8bac7666cdc780a3390110e420350fffb62b909Timo Sirainen test_assert(array_count(&range) == 1);
c8bac7666cdc780a3390110e420350fffb62b909Timo Sirainen seq_range_array_add_range(&range, 1, (uint32_t)-1);
c8bac7666cdc780a3390110e420350fffb62b909Timo Sirainen test_assert(array_count(&range) == 1);
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen test_end();
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen}
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainenstatic void test_seq_range_array_remove_nth(void)
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen{
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen ARRAY_TYPE(seq_range) range;
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen const struct seq_range *r;
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen test_begin("seq_range_array_remove_nth()");
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen t_array_init(&range, 8);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen seq_range_array_add_range(&range, 1, 5);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen seq_range_array_add(&range, 7);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen seq_range_array_add_range(&range, 10,20);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen test_assert(array_count(&range) == 3);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen seq_range_array_remove_nth(&range, 0, 2);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen r = array_idx(&range, 0); test_assert(r->seq1 == 3 && r->seq2 == 5);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen seq_range_array_remove_nth(&range, 1, 4);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen r = array_idx(&range, 0); test_assert(r->seq1 == 3 && r->seq2 == 3);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen r = array_idx(&range, 1); test_assert(r->seq1 == 11 && r->seq2 == 20);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen seq_range_array_remove_nth(&range, 5, (uint32_t)-1);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen r = array_idx(&range, 1); test_assert(r->seq1 == 11 && r->seq2 == 14);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen test_assert(array_count(&range) == 2);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen test_end();
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen}
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainenstatic void test_seq_range_array_random(void)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen{
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody#define SEQ_RANGE_TEST_BUFSIZE 100
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody#define SEQ_RANGE_TEST_COUNT 20000
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen unsigned char shadowbuf[SEQ_RANGE_TEST_BUFSIZE];
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen ARRAY_TYPE(seq_range) range;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen const struct seq_range *seqs;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen uint32_t seq1, seq2;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen unsigned int i, j, ret, ret2, count;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen int test = -1;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen ret = ret2 = 0;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen i_array_init(&range, 1);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen memset(shadowbuf, 0, sizeof(shadowbuf));
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen for (i = 0; i < SEQ_RANGE_TEST_COUNT; i++) {
62461eb609e1d852e027cf4e07d30d51288678a2Aki Tuomi seq1 = i_rand() % SEQ_RANGE_TEST_BUFSIZE;
62461eb609e1d852e027cf4e07d30d51288678a2Aki Tuomi seq2 = seq1 + i_rand() % (SEQ_RANGE_TEST_BUFSIZE - seq1);
62461eb609e1d852e027cf4e07d30d51288678a2Aki Tuomi test = i_rand() % 4;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen switch (test) {
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen case 0:
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody ret = seq_range_array_add(&range, seq1) ? 0 : 1; /* FALSE == added */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody ret2 = shadowbuf[seq1] == 0 ? 1 : 0;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen shadowbuf[seq1] = 1;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen break;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen case 1:
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody ret = seq_range_array_add_range_count(&range, seq1, seq2);
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody for (ret2 = 0; seq1 <= seq2; seq1++) {
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody if (shadowbuf[seq1] == 0) {
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody ret2++;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody shadowbuf[seq1] = 1;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody }
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen break;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen case 2:
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen ret = seq_range_array_remove(&range, seq1) ? 1 : 0;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen ret2 = shadowbuf[seq1] != 0 ? 1 : 0;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen shadowbuf[seq1] = 0;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen break;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen case 3:
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen ret = seq_range_array_remove_range(&range, seq1, seq2);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen for (ret2 = 0; seq1 <= seq2; seq1++) {
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen if (shadowbuf[seq1] != 0) {
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen ret2++;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen shadowbuf[seq1] = 0;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen break;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen if (ret != ret2)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen break;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen seqs = array_get(&range, &count);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen for (j = 0, seq1 = 0; j < count; j++) {
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen if (j > 0 && seqs[j-1].seq2+1 >= seqs[j].seq1)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen goto fail;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen for (; seq1 < seqs[j].seq1; seq1++) {
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen if (shadowbuf[seq1] != 0)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen goto fail;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen for (; seq1 <= seqs[j].seq2; seq1++) {
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen if (shadowbuf[seq1] == 0)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen goto fail;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen i_assert(seq1 <= SEQ_RANGE_TEST_BUFSIZE);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen for (; seq1 < SEQ_RANGE_TEST_BUFSIZE; seq1++) {
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen if (shadowbuf[seq1] != 0)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen goto fail;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainenfail:
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen if (i == SEQ_RANGE_TEST_COUNT)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen test_out("seq_range_array random", TRUE);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen else {
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen test_out_reason("seq_range_array random", FALSE,
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen t_strdup_printf("round %u test %d failed", i, test));
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
9f5db9cf866a978aab404772a0daf8794069bba5Phil Carmody array_free(&range);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen}
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainenstatic void test_seq_range_array_invert_minmax(uint32_t min, uint32_t max)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen{
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen ARRAY_TYPE(seq_range) range = ARRAY_INIT;
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen struct seq_range_iter iter;
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen unsigned int n, inverse_mask, mask_inside, mask_size = max-min+1;
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen uint32_t seq;
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen i_assert(mask_size <= sizeof(unsigned int)*8);
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen t_array_init(&range, 16);
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen for (unsigned int mask = 0; mask < mask_size; mask++) {
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen array_clear(&range);
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen for (unsigned int i = 0; i < mask_size; i++) {
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen if ((mask & (1 << i)) != 0)
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen seq_range_array_add(&range, min+i);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen seq_range_array_invert(&range, min, max);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen inverse_mask = 0;
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen seq_range_array_iter_init(&iter, &range); n = 0;
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen while (seq_range_array_iter_nth(&iter, n++, &seq)) {
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen test_assert(seq >= min && seq <= max);
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen inverse_mask |= 1 << (seq-min);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen mask_inside = ((1 << mask_size)-1);
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen test_assert_idx((inverse_mask & ~mask_inside) == 0, mask);
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen test_assert_idx(inverse_mask == (mask ^ mask_inside), mask);
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen }
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen}
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainenstatic void test_seq_range_array_invert(void)
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen{
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen test_begin("seq_range_array_invert()");
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen /* first numbers */
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen for (unsigned int min = 0; min <= 7; min++) {
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen for (unsigned int max = min; max <= 7; max++) T_BEGIN {
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen test_seq_range_array_invert_minmax(min, max);
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen } T_END;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen /* last numbers */
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen for (uint64_t min = 0xffffffff-7; min <= 0xffffffff; min++) {
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen for (uint64_t max = min; max <= 0xffffffff; max++) T_BEGIN {
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen test_seq_range_array_invert_minmax(min, max);
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen } T_END;
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen }
f7bd22354fb9311dfbf3e340a69c15d8b00facc1Timo Sirainen test_end();
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen}
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainenstatic void test_seq_range_array_invert_edges(void)
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen{
b7324e421e2132cbbf753e6fdbe675bbaecdf929Timo Sirainen static const struct {
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen int64_t a_seq1, a_seq2, b_seq1, b_seq2;
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen int64_t resa_seq1, resa_seq2, resb_seq1, resb_seq2;
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen } tests[] = {
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen { -1, -1, -1, -1,
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen 0, 0xffffffff, -1, -1 },
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen { 0, 0xffffffff, -1, -1,
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen -1, -1, -1, -1 },
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen { 0, 0xfffffffe, -1, -1,
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen 0xffffffff, 0xffffffff, -1, -1 },
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen { 1, 0xfffffffe, -1, -1,
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen 0, 0, 0xffffffff, 0xffffffff },
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen { 1, 0xffffffff, -1, -1,
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen 0, 0, -1, -1 },
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen { 0, 0, 0xffffffff, 0xffffffff,
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen 1, 0xfffffffe, -1, -1 },
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen { 0xffffffff, 0xffffffff, -1, -1,
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen 0, 0xfffffffe, -1, -1 },
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen };
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen ARRAY_TYPE(seq_range) range = ARRAY_INIT;
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen const struct seq_range *result;
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen unsigned int count;
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen test_begin("seq_range_array_invert() edges");
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen for (unsigned int i = 0; i < N_ELEMENTS(tests); i++) T_BEGIN {
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen t_array_init(&range, 10);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen if (tests[i].a_seq1 != -1)
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen seq_range_array_add_range(&range, tests[i].a_seq1, tests[i].a_seq2);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen if (tests[i].b_seq1 != -1)
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen seq_range_array_add_range(&range, tests[i].b_seq1, tests[i].b_seq2);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen seq_range_array_invert(&range, 0, 0xffffffff);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen result = array_get(&range, &count);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen if (tests[i].resa_seq1 == -1)
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen test_assert_idx(count == 0, i);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen else {
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen test_assert(result[0].seq1 == tests[i].resa_seq1);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen test_assert(result[0].seq2 == tests[i].resa_seq2);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen if (tests[i].resb_seq1 == -1)
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen test_assert_idx(count == 1, i);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen else {
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen test_assert(result[1].seq1 == tests[i].resb_seq1);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen test_assert(result[1].seq2 == tests[i].resb_seq2);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen }
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen }
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen } T_END;
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen test_end();
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen}
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainenstatic void test_seq_range_create(ARRAY_TYPE(seq_range) *array, uint8_t byte)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen{
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen unsigned int i;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen array_clear(array);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen for (i = 0; i < 8; i++) {
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen if ((byte & (1 << i)) != 0)
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainen seq_range_array_add(array, i + 1);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen}
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainenstatic void test_seq_range_array_have_common(void)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen{
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen ARRAY_TYPE(seq_range) arr1, arr2;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen unsigned int i, j;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen bool ret1, ret2, success = TRUE;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen t_array_init(&arr1, 8);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen t_array_init(&arr2, 8);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen for (i = 0; i < 256; i++) {
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen test_seq_range_create(&arr1, i);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen for (j = 0; j < 256; j++) {
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen test_seq_range_create(&arr2, j);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen ret1 = seq_range_array_have_common(&arr1, &arr2);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen ret2 = (i & j) != 0;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen if (ret1 != ret2)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen success = FALSE;
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen }
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen test_out("seq_range_array_have_common()", success);
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen}
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainenvoid test_seq_range_array(void)
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen{
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen test_seq_range_array_add_boundaries();
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen test_seq_range_array_add_merge();
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen test_seq_range_array_remove_nth();
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen test_seq_range_array_invert();
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen test_seq_range_array_invert_edges();
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen test_seq_range_array_have_common();
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen test_seq_range_array_random();
48acc31adebfdd4e4945ee76e1f5259e4b1b6fffTimo Sirainen}