Mercurial > dovecot > original-hg > dovecot-1.2

annotate src/lib/seq-range-array.c @ 3716:821035fdc9f6 HEAD

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Moved seq_range_*() functions to more generic ones in lib/.
author Timo Sirainen <tss@iki.fi>
date Fri, 25 Nov 2005 17:16:46 +0200
parents
children 55df57c028d4
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
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
7 static int seq_range_lookup(array_t *array, uint32_t seq, unsigned int *idx_r)
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 */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
124 data[count-1].seq2--;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
125 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
126 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
127 if (data[0].seq1 == seq) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
128 /* shrink up first range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
129 data[0].seq1++;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
130 return;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
131 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
132
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
133 /* 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
134 binary search */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
135 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
136 while (left_idx < right_idx) {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
137 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
138
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
139 if (data[idx].seq1 > seq)
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
140 right_idx = idx;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
141 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
142 left_idx = idx+1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
143 else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
144 /* found it */
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 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
147 /* a single sequence range.
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
148 remove it entirely */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
149 array_delete(array, idx, 1);
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
150 } else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
151 /* shrink the range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
152 data[idx].seq1++;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
153 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
154 } 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
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].seq2--;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
157 } else {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
158 /* split the sequence range */
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
159 value.seq1 = seq + 1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
160 value.seq2 = data[idx].seq2;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
161 data[idx].seq2 = seq - 1;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
162
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
163 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
164 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
165 break;
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
166 }
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
167 }
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
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
170 int seq_range_exists(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
171 {
821035fdc9f6 Moved seq_range_*() functions to more generic ones in lib/.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
172 unsigned int idx;
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 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
175 }