Yet Another eXchange Tool  0.9.0
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://doc.redmine.dkrz.de/yaxt/html/
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 
59 void
60 xt_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 
68 void
69 xt_cover_finish(struct Xt_pos_ext_vec *restrict cover)
70 {
71  free(cover->pos_ext);
72 }
73 
74 bool
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 
94 size_t
95 xt_cover_search(struct Xt_pos_ext_vec *restrict cover,
96  struct Xt_pos_range query, bool forward,
97  size_t search_start_pos)
98 {
99  size_t i, num_pos_ext = cover->num_pos_ext;
100  struct Xt_pos_ext *restrict covered_pos_ext = cover->pos_ext;
101  if (num_pos_ext)
102  {
103  i = search_start_pos;
104  if (forward) {
105  while ((query.start >= (covered_pos_ext[i].start
106  + covered_pos_ext[i].size))
107  & (i < num_pos_ext - 1))
108  ++i;
109  } else {
110  while ((i > 0)
111  & (query.end < covered_pos_ext[i - 1].start - 1))
112  --i;
113  if ((i == 0)
114  & (query.start > covered_pos_ext[0].start + covered_pos_ext[0].size))
115  i = 1;
116  }
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)))
120  i = SIZE_MAX;
121  }
122  else
123  i = SIZE_MAX;
124  return i;
125 }
126 
127 void
128 xt_cover_range_append(struct Xt_pos_ext_vec *restrict cover,
129  struct Xt_pos_ext range)
130 {
131  size_t num_pos_ext = cover->num_pos_ext;
132  struct Xt_pos_ext *restrict cover_pos_ext = cover->pos_ext;
133  if (num_pos_ext > 0
134  && (cover_pos_ext[num_pos_ext - 1].start
135  + cover_pos_ext[num_pos_ext - 1].size
136  == range.start)) {
137  cover_pos_ext[num_pos_ext - 1].size += range.size;
138  } else {
139  ENSURE_ARRAY_SIZE(cover_pos_ext, cover->size_pos_ext, num_pos_ext + 1);
140  cover->pos_ext = cover_pos_ext;
141  cover_pos_ext[num_pos_ext] = range;
142  ++cover->num_pos_ext;
143  }
144 }
145 
146 
147 size_t
149  struct Xt_pos_range range, bool forward,
150  size_t search_start_pos)
151 {
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))
158  {
159  /* let caller handle overlap cases */
160  return insert_pos;
161  }
162  else if (range.end + 1 < cover_pos_ext[insert_pos].start)
163  {
164  /* range precedes cover->pos_ext[insert_pos] with a hole
165  * but might be a seemless extension of
166  * cover->pos_ext[insert_pos-1] */
167  if (insert_pos > 0
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;
171  else
172  {
173  size_t num_pos_ext = cover->num_pos_ext;
174  ENSURE_ARRAY_SIZE(cover_pos_ext,
175  cover->size_pos_ext,
176  num_pos_ext + 1);
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]
182  = (struct Xt_pos_ext){ .start = range.start,
183  .size = range.end - range.start + 1};
184  cover->num_pos_ext = ++num_pos_ext;
185  }
186  insert_pos = SIZE_MAX;
187  }
188  else if (range.end + 1 == cover_pos_ext[insert_pos].start)
189  {
190  cover_pos_ext[insert_pos].start = range.start;
191  cover_pos_ext[insert_pos].size += range.end - range.start + 1;
192  if (insert_pos > 0
193  && (cover_pos_ext[insert_pos].start
194  == (cover_pos_ext[insert_pos - 1].start
195  + cover_pos_ext[insert_pos - 1].size)))
196  {
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));
202  }
203  insert_pos = SIZE_MAX;
204  }
205  } else {
206  /* range was not found -> append */
207  xt_cover_range_append(cover, (struct Xt_pos_ext){ .start = range.start,
208  .size = range.end - range.start + 1});
209  }
210  return insert_pos;
211 }
212 
213 /*
214  * Local Variables:
215  * c-basic-offset: 2
216  * coding: utf-8
217  * indent-tabs-mode: nil
218  * show-trailing-whitespace: t
219  * require-trailing-newline: t
220  * End:
221  */
#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:60
size_t num_pos_ext
Definition: xt_cover.h:59
int size
Definition: xt_core.h:93
int start
Definition: xt_core.h:93
void xt_cover_range_append(struct Xt_pos_ext_vec *restrict cover, struct Xt_pos_ext range)
Definition: xt_cover.c:128
void xt_cover_finish(struct Xt_pos_ext_vec *restrict cover)
Definition: xt_cover.c:69
size_t xt_cover_search(struct Xt_pos_ext_vec *restrict cover, struct Xt_pos_range query, bool forward, size_t search_start_pos)
Definition: xt_cover.c:95
bool xt_idxlist_pos_ext_is_full_cover(Xt_idxlist idxlist, struct Xt_pos_ext_vec cover)
Definition: xt_cover.c:75
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)
Definition: xt_cover.c:148
void xt_cover_start(struct Xt_pos_ext_vec *restrict cover, size_t initial_size)
Definition: xt_cover.c:60
index list declaration
int xt_idxlist_get_num_indices(Xt_idxlist idxlist)
Definition: xt_idxlist.c:98