/src/croaring/include/roaring/containers/run.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * run.h |
3 | | * |
4 | | */ |
5 | | |
6 | | #ifndef INCLUDE_CONTAINERS_RUN_H_ |
7 | | #define INCLUDE_CONTAINERS_RUN_H_ |
8 | | |
9 | | #include <roaring/roaring_types.h> // roaring_iterator |
10 | | |
11 | | // Include other headers after roaring_types.h |
12 | | #include <assert.h> |
13 | | #include <stdbool.h> |
14 | | #include <stdint.h> |
15 | | #include <string.h> |
16 | | |
17 | | #include <roaring/array_util.h> // binarySearch()/memequals() for inlining |
18 | | #include <roaring/containers/container_defs.h> // container_t, perfparameters |
19 | | #include <roaring/portability.h> |
20 | | |
21 | | #ifdef __cplusplus |
22 | | extern "C" { |
23 | | namespace roaring { |
24 | | |
25 | | // Note: in pure C++ code, you should avoid putting `using` in header files |
26 | | using api::roaring_iterator; |
27 | | using api::roaring_iterator64; |
28 | | |
29 | | namespace internal { |
30 | | #endif |
31 | | |
32 | | /* struct rle16_s - run length pair |
33 | | * |
34 | | * @value: start position of the run |
35 | | * @length: length of the run is `length + 1` |
36 | | * |
37 | | * An RLE pair {v, l} would represent the integers between the interval |
38 | | * [v, v+l+1], e.g. {3, 2} = [3, 4, 5]. |
39 | | */ |
40 | | struct rle16_s { |
41 | | uint16_t value; |
42 | | uint16_t length; |
43 | | }; |
44 | | |
45 | | typedef struct rle16_s rle16_t; |
46 | | |
47 | | #ifdef __cplusplus |
48 | | #define CROARING_MAKE_RLE16(val, len) \ |
49 | | { (uint16_t)(val), (uint16_t)(len) } // no tagged structs until c++20 |
50 | | #else |
51 | | #define CROARING_MAKE_RLE16(val, len) \ |
52 | 0 | (rle16_t) { .value = (uint16_t)(val), .length = (uint16_t)(len) } |
53 | | #endif |
54 | | |
55 | | /* struct run_container_s - run container bitmap |
56 | | * |
57 | | * @n_runs: number of rle_t pairs in `runs`. |
58 | | * @capacity: capacity in rle_t pairs `runs` can hold. |
59 | | * @runs: pairs of rle_t. |
60 | | */ |
61 | | STRUCT_CONTAINER(run_container_s) { |
62 | | int32_t n_runs; |
63 | | int32_t capacity; |
64 | | rle16_t *runs; |
65 | | }; |
66 | | |
67 | | typedef struct run_container_s run_container_t; |
68 | | |
69 | 209k | #define CAST_run(c) CAST(run_container_t *, c) // safer downcast |
70 | 234k | #define const_CAST_run(c) CAST(const run_container_t *, c) |
71 | | #define movable_CAST_run(c) movable_CAST(run_container_t **, c) |
72 | | |
73 | | /* Create a new run container. Return NULL in case of failure. */ |
74 | | run_container_t *run_container_create(void); |
75 | | |
76 | | /* Create a new run container with given capacity. Return NULL in case of |
77 | | * failure. */ |
78 | | run_container_t *run_container_create_given_capacity(int32_t size); |
79 | | |
80 | | /* |
81 | | * Shrink the capacity to the actual size, return the number of bytes saved. |
82 | | */ |
83 | | int run_container_shrink_to_fit(run_container_t *src); |
84 | | |
85 | | /* Free memory owned by `run'. */ |
86 | | void run_container_free(run_container_t *run); |
87 | | |
88 | | /* Duplicate container */ |
89 | | run_container_t *run_container_clone(const run_container_t *src); |
90 | | |
91 | | /* |
92 | | * Effectively deletes the value at index index, repacking data. |
93 | | */ |
94 | 207 | static inline void recoverRoomAtIndex(run_container_t *run, uint16_t index) { |
95 | 207 | memmove(run->runs + index, run->runs + (1 + index), |
96 | 207 | (run->n_runs - index - 1) * sizeof(rle16_t)); |
97 | 207 | run->n_runs--; |
98 | 207 | } Unexecuted instantiation: roaring.c:recoverRoomAtIndex Unexecuted instantiation: roaring64.c:recoverRoomAtIndex Unexecuted instantiation: roaring_array.c:recoverRoomAtIndex Unexecuted instantiation: containers.c:recoverRoomAtIndex Unexecuted instantiation: convert.c:recoverRoomAtIndex Unexecuted instantiation: mixed_intersection.c:recoverRoomAtIndex Unexecuted instantiation: mixed_union.c:recoverRoomAtIndex Unexecuted instantiation: mixed_equal.c:recoverRoomAtIndex Unexecuted instantiation: mixed_subset.c:recoverRoomAtIndex Unexecuted instantiation: mixed_negation.c:recoverRoomAtIndex Unexecuted instantiation: mixed_xor.c:recoverRoomAtIndex Unexecuted instantiation: mixed_andnot.c:recoverRoomAtIndex Line | Count | Source | 94 | 207 | static inline void recoverRoomAtIndex(run_container_t *run, uint16_t index) { | 95 | 207 | memmove(run->runs + index, run->runs + (1 + index), | 96 | 207 | (run->n_runs - index - 1) * sizeof(rle16_t)); | 97 | 207 | run->n_runs--; | 98 | 207 | } |
|
99 | | |
100 | | /** |
101 | | * Good old binary search through rle data |
102 | | */ |
103 | | inline int32_t interleavedBinarySearch(const rle16_t *array, int32_t lenarray, |
104 | 387k | uint16_t ikey) { |
105 | 387k | int32_t low = 0; |
106 | 387k | int32_t high = lenarray - 1; |
107 | 1.20M | while (low <= high) { |
108 | 816k | int32_t middleIndex = (low + high) >> 1; |
109 | 816k | uint16_t middleValue = array[middleIndex].value; |
110 | 816k | if (middleValue < ikey) { |
111 | 591k | low = middleIndex + 1; |
112 | 591k | } else if (middleValue > ikey) { |
113 | 225k | high = middleIndex - 1; |
114 | 225k | } else { |
115 | 11 | return middleIndex; |
116 | 11 | } |
117 | 816k | } |
118 | 387k | return -(low + 1); |
119 | 387k | } |
120 | | |
121 | | /* |
122 | | * Returns index of the run which contains $ikey |
123 | | */ |
124 | | static inline int32_t rle16_find_run(const rle16_t *array, int32_t lenarray, |
125 | 0 | uint16_t ikey) { |
126 | 0 | int32_t low = 0; |
127 | 0 | int32_t high = lenarray - 1; |
128 | 0 | while (low <= high) { |
129 | 0 | int32_t middleIndex = (low + high) >> 1; |
130 | 0 | uint16_t min = array[middleIndex].value; |
131 | 0 | uint16_t max = array[middleIndex].value + array[middleIndex].length; |
132 | 0 | if (ikey > max) { |
133 | 0 | low = middleIndex + 1; |
134 | 0 | } else if (ikey < min) { |
135 | 0 | high = middleIndex - 1; |
136 | 0 | } else { |
137 | 0 | return middleIndex; |
138 | 0 | } |
139 | 0 | } |
140 | 0 | return -(low + 1); |
141 | 0 | } Unexecuted instantiation: roaring.c:rle16_find_run Unexecuted instantiation: roaring64.c:rle16_find_run Unexecuted instantiation: roaring_array.c:rle16_find_run Unexecuted instantiation: containers.c:rle16_find_run Unexecuted instantiation: convert.c:rle16_find_run Unexecuted instantiation: mixed_intersection.c:rle16_find_run Unexecuted instantiation: mixed_union.c:rle16_find_run Unexecuted instantiation: mixed_equal.c:rle16_find_run Unexecuted instantiation: mixed_subset.c:rle16_find_run Unexecuted instantiation: mixed_negation.c:rle16_find_run Unexecuted instantiation: mixed_xor.c:rle16_find_run Unexecuted instantiation: mixed_andnot.c:rle16_find_run Unexecuted instantiation: run.c:rle16_find_run |
142 | | |
143 | | /** |
144 | | * Returns number of runs which can'be be merged with the key because they |
145 | | * are less than the key. |
146 | | * Note that [5,6,7,8] can be merged with the key 9 and won't be counted. |
147 | | */ |
148 | | static inline int32_t rle16_count_less(const rle16_t *array, int32_t lenarray, |
149 | 0 | uint16_t key) { |
150 | 0 | if (lenarray == 0) return 0; |
151 | 0 | int32_t low = 0; |
152 | 0 | int32_t high = lenarray - 1; |
153 | 0 | while (low <= high) { |
154 | 0 | int32_t middleIndex = (low + high) >> 1; |
155 | 0 | uint16_t min_value = array[middleIndex].value; |
156 | 0 | uint16_t max_value = |
157 | 0 | array[middleIndex].value + array[middleIndex].length; |
158 | 0 | if (max_value + UINT32_C(1) < key) { // uint32 arithmetic |
159 | 0 | low = middleIndex + 1; |
160 | 0 | } else if (key < min_value) { |
161 | 0 | high = middleIndex - 1; |
162 | 0 | } else { |
163 | 0 | return middleIndex; |
164 | 0 | } |
165 | 0 | } |
166 | 0 | return low; |
167 | 0 | } Unexecuted instantiation: roaring.c:rle16_count_less Unexecuted instantiation: roaring64.c:rle16_count_less Unexecuted instantiation: roaring_array.c:rle16_count_less Unexecuted instantiation: containers.c:rle16_count_less Unexecuted instantiation: convert.c:rle16_count_less Unexecuted instantiation: mixed_intersection.c:rle16_count_less Unexecuted instantiation: mixed_union.c:rle16_count_less Unexecuted instantiation: mixed_equal.c:rle16_count_less Unexecuted instantiation: mixed_subset.c:rle16_count_less Unexecuted instantiation: mixed_negation.c:rle16_count_less Unexecuted instantiation: mixed_xor.c:rle16_count_less Unexecuted instantiation: mixed_andnot.c:rle16_count_less Unexecuted instantiation: run.c:rle16_count_less |
168 | | |
169 | | static inline int32_t rle16_count_greater(const rle16_t *array, |
170 | 0 | int32_t lenarray, uint16_t key) { |
171 | 0 | if (lenarray == 0) return 0; |
172 | 0 | int32_t low = 0; |
173 | 0 | int32_t high = lenarray - 1; |
174 | 0 | while (low <= high) { |
175 | 0 | int32_t middleIndex = (low + high) >> 1; |
176 | 0 | uint16_t min_value = array[middleIndex].value; |
177 | 0 | uint16_t max_value = |
178 | 0 | array[middleIndex].value + array[middleIndex].length; |
179 | 0 | if (max_value < key) { |
180 | 0 | low = middleIndex + 1; |
181 | 0 | } else if (key + UINT32_C(1) < min_value) { // uint32 arithmetic |
182 | 0 | high = middleIndex - 1; |
183 | 0 | } else { |
184 | 0 | return lenarray - (middleIndex + 1); |
185 | 0 | } |
186 | 0 | } |
187 | 0 | return lenarray - low; |
188 | 0 | } Unexecuted instantiation: roaring.c:rle16_count_greater Unexecuted instantiation: roaring64.c:rle16_count_greater Unexecuted instantiation: roaring_array.c:rle16_count_greater Unexecuted instantiation: containers.c:rle16_count_greater Unexecuted instantiation: convert.c:rle16_count_greater Unexecuted instantiation: mixed_intersection.c:rle16_count_greater Unexecuted instantiation: mixed_union.c:rle16_count_greater Unexecuted instantiation: mixed_equal.c:rle16_count_greater Unexecuted instantiation: mixed_subset.c:rle16_count_greater Unexecuted instantiation: mixed_negation.c:rle16_count_greater Unexecuted instantiation: mixed_xor.c:rle16_count_greater Unexecuted instantiation: mixed_andnot.c:rle16_count_greater Unexecuted instantiation: run.c:rle16_count_greater |
189 | | |
190 | | /** |
191 | | * increase capacity to at least min. Whether the |
192 | | * existing data needs to be copied over depends on copy. If "copy" is false, |
193 | | * then the new content will be uninitialized, otherwise a copy is made. |
194 | | */ |
195 | | void run_container_grow(run_container_t *run, int32_t min, bool copy); |
196 | | |
197 | | /** |
198 | | * Moves the data so that we can write data at index |
199 | | */ |
200 | 192 | static inline void makeRoomAtIndex(run_container_t *run, uint16_t index) { |
201 | | /* This function calls realloc + memmove sequentially to move by one index. |
202 | | * Potentially copying twice the array. |
203 | | */ |
204 | 192 | if (run->n_runs + 1 > run->capacity) |
205 | 192 | run_container_grow(run, run->n_runs + 1, true); |
206 | 192 | memmove(run->runs + 1 + index, run->runs + index, |
207 | 192 | (run->n_runs - index) * sizeof(rle16_t)); |
208 | 192 | run->n_runs++; |
209 | 192 | } Unexecuted instantiation: roaring.c:makeRoomAtIndex Unexecuted instantiation: roaring64.c:makeRoomAtIndex Unexecuted instantiation: roaring_array.c:makeRoomAtIndex Unexecuted instantiation: containers.c:makeRoomAtIndex Unexecuted instantiation: convert.c:makeRoomAtIndex Unexecuted instantiation: mixed_intersection.c:makeRoomAtIndex Unexecuted instantiation: mixed_union.c:makeRoomAtIndex Unexecuted instantiation: mixed_equal.c:makeRoomAtIndex Unexecuted instantiation: mixed_subset.c:makeRoomAtIndex Unexecuted instantiation: mixed_negation.c:makeRoomAtIndex Unexecuted instantiation: mixed_xor.c:makeRoomAtIndex Unexecuted instantiation: mixed_andnot.c:makeRoomAtIndex Line | Count | Source | 200 | 192 | static inline void makeRoomAtIndex(run_container_t *run, uint16_t index) { | 201 | | /* This function calls realloc + memmove sequentially to move by one index. | 202 | | * Potentially copying twice the array. | 203 | | */ | 204 | 192 | if (run->n_runs + 1 > run->capacity) | 205 | 192 | run_container_grow(run, run->n_runs + 1, true); | 206 | 192 | memmove(run->runs + 1 + index, run->runs + index, | 207 | 192 | (run->n_runs - index) * sizeof(rle16_t)); | 208 | 192 | run->n_runs++; | 209 | 192 | } |
|
210 | | |
211 | | /* Add `pos' to `run'. Returns true if `pos' was not present. */ |
212 | | bool run_container_add(run_container_t *run, uint16_t pos); |
213 | | |
214 | | /* Remove `pos' from `run'. Returns true if `pos' was present. */ |
215 | 0 | static inline bool run_container_remove(run_container_t *run, uint16_t pos) { |
216 | 0 | int32_t index = interleavedBinarySearch(run->runs, run->n_runs, pos); |
217 | 0 | if (index >= 0) { |
218 | 0 | int32_t le = run->runs[index].length; |
219 | 0 | if (le == 0) { |
220 | 0 | recoverRoomAtIndex(run, (uint16_t)index); |
221 | 0 | } else { |
222 | 0 | run->runs[index].value++; |
223 | 0 | run->runs[index].length--; |
224 | 0 | } |
225 | 0 | return true; |
226 | 0 | } |
227 | 0 | index = -index - 2; // points to preceding value, possibly -1 |
228 | 0 | if (index >= 0) { // possible match |
229 | 0 | int32_t offset = pos - run->runs[index].value; |
230 | 0 | int32_t le = run->runs[index].length; |
231 | 0 | if (offset < le) { |
232 | | // need to break in two |
233 | 0 | run->runs[index].length = (uint16_t)(offset - 1); |
234 | | // need to insert |
235 | 0 | uint16_t newvalue = pos + 1; |
236 | 0 | int32_t newlength = le - offset - 1; |
237 | 0 | makeRoomAtIndex(run, (uint16_t)(index + 1)); |
238 | 0 | run->runs[index + 1].value = newvalue; |
239 | 0 | run->runs[index + 1].length = (uint16_t)newlength; |
240 | 0 | return true; |
241 | |
|
242 | 0 | } else if (offset == le) { |
243 | 0 | run->runs[index].length--; |
244 | 0 | return true; |
245 | 0 | } |
246 | 0 | } |
247 | | // no match |
248 | 0 | return false; |
249 | 0 | } Unexecuted instantiation: roaring.c:run_container_remove Unexecuted instantiation: roaring64.c:run_container_remove Unexecuted instantiation: roaring_array.c:run_container_remove Unexecuted instantiation: containers.c:run_container_remove Unexecuted instantiation: convert.c:run_container_remove Unexecuted instantiation: mixed_intersection.c:run_container_remove Unexecuted instantiation: mixed_union.c:run_container_remove Unexecuted instantiation: mixed_equal.c:run_container_remove Unexecuted instantiation: mixed_subset.c:run_container_remove Unexecuted instantiation: mixed_negation.c:run_container_remove Unexecuted instantiation: mixed_xor.c:run_container_remove Unexecuted instantiation: mixed_andnot.c:run_container_remove Unexecuted instantiation: run.c:run_container_remove |
250 | | |
251 | | /* Check whether `pos' is present in `run'. */ |
252 | 222k | inline bool run_container_contains(const run_container_t *run, uint16_t pos) { |
253 | 222k | int32_t index = interleavedBinarySearch(run->runs, run->n_runs, pos); |
254 | 222k | if (index >= 0) return true; |
255 | 222k | index = -index - 2; // points to preceding value, possibly -1 |
256 | 222k | if (index != -1) { // possible match |
257 | 222k | int32_t offset = pos - run->runs[index].value; |
258 | 222k | int32_t le = run->runs[index].length; |
259 | 222k | if (offset <= le) return true; |
260 | 222k | } |
261 | 165k | return false; |
262 | 222k | } |
263 | | |
264 | | /* |
265 | | * Check whether all positions in a range of positions from pos_start (included) |
266 | | * to pos_end (excluded) is present in `run'. |
267 | | */ |
268 | | static inline bool run_container_contains_range(const run_container_t *run, |
269 | | uint32_t pos_start, |
270 | 0 | uint32_t pos_end) { |
271 | 0 | uint32_t count = 0; |
272 | 0 | int32_t index = |
273 | 0 | interleavedBinarySearch(run->runs, run->n_runs, (uint16_t)pos_start); |
274 | 0 | if (index < 0) { |
275 | 0 | index = -index - 2; |
276 | 0 | if ((index == -1) || |
277 | 0 | ((pos_start - run->runs[index].value) > run->runs[index].length)) { |
278 | 0 | return false; |
279 | 0 | } |
280 | 0 | } |
281 | 0 | for (int32_t i = index; i < run->n_runs; ++i) { |
282 | 0 | const uint32_t stop = run->runs[i].value + run->runs[i].length; |
283 | 0 | if (run->runs[i].value >= pos_end) break; |
284 | 0 | if (stop >= pos_end) { |
285 | 0 | count += (((pos_end - run->runs[i].value) > 0) |
286 | 0 | ? (pos_end - run->runs[i].value) |
287 | 0 | : 0); |
288 | 0 | break; |
289 | 0 | } |
290 | 0 | const uint32_t min = (stop - pos_start) > 0 ? (stop - pos_start) : 0; |
291 | 0 | count += (min < run->runs[i].length) ? min : run->runs[i].length; |
292 | 0 | } |
293 | 0 | return count >= (pos_end - pos_start - 1); |
294 | 0 | } Unexecuted instantiation: roaring.c:run_container_contains_range Unexecuted instantiation: roaring64.c:run_container_contains_range Unexecuted instantiation: roaring_array.c:run_container_contains_range Unexecuted instantiation: containers.c:run_container_contains_range Unexecuted instantiation: convert.c:run_container_contains_range Unexecuted instantiation: mixed_intersection.c:run_container_contains_range Unexecuted instantiation: mixed_union.c:run_container_contains_range Unexecuted instantiation: mixed_equal.c:run_container_contains_range Unexecuted instantiation: mixed_subset.c:run_container_contains_range Unexecuted instantiation: mixed_negation.c:run_container_contains_range Unexecuted instantiation: mixed_xor.c:run_container_contains_range Unexecuted instantiation: mixed_andnot.c:run_container_contains_range Unexecuted instantiation: run.c:run_container_contains_range |
295 | | |
296 | | /* Get the cardinality of `run'. Requires an actual computation. */ |
297 | | int run_container_cardinality(const run_container_t *run); |
298 | | |
299 | | /* Card > 0?, see run_container_empty for the reverse */ |
300 | | static inline bool run_container_nonzero_cardinality( |
301 | 0 | const run_container_t *run) { |
302 | 0 | return run->n_runs > 0; // runs never empty |
303 | 0 | } Unexecuted instantiation: roaring.c:run_container_nonzero_cardinality Unexecuted instantiation: roaring64.c:run_container_nonzero_cardinality Unexecuted instantiation: roaring_array.c:run_container_nonzero_cardinality Unexecuted instantiation: containers.c:run_container_nonzero_cardinality Unexecuted instantiation: convert.c:run_container_nonzero_cardinality Unexecuted instantiation: mixed_intersection.c:run_container_nonzero_cardinality Unexecuted instantiation: mixed_union.c:run_container_nonzero_cardinality Unexecuted instantiation: mixed_equal.c:run_container_nonzero_cardinality Unexecuted instantiation: mixed_subset.c:run_container_nonzero_cardinality Unexecuted instantiation: mixed_negation.c:run_container_nonzero_cardinality Unexecuted instantiation: mixed_xor.c:run_container_nonzero_cardinality Unexecuted instantiation: mixed_andnot.c:run_container_nonzero_cardinality Unexecuted instantiation: run.c:run_container_nonzero_cardinality |
304 | | |
305 | | /* Card == 0?, see run_container_nonzero_cardinality for the reverse */ |
306 | 0 | static inline bool run_container_empty(const run_container_t *run) { |
307 | 0 | return run->n_runs == 0; // runs never empty |
308 | 0 | } Unexecuted instantiation: roaring.c:run_container_empty Unexecuted instantiation: roaring64.c:run_container_empty Unexecuted instantiation: roaring_array.c:run_container_empty Unexecuted instantiation: containers.c:run_container_empty Unexecuted instantiation: convert.c:run_container_empty Unexecuted instantiation: mixed_intersection.c:run_container_empty Unexecuted instantiation: mixed_union.c:run_container_empty Unexecuted instantiation: mixed_equal.c:run_container_empty Unexecuted instantiation: mixed_subset.c:run_container_empty Unexecuted instantiation: mixed_negation.c:run_container_empty Unexecuted instantiation: mixed_xor.c:run_container_empty Unexecuted instantiation: mixed_andnot.c:run_container_empty Unexecuted instantiation: run.c:run_container_empty |
309 | | |
310 | | /* Copy one container into another. We assume that they are distinct. */ |
311 | | void run_container_copy(const run_container_t *src, run_container_t *dst); |
312 | | |
313 | | /** |
314 | | * Append run described by vl to the run container, possibly merging. |
315 | | * It is assumed that the run would be inserted at the end of the container, no |
316 | | * check is made. |
317 | | * It is assumed that the run container has the necessary capacity: caller is |
318 | | * responsible for checking memory capacity. |
319 | | * |
320 | | * |
321 | | * This is not a safe function, it is meant for performance: use with care. |
322 | | */ |
323 | | static inline void run_container_append(run_container_t *run, rle16_t vl, |
324 | 0 | rle16_t *previousrl) { |
325 | 0 | const uint32_t previousend = previousrl->value + previousrl->length; |
326 | 0 | if (vl.value > previousend + 1) { // we add a new one |
327 | 0 | run->runs[run->n_runs] = vl; |
328 | 0 | run->n_runs++; |
329 | 0 | *previousrl = vl; |
330 | 0 | } else { |
331 | 0 | uint32_t newend = vl.value + vl.length + UINT32_C(1); |
332 | 0 | if (newend > previousend) { // we merge |
333 | 0 | previousrl->length = (uint16_t)(newend - 1 - previousrl->value); |
334 | 0 | run->runs[run->n_runs - 1] = *previousrl; |
335 | 0 | } |
336 | 0 | } |
337 | 0 | } Unexecuted instantiation: roaring.c:run_container_append Unexecuted instantiation: roaring64.c:run_container_append Unexecuted instantiation: roaring_array.c:run_container_append Unexecuted instantiation: containers.c:run_container_append Unexecuted instantiation: convert.c:run_container_append Unexecuted instantiation: mixed_intersection.c:run_container_append Unexecuted instantiation: mixed_union.c:run_container_append Unexecuted instantiation: mixed_equal.c:run_container_append Unexecuted instantiation: mixed_subset.c:run_container_append Unexecuted instantiation: mixed_negation.c:run_container_append Unexecuted instantiation: mixed_xor.c:run_container_append Unexecuted instantiation: mixed_andnot.c:run_container_append Unexecuted instantiation: run.c:run_container_append |
338 | | |
339 | | /** |
340 | | * Like run_container_append but it is assumed that the content of run is empty. |
341 | | */ |
342 | | static inline rle16_t run_container_append_first(run_container_t *run, |
343 | 0 | rle16_t vl) { |
344 | 0 | run->runs[run->n_runs] = vl; |
345 | 0 | run->n_runs++; |
346 | 0 | return vl; |
347 | 0 | } Unexecuted instantiation: roaring.c:run_container_append_first Unexecuted instantiation: roaring64.c:run_container_append_first Unexecuted instantiation: roaring_array.c:run_container_append_first Unexecuted instantiation: containers.c:run_container_append_first Unexecuted instantiation: convert.c:run_container_append_first Unexecuted instantiation: mixed_intersection.c:run_container_append_first Unexecuted instantiation: mixed_union.c:run_container_append_first Unexecuted instantiation: mixed_equal.c:run_container_append_first Unexecuted instantiation: mixed_subset.c:run_container_append_first Unexecuted instantiation: mixed_negation.c:run_container_append_first Unexecuted instantiation: mixed_xor.c:run_container_append_first Unexecuted instantiation: mixed_andnot.c:run_container_append_first Unexecuted instantiation: run.c:run_container_append_first |
348 | | |
349 | | /** |
350 | | * append a single value given by val to the run container, possibly merging. |
351 | | * It is assumed that the value would be inserted at the end of the container, |
352 | | * no check is made. |
353 | | * It is assumed that the run container has the necessary capacity: caller is |
354 | | * responsible for checking memory capacity. |
355 | | * |
356 | | * This is not a safe function, it is meant for performance: use with care. |
357 | | */ |
358 | | static inline void run_container_append_value(run_container_t *run, |
359 | | uint16_t val, |
360 | 0 | rle16_t *previousrl) { |
361 | 0 | const uint32_t previousend = previousrl->value + previousrl->length; |
362 | 0 | if (val > previousend + 1) { // we add a new one |
363 | 0 | *previousrl = CROARING_MAKE_RLE16(val, 0); |
364 | 0 | run->runs[run->n_runs] = *previousrl; |
365 | 0 | run->n_runs++; |
366 | 0 | } else if (val == previousend + 1) { // we merge |
367 | 0 | previousrl->length++; |
368 | 0 | run->runs[run->n_runs - 1] = *previousrl; |
369 | 0 | } |
370 | 0 | } Unexecuted instantiation: roaring.c:run_container_append_value Unexecuted instantiation: roaring64.c:run_container_append_value Unexecuted instantiation: roaring_array.c:run_container_append_value Unexecuted instantiation: containers.c:run_container_append_value Unexecuted instantiation: convert.c:run_container_append_value Unexecuted instantiation: mixed_intersection.c:run_container_append_value Unexecuted instantiation: mixed_union.c:run_container_append_value Unexecuted instantiation: mixed_equal.c:run_container_append_value Unexecuted instantiation: mixed_subset.c:run_container_append_value Unexecuted instantiation: mixed_negation.c:run_container_append_value Unexecuted instantiation: mixed_xor.c:run_container_append_value Unexecuted instantiation: mixed_andnot.c:run_container_append_value Unexecuted instantiation: run.c:run_container_append_value |
371 | | |
372 | | /** |
373 | | * Like run_container_append_value but it is assumed that the content of run is |
374 | | * empty. |
375 | | */ |
376 | | static inline rle16_t run_container_append_value_first(run_container_t *run, |
377 | 0 | uint16_t val) { |
378 | 0 | rle16_t newrle = CROARING_MAKE_RLE16(val, 0); |
379 | 0 | run->runs[run->n_runs] = newrle; |
380 | 0 | run->n_runs++; |
381 | 0 | return newrle; |
382 | 0 | } Unexecuted instantiation: roaring.c:run_container_append_value_first Unexecuted instantiation: roaring64.c:run_container_append_value_first Unexecuted instantiation: roaring_array.c:run_container_append_value_first Unexecuted instantiation: containers.c:run_container_append_value_first Unexecuted instantiation: convert.c:run_container_append_value_first Unexecuted instantiation: mixed_intersection.c:run_container_append_value_first Unexecuted instantiation: mixed_union.c:run_container_append_value_first Unexecuted instantiation: mixed_equal.c:run_container_append_value_first Unexecuted instantiation: mixed_subset.c:run_container_append_value_first Unexecuted instantiation: mixed_negation.c:run_container_append_value_first Unexecuted instantiation: mixed_xor.c:run_container_append_value_first Unexecuted instantiation: mixed_andnot.c:run_container_append_value_first Unexecuted instantiation: run.c:run_container_append_value_first |
383 | | |
384 | | /* Check whether the container spans the whole chunk (cardinality = 1<<16). |
385 | | * This check can be done in constant time (inexpensive). */ |
386 | 0 | static inline bool run_container_is_full(const run_container_t *run) { |
387 | 0 | rle16_t vl = run->runs[0]; |
388 | 0 | return (run->n_runs == 1) && (vl.value == 0) && (vl.length == 0xFFFF); |
389 | 0 | } Unexecuted instantiation: roaring.c:run_container_is_full Unexecuted instantiation: roaring64.c:run_container_is_full Unexecuted instantiation: roaring_array.c:run_container_is_full Unexecuted instantiation: containers.c:run_container_is_full Unexecuted instantiation: convert.c:run_container_is_full Unexecuted instantiation: mixed_intersection.c:run_container_is_full Unexecuted instantiation: mixed_union.c:run_container_is_full Unexecuted instantiation: mixed_equal.c:run_container_is_full Unexecuted instantiation: mixed_subset.c:run_container_is_full Unexecuted instantiation: mixed_negation.c:run_container_is_full Unexecuted instantiation: mixed_xor.c:run_container_is_full Unexecuted instantiation: mixed_andnot.c:run_container_is_full Unexecuted instantiation: run.c:run_container_is_full |
390 | | |
391 | | /* Compute the union of `src_1' and `src_2' and write the result to `dst' |
392 | | * It is assumed that `dst' is distinct from both `src_1' and `src_2'. */ |
393 | | void run_container_union(const run_container_t *src_1, |
394 | | const run_container_t *src_2, run_container_t *dst); |
395 | | |
396 | | /* Compute the union of `src_1' and `src_2' and write the result to `src_1' */ |
397 | | void run_container_union_inplace(run_container_t *src_1, |
398 | | const run_container_t *src_2); |
399 | | |
400 | | /* Compute the intersection of src_1 and src_2 and write the result to |
401 | | * dst. It is assumed that dst is distinct from both src_1 and src_2. */ |
402 | | void run_container_intersection(const run_container_t *src_1, |
403 | | const run_container_t *src_2, |
404 | | run_container_t *dst); |
405 | | |
406 | | /* Compute the size of the intersection of src_1 and src_2 . */ |
407 | | int run_container_intersection_cardinality(const run_container_t *src_1, |
408 | | const run_container_t *src_2); |
409 | | |
410 | | /* Check whether src_1 and src_2 intersect. */ |
411 | | bool run_container_intersect(const run_container_t *src_1, |
412 | | const run_container_t *src_2); |
413 | | |
414 | | /* Compute the symmetric difference of `src_1' and `src_2' and write the result |
415 | | * to `dst' |
416 | | * It is assumed that `dst' is distinct from both `src_1' and `src_2'. */ |
417 | | void run_container_xor(const run_container_t *src_1, |
418 | | const run_container_t *src_2, run_container_t *dst); |
419 | | |
420 | | /* |
421 | | * Write out the 16-bit integers contained in this container as a list of 32-bit |
422 | | * integers using base |
423 | | * as the starting value (it might be expected that base has zeros in its 16 |
424 | | * least significant bits). |
425 | | * The function returns the number of values written. |
426 | | * The caller is responsible for allocating enough memory in out. |
427 | | */ |
428 | | int run_container_to_uint32_array(void *vout, const run_container_t *cont, |
429 | | uint32_t base); |
430 | | |
431 | | /* |
432 | | * Print this container using printf (useful for debugging). |
433 | | */ |
434 | | void run_container_printf(const run_container_t *v); |
435 | | |
436 | | /* |
437 | | * Print this container using printf as a comma-separated list of 32-bit |
438 | | * integers starting at base. |
439 | | */ |
440 | | void run_container_printf_as_uint32_array(const run_container_t *v, |
441 | | uint32_t base); |
442 | | |
443 | | bool run_container_validate(const run_container_t *run, const char **reason); |
444 | | |
445 | | /** |
446 | | * Return the serialized size in bytes of a container having "num_runs" runs. |
447 | | */ |
448 | 44.9k | static inline int32_t run_container_serialized_size_in_bytes(int32_t num_runs) { |
449 | 44.9k | return sizeof(uint16_t) + |
450 | 44.9k | sizeof(rle16_t) * num_runs; // each run requires 2 2-byte entries. |
451 | 44.9k | } Unexecuted instantiation: roaring.c:run_container_serialized_size_in_bytes Unexecuted instantiation: roaring64.c:run_container_serialized_size_in_bytes Unexecuted instantiation: roaring_array.c:run_container_serialized_size_in_bytes Unexecuted instantiation: containers.c:run_container_serialized_size_in_bytes Unexecuted instantiation: convert.c:run_container_serialized_size_in_bytes Unexecuted instantiation: mixed_intersection.c:run_container_serialized_size_in_bytes Unexecuted instantiation: mixed_union.c:run_container_serialized_size_in_bytes Unexecuted instantiation: mixed_equal.c:run_container_serialized_size_in_bytes Unexecuted instantiation: mixed_subset.c:run_container_serialized_size_in_bytes Unexecuted instantiation: mixed_negation.c:run_container_serialized_size_in_bytes Unexecuted instantiation: mixed_xor.c:run_container_serialized_size_in_bytes Unexecuted instantiation: mixed_andnot.c:run_container_serialized_size_in_bytes run.c:run_container_serialized_size_in_bytes Line | Count | Source | 448 | 44.9k | static inline int32_t run_container_serialized_size_in_bytes(int32_t num_runs) { | 449 | 44.9k | return sizeof(uint16_t) + | 450 | 44.9k | sizeof(rle16_t) * num_runs; // each run requires 2 2-byte entries. | 451 | 44.9k | } |
|
452 | | |
453 | | bool run_container_iterate(const run_container_t *cont, uint32_t base, |
454 | | roaring_iterator iterator, void *ptr); |
455 | | bool run_container_iterate64(const run_container_t *cont, uint32_t base, |
456 | | roaring_iterator64 iterator, uint64_t high_bits, |
457 | | void *ptr); |
458 | | |
459 | | /** |
460 | | * Writes the underlying array to buf, outputs how many bytes were written. |
461 | | * This is meant to be byte-by-byte compatible with the Java and Go versions of |
462 | | * Roaring. |
463 | | * The number of bytes written should be run_container_size_in_bytes(container). |
464 | | */ |
465 | | int32_t run_container_write(const run_container_t *container, char *buf); |
466 | | |
467 | | /** |
468 | | * Reads the instance from buf, outputs how many bytes were read. |
469 | | * This is meant to be byte-by-byte compatible with the Java and Go versions of |
470 | | * Roaring. |
471 | | * The number of bytes read should be bitset_container_size_in_bytes(container). |
472 | | * The cardinality parameter is provided for consistency with other containers, |
473 | | * but |
474 | | * it might be effectively ignored.. |
475 | | */ |
476 | | int32_t run_container_read(int32_t cardinality, run_container_t *container, |
477 | | const char *buf); |
478 | | |
479 | | /** |
480 | | * Return the serialized size in bytes of a container (see run_container_write). |
481 | | * This is meant to be compatible with the Java and Go versions of Roaring. |
482 | | */ |
483 | | ALLOW_UNALIGNED |
484 | | static inline int32_t run_container_size_in_bytes( |
485 | 44.9k | const run_container_t *container) { |
486 | 44.9k | return run_container_serialized_size_in_bytes(container->n_runs); |
487 | 44.9k | } Unexecuted instantiation: roaring.c:run_container_size_in_bytes Unexecuted instantiation: roaring64.c:run_container_size_in_bytes Unexecuted instantiation: roaring_array.c:run_container_size_in_bytes Unexecuted instantiation: containers.c:run_container_size_in_bytes Unexecuted instantiation: convert.c:run_container_size_in_bytes Unexecuted instantiation: mixed_intersection.c:run_container_size_in_bytes Unexecuted instantiation: mixed_union.c:run_container_size_in_bytes Unexecuted instantiation: mixed_equal.c:run_container_size_in_bytes Unexecuted instantiation: mixed_subset.c:run_container_size_in_bytes Unexecuted instantiation: mixed_negation.c:run_container_size_in_bytes Unexecuted instantiation: mixed_xor.c:run_container_size_in_bytes Unexecuted instantiation: mixed_andnot.c:run_container_size_in_bytes run.c:run_container_size_in_bytes Line | Count | Source | 485 | 44.9k | const run_container_t *container) { | 486 | 44.9k | return run_container_serialized_size_in_bytes(container->n_runs); | 487 | 44.9k | } |
|
488 | | |
489 | | /** |
490 | | * Return true if the two containers have the same content. |
491 | | */ |
492 | | ALLOW_UNALIGNED |
493 | | static inline bool run_container_equals(const run_container_t *container1, |
494 | 0 | const run_container_t *container2) { |
495 | 0 | if (container1->n_runs != container2->n_runs) { |
496 | 0 | return false; |
497 | 0 | } |
498 | 0 | return memequals(container1->runs, container2->runs, |
499 | 0 | container1->n_runs * sizeof(rle16_t)); |
500 | 0 | } Unexecuted instantiation: roaring.c:run_container_equals Unexecuted instantiation: roaring64.c:run_container_equals Unexecuted instantiation: roaring_array.c:run_container_equals Unexecuted instantiation: containers.c:run_container_equals Unexecuted instantiation: convert.c:run_container_equals Unexecuted instantiation: mixed_intersection.c:run_container_equals Unexecuted instantiation: mixed_union.c:run_container_equals Unexecuted instantiation: mixed_equal.c:run_container_equals Unexecuted instantiation: mixed_subset.c:run_container_equals Unexecuted instantiation: mixed_negation.c:run_container_equals Unexecuted instantiation: mixed_xor.c:run_container_equals Unexecuted instantiation: mixed_andnot.c:run_container_equals Unexecuted instantiation: run.c:run_container_equals |
501 | | |
502 | | /** |
503 | | * Return true if container1 is a subset of container2. |
504 | | */ |
505 | | bool run_container_is_subset(const run_container_t *container1, |
506 | | const run_container_t *container2); |
507 | | |
508 | | /** |
509 | | * Used in a start-finish scan that appends segments, for XOR and NOT |
510 | | */ |
511 | | |
512 | | void run_container_smart_append_exclusive(run_container_t *src, |
513 | | const uint16_t start, |
514 | | const uint16_t length); |
515 | | |
516 | | /** |
517 | | * The new container consists of a single run [start,stop). |
518 | | * It is required that stop>start, the caller is responsability for this check. |
519 | | * It is required that stop <= (1<<16), the caller is responsability for this |
520 | | * check. The cardinality of the created container is stop - start. Returns NULL |
521 | | * on failure |
522 | | */ |
523 | | static inline run_container_t *run_container_create_range(uint32_t start, |
524 | 0 | uint32_t stop) { |
525 | 0 | run_container_t *rc = run_container_create_given_capacity(1); |
526 | 0 | if (rc) { |
527 | 0 | rle16_t r; |
528 | 0 | r.value = (uint16_t)start; |
529 | 0 | r.length = (uint16_t)(stop - start - 1); |
530 | 0 | run_container_append_first(rc, r); |
531 | 0 | } |
532 | 0 | return rc; |
533 | 0 | } Unexecuted instantiation: roaring.c:run_container_create_range Unexecuted instantiation: roaring64.c:run_container_create_range Unexecuted instantiation: roaring_array.c:run_container_create_range Unexecuted instantiation: containers.c:run_container_create_range Unexecuted instantiation: convert.c:run_container_create_range Unexecuted instantiation: mixed_intersection.c:run_container_create_range Unexecuted instantiation: mixed_union.c:run_container_create_range Unexecuted instantiation: mixed_equal.c:run_container_create_range Unexecuted instantiation: mixed_subset.c:run_container_create_range Unexecuted instantiation: mixed_negation.c:run_container_create_range Unexecuted instantiation: mixed_xor.c:run_container_create_range Unexecuted instantiation: mixed_andnot.c:run_container_create_range Unexecuted instantiation: run.c:run_container_create_range |
534 | | |
535 | | /** |
536 | | * If the element of given rank is in this container, supposing that the first |
537 | | * element has rank start_rank, then the function returns true and sets element |
538 | | * accordingly. |
539 | | * Otherwise, it returns false and update start_rank. |
540 | | */ |
541 | | bool run_container_select(const run_container_t *container, |
542 | | uint32_t *start_rank, uint32_t rank, |
543 | | uint32_t *element); |
544 | | |
545 | | /* Compute the difference of src_1 and src_2 and write the result to |
546 | | * dst. It is assumed that dst is distinct from both src_1 and src_2. */ |
547 | | |
548 | | void run_container_andnot(const run_container_t *src_1, |
549 | | const run_container_t *src_2, run_container_t *dst); |
550 | | |
551 | | void run_container_offset(const run_container_t *c, container_t **loc, |
552 | | container_t **hic, uint16_t offset); |
553 | | |
554 | | /* Returns the smallest value (assumes not empty) */ |
555 | 0 | inline uint16_t run_container_minimum(const run_container_t *run) { |
556 | 0 | if (run->n_runs == 0) return 0; |
557 | 0 | return run->runs[0].value; |
558 | 0 | } |
559 | | |
560 | | /* Returns the largest value (assumes not empty) */ |
561 | 0 | inline uint16_t run_container_maximum(const run_container_t *run) { |
562 | 0 | if (run->n_runs == 0) return 0; |
563 | 0 | return run->runs[run->n_runs - 1].value + run->runs[run->n_runs - 1].length; |
564 | 0 | } |
565 | | |
566 | | /* Returns the number of values equal or smaller than x */ |
567 | | int run_container_rank(const run_container_t *arr, uint16_t x); |
568 | | |
569 | | /* bulk version of run_container_rank(); return number of consumed elements */ |
570 | | uint32_t run_container_rank_many(const run_container_t *arr, |
571 | | uint64_t start_rank, const uint32_t *begin, |
572 | | const uint32_t *end, uint64_t *ans); |
573 | | |
574 | | /* Returns the index of x, if not exsist return -1 */ |
575 | | int run_container_get_index(const run_container_t *arr, uint16_t x); |
576 | | |
577 | | /* Returns the index of the first run containing a value at least as large as x, |
578 | | * or -1 */ |
579 | | inline int run_container_index_equalorlarger(const run_container_t *arr, |
580 | 0 | uint16_t x) { |
581 | 0 | int32_t index = interleavedBinarySearch(arr->runs, arr->n_runs, x); |
582 | 0 | if (index >= 0) return index; |
583 | 0 | index = -index - 2; // points to preceding run, possibly -1 |
584 | 0 | if (index != -1) { // possible match |
585 | 0 | int32_t offset = x - arr->runs[index].value; |
586 | 0 | int32_t le = arr->runs[index].length; |
587 | 0 | if (offset <= le) return index; |
588 | 0 | } |
589 | 0 | index += 1; |
590 | 0 | if (index < arr->n_runs) { |
591 | 0 | return index; |
592 | 0 | } |
593 | 0 | return -1; |
594 | 0 | } |
595 | | |
596 | | /* |
597 | | * Add all values in range [min, max] using hint. |
598 | | */ |
599 | | static inline void run_container_add_range_nruns(run_container_t *run, |
600 | | uint32_t min, uint32_t max, |
601 | | int32_t nruns_less, |
602 | 0 | int32_t nruns_greater) { |
603 | 0 | int32_t nruns_common = run->n_runs - nruns_less - nruns_greater; |
604 | 0 | if (nruns_common == 0) { |
605 | 0 | makeRoomAtIndex(run, (uint16_t)nruns_less); |
606 | 0 | run->runs[nruns_less].value = (uint16_t)min; |
607 | 0 | run->runs[nruns_less].length = (uint16_t)(max - min); |
608 | 0 | } else { |
609 | 0 | uint32_t common_min = run->runs[nruns_less].value; |
610 | 0 | uint32_t common_max = run->runs[nruns_less + nruns_common - 1].value + |
611 | 0 | run->runs[nruns_less + nruns_common - 1].length; |
612 | 0 | uint32_t result_min = (common_min < min) ? common_min : min; |
613 | 0 | uint32_t result_max = (common_max > max) ? common_max : max; |
614 | |
|
615 | 0 | run->runs[nruns_less].value = (uint16_t)result_min; |
616 | 0 | run->runs[nruns_less].length = (uint16_t)(result_max - result_min); |
617 | |
|
618 | 0 | memmove(&(run->runs[nruns_less + 1]), |
619 | 0 | &(run->runs[run->n_runs - nruns_greater]), |
620 | 0 | nruns_greater * sizeof(rle16_t)); |
621 | 0 | run->n_runs = nruns_less + 1 + nruns_greater; |
622 | 0 | } |
623 | 0 | } Unexecuted instantiation: roaring.c:run_container_add_range_nruns Unexecuted instantiation: roaring64.c:run_container_add_range_nruns Unexecuted instantiation: roaring_array.c:run_container_add_range_nruns Unexecuted instantiation: containers.c:run_container_add_range_nruns Unexecuted instantiation: convert.c:run_container_add_range_nruns Unexecuted instantiation: mixed_intersection.c:run_container_add_range_nruns Unexecuted instantiation: mixed_union.c:run_container_add_range_nruns Unexecuted instantiation: mixed_equal.c:run_container_add_range_nruns Unexecuted instantiation: mixed_subset.c:run_container_add_range_nruns Unexecuted instantiation: mixed_negation.c:run_container_add_range_nruns Unexecuted instantiation: mixed_xor.c:run_container_add_range_nruns Unexecuted instantiation: mixed_andnot.c:run_container_add_range_nruns Unexecuted instantiation: run.c:run_container_add_range_nruns |
624 | | |
625 | | /** |
626 | | * Add all values in range [min, max]. This function is currently unused |
627 | | * and left as documentation. |
628 | | */ |
629 | | /*static inline void run_container_add_range(run_container_t* run, |
630 | | uint32_t min, uint32_t max) { |
631 | | int32_t nruns_greater = rle16_count_greater(run->runs, run->n_runs, max); |
632 | | int32_t nruns_less = rle16_count_less(run->runs, run->n_runs - |
633 | | nruns_greater, min); run_container_add_range_nruns(run, min, max, nruns_less, |
634 | | nruns_greater); |
635 | | }*/ |
636 | | |
637 | | /** |
638 | | * Shifts last $count elements either left (distance < 0) or right (distance > |
639 | | * 0) |
640 | | */ |
641 | | static inline void run_container_shift_tail(run_container_t *run, int32_t count, |
642 | 0 | int32_t distance) { |
643 | 0 | if (distance > 0) { |
644 | 0 | if (run->capacity < count + distance) { |
645 | 0 | run_container_grow(run, count + distance, true); |
646 | 0 | } |
647 | 0 | } |
648 | 0 | int32_t srcpos = run->n_runs - count; |
649 | 0 | int32_t dstpos = srcpos + distance; |
650 | 0 | memmove(&(run->runs[dstpos]), &(run->runs[srcpos]), |
651 | 0 | sizeof(rle16_t) * count); |
652 | 0 | run->n_runs += distance; |
653 | 0 | } Unexecuted instantiation: roaring.c:run_container_shift_tail Unexecuted instantiation: roaring64.c:run_container_shift_tail Unexecuted instantiation: roaring_array.c:run_container_shift_tail Unexecuted instantiation: containers.c:run_container_shift_tail Unexecuted instantiation: convert.c:run_container_shift_tail Unexecuted instantiation: mixed_intersection.c:run_container_shift_tail Unexecuted instantiation: mixed_union.c:run_container_shift_tail Unexecuted instantiation: mixed_equal.c:run_container_shift_tail Unexecuted instantiation: mixed_subset.c:run_container_shift_tail Unexecuted instantiation: mixed_negation.c:run_container_shift_tail Unexecuted instantiation: mixed_xor.c:run_container_shift_tail Unexecuted instantiation: mixed_andnot.c:run_container_shift_tail Unexecuted instantiation: run.c:run_container_shift_tail |
654 | | |
655 | | /** |
656 | | * Remove all elements in range [min, max] |
657 | | */ |
658 | | static inline void run_container_remove_range(run_container_t *run, |
659 | 0 | uint32_t min, uint32_t max) { |
660 | 0 | int32_t first = rle16_find_run(run->runs, run->n_runs, (uint16_t)min); |
661 | 0 | int32_t last = rle16_find_run(run->runs, run->n_runs, (uint16_t)max); |
662 | |
|
663 | 0 | if (first >= 0 && min > run->runs[first].value && |
664 | 0 | max < ((uint32_t)run->runs[first].value + |
665 | 0 | (uint32_t)run->runs[first].length)) { |
666 | | // split this run into two adjacent runs |
667 | | |
668 | | // right subinterval |
669 | 0 | makeRoomAtIndex(run, (uint16_t)(first + 1)); |
670 | 0 | run->runs[first + 1].value = (uint16_t)(max + 1); |
671 | 0 | run->runs[first + 1].length = |
672 | 0 | (uint16_t)((run->runs[first].value + run->runs[first].length) - |
673 | 0 | (max + 1)); |
674 | | |
675 | | // left subinterval |
676 | 0 | run->runs[first].length = |
677 | 0 | (uint16_t)((min - 1) - run->runs[first].value); |
678 | |
|
679 | 0 | return; |
680 | 0 | } |
681 | | |
682 | | // update left-most partial run |
683 | 0 | if (first >= 0) { |
684 | 0 | if (min > run->runs[first].value) { |
685 | 0 | run->runs[first].length = |
686 | 0 | (uint16_t)((min - 1) - run->runs[first].value); |
687 | 0 | first++; |
688 | 0 | } |
689 | 0 | } else { |
690 | 0 | first = -first - 1; |
691 | 0 | } |
692 | | |
693 | | // update right-most run |
694 | 0 | if (last >= 0) { |
695 | 0 | uint16_t run_max = run->runs[last].value + run->runs[last].length; |
696 | 0 | if (run_max > max) { |
697 | 0 | run->runs[last].value = (uint16_t)(max + 1); |
698 | 0 | run->runs[last].length = (uint16_t)(run_max - (max + 1)); |
699 | 0 | last--; |
700 | 0 | } |
701 | 0 | } else { |
702 | 0 | last = (-last - 1) - 1; |
703 | 0 | } |
704 | | |
705 | | // remove intermediate runs |
706 | 0 | if (first <= last) { |
707 | 0 | run_container_shift_tail(run, run->n_runs - (last + 1), |
708 | 0 | -(last - first + 1)); |
709 | 0 | } |
710 | 0 | } Unexecuted instantiation: roaring.c:run_container_remove_range Unexecuted instantiation: roaring64.c:run_container_remove_range Unexecuted instantiation: roaring_array.c:run_container_remove_range Unexecuted instantiation: containers.c:run_container_remove_range Unexecuted instantiation: convert.c:run_container_remove_range Unexecuted instantiation: mixed_intersection.c:run_container_remove_range Unexecuted instantiation: mixed_union.c:run_container_remove_range Unexecuted instantiation: mixed_equal.c:run_container_remove_range Unexecuted instantiation: mixed_subset.c:run_container_remove_range Unexecuted instantiation: mixed_negation.c:run_container_remove_range Unexecuted instantiation: mixed_xor.c:run_container_remove_range Unexecuted instantiation: mixed_andnot.c:run_container_remove_range Unexecuted instantiation: run.c:run_container_remove_range |
711 | | |
712 | | #ifdef __cplusplus |
713 | | } |
714 | | } |
715 | | } // extern "C" { namespace roaring { namespace internal { |
716 | | #endif |
717 | | |
718 | | #endif /* INCLUDE_CONTAINERS_RUN_H_ */ |