roaring.h

Go to the documentation of this file.

/*
 * An implementation of Roaring Bitmaps in C.
 *
 * This is the main public header for the 32-bit CRoaring API. A Roaring bitmap
 * represents a set of unsigned 32-bit integers by partitioning the value space
 * into 16-bit chunks and storing each chunk in a container chosen to match the
 * local data density. Sparse chunks are typically kept as sorted arrays,
 * denser chunks as bitsets, and long consecutive runs as run containers.
 *
 * This hybrid representation aims to keep bitmaps compact while still
 * supporting fast membership tests, iteration, rank/select queries,
 * serialization, and set operations such as union, intersection, difference,
 * and symmetric difference.
 */
 
#ifndef ROARING_H
#define ROARING_H
 
#include <stdbool.h>
#include <stddef.h>  // for `size_t`
#include <stdint.h>
 
#include <roaring/roaring_types.h>
 
// Include other headers after roaring_types.h
#include <roaring/bitset/bitset.h>
#include <roaring/containers/containers.h>
#include <roaring/memory.h>
#include <roaring/portability.h>
#include <roaring/roaring_array.h>
#include <roaring/roaring_version.h>
 
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace api {
#endif
 
typedef struct roaring_bitmap_s {
    roaring_array_t high_low_container;
} roaring_bitmap_t;
 
roaring_bitmap_t *roaring_bitmap_create_with_capacity(uint32_t cap);
 
inline roaring_bitmap_t *roaring_bitmap_create(void) {
    return roaring_bitmap_create_with_capacity(0);
}
 
bool roaring_bitmap_init_with_capacity(roaring_bitmap_t *r, uint32_t cap);
 
inline void roaring_bitmap_init_cleared(roaring_bitmap_t *r) {
    roaring_bitmap_init_with_capacity(r, 0);
}
 
roaring_bitmap_t *roaring_bitmap_from_range(uint64_t min, uint64_t max,
                                            uint32_t step);
 
roaring_bitmap_t *roaring_bitmap_of_ptr(size_t n_args, const uint32_t *vals);
 
bool roaring_contains_shared(const roaring_bitmap_t *r);
 
bool roaring_unshare_all(roaring_bitmap_t *r);
 
/*
 * Whether you want to use copy-on-write.
 * Saves memory and avoids copies, but needs more care in a threaded context.
 * Most users should ignore this flag.
 *
 * Note: If you do turn this flag to 'true', enabling COW, then ensure that you
 * do so for all of your bitmaps, since interactions between bitmaps with and
 * without COW is unsafe.
 *
 * When setting this flag to false, if any containers are shared, they
 * are unshared (cloned) immediately.
 */
inline bool roaring_bitmap_get_copy_on_write(const roaring_bitmap_t *r) {
    return r->high_low_container.flags & ROARING_FLAG_COW;
}
inline void roaring_bitmap_set_copy_on_write(roaring_bitmap_t *r, bool cow) {
    if (cow) {
        r->high_low_container.flags |= ROARING_FLAG_COW;
    } else {
        if (roaring_bitmap_get_copy_on_write(r)) {
            roaring_unshare_all(r);
        }
        r->high_low_container.flags &= ~ROARING_FLAG_COW;
    }
}
 
roaring_bitmap_t *roaring_bitmap_add_offset(const roaring_bitmap_t *bm,
                                            int64_t offset);
void roaring_bitmap_printf_describe(const roaring_bitmap_t *r);
 
CROARING_DEPRECATED roaring_bitmap_t *roaring_bitmap_of(size_t n, ...);
 
#ifdef __cplusplus
// Use an immediately invoked closure, capturing by reference
// (in case __VA_ARGS__ refers to context outside the closure)
// Include a 0 at the beginning of the array to make the array length > 0
// (zero sized arrays are not valid in standard c/c++)
#define roaring_bitmap_from(...)                                              \
    [&]() {                                                                   \
        const uint32_t roaring_bitmap_from_array[] = {0, __VA_ARGS__};        \
        return roaring_bitmap_of_ptr((sizeof(roaring_bitmap_from_array) /     \
                                      sizeof(roaring_bitmap_from_array[0])) - \
                                         1,                                   \
                                     &roaring_bitmap_from_array[1]);          \
    }()
#else
// While __VA_ARGS__ occurs twice in expansion, one of the times is in a sizeof
// expression, which is an unevaluated context, so it's even safe in the case
// where expressions passed have side effects (roaring64_bitmap_from(my_func(),
// ++i))
// Include a 0 at the beginning of the array to make the array length > 0
// (zero sized arrays are not valid in standard c/c++)
#define roaring_bitmap_from(...)                                             \
    roaring_bitmap_of_ptr(                                                   \
        (sizeof((const uint32_t[]){0, __VA_ARGS__}) / sizeof(uint32_t)) - 1, \
        &((const uint32_t[]){0, __VA_ARGS__})[1])
#endif
 
roaring_bitmap_t *roaring_bitmap_copy(const roaring_bitmap_t *r);
 
bool roaring_bitmap_overwrite(roaring_bitmap_t *dest,
                              const roaring_bitmap_t *src);
 
void roaring_bitmap_printf(const roaring_bitmap_t *r);
 
roaring_bitmap_t *roaring_bitmap_and(const roaring_bitmap_t *r1,
                                     const roaring_bitmap_t *r2);
 
uint64_t roaring_bitmap_and_cardinality(const roaring_bitmap_t *r1,
                                        const roaring_bitmap_t *r2);
 
bool roaring_bitmap_intersect(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);
 
double roaring_bitmap_jaccard_index(const 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);
 
uint64_t roaring_bitmap_andnot_cardinality(const roaring_bitmap_t *r1,
                                           const roaring_bitmap_t *r2);
 
uint64_t roaring_bitmap_xor_cardinality(const roaring_bitmap_t *r1,
                                        const roaring_bitmap_t *r2);
 
void roaring_bitmap_and_inplace(roaring_bitmap_t *r1,
                                const roaring_bitmap_t *r2);
 
roaring_bitmap_t *roaring_bitmap_or(const roaring_bitmap_t *r1,
                                    const roaring_bitmap_t *r2);
 
void roaring_bitmap_or_inplace(roaring_bitmap_t *r1,
                               const roaring_bitmap_t *r2);
 
roaring_bitmap_t *roaring_bitmap_or_many(size_t number,
                                         const roaring_bitmap_t **rs);
 
roaring_bitmap_t *roaring_bitmap_or_many_heap(uint32_t number,
                                              const roaring_bitmap_t **rs);
 
roaring_bitmap_t *roaring_bitmap_xor(const roaring_bitmap_t *r1,
                                     const roaring_bitmap_t *r2);
 
void roaring_bitmap_xor_inplace(roaring_bitmap_t *r1,
                                const roaring_bitmap_t *r2);
 
roaring_bitmap_t *roaring_bitmap_xor_many(size_t number,
                                          const roaring_bitmap_t **rs);
 
roaring_bitmap_t *roaring_bitmap_andnot(const roaring_bitmap_t *r1,
                                        const roaring_bitmap_t *r2);
 
void roaring_bitmap_andnot_inplace(roaring_bitmap_t *r1,
                                   const roaring_bitmap_t *r2);
 
void roaring_bitmap_free(const roaring_bitmap_t *r);
 
typedef struct roaring_bulk_context_s {
    ROARING_CONTAINER_T *container;
    int idx;
    uint16_t key;
    uint8_t typecode;
} roaring_bulk_context_t;
 
void roaring_bitmap_add_bulk(roaring_bitmap_t *r,
                             roaring_bulk_context_t *context, uint32_t val);
 
void roaring_bitmap_add_many(roaring_bitmap_t *r, size_t n_args,
                             const uint32_t *vals);
 
void roaring_bitmap_add(roaring_bitmap_t *r, uint32_t x);
 
bool roaring_bitmap_add_checked(roaring_bitmap_t *r, uint32_t x);
 
void roaring_bitmap_add_range_closed(roaring_bitmap_t *r, uint32_t min,
                                     uint32_t max);
 
inline void roaring_bitmap_add_range(roaring_bitmap_t *r, uint64_t min,
                                     uint64_t max) {
    if (max <= min || min > (uint64_t)UINT32_MAX + 1) {
        return;
    }
    roaring_bitmap_add_range_closed(r, (uint32_t)min, (uint32_t)(max - 1));
}
 
void roaring_bitmap_remove(roaring_bitmap_t *r, uint32_t x);
 
void roaring_bitmap_remove_range_closed(roaring_bitmap_t *r, uint32_t min,
                                        uint32_t max);
 
inline void roaring_bitmap_remove_range(roaring_bitmap_t *r, uint64_t min,
                                        uint64_t max) {
    if (max <= min || min > (uint64_t)UINT32_MAX + 1) {
        return;
    }
    roaring_bitmap_remove_range_closed(r, (uint32_t)min, (uint32_t)(max - 1));
}
 
void roaring_bitmap_remove_many(roaring_bitmap_t *r, size_t n_args,
                                const uint32_t *vals);
 
bool roaring_bitmap_remove_checked(roaring_bitmap_t *r, uint32_t x);
 
inline bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t val) {
    // For performance reasons, this function is inline and uses internal
    // functions directly.
#ifdef __cplusplus
    using namespace ::roaring::internal;
#endif
    const uint16_t hb = val >> 16;
    /*
     * the next function call involves a binary search and lots of branching.
     */
    int32_t i = ra_get_index(&r->high_low_container, hb);
    if (i < 0) return false;
 
    uint8_t typecode;
    // next call ought to be cheap
    container_t *container = ra_get_container_at_index(&r->high_low_container,
                                                       (uint16_t)i, &typecode);
    // rest might be a tad expensive, possibly involving another round of binary
    // search
    return container_contains(container, val & 0xFFFF, typecode);
}
 
