Coverage Report

Created: 2023-01-15 06:02

/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_ */