Coverage Report

Created: 2025-07-09 06:15

/src/croaring/include/roaring/roaring_array.h
Line
Count
Source (jump to first uncovered line)
1
#ifndef INCLUDE_ROARING_ARRAY_H
2
#define INCLUDE_ROARING_ARRAY_H
3
4
#include <assert.h>
5
#include <stdbool.h>
6
#include <stdint.h>
7
8
#include <roaring/array_util.h>
9
#include <roaring/containers/containers.h>  // get_writable_copy_if_shared()
10
11
#ifdef __cplusplus
12
extern "C" {
13
namespace roaring {
14
15
// Note: in pure C++ code, you should avoid putting `using` in header files
16
using api::roaring_array_t;
17
18
namespace internal {
19
#endif
20
21
enum {
22
    SERIAL_COOKIE_NO_RUNCONTAINER = 12346,
23
    SERIAL_COOKIE = 12347,
24
    FROZEN_COOKIE = 13766,
25
    NO_OFFSET_THRESHOLD = 4
26
};
27
28
/**
29
 * Create a new roaring array
30
 */
31
roaring_array_t *ra_create(void);
32
33
/**
34
 * Initialize an existing roaring array with the specified capacity (in number
35
 * of containers)
36
 */
37
bool ra_init_with_capacity(roaring_array_t *new_ra, uint32_t cap);
38
39
/**
40
 * Initialize with zero capacity
41
 */
42
void ra_init(roaring_array_t *t);
43
44
/**
45
 * Copies this roaring array, we assume that dest is not initialized
46
 */
47
bool ra_copy(const roaring_array_t *source, roaring_array_t *dest,
48
             bool copy_on_write);
49
50
/*
51
 * Shrinks the capacity, returns the number of bytes saved.
52
 */
53
int ra_shrink_to_fit(roaring_array_t *ra);
54
55
/**
56
 * Copies this roaring array, we assume that dest is initialized
57
 */
58
bool ra_overwrite(const roaring_array_t *source, roaring_array_t *dest,
59
                  bool copy_on_write);
60
61
/**
62
 * Frees the memory used by a roaring array
63
 */
64
void ra_clear(roaring_array_t *r);
65
66
/**
67
 * Frees the memory used by a roaring array, but does not free the containers
68
 */
69
void ra_clear_without_containers(roaring_array_t *r);
70
71
/**
72
 * Frees just the containers
73
 */
74
void ra_clear_containers(roaring_array_t *ra);
75
76
/**
77
 * Get the index corresponding to a 16-bit key
78
 */
79
683k
inline int32_t ra_get_index(const roaring_array_t *ra, uint16_t x) {
80
683k
    if ((ra->size == 0) || ra->keys[ra->size - 1] == x) return ra->size - 1;
81
203k
    return binarySearch(ra->keys, (int32_t)ra->size, x);
82
683k
}
83
84
/**
85
 * Retrieves the container at index i, filling in the typecode
86
 */
87
inline container_t *ra_get_container_at_index(const roaring_array_t *ra,
88
729k
                                              uint16_t i, uint8_t *typecode) {
89
729k
    *typecode = ra->typecodes[i];
90
729k
    return ra->containers[i];
91
729k
}
92
93
/**
94
 * Retrieves the key at index i
95
 */
96
45.8k
inline uint16_t ra_get_key_at_index(const roaring_array_t *ra, uint16_t i) {
97
45.8k
    return ra->keys[i];
98
45.8k
}
99
100
/**
101
 * Add a new key-value pair at index i
102
 */
103
void ra_insert_new_key_value_at(roaring_array_t *ra, int32_t i, uint16_t key,
104
                                container_t *c, uint8_t typecode);
105
106
/**
107
 * Append a new key-value pair
108
 */
109
void ra_append(roaring_array_t *ra, uint16_t key, container_t *c,
110
               uint8_t typecode);
111
112
/**
113
 * Append a new key-value pair to ra, cloning (in COW sense) a value from sa
114
 * at index index
115
 */
116
void ra_append_copy(roaring_array_t *ra, const roaring_array_t *sa,
117
                    uint16_t index, bool copy_on_write);
118
119
/**
120
 * Append new key-value pairs to ra, cloning (in COW sense)  values from sa
121
 * at indexes
122
 * [start_index, end_index)
123
 */
124
void ra_append_copy_range(roaring_array_t *ra, const roaring_array_t *sa,
125
                          int32_t start_index, int32_t end_index,
126
                          bool copy_on_write);
127
128
/** appends from sa to ra, ending with the greatest key that is
129
 * is less or equal stopping_key
130
 */
131
void ra_append_copies_until(roaring_array_t *ra, const roaring_array_t *sa,
132
                            uint16_t stopping_key, bool copy_on_write);
133
134
/** appends from sa to ra, starting with the smallest key that is
135
 * is strictly greater than before_start
136
 */
137
138
void ra_append_copies_after(roaring_array_t *ra, const roaring_array_t *sa,
139
                            uint16_t before_start, bool copy_on_write);
140
141
/**
142
 * Move the key-value pairs to ra from sa at indexes
143
 * [start_index, end_index), old array should not be freed
144
 * (use ra_clear_without_containers)
145
 **/
146
void ra_append_move_range(roaring_array_t *ra, roaring_array_t *sa,
147
                          int32_t start_index, int32_t end_index);
148
/**
149
 * Append new key-value pairs to ra,  from sa at indexes
150
 * [start_index, end_index)
151
 */
152
void ra_append_range(roaring_array_t *ra, roaring_array_t *sa,
153
                     int32_t start_index, int32_t end_index,
154
                     bool copy_on_write);
155
156
/**
157
 * Set the container at the corresponding index using the specified
158
 * typecode.
159
 */
160
inline void ra_set_container_at_index(const roaring_array_t *ra, int32_t i,
161
0
                                      container_t *c, uint8_t typecode) {
162
0
    assert(i < ra->size);
163
0
    ra->containers[i] = c;
164
0
    ra->typecodes[i] = typecode;
165
0
}
166
167
container_t *ra_get_container(roaring_array_t *ra, uint16_t x,
168
                              uint8_t *typecode);
169
170
/**
171
 * If needed, increase the capacity of the array so that it can fit k values
172
 * (at
173
 * least);
174
 */
175
bool extend_array(roaring_array_t *ra, int32_t k);
176
177
2.59k
inline int32_t ra_get_size(const roaring_array_t *ra) { return ra->size; }
178
179
static inline int32_t ra_advance_until(const roaring_array_t *ra, uint16_t x,
180
0
                                       int32_t pos) {
181
0
    return advanceUntil(ra->keys, pos, ra->size, x);
182
0
}
Unexecuted instantiation: roaring.c:ra_advance_until
Unexecuted instantiation: roaring64.c:ra_advance_until
Unexecuted instantiation: roaring_array.c:ra_advance_until
183
184
int32_t ra_advance_until_freeing(roaring_array_t *ra, uint16_t x, int32_t pos);
185
186
void ra_downsize(roaring_array_t *ra, int32_t new_length);
187
188
inline void ra_replace_key_and_container_at_index(roaring_array_t *ra,
189
                                                  int32_t i, uint16_t key,
190
                                                  container_t *c,
191
0
                                                  uint8_t typecode) {
192
0
    assert(i < ra->size);
193
194
0
    ra->keys[i] = key;
195
0
    ra->containers[i] = c;
196
0
    ra->typecodes[i] = typecode;
197
0
}
198
199
// write set bits to an array
200
void ra_to_uint32_array(const roaring_array_t *ra, uint32_t *ans);
201
202
bool ra_range_uint32_array(const roaring_array_t *ra, size_t offset,
203
                           size_t limit, uint32_t *ans);
204
205
/**
206
 * write a bitmap to a buffer. This is meant to be compatible with
207
 * the
208
 * Java and Go versions. Return the size in bytes of the serialized
209
 * output (which should be ra_portable_size_in_bytes(ra)).
210
 */
211
size_t ra_portable_serialize(const roaring_array_t *ra, char *buf);
212
213
/**
214
 * read a bitmap from a serialized version. This is meant to be compatible
215
 * with the Java and Go versions.
216
 * maxbytes  indicates how many bytes available from buf.
217
 * When the function returns true, roaring_array_t is populated with the data
218
 * and *readbytes indicates how many bytes were read. In all cases, if the
219
 * function returns true, then maxbytes >= *readbytes.
220
 */
221
bool ra_portable_deserialize(roaring_array_t *ra, const char *buf,
222
                             const size_t maxbytes, size_t *readbytes);
223
224
/**
225
 * Quickly checks whether there is a serialized bitmap at the pointer,
226
 * not exceeding size "maxbytes" in bytes. This function does not allocate
227
 * memory dynamically.
228
 *
229
 * This function returns 0 if and only if no valid bitmap is found.
230
 * Otherwise, it returns how many bytes are occupied by the bitmap data.
231
 */
232
size_t ra_portable_deserialize_size(const char *buf, const size_t maxbytes);
233
234
/**
235
 * How many bytes are required to serialize this bitmap (meant to be
236
 * compatible
237
 * with Java and Go versions)
238
 */
239
size_t ra_portable_size_in_bytes(const roaring_array_t *ra);
240
241
/**
242
 * return true if it contains at least one run container.
243
 */
244
bool ra_has_run_container(const roaring_array_t *ra);
245
246
/**
247
 * Size of the header when serializing (meant to be compatible
248
 * with Java and Go versions)
249
 */
250
uint32_t ra_portable_header_size(const roaring_array_t *ra);
251
252
/**
253
 * If the container at the index i is share, unshare it (creating a local
254
 * copy if needed).
255
 */
256
static inline void ra_unshare_container_at_index(roaring_array_t *ra,
257
323k
                                                 uint16_t i) {
258
323k
    assert(i < ra->size);
259
323k
    ra->containers[i] =
260
323k
        get_writable_copy_if_shared(ra->containers[i], &ra->typecodes[i]);
261
323k
}
roaring.c:ra_unshare_container_at_index
Line
Count
Source
257
323k
                                                 uint16_t i) {
258
323k
    assert(i < ra->size);
259
323k
    ra->containers[i] =
260
323k
        get_writable_copy_if_shared(ra->containers[i], &ra->typecodes[i]);
261
323k
}
Unexecuted instantiation: roaring64.c:ra_unshare_container_at_index
Unexecuted instantiation: roaring_array.c:ra_unshare_container_at_index
262
263
/**
264
 * remove at index i, sliding over all entries after i
265
 */
266
void ra_remove_at_index(roaring_array_t *ra, int32_t i);
267
268
/**
269
 * clears all containers, sets the size at 0 and shrinks the memory usage.
270
 */
271
void ra_reset(roaring_array_t *ra);
272
273
/**
274
 * remove at index i, sliding over all entries after i. Free removed container.
275
 */
276
void ra_remove_at_index_and_free(roaring_array_t *ra, int32_t i);
277
278
/**
279
 * remove a chunk of indices, sliding over entries after it
280
 */
281
// void ra_remove_index_range(roaring_array_t *ra, int32_t begin, int32_t end);
282
283
// used in inplace andNot only, to slide left the containers from
284
// the mutated RoaringBitmap that are after the largest container of
285
// the argument RoaringBitmap.  It is followed by a call to resize.
286
//
287
void ra_copy_range(roaring_array_t *ra, uint32_t begin, uint32_t end,
288
                   uint32_t new_begin);
289
290
/**
291
 * Shifts rightmost $count containers to the left (distance < 0) or
292
 * to the right (distance > 0).
293
 * Allocates memory if necessary.
294
 * This function doesn't free or create new containers.
295
 * Caller is responsible for that.
296
 */
297
void ra_shift_tail(roaring_array_t *ra, int32_t count, int32_t distance);
298
299
#ifdef __cplusplus
300
}  // namespace internal
301
}
302
}  // extern "C" { namespace roaring {
303
#endif
304
305
#endif