bool roaring_bitmap_contains_range(const roaring_bitmap_t *r,
                                   uint64_t range_start, uint64_t range_end);
 
bool roaring_bitmap_contains_range_closed(const roaring_bitmap_t *r,
                                          uint32_t range_start,
                                          uint32_t range_end);
 
bool roaring_bitmap_contains_bulk(const roaring_bitmap_t *r,
                                  roaring_bulk_context_t *context,
                                  uint32_t val);
 
uint64_t roaring_bitmap_get_cardinality(const roaring_bitmap_t *r);
 
uint64_t roaring_bitmap_range_cardinality(const roaring_bitmap_t *r,
                                          uint64_t range_start,
                                          uint64_t range_end);
 
uint64_t roaring_bitmap_range_cardinality_closed(const roaring_bitmap_t *r,
                                                 uint32_t range_start,
                                                 uint32_t range_end);
bool roaring_bitmap_is_empty(const roaring_bitmap_t *r);
 
void roaring_bitmap_clear(roaring_bitmap_t *r);
 
void roaring_bitmap_to_uint32_array(const roaring_bitmap_t *r, uint32_t *ans);
 
bool roaring_bitmap_to_bitset(const roaring_bitmap_t *r, bitset_t *bitset);
 
bool roaring_bitmap_range_uint32_array(const roaring_bitmap_t *r, size_t offset,
                                       size_t limit, uint32_t *ans);
 
