/src/croaring/include/roaring/containers/array.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * array.h |
3 | | * |
4 | | */ |
5 | | |
6 | | #ifndef INCLUDE_CONTAINERS_ARRAY_H_ |
7 | | #define INCLUDE_CONTAINERS_ARRAY_H_ |
8 | | |
9 | | #include <string.h> |
10 | | |
11 | | #include <roaring/portability.h> |
12 | | #include <roaring/roaring_types.h> // roaring_iterator |
13 | | #include <roaring/array_util.h> // binarySearch()/memequals() for inlining |
14 | | |
15 | | #include <roaring/containers/container_defs.h> // container_t, perfparameters |
16 | | |
17 | | #ifdef __cplusplus |
18 | | extern "C" { namespace roaring { |
19 | | |
20 | | // Note: in pure C++ code, you should avoid putting `using` in header files |
21 | | using api::roaring_iterator; |
22 | | using api::roaring_iterator64; |
23 | | |
24 | | namespace internal { |
25 | | #endif |
26 | | |
27 | | /* Containers with DEFAULT_MAX_SIZE or less integers should be arrays */ |
28 | | enum { DEFAULT_MAX_SIZE = 4096 }; |
29 | | |
30 | | /* struct array_container - sparse representation of a bitmap |
31 | | * |
32 | | * @cardinality: number of indices in `array` (and the bitmap) |
33 | | * @capacity: allocated size of `array` |
34 | | * @array: sorted list of integers |
35 | | */ |
36 | | STRUCT_CONTAINER(array_container_s) { |
37 | | int32_t cardinality; |
38 | | int32_t capacity; |
39 | | uint16_t *array; |
40 | | }; |
41 | | |
42 | | typedef struct array_container_s array_container_t; |
43 | | |
44 | 657k | #define CAST_array(c) CAST(array_container_t *, c) // safer downcast |
45 | 0 | #define const_CAST_array(c) CAST(const array_container_t *, c) |
46 | | #define movable_CAST_array(c) movable_CAST(array_container_t **, c) |
47 | | |
48 | | /* Create a new array with default. Return NULL in case of failure. See also |
49 | | * array_container_create_given_capacity. */ |
50 | | array_container_t *array_container_create(void); |
51 | | |
52 | | /* Create a new array with a specified capacity size. Return NULL in case of |
53 | | * failure. */ |
54 | | array_container_t *array_container_create_given_capacity(int32_t size); |
55 | | |
56 | | /* Create a new array containing all values in [min,max). */ |
57 | | array_container_t * array_container_create_range(uint32_t min, uint32_t max); |
58 | | |
59 | | /* |
60 | | * Shrink the capacity to the actual size, return the number of bytes saved. |
61 | | */ |
62 | | int array_container_shrink_to_fit(array_container_t *src); |
63 | | |
64 | | /* Free memory owned by `array'. */ |
65 | | void array_container_free(array_container_t *array); |
66 | | |
67 | | /* Duplicate container */ |
68 | | array_container_t *array_container_clone(const array_container_t *src); |
69 | | |
70 | | /* Get the cardinality of `array'. */ |
71 | 0 | static inline int array_container_cardinality(const array_container_t *array) { |
72 | 0 | return array->cardinality; |
73 | 0 | } Unexecuted instantiation: roaring.c:array_container_cardinality Unexecuted instantiation: roaring_array.c:array_container_cardinality Unexecuted instantiation: array.c:array_container_cardinality Unexecuted instantiation: containers.c:array_container_cardinality Unexecuted instantiation: convert.c:array_container_cardinality Unexecuted instantiation: mixed_intersection.c:array_container_cardinality Unexecuted instantiation: mixed_union.c:array_container_cardinality Unexecuted instantiation: mixed_equal.c:array_container_cardinality Unexecuted instantiation: mixed_subset.c:array_container_cardinality Unexecuted instantiation: mixed_negation.c:array_container_cardinality Unexecuted instantiation: mixed_xor.c:array_container_cardinality Unexecuted instantiation: mixed_andnot.c:array_container_cardinality |
74 | | |
75 | | static inline bool array_container_nonzero_cardinality( |
76 | 0 | const array_container_t *array) { |
77 | 0 | return array->cardinality > 0; |
78 | 0 | } Unexecuted instantiation: roaring.c:array_container_nonzero_cardinality Unexecuted instantiation: roaring_array.c:array_container_nonzero_cardinality Unexecuted instantiation: array.c:array_container_nonzero_cardinality Unexecuted instantiation: containers.c:array_container_nonzero_cardinality Unexecuted instantiation: convert.c:array_container_nonzero_cardinality Unexecuted instantiation: mixed_intersection.c:array_container_nonzero_cardinality Unexecuted instantiation: mixed_union.c:array_container_nonzero_cardinality Unexecuted instantiation: mixed_equal.c:array_container_nonzero_cardinality Unexecuted instantiation: mixed_subset.c:array_container_nonzero_cardinality Unexecuted instantiation: mixed_negation.c:array_container_nonzero_cardinality Unexecuted instantiation: mixed_xor.c:array_container_nonzero_cardinality Unexecuted instantiation: mixed_andnot.c:array_container_nonzero_cardinality |
79 | | |
80 | | /* Copy one container into another. We assume that they are distinct. */ |
81 | | void array_container_copy(const array_container_t *src, array_container_t *dst); |
82 | | |
83 | | /* Add all the values in [min,max) (included) at a distance k*step from min. |
84 | | The container must have a size less or equal to DEFAULT_MAX_SIZE after this |
85 | | addition. */ |
86 | | void array_container_add_from_range(array_container_t *arr, uint32_t min, |
87 | | uint32_t max, uint16_t step); |
88 | | |
89 | | |
90 | 0 | static inline bool array_container_empty(const array_container_t *array) { |
91 | 0 | return array->cardinality == 0; |
92 | 0 | } Unexecuted instantiation: roaring.c:array_container_empty Unexecuted instantiation: roaring_array.c:array_container_empty Unexecuted instantiation: array.c:array_container_empty Unexecuted instantiation: containers.c:array_container_empty Unexecuted instantiation: convert.c:array_container_empty Unexecuted instantiation: mixed_intersection.c:array_container_empty Unexecuted instantiation: mixed_union.c:array_container_empty Unexecuted instantiation: mixed_equal.c:array_container_empty Unexecuted instantiation: mixed_subset.c:array_container_empty Unexecuted instantiation: mixed_negation.c:array_container_empty Unexecuted instantiation: mixed_xor.c:array_container_empty Unexecuted instantiation: mixed_andnot.c:array_container_empty |
93 | | |
94 | | /* check whether the cardinality is equal to the capacity (this does not mean |
95 | | * that it contains 1<<16 elements) */ |
96 | 0 | static inline bool array_container_full(const array_container_t *array) { |
97 | 0 | return array->cardinality == array->capacity; |
98 | 0 | } Unexecuted instantiation: roaring.c:array_container_full Unexecuted instantiation: roaring_array.c:array_container_full Unexecuted instantiation: array.c:array_container_full Unexecuted instantiation: containers.c:array_container_full Unexecuted instantiation: convert.c:array_container_full Unexecuted instantiation: mixed_intersection.c:array_container_full Unexecuted instantiation: mixed_union.c:array_container_full Unexecuted instantiation: mixed_equal.c:array_container_full Unexecuted instantiation: mixed_subset.c:array_container_full Unexecuted instantiation: mixed_negation.c:array_container_full Unexecuted instantiation: mixed_xor.c:array_container_full Unexecuted instantiation: mixed_andnot.c:array_container_full |
99 | | |
100 | | |
101 | | /* Compute the union of `src_1' and `src_2' and write the result to `dst' |
102 | | * It is assumed that `dst' is distinct from both `src_1' and `src_2'. */ |
103 | | void array_container_union(const array_container_t *src_1, |
104 | | const array_container_t *src_2, |
105 | | array_container_t *dst); |
106 | | |
107 | | /* symmetric difference, see array_container_union */ |
108 | | void array_container_xor(const array_container_t *array_1, |
109 | | const array_container_t *array_2, |
110 | | array_container_t *out); |
111 | | |
112 | | /* Computes the intersection of src_1 and src_2 and write the result to |
113 | | * dst. It is assumed that dst is distinct from both src_1 and src_2. */ |
114 | | void array_container_intersection(const array_container_t *src_1, |
115 | | const array_container_t *src_2, |
116 | | array_container_t *dst); |
117 | | |
118 | | /* Check whether src_1 and src_2 intersect. */ |
119 | | bool array_container_intersect(const array_container_t *src_1, |
120 | | const array_container_t *src_2); |
121 | | |
122 | | |
123 | | /* computers the size of the intersection between two arrays. |
124 | | */ |
125 | | int array_container_intersection_cardinality(const array_container_t *src_1, |
126 | | const array_container_t *src_2); |
127 | | |
128 | | /* computes the intersection of array1 and array2 and write the result to |
129 | | * array1. |
130 | | * */ |
131 | | void array_container_intersection_inplace(array_container_t *src_1, |
132 | | const array_container_t *src_2); |
133 | | |
134 | | /* |
135 | | * Write out the 16-bit integers contained in this container as a list of 32-bit |
136 | | * integers using base |
137 | | * as the starting value (it might be expected that base has zeros in its 16 |
138 | | * least significant bits). |
139 | | * The function returns the number of values written. |
140 | | * The caller is responsible for allocating enough memory in out. |
141 | | */ |
142 | | int array_container_to_uint32_array(void *vout, const array_container_t *cont, |
143 | | uint32_t base); |
144 | | |
145 | | /* Compute the number of runs */ |
146 | | int32_t array_container_number_of_runs(const array_container_t *ac); |
147 | | |
148 | | /* |
149 | | * Print this container using printf (useful for debugging). |
150 | | */ |
151 | | void array_container_printf(const array_container_t *v); |
152 | | |
153 | | /* |
154 | | * Print this container using printf as a comma-separated list of 32-bit |
155 | | * integers starting at base. |
156 | | */ |
157 | | void array_container_printf_as_uint32_array(const array_container_t *v, |
158 | | uint32_t base); |
159 | | |
160 | | /** |
161 | | * Return the serialized size in bytes of a container having cardinality "card". |
162 | | */ |
163 | 0 | static inline int32_t array_container_serialized_size_in_bytes(int32_t card) { |
164 | 0 | return card * 2 + 2; |
165 | 0 | } Unexecuted instantiation: roaring.c:array_container_serialized_size_in_bytes Unexecuted instantiation: roaring_array.c:array_container_serialized_size_in_bytes Unexecuted instantiation: array.c:array_container_serialized_size_in_bytes Unexecuted instantiation: containers.c:array_container_serialized_size_in_bytes Unexecuted instantiation: convert.c:array_container_serialized_size_in_bytes Unexecuted instantiation: mixed_intersection.c:array_container_serialized_size_in_bytes Unexecuted instantiation: mixed_union.c:array_container_serialized_size_in_bytes Unexecuted instantiation: mixed_equal.c:array_container_serialized_size_in_bytes Unexecuted instantiation: mixed_subset.c:array_container_serialized_size_in_bytes Unexecuted instantiation: mixed_negation.c:array_container_serialized_size_in_bytes Unexecuted instantiation: mixed_xor.c:array_container_serialized_size_in_bytes Unexecuted instantiation: mixed_andnot.c:array_container_serialized_size_in_bytes |
166 | | |
167 | | /** |
168 | | * Increase capacity to at least min. |
169 | | * Whether the existing data needs to be copied over depends on the "preserve" |
170 | | * parameter. If preserve is false, then the new content will be uninitialized, |
171 | | * otherwise the old content is copied. |
172 | | */ |
173 | | void array_container_grow(array_container_t *container, int32_t min, |
174 | | bool preserve); |
175 | | |
176 | | bool array_container_iterate(const array_container_t *cont, uint32_t base, |
177 | | roaring_iterator iterator, void *ptr); |
178 | | bool array_container_iterate64(const array_container_t *cont, uint32_t base, |
179 | | roaring_iterator64 iterator, uint64_t high_bits, |
180 | | void *ptr); |
181 | | |
182 | | /** |
183 | | * Writes the underlying array to buf, outputs how many bytes were written. |
184 | | * This is meant to be byte-by-byte compatible with the Java and Go versions of |
185 | | * Roaring. |
186 | | * The number of bytes written should be |
187 | | * array_container_size_in_bytes(container). |
188 | | * |
189 | | */ |
190 | | int32_t array_container_write(const array_container_t *container, char *buf); |
191 | | /** |
192 | | * Reads the instance from buf, outputs how many bytes were read. |
193 | | * This is meant to be byte-by-byte compatible with the Java and Go versions of |
194 | | * Roaring. |
195 | | * The number of bytes read should be array_container_size_in_bytes(container). |
196 | | * You need to provide the (known) cardinality. |
197 | | */ |
198 | | int32_t array_container_read(int32_t cardinality, array_container_t *container, |
199 | | const char *buf); |
200 | | |
201 | | /** |
202 | | * Return the serialized size in bytes of a container (see |
203 | | * bitset_container_write) |
204 | | * This is meant to be compatible with the Java and Go versions of Roaring and |
205 | | * assumes |
206 | | * that the cardinality of the container is already known. |
207 | | * |
208 | | */ |
209 | | static inline int32_t array_container_size_in_bytes( |
210 | 657k | const array_container_t *container) { |
211 | 657k | return container->cardinality * sizeof(uint16_t); |
212 | 657k | } Unexecuted instantiation: roaring.c:array_container_size_in_bytes Unexecuted instantiation: roaring_array.c:array_container_size_in_bytes array.c:array_container_size_in_bytes Line | Count | Source | 210 | 657k | const array_container_t *container) { | 211 | 657k | return container->cardinality * sizeof(uint16_t); | 212 | 657k | } |
Unexecuted instantiation: containers.c:array_container_size_in_bytes Unexecuted instantiation: convert.c:array_container_size_in_bytes Unexecuted instantiation: mixed_intersection.c:array_container_size_in_bytes Unexecuted instantiation: mixed_union.c:array_container_size_in_bytes Unexecuted instantiation: mixed_equal.c:array_container_size_in_bytes Unexecuted instantiation: mixed_subset.c:array_container_size_in_bytes Unexecuted instantiation: mixed_negation.c:array_container_size_in_bytes Unexecuted instantiation: mixed_xor.c:array_container_size_in_bytes Unexecuted instantiation: mixed_andnot.c:array_container_size_in_bytes |
213 | | |
214 | | /** |
215 | | * Return true if the two arrays have the same content. |
216 | | */ |
217 | | static inline bool array_container_equals( |
218 | | const array_container_t *container1, |
219 | 0 | const array_container_t *container2) { |
220 | |
|
221 | 0 | if (container1->cardinality != container2->cardinality) { |
222 | 0 | return false; |
223 | 0 | } |
224 | 0 | return memequals(container1->array, container2->array, container1->cardinality*2); |
225 | 0 | } Unexecuted instantiation: roaring.c:array_container_equals Unexecuted instantiation: roaring_array.c:array_container_equals Unexecuted instantiation: array.c:array_container_equals Unexecuted instantiation: containers.c:array_container_equals Unexecuted instantiation: convert.c:array_container_equals Unexecuted instantiation: mixed_intersection.c:array_container_equals Unexecuted instantiation: mixed_union.c:array_container_equals Unexecuted instantiation: mixed_equal.c:array_container_equals Unexecuted instantiation: mixed_subset.c:array_container_equals Unexecuted instantiation: mixed_negation.c:array_container_equals Unexecuted instantiation: mixed_xor.c:array_container_equals Unexecuted instantiation: mixed_andnot.c:array_container_equals |
226 | | |
227 | | /** |
228 | | * Return true if container1 is a subset of container2. |
229 | | */ |
230 | | bool array_container_is_subset(const array_container_t *container1, |
231 | | const array_container_t *container2); |
232 | | |
233 | | /** |
234 | | * If the element of given rank is in this container, supposing that the first |
235 | | * element has rank start_rank, then the function returns true and sets element |
236 | | * accordingly. |
237 | | * Otherwise, it returns false and update start_rank. |
238 | | */ |
239 | | static inline bool array_container_select(const array_container_t *container, |
240 | | uint32_t *start_rank, uint32_t rank, |
241 | 0 | uint32_t *element) { |
242 | 0 | int card = array_container_cardinality(container); |
243 | 0 | if (*start_rank + card <= rank) { |
244 | 0 | *start_rank += card; |
245 | 0 | return false; |
246 | 0 | } else { |
247 | 0 | *element = container->array[rank - *start_rank]; |
248 | 0 | return true; |
249 | 0 | } |
250 | 0 | } Unexecuted instantiation: roaring.c:array_container_select Unexecuted instantiation: roaring_array.c:array_container_select Unexecuted instantiation: array.c:array_container_select Unexecuted instantiation: containers.c:array_container_select Unexecuted instantiation: convert.c:array_container_select Unexecuted instantiation: mixed_intersection.c:array_container_select Unexecuted instantiation: mixed_union.c:array_container_select Unexecuted instantiation: mixed_equal.c:array_container_select Unexecuted instantiation: mixed_subset.c:array_container_select Unexecuted instantiation: mixed_negation.c:array_container_select Unexecuted instantiation: mixed_xor.c:array_container_select Unexecuted instantiation: mixed_andnot.c:array_container_select |
251 | | |
252 | | /* Computes the difference of array1 and array2 and write the result |
253 | | * to array out. |
254 | | * Array out does not need to be distinct from array_1 |
255 | | */ |
256 | | void array_container_andnot(const array_container_t *array_1, |
257 | | const array_container_t *array_2, |
258 | | array_container_t *out); |
259 | | |
260 | | /* Append x to the set. Assumes that the value is larger than any preceding |
261 | | * values. */ |
262 | | static inline void array_container_append(array_container_t *arr, |
263 | 0 | uint16_t pos) { |
264 | 0 | const int32_t capacity = arr->capacity; |
265 | |
|
266 | 0 | if (array_container_full(arr)) { |
267 | 0 | array_container_grow(arr, capacity + 1, true); |
268 | 0 | } |
269 | |
|
270 | 0 | arr->array[arr->cardinality++] = pos; |
271 | 0 | } Unexecuted instantiation: roaring.c:array_container_append Unexecuted instantiation: roaring_array.c:array_container_append Unexecuted instantiation: array.c:array_container_append Unexecuted instantiation: containers.c:array_container_append Unexecuted instantiation: convert.c:array_container_append Unexecuted instantiation: mixed_intersection.c:array_container_append Unexecuted instantiation: mixed_union.c:array_container_append Unexecuted instantiation: mixed_equal.c:array_container_append Unexecuted instantiation: mixed_subset.c:array_container_append Unexecuted instantiation: mixed_negation.c:array_container_append Unexecuted instantiation: mixed_xor.c:array_container_append Unexecuted instantiation: mixed_andnot.c:array_container_append |
272 | | |
273 | | /** |
274 | | * Add value to the set if final cardinality doesn't exceed max_cardinality. |
275 | | * Return code: |
276 | | * 1 -- value was added |
277 | | * 0 -- value was already present |
278 | | * -1 -- value was not added because cardinality would exceed max_cardinality |
279 | | */ |
280 | | static inline int array_container_try_add(array_container_t *arr, uint16_t value, |
281 | 0 | int32_t max_cardinality) { |
282 | 0 | const int32_t cardinality = arr->cardinality; |
283 | | |
284 | | // best case, we can append. |
285 | 0 | if ((array_container_empty(arr) || arr->array[cardinality - 1] < value) && |
286 | 0 | cardinality < max_cardinality) { |
287 | 0 | array_container_append(arr, value); |
288 | 0 | return 1; |
289 | 0 | } |
290 | | |
291 | 0 | const int32_t loc = binarySearch(arr->array, cardinality, value); |
292 | |
|
293 | 0 | if (loc >= 0) { |
294 | 0 | return 0; |
295 | 0 | } else if (cardinality < max_cardinality) { |
296 | 0 | if (array_container_full(arr)) { |
297 | 0 | array_container_grow(arr, arr->capacity + 1, true); |
298 | 0 | } |
299 | 0 | const int32_t insert_idx = -loc - 1; |
300 | 0 | memmove(arr->array + insert_idx + 1, arr->array + insert_idx, |
301 | 0 | (cardinality - insert_idx) * sizeof(uint16_t)); |
302 | 0 | arr->array[insert_idx] = value; |
303 | 0 | arr->cardinality++; |
304 | 0 | return 1; |
305 | 0 | } else { |
306 | 0 | return -1; |
307 | 0 | } |
308 | 0 | } Unexecuted instantiation: roaring.c:array_container_try_add Unexecuted instantiation: roaring_array.c:array_container_try_add Unexecuted instantiation: array.c:array_container_try_add Unexecuted instantiation: containers.c:array_container_try_add Unexecuted instantiation: convert.c:array_container_try_add Unexecuted instantiation: mixed_intersection.c:array_container_try_add Unexecuted instantiation: mixed_union.c:array_container_try_add Unexecuted instantiation: mixed_equal.c:array_container_try_add Unexecuted instantiation: mixed_subset.c:array_container_try_add Unexecuted instantiation: mixed_negation.c:array_container_try_add Unexecuted instantiation: mixed_xor.c:array_container_try_add Unexecuted instantiation: mixed_andnot.c:array_container_try_add |
309 | | |
310 | | /* Add value to the set. Returns true if x was not already present. */ |
311 | 0 | static inline bool array_container_add(array_container_t *arr, uint16_t value) { |
312 | 0 | return array_container_try_add(arr, value, INT32_MAX) == 1; |
313 | 0 | } Unexecuted instantiation: roaring.c:array_container_add Unexecuted instantiation: roaring_array.c:array_container_add Unexecuted instantiation: array.c:array_container_add Unexecuted instantiation: containers.c:array_container_add Unexecuted instantiation: convert.c:array_container_add Unexecuted instantiation: mixed_intersection.c:array_container_add Unexecuted instantiation: mixed_union.c:array_container_add Unexecuted instantiation: mixed_equal.c:array_container_add Unexecuted instantiation: mixed_subset.c:array_container_add Unexecuted instantiation: mixed_negation.c:array_container_add Unexecuted instantiation: mixed_xor.c:array_container_add Unexecuted instantiation: mixed_andnot.c:array_container_add |
314 | | |
315 | | /* Remove x from the set. Returns true if x was present. */ |
316 | | static inline bool array_container_remove(array_container_t *arr, |
317 | 0 | uint16_t pos) { |
318 | 0 | const int32_t idx = binarySearch(arr->array, arr->cardinality, pos); |
319 | 0 | const bool is_present = idx >= 0; |
320 | 0 | if (is_present) { |
321 | 0 | memmove(arr->array + idx, arr->array + idx + 1, |
322 | 0 | (arr->cardinality - idx - 1) * sizeof(uint16_t)); |
323 | 0 | arr->cardinality--; |
324 | 0 | } |
325 | |
|
326 | 0 | return is_present; |
327 | 0 | } Unexecuted instantiation: roaring.c:array_container_remove Unexecuted instantiation: roaring_array.c:array_container_remove Unexecuted instantiation: array.c:array_container_remove Unexecuted instantiation: containers.c:array_container_remove Unexecuted instantiation: convert.c:array_container_remove Unexecuted instantiation: mixed_intersection.c:array_container_remove Unexecuted instantiation: mixed_union.c:array_container_remove Unexecuted instantiation: mixed_equal.c:array_container_remove Unexecuted instantiation: mixed_subset.c:array_container_remove Unexecuted instantiation: mixed_negation.c:array_container_remove Unexecuted instantiation: mixed_xor.c:array_container_remove Unexecuted instantiation: mixed_andnot.c:array_container_remove |
328 | | |
329 | | /* Check whether x is present. */ |
330 | | inline bool array_container_contains(const array_container_t *arr, |
331 | 0 | uint16_t pos) { |
332 | | // return binarySearch(arr->array, arr->cardinality, pos) >= 0; |
333 | | // binary search with fallback to linear search for short ranges |
334 | 0 | int32_t low = 0; |
335 | 0 | const uint16_t * carr = (const uint16_t *) arr->array; |
336 | 0 | int32_t high = arr->cardinality - 1; |
337 | | // while (high - low >= 0) { |
338 | 0 | while(high >= low + 16) { |
339 | 0 | int32_t middleIndex = (low + high)>>1; |
340 | 0 | uint16_t middleValue = carr[middleIndex]; |
341 | 0 | if (middleValue < pos) { |
342 | 0 | low = middleIndex + 1; |
343 | 0 | } else if (middleValue > pos) { |
344 | 0 | high = middleIndex - 1; |
345 | 0 | } else { |
346 | 0 | return true; |
347 | 0 | } |
348 | 0 | } |
349 | | |
350 | 0 | for (int i=low; i <= high; i++) { |
351 | 0 | uint16_t v = carr[i]; |
352 | 0 | if (v == pos) { |
353 | 0 | return true; |
354 | 0 | } |
355 | 0 | if ( v > pos ) return false; |
356 | 0 | } |
357 | 0 | return false; |
358 | |
|
359 | 0 | } |
360 | | |
361 | | void array_container_offset(const array_container_t *c, |
362 | | container_t **loc, container_t **hic, |
363 | | uint16_t offset); |
364 | | |
365 | | //* Check whether a range of values from range_start (included) to range_end (excluded) is present. */ |
366 | | static inline bool array_container_contains_range(const array_container_t *arr, |
367 | 0 | uint32_t range_start, uint32_t range_end) { |
368 | 0 | const int32_t range_count = range_end - range_start; |
369 | 0 | const uint16_t rs_included = range_start; |
370 | 0 | const uint16_t re_included = range_end - 1; |
371 | | |
372 | | // Empty range is always included |
373 | 0 | if (range_count <= 0) { |
374 | 0 | return true; |
375 | 0 | } |
376 | 0 | if (range_count > arr->cardinality) { |
377 | 0 | return false; |
378 | 0 | } |
379 | | |
380 | 0 | const int32_t start = binarySearch(arr->array, arr->cardinality, rs_included); |
381 | | // If this sorted array contains all items in the range: |
382 | | // * the start item must be found |
383 | | // * the last item in range range_count must exist, and be the expected end value |
384 | 0 | return (start >= 0) && (arr->cardinality >= start + range_count) && |
385 | 0 | (arr->array[start + range_count - 1] == re_included); |
386 | 0 | } Unexecuted instantiation: roaring.c:array_container_contains_range Unexecuted instantiation: roaring_array.c:array_container_contains_range Unexecuted instantiation: array.c:array_container_contains_range Unexecuted instantiation: containers.c:array_container_contains_range Unexecuted instantiation: convert.c:array_container_contains_range Unexecuted instantiation: mixed_intersection.c:array_container_contains_range Unexecuted instantiation: mixed_union.c:array_container_contains_range Unexecuted instantiation: mixed_equal.c:array_container_contains_range Unexecuted instantiation: mixed_subset.c:array_container_contains_range Unexecuted instantiation: mixed_negation.c:array_container_contains_range Unexecuted instantiation: mixed_xor.c:array_container_contains_range Unexecuted instantiation: mixed_andnot.c:array_container_contains_range |
387 | | |
388 | | /* Returns the smallest value (assumes not empty) */ |
389 | 0 | inline uint16_t array_container_minimum(const array_container_t *arr) { |
390 | 0 | if (arr->cardinality == 0) return 0; |
391 | 0 | return arr->array[0]; |
392 | 0 | } |
393 | | |
394 | | /* Returns the largest value (assumes not empty) */ |
395 | 0 | inline uint16_t array_container_maximum(const array_container_t *arr) { |
396 | 0 | if (arr->cardinality == 0) return 0; |
397 | 0 | return arr->array[arr->cardinality - 1]; |
398 | 0 | } |
399 | | |
400 | | /* Returns the number of values equal or smaller than x */ |
401 | 0 | inline int array_container_rank(const array_container_t *arr, uint16_t x) { |
402 | 0 | const int32_t idx = binarySearch(arr->array, arr->cardinality, x); |
403 | 0 | const bool is_present = idx >= 0; |
404 | 0 | if (is_present) { |
405 | 0 | return idx + 1; |
406 | 0 | } else { |
407 | 0 | return -idx - 1; |
408 | 0 | } |
409 | 0 | } |
410 | | |
411 | | /* Returns the index of the first value equal or smaller than x, or -1 */ |
412 | 0 | inline int array_container_index_equalorlarger(const array_container_t *arr, uint16_t x) { |
413 | 0 | const int32_t idx = binarySearch(arr->array, arr->cardinality, x); |
414 | 0 | const bool is_present = idx >= 0; |
415 | 0 | if (is_present) { |
416 | 0 | return idx; |
417 | 0 | } else { |
418 | 0 | int32_t candidate = - idx - 1; |
419 | 0 | if(candidate < arr->cardinality) return candidate; |
420 | 0 | return -1; |
421 | 0 | } |
422 | 0 | } |
423 | | |
424 | | /* |
425 | | * Adds all values in range [min,max] using hint: |
426 | | * nvals_less is the number of array values less than $min |
427 | | * nvals_greater is the number of array values greater than $max |
428 | | */ |
429 | | static inline void array_container_add_range_nvals(array_container_t *array, |
430 | | uint32_t min, uint32_t max, |
431 | | int32_t nvals_less, |
432 | 0 | int32_t nvals_greater) { |
433 | 0 | int32_t union_cardinality = nvals_less + (max - min + 1) + nvals_greater; |
434 | 0 | if (union_cardinality > array->capacity) { |
435 | 0 | array_container_grow(array, union_cardinality, true); |
436 | 0 | } |
437 | 0 | memmove(&(array->array[union_cardinality - nvals_greater]), |
438 | 0 | &(array->array[array->cardinality - nvals_greater]), |
439 | 0 | nvals_greater * sizeof(uint16_t)); |
440 | 0 | for (uint32_t i = 0; i <= max - min; i++) { |
441 | 0 | array->array[nvals_less + i] = min + i; |
442 | 0 | } |
443 | 0 | array->cardinality = union_cardinality; |
444 | 0 | } Unexecuted instantiation: roaring.c:array_container_add_range_nvals Unexecuted instantiation: roaring_array.c:array_container_add_range_nvals Unexecuted instantiation: array.c:array_container_add_range_nvals Unexecuted instantiation: containers.c:array_container_add_range_nvals Unexecuted instantiation: convert.c:array_container_add_range_nvals Unexecuted instantiation: mixed_intersection.c:array_container_add_range_nvals Unexecuted instantiation: mixed_union.c:array_container_add_range_nvals Unexecuted instantiation: mixed_equal.c:array_container_add_range_nvals Unexecuted instantiation: mixed_subset.c:array_container_add_range_nvals Unexecuted instantiation: mixed_negation.c:array_container_add_range_nvals Unexecuted instantiation: mixed_xor.c:array_container_add_range_nvals Unexecuted instantiation: mixed_andnot.c:array_container_add_range_nvals |
445 | | |
446 | | /** |
447 | | * Adds all values in range [min,max]. This function is currently unused |
448 | | * and left as a documentation. |
449 | | */ |
450 | | /*static inline void array_container_add_range(array_container_t *array, |
451 | | uint32_t min, uint32_t max) { |
452 | | int32_t nvals_greater = count_greater(array->array, array->cardinality, max); |
453 | | int32_t nvals_less = count_less(array->array, array->cardinality - nvals_greater, min); |
454 | | array_container_add_range_nvals(array, min, max, nvals_less, nvals_greater); |
455 | | }*/ |
456 | | |
457 | | /* |
458 | | * Removes all elements array[pos] .. array[pos+count-1] |
459 | | */ |
460 | | static inline void array_container_remove_range(array_container_t *array, |
461 | 0 | uint32_t pos, uint32_t count) { |
462 | 0 | if (count != 0) { |
463 | 0 | memmove(&(array->array[pos]), &(array->array[pos+count]), |
464 | 0 | (array->cardinality - pos - count) * sizeof(uint16_t)); |
465 | 0 | array->cardinality -= count; |
466 | 0 | } |
467 | 0 | } Unexecuted instantiation: roaring.c:array_container_remove_range Unexecuted instantiation: roaring_array.c:array_container_remove_range Unexecuted instantiation: array.c:array_container_remove_range Unexecuted instantiation: containers.c:array_container_remove_range Unexecuted instantiation: convert.c:array_container_remove_range Unexecuted instantiation: mixed_intersection.c:array_container_remove_range Unexecuted instantiation: mixed_union.c:array_container_remove_range Unexecuted instantiation: mixed_equal.c:array_container_remove_range Unexecuted instantiation: mixed_subset.c:array_container_remove_range Unexecuted instantiation: mixed_negation.c:array_container_remove_range Unexecuted instantiation: mixed_xor.c:array_container_remove_range Unexecuted instantiation: mixed_andnot.c:array_container_remove_range |
468 | | |
469 | | #ifdef __cplusplus |
470 | | } } } // extern "C" { namespace roaring { namespace internal { |
471 | | #endif |
472 | | |
473 | | #endif /* INCLUDE_CONTAINERS_ARRAY_H_ */ |