63 cover->num_pos_ext = 0;
64 cover->size_pos_ext = initial_size;
65 cover->pos_ext =
xmalloc(
sizeof (*cover->pos_ext) * initial_size);
84 int after_last_end_pos = 0;
85 int continuations_hold = 1;
87 continuations_hold &= (cover.
pos_ext[i].
start == after_last_end_pos);
90 continuations_hold &= (after_last_end_pos == idxlist_size);
91 return continuations_hold;
97 size_t search_start_pos)
99 size_t i, num_pos_ext = cover->num_pos_ext;
100 struct Xt_pos_ext *restrict covered_pos_ext = cover->pos_ext;
103 i = search_start_pos;
105 while ((query.
start >= (covered_pos_ext[i].start
106 + covered_pos_ext[i].size))
107 & (i < num_pos_ext - 1))
111 & (query.
end < covered_pos_ext[i - 1].start - 1))
114 & (query.
start > covered_pos_ext[0].start + covered_pos_ext[0].size))
117 if ((i >= num_pos_ext - 1)
118 & (query.
start >= (covered_pos_ext[num_pos_ext - 1].start
119 + covered_pos_ext[num_pos_ext - 1].size)))
131 size_t num_pos_ext = cover->num_pos_ext;
132 struct Xt_pos_ext *restrict cover_pos_ext = cover->pos_ext;
134 && (cover_pos_ext[num_pos_ext - 1].
start
135 + cover_pos_ext[num_pos_ext - 1].
size
137 cover_pos_ext[num_pos_ext - 1].
size += range.
size;
140 cover->pos_ext = cover_pos_ext;
141 cover_pos_ext[num_pos_ext] = range;
142 ++cover->num_pos_ext;
150 size_t search_start_pos)
152 size_t insert_pos =
xt_cover_search(cover, range, forward, search_start_pos);
153 struct Xt_pos_ext *restrict cover_pos_ext = cover->pos_ext;
154 if (insert_pos != SIZE_MAX) {
155 if ((range.
start < (cover_pos_ext[insert_pos].start
156 + cover_pos_ext[insert_pos].size))
157 & (range.
end >= cover_pos_ext[insert_pos].start))
162 else if (range.
end + 1 < cover_pos_ext[insert_pos].start)
168 && (cover_pos_ext[insert_pos - 1].
start
169 + cover_pos_ext[insert_pos - 1].
size == range.
start))
170 cover_pos_ext[insert_pos - 1].
size += range.
end - range.
start + 1;
173 size_t num_pos_ext = cover->num_pos_ext;
177 cover->pos_ext = cover_pos_ext;
178 memmove(cover_pos_ext + insert_pos + 1, cover_pos_ext + insert_pos,
179 sizeof (*cover_pos_ext)
180 * (num_pos_ext - insert_pos));
181 cover_pos_ext[insert_pos]
183 .size = range.
end - range.
start + 1};
184 cover->num_pos_ext = ++num_pos_ext;
186 insert_pos = SIZE_MAX;
188 else if (range.
end + 1 == cover_pos_ext[insert_pos].start)
190 cover_pos_ext[insert_pos].start = range.
start;
191 cover_pos_ext[insert_pos].size += range.
end - range.
start + 1;
193 && (cover_pos_ext[insert_pos].start
194 == (cover_pos_ext[insert_pos - 1].start
195 + cover_pos_ext[insert_pos - 1].size)))
197 cover_pos_ext[insert_pos - 1].size
198 += cover_pos_ext[insert_pos].size;
199 memmove(cover_pos_ext + insert_pos, cover_pos_ext + insert_pos + 1,
200 (--cover->num_pos_ext - insert_pos)
201 * sizeof (*cover_pos_ext));
203 insert_pos = SIZE_MAX;
208 .size = range.
end - range.
start + 1});
#define ENSURE_ARRAY_SIZE(arrayp, curr_array_size, req_size)
add versions of standard API functions not returning on error
struct Xt_pos_ext * pos_ext
void xt_cover_range_append(struct Xt_pos_ext_vec *restrict cover, struct Xt_pos_ext range)
void xt_cover_finish(struct Xt_pos_ext_vec *restrict cover)
size_t xt_cover_search(struct Xt_pos_ext_vec *restrict cover, struct Xt_pos_range query, bool forward, size_t search_start_pos)
bool xt_idxlist_pos_ext_is_full_cover(Xt_idxlist idxlist, struct Xt_pos_ext_vec cover)
size_t xt_cover_insert_or_overlap(struct Xt_pos_ext_vec *restrict cover, struct Xt_pos_range range, bool forward, size_t search_start_pos)
void xt_cover_start(struct Xt_pos_ext_vec *restrict cover, size_t initial_size)
int xt_idxlist_get_num_indices(Xt_idxlist idxlist)