dovecot: Added seq_range_array_invert()

[dovecot at dovecot.org]

details:   http://hg.dovecot.org/dovecot/rev/3896c75bfaa8
changeset: 6758:3896c75bfaa8
user:      Timo Sirainen <tss at iki.fi>
date:      Sat Nov 10 19:16:01 2007 +0200
description:
Added seq_range_array_invert()

diffstat:

3 files changed, 100 insertions(+)
src/lib/seq-range-array.c |   50 +++++++++++++++++++++++++++++++++++++++++++++
src/lib/seq-range-array.h |    4 +++
src/tests/test-lib.c      |   46 +++++++++++++++++++++++++++++++++++++++++

diffs (142 lines):

diff -r f7aea3542cce -r 3896c75bfaa8 src/lib/seq-range-array.c
--- 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 @@ bool seq_range_exists(const ARRAY_TYPE(s
 
 	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);
+	}
+}
diff -r f7aea3542cce -r 3896c75bfaa8 src/lib/seq-range-array.h
--- 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 @@ unsigned int seq_range_array_remove_rang
 /* 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
diff -r f7aea3542cce -r 3896c75bfaa8 src/tests/test-lib.c
--- 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_bsearch_insert_pos(void
 	}
 }
 
+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 @@ int main(void)
 	test_base64_encode();
 	test_base64_decode();
 	test_bsearch_insert_pos();
+	test_seq_range_array();
 	test_istreams();
 	return test_deinit();
 }