roaring64.h

Go to the documentation of this file.

/*
 * roaring64.h
 *
 * This file declares the 64-bit Roaring bitmap API. A roaring64 bitmap stores
 * sets of 64-bit unsigned integers by partitioning the value space by high
 * bits and using Roaring containers for the lower bits inside each partition.
 * This keeps the structure compact while preserving fast membership tests,
 * insertions, iteration, and set operations over large sparse integer sets.
 */
#ifndef ROARING64_H
#define ROARING64_H
 
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
 
#include <roaring/memory.h>
#include <roaring/portability.h>
#include <roaring/roaring.h>
#include <roaring/roaring_types.h>
 
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace api {
#endif
 
typedef struct roaring64_bitmap_s roaring64_bitmap_t;
typedef uint64_t roaring64_leaf_t;
typedef struct roaring64_iterator_s roaring64_iterator_t;
 
typedef struct roaring64_bulk_context_s {
    uint8_t high_bytes[6];
    roaring64_leaf_t *leaf;
} roaring64_bulk_context_t;
 
roaring64_bitmap_t *roaring64_bitmap_create(void);
void roaring64_bitmap_free(roaring64_bitmap_t *r);
 
roaring64_bitmap_t *roaring64_bitmap_copy(const roaring64_bitmap_t *r);
 
void roaring64_bitmap_overwrite(roaring64_bitmap_t *dest,
                                const roaring64_bitmap_t *src);
 
roaring64_bitmap_t *roaring64_bitmap_of_ptr(size_t n_args,
                                            const uint64_t *vals);
 
#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 roaring64_bitmap_from(...)                                       \
    [&]() {                                                              \
        const uint64_t roaring64_bitmap_from_array[] = {0, __VA_ARGS__}; \
        return roaring64_bitmap_of_ptr(                                  \
            (sizeof(roaring64_bitmap_from_array) /                       \
             sizeof(roaring64_bitmap_from_array[0])) -                   \
                1,                                                       \
            &roaring64_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 roaring64_bitmap_from(...)                                           \
    roaring64_bitmap_of_ptr(                                                 \
        (sizeof((const uint64_t[]){0, __VA_ARGS__}) / sizeof(uint64_t)) - 1, \
        &((const uint64_t[]){0, __VA_ARGS__})[1])
#endif
 
roaring64_bitmap_t *roaring64_bitmap_move_from_roaring32(roaring_bitmap_t *r);
 
roaring64_bitmap_t *roaring64_bitmap_from_range(uint64_t min, uint64_t max,
                                                uint64_t step);
 
void roaring64_bitmap_add(roaring64_bitmap_t *r, uint64_t val);
 
bool roaring64_bitmap_add_checked(roaring64_bitmap_t *r, uint64_t val);
 
void roaring64_bitmap_add_bulk(roaring64_bitmap_t *r,
                               roaring64_bulk_context_t *context, uint64_t val);
 
void roaring64_bitmap_add_many(roaring64_bitmap_t *r, size_t n_args,
                               const uint64_t *vals);
 
void roaring64_bitmap_add_range(roaring64_bitmap_t *r, uint64_t min,
                                uint64_t max);
 
void roaring64_bitmap_add_range_closed(roaring64_bitmap_t *r, uint64_t min,
                                       uint64_t max);
 
void roaring64_bitmap_remove(roaring64_bitmap_t *r, uint64_t val);
 
bool roaring64_bitmap_remove_checked(roaring64_bitmap_t *r, uint64_t val);
 
void roaring64_bitmap_remove_bulk(roaring64_bitmap_t *r,
                                  roaring64_bulk_context_t *context,
                                  uint64_t val);
 
void roaring64_bitmap_remove_many(roaring64_bitmap_t *r, size_t n_args,
                                  const uint64_t *vals);
 
void roaring64_bitmap_remove_range(roaring64_bitmap_t *r, uint64_t min,
                                   uint64_t max);
 
void roaring64_bitmap_remove_range_closed(roaring64_bitmap_t *r, uint64_t min,
                                          uint64_t max);
 
void roaring64_bitmap_clear(roaring64_bitmap_t *r);
 
bool roaring64_bitmap_contains(const roaring64_bitmap_t *r, uint64_t val);
 
bool roaring64_bitmap_contains_range(const roaring64_bitmap_t *r, uint64_t min,
                                     uint64_t max);
 
bool roaring64_bitmap_contains_range_closed(const roaring64_bitmap_t *r,
                                            uint64_t min, uint64_t max);
 
bool roaring64_bitmap_contains_bulk(const roaring64_bitmap_t *r,
                                    roaring64_bulk_context_t *context,
                                    uint64_t val);
 
bool roaring64_bitmap_select(const roaring64_bitmap_t *r, uint64_t rank,
                             uint64_t *element);
 
uint64_t roaring64_bitmap_rank(const roaring64_bitmap_t *r, uint64_t val);
 
bool roaring64_bitmap_get_index(const roaring64_bitmap_t *r, uint64_t val,
                                uint64_t *out_index);
 
uint64_t roaring64_bitmap_get_cardinality(const roaring64_bitmap_t *r);
 
uint64_t roaring64_bitmap_range_cardinality(const roaring64_bitmap_t *r,
                                            uint64_t min, uint64_t max);
 
uint64_t roaring64_bitmap_range_closed_cardinality(const roaring64_bitmap_t *r,
                                                   uint64_t min, uint64_t max);
 
bool roaring64_bitmap_is_empty(const roaring64_bitmap_t *r);
 
uint64_t roaring64_bitmap_minimum(const roaring64_bitmap_t *r);
 
uint64_t roaring64_bitmap_maximum(const roaring64_bitmap_t *r);
 
bool roaring64_bitmap_remove_run_compression(roaring64_bitmap_t *r);
 
bool roaring64_bitmap_run_optimize(roaring64_bitmap_t *r);
 
size_t roaring64_bitmap_shrink_to_fit(roaring64_bitmap_t *r);
 
void roaring64_bitmap_statistics(const roaring64_bitmap_t *r,
                                 roaring64_statistics_t *stat);
 
bool roaring64_bitmap_internal_validate(const roaring64_bitmap_t *r,
                                        const char **reason);
 
bool roaring64_bitmap_equals(const roaring64_bitmap_t *r1,
                             const roaring64_bitmap_t *r2);
 
bool roaring64_bitmap_is_subset(const roaring64_bitmap_t *r1,
                                const roaring64_bitmap_t *r2);
 
bool roaring64_bitmap_is_strict_subset(const roaring64_bitmap_t *r1,
                                       const roaring64_bitmap_t *r2);
 
roaring64_bitmap_t *roaring64_bitmap_and(const roaring64_bitmap_t *r1,
                                         const roaring64_bitmap_t *r2);
 
uint64_t roaring64_bitmap_and_cardinality(const roaring64_bitmap_t *r1,
                                          const roaring64_bitmap_t *r2);
 
void roaring64_bitmap_and_inplace(roaring64_bitmap_t *r1,
                                  const roaring64_bitmap_t *r2);
 
bool roaring64_bitmap_intersect(const roaring64_bitmap_t *r1,
                                const roaring64_bitmap_t *r2);
 
bool roaring64_bitmap_intersect_with_range(const roaring64_bitmap_t *r,
                                           uint64_t min, uint64_t max);
 
double roaring64_bitmap_jaccard_index(const roaring64_bitmap_t *r1,
                                      const roaring64_bitmap_t *r2);
 
roaring64_bitmap_t *roaring64_bitmap_or(const roaring64_bitmap_t *r1,
                                        const roaring64_bitmap_t *r2);
 
uint64_t roaring64_bitmap_or_cardinality(const roaring64_bitmap_t *r1,
                                         const roaring64_bitmap_t *r2);
 
void roaring64_bitmap_or_inplace(roaring64_bitmap_t *r1,
                                 const roaring64_bitmap_t *r2);
 
roaring64_bitmap_t *roaring64_bitmap_xor(const roaring64_bitmap_t *r1,
                                         const roaring64_bitmap_t *r2);
 
uint64_t roaring64_bitmap_xor_cardinality(const roaring64_bitmap_t *r1,
                                          const roaring64_bitmap_t *r2);
 
void roaring64_bitmap_xor_inplace(roaring64_bitmap_t *r1,
                                  const roaring64_bitmap_t *r2);
 
roaring64_bitmap_t *roaring64_bitmap_andnot(const roaring64_bitmap_t *r1,
                                            const roaring64_bitmap_t *r2);
 
uint64_t roaring64_bitmap_andnot_cardinality(const roaring64_bitmap_t *r1,
                                             const roaring64_bitmap_t *r2);
 
void roaring64_bitmap_andnot_inplace(roaring64_bitmap_t *r1,
                                     const roaring64_bitmap_t *r2);
 
roaring64_bitmap_t *roaring64_bitmap_flip(const roaring64_bitmap_t *r,
                                          uint64_t min, uint64_t max);
 
roaring64_bitmap_t *roaring64_bitmap_flip_closed(const roaring64_bitmap_t *r,
                                                 uint64_t min, uint64_t max);
 
void roaring64_bitmap_flip_inplace(roaring64_bitmap_t *r, uint64_t min,
                                   uint64_t max);
void roaring64_bitmap_flip_closed_inplace(roaring64_bitmap_t *r, uint64_t min,
                                          uint64_t max);
roaring64_bitmap_t *roaring64_bitmap_add_offset_signed(
    const roaring64_bitmap_t *r, bool positive, uint64_t offset);
 
static inline roaring64_bitmap_t *roaring64_bitmap_add_offset(
    const roaring64_bitmap_t *r, uint64_t offset) {
    return roaring64_bitmap_add_offset_signed(r, true, offset);
}
 
static inline roaring64_bitmap_t *roaring64_bitmap_sub_offset(
    const roaring64_bitmap_t *r, uint64_t offset) {
    return roaring64_bitmap_add_offset_signed(r, false, offset);
}
 
size_t roaring64_bitmap_portable_size_in_bytes(const roaring64_bitmap_t *r);
 
size_t roaring64_bitmap_portable_serialize(const roaring64_bitmap_t *r,
                                           char *buf);
size_t roaring64_bitmap_portable_deserialize_size(const char *buf,
                                                  size_t maxbytes);
 
roaring64_bitmap_t *roaring64_bitmap_portable_deserialize_safe(const char *buf,
                                                               size_t maxbytes);
 
size_t roaring64_bitmap_frozen_size_in_bytes(const roaring64_bitmap_t *r);
 
size_t roaring64_bitmap_frozen_serialize(const roaring64_bitmap_t *r,
                                         char *buf);
 
roaring64_bitmap_t *roaring64_bitmap_frozen_view(const char *buf,
                                                 size_t maxbytes);
 
bool roaring64_bitmap_iterate(const roaring64_bitmap_t *r,
                              roaring_iterator64 iterator, void *ptr);
 
void roaring64_bitmap_to_uint64_array(const roaring64_bitmap_t *r,
                                      uint64_t *out);
 
roaring64_iterator_t *roaring64_iterator_create(const roaring64_bitmap_t *r);
 
roaring64_iterator_t *roaring64_iterator_create_last(
    const roaring64_bitmap_t *r);
 
void roaring64_iterator_reinit(const roaring64_bitmap_t *r,
                               roaring64_iterator_t *it);
 
void roaring64_iterator_reinit_last(const roaring64_bitmap_t *r,
                                    roaring64_iterator_t *it);
 
roaring64_iterator_t *roaring64_iterator_copy(const roaring64_iterator_t *it);
 
void roaring64_iterator_free(roaring64_iterator_t *it);
 
bool roaring64_iterator_has_value(const roaring64_iterator_t *it);
 
uint64_t roaring64_iterator_value(const roaring64_iterator_t *it);
 
bool roaring64_iterator_advance(roaring64_iterator_t *it);
 
bool roaring64_iterator_previous(roaring64_iterator_t *it);
 
bool roaring64_iterator_move_equalorlarger(roaring64_iterator_t *it,
                                           uint64_t val);
 
uint64_t roaring64_iterator_read(roaring64_iterator_t *it, uint64_t *buf,
                                 uint64_t count);
 
uint64_t roaring64_iterator_read_backward(roaring64_iterator_t *it,
                                          uint64_t *buf, uint64_t count);
 
typedef struct roaring64_range_closed_s {
    uint64_t min;
    uint64_t max;
} roaring64_range_closed_t;
 
size_t roaring64_iterator_read_ranges(roaring64_iterator_t *it,
                                      roaring64_range_closed_t *buf,
                                      size_t count);
 
size_t roaring64_iterator_read_prev_ranges(roaring64_iterator_t *it,
                                           roaring64_range_closed_t *buf,
                                           size_t count);
 
#ifdef __cplusplus
}  // extern "C"
}  // namespace roaring
}  // namespace api
#endif
 
#endif /* ROARING64_H */