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