dovecot-2.2: lib: seq-range-array - add range changes
dovecot at dovecot.org
dovecot at dovecot.org
Tue Jan 20 23:54:58 UTC 2015
details: http://hg.dovecot.org/dovecot-2.2/rev/230f3579c9b7
changeset: 18190:230f3579c9b7
user: Phil Carmody <phil at dovecot.fi>
date: Wed Jan 21 01:44:31 2015 +0200
description:
lib: seq-range-array - add range changes
Pull the _add_range() guts into a private helper function, and add a new
_add_range_count() helper which also returns the number of SEQs added.
Expand the tests to test this new functionality.
Signed-off-by: Phil Carmody <phil at dovecot.fi>
diffstat:
src/lib/seq-range-array.c | 56 ++++++++++++++++++++++++++++++++++++++++-
src/lib/seq-range-array.h | 10 ++++++-
src/lib/test-seq-range-array.c | 16 ++++++++---
3 files changed, 74 insertions(+), 8 deletions(-)
diffs (143 lines):
diff -r 3ef7f3d53d17 -r 230f3579c9b7 src/lib/seq-range-array.c
--- a/src/lib/seq-range-array.c Wed Jan 21 01:42:01 2015 +0200
+++ b/src/lib/seq-range-array.c Wed Jan 21 01:44:31 2015 +0200
@@ -110,8 +110,10 @@
seq_range_array_add(array, seq);
}
-void seq_range_array_add_range(ARRAY_TYPE(seq_range) *array,
- uint32_t seq1, uint32_t seq2)
+static void
+seq_range_array_add_range_internal(ARRAY_TYPE(seq_range) *array,
+ uint32_t seq1, uint32_t seq2,
+ unsigned int *r_count)
{
struct seq_range *data, value;
unsigned int idx1, idx2, count;
@@ -120,6 +122,43 @@
seq_range_lookup(array, seq2, &idx2);
data = array_get_modifiable(array, &count);
+ if (r_count != NULL) {
+ /* Find number we're adding by counting the number we're
+ not adding, and subtracting that from the nominal range. */
+ unsigned int added = seq2+1 - seq1;
+ unsigned int countidx2 = idx2;
+ unsigned int overcounted = 0u, notadded = 0u;
+ unsigned int i;
+
+ if (idx1 == count) {
+ /* not in a range as too far right */
+ } else if (seq1 < data[idx1].seq1) {
+ /* not in a range, to the left of a real range */
+ } else {
+ /* count the whole of this range, which is an overcount */
+ overcounted += seq1 - data[idx1].seq1;
+ /* fencepost check: equality means the whole range is valid,
+ therefore there's no overcounting. Result = 0 overcount */
+ }
+ if (idx2 == count) {
+ /* not in a range as too far right */
+ } else if (seq2 < data[idx2].seq1) {
+ /* not in a range, to the left of a real range */
+ } else {
+ /* count the whole of this range, which is an overcount */
+ overcounted += data[idx2].seq2 - seq2;
+ countidx2++; /* may become == count i.e. past the end */
+ /* fencepost check: equality means the whole range is valid,
+ therefore there's no overcounting. Result = 0 overcount. */
+ }
+ /* Now count how many we're not adding */
+ for (i = idx1; i < countidx2; i++)
+ notadded += data[i].seq2+1 - data[i].seq1;
+ /* Maybe the not added tally included some over-counting too */
+ added -= (notadded - overcounted);
+ *r_count = added;
+ }
+
if (idx1 > 0 && data[idx1-1].seq2+1 == seq1)
idx1--;
@@ -149,6 +188,19 @@
}
}
+void seq_range_array_add_range(ARRAY_TYPE(seq_range) *array,
+ uint32_t seq1, uint32_t seq2)
+{
+ seq_range_array_add_range_internal(array, seq1, seq2, NULL);
+}
+unsigned int seq_range_array_add_range_count(ARRAY_TYPE(seq_range) *array,
+ uint32_t seq1, uint32_t seq2)
+{
+ unsigned int count;
+ seq_range_array_add_range_internal(array, seq1, seq2, &count);
+ return count;
+}
+
void seq_range_array_merge(ARRAY_TYPE(seq_range) *dest,
const ARRAY_TYPE(seq_range) *src)
{
diff -r 3ef7f3d53d17 -r 230f3579c9b7 src/lib/seq-range-array.h
--- a/src/lib/seq-range-array.h Wed Jan 21 01:42:01 2015 +0200
+++ b/src/lib/seq-range-array.h Wed Jan 21 01:44:31 2015 +0200
@@ -11,7 +11,13 @@
unsigned int prev_n, prev_idx;
};
-/* Add sequrence to range. If the array isn't created yet, create it with
+static inline uint32_t ATTR_PURE seq_range_length(struct seq_range *range)
+{
+ i_assert(range->seq2 >= range->seq1);
+ return range->seq2 - range->seq1 + 1;
+}
+
+/* Add sequence to range. If the array isn't created yet, create it with
initial size of init_count. */
bool ATTR_NOWARN_UNUSED_RESULT
seq_range_array_add(ARRAY_TYPE(seq_range) *array, uint32_t seq);
@@ -21,6 +27,8 @@
unsigned int init_count, uint32_t seq);
void seq_range_array_add_range(ARRAY_TYPE(seq_range) *array,
uint32_t seq1, uint32_t seq2);
+unsigned int seq_range_array_add_range_count(ARRAY_TYPE(seq_range) *array,
+ uint32_t seq1, uint32_t seq2);
void seq_range_array_merge(ARRAY_TYPE(seq_range) *dest,
const ARRAY_TYPE(seq_range) *src);
/* Remove the given sequrence from range. Returns TRUE if it was found. */
diff -r 3ef7f3d53d17 -r 230f3579c9b7 src/lib/test-seq-range-array.c
--- a/src/lib/test-seq-range-array.c Wed Jan 21 01:42:01 2015 +0200
+++ b/src/lib/test-seq-range-array.c Wed Jan 21 01:44:31 2015 +0200
@@ -82,8 +82,8 @@
static void test_seq_range_array_random(void)
{
-#define SEQ_RANGE_TEST_BUFSIZE 20
-#define SEQ_RANGE_TEST_COUNT 10000
+#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;
@@ -100,12 +100,18 @@
test = rand() % 4;
switch (test) {
case 0:
- seq_range_array_add(&range, seq1);
+ ret = seq_range_array_add(&range, seq1) ? 0 : 1; /* FALSE == added */
+ ret2 = shadowbuf[seq1] == 0 ? 1 : 0;
shadowbuf[seq1] = 1;
break;
case 1:
- seq_range_array_add_range(&range, seq1, seq2);
- memset(shadowbuf + seq1, 1, seq2 - seq1 + 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;
More information about the dovecot-cvs
mailing list