Mercurial > dovecot > original-hg > dovecot-1.2
view src/lib/seq-range-array.c @ 7086:7ed926ed7aa4 HEAD
Updated copyright notices to include year 2008.
author | Timo Sirainen <tss@iki.fi> |
---|---|
date | Tue, 01 Jan 2008 22:05:21 +0200 |
parents | 0a3186f44dff |
children | 010485455f75 |
line wrap: on
line source
/* Copyright (c) 2005-2008 Dovecot authors, see the included COPYING file */ #include "lib.h" #include "array.h" #include "seq-range-array.h" static bool 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); 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; } } *idx_r = idx; return FALSE; } void seq_range_array_add(ARRAY_TYPE(seq_range) *array, unsigned int init_count, uint32_t seq) { struct seq_range *data, value; unsigned int idx, count; value.seq1 = value.seq2 = seq; if (!array_is_created(array)) i_array_init(array, init_count); data = array_get_modifiable(array, &count); if (count == 0) { array_append(array, &value, 1); return; } /* quick checks */ if (data[count-1].seq2 == seq-1) { /* grow last range */ data[count-1].seq2 = seq; return; } if (data[count-1].seq2 < seq) { array_append(array, &value, 1); return; } if (data[0].seq1 == seq+1) { /* grow down first range */ data[0].seq1 = seq; return; } if (data[0].seq1 > seq) { array_insert(array, 0, &value, 1); return; } /* somewhere in the middle, array is sorted so find it with binary search */ 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 */ 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 (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); } } 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_delete(array, 0, 1); return TRUE; } /* somewhere in the middle, array is sorted so find it with binary search */ idx = 0; 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); (void)seq_range_lookup(array, seq1, &idx); if (idx < count && data[idx].seq2 < 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; remove_count += data[idx2].seq2 - data[idx2].seq1 + 1; } 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 ret = 0; const struct seq_range *src_range; unsigned int i, count; src_range = array_get(src, &count); for (i = 0; i < count; i++) { ret += seq_range_array_remove_range(dest, src_range[i].seq1, src_range[i].seq2); } return ret; } unsigned int seq_range_array_remove_invert_range(ARRAY_TYPE(seq_range) *dest, const ARRAY_TYPE(seq_range) *src) { const struct seq_range *src_range; unsigned int i, count, ret = 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) { ret += seq_range_array_remove_range(dest, last_seq + 1, src_range[i].seq1 - 1); } last_seq = src_range[i].seq2; } if (last_seq != (uint32_t)-1) { ret += seq_range_array_remove_range(dest, last_seq + 1, (uint32_t)-1); } return ret; } bool seq_range_exists(const ARRAY_TYPE(seq_range) *array, uint32_t seq) { unsigned int idx; return seq_range_lookup(array, seq, &idx); } 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 next_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_append(array, &value, 1); 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; ) { next_min_seq = range[i].seq2 + 1; if (range[i].seq1 == min_seq) { array_delete(array, i, 1); range = array_get_modifiable(array, &count); } else { range[i].seq2 = range[i].seq1 - 1; range[i].seq1 = min_seq; i++; } min_seq = next_min_seq; } if (min_seq <= max_seq) { value.seq1 = min_seq; value.seq2 = max_seq; array_append(array, &value, 1); } }