bool roaring_bitmap_remove_run_compression(roaring_bitmap_t *r);
 
bool roaring_bitmap_run_optimize(roaring_bitmap_t *r);
 
size_t roaring_bitmap_shrink_to_fit(roaring_bitmap_t *r);
 
size_t roaring_bitmap_serialize(const roaring_bitmap_t *r, char *buf);
 
roaring_bitmap_t *roaring_bitmap_deserialize(const void *buf);
 
roaring_bitmap_t *roaring_bitmap_deserialize_safe(const void *buf,
                                                  size_t maxbytes);
 
size_t roaring_bitmap_size_in_bytes(const roaring_bitmap_t *r);
 
roaring_bitmap_t *roaring_bitmap_portable_deserialize(const char *buf);
 
roaring_bitmap_t *roaring_bitmap_portable_deserialize_safe(const char *buf,
                                                           size_t maxbytes);
 
roaring_bitmap_t *roaring_bitmap_portable_deserialize_frozen(const char *buf);
 
size_t roaring_bitmap_portable_deserialize_size(const char *buf,
                                                size_t maxbytes);
 
size_t roaring_bitmap_portable_size_in_bytes(const roaring_bitmap_t *r);
 
size_t roaring_bitmap_portable_serialize(const roaring_bitmap_t *r, char *buf);
 
