src/lib/seq-range-array.c

bcb4e51a409d94ae670de96afb8483a4f7855294Stephan Bosch/* Copyright (c) 2005-2018 Dovecot authors, see the included COPYING file */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen#include "lib.h"
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen#include "array.h"
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen#include "seq-range-array.h"
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainenstatic bool ATTR_NOWARN_UNUSED_RESULT
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainenseq_range_lookup(const ARRAY_TYPE(seq_range) *array,
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen         uint32_t seq, unsigned int *idx_r)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen{
eb5ea3f4513ff2999892b8d904551f58b74f65f9Timo Sirainen    const struct seq_range *data;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    unsigned int idx, left_idx, right_idx, count;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
eb5ea3f4513ff2999892b8d904551f58b74f65f9Timo Sirainen    data = array_get(array, &count);
25480af2e21cf136e461ec802177f52b43154485Timo Sirainen    i_assert(count < INT_MAX);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    idx = 0; left_idx = 0; right_idx = count;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    while (left_idx < right_idx) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        idx = (left_idx + right_idx) / 2;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        if (data[idx].seq1 <= seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            if (data[idx].seq2 >= seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                /* it's already in the range */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                *idx_r = idx;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                return TRUE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            left_idx = idx+1;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        } else {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            right_idx = idx;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    }
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen    if (left_idx > idx)
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen        idx++;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    *idx_r = idx;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    return FALSE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen}
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainenbool seq_range_array_add(ARRAY_TYPE(seq_range) *array, uint32_t seq)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen{
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    struct seq_range *data, value;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    unsigned int idx, count;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    value.seq1 = value.seq2 = seq;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen    data = array_get_modifiable(array, &count);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    if (count == 0) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        array_append(array, &value, 1);
c991d8c2c0d5d6c025e24fc00cb06dd61c42456dTimo Sirainen        return FALSE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    /* quick checks */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    if (data[count-1].seq2 < seq) {
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen        if (data[count-1].seq2 == seq-1) {
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen            /* grow last range */
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen            data[count-1].seq2 = seq;
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen        } else {
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen            array_append(array, &value, 1);
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen        }
c991d8c2c0d5d6c025e24fc00cb06dd61c42456dTimo Sirainen        return FALSE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    if (data[0].seq1 > seq) {
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen        if (data[0].seq1-1 == seq) {
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen            /* grow down first range */
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen            data[0].seq1 = seq;
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen        } else {
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen            array_insert(array, 0, &value, 1);
4082d5b171d1c3a00ba705093d62b8afc9cf17aeTimo Sirainen        }
c991d8c2c0d5d6c025e24fc00cb06dd61c42456dTimo Sirainen        return FALSE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    /* somewhere in the middle, array is sorted so find it with
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen       binary search */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    if (seq_range_lookup(array, seq, &idx))
c991d8c2c0d5d6c025e24fc00cb06dd61c42456dTimo Sirainen        return TRUE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen    /* idx == count couldn't happen because we already handle it above */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    i_assert(idx < count && data[idx].seq1 >= seq);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    i_assert(data[idx].seq1 > seq || data[idx].seq2 < seq);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    if (data[idx].seq1 == seq+1) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        data[idx].seq1 = seq;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        if (idx > 0 && data[idx-1].seq2 == seq-1) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            /* merge */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            data[idx-1].seq2 = data[idx].seq2;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            array_delete(array, idx, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    } else {
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen        if (idx > 0 && data[idx-1].seq2 == seq-1)
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen            idx--;
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen        if (data[idx].seq2 == seq-1) {
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen            i_assert(idx+1 < count); /* already handled above */
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen            data[idx].seq2 = seq;
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen            if (data[idx+1].seq1 == seq+1) {
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen                /* merge */
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen                data[idx+1].seq1 = data[idx].seq1;
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen                array_delete(array, idx, 1);
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen            }
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen        } else {
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen            array_insert(array, idx, &value, 1);
d06d6667bac64aabe1efb216af56ca45108d63b0Timo Sirainen        }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    }
c991d8c2c0d5d6c025e24fc00cb06dd61c42456dTimo Sirainen    return FALSE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen}
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainenvoid seq_range_array_add_with_init(ARRAY_TYPE(seq_range) *array,
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainen                   unsigned int init_count, uint32_t seq)
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainen{
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainen    if (!array_is_created(array))
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainen        i_array_init(array, init_count);
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen    seq_range_array_add(array, seq);
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainen}
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainen
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmodystatic void
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmodyseq_range_array_add_range_internal(ARRAY_TYPE(seq_range) *array,
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody                   uint32_t seq1, uint32_t seq2,
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody                   unsigned int *r_count)
605eca549c08af753e05c25937bcccd66079c321Timo Sirainen{
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen    struct seq_range *data, value;
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen    unsigned int idx1, idx2, count;
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen    seq_range_lookup(array, seq1, &idx1);
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen    seq_range_lookup(array, seq2, &idx2);
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen    data = array_get_modifiable(array, &count);
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody    if (r_count != NULL) {
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        /* Find number we're adding by counting the number we're
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody           not adding, and subtracting that from the nominal range. */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        unsigned int added = seq2+1 - seq1;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        unsigned int countidx2 = idx2;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        unsigned int overcounted = 0u, notadded = 0u;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        unsigned int i;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        if (idx1 == count) {
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            /* not in a range as too far right */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        } else if (seq1 < data[idx1].seq1) {
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            /* not in a range, to the left of a real range */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        } else {
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            /* count the whole of this range, which is an overcount */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            overcounted += seq1 - data[idx1].seq1;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            /* fencepost check: equality means the whole range is valid,
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody               therefore there's no overcounting. Result = 0 overcount */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        }
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        if (idx2 == count) {
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            /* not in a range as too far right */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        } else  if (seq2 < data[idx2].seq1) {
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            /* not in a range, to the left of a real range */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        } else {
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            /* count the whole of this range, which is an overcount */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            overcounted += data[idx2].seq2 - seq2;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            countidx2++; /* may become == count i.e. past the end */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            /* fencepost check: equality  means the whole range is valid,
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody               therefore there's no overcounting. Result = 0 overcount. */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        }
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        /* Now count how many we're not adding */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        for (i = idx1; i < countidx2; i++)
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody            notadded += data[i].seq2+1 - data[i].seq1;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        /* Maybe the not added tally included some over-counting too */
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        added -= (notadded - overcounted);
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody        *r_count = added;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody    }
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen    if (idx1 > 0 && data[idx1-1].seq2+1 == seq1)
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen        idx1--;
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen    if (idx1 == idx2 &&
c8bac7666cdc780a3390110e420350fffb62b909Timo Sirainen        (idx2 == count || (seq2 < (uint32_t)-1 && data[idx2].seq1 > seq2+1)) &&
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen        (idx1 == 0 || data[idx1-1].seq2 < seq1-1)) {
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen        /* no overlapping */
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen        value.seq1 = seq1;
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen        value.seq2 = seq2;
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen        array_insert(array, idx1, &value, 1);
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen    } else {
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen        i_assert(idx1 < count);
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen        if (seq1 < data[idx1].seq1)
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen            data[idx1].seq1 = seq1;
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen        if (seq2 > data[idx1].seq2) {
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen            /* merge */
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen            if (idx2 == count ||
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen                data[idx2].seq1 > seq2+1)
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen                idx2--;
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen            if (seq2 >= data[idx2].seq2) {
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen                data[idx1].seq2 = seq2;
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen            } else {
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen                data[idx1].seq2 = data[idx2].seq2;
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen            }
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen            array_delete(array, idx1 + 1, idx2 - idx1);
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen        }
355fe8b5d02904df39e793f66da5432d86649d4aTimo Sirainen    }
605eca549c08af753e05c25937bcccd66079c321Timo Sirainen}
605eca549c08af753e05c25937bcccd66079c321Timo Sirainen
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmodyvoid seq_range_array_add_range(ARRAY_TYPE(seq_range) *array,
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody                   uint32_t seq1, uint32_t seq2)
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody{
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody    seq_range_array_add_range_internal(array, seq1, seq2, NULL);
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody}
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmodyunsigned int seq_range_array_add_range_count(ARRAY_TYPE(seq_range) *array,
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody                         uint32_t seq1, uint32_t seq2)
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody{
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody    unsigned int count;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody    seq_range_array_add_range_internal(array, seq1, seq2, &count);
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody    return count;
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody}
ba66ac5557ca97d8a6fe5d524056264a9f92243cPhil Carmody
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainenvoid seq_range_array_merge(ARRAY_TYPE(seq_range) *dest,
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainen               const ARRAY_TYPE(seq_range) *src)
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainen{
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainen    const struct seq_range *range;
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainen
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainen    if (array_count(dest) == 0) {
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainen        array_append_array(dest, src);
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainen        return;
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainen    }
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainen
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen    array_foreach(src, range)
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen        seq_range_array_add_range(dest, range->seq1, range->seq2);
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainen}
6646bd844c85d5b27451199d8868b6d2357cd293Timo Sirainen
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainenbool seq_range_array_remove(ARRAY_TYPE(seq_range) *array, uint32_t seq)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen{
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    struct seq_range *data, value;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    unsigned int idx, left_idx, right_idx, count;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    if (!array_is_created(array))
1d3f7c1278168d5b1cbfa9a2cc9929a0909056b4Timo Sirainen        return FALSE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen    data = array_get_modifiable(array, &count);
e8ecd8f24ffc612f5d0be10f7931ac619f1eab88Timo Sirainen    if (count == 0)
1d3f7c1278168d5b1cbfa9a2cc9929a0909056b4Timo Sirainen        return FALSE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    /* quick checks */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    if (seq > data[count-1].seq2 || seq < data[0].seq1) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        /* outside the range */
1d3f7c1278168d5b1cbfa9a2cc9929a0909056b4Timo Sirainen        return FALSE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    if (data[count-1].seq2 == seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        /* shrink last range */
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen        if (data[count-1].seq1 != data[count-1].seq2)
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen            data[count-1].seq2--;
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen        else
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen            array_delete(array, count-1, 1);
1d3f7c1278168d5b1cbfa9a2cc9929a0909056b4Timo Sirainen        return TRUE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    if (data[0].seq1 == seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        /* shrink up first range */
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen        if (data[0].seq1 != data[0].seq2)
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen            data[0].seq1++;
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen        else
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen            array_delete(array, 0, 1);
1d3f7c1278168d5b1cbfa9a2cc9929a0909056b4Timo Sirainen        return TRUE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    /* somewhere in the middle, array is sorted so find it with
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen       binary search */
25480af2e21cf136e461ec802177f52b43154485Timo Sirainen    i_assert(count < INT_MAX);
8bb360f9e5de1c25e4f875205bb06e8bf15dae14Timo Sirainen    left_idx = 0; right_idx = count;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    while (left_idx < right_idx) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        idx = (left_idx + right_idx) / 2;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        if (data[idx].seq1 > seq)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            right_idx = idx;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        else if (data[idx].seq2 < seq)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            left_idx = idx+1;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        else {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            /* found it */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            if (data[idx].seq1 == seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                if (data[idx].seq1 == data[idx].seq2) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                    /* a single sequence range.
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                       remove it entirely */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                    array_delete(array, idx, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                } else {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                    /* shrink the range */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                    data[idx].seq1++;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            } else if (data[idx].seq2 == seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                /* shrink the range */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                data[idx].seq2--;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            } else {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                /* split the sequence range */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                value.seq1 = seq + 1;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                value.seq2 = data[idx].seq2;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen                data[idx].seq2 = seq - 1;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
4c9a72e0988d462df49810984dc93b3fd4a24c23Timo Sirainen                array_insert(array, idx + 1, &value, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen            }
1d3f7c1278168d5b1cbfa9a2cc9929a0909056b4Timo Sirainen            return TRUE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen        }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    }
1d3f7c1278168d5b1cbfa9a2cc9929a0909056b4Timo Sirainen    return FALSE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen}
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainenunsigned int seq_range_array_remove_range(ARRAY_TYPE(seq_range) *array,
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen                      uint32_t seq1, uint32_t seq2)
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen{
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen    const struct seq_range *data;
ef174bf5299348e8c0662d235341869f319cfe54Timo Sirainen    unsigned int idx, idx2, count, remove_count = 0;
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen    /* remove first and last. this makes sure that everything between
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen       can simply be deleted with array_delete().
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen       FIXME: it would be faster if we did only one binary lookup here
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen       and handled the splitting ourself.. */
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen    if (seq_range_array_remove(array, seq1))
ef174bf5299348e8c0662d235341869f319cfe54Timo Sirainen        remove_count++;
749a9676d265a517c7a731f5b9336c524a49e6a6Timo Sirainen    if (seq1 == seq2)
ef174bf5299348e8c0662d235341869f319cfe54Timo Sirainen        return remove_count;
749a9676d265a517c7a731f5b9336c524a49e6a6Timo Sirainen    seq1++;
ef174bf5299348e8c0662d235341869f319cfe54Timo Sirainen
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen    if (seq_range_array_remove(array, seq2--))
ef174bf5299348e8c0662d235341869f319cfe54Timo Sirainen        remove_count++;
5e85a6a1349177c613dea55aabb20d857b8240a5Timo Sirainen    if (seq1 > seq2)
ef174bf5299348e8c0662d235341869f319cfe54Timo Sirainen        return remove_count;
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen    /* find the beginning */
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen    data = array_get(array, &count);
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen    seq_range_lookup(array, seq1, &idx);
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen    if (idx == count)
ef174bf5299348e8c0662d235341869f319cfe54Timo Sirainen        return remove_count;
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen    i_assert(data[idx].seq1 >= seq1);
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen    for (idx2 = idx; idx2 < count; idx2++) {
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen        if (data[idx2].seq1 > seq2)
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen            break;
ef174bf5299348e8c0662d235341869f319cfe54Timo Sirainen        remove_count += data[idx2].seq2 - data[idx2].seq1 + 1;
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen    }
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen    array_delete(array, idx, idx2-idx);
ef174bf5299348e8c0662d235341869f319cfe54Timo Sirainen    return remove_count;
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen}
ba14267101444b8f144091cefd437e1ea44d3e32Timo Sirainen
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainenunsigned int seq_range_array_remove_seq_range(ARRAY_TYPE(seq_range) *dest,
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen                          const ARRAY_TYPE(seq_range) *src)
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen{
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    unsigned int ret = 0;
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    const struct seq_range *src_range;
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen    array_foreach(src, src_range) {
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen        ret += seq_range_array_remove_range(dest, src_range->seq1,
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen                            src_range->seq2);
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    }
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    return ret;
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen}
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainenvoid seq_range_array_remove_nth(ARRAY_TYPE(seq_range) *array,
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen                uint32_t n, uint32_t count)
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen{
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen    struct seq_range_iter iter;
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen    uint32_t seq1, seq2;
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen    if (count == 0)
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen        return;
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen    seq_range_array_iter_init(&iter, array);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen    if (!seq_range_array_iter_nth(&iter, n, &seq1)) {
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen        /* n points beyond array */
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen        return;
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen    }
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen    if (count-1 >= (uint32_t)-1 - n ||
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen        !seq_range_array_iter_nth(&iter, n + (count-1), &seq2)) {
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen        /* count points beyond array */
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen        seq2 = (uint32_t)-1;
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen    }
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen    seq_range_array_remove_range(array, seq1, seq2);
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen}
199566f5a171b2c43b9a5254634f6bf47b8baca8Timo Sirainen
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainenunsigned int seq_range_array_intersect(ARRAY_TYPE(seq_range) *dest,
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen                       const ARRAY_TYPE(seq_range) *src)
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen{
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    const struct seq_range *src_range;
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    unsigned int i, count, ret = 0;
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    uint32_t last_seq = 0;
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    src_range = array_get(src, &count);
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    for (i = 0; i < count; i++) {
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen        if (last_seq + 1 < src_range[i].seq1) {
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen            ret += seq_range_array_remove_range(dest,
e34d170f8f0e084bd94bfbc1a7085ece67e508dfTimo Sirainen                    last_seq + 1, src_range[i].seq1 - 1);
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen        }
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen        last_seq = src_range[i].seq2;
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    }
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    if (last_seq != (uint32_t)-1) {
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen        ret += seq_range_array_remove_range(dest, last_seq + 1,
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen                            (uint32_t)-1);
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen    }
461ffead9720d1e516b959d5e41f049c73d38c7cTimo Sirainen    return ret;
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen}
c47e837a127c533e67debafde8ccf9691041be16Timo Sirainen
eb5ea3f4513ff2999892b8d904551f58b74f65f9Timo Sirainenbool seq_range_exists(const ARRAY_TYPE(seq_range) *array, uint32_t seq)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen{
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    unsigned int idx;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen    return seq_range_lookup(array, seq, &idx);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen}
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainenbool seq_range_array_have_common(const ARRAY_TYPE(seq_range) *array1,
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen                 const ARRAY_TYPE(seq_range) *array2)
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen{
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen    const struct seq_range *range1, *range2;
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen    unsigned int i1, i2, count1, count2;
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen    range1 = array_get(array1, &count1);
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen    range2 = array_get(array2, &count2);
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen    for (i1 = i2 = 0; i1 < count1 && i2 < count2; ) {
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen        if (range1[i1].seq1 <= range2[i2].seq2 &&
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen            range1[i1].seq2 >= range2[i2].seq1)
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen            return TRUE;
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen        if (range1[i1].seq1 < range2[i2].seq1)
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen            i1++;
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen        else
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen            i2++;
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen    }
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen    return FALSE;
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen}
e4cebacdec9c9e5b685dde5f7cbf7a5cf7e1d248Timo Sirainen
9905ec03fb2011419caeac4cd5a1b6c28ab50a73Timo Sirainenunsigned int seq_range_count(const ARRAY_TYPE(seq_range) *array)
9905ec03fb2011419caeac4cd5a1b6c28ab50a73Timo Sirainen{
9905ec03fb2011419caeac4cd5a1b6c28ab50a73Timo Sirainen    const struct seq_range *range;
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen    unsigned int seq_count = 0;
9905ec03fb2011419caeac4cd5a1b6c28ab50a73Timo Sirainen
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen    array_foreach(array, range)
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen        seq_count += range->seq2 - range->seq1 + 1;
9905ec03fb2011419caeac4cd5a1b6c28ab50a73Timo Sirainen    return seq_count;
9905ec03fb2011419caeac4cd5a1b6c28ab50a73Timo Sirainen}
9905ec03fb2011419caeac4cd5a1b6c28ab50a73Timo Sirainen
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainenvoid seq_range_array_invert(ARRAY_TYPE(seq_range) *array,
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen                uint32_t min_seq, uint32_t max_seq)
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen{
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    struct seq_range *range, value;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    unsigned int i, count;
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen    uint32_t prev_min_seq;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    if (array_is_created(array))
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        range = array_get_modifiable(array, &count);
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    else {
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        range = NULL;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        count = 0;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    }
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    if (count == 0) {
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        /* empty -> full */
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        if (!array_is_created(array))
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen            i_array_init(array, 4);
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        value.seq1 = min_seq;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        value.seq2 = max_seq;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        array_append(array, &value, 1);
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        return;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    }
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    i_assert(range[0].seq1 >= min_seq);
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    i_assert(range[count-1].seq2 <= max_seq);
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    if (range[0].seq1 == min_seq && range[0].seq2 == max_seq) {
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        /* full -> empty */
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        array_clear(array);
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        return;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    }
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    for (i = 0; i < count; ) {
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen        prev_min_seq = min_seq;
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen        min_seq = range[i].seq2;
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen        if (range[i].seq1 == prev_min_seq) {
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen            array_delete(array, i, 1);
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen            range = array_get_modifiable(array, &count);
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        } else {
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen            range[i].seq2 = range[i].seq1 - 1;
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen            range[i].seq1 = prev_min_seq;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen            i++;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        }
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen        if (min_seq >= max_seq) {
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen            /* max_seq is reached. the rest of the array should be
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen               empty. we'll return here, because min_seq++ may
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen               wrap to 0. */
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen            i_assert(min_seq == max_seq);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen            i_assert(i == count);
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen            return;
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen        }
369764cc0856a4c5e9b4081de8c4e29e90f11ccdTimo Sirainen        min_seq++;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    }
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    if (min_seq <= max_seq) {
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        value.seq1 = min_seq;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        value.seq2 = max_seq;
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen        array_append(array, &value, 1);
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen    }
90b50df264b57e0f63cd8cc6aea1ce3bb7cf5f64Timo Sirainen}
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainenvoid seq_range_array_iter_init(struct seq_range_iter *iter_r,
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen                   const ARRAY_TYPE(seq_range) *array)
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen{
efe78d3ba24fc866af1c79b9223dc0809ba26cadStephan Bosch    i_zero(iter_r);
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen    iter_r->array = array;
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen}
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainenbool seq_range_array_iter_nth(struct seq_range_iter *iter, unsigned int n,
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen                  uint32_t *seq_r)
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen{
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen    const struct seq_range *range;
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen    unsigned int i, count, diff;
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen    if (n < iter->prev_n) {
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen        /* iterating backwards, don't bother optimizing */
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen        iter->prev_n = 0;
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen        iter->prev_idx = 0;
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen    }
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen    range = array_get(iter->array, &count);
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen    for (i = iter->prev_idx; i < count; i++) {
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen        diff = range[i].seq2 - range[i].seq1;
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen        if (n <= iter->prev_n + diff) {
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen            i_assert(n >= iter->prev_n);
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen            *seq_r = range[i].seq1 + (n - iter->prev_n);
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen            iter->prev_idx = i;
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen            return TRUE;
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen        }
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen        iter->prev_n += diff + 1;
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen    }
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen    iter->prev_idx = i;
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen    return FALSE;
5fdeff082e329e4a85bb7e74aaec2c35e2288557Timo Sirainen}