1 | #ifndef INCLUDE_ROARING_ARRAY_H |
2 | #define INCLUDE_ROARING_ARRAY_H |
3 | #ifdef __cplusplus |
4 | extern "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 | |
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 | * 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 | |
38 | typedef 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 | */ |
50 | roaring_array_t *ra_create(void); |
51 | |
52 | /** |
53 | * Initialize an existing roaring array with the specified capacity (in number |
54 | * of containers) |
55 | */ |
56 | bool ra_init_with_capacity(roaring_array_t *new_ra, uint32_t cap); |
57 | |
58 | /** |
59 | * Initialize with zero capacity |
60 | */ |
61 | void ra_init(roaring_array_t *t); |
62 | |
63 | /** |
64 | * Copies this roaring array, we assume that dest is not initialized |
65 | */ |
66 | bool 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 | */ |
72 | int ra_shrink_to_fit(roaring_array_t *ra); |
73 | |
74 | /** |
75 | * Copies this roaring array, we assume that dest is initialized |
76 | */ |
77 | bool 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 | */ |
83 | void ra_clear(roaring_array_t *r); |
84 | |
85 | /** |
86 | * Frees the memory used by a roaring array, but does not free the containers |
87 | */ |
88 | void ra_clear_without_containers(roaring_array_t *r); |
89 | |
90 | /** |
91 | * Frees just the containers |
92 | */ |
93 | void ra_clear_containers(roaring_array_t *ra); |
94 | |
95 | /** |
96 | * Get the index corresponding to a 16-bit key |
97 | */ |
98 | inline 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 | */ |
106 | inline 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 | */ |
115 | uint16_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 | */ |
120 | void 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 | */ |
126 | void 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 | */ |
132 | void 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 | */ |
140 | void 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 | */ |
147 | void 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 | |
154 | void 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 | **/ |
162 | void 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 | */ |
168 | void 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 | */ |
176 | inline 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 | */ |
188 | bool extend_array(roaring_array_t *ra, int32_t k); |
189 | |
190 | inline int32_t ra_get_size(const roaring_array_t *ra) { return ra->size; } |
191 | |
192 | static 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 | |
197 | int32_t ra_advance_until_freeing(roaring_array_t *ra, uint16_t x, int32_t pos); |
198 | |
199 | void ra_downsize(roaring_array_t *ra, int32_t new_length); |
200 | |
201 | inline 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 |
212 | void ra_to_uint32_array(const roaring_array_t *ra, uint32_t *ans); |
213 | |
214 | bool 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 | */ |
222 | size_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 | */ |
232 | bool 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 | */ |
242 | size_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 | */ |
249 | size_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 | */ |
254 | bool 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 | */ |
260 | uint32_t (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 | */ |
266 | static 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 | */ |
276 | void 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 | */ |
282 | void ra_reset(roaring_array_t *ra); |
283 | |
284 | /** |
285 | * remove at index i, sliding over all entries after i. Free removed container. |
286 | */ |
287 | void 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 | // |
298 | void 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 | */ |
308 | void ra_shift_tail(roaring_array_t *ra, int32_t count, int32_t distance); |
309 | |
310 | #ifdef __cplusplus |
311 | } |
312 | #endif |
313 | |
314 | #endif |
315 | |