Mercurial > dovecot > original-hg > dovecot-1.2
changeset 7743:18f5d0538baa HEAD
Implemented optimized seq_range_array_add_range().
author | Timo Sirainen <tss@iki.fi> |
---|---|
date | Fri, 29 Feb 2008 05:02:48 +0200 |
parents | 338ea1ecca5f |
children | 1d79c534b54b |
files | src/lib/seq-range-array.c |
diffstat | 1 files changed, 37 insertions(+), 9 deletions(-) [+] |
line wrap: on
line diff
--- a/src/lib/seq-range-array.c Fri Feb 29 05:01:56 2008 +0200 +++ b/src/lib/seq-range-array.c Fri Feb 29 05:02:48 2008 +0200 @@ -27,6 +27,8 @@ right_idx = idx; } } + if (left_idx > idx) + idx++; *idx_r = idx; return FALSE; } @@ -73,10 +75,7 @@ if (seq_range_lookup(array, seq, &idx)) return; - if (data[idx].seq2 < seq) - idx++; - - /* idx == count couldn't happen because we already handle it above */ + /* 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); @@ -103,9 +102,40 @@ void seq_range_array_add_range(ARRAY_TYPE(seq_range) *array, uint32_t seq1, uint32_t seq2) { - /* FIXME: optimize */ - for (; seq1 <= seq2; seq1++) - seq_range_array_add(array, 2, seq1); + struct seq_range *data, value; + unsigned int idx1, idx2, count; + + (void)seq_range_lookup(array, seq1, &idx1); + (void)seq_range_lookup(array, seq2, &idx2); + + data = array_get_modifiable(array, &count); + if (idx1 > 0 && data[idx1-1].seq2+1 == seq1) + idx1--; + + if (idx1 == idx2 && + (idx2 == count || 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); + } + } } bool seq_range_array_remove(ARRAY_TYPE(seq_range) *array, uint32_t seq) @@ -205,8 +235,6 @@ /* find the beginning */ data = array_get(array, &count); (void)seq_range_lookup(array, seq1, &idx); - if (idx < count && data[idx].seq2 < seq1) - idx++; if (idx == count) return remove_count;