seq-range-array.c revision c47e837a127c533e67debafde8ccf9691041be16
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen/* Copyright (c) 2005-2007 Dovecot authors, see the included COPYING file */
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen#include "lib.h"
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen#include "array.h"
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen#include "seq-range-array.h"
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainenstatic bool seq_range_lookup(const ARRAY_TYPE(seq_range) *array,
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen uint32_t seq, unsigned int *idx_r)
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen{
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen const struct seq_range *data;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen unsigned int idx, left_idx, right_idx, count;
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen data = array_get(array, &count);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen idx = 0; left_idx = 0; right_idx = count;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen while (left_idx < right_idx) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen idx = (left_idx + right_idx) / 2;
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen if (data[idx].seq1 <= seq) {
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen if (data[idx].seq2 >= seq) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* it's already in the range */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen *idx_r = idx;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return TRUE;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen left_idx = idx+1;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen } else {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen right_idx = idx;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen *idx_r = idx;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return FALSE;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen}
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainenvoid seq_range_array_add(ARRAY_TYPE(seq_range) *array,
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen unsigned int init_count, uint32_t seq)
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen{
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen struct seq_range *data, value;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen unsigned int idx, count;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen value.seq1 = value.seq2 = seq;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (!array_is_created(array))
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen i_array_init(array, init_count);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen data = array_get_modifiable(array, &count);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (count == 0) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen array_append(array, &value, 1);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* quick checks */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (data[count-1].seq2 == seq-1) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* grow last range */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen data[count-1].seq2 = seq;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return;
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen }
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen if (data[count-1].seq2 < seq) {
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen array_append(array, &value, 1);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return;
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen }
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen if (data[0].seq1 == seq+1) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* grow down first range */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen data[0].seq1 = seq;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (data[0].seq1 > seq) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen array_insert(array, 0, &value, 1);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return;
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen }
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen /* somewhere in the middle, array is sorted so find it with
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen binary search */
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen if (seq_range_lookup(array, seq, &idx))
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen return;
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen if (data[idx].seq2 < seq)
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen idx++;
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen /* idx == count couldn't happen because we already handle it above */
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen i_assert(idx < count && data[idx].seq1 >= seq);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen i_assert(data[idx].seq1 > seq || data[idx].seq2 < seq);
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen if (data[idx].seq1 == seq+1) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen data[idx].seq1 = seq;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (idx > 0 && data[idx-1].seq2 == seq-1) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* merge */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen data[idx-1].seq2 = data[idx].seq2;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen array_delete(array, idx, 1);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen } else if (data[idx].seq2 == seq-1) {
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen i_assert(idx+1 < count); /* already handled above */
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen data[idx].seq2 = seq;
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen if (data[idx+1].seq1 == seq+1) {
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen /* merge */
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen data[idx+1].seq1 = data[idx].seq1;
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen array_delete(array, idx, 1);
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen }
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen } else {
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen array_insert(array, idx, &value, 1);
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen}
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainenbool seq_range_array_remove(ARRAY_TYPE(seq_range) *array, uint32_t seq)
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen{
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen struct seq_range *data, value;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen unsigned int idx, left_idx, right_idx, count;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (!array_is_created(array))
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return FALSE;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen data = array_get_modifiable(array, &count);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (count == 0)
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return FALSE;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* quick checks */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (seq > data[count-1].seq2 || seq < data[0].seq1) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* outside the range */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return FALSE;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (data[count-1].seq2 == seq) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* shrink last range */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (data[count-1].seq1 != data[count-1].seq2)
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen data[count-1].seq2--;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen else
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen array_delete(array, count-1, 1);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return TRUE;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (data[0].seq1 == seq) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* shrink up first range */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (data[0].seq1 != data[0].seq2)
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen data[0].seq1++;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen else
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen array_delete(array, 0, 1);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return TRUE;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* somewhere in the middle, array is sorted so find it with
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen binary search */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen idx = 0; left_idx = 0; right_idx = count;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen while (left_idx < right_idx) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen idx = (left_idx + right_idx) / 2;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (data[idx].seq1 > seq)
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen right_idx = idx;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen else if (data[idx].seq2 < seq)
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen left_idx = idx+1;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen else {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* found it */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (data[idx].seq1 == seq) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen if (data[idx].seq1 == data[idx].seq2) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* a single sequence range.
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen remove it entirely */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen array_delete(array, idx, 1);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen } else {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* shrink the range */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen data[idx].seq1++;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen } else if (data[idx].seq2 == seq) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen /* shrink the range */
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen data[idx].seq2--;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen } else {
fb79b36eb34532dbe67caf99eefe3660b8c841e0Timo Sirainen /* split the sequence range */
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen value.seq1 = seq + 1;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen value.seq2 = data[idx].seq2;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen data[idx].seq2 = seq - 1;
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen array_insert(array, idx + 1, &value, 1);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen }
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen return TRUE;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return FALSE;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen}
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainenunsigned int seq_range_array_remove_range(ARRAY_TYPE(seq_range) *array,
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen uint32_t seq1, uint32_t seq2)
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen{
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen const struct seq_range *data;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen unsigned int idx, idx2, count, remove_count = 0;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen /* remove first and last. this makes sure that everything between
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen can simply be deleted with array_delete().
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen FIXME: it would be faster if we did only one binary lookup here
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen and handled the splitting ourself.. */
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (seq_range_array_remove(array, seq1))
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen remove_count++;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (seq1 == seq2)
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen return remove_count;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen seq1++;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (seq_range_array_remove(array, seq2--))
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen remove_count++;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (seq1 > seq2)
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen return remove_count;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen /* find the beginning */
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen data = array_get(array, &count);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen (void)seq_range_lookup(array, seq1, &idx);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (idx < count && data[idx].seq2 < seq1)
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen idx++;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (idx == count)
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen return remove_count;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen i_assert(data[idx].seq1 >= seq1);
fb79b36eb34532dbe67caf99eefe3660b8c841e0Timo Sirainen for (idx2 = idx; idx2 < count; idx2++) {
fb79b36eb34532dbe67caf99eefe3660b8c841e0Timo Sirainen if (data[idx2].seq1 > seq2)
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen break;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen remove_count += data[idx2].seq2 - data[idx2].seq1 + 1;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen array_delete(array, idx, idx2-idx);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return remove_count;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen}
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainenunsigned int seq_range_array_remove_seq_range(ARRAY_TYPE(seq_range) *dest,
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen const ARRAY_TYPE(seq_range) *src)
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen{
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen unsigned int ret = 0;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen const struct seq_range *src_range;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen unsigned int i, count;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen src_range = array_get(src, &count);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen for (i = 0; i < count; i++) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen ret += seq_range_array_remove_range(dest, src_range[i].seq1,
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen src_range[i].seq2);
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen }
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen return ret;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen}
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainenunsigned int
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainenseq_range_array_remove_invert_range(ARRAY_TYPE(seq_range) *dest,
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen const ARRAY_TYPE(seq_range) *src)
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen{
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen const struct seq_range *src_range;
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen unsigned int i, count, ret = 0;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen uint32_t last_seq = 0;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen src_range = array_get(src, &count);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen for (i = 0; i < count; i++) {
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (last_seq + 1 < src_range[i].seq1) {
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen ret += seq_range_array_remove_range(dest, last_seq + 1,
d6a7cb184cc882a90aa3d9312082e0029f354ff6Timo Sirainen src_range[i].seq1 - 1);
7000810786f2959f02cd6d2f4151a9eb61ff5db8Timo Sirainen }
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen last_seq = src_range[i].seq2;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen }
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (last_seq != (uint32_t)-1) {
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen ret += seq_range_array_remove_range(dest, last_seq + 1,
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen (uint32_t)-1);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen }
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen return ret;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen}
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainenbool seq_range_exists(const ARRAY_TYPE(seq_range) *array, uint32_t seq)
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen{
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen unsigned int idx;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen return seq_range_lookup(array, seq, &idx);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen}
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainenvoid seq_range_array_invert(ARRAY_TYPE(seq_range) *array,
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen uint32_t min_seq, uint32_t max_seq)
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen{
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen struct seq_range *range, value;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen unsigned int i, count;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen uint32_t next_min_seq;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (array_is_created(array))
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen range = array_get_modifiable(array, &count);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen else {
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen range = NULL;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen count = 0;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen }
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (count == 0) {
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen /* empty -> full */
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (!array_is_created(array))
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen i_array_init(array, 4);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen value.seq1 = min_seq;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen value.seq2 = max_seq;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen array_append(array, &value, 1);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen return;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen }
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen i_assert(range[0].seq1 >= min_seq);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen i_assert(range[count-1].seq2 <= max_seq);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (range[0].seq1 == min_seq && range[0].seq2 == max_seq) {
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen /* full -> empty */
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen array_clear(array);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen return;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen }
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen for (i = 0; i < count; ) {
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen next_min_seq = range[i].seq2 + 1;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (range[i].seq1 == min_seq) {
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen array_delete(array, i, 1);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen range = array_get_modifiable(array, &count);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen } else {
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen range[i].seq2 = range[i].seq1 - 1;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen range[i].seq1 = min_seq;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen i++;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen }
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen min_seq = next_min_seq;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen }
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen if (min_seq <= max_seq) {
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen value.seq1 = min_seq;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen value.seq2 = max_seq;
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen array_append(array, &value, 1);
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen }
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen}
f8740ac53310cd28ba4ec6dc9e9ce6e9a3688f39Timo Sirainen