Yet Another eXchange Tool 0.11.4
Loading...
Searching...
No Matches
xt_cover.c
Go to the documentation of this file.
1
12/*
13 * Keywords:
14 * Maintainer: Jörg Behrens <behrens@dkrz.de>
15 * Moritz Hanke <hanke@dkrz.de>
16 * Thomas Jahns <jahns@dkrz.de>
17 * URL: https://dkrz-sw.gitlab-pages.dkrz.de/yaxt/
18 *
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions are
21 * met:
22 *
23 * Redistributions of source code must retain the above copyright notice,
24 * this list of conditions and the following disclaimer.
25 *
26 * Redistributions in binary form must reproduce the above copyright
27 * notice, this list of conditions and the following disclaimer in the
28 * documentation and/or other materials provided with the distribution.
29 *
30 * Neither the name of the DKRZ GmbH nor the names of its contributors
31 * may be used to endorse or promote products derived from this software
32 * without specific prior written permission.
33 *
34 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
35 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
36 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
37 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
38 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
39 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
40 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
41 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
42 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
43 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
44 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
45 */
46
47#ifdef HAVE_CONFIG_H
48#include <config.h>
49#endif
50
51#include <stdlib.h>
52#include <string.h>
53
54#include "core/ppm_xfuncs.h"
55#include "ensure_array_size.h"
56#include "xt/xt_idxlist.h"
57#include "xt_cover.h"
58
59void
60xt_cover_start(struct Xt_pos_ext_vec *restrict cover,
61 size_t initial_size)
62{
63 cover->num_pos_ext = 0;
64 cover->size_pos_ext = initial_size;
65 cover->pos_ext = xmalloc(sizeof (*cover->pos_ext) * initial_size);
66}
67
68void
69xt_cover_finish(struct Xt_pos_ext_vec *restrict cover)
70{
71 free(cover->pos_ext);
72}
73
74bool
76 struct Xt_pos_ext_vec cover)
77{
78 int idxlist_size = xt_idxlist_get_num_indices(idxlist);
79 if ((idxlist_size == 0) & (cover.num_pos_ext == 0))
80 return true;
81 if ((idxlist_size == 0) ^ (cover.num_pos_ext == 0))
82 return false;
83 /* at this point both idxlist and cover are non-empty */
84 int after_last_end_pos = 0;
85 int continuations_hold = 1;
86 for (size_t i = 0; i < cover.num_pos_ext; ++i) {
87 continuations_hold &= (cover.pos_ext[i].start == after_last_end_pos);
88 after_last_end_pos += cover.pos_ext[i].size;
89 }
90 continuations_hold &= (after_last_end_pos == idxlist_size);
91 return continuations_hold;
92}
93
94static size_t
95xt_cover_search_(struct Xt_pos_ext_vec *restrict cover,
96 struct Xt_pos_range query,
97 size_t search_start_pos);
98
99size_t
100xt_cover_search(struct Xt_pos_ext_vec *restrict cover,
101 struct Xt_pos_range query,
102 size_t search_start_pos)
103{
104 return xt_cover_search_(cover, query, search_start_pos);
105}
106
107static size_t
108xt_cover_search_(struct Xt_pos_ext_vec *restrict cover,
109 struct Xt_pos_range query,
110 size_t search_start_pos)
111{
112 size_t num_pos_ext = cover->num_pos_ext;
113 struct Xt_pos_ext *restrict covered_pos_ext = cover->pos_ext;
114 size_t lb = search_start_pos, ub = num_pos_ext;
115 size_t result = SIZE_MAX;
116 while (lb < ub) {
117 size_t guess = lb+(ub-lb)/2;
118 if (query.start >= (covered_pos_ext[guess].start
119 + covered_pos_ext[guess].size))
120 lb = guess+1;
121 else if (query.end < covered_pos_ext[guess].start) {
122 if (guess == 0
123 || query.start >= (covered_pos_ext[guess-1].start
124 + covered_pos_ext[guess-1].size)) {
125 result = guess;
126 break;
127 } else
128 ub = guess;
129 } else {
130 while (guess && query.start < (covered_pos_ext[guess-1].start
131 + covered_pos_ext[guess-1].size))
132 --guess;
133 result = guess;
134 break;
135 }
136 }
137 return result;
138}
139
140void
142 struct Xt_pos_ext range)
143{
144 size_t num_pos_ext = cover->num_pos_ext;
145 struct Xt_pos_ext *restrict cover_pos_ext = cover->pos_ext;
146 if (num_pos_ext > 0
147 && (cover_pos_ext[num_pos_ext - 1].start
148 + cover_pos_ext[num_pos_ext - 1].size
149 == range.start)) {
150 cover_pos_ext[num_pos_ext - 1].size += range.size;
151 } else {
152 ENSURE_ARRAY_SIZE(cover_pos_ext, cover->size_pos_ext, num_pos_ext + 1);
153 cover->pos_ext = cover_pos_ext;
154 cover_pos_ext[num_pos_ext] = range;
155 ++cover->num_pos_ext;
156 }
157}
158
159
160size_t
162 struct Xt_pos_range range,
163 size_t search_start_pos)
164{
165 size_t insert_pos = xt_cover_search_(cover, range, search_start_pos);
166 struct Xt_pos_ext *restrict cover_pos_ext = cover->pos_ext;
167 if (insert_pos != SIZE_MAX) {
168 if ((range.start < (cover_pos_ext[insert_pos].start
169 + cover_pos_ext[insert_pos].size))
170 & (range.end >= cover_pos_ext[insert_pos].start))
171 {
172 /* let caller handle overlap cases */
173 return insert_pos;
174 }
175 else if (range.end + 1 < cover_pos_ext[insert_pos].start)
176 {
177 /* range precedes cover->pos_ext[insert_pos] with a hole
178 * but might be a seamless extension of
179 * cover->pos_ext[insert_pos-1] */
180 if (insert_pos > 0
181 && (cover_pos_ext[insert_pos - 1].start
182 + cover_pos_ext[insert_pos - 1].size == range.start))
183 cover_pos_ext[insert_pos - 1].size += range.end - range.start + 1;
184 else
185 {
186 size_t num_pos_ext = cover->num_pos_ext;
187 ENSURE_ARRAY_SIZE(cover_pos_ext,
188 cover->size_pos_ext,
189 num_pos_ext + 1);
190 cover->pos_ext = cover_pos_ext;
191 memmove(cover_pos_ext + insert_pos + 1, cover_pos_ext + insert_pos,
192 sizeof (*cover_pos_ext)
193 * (num_pos_ext - insert_pos));
194 cover_pos_ext[insert_pos]
195 = (struct Xt_pos_ext){ .start = range.start,
196 .size = range.end - range.start + 1};
197 cover->num_pos_ext = ++num_pos_ext;
198 }
199 insert_pos = SIZE_MAX;
200 }
201 else if (range.end + 1 == cover_pos_ext[insert_pos].start)
202 {
203 cover_pos_ext[insert_pos].start = range.start;
204 cover_pos_ext[insert_pos].size += range.end - range.start + 1;
205 if (insert_pos > 0
206 && (cover_pos_ext[insert_pos].start
207 == (cover_pos_ext[insert_pos - 1].start
208 + cover_pos_ext[insert_pos - 1].size)))
209 {
210 cover_pos_ext[insert_pos - 1].size
211 += cover_pos_ext[insert_pos].size;
212 memmove(cover_pos_ext + insert_pos, cover_pos_ext + insert_pos + 1,
213 (--cover->num_pos_ext - insert_pos)
214 * sizeof (*cover_pos_ext));
215 }
216 insert_pos = SIZE_MAX;
217 }
218 } else {
219 /* range was not found -> append */
220 xt_cover_range_append(cover, (struct Xt_pos_ext){ .start = range.start,
221 .size = range.end - range.start + 1});
222 }
223 return insert_pos;
224}
225
226/*
227 * Local Variables:
228 * c-basic-offset: 2
229 * coding: utf-8
230 * indent-tabs-mode: nil
231 * show-trailing-whitespace: t
232 * require-trailing-newline: t
233 * End:
234 */
#define ENSURE_ARRAY_SIZE(arrayp, curr_array_size, req_size)
add versions of standard API functions not returning on error
#define xmalloc(size)
Definition ppm_xfuncs.h:70
struct Xt_pos_ext * pos_ext
Definition xt_cover.h:61
size_t num_pos_ext
Definition xt_cover.h:60
int size
Definition xt_core.h:97
int start
Definition xt_core.h:97
static size_t xt_cover_search_(struct Xt_pos_ext_vec *restrict cover, struct Xt_pos_range query, size_t search_start_pos)
Definition xt_cover.c:108
size_t xt_cover_insert_or_overlap(struct Xt_pos_ext_vec *restrict cover, struct Xt_pos_range range, size_t search_start_pos)
Definition xt_cover.c:161
void xt_cover_range_append(struct Xt_pos_ext_vec *restrict cover, struct Xt_pos_ext range)
Definition xt_cover.c:141
void xt_cover_finish(struct Xt_pos_ext_vec *restrict cover)
Definition xt_cover.c:69
bool xt_idxlist_pos_ext_is_full_cover(Xt_idxlist idxlist, struct Xt_pos_ext_vec cover)
Definition xt_cover.c:75
void xt_cover_start(struct Xt_pos_ext_vec *restrict cover, size_t initial_size)
Definition xt_cover.c:60
size_t xt_cover_search(struct Xt_pos_ext_vec *restrict cover, struct Xt_pos_range query, size_t search_start_pos)
Definition xt_cover.c:100
index list declaration
#define xt_idxlist_get_num_indices(idxlist)