Mercurial > dovecot > original-hg > dovecot-1.2
annotate src/lib/seq-range-array.c @ 6102:a7dca74c0978 HEAD
seq_range_array_remove_range() sometimes didn't remove one sequence from the
middle.
author | Timo Sirainen <tss@iki.fi> |
---|---|
date | Thu, 19 Jul 2007 05:34:41 +0300 |
parents | fef4aad133dd |
children | 65c69a53a7be |
rev | line source |
---|---|
3716
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
1 /* Copyright (c) 2005 Timo Sirainen */ |
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 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
30 *idx_r = idx; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
31 return FALSE; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
32 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
33 |
4451
1a35d53c18fc
Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents:
4206
diff
changeset
|
34 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
|
35 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
|
36 { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
37 struct seq_range *data, value; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
38 unsigned int idx, count; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
39 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
40 value.seq1 = value.seq2 = seq; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
41 |
4451
1a35d53c18fc
Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents:
4206
diff
changeset
|
42 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
|
43 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
|
44 |
4451
1a35d53c18fc
Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents:
4206
diff
changeset
|
45 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
|
46 if (count == 0) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
47 array_append(array, &value, 1); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
48 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
49 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
50 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
51 /* quick checks */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
52 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
|
53 /* grow last range */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
54 data[count-1].seq2 = seq; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
55 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
56 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
57 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
|
58 array_append(array, &value, 1); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
59 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
60 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
61 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
|
62 /* grow down first range */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
63 data[0].seq1 = seq; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
64 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
65 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
66 if (data[0].seq1 > seq) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
67 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
|
68 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
69 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
70 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
71 /* 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
|
72 binary search */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
73 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
|
74 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
75 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
76 if (data[idx].seq2 < seq) |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
77 idx++; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
78 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
79 /* idx == count couldn't happen because we already handle it above */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
80 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
|
81 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
|
82 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
83 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
|
84 data[idx].seq1 = seq; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
85 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
|
86 /* merge */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
87 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
|
88 array_delete(array, idx, 1); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
89 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
90 } 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
|
91 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
|
92 data[idx].seq2 = seq; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
93 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
|
94 /* merge */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
95 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
|
96 array_delete(array, idx, 1); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
97 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
98 } else { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
99 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
|
100 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
101 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
102 |
6037
d911d943438e
Recent flag handling rewrite. Still not perfect with maildir.
Timo Sirainen <tss@iki.fi>
parents:
4932
diff
changeset
|
103 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
|
104 { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
105 struct seq_range *data, value; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
106 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
|
107 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
108 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
|
109 return FALSE; |
3716
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
110 |
4451
1a35d53c18fc
Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents:
4206
diff
changeset
|
111 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
|
112 if (count == 0) |
6037
d911d943438e
Recent flag handling rewrite. Still not perfect with maildir.
Timo Sirainen <tss@iki.fi>
parents:
4932
diff
changeset
|
113 return FALSE; |
3716
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
114 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
115 /* quick checks */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
116 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
|
117 /* outside the range */ |
6037
d911d943438e
Recent flag handling rewrite. Still not perfect with maildir.
Timo Sirainen <tss@iki.fi>
parents:
4932
diff
changeset
|
118 return FALSE; |
3716
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
119 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
120 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
|
121 /* 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
|
122 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
|
123 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
|
124 else |
d7e169797e3e
Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents:
3863
diff
changeset
|
125 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
|
126 return TRUE; |
3716
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
127 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
128 if (data[0].seq1 == seq) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
129 /* 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
|
130 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
|
131 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
|
132 else |
d7e169797e3e
Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents:
3863
diff
changeset
|
133 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
|
134 return TRUE; |
3716
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
135 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
136 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
137 /* 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
|
138 binary search */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
139 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
|
140 while (left_idx < right_idx) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
141 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
|
142 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
143 if (data[idx].seq1 > seq) |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
144 right_idx = idx; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
145 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
|
146 left_idx = idx+1; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
147 else { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
148 /* found it */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
149 if (data[idx].seq1 == seq) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
150 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
|
151 /* a single sequence range. |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
152 remove it entirely */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
153 array_delete(array, idx, 1); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
154 } else { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
155 /* shrink the range */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
156 data[idx].seq1++; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
157 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
158 } 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
|
159 /* shrink the range */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
160 data[idx].seq2--; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
161 } else { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
162 /* split the sequence range */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
163 value.seq1 = seq + 1; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
164 value.seq2 = data[idx].seq2; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
165 data[idx].seq2 = seq - 1; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
166 |
4206
ec7e56827ea8
Fix for seq_range_array_remove()
Timo Sirainen <tss@iki.fi>
parents:
4173
diff
changeset
|
167 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
|
168 } |
6037
d911d943438e
Recent flag handling rewrite. Still not perfect with maildir.
Timo Sirainen <tss@iki.fi>
parents:
4932
diff
changeset
|
169 return TRUE; |
3716
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
170 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
171 } |
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 |
6040
fef4aad133dd
seq_range_array_remove_range() returns now how many sequences were removed.
Timo Sirainen <tss@iki.fi>
parents:
6037
diff
changeset
|
175 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
|
176 uint32_t seq1, uint32_t seq2) |
4932
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
177 { |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
178 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
|
179 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
|
180 |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
181 /* 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
|
182 can simply be deleted with array_delete(). |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
183 |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
184 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
|
185 and handled the splitting ourself.. */ |
6040
fef4aad133dd
seq_range_array_remove_range() returns now how many sequences were removed.
Timo Sirainen <tss@iki.fi>
parents:
6037
diff
changeset
|
186 if (seq_range_array_remove(array, seq1++)) |
fef4aad133dd
seq_range_array_remove_range() returns now how many sequences were removed.
Timo Sirainen <tss@iki.fi>
parents:
6037
diff
changeset
|
187 remove_count++; |
4932
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
188 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
|
189 return remove_count; |
fef4aad133dd
seq_range_array_remove_range() returns now how many sequences were removed.
Timo Sirainen <tss@iki.fi>
parents:
6037
diff
changeset
|
190 |
fef4aad133dd
seq_range_array_remove_range() returns now how many sequences were removed.
Timo Sirainen <tss@iki.fi>
parents:
6037
diff
changeset
|
191 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
|
192 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
|
193 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
|
194 return remove_count; |
4932
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
195 |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
196 /* find the beginning */ |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
197 data = array_get(array, &count); |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
198 (void)seq_range_lookup(array, seq1, &idx); |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
199 if (idx < count && data[idx].seq2 < seq1) |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
200 idx++; |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
201 |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
202 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
|
203 return remove_count; |
4932
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
204 |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
205 i_assert(data[idx].seq1 >= seq1); |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
206 for (idx2 = idx; idx2 < count; idx2++) { |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
207 if (data[idx2].seq1 > seq2) |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
208 break; |
6040
fef4aad133dd
seq_range_array_remove_range() returns now how many sequences were removed.
Timo Sirainen <tss@iki.fi>
parents:
6037
diff
changeset
|
209 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
|
210 } |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
211 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
|
212 return remove_count; |
4932
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
213 } |
f38f3f11a93f
Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents:
4687
diff
changeset
|
214 |
4687
c8b565e87966
seq_range_exists() can take a const pointer to the array.
Timo Sirainen <tss@iki.fi>
parents:
4596
diff
changeset
|
215 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
|
216 { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
217 unsigned int idx; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
218 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
219 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
|
220 } |