CRoaring 4.3.3
Roaring bitmaps in C (and C++)
Loading...
Searching...
No Matches
roaring.h
Go to the documentation of this file.
1/*
2 * An implementation of Roaring Bitmaps in C.
3 */
4
5#ifndef ROARING_H
6#define ROARING_H
7
8#include <stdbool.h>
9#include <stddef.h> // for `size_t`
10#include <stdint.h>
11
12#include <roaring/roaring_types.h>
13
14// Include other headers after roaring_types.h
15#include <roaring/bitset/bitset.h>
16#include <roaring/memory.h>
17#include <roaring/portability.h>
18#include <roaring/roaring_version.h>
19
20#ifdef __cplusplus
21extern "C" {
22namespace roaring {
23namespace api {
24#endif
25
29
37
46
53
62
68roaring_bitmap_t *roaring_bitmap_from_range(uint64_t min, uint64_t max,
69 uint32_t step);
70
75roaring_bitmap_t *roaring_bitmap_of_ptr(size_t n_args, const uint32_t *vals);
76
77/*
78 * Whether you want to use copy-on-write.
79 * Saves memory and avoids copies, but needs more care in a threaded context.
80 * Most users should ignore this flag.
81 *
82 * Note: If you do turn this flag to 'true', enabling COW, then ensure that you
83 * do so for all of your bitmaps, since interactions between bitmaps with and
84 * without COW is unsafe.
85 */
87 return r->high_low_container.flags & ROARING_FLAG_COW;
88}
90 if (cow) {
91 r->high_low_container.flags |= ROARING_FLAG_COW;
92 } else {
93 r->high_low_container.flags &= ~ROARING_FLAG_COW;
94 }
95}
96
103 int64_t offset);
108
117CROARING_DEPRECATED roaring_bitmap_t *roaring_bitmap_of(size_t n, ...);
118
119#ifdef __cplusplus
126// Use an immediately invoked closure, capturing by reference
127// (in case __VA_ARGS__ refers to context outside the closure)
128// Include a 0 at the beginning of the array to make the array length > 0
129// (zero sized arrays are not valid in standard c/c++)
130#define roaring_bitmap_from(...) \
131 [&]() { \
132 const uint32_t roaring_bitmap_from_array[] = {0, __VA_ARGS__}; \
133 return roaring_bitmap_of_ptr((sizeof(roaring_bitmap_from_array) / \
134 sizeof(roaring_bitmap_from_array[0])) - \
135 1, \
136 &roaring_bitmap_from_array[1]); \
137 }()
138#else
145// While __VA_ARGS__ occurs twice in expansion, one of the times is in a sizeof
146// expression, which is an unevaluated context, so it's even safe in the case
147// where expressions passed have side effects (roaring64_bitmap_from(my_func(),
148// ++i))
149// Include a 0 at the beginning of the array to make the array length > 0
150// (zero sized arrays are not valid in standard c/c++)
151#define roaring_bitmap_from(...) \
152 roaring_bitmap_of_ptr( \
153 (sizeof((const uint32_t[]){0, __VA_ARGS__}) / sizeof(uint32_t)) - 1, \
154 &((const uint32_t[]){0, __VA_ARGS__})[1])
155#endif
156
163
177 const roaring_bitmap_t *src);
178
183
195 const roaring_bitmap_t *r2);
196
201 const roaring_bitmap_t *r2);
202
207 const roaring_bitmap_t *r2);
208
213 uint64_t y);
214
222 const roaring_bitmap_t *r2);
223
228 const roaring_bitmap_t *r2);
229
234 const roaring_bitmap_t *r2);
235
240 const roaring_bitmap_t *r2);
241
250 const roaring_bitmap_t *r2);
251
258 const roaring_bitmap_t *r2);
259
265 const roaring_bitmap_t *r2);
266
274 const roaring_bitmap_t **rs);
275
282 const roaring_bitmap_t **rs);
283
290 const roaring_bitmap_t *r2);
291
296 const roaring_bitmap_t *r2);
297
304 const roaring_bitmap_t **rs);
305
312 const roaring_bitmap_t *r2);
313
318 const roaring_bitmap_t *r2);
319
335
348 ROARING_CONTAINER_T *container;
349 int idx;
350 uint16_t key;
351 uint8_t typecode;
353
369 roaring_bulk_context_t *context, uint32_t val);
370
380 const uint32_t *vals);
381
386
392
397 uint32_t max);
398
402inline void roaring_bitmap_add_range(roaring_bitmap_t *r, uint64_t min,
403 uint64_t max) {
404 if (max <= min || min > (uint64_t)UINT32_MAX + 1) {
405 return;
406 }
407 roaring_bitmap_add_range_closed(r, (uint32_t)min, (uint32_t)(max - 1));
408}
409
414
419 uint32_t max);
420
425 uint64_t max) {
426 if (max <= min || min > (uint64_t)UINT32_MAX + 1) {
427 return;
428 }
429 roaring_bitmap_remove_range_closed(r, (uint32_t)min, (uint32_t)(max - 1));
430}
431
436 const uint32_t *vals);
437
443
447bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t val);
448
454 uint64_t range_start, uint64_t range_end);
455
461 uint32_t range_start,
462 uint32_t range_end);
463
480 roaring_bulk_context_t *context,
481 uint32_t val);
482
487
492 uint64_t range_start,
493 uint64_t range_end);
494
499 uint32_t range_start,
500 uint32_t range_end);
505
512
521
538bool roaring_bitmap_to_bitset(const roaring_bitmap_t *r, bitset_t *bitset);
539
551 size_t limit, uint32_t *ans);
552
558
567
573
592size_t roaring_bitmap_serialize(const roaring_bitmap_t *r, char *buf);
593
607
625 size_t maxbytes);
626
632
651
688 size_t maxbytes);
689
713
722 size_t maxbytes);
723
731
751
752/*
753 * "Frozen" serialization format imitates memory layout of roaring_bitmap_t.
754 * Deserialized bitmap is a constant view of the underlying buffer.
755 * This significantly reduces amount of allocations and copying required during
756 * deserialization.
757 * It can be used with memory mapped files.
758 * Example can be found in benchmarks/frozen_benchmark.c
759 *
760 * [#####] const roaring_bitmap_t *
761 * | | |
762 * +----+ | +-+
763 * | | |
764 * [#####################################] underlying buffer
765 *
766 * Note that because frozen serialization format imitates C memory layout
767 * of roaring_bitmap_t, it is not fixed. It is different on big/little endian
768 * platforms and can be changed in future.
769 */
770
775
789
806 size_t length);
807
821bool roaring_iterate(const roaring_bitmap_t *r, roaring_iterator iterator,
822 void *ptr);
823
824bool roaring_iterate64(const roaring_bitmap_t *r, roaring_iterator64 iterator,
825 uint64_t high_bits, void *ptr);
826
831 const roaring_bitmap_t *r2);
832
837 const roaring_bitmap_t *r2);
838
844 const roaring_bitmap_t *r2);
845
864 const roaring_bitmap_t *r2,
865 const bool bitsetconversion);
866
876 const roaring_bitmap_t *r2,
877 const bool bitsetconversion);
878
886
901 const roaring_bitmap_t *r2);
902
909 const roaring_bitmap_t *r2);
910
918 uint64_t range_start, uint64_t range_end);
919
927 uint32_t range_start,
928 uint32_t range_end);
935void roaring_bitmap_flip_inplace(roaring_bitmap_t *r1, uint64_t range_start,
936 uint64_t range_end);
937
945 uint32_t range_start,
946 uint32_t range_end);
947
954bool roaring_bitmap_select(const roaring_bitmap_t *r, uint32_t rank,
955 uint32_t *element);
956
967uint64_t roaring_bitmap_rank(const roaring_bitmap_t *r, uint32_t x);
968
978void roaring_bitmap_rank_many(const roaring_bitmap_t *r, const uint32_t *begin,
979 const uint32_t *end, uint64_t *ans);
980
988int64_t roaring_bitmap_get_index(const roaring_bitmap_t *r, uint32_t x);
989
994
999
1007 roaring_statistics_t *stat);
1008
1024 const char **reason);
1025
1026
1047 const roaring_bitmap_t *parent; // Owner
1048 const ROARING_CONTAINER_T *container; // Current container
1049 uint8_t typecode; // Typecode of current container
1050 int32_t container_index; // Current container index
1051 uint32_t highbits; // High 16 bits of the current value
1052 roaring_container_iterator_t container_it;
1053
1057
1065
1067CROARING_DEPRECATED static inline void roaring_init_iterator(
1069 roaring_iterator_init(r, newit);
1070}
1071
1079
1081CROARING_DEPRECATED static inline void roaring_init_iterator_last(
1084}
1085
1095
1097CROARING_DEPRECATED static inline roaring_uint32_iterator_t *
1101
1112
1114CROARING_DEPRECATED static inline bool roaring_advance_uint32_iterator(
1117}
1118
1129
1131CROARING_DEPRECATED static inline bool roaring_previous_uint32_iterator(
1134}
1135
1142 uint32_t val);
1143
1145CROARING_DEPRECATED static inline bool
1150
1156 const roaring_uint32_iterator_t *it);
1157
1159CROARING_DEPRECATED static inline roaring_uint32_iterator_t *
1163
1168
1170CROARING_DEPRECATED static inline void roaring_free_uint32_iterator(
1173}
1174
1175/*
1176 * Reads next ${count} values from iterator into user-supplied ${buf}.
1177 * Returns the number of read elements.
1178 * This number can be smaller than ${count}, which means that iterator is
1179 * drained.
1180 *
1181 * This function satisfies semantics of iteration and can be used together with
1182 * other iterator functions.
1183 * - first value is copied from ${it}->current_value
1184 * - after function returns, iterator is positioned at the next element
1185 */
1187 uint32_t *buf, uint32_t count);
1188
1190CROARING_DEPRECATED static inline uint32_t roaring_read_uint32_iterator(
1191 roaring_uint32_iterator_t *it, uint32_t *buf, uint32_t count) {
1192 return roaring_uint32_iterator_read(it, buf, count);
1193}
1194
1195#ifdef __cplusplus
1196}
1197}
1198} // extern "C" { namespace roaring { namespace api {
1199#endif
1200
1201#endif /* ROARING_H */
1202
1203#ifdef __cplusplus
1215#if !defined(ROARING_API_NOT_IN_GLOBAL_NAMESPACE)
1216using namespace ::roaring::api;
1217#endif
1218#endif
1219
1220// roaring64 will include roaring.h, but we would
1221// prefer to avoid having our users include roaring64.h
1222// in addition to roaring.h.
1223#include <roaring/roaring64.h>
bool roaring_bitmap_select(const roaring_bitmap_t *r, uint32_t rank, uint32_t *element)
roaring_bitmap_t * roaring_bitmap_create(void)
Definition roaring.h:43
roaring_bitmap_t * roaring_bitmap_flip(const roaring_bitmap_t *r1, uint64_t range_start, uint64_t range_end)
bool roaring_bitmap_add_checked(roaring_bitmap_t *r, uint32_t x)
void roaring_bitmap_andnot_inplace(roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
void roaring_bitmap_add_range_closed(roaring_bitmap_t *r, uint32_t min, uint32_t max)
size_t roaring_bitmap_portable_deserialize_size(const char *buf, size_t maxbytes)
bool roaring_bitmap_contains_bulk(const roaring_bitmap_t *r, roaring_bulk_context_t *context, uint32_t val)
roaring_bitmap_t * roaring_bitmap_create_with_capacity(uint32_t cap)
size_t roaring_bitmap_portable_serialize(const roaring_bitmap_t *r, char *buf)
bool roaring_bitmap_equals(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
void roaring_bitmap_flip_inplace(roaring_bitmap_t *r1, uint64_t range_start, uint64_t range_end)
size_t roaring_bitmap_shrink_to_fit(roaring_bitmap_t *r)
void roaring_iterator_init_last(const roaring_bitmap_t *r, roaring_uint32_iterator_t *newit)
void roaring_bitmap_remove_many(roaring_bitmap_t *r, size_t n_args, const uint32_t *vals)
void roaring_bitmap_clear(roaring_bitmap_t *r)
bool roaring_bitmap_intersect(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
bool roaring_iterate64(const roaring_bitmap_t *r, roaring_iterator64 iterator, uint64_t high_bits, void *ptr)
void roaring_bitmap_printf_describe(const roaring_bitmap_t *r)
bool roaring_bitmap_internal_validate(const roaring_bitmap_t *r, const char **reason)
static CROARING_DEPRECATED void roaring_init_iterator(const roaring_bitmap_t *r, roaring_uint32_iterator_t *newit)
Definition roaring.h:1067
static CROARING_DEPRECATED roaring_uint32_iterator_t * roaring_create_iterator(const roaring_bitmap_t *r)
Definition roaring.h:1098
roaring_bitmap_t * roaring_bitmap_copy(const roaring_bitmap_t *r)
bool roaring_bitmap_run_optimize(roaring_bitmap_t *r)
roaring_bitmap_t * roaring_bitmap_lazy_xor(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
void roaring_bitmap_and_inplace(roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
uint64_t roaring_bitmap_or_cardinality(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
static CROARING_DEPRECATED void roaring_init_iterator_last(const roaring_bitmap_t *r, roaring_uint32_iterator_t *newit)
Definition roaring.h:1081
roaring_bitmap_t * roaring_bitmap_or_many_heap(uint32_t number, const roaring_bitmap_t **rs)
void roaring_iterator_init(const roaring_bitmap_t *r, roaring_uint32_iterator_t *newit)
size_t roaring_bitmap_frozen_size_in_bytes(const roaring_bitmap_t *r)
uint64_t roaring_bitmap_range_cardinality(const roaring_bitmap_t *r, uint64_t range_start, uint64_t range_end)
bool roaring_bitmap_range_uint32_array(const roaring_bitmap_t *r, size_t offset, size_t limit, uint32_t *ans)
bool roaring_bitmap_get_copy_on_write(const roaring_bitmap_t *r)
Definition roaring.h:86
void roaring_bitmap_to_uint32_array(const roaring_bitmap_t *r, uint32_t *ans)
roaring_uint32_iterator_t * roaring_uint32_iterator_copy(const roaring_uint32_iterator_t *it)
roaring_bitmap_t * roaring_bitmap_portable_deserialize_frozen(const char *buf)
roaring_bitmap_t * roaring_bitmap_or_many(size_t number, const roaring_bitmap_t **rs)
bool roaring_bitmap_overwrite(roaring_bitmap_t *dest, const roaring_bitmap_t *src)
roaring_bitmap_t * roaring_bitmap_portable_deserialize(const char *buf)
void roaring_bitmap_xor_inplace(roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
bool roaring_uint32_iterator_move_equalorlarger(roaring_uint32_iterator_t *it, uint32_t val)
double roaring_bitmap_jaccard_index(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
size_t roaring_bitmap_size_in_bytes(const roaring_bitmap_t *r)
const roaring_bitmap_t * roaring_bitmap_frozen_view(const char *buf, size_t length)
bool roaring_uint32_iterator_previous(roaring_uint32_iterator_t *it)
bool roaring_bitmap_remove_run_compression(roaring_bitmap_t *r)
bool roaring_iterate(const roaring_bitmap_t *r, roaring_iterator iterator, void *ptr)
void roaring_bitmap_init_cleared(roaring_bitmap_t *r)
Definition roaring.h:59
roaring_uint32_iterator_t * roaring_iterator_create(const roaring_bitmap_t *r)
void roaring_bitmap_add_bulk(roaring_bitmap_t *r, roaring_bulk_context_t *context, uint32_t val)
void roaring_bitmap_frozen_serialize(const roaring_bitmap_t *r, char *buf)
void roaring_bitmap_remove_range(roaring_bitmap_t *r, uint64_t min, uint64_t max)
Definition roaring.h:424
void roaring_bitmap_lazy_xor_inplace(roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
void roaring_bitmap_add_many(roaring_bitmap_t *r, size_t n_args, const uint32_t *vals)
bool roaring_bitmap_contains_range(const roaring_bitmap_t *r, uint64_t range_start, uint64_t range_end)
void roaring_bitmap_lazy_or_inplace(roaring_bitmap_t *r1, const roaring_bitmap_t *r2, const bool bitsetconversion)
bool roaring_bitmap_is_empty(const roaring_bitmap_t *r)
static CROARING_DEPRECATED bool roaring_previous_uint32_iterator(roaring_uint32_iterator_t *it)
Definition roaring.h:1131
roaring_bitmap_t * roaring_bitmap_portable_deserialize_safe(const char *buf, size_t maxbytes)
roaring_bitmap_t * roaring_bitmap_from_range(uint64_t min, uint64_t max, uint32_t step)
roaring_bitmap_t * roaring_bitmap_or(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
void roaring_bitmap_free(const roaring_bitmap_t *r)
void roaring_bitmap_statistics(const roaring_bitmap_t *r, roaring_statistics_t *stat)
bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t val)
void roaring_bitmap_remove(roaring_bitmap_t *r, uint32_t x)
roaring_bitmap_t * roaring_bitmap_add_offset(const roaring_bitmap_t *bm, int64_t offset)
void roaring_bitmap_set_copy_on_write(roaring_bitmap_t *r, bool cow)
Definition roaring.h:89
roaring_bitmap_t * roaring_bitmap_deserialize_safe(const void *buf, size_t maxbytes)
void roaring_bitmap_remove_range_closed(roaring_bitmap_t *r, uint32_t min, uint32_t max)
bool roaring_bitmap_is_strict_subset(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
roaring_bitmap_t * roaring_bitmap_lazy_or(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2, const bool bitsetconversion)
struct roaring_bitmap_s roaring_bitmap_t
uint64_t roaring_bitmap_xor_cardinality(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
roaring_bitmap_t * roaring_bitmap_flip_closed(const roaring_bitmap_t *x1, uint32_t range_start, uint32_t range_end)
bool roaring_bitmap_to_bitset(const roaring_bitmap_t *r, bitset_t *bitset)
uint64_t roaring_bitmap_andnot_cardinality(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
bool roaring_bitmap_intersect_with_range(const roaring_bitmap_t *bm, uint64_t x, uint64_t y)
roaring_bitmap_t * roaring_bitmap_deserialize(const void *buf)
size_t roaring_bitmap_portable_size_in_bytes(const roaring_bitmap_t *r)
static CROARING_DEPRECATED roaring_uint32_iterator_t * roaring_copy_uint32_iterator(const roaring_uint32_iterator_t *it)
Definition roaring.h:1160
bool roaring_bitmap_is_subset(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
static CROARING_DEPRECATED uint32_t roaring_read_uint32_iterator(roaring_uint32_iterator_t *it, uint32_t *buf, uint32_t count)
Definition roaring.h:1190
void roaring_bitmap_rank_many(const roaring_bitmap_t *r, const uint32_t *begin, const uint32_t *end, uint64_t *ans)
CROARING_DEPRECATED roaring_bitmap_t * roaring_bitmap_of(size_t n,...)
void roaring_bitmap_or_inplace(roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
uint32_t roaring_uint32_iterator_read(roaring_uint32_iterator_t *it, uint32_t *buf, uint32_t count)
uint64_t roaring_bitmap_rank(const roaring_bitmap_t *r, uint32_t x)
void roaring_uint32_iterator_free(roaring_uint32_iterator_t *it)
static CROARING_DEPRECATED bool roaring_move_uint32_iterator_equalorlarger(roaring_uint32_iterator_t *it, uint32_t val)
Definition roaring.h:1146
uint32_t roaring_bitmap_maximum(const roaring_bitmap_t *r)
bool roaring_bitmap_init_with_capacity(roaring_bitmap_t *r, uint32_t cap)
roaring_bitmap_t * roaring_bitmap_xor_many(size_t number, const roaring_bitmap_t **rs)
void roaring_bitmap_add_range(roaring_bitmap_t *r, uint64_t min, uint64_t max)
Definition roaring.h:402
void roaring_bitmap_flip_inplace_closed(roaring_bitmap_t *r1, uint32_t range_start, uint32_t range_end)
int64_t roaring_bitmap_get_index(const roaring_bitmap_t *r, uint32_t x)
roaring_bitmap_t * roaring_bitmap_and(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
uint64_t roaring_bitmap_get_cardinality(const roaring_bitmap_t *r)
uint64_t roaring_bitmap_range_cardinality_closed(const roaring_bitmap_t *r, uint32_t range_start, uint32_t range_end)
size_t roaring_bitmap_serialize(const roaring_bitmap_t *r, char *buf)
uint64_t roaring_bitmap_and_cardinality(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
roaring_bitmap_t * roaring_bitmap_xor(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
struct roaring_bulk_context_s roaring_bulk_context_t
struct roaring_uint32_iterator_s roaring_uint32_iterator_t
bool roaring_bitmap_contains_range_closed(const roaring_bitmap_t *r, uint32_t range_start, uint32_t range_end)
bool roaring_bitmap_remove_checked(roaring_bitmap_t *r, uint32_t x)
static CROARING_DEPRECATED bool roaring_advance_uint32_iterator(roaring_uint32_iterator_t *it)
Definition roaring.h:1114
void roaring_bitmap_repair_after_lazy(roaring_bitmap_t *r1)
void roaring_bitmap_printf(const roaring_bitmap_t *r)
bool roaring_uint32_iterator_advance(roaring_uint32_iterator_t *it)
static CROARING_DEPRECATED void roaring_free_uint32_iterator(roaring_uint32_iterator_t *it)
Definition roaring.h:1170
roaring_bitmap_t * roaring_bitmap_andnot(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2)
uint32_t roaring_bitmap_minimum(const roaring_bitmap_t *r)
roaring_bitmap_t * roaring_bitmap_of_ptr(size_t n_args, const uint32_t *vals)
void roaring_bitmap_add(roaring_bitmap_t *r, uint32_t x)
roaring_array_t high_low_container
Definition roaring.h:27
ROARING_CONTAINER_T * container
Definition roaring.h:348
const roaring_bitmap_t * parent
Definition roaring.h:1047
const ROARING_CONTAINER_T * container
Definition roaring.h:1048
roaring_container_iterator_t container_it
Definition roaring.h:1052