Mercurial > dovecot > original-hg > dovecot-2.2
changeset 6758:3896c75bfaa8 HEAD
Added seq_range_array_invert()
author | Timo Sirainen <tss@iki.fi> |
---|---|
date | Sat, 10 Nov 2007 19:16:01 +0200 |
parents | f7aea3542cce |
children | 8e0d9821c0d7 |
files | src/lib/seq-range-array.c src/lib/seq-range-array.h src/tests/test-lib.c |
diffstat | 3 files changed, 100 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/src/lib/seq-range-array.c Sat Nov 10 18:10:18 2007 +0200 +++ b/src/lib/seq-range-array.c Sat Nov 10 19:16:01 2007 +0200 @@ -218,3 +218,53 @@ return seq_range_lookup(array, seq, &idx); } + +void seq_range_array_invert(ARRAY_TYPE(seq_range) *array, + uint32_t min_seq, uint32_t max_seq) +{ + struct seq_range *range, value; + unsigned int i, count; + uint32_t next_min_seq; + + if (array_is_created(array)) + range = array_get_modifiable(array, &count); + else { + range = NULL; + count = 0; + } + if (count == 0) { + /* empty -> full */ + if (!array_is_created(array)) + i_array_init(array, 4); + value.seq1 = min_seq; + value.seq2 = max_seq; + array_append(array, &value, 1); + return; + } + i_assert(range[0].seq1 >= min_seq); + i_assert(range[count-1].seq2 <= max_seq); + + if (range[0].seq1 == min_seq && range[0].seq2 == max_seq) { + /* full -> empty */ + array_clear(array); + return; + } + + for (i = 0; i < count; ) { + next_min_seq = range[i].seq2 + 1; + if (range[i].seq1 == min_seq) { + array_delete(array, i, 1); + range = array_get_modifiable(array, &count); + } else { + range[i].seq2 = range[i].seq1 - 1; + range[i].seq1 = min_seq; + i++; + } + min_seq = next_min_seq; + } + if (min_seq <= max_seq) { + value.seq1 = min_seq; + value.seq2 = max_seq; + array_append(array, &value, 1); + } +}
--- a/src/lib/seq-range-array.h Sat Nov 10 18:10:18 2007 +0200 +++ b/src/lib/seq-range-array.h Sat Nov 10 19:16:01 2007 +0200 @@ -19,4 +19,8 @@ /* Returns TRUE if sequence exists in the range. */ bool seq_range_exists(const ARRAY_TYPE(seq_range) *array, uint32_t seq); +/* Invert the sequence range. For example 5:6 -> min_seq:4,7:max_seq. */ +void seq_range_array_invert(ARRAY_TYPE(seq_range) *array, + uint32_t min_seq, uint32_t max_seq); + #endif
--- a/src/tests/test-lib.c Sat Nov 10 18:10:18 2007 +0200 +++ b/src/tests/test-lib.c Sat Nov 10 19:16:01 2007 +0200 @@ -1,9 +1,11 @@ /* Copyright (c) 2007 Dovecot authors, see the included COPYING file */ #include "test-lib.h" +#include "array.h" #include "str.h" #include "base64.h" #include "bsearch-insert-pos.h" +#include "seq-range-array.h" static void test_base64_encode(void) { @@ -120,6 +122,49 @@ } } +static void test_seq_range_array(void) +{ + static const unsigned int input_min = 1, input_max = 5; + static const unsigned int input[] = { + 1, 2, 3, 4, 5, -1U, + 2, 3, 4, -1U, + 1, 2, 4, 5, -1U, + 1, 3, 5, -1U, + 1, -1U, + 5, -1U, + -1U + }; + ARRAY_TYPE(seq_range) range = ARRAY_INIT; + unsigned int i, j, seq, start, num; + bool old_exists, success; + + for (i = num = 0; input[i] != -1U; num++, i++) { + success = TRUE; + start = i; + for (; input[i] != -1U; i++) { + seq_range_array_add(&range, 32, input[i]); + for (j = start; j < i; j++) { + if (!seq_range_exists(&range, input[j])) + success = FALSE; + } + } + + seq_range_array_invert(&range, input_min, input_max); + for (seq = input_min; seq <= input_max; seq++) { + for (j = start; input[j] != -1U; j++) { + if (input[j] == seq) + break; + } + old_exists = input[j] != -1U; + if (seq_range_exists(&range, seq) == old_exists) + success = FALSE; + } + test_out(t_strdup_printf("seq_range_array_invert(%u)", num), + success); + array_free(&range); + } +} + int main(void) { test_init(); @@ -127,6 +172,7 @@ test_base64_encode(); test_base64_decode(); test_bsearch_insert_pos(); + test_seq_range_array(); test_istreams(); return test_deinit(); }