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