/*
 * "Frozen" serialization format imitates memory layout of roaring_bitmap_t.
 * Deserialized bitmap is a constant view of the underlying buffer.
 * This significantly reduces amount of allocations and copying required during
 * deserialization.
 * It can be used with memory mapped files.
 * Example can be found in benchmarks/frozen_benchmark.c
 *
 *         [#####] const roaring_bitmap_t *
 *          | | |
 *     +----+ | +-+
 *     |      |   |
 * [#####################################] underlying buffer
 *
 * Note that because frozen serialization format imitates C memory layout
 * of roaring_bitmap_t, it is not fixed. It is different on big/little endian
 * platforms and can be changed in future.
 */
 
size_t roaring_bitmap_frozen_size_in_bytes(const roaring_bitmap_t *r);
 
void roaring_bitmap_frozen_serialize(const roaring_bitmap_t *r, char *buf);
 
const roaring_bitmap_t *roaring_bitmap_frozen_view(const char *buf,
                                                   size_t length);
 
bool roaring_iterate(const roaring_bitmap_t *r, roaring_iterator iterator,
                     void *ptr);
 
bool roaring_iterate64(const roaring_bitmap_t *r, roaring_iterator64 iterator,
                       uint64_t high_bits, void *ptr);
 
bool roaring_bitmap_equals(const roaring_bitmap_t *r1,
                           const roaring_bitmap_t *r2);
 
bool roaring_bitmap_is_subset(const roaring_bitmap_t *r1,
                              const roaring_bitmap_t *r2);
 
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);
 
void roaring_bitmap_lazy_or_inplace(roaring_bitmap_t *r1,
                                    const roaring_bitmap_t *r2,
                                    const bool bitsetconversion);
 
void roaring_bitmap_repair_after_lazy(roaring_bitmap_t *r1);
 
roaring_bitmap_t *roaring_bitmap_lazy_xor(const roaring_bitmap_t *r1,
                                          const roaring_bitmap_t *r2);
 
void roaring_bitmap_lazy_xor_inplace(roaring_bitmap_t *r1,
                                     const roaring_bitmap_t *r2);
 
roaring_bitmap_t *roaring_bitmap_flip(const roaring_bitmap_t *r1,
                                      uint64_t range_start, uint64_t range_end);
 
roaring_bitmap_t *roaring_bitmap_flip_closed(const roaring_bitmap_t *x1,
                                             uint32_t range_start,
                                             uint32_t range_end);
void roaring_bitmap_flip_inplace(roaring_bitmap_t *r1, uint64_t range_start,
                                 uint64_t range_end);
 
void roaring_bitmap_flip_inplace_closed(roaring_bitmap_t *r1,
                                        uint32_t range_start,
                                        uint32_t range_end);
 
bool roaring_bitmap_select(const roaring_bitmap_t *r, uint32_t rank,
                           uint32_t *element);
 
uint64_t roaring_bitmap_rank(const roaring_bitmap_t *r, uint32_t x);
 
void roaring_bitmap_rank_many(const roaring_bitmap_t *r, const uint32_t *begin,
                              const uint32_t *end, uint64_t *ans);
 
int64_t roaring_bitmap_get_index(const roaring_bitmap_t *r, uint32_t x);
 
uint32_t roaring_bitmap_minimum(const roaring_bitmap_t *r);
 
uint32_t roaring_bitmap_maximum(const roaring_bitmap_t *r);
 
void roaring_bitmap_statistics(const roaring_bitmap_t *r,
                               roaring_statistics_t *stat);
 
bool roaring_bitmap_internal_validate(const roaring_bitmap_t *r,
                                      const char **reason);
 
 
typedef struct roaring_uint32_iterator_s {
    const roaring_bitmap_t *parent;        // Owner
    const ROARING_CONTAINER_T *container;  // Current container
    uint8_t typecode;                      // Typecode of current container
    int32_t container_index;               // Current container index
    uint32_t highbits;                     // High 16 bits of the current value
    roaring_container_iterator_t container_it;
 
    uint32_t current_value;
    bool has_value;
} roaring_uint32_iterator_t;
 
void roaring_iterator_init(const roaring_bitmap_t *r,
                           roaring_uint32_iterator_t *newit);
 
