1/*
2An implementation of Roaring Bitmaps in C.
3*/
4
5#ifndef ROARING_H
6#define ROARING_H
7#ifdef __cplusplus
8extern "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
16typedef 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 */
23roaring_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*/
29roaring_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 */
36roaring_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 */
41roaring_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 */
51inline bool roaring_bitmap_get_copy_on_write(const roaring_bitmap_t* r) {
52 return r->high_low_container.flags & ROARING_FLAG_COW;
53}
54inline 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 */
65void roaring_bitmap_printf_describe(const roaring_bitmap_t *ra);
66
67/**
68 * Creates a new bitmap from a list of uint32_t integers
69 */
70roaring_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 */
77roaring_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 */
89bool roaring_bitmap_overwrite(roaring_bitmap_t *dest,
90 const roaring_bitmap_t *src);
91
92/**
93 * Print the content of the bitmap.
94 */
95void 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 */
103roaring_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 */
110uint64_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 */
118bool 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 */
129double 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 */
136uint64_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 */
143uint64_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 */
150uint64_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 */
156void 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 */
163roaring_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 */
171void 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 */
180roaring_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 */
190roaring_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 */
197roaring_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 */
204void 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 */
213roaring_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 */
220roaring_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 */
227void 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 */
244void 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 */
251void 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 */
258void 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 */
264bool roaring_bitmap_add_checked(roaring_bitmap_t *r, uint32_t x);
265
266/**
267 * Add all values in range [min, max]
268 */
269void 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 */
274inline 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 */
283void roaring_bitmap_remove(roaring_bitmap_t *r, uint32_t x);
284
285/** Remove all values in range [min, max] */
286void roaring_bitmap_remove_range_closed(roaring_bitmap_t *ra, uint32_t min, uint32_t max);
287
288/** Remove all values in range [min, max) */
289inline 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 */
295void 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 */
302bool roaring_bitmap_remove_checked(roaring_bitmap_t *r, uint32_t x);
303
304/**
305 * Check if value x is present
306 */
307inline 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 */
326bool 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 */
331uint64_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 */
336uint64_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*/
342bool roaring_bitmap_is_empty(const roaring_bitmap_t *ra);
343
344
345/**
346* Empties the bitmap
347*/
348void 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 */
357void 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 */
369bool 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 */
375bool 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 */
383bool 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*/
389size_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*/
405size_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*/
411roaring_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 */
417size_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 */
429roaring_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 */
438roaring_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 */
447size_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 */
455size_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 */
466size_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 */
490size_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 */
496void 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 */
510const 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 */
525bool roaring_iterate(const roaring_bitmap_t *ra, roaring_iterator iterator,
526 void *ptr);
527
528bool 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 */
534bool 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 */
540bool 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 */
548bool 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 **/
564roaring_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 */
574void 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 */
585void 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 */
598roaring_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 */
606void 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
616roaring_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
626void 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 */
634bool 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*/
640uint64_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*/
646uint32_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*/
652uint32_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*/
659void 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
665roaring_bitmap_t *ra =...
666roaring_uint32_iterator_t i;
667roaring_create_iterator(ra, &i);
668while(i.has_value) {
669 printf("value = %d\n", i.current_value);
670 roaring_advance_uint32_iterator(&i);
671}
672
673Obviously, if you modify the underlying bitmap, the iterator
674becomes invalid. So don't.
675*/
676
677typedef 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*/
703void 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*/
711void 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*/
723roaring_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*/
730bool 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*/
737bool 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*/
743bool 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*/
748roaring_uint32_iterator_t *roaring_copy_uint32_iterator(
749 const roaring_uint32_iterator_t *it);
750
751/**
752* Free memory following roaring_create_iterator
753*/
754void 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 */
766uint32_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