Mercurial > dovecot > core-2.2

annotate src/lib/seq-range-array.c @ 22664:fea53c2725c0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
director: Fix director_max_parallel_moves/kicks type Should be uint, not time.
author Timo Sirainen <timo.sirainen@dovecot.fi>
date Thu, 09 Nov 2017 12:24:16 +0200
parents 2e2563132d5f
children cb108f786fb4
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
21390
2e2563132d5f Updated copyright notices to include the year 2017.
Stephan Bosch <stephan.bosch@dovecot.fi>
parents: 21389
diff changeset
1 /* Copyright (c) 2005-2017 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
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
7 static bool ATTR_NOWARN_UNUSED_RESULT
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
8 seq_range_lookup(const ARRAY_TYPE(seq_range) *array,
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
9 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
10 {
4687
c8b565e87966 seq_range_exists() can take a const pointer to the array.
Timo Sirainen <tss@iki.fi>
parents: 4596
diff changeset
11 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
12 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
13
4687
c8b565e87966 seq_range_exists() can take a const pointer to the array.
Timo Sirainen <tss@iki.fi>
parents: 4596
diff changeset
14 data = array_get(array, &count);
16361
38ca85ccd5af Added asserts to binary searches to make sure we don't go to infinite loop.
Timo Sirainen <tss@iki.fi>
parents: 15907
diff changeset
15 i_assert(count < INT_MAX);
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
16
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
17 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
18 while (left_idx < right_idx) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
19 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
20
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
21 if (data[idx].seq1 <= seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
22 if (data[idx].seq2 >= seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
23 /* 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
24 *idx_r = idx;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
25 return TRUE;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
26 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
27 left_idx = idx+1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
28 } else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
29 right_idx = idx;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
30 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
31 }
7308
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
32 if (left_idx > idx)
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
33 idx++;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
34 *idx_r = idx;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
35 return FALSE;
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
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
38 bool seq_range_array_add(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
39 {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
40 struct seq_range *data, value;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
41 unsigned int idx, count;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
42
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
43 value.seq1 = value.seq2 = seq;
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);
11172
4ee1d2312d83 seq_range_array_add() returns now TRUE if seq was already in array.
Timo Sirainen <tss@iki.fi>
parents: 11039
diff changeset
48 return FALSE;
3716
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) {
15907
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
53 if (data[count-1].seq2 == seq-1) {
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
54 /* grow last range */
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
55 data[count-1].seq2 = seq;
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
56 } else {
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
57 array_append(array, &value, 1);
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
58 }
11172
4ee1d2312d83 seq_range_array_add() returns now TRUE if seq was already in array.
Timo Sirainen <tss@iki.fi>
parents: 11039
diff changeset
59 return FALSE;
3716
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) {
15907
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
62 if (data[0].seq1-1 == seq) {
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
63 /* grow down first range */
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
64 data[0].seq1 = seq;
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
65 } else {
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
66 array_insert(array, 0, &value, 1);
db0ada89b81a seq_range_array_add(): Fixed handling sequence ranges that contain zeros.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
67 }
11172
4ee1d2312d83 seq_range_array_add() returns now TRUE if seq was already in array.
Timo Sirainen <tss@iki.fi>
parents: 11039
diff changeset
68 return FALSE;
3716
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))
11172
4ee1d2312d83 seq_range_array_add() returns now TRUE if seq was already in array.
Timo Sirainen <tss@iki.fi>
parents: 11039
diff changeset
74 return TRUE;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
75
7308
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
76 /* 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
77 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
78 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
79
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
80 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
81 data[idx].seq1 = seq;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
82 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
83 /* merge */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
84 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
85 array_delete(array, idx, 1);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
86 }
14527
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
87 } else {
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
88 if (idx > 0 && data[idx-1].seq2 == seq-1)
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
89 idx--;
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
90 if (data[idx].seq2 == seq-1) {
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
91 i_assert(idx+1 < count); /* already handled above */
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
92 data[idx].seq2 = seq;
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
93 if (data[idx+1].seq1 == seq+1) {
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
94 /* merge */
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
95 data[idx+1].seq1 = data[idx].seq1;
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
96 array_delete(array, idx, 1);
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
97 }
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
98 } else {
bac5e1dae4ed seq_range_array_add(): Ranges weren't always merged when they could have.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
99 array_insert(array, idx, &value, 1);
3716
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 }
11172
4ee1d2312d83 seq_range_array_add() returns now TRUE if seq was already in array.
Timo Sirainen <tss@iki.fi>
parents: 11039
diff changeset
102 return FALSE;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
103 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
104
14676
69ba6977bed8 seq_range_array_add() API changed. Added other functions to provide the less common use cases.
Timo Sirainen <tss@iki.fi>
parents: 14527
diff changeset
105 void seq_range_array_add_with_init(ARRAY_TYPE(seq_range) *array,
69ba6977bed8 seq_range_array_add() API changed. Added other functions to provide the less common use cases.
Timo Sirainen <tss@iki.fi>
parents: 14527
diff changeset
106 unsigned int init_count, uint32_t seq)
69ba6977bed8 seq_range_array_add() API changed. Added other functions to provide the less common use cases.
Timo Sirainen <tss@iki.fi>
parents: 14527
diff changeset
107 {
69ba6977bed8 seq_range_array_add() API changed. Added other functions to provide the less common use cases.
Timo Sirainen <tss@iki.fi>
parents: 14527
diff changeset
108 if (!array_is_created(array))
69ba6977bed8 seq_range_array_add() API changed. Added other functions to provide the less common use cases.
Timo Sirainen <tss@iki.fi>
parents: 14527
diff changeset
109 i_array_init(array, init_count);
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
110 seq_range_array_add(array, seq);
14676
69ba6977bed8 seq_range_array_add() API changed. Added other functions to provide the less common use cases.
Timo Sirainen <tss@iki.fi>
parents: 14527
diff changeset
111 }
69ba6977bed8 seq_range_array_add() API changed. Added other functions to provide the less common use cases.
Timo Sirainen <tss@iki.fi>
parents: 14527
diff changeset
112
18190
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
113 static void
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
114 seq_range_array_add_range_internal(ARRAY_TYPE(seq_range) *array,
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
115 uint32_t seq1, uint32_t seq2,
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
116 unsigned int *r_count)
7127
010485455f75 Added unoptimized seq_range_array_add_range()
Timo Sirainen <tss@iki.fi>
parents: 7086
diff changeset
117 {
7308
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
118 struct seq_range *data, value;
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
119 unsigned int idx1, idx2, count;
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
120
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
121 seq_range_lookup(array, seq1, &idx1);
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
122 seq_range_lookup(array, seq2, &idx2);
7308
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
123
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
124 data = array_get_modifiable(array, &count);
18190
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
125 if (r_count != NULL) {
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
126 /* Find number we're adding by counting the number we're
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
127 not adding, and subtracting that from the nominal range. */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
128 unsigned int added = seq2+1 - seq1;
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
129 unsigned int countidx2 = idx2;
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
130 unsigned int overcounted = 0u, notadded = 0u;
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
131 unsigned int i;
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
132
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
133 if (idx1 == count) {
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
134 /* not in a range as too far right */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
135 } else if (seq1 < data[idx1].seq1) {
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
136 /* not in a range, to the left of a real range */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
137 } else {
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
138 /* count the whole of this range, which is an overcount */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
139 overcounted += seq1 - data[idx1].seq1;
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
140 /* fencepost check: equality means the whole range is valid,
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
141 therefore there's no overcounting. Result = 0 overcount */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
142 }
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
143 if (idx2 == count) {
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
144 /* not in a range as too far right */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
145 } else if (seq2 < data[idx2].seq1) {
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
146 /* not in a range, to the left of a real range */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
147 } else {
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
148 /* count the whole of this range, which is an overcount */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
149 overcounted += data[idx2].seq2 - seq2;
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
150 countidx2++; /* may become == count i.e. past the end */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
151 /* fencepost check: equality means the whole range is valid,
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
152 therefore there's no overcounting. Result = 0 overcount. */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
153 }
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
154 /* Now count how many we're not adding */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
155 for (i = idx1; i < countidx2; i++)
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
156 notadded += data[i].seq2+1 - data[i].seq1;
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
157 /* Maybe the not added tally included some over-counting too */
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
158 added -= (notadded - overcounted);
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
159 *r_count = added;
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
160 }
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
161
7308
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
162 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
163 idx1--;
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
164
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
165 if (idx1 == idx2 &&
21259
5c75425daf63 lib: seq_range_array_*(): Fix seq2=2^32-1 handling
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 19552
diff changeset
166 (idx2 == count || (seq2 < (uint32_t)-1 && data[idx2].seq1 > seq2+1)) &&
7308
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
167 (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
168 /* no overlapping */
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
169 value.seq1 = seq1;
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
170 value.seq2 = seq2;
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
171 array_insert(array, idx1, &value, 1);
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
172 } else {
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
173 i_assert(idx1 < count);
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
174 if (seq1 < data[idx1].seq1)
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
175 data[idx1].seq1 = seq1;
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
176 if (seq2 > data[idx1].seq2) {
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
177 /* merge */
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
178 if (idx2 == count ||
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
179 data[idx2].seq1 > seq2+1)
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
180 idx2--;
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
181 if (seq2 >= data[idx2].seq2) {
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
182 data[idx1].seq2 = seq2;
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
183 } else {
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
184 data[idx1].seq2 = data[idx2].seq2;
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
185 }
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
186 array_delete(array, idx1 + 1, idx2 - idx1);
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
187 }
e318f3c8a724 Implemented optimized seq_range_array_add_range().
Timo Sirainen <tss@iki.fi>
parents: 7127
diff changeset
188 }
7127
010485455f75 Added unoptimized seq_range_array_add_range()
Timo Sirainen <tss@iki.fi>
parents: 7086
diff changeset
189 }
010485455f75 Added unoptimized seq_range_array_add_range()
Timo Sirainen <tss@iki.fi>
parents: 7086
diff changeset
190
18190
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
191 void seq_range_array_add_range(ARRAY_TYPE(seq_range) *array,
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
192 uint32_t seq1, uint32_t seq2)
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
193 {
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
194 seq_range_array_add_range_internal(array, seq1, seq2, NULL);
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
195 }
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
196 unsigned int seq_range_array_add_range_count(ARRAY_TYPE(seq_range) *array,
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
197 uint32_t seq1, uint32_t seq2)
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
198 {
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
199 unsigned int count;
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
200 seq_range_array_add_range_internal(array, seq1, seq2, &count);
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
201 return count;
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
202 }
230f3579c9b7 lib: seq-range-array - add range changes
Phil Carmody <phil@dovecot.fi>
parents: 18137
diff changeset
203
7646
f0dc2a3dee54 Added seq_range_array_merge()
Timo Sirainen <tss@iki.fi>
parents: 7628
diff changeset
204 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
205 const ARRAY_TYPE(seq_range) *src)
f0dc2a3dee54 Added seq_range_array_merge()
Timo Sirainen <tss@iki.fi>
parents: 7628
diff changeset
206 {
f0dc2a3dee54 Added seq_range_array_merge()
Timo Sirainen <tss@iki.fi>
parents: 7628
diff changeset
207 const struct seq_range *range;
f0dc2a3dee54 Added seq_range_array_merge()
Timo Sirainen <tss@iki.fi>
parents: 7628
diff changeset
208
f0dc2a3dee54 Added seq_range_array_merge()
Timo Sirainen <tss@iki.fi>
parents: 7628
diff changeset
209 if (array_count(dest) == 0) {
f0dc2a3dee54 Added seq_range_array_merge()
Timo Sirainen <tss@iki.fi>
parents: 7628
diff changeset
210 array_append_array(dest, src);
f0dc2a3dee54 Added seq_range_array_merge()
Timo Sirainen <tss@iki.fi>
parents: 7628
diff changeset
211 return;
f0dc2a3dee54 Added seq_range_array_merge()
Timo Sirainen <tss@iki.fi>
parents: 7628
diff changeset
212 }
f0dc2a3dee54 Added seq_range_array_merge()
Timo Sirainen <tss@iki.fi>
parents: 7628
diff changeset
213
10000
c610321584ca Use array_foreach*() in some useful places.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
214 array_foreach(src, range)
c610321584ca Use array_foreach*() in some useful places.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
215 seq_range_array_add_range(dest, range->seq1, range->seq2);
7646
f0dc2a3dee54 Added seq_range_array_merge()
Timo Sirainen <tss@iki.fi>
parents: 7628
diff changeset
216 }
f0dc2a3dee54 Added seq_range_array_merge()
Timo Sirainen <tss@iki.fi>
parents: 7628
diff changeset
217
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
218 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
219 {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
220 struct seq_range *data, value;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
221 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
222
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
223 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
224 return FALSE;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
225
4451
1a35d53c18fc Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents: 4206
diff changeset
226 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
227 if (count == 0)
6037
d911d943438e Recent flag handling rewrite. Still not perfect with maildir.
Timo Sirainen <tss@iki.fi>
parents: 4932
diff changeset
228 return FALSE;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
229
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
230 /* quick checks */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
231 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
232 /* outside the range */
6037
d911d943438e Recent flag handling rewrite. Still not perfect with maildir.
Timo Sirainen <tss@iki.fi>
parents: 4932
diff changeset
233 return FALSE;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
234 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
235 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
236 /* 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
237 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
238 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
239 else
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
240 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
241 return TRUE;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
242 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
243 if (data[0].seq1 == seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
244 /* 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
245 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
246 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
247 else
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
248 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
249 return TRUE;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
250 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
251
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
252 /* 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
253 binary search */
16361
38ca85ccd5af Added asserts to binary searches to make sure we don't go to infinite loop.
Timo Sirainen <tss@iki.fi>
parents: 15907
diff changeset
254 i_assert(count < INT_MAX);
11039
0f98525e4567 Removed dead code.
Timo Sirainen <tss@iki.fi>
parents: 10582
diff changeset
255 left_idx = 0; right_idx = count;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
256 while (left_idx < right_idx) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
257 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
258
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
259 if (data[idx].seq1 > seq)
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
260 right_idx = idx;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
261 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
262 left_idx = idx+1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
263 else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
264 /* found it */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
265 if (data[idx].seq1 == seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
266 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
267 /* a single sequence range.
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
268 remove it entirely */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
269 array_delete(array, idx, 1);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
270 } else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
271 /* shrink the range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
272 data[idx].seq1++;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
273 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
274 } 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
275 /* shrink the range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
276 data[idx].seq2--;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
277 } else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
278 /* split the sequence range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
279 value.seq1 = seq + 1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
280 value.seq2 = data[idx].seq2;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
281 data[idx].seq2 = seq - 1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
282
4206
ec7e56827ea8 Fix for seq_range_array_remove()
Timo Sirainen <tss@iki.fi>
parents: 4173
diff changeset
283 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
284 }
6037
d911d943438e Recent flag handling rewrite. Still not perfect with maildir.
Timo Sirainen <tss@iki.fi>
parents: 4932
diff changeset
285 return TRUE;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
286 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
287 }
6037
d911d943438e Recent flag handling rewrite. Still not perfect with maildir.
Timo Sirainen <tss@iki.fi>
parents: 4932
diff changeset
288 return FALSE;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
289 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
290
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
291 unsigned int seq_range_array_remove_range(ARRAY_TYPE(seq_range) *array,
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
292 uint32_t seq1, uint32_t seq2)
4932
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
293 {
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
294 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
295 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
296
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
297 /* 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
298 can simply be deleted with array_delete().
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
299
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
300 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
301 and handled the splitting ourself.. */
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
302 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
303 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
304 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
305 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
306 seq1++;
6040
fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed.
Timo Sirainen <tss@iki.fi>
parents: 6037
diff changeset
307
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
308 if (seq_range_array_remove(array, seq2--))
6040
fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed.
Timo Sirainen <tss@iki.fi>
parents: 6037
diff changeset
309 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
310 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
311 return remove_count;
4932
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
312
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
313 /* find the beginning */
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
314 data = array_get(array, &count);
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
315 seq_range_lookup(array, seq1, &idx);
4932
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
316
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
317 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
318 return remove_count;
4932
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
319
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
320 i_assert(data[idx].seq1 >= seq1);
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
321 for (idx2 = idx; idx2 < count; idx2++) {
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
322 if (data[idx2].seq1 > seq2)
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
323 break;
6040
fef4aad133dd seq_range_array_remove_range() returns now how many sequences were removed.
Timo Sirainen <tss@iki.fi>
parents: 6037
diff changeset
324 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
325 }
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
326 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
327 return remove_count;
4932
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
328 }
f38f3f11a93f Added seq_range_array_remove_range()
Timo Sirainen <tss@iki.fi>
parents: 4687
diff changeset
329
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
330 unsigned int seq_range_array_remove_seq_range(ARRAY_TYPE(seq_range) *dest,
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
331 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
332 {
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
333 unsigned int ret = 0;
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
334 const struct seq_range *src_range;
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
335
10000
c610321584ca Use array_foreach*() in some useful places.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
336 array_foreach(src, src_range) {
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
337 ret += seq_range_array_remove_range(dest, src_range->seq1,
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
338 src_range->seq2);
6897
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
339 }
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
340 return ret;
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
341 }
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
342
17312
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
343 void seq_range_array_remove_nth(ARRAY_TYPE(seq_range) *array,
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
344 uint32_t n, uint32_t count)
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
345 {
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
346 struct seq_range_iter iter;
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
347 uint32_t seq1, seq2;
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
348
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
349 if (count == 0)
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
350 return;
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
351
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
352 seq_range_array_iter_init(&iter, array);
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
353 if (!seq_range_array_iter_nth(&iter, n, &seq1)) {
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
354 /* n points beyond array */
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
355 return;
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
356 }
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
357 if (count-1 >= (uint32_t)-1 - n ||
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
358 !seq_range_array_iter_nth(&iter, n + (count-1), &seq2)) {
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
359 /* count points beyond array */
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
360 seq2 = (uint32_t)-1;
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
361 }
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
362 seq_range_array_remove_range(array, seq1, seq2);
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
363 }
0d237a4dacd2 Added seq_range_array_remove_nth()
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
364
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
365 unsigned int seq_range_array_intersect(ARRAY_TYPE(seq_range) *dest,
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
366 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
367 {
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
368 const struct seq_range *src_range;
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
369 unsigned int i, count, ret = 0;
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
370 uint32_t last_seq = 0;
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
371
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
372 src_range = array_get(src, &count);
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
373 for (i = 0; i < count; i++) {
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
374 if (last_seq + 1 < src_range[i].seq1) {
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
375 ret += seq_range_array_remove_range(dest,
14682
d0d7b810646b Make sure we check all the functions' return values. Minor API changes to simplify this.
Timo Sirainen <tss@iki.fi>
parents: 14677
diff changeset
376 last_seq + 1, src_range[i].seq1 - 1);
6897
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
377 }
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
378 last_seq = src_range[i].seq2;
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
379 }
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
380 if (last_seq != (uint32_t)-1) {
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
381 ret += seq_range_array_remove_range(dest, last_seq + 1,
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
382 (uint32_t)-1);
6897
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
383 }
14685
67b9119fbd09 seq-range-array: Reverted most of recent API changes.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
384 return ret;
6897
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
385 }
0a3186f44dff Added seq_range_array_remove_seq_range() and
Timo Sirainen <tss@iki.fi>
parents: 6852
diff changeset
386
4687
c8b565e87966 seq_range_exists() can take a const pointer to the array.
Timo Sirainen <tss@iki.fi>
parents: 4596
diff changeset
387 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
388 {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
389 unsigned int idx;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
390
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
391 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
392 }
6758
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
393
7905
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
394 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
395 const ARRAY_TYPE(seq_range) *array2)
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
396 {
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
397 const struct seq_range *range1, *range2;
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
398 unsigned int i1, i2, count1, count2;
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
399
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
400 range1 = array_get(array1, &count1);
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
401 range2 = array_get(array2, &count2);
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
402 for (i1 = i2 = 0; i1 < count1 && i2 < count2; ) {
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
403 if (range1[i1].seq1 <= range2[i2].seq2 &&
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
404 range1[i1].seq2 >= range2[i2].seq1)
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
405 return TRUE;
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
406
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
407 if (range1[i1].seq1 < range2[i2].seq1)
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
408 i1++;
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
409 else
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
410 i2++;
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
411 }
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
412 return FALSE;
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
413 }
3e8bcf4f6f5e Added seq_range_array_have_common().
Timo Sirainen <tss@iki.fi>
parents: 7886
diff changeset
414
7668
bba1bb98d162 Added seq_range_count().
Timo Sirainen <tss@iki.fi>
parents: 7646
diff changeset
415 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
416 {
bba1bb98d162 Added seq_range_count().
Timo Sirainen <tss@iki.fi>
parents: 7646
diff changeset
417 const struct seq_range *range;
10000
c610321584ca Use array_foreach*() in some useful places.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
418 unsigned int seq_count = 0;
7668
bba1bb98d162 Added seq_range_count().
Timo Sirainen <tss@iki.fi>
parents: 7646
diff changeset
419
10000
c610321584ca Use array_foreach*() in some useful places.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
420 array_foreach(array, range)
c610321584ca Use array_foreach*() in some useful places.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
421 seq_count += range->seq2 - range->seq1 + 1;
7668
bba1bb98d162 Added seq_range_count().
Timo Sirainen <tss@iki.fi>
parents: 7646
diff changeset
422 return seq_count;
bba1bb98d162 Added seq_range_count().
Timo Sirainen <tss@iki.fi>
parents: 7646
diff changeset
423 }
bba1bb98d162 Added seq_range_count().
Timo Sirainen <tss@iki.fi>
parents: 7646
diff changeset
424
6758
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
425 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
426 uint32_t min_seq, uint32_t max_seq)
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
427 {
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
428 struct seq_range *range, value;
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
429 unsigned int i, count;
21273
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
430 uint32_t prev_min_seq;
6758
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
431
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
432 if (array_is_created(array))
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
433 range = array_get_modifiable(array, &count);
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
434 else {
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
435 range = NULL;
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
436 count = 0;
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
437 }
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
438 if (count == 0) {
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
439 /* empty -> full */
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
440 if (!array_is_created(array))
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
441 i_array_init(array, 4);
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
442 value.seq1 = min_seq;
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
443 value.seq2 = max_seq;
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
444 array_append(array, &value, 1);
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
445 return;
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
446 }
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
447 i_assert(range[0].seq1 >= min_seq);
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
448 i_assert(range[count-1].seq2 <= max_seq);
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
449
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
450 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
451 /* full -> empty */
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
452 array_clear(array);
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
453 return;
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
454 }
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
455
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
456 for (i = 0; i < count; ) {
21273
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
457 prev_min_seq = min_seq;
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
458 min_seq = range[i].seq2;
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
459 if (range[i].seq1 == prev_min_seq) {
6758
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
460 array_delete(array, i, 1);
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
461 range = array_get_modifiable(array, &count);
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
462 } else {
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
463 range[i].seq2 = range[i].seq1 - 1;
21273
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
464 range[i].seq1 = prev_min_seq;
6758
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
465 i++;
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
466 }
21273
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
467 if (min_seq >= max_seq) {
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
468 /* max_seq is reached. the rest of the array should be
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
469 empty. we'll return here, because min_seq++ may
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
470 wrap to 0. */
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
471 i_assert(min_seq == max_seq);
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
472 i_assert(i == count);
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
473 return;
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
474 }
ff92e16346c9 lib: Fix seq_range_array_invert() when input contains 2^32-1
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21259
diff changeset
475 min_seq++;
6758
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
476 }
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
477 if (min_seq <= max_seq) {
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
478 value.seq1 = min_seq;
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
479 value.seq2 = max_seq;
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
480 array_append(array, &value, 1);
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
481 }
3896c75bfaa8 Added seq_range_array_invert()
Timo Sirainen <tss@iki.fi>
parents: 6429
diff changeset
482 }
7628
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
483
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
484 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
485 const ARRAY_TYPE(seq_range) *array)
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
486 {
21389
59437f8764c6 global: Replaced all instances of memset(p, 0, sizeof(*p)) with the new i_zero() macro.
Stephan Bosch <stephan.bosch@dovecot.fi>
parents: 21273
diff changeset
487 i_zero(iter_r);
7628
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
488 iter_r->array = array;
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
489 }
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
490
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
491 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
492 uint32_t *seq_r)
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
493 {
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
494 const struct seq_range *range;
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
495 unsigned int i, count, diff;
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
496
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
497 if (n < iter->prev_n) {
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
498 /* iterating backwards, don't bother optimizing */
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
499 iter->prev_n = 0;
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
500 iter->prev_idx = 0;
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
501 }
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
502
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
503 range = array_get(iter->array, &count);
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
504 for (i = iter->prev_idx; i < count; i++) {
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
505 diff = range[i].seq2 - range[i].seq1;
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
506 if (n <= iter->prev_n + diff) {
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
507 i_assert(n >= iter->prev_n);
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
508 *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
509 iter->prev_idx = i;
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
510 return TRUE;
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
511 }
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
512 iter->prev_n += diff + 1;
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
513 }
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
514 iter->prev_idx = i;
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
515 return FALSE;
af2441dc6de6 Added seq_range_array_iter_nth()
Timo Sirainen <tss@iki.fi>
parents: 7308
diff changeset
516 }