CROARING_DEPRECATED static inline void roaring_init_iterator(
    const roaring_bitmap_t *r, roaring_uint32_iterator_t *newit) {
    roaring_iterator_init(r, newit);
}
 
void roaring_iterator_init_last(const roaring_bitmap_t *r,
                                roaring_uint32_iterator_t *newit);
 
CROARING_DEPRECATED static inline void roaring_init_iterator_last(
    const roaring_bitmap_t *r, roaring_uint32_iterator_t *newit) {
    roaring_iterator_init_last(r, newit);
}
 
roaring_uint32_iterator_t *roaring_iterator_create(const roaring_bitmap_t *r);
 
CROARING_DEPRECATED static inline roaring_uint32_iterator_t *
roaring_create_iterator(const roaring_bitmap_t *r) {
    return roaring_iterator_create(r);
}
 
bool roaring_uint32_iterator_advance(roaring_uint32_iterator_t *it);
 
CROARING_DEPRECATED static inline bool roaring_advance_uint32_iterator(
    roaring_uint32_iterator_t *it) {
    return roaring_uint32_iterator_advance(it);
}
 
bool roaring_uint32_iterator_previous(roaring_uint32_iterator_t *it);
 
CROARING_DEPRECATED static inline bool roaring_previous_uint32_iterator(
    roaring_uint32_iterator_t *it) {
    return roaring_uint32_iterator_previous(it);
}
 
bool roaring_uint32_iterator_move_equalorlarger(roaring_uint32_iterator_t *it,
                                                uint32_t val);
 
CROARING_DEPRECATED static inline bool
roaring_move_uint32_iterator_equalorlarger(roaring_uint32_iterator_t *it,
                                           uint32_t val) {
    return roaring_uint32_iterator_move_equalorlarger(it, val);
}
 
roaring_uint32_iterator_t *roaring_uint32_iterator_copy(
    const roaring_uint32_iterator_t *it);
 
CROARING_DEPRECATED static inline roaring_uint32_iterator_t *
roaring_copy_uint32_iterator(const roaring_uint32_iterator_t *it) {
    return roaring_uint32_iterator_copy(it);
}
 
void roaring_uint32_iterator_free(roaring_uint32_iterator_t *it);
 
CROARING_DEPRECATED static inline void roaring_free_uint32_iterator(
    roaring_uint32_iterator_t *it) {
    roaring_uint32_iterator_free(it);
}
 
uint32_t roaring_uint32_iterator_read(roaring_uint32_iterator_t *it,
                                      uint32_t *buf, uint32_t count);
 
CROARING_DEPRECATED static inline uint32_t roaring_read_uint32_iterator(
    roaring_uint32_iterator_t *it, uint32_t *buf, uint32_t count) {
    return roaring_uint32_iterator_read(it, buf, count);
}
 
uint32_t roaring_uint32_iterator_read_backward(roaring_uint32_iterator_t *it,
                                               uint32_t *buf, uint32_t count);
 
uint32_t roaring_uint32_iterator_skip(roaring_uint32_iterator_t *it,
                                      uint32_t count);
 
uint32_t roaring_uint32_iterator_skip_backward(roaring_uint32_iterator_t *it,
                                               uint32_t count);
 
typedef struct roaring_uint32_range_closed_s {
    uint32_t min;
    uint32_t max;
} roaring_uint32_range_closed_t;
 
size_t roaring_uint32_iterator_read_ranges(roaring_uint32_iterator_t *it,
                                           roaring_uint32_range_closed_t *buf,
                                           size_t count);
 
size_t roaring_uint32_iterator_read_prev_ranges(
    roaring_uint32_iterator_t *it, roaring_uint32_range_closed_t *buf,
    size_t count);
 
#ifdef __cplusplus
}
}
}  // extern "C" { namespace roaring { namespace api {
#endif
 
#endif /* ROARING_H */
 
#ifdef __cplusplus
#if !defined(ROARING_API_NOT_IN_GLOBAL_NAMESPACE)
using namespace ::roaring::api;
#endif
#endif
 
// roaring64 will include roaring.h, but we would
// prefer to avoid having our users include roaring64.h
// in addition to roaring.h.
#include <roaring/roaring64.h>