Mercurial > dovecot > original-hg > dovecot-1.2
annotate src/lib/seq-range-array.c @ 4112:d7e169797e3e HEAD
Removal didn't work properly from beginning/end if the range contained only
a single sequence.
author | Timo Sirainen <tss@iki.fi> |
---|---|
date | Sat, 01 Apr 2006 00:19:05 +0300 |
parents | 55df57c028d4 |
children | 1ba7983b814c |
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 |
3863
55df57c028d4
Added "bool" type and changed all ints that were used as booleans to bool.
Timo Sirainen <tss@iki.fi>
parents:
3716
diff
changeset
|
7 static bool seq_range_lookup(array_t *array, 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
|
8 { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
9 ARRAY_SET_TYPE(array, struct seq_range); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
10 struct seq_range *data; |
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 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
13 data = array_get_modifyable(array, &count); |
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 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
34 void seq_range_array_add(array_t *array, unsigned int init_count, uint32_t seq) |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
35 { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
36 ARRAY_SET_TYPE(array, struct seq_range); |
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 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
42 if (!array_is_created(array)) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
43 array_create(array, default_pool, |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
44 sizeof(struct seq_range), init_count); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
45 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
46 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
47 data = array_get_modifyable(array, &count); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
48 if (count == 0) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
49 array_append(array, &value, 1); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
50 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
51 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
52 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
53 /* quick checks */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
54 if (data[count-1].seq2 == seq-1) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
55 /* grow last range */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
56 data[count-1].seq2 = seq; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
57 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
58 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
59 if (data[count-1].seq2 < seq) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
60 array_append(array, &value, 1); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
61 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
62 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
63 if (data[0].seq1 == seq+1) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
64 /* grow down first range */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
65 data[0].seq1 = seq; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
66 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
67 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
68 if (data[0].seq1 > seq) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
69 array_insert(array, 0, &value, 1); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
70 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
71 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
72 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
73 /* somewhere in the middle, array is sorted so find it with |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
74 binary search */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
75 if (seq_range_lookup(array, seq, &idx)) |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
76 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
77 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
78 if (data[idx].seq2 < seq) |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
79 idx++; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
80 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
81 /* 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
|
82 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
|
83 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
|
84 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
85 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
|
86 data[idx].seq1 = seq; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
87 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
|
88 /* merge */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
89 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
|
90 array_delete(array, idx, 1); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
91 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
92 } 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
|
93 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
|
94 data[idx].seq2 = seq; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
95 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
|
96 /* merge */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
97 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
|
98 array_delete(array, idx, 1); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
99 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
100 } else { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
101 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
|
102 } |
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 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
105 void seq_range_array_remove(array_t *array, uint32_t seq) |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
106 { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
107 ARRAY_SET_TYPE(array, struct seq_range); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
108 struct seq_range *data, value; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
109 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
|
110 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
111 if (!array_is_created(array)) |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
112 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
113 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
114 data = array_get_modifyable(array, &count); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
115 i_assert(count > 0); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
116 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
117 /* quick checks */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
118 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
|
119 /* outside the range */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
120 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
121 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
122 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
|
123 /* 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
|
124 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
|
125 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
|
126 else |
d7e169797e3e
Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents:
3863
diff
changeset
|
127 array_delete(array, count-1, 1); |
3716
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
128 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
129 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
130 if (data[0].seq1 == seq) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
131 /* 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
|
132 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
|
133 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
|
134 else |
d7e169797e3e
Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents:
3863
diff
changeset
|
135 array_delete(array, 0, 1); |
3716
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
136 return; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
137 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
138 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
139 /* 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
|
140 binary search */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
141 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
|
142 while (left_idx < right_idx) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
143 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
|
144 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
145 if (data[idx].seq1 > seq) |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
146 right_idx = idx; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
147 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
|
148 left_idx = idx+1; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
149 else { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
150 /* found it */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
151 if (data[idx].seq1 == seq) { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
152 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
|
153 /* a single sequence range. |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
154 remove it entirely */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
155 array_delete(array, idx, 1); |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
156 } else { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
157 /* shrink the range */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
158 data[idx].seq1++; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
159 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
160 } 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
|
161 /* shrink the range */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
162 data[idx].seq2--; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
163 } else { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
164 /* split the sequence range */ |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
165 value.seq1 = seq + 1; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
166 value.seq2 = data[idx].seq2; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
167 data[idx].seq2 = seq - 1; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
168 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
169 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
|
170 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
171 break; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
172 } |
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 } |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
175 |
3863
55df57c028d4
Added "bool" type and changed all ints that were used as booleans to bool.
Timo Sirainen <tss@iki.fi>
parents:
3716
diff
changeset
|
176 bool seq_range_exists(array_t *array, uint32_t seq) |
3716
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
177 { |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
178 unsigned int idx; |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
179 |
821035fdc9f6
Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff
changeset
|
180 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
|
181 } |