dovecot-2.1: seq_range_array_add(): Ranges weren't always merged...

[dovecot at dovecot.org]

details:   http://hg.dovecot.org/dovecot-2.1/rev/bac5e1dae4ed
changeset: 14491:bac5e1dae4ed
user:      Timo Sirainen <tss at iki.fi>
date:      Mon Apr 30 22:53:19 2012 +0300
description:
seq_range_array_add(): Ranges weren't always merged when they could have.
This didn't break anything, but it used up more memory than necessary.

diffstat:

 src/lib/seq-range-array.c      |  22 +++++++++++++---------
 src/lib/test-seq-range-array.c |  16 +++++++++++++++-
 2 files changed, 28 insertions(+), 10 deletions(-)

diffs (73 lines):

diff -r 2f776ca73cef -r bac5e1dae4ed src/lib/seq-range-array.c
--- a/src/lib/seq-range-array.c	Sat Apr 28 18:24:24 2012 +0300
+++ b/src/lib/seq-range-array.c	Mon Apr 30 22:53:19 2012 +0300
@@ -86,16 +86,20 @@
 			data[idx-1].seq2 = data[idx].seq2;
 			array_delete(array, idx, 1);
 		}
-	} else if (data[idx].seq2 == seq-1) {
-		i_assert(idx+1 < count); /* already handled above */
-		data[idx].seq2 = seq;
-		if (data[idx+1].seq1 == seq+1) {
-			/* merge */
-			data[idx+1].seq1 = data[idx].seq1;
-			array_delete(array, idx, 1);
+	} else {
+		if (idx > 0 && data[idx-1].seq2 == seq-1)
+			idx--;
+		if (data[idx].seq2 == seq-1) {
+			i_assert(idx+1 < count); /* already handled above */
+			data[idx].seq2 = seq;
+			if (data[idx+1].seq1 == seq+1) {
+				/* merge */
+				data[idx+1].seq1 = data[idx].seq1;
+				array_delete(array, idx, 1);
+			}
+		} else {
+			array_insert(array, idx, &value, 1);
 		}
-	} else {
-		array_insert(array, idx, &value, 1);
 	}
 	return FALSE;
 }
diff -r 2f776ca73cef -r bac5e1dae4ed src/lib/test-seq-range-array.c
--- a/src/lib/test-seq-range-array.c	Sat Apr 28 18:24:24 2012 +0300
+++ b/src/lib/test-seq-range-array.c	Mon Apr 30 22:53:19 2012 +0300
@@ -6,6 +6,19 @@
 
 #include <stdlib.h>
 
+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, 0, 4);
+	seq_range_array_add(&range, 0, 1);
+	seq_range_array_add(&range, 0, 2);
+	test_assert(array_count(&range) == 2);
+	test_end();
+}
+
 static void test_seq_range_array_random(void)
 {
 #define SEQ_RANGE_TEST_BUFSIZE 20
@@ -53,7 +66,7 @@
 
 		seqs = array_get(&range, &count);
 		for (j = 0, seq1 = 0; j < count; j++) {
-			if (j > 0 && seqs[j-1].seq2 >= seqs[j].seq1)
+			if (j > 0 && seqs[j-1].seq2+1 >= seqs[j].seq1)
 				goto fail;
 			for (; seq1 < seqs[j].seq1; seq1++) {
 				if (shadowbuf[seq1] != 0)
@@ -156,6 +169,7 @@
 
 void test_seq_range_array(void)
 {
+	test_seq_range_array_add_merge();
 	test_seq_range_array_invert();
 	test_seq_range_array_have_common();
 	test_seq_range_array_random();