dovecot/original-hg/dovecot-1.2: src/lib/seq-range-array.c annotate

annotate src/lib/seq-range-array.c @ 9575:0a00dcc4f0ea HEAD

lib-storage: Allow shared namespace prefix to use %variable modifiers.

author	Timo Sirainen <tss@iki.fi>
date	Wed, 26 May 2010 17:07:51 +0100
parents	00cd9aacd03c
children

rev	line source
9532 00cd9aacd03c Updated copyright notices to include year 2010. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	1 /* Copyright (c) 2005-2010 Dovecot authors, see the included COPYING file */
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	2
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	3 #include "lib.h"
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	4 #include "array.h"
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	5 #include "seq-range-array.h"
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	6
4687 c8b565e87966 seq_range_exists() can take a const pointer to the array. Timo Sirainen <tss@iki.fi> parents: 4596 diff changeset	7 static bool seq_range_lookup(const ARRAY_TYPE(seq_range) *array,
4451 1a35d53c18fc Array API redesigned to work using unions. It now provides type safety Timo Sirainen <tss@iki.fi> parents: 4206 diff changeset	8 uint32_t seq, unsigned int *idx_r)
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	9 {
4687 c8b565e87966 seq_range_exists() can take a const pointer to the array. Timo Sirainen <tss@iki.fi> parents: 4596 diff changeset	10 const struct seq_range *data;
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	11 unsigned int idx, left_idx, right_idx, count;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	12
4687 c8b565e87966 seq_range_exists() can take a const pointer to the array. Timo Sirainen <tss@iki.fi> parents: 4596 diff changeset	13 data = array_get(array, &count);
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	14
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	15 idx = 0; left_idx = 0; right_idx = count;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	16 while (left_idx < right_idx) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	17 idx = (left_idx + right_idx) / 2;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	18
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	19 if (data[idx].seq1 <= seq) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	20 if (data[idx].seq2 >= seq) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	21 /* it's already in the range */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	22 *idx_r = idx;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	23 return TRUE;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	24 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	25 left_idx = idx+1;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	26 } else {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	27 right_idx = idx;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	28 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	29 }
7308 e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	30 if (left_idx > idx)
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	31 idx++;
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	32 *idx_r = idx;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	33 return FALSE;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	34 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	35
4451 1a35d53c18fc Array API redesigned to work using unions. It now provides type safety Timo Sirainen <tss@iki.fi> parents: 4206 diff changeset	36 void seq_range_array_add(ARRAY_TYPE(seq_range) *array,
1a35d53c18fc Array API redesigned to work using unions. It now provides type safety Timo Sirainen <tss@iki.fi> parents: 4206 diff changeset	37 unsigned int init_count, uint32_t seq)
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	38 {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	39 struct seq_range *data, value;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	40 unsigned int idx, count;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	41
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	42 value.seq1 = value.seq2 = seq;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	43
4451 1a35d53c18fc Array API redesigned to work using unions. It now provides type safety Timo Sirainen <tss@iki.fi> parents: 4206 diff changeset	44 if (!array_is_created(array))
4596 bf4e98a0de3f Replaced ARRAY_CREATE() macro with [ipt]_array_init() macros. The macro Timo Sirainen <tss@iki.fi> parents: 4594 diff changeset	45 i_array_init(array, init_count);
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	46
4451 1a35d53c18fc Array API redesigned to work using unions. It now provides type safety Timo Sirainen <tss@iki.fi> parents: 4206 diff changeset	47 data = array_get_modifiable(array, &count);
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	48 if (count == 0) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	49 array_append(array, &value, 1);
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	50 return;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	51 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	52
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	53 /* quick checks */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	54 if (data[count-1].seq2 == seq-1) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	55 /* grow last range */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	56 data[count-1].seq2 = seq;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	57 return;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	58 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	59 if (data[count-1].seq2 < seq) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	60 array_append(array, &value, 1);
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	61 return;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	62 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	63 if (data[0].seq1 == seq+1) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	64 /* grow down first range */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	65 data[0].seq1 = seq;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	66 return;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	67 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	68 if (data[0].seq1 > seq) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	69 array_insert(array, 0, &value, 1);
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	70 return;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	71 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	72
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	73 /* somewhere in the middle, array is sorted so find it with
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	74 binary search */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	75 if (seq_range_lookup(array, seq, &idx))
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	76 return;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	77
7308 e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	78 /* idx == count couldn't happen because we already handle it above */
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	79 i_assert(idx < count && data[idx].seq1 >= seq);
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	80 i_assert(data[idx].seq1 > seq \|\| data[idx].seq2 < seq);
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	81
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	82 if (data[idx].seq1 == seq+1) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	83 data[idx].seq1 = seq;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	84 if (idx > 0 && data[idx-1].seq2 == seq-1) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	85 /* merge */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	86 data[idx-1].seq2 = data[idx].seq2;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	87 array_delete(array, idx, 1);
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	88 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	89 } else if (data[idx].seq2 == seq-1) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	90 i_assert(idx+1 < count); /* already handled above */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	91 data[idx].seq2 = seq;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	92 if (data[idx+1].seq1 == seq+1) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	93 /* merge */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	94 data[idx+1].seq1 = data[idx].seq1;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	95 array_delete(array, idx, 1);
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	96 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	97 } else {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	98 array_insert(array, idx, &value, 1);
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	99 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	100 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	101
7127 010485455f75 Added unoptimized seq_range_array_add_range() Timo Sirainen <tss@iki.fi> parents: 7086 diff changeset	102 void seq_range_array_add_range(ARRAY_TYPE(seq_range) *array,
010485455f75 Added unoptimized seq_range_array_add_range() Timo Sirainen <tss@iki.fi> parents: 7086 diff changeset	103 uint32_t seq1, uint32_t seq2)
010485455f75 Added unoptimized seq_range_array_add_range() Timo Sirainen <tss@iki.fi> parents: 7086 diff changeset	104 {
7308 e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	105 struct seq_range *data, value;
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	106 unsigned int idx1, idx2, count;
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	107
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	108 (void)seq_range_lookup(array, seq1, &idx1);
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	109 (void)seq_range_lookup(array, seq2, &idx2);
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	110
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	111 data = array_get_modifiable(array, &count);
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	112 if (idx1 > 0 && data[idx1-1].seq2+1 == seq1)
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	113 idx1--;
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	114
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	115 if (idx1 == idx2 &&
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	116 (idx2 == count \|\| data[idx2].seq1 > seq2+1) &&
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	117 (idx1 == 0 \|\| data[idx1-1].seq2 < seq1-1)) {
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	118 /* no overlapping */
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	119 value.seq1 = seq1;
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	120 value.seq2 = seq2;
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	121 array_insert(array, idx1, &value, 1);
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	122 } else {
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	123 i_assert(idx1 < count);
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	124 if (seq1 < data[idx1].seq1)
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	125 data[idx1].seq1 = seq1;
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	126 if (seq2 > data[idx1].seq2) {
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	127 /* merge */
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	128 if (idx2 == count \|\|
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	129 data[idx2].seq1 > seq2+1)
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	130 idx2--;
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	131 if (seq2 >= data[idx2].seq2) {
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	132 data[idx1].seq2 = seq2;
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	133 } else {
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	134 data[idx1].seq2 = data[idx2].seq2;
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	135 }
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	136 array_delete(array, idx1 + 1, idx2 - idx1);
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	137 }
e318f3c8a724 Implemented optimized seq_range_array_add_range(). Timo Sirainen <tss@iki.fi> parents: 7127 diff changeset	138 }
7127 010485455f75 Added unoptimized seq_range_array_add_range() Timo Sirainen <tss@iki.fi> parents: 7086 diff changeset	139 }
010485455f75 Added unoptimized seq_range_array_add_range() Timo Sirainen <tss@iki.fi> parents: 7086 diff changeset	140
7646 f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	141 void seq_range_array_merge(ARRAY_TYPE(seq_range) *dest,
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	142 const ARRAY_TYPE(seq_range) *src)
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	143 {
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	144 const struct seq_range *range;
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	145 unsigned int i, count;
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	146
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	147 if (array_count(dest) == 0) {
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	148 array_append_array(dest, src);
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	149 return;
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	150 }
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	151
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	152 range = array_get(src, &count);
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	153 for (i = 0; i < count; i++)
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	154 seq_range_array_add_range(dest, range[i].seq1, range[i].seq2);
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	155 }
f0dc2a3dee54 Added seq_range_array_merge() Timo Sirainen <tss@iki.fi> parents: 7628 diff changeset	156
6037 d911d943438e Recent flag handling rewrite. Still not perfect with maildir. Timo Sirainen <tss@iki.fi> parents: 4932 diff changeset	157 bool seq_range_array_remove(ARRAY_TYPE(seq_range) *array, uint32_t seq)
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	158 {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	159 struct seq_range *data, value;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	160 unsigned int idx, left_idx, right_idx, count;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	161
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	162 if (!array_is_created(array))
6037 d911d943438e Recent flag handling rewrite. Still not perfect with maildir. Timo Sirainen <tss@iki.fi> parents: 4932 diff changeset	163 return FALSE;
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	164
4451 1a35d53c18fc Array API redesigned to work using unions. It now provides type safety Timo Sirainen <tss@iki.fi> parents: 4206 diff changeset	165 data = array_get_modifiable(array, &count);
4173 1ba7983b814c seq_range_array_remove(): Don't crash if array is empty. Timo Sirainen <tss@iki.fi> parents: 4112 diff changeset	166 if (count == 0)
6037 d911d943438e Recent flag handling rewrite. Still not perfect with maildir. Timo Sirainen <tss@iki.fi> parents: 4932 diff changeset	167 return FALSE;
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	168
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	169 /* quick checks */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	170 if (seq > data[count-1].seq2 \|\| seq < data[0].seq1) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	171 /* outside the range */
6037 d911d943438e Recent flag handling rewrite. Still not perfect with maildir. Timo Sirainen <tss@iki.fi> parents: 4932 diff changeset	172 return FALSE;
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	173 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	174 if (data[count-1].seq2 == seq) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	175 /* shrink last range */
4112 d7e169797e3e Removal didn't work properly from beginning/end if the range contained only Timo Sirainen <tss@iki.fi> parents: 3863 diff changeset	176 if (data[count-1].seq1 != data[count-1].seq2)
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only Timo Sirainen <tss@iki.fi> parents: 3863 diff changeset	177 data[count-1].seq2--;
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only Timo Sirainen <tss@iki.fi> parents: 3863 diff changeset	178 else
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only Timo Sirainen <tss@iki.fi> parents: 3863 diff changeset	179 array_delete(array, count-1, 1);
6037 d911d943438e Recent flag handling rewrite. Still not perfect with maildir. Timo Sirainen <tss@iki.fi> parents: 4932 diff changeset	180 return TRUE;
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	181 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	182 if (data[0].seq1 == seq) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	183 /* shrink up first range */
4112 d7e169797e3e Removal didn't work properly from beginning/end if the range contained only Timo Sirainen <tss@iki.fi> parents: 3863 diff changeset	184 if (data[0].seq1 != data[0].seq2)
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only Timo Sirainen <tss@iki.fi> parents: 3863 diff changeset	185 data[0].seq1++;
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only Timo Sirainen <tss@iki.fi> parents: 3863 diff changeset	186 else
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only Timo Sirainen <tss@iki.fi> parents: 3863 diff changeset	187 array_delete(array, 0, 1);
6037 d911d943438e Recent flag handling rewrite. Still not perfect with maildir. Timo Sirainen <tss@iki.fi> parents: 4932 diff changeset	188 return TRUE;
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	189 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	190
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	191 /* somewhere in the middle, array is sorted so find it with
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	192 binary search */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	193 idx = 0; left_idx = 0; right_idx = count;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	194 while (left_idx < right_idx) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	195 idx = (left_idx + right_idx) / 2;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	196
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	197 if (data[idx].seq1 > seq)
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	198 right_idx = idx;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	199 else if (data[idx].seq2 < seq)
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	200 left_idx = idx+1;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	201 else {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	202 /* found it */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	203 if (data[idx].seq1 == seq) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	204 if (data[idx].seq1 == data[idx].seq2) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	205 /* a single sequence range.
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	206 remove it entirely */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	207 array_delete(array, idx, 1);
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	208 } else {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	209 /* shrink the range */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	210 data[idx].seq1++;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	211 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	212 } else if (data[idx].seq2 == seq) {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	213 /* shrink the range */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	214 data[idx].seq2--;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	215 } else {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	216 /* split the sequence range */
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	217 value.seq1 = seq + 1;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	218 value.seq2 = data[idx].seq2;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	219 data[idx].seq2 = seq - 1;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	220
4206 ec7e56827ea8 Fix for seq_range_array_remove() Timo Sirainen <tss@iki.fi> parents: 4173 diff changeset	221 array_insert(array, idx + 1, &value, 1);
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	222 }
6037 d911d943438e Recent flag handling rewrite. Still not perfect with maildir. Timo Sirainen <tss@iki.fi> parents: 4932 diff changeset	223 return TRUE;
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	224 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	225 }
6037 d911d943438e Recent flag handling rewrite. Still not perfect with maildir. Timo Sirainen <tss@iki.fi> parents: 4932 diff changeset	226 return FALSE;
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	227 }
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	228
6040 fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	229 unsigned int seq_range_array_remove_range(ARRAY_TYPE(seq_range) *array,
fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	230 uint32_t seq1, uint32_t seq2)
4932 f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	231 {
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	232 const struct seq_range *data;
6040 fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	233 unsigned int idx, idx2, count, remove_count = 0;
4932 f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	234
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	235 /* remove first and last. this makes sure that everything between
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	236 can simply be deleted with array_delete().
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	237
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	238 FIXME: it would be faster if we did only one binary lookup here
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	239 and handled the splitting ourself.. */
6852 6ed01546f211 seq_range_array_remove_range(): Don't break if seq2 is -1U. Timo Sirainen <tss@iki.fi> parents: 6758 diff changeset	240 if (seq_range_array_remove(array, seq1))
6040 fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	241 remove_count++;
6852 6ed01546f211 seq_range_array_remove_range(): Don't break if seq2 is -1U. Timo Sirainen <tss@iki.fi> parents: 6758 diff changeset	242 if (seq1 == seq2)
6040 fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	243 return remove_count;
6852 6ed01546f211 seq_range_array_remove_range(): Don't break if seq2 is -1U. Timo Sirainen <tss@iki.fi> parents: 6758 diff changeset	244 seq1++;
6040 fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	245
fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	246 if (seq_range_array_remove(array, seq2--))
fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	247 remove_count++;
6102 a7dca74c0978 seq_range_array_remove_range() sometimes didn't remove one sequence from the Timo Sirainen <tss@iki.fi> parents: 6040 diff changeset	248 if (seq1 > seq2)
6040 fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	249 return remove_count;
4932 f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	250
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	251 /* find the beginning */
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	252 data = array_get(array, &count);
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	253 (void)seq_range_lookup(array, seq1, &idx);
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	254
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	255 if (idx == count)
6040 fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	256 return remove_count;
4932 f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	257
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	258 i_assert(data[idx].seq1 >= seq1);
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	259 for (idx2 = idx; idx2 < count; idx2++) {
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	260 if (data[idx2].seq1 > seq2)
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	261 break;
6040 fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	262 remove_count += data[idx2].seq2 - data[idx2].seq1 + 1;
4932 f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	263 }
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	264 array_delete(array, idx, idx2-idx);
6040 fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed. Timo Sirainen <tss@iki.fi> parents: 6037 diff changeset	265 return remove_count;
4932 f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	266 }
f38f3f11a93f Added seq_range_array_remove_range() Timo Sirainen <tss@iki.fi> parents: 4687 diff changeset	267
6897 0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	268 unsigned int seq_range_array_remove_seq_range(ARRAY_TYPE(seq_range) *dest,
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	269 const ARRAY_TYPE(seq_range) *src)
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	270 {
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	271 unsigned int ret = 0;
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	272 const struct seq_range *src_range;
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	273 unsigned int i, count;
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	274
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	275 src_range = array_get(src, &count);
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	276 for (i = 0; i < count; i++) {
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	277 ret += seq_range_array_remove_range(dest, src_range[i].seq1,
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	278 src_range[i].seq2);
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	279 }
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	280 return ret;
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	281 }
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	282
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	283 unsigned int
7886 d12fc53f71be Renamed seq_range_array_remove_invert_range() to seq_range_array_intersect(). Timo Sirainen <tss@iki.fi> parents: 7668 diff changeset	284 seq_range_array_intersect(ARRAY_TYPE(seq_range) *dest,
d12fc53f71be Renamed seq_range_array_remove_invert_range() to seq_range_array_intersect(). Timo Sirainen <tss@iki.fi> parents: 7668 diff changeset	285 const ARRAY_TYPE(seq_range) *src)
6897 0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	286 {
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	287 const struct seq_range *src_range;
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	288 unsigned int i, count, ret = 0;
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	289 uint32_t last_seq = 0;
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	290
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	291 src_range = array_get(src, &count);
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	292 for (i = 0; i < count; i++) {
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	293 if (last_seq + 1 < src_range[i].seq1) {
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	294 ret += seq_range_array_remove_range(dest, last_seq + 1,
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	295 src_range[i].seq1 - 1);
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	296 }
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	297 last_seq = src_range[i].seq2;
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	298 }
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	299 if (last_seq != (uint32_t)-1) {
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	300 ret += seq_range_array_remove_range(dest, last_seq + 1,
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	301 (uint32_t)-1);
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	302 }
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	303 return ret;
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	304 }
0a3186f44dff Added seq_range_array_remove_seq_range() and Timo Sirainen <tss@iki.fi> parents: 6852 diff changeset	305
4687 c8b565e87966 seq_range_exists() can take a const pointer to the array. Timo Sirainen <tss@iki.fi> parents: 4596 diff changeset	306 bool seq_range_exists(const ARRAY_TYPE(seq_range) *array, uint32_t seq)
3716 821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	307 {
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	308 unsigned int idx;
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	309
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	310 return seq_range_lookup(array, seq, &idx);
821035fdc9f6 Moved seq_range_() functions to more generic ones in lib/. Timo Sirainen <tss@iki.fi>* parents: diff changeset	311 }
6758 3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	312
7905 3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	313 bool seq_range_array_have_common(const ARRAY_TYPE(seq_range) *array1,
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	314 const ARRAY_TYPE(seq_range) *array2)
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	315 {
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	316 const struct seq_range range1, range2;
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	317 unsigned int i1, i2, count1, count2;
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	318
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	319 range1 = array_get(array1, &count1);
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	320 range2 = array_get(array2, &count2);
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	321 for (i1 = i2 = 0; i1 < count1 && i2 < count2; ) {
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	322 if (range1[i1].seq1 <= range2[i2].seq2 &&
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	323 range1[i1].seq2 >= range2[i2].seq1)
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	324 return TRUE;
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	325
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	326 if (range1[i1].seq1 < range2[i2].seq1)
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	327 i1++;
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	328 else
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	329 i2++;
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	330 }
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	331 return FALSE;
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	332 }
3e8bcf4f6f5e Added seq_range_array_have_common(). Timo Sirainen <tss@iki.fi> parents: 7886 diff changeset	333
7668 bba1bb98d162 Added seq_range_count(). Timo Sirainen <tss@iki.fi> parents: 7646 diff changeset	334 unsigned int seq_range_count(const ARRAY_TYPE(seq_range) *array)
bba1bb98d162 Added seq_range_count(). Timo Sirainen <tss@iki.fi> parents: 7646 diff changeset	335 {
bba1bb98d162 Added seq_range_count(). Timo Sirainen <tss@iki.fi> parents: 7646 diff changeset	336 const struct seq_range *range;
bba1bb98d162 Added seq_range_count(). Timo Sirainen <tss@iki.fi> parents: 7646 diff changeset	337 unsigned int i, count, seq_count;
bba1bb98d162 Added seq_range_count(). Timo Sirainen <tss@iki.fi> parents: 7646 diff changeset	338
bba1bb98d162 Added seq_range_count(). Timo Sirainen <tss@iki.fi> parents: 7646 diff changeset	339 range = array_get(array, &count);
bba1bb98d162 Added seq_range_count(). Timo Sirainen <tss@iki.fi> parents: 7646 diff changeset	340 for (i = seq_count = 0; i < count; i++)
bba1bb98d162 Added seq_range_count(). Timo Sirainen <tss@iki.fi> parents: 7646 diff changeset	341 seq_count += range[i].seq2 - range[i].seq1 + 1;
bba1bb98d162 Added seq_range_count(). Timo Sirainen <tss@iki.fi> parents: 7646 diff changeset	342 return seq_count;
bba1bb98d162 Added seq_range_count(). Timo Sirainen <tss@iki.fi> parents: 7646 diff changeset	343 }
bba1bb98d162 Added seq_range_count(). Timo Sirainen <tss@iki.fi> parents: 7646 diff changeset	344
6758 3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	345 void seq_range_array_invert(ARRAY_TYPE(seq_range) *array,
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	346 uint32_t min_seq, uint32_t max_seq)
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	347 {
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	348 struct seq_range *range, value;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	349 unsigned int i, count;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	350 uint32_t next_min_seq;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	351
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	352 if (array_is_created(array))
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	353 range = array_get_modifiable(array, &count);
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	354 else {
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	355 range = NULL;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	356 count = 0;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	357 }
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	358 if (count == 0) {
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	359 /* empty -> full */
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	360 if (!array_is_created(array))
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	361 i_array_init(array, 4);
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	362 value.seq1 = min_seq;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	363 value.seq2 = max_seq;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	364 array_append(array, &value, 1);
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	365 return;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	366 }
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	367 i_assert(range[0].seq1 >= min_seq);
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	368 i_assert(range[count-1].seq2 <= max_seq);
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	369
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	370 if (range[0].seq1 == min_seq && range[0].seq2 == max_seq) {
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	371 /* full -> empty */
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	372 array_clear(array);
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	373 return;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	374 }
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	375
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	376 for (i = 0; i < count; ) {
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	377 next_min_seq = range[i].seq2 + 1;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	378 if (range[i].seq1 == min_seq) {
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	379 array_delete(array, i, 1);
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	380 range = array_get_modifiable(array, &count);
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	381 } else {
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	382 range[i].seq2 = range[i].seq1 - 1;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	383 range[i].seq1 = min_seq;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	384 i++;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	385 }
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	386 min_seq = next_min_seq;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	387 }
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	388 if (min_seq <= max_seq) {
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	389 value.seq1 = min_seq;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	390 value.seq2 = max_seq;
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	391 array_append(array, &value, 1);
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	392 }
3896c75bfaa8 Added seq_range_array_invert() Timo Sirainen <tss@iki.fi> parents: 6429 diff changeset	393 }
7628 af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	394
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	395 void seq_range_array_iter_init(struct seq_range_iter *iter_r,
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	396 const ARRAY_TYPE(seq_range) *array)
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	397 {
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	398 memset(iter_r, 0, sizeof(*iter_r));
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	399 iter_r->array = array;
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	400 }
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	401
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	402 bool seq_range_array_iter_nth(struct seq_range_iter *iter, unsigned int n,
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	403 uint32_t *seq_r)
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	404 {
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	405 const struct seq_range *range;
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	406 unsigned int i, count, diff;
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	407
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	408 if (n < iter->prev_n) {
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	409 /* iterating backwards, don't bother optimizing */
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	410 iter->prev_n = 0;
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	411 iter->prev_idx = 0;
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	412 }
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	413
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	414 range = array_get(iter->array, &count);
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	415 for (i = iter->prev_idx; i < count; i++) {
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	416 diff = range[i].seq2 - range[i].seq1;
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	417 if (n <= iter->prev_n + diff) {
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	418 i_assert(n >= iter->prev_n);
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	419 *seq_r = range[i].seq1 + (n - iter->prev_n);
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	420 iter->prev_idx = i;
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	421 return TRUE;
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	422 }
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	423 iter->prev_n += diff + 1;
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	424 }
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	425 iter->prev_idx = i;
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	426 return FALSE;
af2441dc6de6 Added seq_range_array_iter_nth() Timo Sirainen <tss@iki.fi> parents: 7308 diff changeset	427 }

Mercurial > dovecot > original-hg > dovecot-1.2

annotate src/lib/seq-range-array.c @ 9575:0a00dcc4f0ea HEAD