dovecot-1.2: Added seq_range_array_have_common().

[dovecot at dovecot.org]

details:   http://hg.dovecot.org/dovecot-1.2/rev/3e8bcf4f6f5e
changeset: 7905:3e8bcf4f6f5e
user:      Timo Sirainen <tss at iki.fi>
date:      Fri Jun 20 04:41:03 2008 +0300
description:
Added seq_range_array_have_common().

diffstat:

3 files changed, 63 insertions(+), 1 deletion(-)
src/lib/seq-range-array.c |   21 +++++++++++++++++++++
src/lib/seq-range-array.h |    3 +++
src/tests/test-lib.c      |   40 +++++++++++++++++++++++++++++++++++++++-

diffs (101 lines):

diff -r 34085062ad89 -r 3e8bcf4f6f5e src/lib/seq-range-array.c
--- a/src/lib/seq-range-array.c	Thu Jun 19 09:15:28 2008 +0300
+++ b/src/lib/seq-range-array.c	Fri Jun 20 04:41:03 2008 +0300
@@ -310,6 +310,27 @@ bool seq_range_exists(const ARRAY_TYPE(s
 	return seq_range_lookup(array, seq, &idx);
 }
 
+bool seq_range_array_have_common(const ARRAY_TYPE(seq_range) *array1,
+				 const ARRAY_TYPE(seq_range) *array2)
+{
+	const struct seq_range *range1, *range2;
+	unsigned int i1, i2, count1, count2;
+
+	range1 = array_get(array1, &count1);
+	range2 = array_get(array2, &count2);
+	for (i1 = i2 = 0; i1 < count1 && i2 < count2; ) {
+		if (range1[i1].seq1 <= range2[i2].seq2 &&
+		    range1[i1].seq2 >= range2[i2].seq1)
+			return TRUE;
+
+		if (range1[i1].seq1 < range2[i2].seq1)
+			i1++;
+		else
+			i2++;
+	}
+	return FALSE;
+}
+
 unsigned int seq_range_count(const ARRAY_TYPE(seq_range) *array)
 {
 	const struct seq_range *range;
diff -r 34085062ad89 -r 3e8bcf4f6f5e src/lib/seq-range-array.h
--- a/src/lib/seq-range-array.h	Thu Jun 19 09:15:28 2008 +0300
+++ b/src/lib/seq-range-array.h	Fri Jun 20 04:41:03 2008 +0300
@@ -33,6 +33,9 @@ seq_range_array_intersect(ARRAY_TYPE(seq
 			  const ARRAY_TYPE(seq_range) *src);
 /* Returns TRUE if sequence exists in the range. */
 bool seq_range_exists(const ARRAY_TYPE(seq_range) *array, uint32_t seq);
+/* Returns TRUE if arrays have common sequences. */
+bool seq_range_array_have_common(const ARRAY_TYPE(seq_range) *array1,
+				 const ARRAY_TYPE(seq_range) *array2);
 /* Return number of sequences in the range. */
 unsigned int seq_range_count(const ARRAY_TYPE(seq_range) *array);
 
diff -r 34085062ad89 -r 3e8bcf4f6f5e src/tests/test-lib.c
--- a/src/tests/test-lib.c	Thu Jun 19 09:15:28 2008 +0300
+++ b/src/tests/test-lib.c	Fri Jun 20 04:41:03 2008 +0300
@@ -605,7 +605,7 @@ fail:
 	}
 }
 
-static void test_seq_range_array(void)
+static void test_seq_range_array_invert(void)
 {
 	static const unsigned int input_min = 1, input_max = 5;
 	static const unsigned int input[] = {
@@ -646,6 +646,44 @@ static void test_seq_range_array(void)
 			 success);
 		array_free(&range);
 	}
+}
+
+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, 0, 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);
+}
+
+static void test_seq_range_array(void)
+{
+	test_seq_range_array_invert();
+	test_seq_range_array_have_common();
 	test_seq_range_array_random();
 }