1 files changed, 569 insertions, 0 deletions
diff --git a/src/lib/seq-range-array.c b/src/lib/seq-range-array.c
new file mode 100644
index 0000000..2d8dbfc
--- /dev/null
+++ b/src/lib/seq-range-array.c
@@ -0,0 +1,569 @@
+/* Copyright (c) 2005-2018 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "array.h"
+#include "seq-range-array.h"
+
+static bool seq_range_is_overflowed(const ARRAY_TYPE(seq_range) *array)
+{
+	const struct seq_range *range;
+	unsigned int count;
+
+	range = array_get(array, &count);
+	return count == 1 && range[0].seq1 == 0 &&
+		range[0].seq2 == (uint32_t)-1;
+}
+
+static bool ATTR_NOWARN_UNUSED_RESULT
+seq_range_lookup(const ARRAY_TYPE(seq_range) *array,
+		 uint32_t seq, unsigned int *idx_r)
+{
+	const struct seq_range *data;
+	unsigned int idx, left_idx, right_idx, count;
+
+	data = array_get(array, &count);
+	i_assert(count < INT_MAX);
+
+	idx = 0; left_idx = 0; right_idx = count;
+	while (left_idx < right_idx) {
+		idx = (left_idx + right_idx) / 2;
+
+		if (data[idx].seq1 <= seq) {
+			if (data[idx].seq2 >= seq) {
+				/* it's already in the range */
+				*idx_r = idx;
+				return TRUE;
+			}
+			left_idx = idx+1;
+		} else {
+			right_idx = idx;
+		}
+	}
+	if (left_idx > idx)
+		idx++;
+	*idx_r = idx;
+	return FALSE;
+}
+
+static bool
+seq_range_array_add_slow_path(ARRAY_TYPE(seq_range) *array, uint32_t seq)
+{
+	struct seq_range *data, value;
+	unsigned int idx, count;
+
+	value.seq1 = value.seq2 = seq;
+	data = array_get_modifiable(array, &count);
+
+	/* somewhere in the middle, array is sorted so find it with
+	   binary search */
+	if (seq_range_lookup(array, seq, &idx))
+		return TRUE;
+
+	/* idx == count couldn't happen because we already handle it above */
+	i_assert(idx < count && data[idx].seq1 >= seq);
+	i_assert(data[idx].seq1 > seq || data[idx].seq2 < seq);
+
+	if (data[idx].seq1 == seq+1) {
+		data[idx].seq1 = seq;
+		if (idx > 0 && data[idx-1].seq2 == seq-1) {
+			/* merge */
+			data[idx-1].seq2 = data[idx].seq2;
+			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);
+		}
+	}
+	return FALSE;
+}
+
+bool seq_range_array_add(ARRAY_TYPE(seq_range) *array, uint32_t seq)
+{
+	struct seq_range *data, value;
+	unsigned int count;
+	bool exists = FALSE;
+
+	value.seq1 = value.seq2 = seq;
+
+	data = array_get_modifiable(array, &count);
+	/* quick checks */
+	if (count == 0)
+		array_push_back(array, &value);
+	else if (data[count-1].seq2 < seq) {
+		if (data[count-1].seq2 == seq-1) {
+			/* grow last range */
+			data[count-1].seq2 = seq;
+		} else {
+			array_push_back(array, &value);
+		}
+	} else if (data[0].seq1 > seq) {
+		if (data[0].seq1-1 == seq) {
+			/* grow down first range */
+			data[0].seq1 = seq;
+		} else {
+			array_push_front(array, &value);
+		}
+	} else {
+		exists = seq_range_array_add_slow_path(array, seq);
+	}
+	i_assert(!seq_range_is_overflowed(array));
+	return exists;
+}
+
+void seq_range_array_add_with_init(ARRAY_TYPE(seq_range) *array,
+				   unsigned int init_count, uint32_t seq)
+{
+	if (!array_is_created(array))
+		i_array_init(array, init_count);
+	seq_range_array_add(array, seq);
+}
+
+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;
+
+	seq_range_lookup(array, seq1, &idx1);
+	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--;
+
+	if (idx1 == idx2 &&
+	    (idx2 == count || (seq2 < (uint32_t)-1 && data[idx2].seq1 > seq2+1)) &&
+	    (idx1 == 0 || data[idx1-1].seq2 < seq1-1)) {
+		/* no overlapping */
+		value.seq1 = seq1;
+		value.seq2 = seq2;
+		array_insert(array, idx1, &value, 1);
+	} else {
+		i_assert(idx1 < count);
+		if (seq1 < data[idx1].seq1)
+			data[idx1].seq1 = seq1;
+		if (seq2 > data[idx1].seq2) {
+			/* merge */
+			if (idx2 == count ||
+			    data[idx2].seq1 > seq2+1)
+				idx2--;
+			if (seq2 >= data[idx2].seq2) {
+				data[idx1].seq2 = seq2;
+			} else {
+				data[idx1].seq2 = data[idx2].seq2;
+			}
+			array_delete(array, idx1 + 1, idx2 - idx1);
+		}
+	}
+	i_assert(!seq_range_is_overflowed(array));
+}
+
+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)
+{
+	const struct seq_range *range;
+
+	if (array_count(dest) == 0) {
+		array_append_array(dest, src);
+		return;
+	}
+
+	array_foreach(src, range)
+		seq_range_array_add_range(dest, range->seq1, range->seq2);
+}
+
+void seq_range_array_merge_n(ARRAY_TYPE(seq_range) *dest,
+			     const ARRAY_TYPE(seq_range) *src,
+			     unsigned int count)
+{
+	const struct seq_range *src_range;
+	unsigned int src_idx, src_count;
+	unsigned int merge_count = count;
+
+	src_range = array_get(src, &src_count);
+	for (src_idx = 0; src_idx < src_count && merge_count > 0; src_idx++) {
+		uint32_t first_seq = src_range[src_idx].seq1;
+		uint32_t last_seq = src_range[src_idx].seq2;
+		unsigned int idx_count = last_seq - first_seq + 1;
+
+		if (idx_count > merge_count) {
+			last_seq = first_seq + merge_count - 1;
+			merge_count = 0;
+		} else {
+			merge_count -= idx_count;
+		}
+		seq_range_array_add_range(dest, first_seq, last_seq);
+	}
+}
+
+bool seq_range_array_remove(ARRAY_TYPE(seq_range) *array, uint32_t seq)
+{
+	struct seq_range *data, value;
+	unsigned int idx, left_idx, right_idx, count;
+
+	if (!array_is_created(array))
+		return FALSE;
+
+	data = array_get_modifiable(array, &count);
+	if (count == 0)
+		return FALSE;
+
+	/* quick checks */
+	if (seq > data[count-1].seq2 || seq < data[0].seq1) {
+		/* outside the range */
+		return FALSE;
+	}
+	if (data[count-1].seq2 == seq) {
+		/* shrink last range */
+		if (data[count-1].seq1 != data[count-1].seq2)
+			data[count-1].seq2--;
+		else
+			array_delete(array, count-1, 1);
+		return TRUE;
+	}
+	if (data[0].seq1 == seq) {
+		/* shrink up first range */
+		if (data[0].seq1 != data[0].seq2)
+			data[0].seq1++;
+		else
+			array_pop_front(array);
+		return TRUE;
+	}
+
+	/* somewhere in the middle, array is sorted so find it with
+	   binary search */
+	i_assert(count < INT_MAX);
+	left_idx = 0; right_idx = count;
+	while (left_idx < right_idx) {
+		idx = (left_idx + right_idx) / 2;
+
+		if (data[idx].seq1 > seq)
+			right_idx = idx;
+		else if (data[idx].seq2 < seq)
+			left_idx = idx+1;
+		else {
+			/* found it */
+			if (data[idx].seq1 == seq) {
+				if (data[idx].seq1 == data[idx].seq2) {
+					/* a single sequence range.
+					   remove it entirely */
+					array_delete(array, idx, 1);
+				} else {
+					/* shrink the range */
+					data[idx].seq1++;
+				}
+			} else if (data[idx].seq2 == seq) {
+				/* shrink the range */
+				data[idx].seq2--;
+			} else {
+				/* split the sequence range */
+				value.seq1 = seq + 1;
+				value.seq2 = data[idx].seq2;
+				data[idx].seq2 = seq - 1;
+
+				array_insert(array, idx + 1, &value, 1);
+			}
+			return TRUE;
+		}
+	}
+	return FALSE;
+}
+
+unsigned int seq_range_array_remove_range(ARRAY_TYPE(seq_range) *array,
+					  uint32_t seq1, uint32_t seq2)
+{
+	const struct seq_range *data;
+	unsigned int idx, idx2, count, remove_count = 0;
+
+	/* remove first and last. this makes sure that everything between
+	   can simply be deleted with array_delete().
+
+	   FIXME: it would be faster if we did only one binary lookup here
+	   and handled the splitting ourself.. */
+	if (seq_range_array_remove(array, seq1))
+		remove_count++;
+	if (seq1 == seq2)
+		return remove_count;
+	seq1++;
+
+	if (seq_range_array_remove(array, seq2--))
+		remove_count++;
+	if (seq1 > seq2)
+		return remove_count;
+
+	/* find the beginning */
+	data = array_get(array, &count);
+	seq_range_lookup(array, seq1, &idx);
+
+	if (idx == count)
+		return remove_count;
+
+	i_assert(data[idx].seq1 >= seq1);
+	for (idx2 = idx; idx2 < count; idx2++) {
+		if (data[idx2].seq1 > seq2)
+			break;
+		i_assert(UINT_MAX - remove_count >= seq_range_length(&data[idx2]));
+		remove_count += seq_range_length(&data[idx2]);
+	}
+	array_delete(array, idx, idx2-idx);
+	return remove_count;
+}
+
+unsigned int seq_range_array_remove_seq_range(ARRAY_TYPE(seq_range) *dest,
+					      const ARRAY_TYPE(seq_range) *src)
+{
+	unsigned int count, full_count = 0;
+	const struct seq_range *src_range;
+
+	array_foreach(src, src_range) {
+		count = seq_range_array_remove_range(dest, src_range->seq1,
+						     src_range->seq2);
+		i_assert(UINT_MAX - full_count >= count);
+		full_count += count;
+	}
+	return full_count;
+}
+
+void seq_range_array_remove_nth(ARRAY_TYPE(seq_range) *array,
+				uint32_t n, uint32_t count)
+{
+	struct seq_range_iter iter;
+	uint32_t seq1, seq2;
+
+	if (count == 0)
+		return;
+
+	seq_range_array_iter_init(&iter, array);
+	if (!seq_range_array_iter_nth(&iter, n, &seq1)) {
+		/* n points beyond array */
+		return;
+	}
+	if (count-1 >= (uint32_t)-1 - n ||
+	    !seq_range_array_iter_nth(&iter, n + (count-1), &seq2)) {
+		/* count points beyond array */
+		seq2 = (uint32_t)-1;
+	}
+	seq_range_array_remove_range(array, seq1, seq2);
+}
+
+unsigned int seq_range_array_intersect(ARRAY_TYPE(seq_range) *dest,
+				       const ARRAY_TYPE(seq_range) *src)
+{
+	const struct seq_range *src_range;
+	unsigned int i, count, remove_count, full_count = 0;
+	uint32_t last_seq = 0;
+
+	src_range = array_get(src, &count);
+	for (i = 0; i < count; i++) {
+		if (last_seq + 1 < src_range[i].seq1) {
+			remove_count = seq_range_array_remove_range(dest,
+				last_seq + 1, src_range[i].seq1 - 1);
+			i_assert(UINT_MAX - full_count >= remove_count);
+			full_count += remove_count;
+		}
+		last_seq = src_range[i].seq2;
+	}
+	if (last_seq != (uint32_t)-1) {
+		remove_count = seq_range_array_remove_range(dest, last_seq + 1,
+							    (uint32_t)-1);
+		i_assert(UINT_MAX - full_count >= remove_count);
+		full_count += remove_count;
+	}
+	return full_count;
+}
+
+bool seq_range_exists(const ARRAY_TYPE(seq_range) *array, uint32_t seq)
+{
+	unsigned int idx;
+
+	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;
+	unsigned int seq_count = 0;
+
+	array_foreach(array, range) {
+		i_assert(UINT_MAX - seq_count >= seq_range_length(range));
+		seq_count += seq_range_length(range);
+	}
+	return seq_count;
+}
+
+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 prev_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_push_back(array, &value);
+		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; ) {
+		prev_min_seq = min_seq;
+		min_seq = range[i].seq2;
+		if (range[i].seq1 == prev_min_seq) {
+			array_delete(array, i, 1);
+			range = array_get_modifiable(array, &count);
+		} else {
+			range[i].seq2 = range[i].seq1 - 1;
+			range[i].seq1 = prev_min_seq;
+			i++;
+		}
+		if (min_seq >= max_seq) {
+			/* max_seq is reached. the rest of the array should be
+			   empty. we'll return here, because min_seq++ may
+			   wrap to 0. */
+			i_assert(min_seq == max_seq);
+			i_assert(i == count);
+			return;
+		}
+		min_seq++;
+	}
+	if (min_seq <= max_seq) {
+		value.seq1 = min_seq;
+		value.seq2 = max_seq;
+		array_push_back(array, &value);
+	}
+}
+
+void seq_range_array_iter_init(struct seq_range_iter *iter_r,
+			       const ARRAY_TYPE(seq_range) *array)
+{
+	i_zero(iter_r);
+	iter_r->array = array;
+}
+
+bool seq_range_array_iter_nth(struct seq_range_iter *iter, unsigned int n,
+			      uint32_t *seq_r)
+{
+	const struct seq_range *range;
+	unsigned int i, count, diff;
+
+	if (n < iter->prev_n) {
+		/* iterating backwards, don't bother optimizing */
+		iter->prev_n = 0;
+		iter->prev_idx = 0;
+	}
+
+	range = array_get(iter->array, &count);
+	for (i = iter->prev_idx; i < count; i++) {
+		diff = range[i].seq2 - range[i].seq1;
+		if (n <= iter->prev_n + diff) {
+			i_assert(n >= iter->prev_n);
+			*seq_r = range[i].seq1 + (n - iter->prev_n);
+			iter->prev_idx = i;
+			return TRUE;
+		}
+		iter->prev_n += diff + 1;
+	}
+	iter->prev_idx = i;
+	return FALSE;
+}