Coverage Report

Created: 2025-07-09 06:15

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