1 | /* |
2 | An implementation of Roaring Bitmaps in C. |
3 | */ |
4 | |
5 | #ifndef ROARING_H |
6 | #define ROARING_H |
7 | #ifdef __cplusplus |
8 | extern "C" { |
9 | #endif |
10 | |
11 | #include <roaring/roaring_array.h> |
12 | #include <roaring/roaring_types.h> |
13 | #include <roaring/roaring_version.h> |
14 | #include <stdbool.h> |
15 | |
16 | typedef struct roaring_bitmap_s { |
17 | roaring_array_t high_low_container; |
18 | } roaring_bitmap_t; |
19 | |
20 | /** |
21 | * Creates a new bitmap (initially empty) |
22 | */ |
23 | roaring_bitmap_t *roaring_bitmap_create(void); |
24 | |
25 | /** |
26 | * Add all the values between min (included) and max (excluded) that are at a |
27 | * distance k*step from min. |
28 | */ |
29 | roaring_bitmap_t *roaring_bitmap_from_range(uint64_t min, uint64_t max, |
30 | uint32_t step); |
31 | |
32 | /** |
33 | * Creates a new bitmap (initially empty) with a provided |
34 | * container-storage capacity (it is a performance hint). |
35 | */ |
36 | roaring_bitmap_t *roaring_bitmap_create_with_capacity(uint32_t cap); |
37 | |
38 | /** |
39 | * Creates a new bitmap from a pointer of uint32_t integers |
40 | */ |
41 | roaring_bitmap_t *roaring_bitmap_of_ptr(size_t n_args, const uint32_t *vals); |
42 | |
43 | /* |
44 | * Whether you want to use copy-on-write. |
45 | * Saves memory and avoids copies but needs more care in a threaded context. |
46 | * Most users should ignore this flag. |
47 | * Note: if you do turn this flag to 'true', enabling COW, |
48 | * then ensure that you do so for all of your bitmaps since |
49 | * interactions between bitmaps with and without COW is unsafe. |
50 | */ |
51 | inline bool roaring_bitmap_get_copy_on_write(const roaring_bitmap_t* r) { |
52 | return r->high_low_container.flags & ROARING_FLAG_COW; |
53 | } |
54 | inline void roaring_bitmap_set_copy_on_write(roaring_bitmap_t* r, bool cow) { |
55 | if (cow) { |
56 | r->high_low_container.flags |= ROARING_FLAG_COW; |
57 | } else { |
58 | r->high_low_container.flags &= ~ROARING_FLAG_COW; |
59 | } |
60 | } |
61 | |
62 | /** |
63 | * Describe the inner structure of the bitmap. |
64 | */ |
65 | void roaring_bitmap_printf_describe(const roaring_bitmap_t *ra); |
66 | |
67 | /** |
68 | * Creates a new bitmap from a list of uint32_t integers |
69 | */ |
70 | roaring_bitmap_t *roaring_bitmap_of(size_t n, ...); |
71 | |
72 | /** |
73 | * Copies a bitmap. This does memory allocation. The caller is responsible for |
74 | * memory management. |
75 | * |
76 | */ |
77 | roaring_bitmap_t *roaring_bitmap_copy(const roaring_bitmap_t *r); |
78 | |
79 | |
80 | /** |
81 | * Copies a bitmap from src to dest. It is assumed that the pointer dest |
82 | * is to an already allocated bitmap. The content of the dest bitmap is |
83 | * freed/deleted. |
84 | * |
85 | * It might be preferable and simpler to call roaring_bitmap_copy except |
86 | * that roaring_bitmap_overwrite can save on memory allocations. |
87 | * |
88 | */ |
89 | bool roaring_bitmap_overwrite(roaring_bitmap_t *dest, |
90 | const roaring_bitmap_t *src); |
91 | |
92 | /** |
93 | * Print the content of the bitmap. |
94 | */ |
95 | void roaring_bitmap_printf(const roaring_bitmap_t *ra); |
96 | |
97 | /** |
98 | * Computes the intersection between two bitmaps and returns new bitmap. The |
99 | * caller is |
100 | * responsible for memory management. |
101 | * |
102 | */ |
103 | roaring_bitmap_t *roaring_bitmap_and(const roaring_bitmap_t *x1, |
104 | const roaring_bitmap_t *x2); |
105 | |
106 | /** |
107 | * Computes the size of the intersection between two bitmaps. |
108 | * |
109 | */ |
110 | uint64_t roaring_bitmap_and_cardinality(const roaring_bitmap_t *x1, |
111 | const roaring_bitmap_t *x2); |
112 | |
113 | |
114 | /** |
115 | * Check whether two bitmaps intersect. |
116 | * |
117 | */ |
118 | bool roaring_bitmap_intersect(const roaring_bitmap_t *x1, |
119 | const roaring_bitmap_t *x2); |
120 | |
121 | /** |
122 | * Computes the Jaccard index between two bitmaps. (Also known as the Tanimoto |
123 | * distance, |
124 | * or the Jaccard similarity coefficient) |
125 | * |
126 | * The Jaccard index is undefined if both bitmaps are empty. |
127 | * |
128 | */ |
129 | double roaring_bitmap_jaccard_index(const roaring_bitmap_t *x1, |
130 | const roaring_bitmap_t *x2); |
131 | |
132 | /** |
133 | * Computes the size of the union between two bitmaps. |
134 | * |
135 | */ |
136 | uint64_t roaring_bitmap_or_cardinality(const roaring_bitmap_t *x1, |
137 | const roaring_bitmap_t *x2); |
138 | |
139 | /** |
140 | * Computes the size of the difference (andnot) between two bitmaps. |
141 | * |
142 | */ |
143 | uint64_t roaring_bitmap_andnot_cardinality(const roaring_bitmap_t *x1, |
144 | const roaring_bitmap_t *x2); |
145 | |
146 | /** |
147 | * Computes the size of the symmetric difference (andnot) between two bitmaps. |
148 | * |
149 | */ |
150 | uint64_t roaring_bitmap_xor_cardinality(const roaring_bitmap_t *x1, |
151 | const roaring_bitmap_t *x2); |
152 | |
153 | /** |
154 | * Inplace version modifies x1, x1 == x2 is allowed |
155 | */ |
156 | void roaring_bitmap_and_inplace(roaring_bitmap_t *x1, |
157 | const roaring_bitmap_t *x2); |
158 | |
159 | /** |
160 | * Computes the union between two bitmaps and returns new bitmap. The caller is |
161 | * responsible for memory management. |
162 | */ |
163 | roaring_bitmap_t *roaring_bitmap_or(const roaring_bitmap_t *x1, |
164 | const roaring_bitmap_t *x2); |
165 | |
166 | /** |
167 | * Inplace version of roaring_bitmap_or, modifies x1. TDOO: decide whether x1 == |
168 | *x2 ok |
169 | * |
170 | */ |
171 | void roaring_bitmap_or_inplace(roaring_bitmap_t *x1, |
172 | const roaring_bitmap_t *x2); |
173 | |
174 | /** |
175 | * Compute the union of 'number' bitmaps. See also roaring_bitmap_or_many_heap. |
176 | * Caller is responsible for freeing the |
177 | * result. |
178 | * |
179 | */ |
180 | roaring_bitmap_t *roaring_bitmap_or_many(size_t number, |
181 | const roaring_bitmap_t **x); |
182 | |
183 | /** |
184 | * Compute the union of 'number' bitmaps using a heap. This can |
185 | * sometimes be faster than roaring_bitmap_or_many which uses |
186 | * a naive algorithm. Caller is responsible for freeing the |
187 | * result. |
188 | * |
189 | */ |
190 | roaring_bitmap_t *roaring_bitmap_or_many_heap(uint32_t number, |
191 | const roaring_bitmap_t **x); |
192 | |
193 | /** |
194 | * Computes the symmetric difference (xor) between two bitmaps |
195 | * and returns new bitmap. The caller is responsible for memory management. |
196 | */ |
197 | roaring_bitmap_t *roaring_bitmap_xor(const roaring_bitmap_t *x1, |
198 | const roaring_bitmap_t *x2); |
199 | |
200 | /** |
201 | * Inplace version of roaring_bitmap_xor, modifies x1. x1 != x2. |
202 | * |
203 | */ |
204 | void roaring_bitmap_xor_inplace(roaring_bitmap_t *x1, |
205 | const roaring_bitmap_t *x2); |
206 | |
207 | /** |
208 | * Compute the xor of 'number' bitmaps. |
209 | * Caller is responsible for freeing the |
210 | * result. |
211 | * |
212 | */ |
213 | roaring_bitmap_t *roaring_bitmap_xor_many(size_t number, |
214 | const roaring_bitmap_t **x); |
215 | |
216 | /** |
217 | * Computes the difference (andnot) between two bitmaps |
218 | * and returns new bitmap. The caller is responsible for memory management. |
219 | */ |
220 | roaring_bitmap_t *roaring_bitmap_andnot(const roaring_bitmap_t *x1, |
221 | const roaring_bitmap_t *x2); |
222 | |
223 | /** |
224 | * Inplace version of roaring_bitmap_andnot, modifies x1. x1 != x2. |
225 | * |
226 | */ |
227 | void roaring_bitmap_andnot_inplace(roaring_bitmap_t *x1, |
228 | const roaring_bitmap_t *x2); |
229 | |
230 | /** |
231 | * TODO: consider implementing: |
232 | * Compute the xor of 'number' bitmaps using a heap. This can |
233 | * sometimes be faster than roaring_bitmap_xor_many which uses |
234 | * a naive algorithm. Caller is responsible for freeing the |
235 | * result. |
236 | * |
237 | * roaring_bitmap_t *roaring_bitmap_xor_many_heap(uint32_t number, |
238 | * const roaring_bitmap_t **x); |
239 | */ |
240 | |
241 | /** |
242 | * Frees the memory. |
243 | */ |
244 | void roaring_bitmap_free(const roaring_bitmap_t *r); |
245 | |
246 | /** |
247 | * Add value n_args from pointer vals, faster than repeatedly calling |
248 | * roaring_bitmap_add |
249 | * |
250 | */ |
251 | void roaring_bitmap_add_many(roaring_bitmap_t *r, size_t n_args, |
252 | const uint32_t *vals); |
253 | |
254 | /** |
255 | * Add value x |
256 | * |
257 | */ |
258 | void roaring_bitmap_add(roaring_bitmap_t *r, uint32_t x); |
259 | |
260 | /** |
261 | * Add value x |
262 | * Returns true if a new value was added, false if the value was already existing. |
263 | */ |
264 | bool roaring_bitmap_add_checked(roaring_bitmap_t *r, uint32_t x); |
265 | |
266 | /** |
267 | * Add all values in range [min, max] |
268 | */ |
269 | void roaring_bitmap_add_range_closed(roaring_bitmap_t *ra, uint32_t min, uint32_t max); |
270 | |
271 | /** |
272 | * Add all values in range [min, max) |
273 | */ |
274 | inline void roaring_bitmap_add_range(roaring_bitmap_t *ra, uint64_t min, uint64_t max) { |
275 | if(max == min) return; |
276 | roaring_bitmap_add_range_closed(ra, (uint32_t)min, (uint32_t)(max - 1)); |
277 | } |
278 | |
279 | /** |
280 | * Remove value x |
281 | * |
282 | */ |
283 | void roaring_bitmap_remove(roaring_bitmap_t *r, uint32_t x); |
284 | |
285 | /** Remove all values in range [min, max] */ |
286 | void roaring_bitmap_remove_range_closed(roaring_bitmap_t *ra, uint32_t min, uint32_t max); |
287 | |
288 | /** Remove all values in range [min, max) */ |
289 | inline void roaring_bitmap_remove_range(roaring_bitmap_t *ra, uint64_t min, uint64_t max) { |
290 | if(max == min) return; |
291 | roaring_bitmap_remove_range_closed(ra, (uint32_t)min, (uint32_t)(max - 1)); |
292 | } |
293 | |
294 | /** Remove multiple values */ |
295 | void roaring_bitmap_remove_many(roaring_bitmap_t *r, size_t n_args, |
296 | const uint32_t *vals); |
297 | |
298 | /** |
299 | * Remove value x |
300 | * Returns true if a new value was removed, false if the value was not existing. |
301 | */ |
302 | bool roaring_bitmap_remove_checked(roaring_bitmap_t *r, uint32_t x); |
303 | |
304 | /** |
305 | * Check if value x is present |
306 | */ |
307 | inline bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t val) { |
308 | const uint16_t hb = val >> 16; |
309 | /* |
310 | * the next function call involves a binary search and lots of branching. |
311 | */ |
312 | int32_t i = ra_get_index(&r->high_low_container, hb); |
313 | if (i < 0) return false; |
314 | |
315 | uint8_t typecode; |
316 | // next call ought to be cheap |
317 | void *container = |
318 | ra_get_container_at_index(&r->high_low_container, i, &typecode); |
319 | // rest might be a tad expensive, possibly involving another round of binary search |
320 | return container_contains(container, val & 0xFFFF, typecode); |
321 | } |
322 | |
323 | /** |
324 | * Check whether a range of values from range_start (included) to range_end (excluded) is present |
325 | */ |
326 | bool roaring_bitmap_contains_range(const roaring_bitmap_t *r, uint64_t range_start, uint64_t range_end); |
327 | |
328 | /** |
329 | * Get the cardinality of the bitmap (number of elements). |
330 | */ |
331 | uint64_t roaring_bitmap_get_cardinality(const roaring_bitmap_t *ra); |
332 | |
333 | /** |
334 | * Returns the number of elements in the range [range_start, range_end). |
335 | */ |
336 | uint64_t roaring_bitmap_range_cardinality(const roaring_bitmap_t *ra, |
337 | uint64_t range_start, uint64_t range_end); |
338 | |
339 | /** |
340 | * Returns true if the bitmap is empty (cardinality is zero). |
341 | */ |
342 | bool roaring_bitmap_is_empty(const roaring_bitmap_t *ra); |
343 | |
344 | |
345 | /** |
346 | * Empties the bitmap |
347 | */ |
348 | void roaring_bitmap_clear(roaring_bitmap_t *ra); |
349 | |
350 | /** |
351 | * Convert the bitmap to an array. Write the output to "ans", |
352 | * caller is responsible to ensure that there is enough memory |
353 | * allocated |
354 | * (e.g., ans = malloc(roaring_bitmap_get_cardinality(mybitmap) |
355 | * * sizeof(uint32_t)) |
356 | */ |
357 | void roaring_bitmap_to_uint32_array(const roaring_bitmap_t *ra, uint32_t *ans); |
358 | |
359 | |
360 | /** |
361 | * Convert the bitmap to an array from "offset" by "limit". Write the output to "ans". |
362 | * so, you can get data in paging. |
363 | * caller is responsible to ensure that there is enough memory |
364 | * allocated |
365 | * (e.g., ans = malloc(roaring_bitmap_get_cardinality(limit) |
366 | * * sizeof(uint32_t)) |
367 | * Return false in case of failure (e.g., insufficient memory) |
368 | */ |
369 | bool roaring_bitmap_range_uint32_array(const roaring_bitmap_t *ra, size_t offset, size_t limit, uint32_t *ans); |
370 | |
371 | /** |
372 | * Remove run-length encoding even when it is more space efficient |
373 | * return whether a change was applied |
374 | */ |
375 | bool roaring_bitmap_remove_run_compression(roaring_bitmap_t *r); |
376 | |
377 | /** convert array and bitmap containers to run containers when it is more |
378 | * efficient; |
379 | * also convert from run containers when more space efficient. Returns |
380 | * true if the result has at least one run container. |
381 | * Additional savings might be possible by calling shrinkToFit(). |
382 | */ |
383 | bool roaring_bitmap_run_optimize(roaring_bitmap_t *r); |
384 | |
385 | /** |
386 | * If needed, reallocate memory to shrink the memory usage. Returns |
387 | * the number of bytes saved. |
388 | */ |
389 | size_t roaring_bitmap_shrink_to_fit(roaring_bitmap_t *r); |
390 | |
391 | /** |
392 | * write the bitmap to an output pointer, this output buffer should refer to |
393 | * at least roaring_bitmap_size_in_bytes(ra) allocated bytes. |
394 | * |
395 | * see roaring_bitmap_portable_serialize if you want a format that's compatible |
396 | * with Java and Go implementations |
397 | * |
398 | * this format has the benefit of being sometimes more space efficient than |
399 | * roaring_bitmap_portable_serialize |
400 | * e.g., when the data is sparse. |
401 | * |
402 | * Returns how many bytes were written which should be |
403 | * roaring_bitmap_size_in_bytes(ra). |
404 | */ |
405 | size_t roaring_bitmap_serialize(const roaring_bitmap_t *ra, char *buf); |
406 | |
407 | /** use with roaring_bitmap_serialize |
408 | * see roaring_bitmap_portable_deserialize if you want a format that's |
409 | * compatible with Java and Go implementations |
410 | */ |
411 | roaring_bitmap_t *roaring_bitmap_deserialize(const void *buf); |
412 | |
413 | /** |
414 | * How many bytes are required to serialize this bitmap (NOT compatible |
415 | * with Java and Go versions) |
416 | */ |
417 | size_t roaring_bitmap_size_in_bytes(const roaring_bitmap_t *ra); |
418 | |
419 | /** |
420 | * read a bitmap from a serialized version. This is meant to be compatible with |
421 | * the Java and Go versions. See format specification at |
422 | * https://github.com/RoaringBitmap/RoaringFormatSpec |
423 | * In case of failure, a null pointer is returned. |
424 | * This function is unsafe in the sense that if there is no valid serialized |
425 | * bitmap at the pointer, then many bytes could be read, possibly causing a buffer |
426 | * overflow. For a safer approach, |
427 | * call roaring_bitmap_portable_deserialize_safe. |
428 | */ |
429 | roaring_bitmap_t *roaring_bitmap_portable_deserialize(const char *buf); |
430 | |
431 | /** |
432 | * read a bitmap from a serialized version in a safe manner (reading up to maxbytes). |
433 | * This is meant to be compatible with |
434 | * the Java and Go versions. See format specification at |
435 | * https://github.com/RoaringBitmap/RoaringFormatSpec |
436 | * In case of failure, a null pointer is returned. |
437 | */ |
438 | roaring_bitmap_t *roaring_bitmap_portable_deserialize_safe(const char *buf, size_t maxbytes); |
439 | |
440 | /** |
441 | * Check how many bytes would be read (up to maxbytes) at this pointer if there |
442 | * is a bitmap, returns zero if there is no valid bitmap. |
443 | * This is meant to be compatible with |
444 | * the Java and Go versions. See format specification at |
445 | * https://github.com/RoaringBitmap/RoaringFormatSpec |
446 | */ |
447 | size_t roaring_bitmap_portable_deserialize_size(const char *buf, size_t maxbytes); |
448 | |
449 | |
450 | /** |
451 | * How many bytes are required to serialize this bitmap (meant to be compatible |
452 | * with Java and Go versions). See format specification at |
453 | * https://github.com/RoaringBitmap/RoaringFormatSpec |
454 | */ |
455 | size_t roaring_bitmap_portable_size_in_bytes(const roaring_bitmap_t *ra); |
456 | |
457 | /** |
458 | * write a bitmap to a char buffer. The output buffer should refer to at least |
459 | * roaring_bitmap_portable_size_in_bytes(ra) bytes of allocated memory. |
460 | * This is meant to be compatible with |
461 | * the |
462 | * Java and Go versions. Returns how many bytes were written which should be |
463 | * roaring_bitmap_portable_size_in_bytes(ra). See format specification at |
464 | * https://github.com/RoaringBitmap/RoaringFormatSpec |
465 | */ |
466 | size_t roaring_bitmap_portable_serialize(const roaring_bitmap_t *ra, char *buf); |
467 | |
468 | /* |
469 | * "Frozen" serialization format imitates memory layout of roaring_bitmap_t. |
470 | * Deserialized bitmap is a constant view of the underlying buffer. |
471 | * This significantly reduces amount of allocations and copying required during |
472 | * deserialization. |
473 | * It can be used with memory mapped files. |
474 | * Example can be found in benchmarks/frozen_benchmark.c |
475 | * |
476 | * [#####] const roaring_bitmap_t * |
477 | * | | | |
478 | * +----+ | +-+ |
479 | * | | | |
480 | * [#####################################] underlying buffer |
481 | * |
482 | * Note that because frozen serialization format imitates C memory layout |
483 | * of roaring_bitmap_t, it is not fixed. It is different on big/little endian |
484 | * platforms and can be changed in future. |
485 | */ |
486 | |
487 | /** |
488 | * Returns number of bytes required to serialize bitmap using frozen format. |
489 | */ |
490 | size_t roaring_bitmap_frozen_size_in_bytes(const roaring_bitmap_t *ra); |
491 | |
492 | /** |
493 | * Serializes bitmap using frozen format. |
494 | * Buffer size must be at least roaring_bitmap_frozen_size_in_bytes(). |
495 | */ |
496 | void roaring_bitmap_frozen_serialize(const roaring_bitmap_t *ra, char *buf); |
497 | |
498 | /** |
499 | * Creates constant bitmap that is a view of a given buffer. |
500 | * Buffer must contain data previously written by roaring_bitmap_frozen_serialize(), |
501 | * and additionally its beginning must be aligned by 32 bytes. |
502 | * Length must be equal exactly to roaring_bitmap_frozen_size_in_bytes(). |
503 | * |
504 | * On error, NULL is returned. |
505 | * |
506 | * Bitmap returned by this function can be used in all readonly contexts. |
507 | * Bitmap must be freed as usual, by calling roaring_bitmap_free(). |
508 | * Underlying buffer must not be freed or modified while it backs any bitmaps. |
509 | */ |
510 | const roaring_bitmap_t *roaring_bitmap_frozen_view(const char *buf, size_t length); |
511 | |
512 | |
513 | /** |
514 | * Iterate over the bitmap elements. The function iterator is called once for |
515 | * all the values with ptr (can be NULL) as the second parameter of each call. |
516 | * |
517 | * roaring_iterator is simply a pointer to a function that returns bool |
518 | * (true means that the iteration should continue while false means that it |
519 | * should stop), |
520 | * and takes (uint32_t,void*) as inputs. |
521 | * |
522 | * Returns true if the roaring_iterator returned true throughout (so that |
523 | * all data points were necessarily visited). |
524 | */ |
525 | bool roaring_iterate(const roaring_bitmap_t *ra, roaring_iterator iterator, |
526 | void *ptr); |
527 | |
528 | bool roaring_iterate64(const roaring_bitmap_t *ra, roaring_iterator64 iterator, |
529 | uint64_t high_bits, void *ptr); |
530 | |
531 | /** |
532 | * Return true if the two bitmaps contain the same elements. |
533 | */ |
534 | bool roaring_bitmap_equals(const roaring_bitmap_t *ra1, |
535 | const roaring_bitmap_t *ra2); |
536 | |
537 | /** |
538 | * Return true if all the elements of ra1 are also in ra2. |
539 | */ |
540 | bool roaring_bitmap_is_subset(const roaring_bitmap_t *ra1, |
541 | const roaring_bitmap_t *ra2); |
542 | |
543 | /** |
544 | * Return true if all the elements of ra1 are also in ra2 and ra2 is strictly |
545 | * greater |
546 | * than ra1. |
547 | */ |
548 | bool roaring_bitmap_is_strict_subset(const roaring_bitmap_t *ra1, |
549 | const roaring_bitmap_t *ra2); |
550 | |
551 | /** |
552 | * (For expert users who seek high performance.) |
553 | * |
554 | * Computes the union between two bitmaps and returns new bitmap. The caller is |
555 | * responsible for memory management. |
556 | * |
557 | * The lazy version defers some computations such as the maintenance of the |
558 | * cardinality counts. Thus you need |
559 | * to call roaring_bitmap_repair_after_lazy after executing "lazy" computations. |
560 | * It is safe to repeatedly call roaring_bitmap_lazy_or_inplace on the result. |
561 | * The bitsetconversion conversion is a flag which determines |
562 | * whether container-container operations force a bitset conversion. |
563 | **/ |
564 | roaring_bitmap_t *roaring_bitmap_lazy_or(const roaring_bitmap_t *x1, |
565 | const roaring_bitmap_t *x2, |
566 | const bool bitsetconversion); |
567 | |
568 | /** |
569 | * (For expert users who seek high performance.) |
570 | * Inplace version of roaring_bitmap_lazy_or, modifies x1 |
571 | * The bitsetconversion conversion is a flag which determines |
572 | * whether container-container operations force a bitset conversion. |
573 | */ |
574 | void roaring_bitmap_lazy_or_inplace(roaring_bitmap_t *x1, |
575 | const roaring_bitmap_t *x2, |
576 | const bool bitsetconversion); |
577 | |
578 | /** |
579 | * (For expert users who seek high performance.) |
580 | * |
581 | * Execute maintenance operations on a bitmap created from |
582 | * roaring_bitmap_lazy_or |
583 | * or modified with roaring_bitmap_lazy_or_inplace. |
584 | */ |
585 | void roaring_bitmap_repair_after_lazy(roaring_bitmap_t *x1); |
586 | |
587 | /** |
588 | * Computes the symmetric difference between two bitmaps and returns new bitmap. |
589 | *The caller is |
590 | * responsible for memory management. |
591 | * |
592 | * The lazy version defers some computations such as the maintenance of the |
593 | * cardinality counts. Thus you need |
594 | * to call roaring_bitmap_repair_after_lazy after executing "lazy" computations. |
595 | * It is safe to repeatedly call roaring_bitmap_lazy_xor_inplace on the result. |
596 | * |
597 | */ |
598 | roaring_bitmap_t *roaring_bitmap_lazy_xor(const roaring_bitmap_t *x1, |
599 | const roaring_bitmap_t *x2); |
600 | |
601 | /** |
602 | * (For expert users who seek high performance.) |
603 | * Inplace version of roaring_bitmap_lazy_xor, modifies x1. x1 != x2 |
604 | * |
605 | */ |
606 | void roaring_bitmap_lazy_xor_inplace(roaring_bitmap_t *x1, |
607 | const roaring_bitmap_t *x2); |
608 | |
609 | /** |
610 | * compute the negation of the roaring bitmap within a specified |
611 | * interval: [range_start, range_end). The number of negated values is |
612 | * range_end - range_start. |
613 | * Areas outside the range are passed through unchanged. |
614 | */ |
615 | |
616 | roaring_bitmap_t *roaring_bitmap_flip(const roaring_bitmap_t *x1, |
617 | uint64_t range_start, uint64_t range_end); |
618 | |
619 | /** |
620 | * compute (in place) the negation of the roaring bitmap within a specified |
621 | * interval: [range_start, range_end). The number of negated values is |
622 | * range_end - range_start. |
623 | * Areas outside the range are passed through unchanged. |
624 | */ |
625 | |
626 | void roaring_bitmap_flip_inplace(roaring_bitmap_t *x1, uint64_t range_start, |
627 | uint64_t range_end); |
628 | |
629 | /** |
630 | * If the size of the roaring bitmap is strictly greater than rank, then this |
631 | function returns true and set element to the element of given rank. |
632 | Otherwise, it returns false. |
633 | */ |
634 | bool roaring_bitmap_select(const roaring_bitmap_t *ra, uint32_t rank, |
635 | uint32_t *element); |
636 | /** |
637 | * roaring_bitmap_rank returns the number of integers that are smaller or equal |
638 | * to x. |
639 | */ |
640 | uint64_t roaring_bitmap_rank(const roaring_bitmap_t *bm, uint32_t x); |
641 | |
642 | /** |
643 | * roaring_bitmap_smallest returns the smallest value in the set. |
644 | * Returns UINT32_MAX if the set is empty. |
645 | */ |
646 | uint32_t roaring_bitmap_minimum(const roaring_bitmap_t *bm); |
647 | |
648 | /** |
649 | * roaring_bitmap_smallest returns the greatest value in the set. |
650 | * Returns 0 if the set is empty. |
651 | */ |
652 | uint32_t roaring_bitmap_maximum(const roaring_bitmap_t *bm); |
653 | |
654 | /** |
655 | * (For advanced users.) |
656 | * Collect statistics about the bitmap, see roaring_types.h for |
657 | * a description of roaring_statistics_t |
658 | */ |
659 | void roaring_bitmap_statistics(const roaring_bitmap_t *ra, |
660 | roaring_statistics_t *stat); |
661 | |
662 | /********************* |
663 | * What follows is code use to iterate through values in a roaring bitmap |
664 | |
665 | roaring_bitmap_t *ra =... |
666 | roaring_uint32_iterator_t i; |
667 | roaring_create_iterator(ra, &i); |
668 | while(i.has_value) { |
669 | printf("value = %d\n", i.current_value); |
670 | roaring_advance_uint32_iterator(&i); |
671 | } |
672 | |
673 | Obviously, if you modify the underlying bitmap, the iterator |
674 | becomes invalid. So don't. |
675 | */ |
676 | |
677 | typedef struct roaring_uint32_iterator_s { |
678 | const roaring_bitmap_t *parent; // owner |
679 | int32_t container_index; // point to the current container index |
680 | int32_t in_container_index; // for bitset and array container, this is out |
681 | // index |
682 | int32_t run_index; // for run container, this points at the run |
683 | |
684 | uint32_t current_value; |
685 | bool has_value; |
686 | |
687 | const void |
688 | *container; // should be: |
689 | // parent->high_low_container.containers[container_index]; |
690 | uint8_t typecode; // should be: |
691 | // parent->high_low_container.typecodes[container_index]; |
692 | uint32_t highbits; // should be: |
693 | // parent->high_low_container.keys[container_index]) << |
694 | // 16; |
695 | |
696 | } roaring_uint32_iterator_t; |
697 | |
698 | /** |
699 | * Initialize an iterator object that can be used to iterate through the |
700 | * values. If there is a value, then this iterator points to the first value |
701 | * and it->has_value is true. The value is in it->current_value. |
702 | */ |
703 | void roaring_init_iterator(const roaring_bitmap_t *ra, |
704 | roaring_uint32_iterator_t *newit); |
705 | |
706 | /** |
707 | * Initialize an iterator object that can be used to iterate through the |
708 | * values. If there is a value, then this iterator points to the last value |
709 | * and it->has_value is true. The value is in it->current_value. |
710 | */ |
711 | void roaring_init_iterator_last(const roaring_bitmap_t *ra, |
712 | roaring_uint32_iterator_t *newit); |
713 | |
714 | /** |
715 | * Create an iterator object that can be used to iterate through the |
716 | * values. Caller is responsible for calling roaring_free_iterator. |
717 | * The iterator is initialized. If there is a value, then this iterator |
718 | * points to the first value and it->has_value is true. |
719 | * The value is in it->current_value. |
720 | * |
721 | * This function calls roaring_init_iterator. |
722 | */ |
723 | roaring_uint32_iterator_t *roaring_create_iterator(const roaring_bitmap_t *ra); |
724 | |
725 | /** |
726 | * Advance the iterator. If there is a new value, then it->has_value is true. |
727 | * The new value is in it->current_value. Values are traversed in increasing |
728 | * orders. For convenience, returns it->has_value. |
729 | */ |
730 | bool roaring_advance_uint32_iterator(roaring_uint32_iterator_t *it); |
731 | |
732 | /** |
733 | * Decrement the iterator. If there is a new value, then it->has_value is true. |
734 | * The new value is in it->current_value. Values are traversed in decreasing |
735 | * orders. For convenience, returns it->has_value. |
736 | */ |
737 | bool roaring_previous_uint32_iterator(roaring_uint32_iterator_t *it); |
738 | |
739 | /** |
740 | * Move the iterator to the first value >= val. If there is a such a value, then it->has_value is true. |
741 | * The new value is in it->current_value. For convenience, returns it->has_value. |
742 | */ |
743 | bool roaring_move_uint32_iterator_equalorlarger(roaring_uint32_iterator_t *it, uint32_t val) ; |
744 | /** |
745 | * Creates a copy of an iterator. |
746 | * Caller must free it. |
747 | */ |
748 | roaring_uint32_iterator_t *roaring_copy_uint32_iterator( |
749 | const roaring_uint32_iterator_t *it); |
750 | |
751 | /** |
752 | * Free memory following roaring_create_iterator |
753 | */ |
754 | void roaring_free_uint32_iterator(roaring_uint32_iterator_t *it); |
755 | |
756 | /* |
757 | * Reads next ${count} values from iterator into user-supplied ${buf}. |
758 | * Returns the number of read elements. |
759 | * This number can be smaller than ${count}, which means that iterator is drained. |
760 | * |
761 | * This function satisfies semantics of iteration and can be used together with |
762 | * other iterator functions. |
763 | * - first value is copied from ${it}->current_value |
764 | * - after function returns, iterator is positioned at the next element |
765 | */ |
766 | uint32_t roaring_read_uint32_iterator(roaring_uint32_iterator_t *it, uint32_t* buf, uint32_t count); |
767 | |
768 | #ifdef __cplusplus |
769 | } |
770 | #endif |
771 | |
772 | #endif |
773 | |