summaryrefslogtreecommitdiffstats
path: root/src/lib/seq-range-array.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-28 09:51:24 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-28 09:51:24 +0000
commitf7548d6d28c313cf80e6f3ef89aed16a19815df1 (patch)
treea3f6f2a3f247293bee59ecd28e8cd8ceb6ca064a /src/lib/seq-range-array.c
parentInitial commit. (diff)
downloaddovecot-f7548d6d28c313cf80e6f3ef89aed16a19815df1.tar.xz
dovecot-f7548d6d28c313cf80e6f3ef89aed16a19815df1.zip
Adding upstream version 1:2.3.19.1+dfsg1.upstream/1%2.3.19.1+dfsg1upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r--src/lib/seq-range-array.c569
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;
+}