Mercurial > dovecot > core-2.2
view src/lib/test-seq-range-array.c @ 22656:1789bf2a1e01
director: Make sure HOST-RESET-USERS isn't used with max_moving_users=0
The reset command would just hang in that case. doveadm would never have
sent this, so this is just an extra sanity check.
author | Timo Sirainen <timo.sirainen@dovecot.fi> |
---|---|
date | Sun, 05 Nov 2017 23:51:56 +0200 |
parents | 2e2563132d5f |
children | cb108f786fb4 |
line wrap: on
line source
/* Copyright (c) 2007-2017 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) { 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(); }