Mercurial > dovecot > original-hg > dovecot-1.2

annotate src/lib/seq-range-array.c @ 4891:6ab2712f1a93 HEAD

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Only imap binary was actually working.
author Timo Sirainen <tss@iki.fi>
date Sun, 10 Dec 2006 14:35:02 +0200
parents c8b565e87966
children f38f3f11a93f
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
1 /* Copyright (c) 2005 Timo Sirainen */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
2
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
3 #include "lib.h"
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
4 #include "array.h"
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
5 #include "seq-range-array.h"
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
6
4687
c8b565e87966 seq_range_exists() can take a const pointer to the array.
Timo Sirainen <tss@iki.fi>
parents: 4596
diff changeset
7 static bool seq_range_lookup(const ARRAY_TYPE(seq_range) *array,
4451
1a35d53c18fc Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents: 4206
diff changeset
8 uint32_t seq, unsigned int *idx_r)
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
9 {
4687
c8b565e87966 seq_range_exists() can take a const pointer to the array.
Timo Sirainen <tss@iki.fi>
parents: 4596
diff changeset
10 const struct seq_range *data;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
11 unsigned int idx, left_idx, right_idx, count;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
12
4687
c8b565e87966 seq_range_exists() can take a const pointer to the array.
Timo Sirainen <tss@iki.fi>
parents: 4596
diff changeset
13 data = array_get(array, &count);
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
14
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
15 idx = 0; left_idx = 0; right_idx = count;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
16 while (left_idx < right_idx) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
17 idx = (left_idx + right_idx) / 2;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
18
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
19 if (data[idx].seq1 <= seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
20 if (data[idx].seq2 >= seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
21 /* it's already in the range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
22 *idx_r = idx;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
23 return TRUE;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
24 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
25 left_idx = idx+1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
26 } else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
27 right_idx = idx;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
28 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
29 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
30 *idx_r = idx;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
31 return FALSE;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
32 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
33
4451
1a35d53c18fc Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents: 4206
diff changeset
34 void seq_range_array_add(ARRAY_TYPE(seq_range) *array,
1a35d53c18fc Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents: 4206
diff changeset
35 unsigned int init_count, uint32_t seq)
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
36 {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
37 struct seq_range *data, value;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
38 unsigned int idx, count;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
39
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
40 value.seq1 = value.seq2 = seq;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
41
4451
1a35d53c18fc Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents: 4206
diff changeset
42 if (!array_is_created(array))
4596
bf4e98a0de3f Replaced ARRAY_CREATE() macro with [ipt]_array_init() macros. The macro
Timo Sirainen <tss@iki.fi>
parents: 4594
diff changeset
43 i_array_init(array, init_count);
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
44
4451
1a35d53c18fc Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents: 4206
diff changeset
45 data = array_get_modifiable(array, &count);
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
46 if (count == 0) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
47 array_append(array, &value, 1);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
48 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
49 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
50
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
51 /* quick checks */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
52 if (data[count-1].seq2 == seq-1) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
53 /* grow last range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
54 data[count-1].seq2 = seq;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
55 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
56 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
57 if (data[count-1].seq2 < seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
58 array_append(array, &value, 1);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
59 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
60 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
61 if (data[0].seq1 == seq+1) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
62 /* grow down first range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
63 data[0].seq1 = seq;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
64 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
65 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
66 if (data[0].seq1 > seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
67 array_insert(array, 0, &value, 1);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
68 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
69 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
70
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
71 /* somewhere in the middle, array is sorted so find it with
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
72 binary search */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
73 if (seq_range_lookup(array, seq, &idx))
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
74 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
75
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
76 if (data[idx].seq2 < seq)
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
77 idx++;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
78
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
79 /* idx == count couldn't happen because we already handle it above */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
80 i_assert(idx < count && data[idx].seq1 >= seq);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
81 i_assert(data[idx].seq1 > seq || data[idx].seq2 < seq);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
82
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
83 if (data[idx].seq1 == seq+1) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
84 data[idx].seq1 = seq;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
85 if (idx > 0 && data[idx-1].seq2 == seq-1) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
86 /* merge */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
87 data[idx-1].seq2 = data[idx].seq2;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
88 array_delete(array, idx, 1);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
89 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
90 } else if (data[idx].seq2 == seq-1) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
91 i_assert(idx+1 < count); /* already handled above */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
92 data[idx].seq2 = seq;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
93 if (data[idx+1].seq1 == seq+1) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
94 /* merge */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
95 data[idx+1].seq1 = data[idx].seq1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
96 array_delete(array, idx, 1);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
97 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
98 } else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
99 array_insert(array, idx, &value, 1);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
100 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
101 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
102
4451
1a35d53c18fc Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents: 4206
diff changeset
103 void seq_range_array_remove(ARRAY_TYPE(seq_range) *array, uint32_t seq)
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
104 {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
105 struct seq_range *data, value;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
106 unsigned int idx, left_idx, right_idx, count;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
107
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
108 if (!array_is_created(array))
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
109 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
110
4451
1a35d53c18fc Array API redesigned to work using unions. It now provides type safety
Timo Sirainen <tss@iki.fi>
parents: 4206
diff changeset
111 data = array_get_modifiable(array, &count);
4173
1ba7983b814c seq_range_array_remove(): Don't crash if array is empty.
Timo Sirainen <tss@iki.fi>
parents: 4112
diff changeset
112 if (count == 0)
1ba7983b814c seq_range_array_remove(): Don't crash if array is empty.
Timo Sirainen <tss@iki.fi>
parents: 4112
diff changeset
113 return;
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
114
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
115 /* quick checks */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
116 if (seq > data[count-1].seq2 || seq < data[0].seq1) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
117 /* outside the range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
118 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
119 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
120 if (data[count-1].seq2 == seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
121 /* shrink last range */
4112
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
122 if (data[count-1].seq1 != data[count-1].seq2)
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
123 data[count-1].seq2--;
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
124 else
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
125 array_delete(array, count-1, 1);
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
126 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
127 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
128 if (data[0].seq1 == seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
129 /* shrink up first range */
4112
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
130 if (data[0].seq1 != data[0].seq2)
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
131 data[0].seq1++;
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
132 else
d7e169797e3e Removal didn't work properly from beginning/end if the range contained only
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
133 array_delete(array, 0, 1);
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
134 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
135 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
136
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
137 /* somewhere in the middle, array is sorted so find it with
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
138 binary search */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
139 idx = 0; left_idx = 0; right_idx = count;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
140 while (left_idx < right_idx) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
141 idx = (left_idx + right_idx) / 2;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
142
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
143 if (data[idx].seq1 > seq)
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
144 right_idx = idx;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
145 else if (data[idx].seq2 < seq)
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
146 left_idx = idx+1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
147 else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
148 /* found it */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
149 if (data[idx].seq1 == seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
150 if (data[idx].seq1 == data[idx].seq2) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
151 /* a single sequence range.
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
152 remove it entirely */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
153 array_delete(array, idx, 1);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
154 } else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
155 /* shrink the range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
156 data[idx].seq1++;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
157 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
158 } else if (data[idx].seq2 == seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
159 /* shrink the range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
160 data[idx].seq2--;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
161 } else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
162 /* split the sequence range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
163 value.seq1 = seq + 1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
164 value.seq2 = data[idx].seq2;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
165 data[idx].seq2 = seq - 1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
166
4206
ec7e56827ea8 Fix for seq_range_array_remove()
Timo Sirainen <tss@iki.fi>
parents: 4173
diff changeset
167 array_insert(array, idx + 1, &value, 1);
3716
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
168 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
169 break;
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 }
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
4687
c8b565e87966 seq_range_exists() can take a const pointer to the array.
Timo Sirainen <tss@iki.fi>
parents: 4596
diff changeset
174 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
175 {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
176 unsigned int idx;
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 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
179 }