#ifndef ROARING_INCLUDE_ROARING_VERSION
#define ROARING_INCLUDE_ROARING_VERSION
#define ROARING_VERSION "4.5.1"
enum {
ROARING_VERSION_MAJOR = 4,
ROARING_VERSION_MINOR = 5,
ROARING_VERSION_REVISION = 1
};
#endif
#ifndef CROARING_INCLUDE_PORTABILITY_H_
#define CROARING_INCLUDE_PORTABILITY_H_
#ifndef __STDC_FORMAT_MACROS
#define __STDC_FORMAT_MACROS 1
#endif
#ifdef _MSC_VER
#define CROARING_VISUAL_STUDIO 1
#ifdef __clang__
#define CROARING_CLANG_VISUAL_STUDIO 1
#else
#define CROARING_REGULAR_VISUAL_STUDIO 1
#endif #endif #ifndef CROARING_VISUAL_STUDIO
#define CROARING_VISUAL_STUDIO 0
#endif
#ifndef CROARING_CLANG_VISUAL_STUDIO
#define CROARING_CLANG_VISUAL_STUDIO 0
#endif
#ifndef CROARING_REGULAR_VISUAL_STUDIO
#define CROARING_REGULAR_VISUAL_STUDIO 0
#endif
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#ifdef __GLIBC__
#include <malloc.h>
#endif
#ifdef __cplusplus
extern "C" { #endif
#if defined(__SIZEOF_LONG_LONG__) && __SIZEOF_LONG_LONG__ != 8
#error This code assumes 64-bit long longs (by use of the GCC intrinsics). Your system is not currently supported.
#endif
#if CROARING_REGULAR_VISUAL_STUDIO
#ifndef __restrict__
#define __restrict__ __restrict
#endif #endif
#if defined(__x86_64__) || defined(_M_X64)
#define CROARING_IS_X64 1
#if defined(_MSC_VER) && (_MSC_VER < 1910)
#undef CROARING_IS_X64
#endif
#if defined(__clang_major__) && (__clang_major__ <= 8) && !defined(__AVX2__)
#undef CROARING_IS_X64
#endif
#ifdef ROARING_DISABLE_X64
#undef CROARING_IS_X64
#endif
#if !CROARING_REGULAR_VISUAL_STUDIO
#include <x86intrin.h>
#if CROARING_CLANG_VISUAL_STUDIO
#include <bmiintrin.h>
#include <lzcntintrin.h>
#include <immintrin.h>
#include <smmintrin.h>
#include <tmmintrin.h>
#include <avxintrin.h>
#include <avx2intrin.h>
#include <wmmintrin.h>
#if _MSC_VER >= 1920
#include <avx512fintrin.h>
#include <avx512dqintrin.h>
#include <avx512cdintrin.h>
#include <avx512bwintrin.h>
#include <avx512vlintrin.h>
#include <avx512vbmiintrin.h>
#include <avx512vbmi2intrin.h>
#include <avx512vpopcntdqintrin.h>
#endif #ifndef _blsr_u64
#define _blsr_u64(n) ((n - 1) & n)
#endif #endif
#endif #endif
#if !defined(CROARING_USENEON) && !defined(DISABLENEON) && defined(__ARM_NEON)
#define CROARING_USENEON
#endif
#if defined(CROARING_USENEON)
#include <arm_neon.h>
#endif
#if defined(__e2k__)
#define CROARING_IS_E2K 1
#endif
#if !CROARING_REGULAR_VISUAL_STUDIO && !defined(CROARING_IS_E2K)
#define CROARING_INLINE_ASM 1
#endif
#if CROARING_REGULAR_VISUAL_STUDIO
#include <intrin.h>
#ifndef __clang__
#define CROARING_INTRINSICS 1
inline int roaring_trailing_zeroes(unsigned long long input_num) {
unsigned long index;
#ifdef _WIN64
_BitScanForward64(&index, input_num);
#else
if ((uint32_t)input_num != 0) {
_BitScanForward(&index, (uint32_t)input_num);
} else {
_BitScanForward(&index, (uint32_t)(input_num >> 32));
index += 32;
}
#endif return index;
}
inline int roaring_leading_zeroes(unsigned long long input_num) {
unsigned long index;
#ifdef _WIN64
_BitScanReverse64(&index, input_num);
#else
if (input_num > 0xFFFFFFFF) {
_BitScanReverse(&index, (uint32_t)(input_num >> 32));
index += 32;
} else {
_BitScanReverse(&index, (uint32_t)(input_num));
}
#endif return 63 - index;
}
#define roaring_unreachable __assume(0)
#endif
#endif
#ifndef CROARING_INTRINSICS
#define CROARING_INTRINSICS 1
#define roaring_unreachable __builtin_unreachable()
inline int roaring_trailing_zeroes(unsigned long long input_num) {
return __builtin_ctzll(input_num);
}
inline int roaring_leading_zeroes(unsigned long long input_num) {
return __builtin_clzll(input_num);
}
#endif
#if CROARING_REGULAR_VISUAL_STUDIO
#define ALIGNED(x) __declspec(align(x))
#elif defined(__GNUC__) || defined(__clang__)
#define ALIGNED(x) __attribute__((aligned(x)))
#else
#warning "Warning. Unrecognized compiler."
#define ALIGNED(x)
#endif
#if defined(__GNUC__) || defined(__clang__)
#define CROARING_WARN_UNUSED __attribute__((warn_unused_result))
#else
#define CROARING_WARN_UNUSED
#endif
#define IS_BIG_ENDIAN (*(uint16_t *)"\0\xff" < 0x100)
#ifdef CROARING_USENEON
#elif (defined(_M_ARM) || defined(_M_ARM64)) && \
((defined(_WIN64) || defined(_WIN32)) && \
defined(CROARING_REGULAR_VISUAL_STUDIO) && \
CROARING_REGULAR_VISUAL_STUDIO)
static inline int roaring_hamming_backup(uint64_t x) {
uint64_t c1 = UINT64_C(0x5555555555555555);
uint64_t c2 = UINT64_C(0x3333333333333333);
uint64_t c4 = UINT64_C(0x0F0F0F0F0F0F0F0F);
x -= (x >> 1) & c1;
x = ((x >> 2) & c2) + (x & c2);
x = (x + (x >> 4)) & c4;
x *= UINT64_C(0x0101010101010101);
return x >> 56;
}
#endif
static inline int roaring_hamming(uint64_t x) {
#if defined(_WIN64) && defined(CROARING_REGULAR_VISUAL_STUDIO) && \
CROARING_REGULAR_VISUAL_STUDIO
#ifdef CROARING_USENEON
return vaddv_u8(vcnt_u8(vcreate_u8(input_num)));
#elif defined(_M_ARM64)
return roaring_hamming_backup(x);
#else
return (int)__popcnt64(x);
#endif #elif defined(_WIN32) && defined(CROARING_REGULAR_VISUAL_STUDIO) && \
CROARING_REGULAR_VISUAL_STUDIO
#ifdef _M_ARM
return roaring_hamming_backup(x);
#else
return (int)__popcnt((unsigned int)x) +
(int)__popcnt((unsigned int)(x >> 32));
#endif #else
return __builtin_popcountll(x);
#endif
}
#ifndef UINT64_C
#define UINT64_C(c) (c##ULL)
#endif
#ifndef UINT32_C
#define UINT32_C(c) (c##UL)
#endif
#ifdef __cplusplus
} #endif
#undef STRINGIFY_IMPLEMENTATION_
#undef STRINGIFY
#define STRINGIFY_IMPLEMENTATION_(a) #a
#define STRINGIFY(a) STRINGIFY_IMPLEMENTATION_(a)
#if CROARING_IS_X64
#ifdef __clang__
#define CROARING_TARGET_REGION(T) \
_Pragma(STRINGIFY(clang attribute push(__attribute__((target(T))), \
apply_to = function)))
#define CROARING_UNTARGET_REGION _Pragma("clang attribute pop")
#elif defined(__GNUC__)
#define CROARING_TARGET_REGION(T) \
_Pragma("GCC push_options") _Pragma(STRINGIFY(GCC target(T)))
#define CROARING_UNTARGET_REGION _Pragma("GCC pop_options")
#endif
#endif
#ifndef CROARING_TARGET_REGION
#define CROARING_TARGET_REGION(T)
#define CROARING_UNTARGET_REGION
#endif
#define CROARING_TARGET_AVX2 \
CROARING_TARGET_REGION("avx2,bmi,pclmul,lzcnt,popcnt")
#define CROARING_TARGET_AVX512 \
CROARING_TARGET_REGION( \
"avx2,bmi,bmi2,pclmul,lzcnt,popcnt,avx512f,avx512dq,avx512bw," \
"avx512vbmi2,avx512bitalg,avx512vpopcntdq")
#define CROARING_UNTARGET_AVX2 CROARING_UNTARGET_REGION
#define CROARING_UNTARGET_AVX512 CROARING_UNTARGET_REGION
#ifdef __AVX2__
#undef CROARING_TARGET_AVX2
#define CROARING_TARGET_AVX2
#undef CROARING_UNTARGET_AVX2
#define CROARING_UNTARGET_AVX2
#endif
#if defined(__AVX512F__) && defined(__AVX512DQ__) && defined(__AVX512BW__) && \
defined(__AVX512VBMI2__) && defined(__AVX512BITALG__) && \
defined(__AVX512VPOPCNTDQ__)
#undef CROARING_TARGET_AVX512
#define CROARING_TARGET_AVX512
#undef CROARING_UNTARGET_AVX512
#define CROARING_UNTARGET_AVX512
#endif
#if defined(__GNUC__) || defined(__clang__)
#define CROARING_ALLOW_UNALIGNED __attribute__((no_sanitize("alignment")))
#else
#define CROARING_ALLOW_UNALIGNED
#endif
#if defined(__BYTE_ORDER__) && defined(__ORDER_BIG_ENDIAN__)
#define CROARING_IS_BIG_ENDIAN (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
#elif defined(_WIN32)
#define CROARING_IS_BIG_ENDIAN 0
#else
#if defined(__APPLE__) || \
defined(__FreeBSD__)
#include <machine/endian.h>
#elif defined(sun) || \
defined(__sun)
#include <sys/byteorder.h>
#else
#ifdef __has_include
#if __has_include(<endian.h>)
#include <endian.h>
#endif #endif
#endif
#ifndef !defined(__BYTE_ORDER__) || !defined(__ORDER_LITTLE_ENDIAN__)
#define CROARING_IS_BIG_ENDIAN 0
#endif
#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
#define CROARING_IS_BIG_ENDIAN 0
#else
#define CROARING_IS_BIG_ENDIAN 1
#endif #endif
#if CROARING_IS_BIG_ENDIAN
#define croaring_htobe64(x) (x)
#elif defined(_WIN32) || defined(_WIN64)
#include <stdlib.h>
#define croaring_htobe64(x) _byteswap_uint64(x)
#elif defined(__APPLE__)
#include <libkern/OSByteOrder.h>
#define croaring_htobe64(x) OSSwapInt64(x)
#elif defined(__has_include) && \
__has_include( \
<byteswap.h>) && (defined(__linux__) || defined(__FreeBSD__))
#include <byteswap.h>
#if defined(__linux__)
#define croaring_htobe64(x) bswap_64(x)
#elif defined(__FreeBSD__)
#define croaring_htobe64(x) bswap64(x)
#else
#warning "Unknown platform, report as an error"
#endif
#else
#define croaring_htobe64(x) \
(((x & 0x00000000000000FFULL) << 56) | \
((x & 0x000000000000FF00ULL) << 40) | \
((x & 0x0000000000FF0000ULL) << 24) | \
((x & 0x00000000FF000000ULL) << 8) | ((x & 0x000000FF00000000ULL) >> 8) | \
((x & 0x0000FF0000000000ULL) >> 24) | \
((x & 0x00FF000000000000ULL) >> 40) | \
((x & 0xFF00000000000000ULL) >> 56))
#endif #define croaring_be64toh(x) croaring_htobe64(x)
#define CROARING_ATOMIC_IMPL_NONE 1
#define CROARING_ATOMIC_IMPL_CPP 2
#define CROARING_ATOMIC_IMPL_C 3
#define CROARING_ATOMIC_IMPL_C_WINDOWS 4
#if !defined(CROARING_ATOMIC_IMPL)
#if defined(__cplusplus) && __cplusplus >= 201103L
#ifdef __has_include
#if __has_include(<atomic>)
#define CROARING_ATOMIC_IMPL CROARING_ATOMIC_IMPL_CPP
#endif #else
#define CROARING_ATOMIC_IMPL CROARING_ATOMIC_IMPL_CPP
#endif #elif __STDC_VERSION__ >= 201112L && !defined(__STDC_NO_ATOMICS__)
#define CROARING_ATOMIC_IMPL CROARING_ATOMIC_IMPL_C
#elif CROARING_REGULAR_VISUAL_STUDIO
#define CROARING_ATOMIC_IMPL CROARING_ATOMIC_IMPL_C_WINDOWS
#endif
#endif
#if CROARING_ATOMIC_IMPL == CROARING_ATOMIC_IMPL_C
#include <stdatomic.h>
typedef _Atomic(uint32_t) croaring_refcount_t;
static inline void croaring_refcount_inc(croaring_refcount_t *val) {
atomic_fetch_add_explicit(val, 1, memory_order_relaxed);
}
static inline bool croaring_refcount_dec(croaring_refcount_t *val) {
bool is_zero = atomic_fetch_sub_explicit(val, 1, memory_order_release) == 1;
if (is_zero) {
atomic_thread_fence(memory_order_acquire);
}
return is_zero;
}
static inline uint32_t croaring_refcount_get(const croaring_refcount_t *val) {
return atomic_load_explicit(val, memory_order_relaxed);
}
#elif CROARING_ATOMIC_IMPL == CROARING_ATOMIC_IMPL_CPP
#include <atomic>
typedef std::atomic<uint32_t> croaring_refcount_t;
static inline void croaring_refcount_inc(croaring_refcount_t *val) {
val->fetch_add(1, std::memory_order_relaxed);
}
static inline bool croaring_refcount_dec(croaring_refcount_t *val) {
bool is_zero = val->fetch_sub(1, std::memory_order_release) == 1;
if (is_zero) {
std::atomic_thread_fence(std::memory_order_acquire);
}
return is_zero;
}
static inline uint32_t croaring_refcount_get(const croaring_refcount_t *val) {
return val->load(std::memory_order_relaxed);
}
#elif CROARING_ATOMIC_IMPL == CROARING_ATOMIC_IMPL_C_WINDOWS
#include <intrin.h>
#pragma intrinsic(_InterlockedIncrement)
#pragma intrinsic(_InterlockedDecrement)
typedef volatile long croaring_refcount_t;
static inline void croaring_refcount_inc(croaring_refcount_t *val) {
_InterlockedIncrement(val);
}
static inline bool croaring_refcount_dec(croaring_refcount_t *val) {
return _InterlockedDecrement(val) == 0;
}
static inline uint32_t croaring_refcount_get(const croaring_refcount_t *val) {
return *val;
}
#elif CROARING_ATOMIC_IMPL == CROARING_ATOMIC_IMPL_NONE
#include <assert.h>
typedef uint32_t croaring_refcount_t;
static inline void croaring_refcount_inc(croaring_refcount_t *val) {
*val += 1;
}
static inline bool croaring_refcount_dec(croaring_refcount_t *val) {
assert(*val > 0);
*val -= 1;
return val == 0;
}
static inline uint32_t croaring_refcount_get(const croaring_refcount_t *val) {
return *val;
}
#else
#error "Unknown atomic implementation"
#endif
#if defined(__GNUC__) || defined(__clang__)
#define CROARING_DEPRECATED __attribute__((deprecated))
#elif defined(_MSC_VER)
#define CROARING_DEPRECATED __declspec(deprecated)
#else
#define CROARING_DEPRECATED
#endif
#if __cplusplus
#define CROARING_ZERO_INITIALIZER \
{}
#else
#define CROARING_ZERO_INITIALIZER \
{ 0 }
#endif
#if defined(__cplusplus)
#define CROARING_STATIC_ASSERT(x, y) static_assert(x, y)
#else
#define CROARING_STATIC_ASSERT(x, y) _Static_assert(x, y)
#endif
#endif
#ifndef ROARING_ISADETECTION_H
#define ROARING_ISADETECTION_H
#if defined(__x86_64__) || defined(_M_AMD64)
#ifndef CROARING_COMPILER_SUPPORTS_AVX512
#ifdef __has_include
#if __has_include(<avx512vbmi2intrin.h>)
#define CROARING_COMPILER_SUPPORTS_AVX512 1
#endif #endif
#ifdef _MSC_VER
#if _MSC_VER >= 1920
#define CROARING_COMPILER_SUPPORTS_AVX512 1
#endif #endif
#ifndef CROARING_COMPILER_SUPPORTS_AVX512
#define CROARING_COMPILER_SUPPORTS_AVX512 0
#endif #endif
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
enum {
ROARING_SUPPORTS_AVX2 = 1,
ROARING_SUPPORTS_AVX512 = 2,
};
int croaring_hardware_support(void);
#ifdef __cplusplus
}
}
} #endif
#endif #endif
#ifndef ROARING_TYPES_H
#define ROARING_TYPES_H
#include <stdbool.h>
#include <stdint.h>
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace api {
#endif
#if defined(__cplusplus)
extern "C++" {
struct container_s {};
}
#define ROARING_CONTAINER_T ::roaring::api::container_s
#else
#define ROARING_CONTAINER_T void
#endif
#define ROARING_FLAG_COW UINT8_C(0x1)
#define ROARING_FLAG_FROZEN UINT8_C(0x2)
typedef struct roaring_array_s {
int32_t size;
int32_t allocation_size;
ROARING_CONTAINER_T **containers; uint16_t *keys;
uint8_t *typecodes;
uint8_t flags;
} roaring_array_t;
typedef bool (*roaring_iterator)(uint32_t value, void *param);
typedef bool (*roaring_iterator64)(uint64_t value, void *param);
typedef struct roaring_statistics_s {
uint32_t n_containers;
uint32_t n_array_containers;
uint32_t n_run_containers;
uint32_t n_bitset_containers;
uint32_t
n_values_array_containers;
uint32_t n_values_run_containers;
uint32_t
n_values_bitset_containers;
uint32_t n_bytes_array_containers;
uint32_t n_bytes_run_containers;
uint32_t n_bytes_bitset_containers;
uint32_t
max_value;
uint32_t
min_value;
CROARING_DEPRECATED
uint64_t sum_value;
uint64_t cardinality;
} roaring_statistics_t;
typedef struct roaring64_statistics_s {
uint64_t n_containers;
uint64_t n_array_containers;
uint64_t n_run_containers;
uint64_t n_bitset_containers;
uint64_t
n_values_array_containers;
uint64_t n_values_run_containers;
uint64_t
n_values_bitset_containers;
uint64_t n_bytes_array_containers;
uint64_t n_bytes_run_containers;
uint64_t n_bytes_bitset_containers;
uint64_t
max_value;
uint64_t
min_value;
uint64_t cardinality;
} roaring64_statistics_t;
typedef struct roaring_container_iterator_s {
int32_t index;
} roaring_container_iterator_t;
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef CROARING_CBITSET_BITSET_H
#define CROARING_CBITSET_BITSET_H
#ifdef __cplusplus
#define CROARING_CBITSET_RESTRICT
#elif (__STDC_VERSION__ >= 199901L) || \
(defined(__GNUC__) && defined(__STDC_VERSION__))
#define CROARING_CBITSET_RESTRICT restrict
#else
#define CROARING_CBITSET_RESTRICT
#endif
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace api {
#endif
struct bitset_s {
uint64_t *CROARING_CBITSET_RESTRICT array;
size_t arraysize;
size_t capacity;
};
typedef struct bitset_s bitset_t;
bitset_t *bitset_create(void);
bitset_t *bitset_create_with_capacity(size_t size);
void bitset_free(bitset_t *bitset);
void bitset_clear(bitset_t *bitset);
void bitset_fill(bitset_t *bitset);
bitset_t *bitset_copy(const bitset_t *bitset);
bool bitset_resize(bitset_t *bitset, size_t newarraysize, bool padwithzeroes);
inline size_t bitset_size_in_bytes(const bitset_t *bitset) {
return bitset->arraysize * sizeof(uint64_t);
}
inline size_t bitset_size_in_bits(const bitset_t *bitset) {
return bitset->arraysize * 64;
}
inline size_t bitset_size_in_words(const bitset_t *bitset) {
return bitset->arraysize;
}
bool bitset_grow(bitset_t *bitset, size_t newarraysize);
bool bitset_trim(bitset_t *bitset);
void bitset_shift_left(bitset_t *bitset, size_t s);
void bitset_shift_right(bitset_t *bitset, size_t s);
inline void bitset_set(bitset_t *bitset, size_t i) {
size_t shiftedi = i / 64;
if (shiftedi >= bitset->arraysize) {
if (!bitset_grow(bitset, shiftedi + 1)) {
return;
}
}
bitset->array[shiftedi] |= ((uint64_t)1) << (i % 64);
}
inline void bitset_set_to_value(bitset_t *bitset, size_t i, bool flag) {
size_t shiftedi = i / 64;
uint64_t mask = ((uint64_t)1) << (i % 64);
uint64_t dynmask = ((uint64_t)flag) << (i % 64);
if (shiftedi >= bitset->arraysize) {
if (!bitset_grow(bitset, shiftedi + 1)) {
return;
}
}
uint64_t w = bitset->array[shiftedi];
w &= ~mask;
w |= dynmask;
bitset->array[shiftedi] = w;
}
inline bool bitset_get(const bitset_t *bitset, size_t i) {
size_t shiftedi = i / 64;
if (shiftedi >= bitset->arraysize) {
return false;
}
return (bitset->array[shiftedi] & (((uint64_t)1) << (i % 64))) != 0;
}
size_t bitset_count(const bitset_t *bitset);
bool bitset_empty(const bitset_t *bitset);
size_t bitset_minimum(const bitset_t *bitset);
size_t bitset_maximum(const bitset_t *bitset);
bool bitset_inplace_union(bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2);
size_t bitset_union_count(const bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2);
void bitset_inplace_intersection(bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2);
size_t bitset_intersection_count(const bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2);
bool bitsets_disjoint(const bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2);
bool bitsets_intersect(const bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2);
bool bitset_contains_all(const bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2);
void bitset_inplace_difference(bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2);
size_t bitset_difference_count(const bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2);
bool bitset_inplace_symmetric_difference(
bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2);
size_t bitset_symmetric_difference_count(
const bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2);
inline bool bitset_next_set_bit(const bitset_t *bitset, size_t *i) {
size_t x = *i / 64;
if (x >= bitset->arraysize) {
return false;
}
uint64_t w = bitset->array[x];
w >>= (*i & 63);
if (w != 0) {
*i += roaring_trailing_zeroes(w);
return true;
}
x++;
while (x < bitset->arraysize) {
w = bitset->array[x];
if (w != 0) {
*i = x * 64 + roaring_trailing_zeroes(w);
return true;
}
x++;
}
return false;
}
inline size_t bitset_next_set_bits(const bitset_t *bitset, size_t *buffer,
size_t capacity, size_t *startfrom) {
if (capacity == 0) return 0; size_t x = *startfrom / 64;
if (x >= bitset->arraysize) {
return 0; }
uint64_t w = bitset->array[x];
w &= ~((UINT64_C(1) << (*startfrom & 63)) - 1);
size_t howmany = 0;
size_t base = x << 6;
while (howmany < capacity) {
while (w != 0) {
uint64_t t = w & (~w + 1);
int r = roaring_trailing_zeroes(w);
buffer[howmany++] = r + base;
if (howmany == capacity) goto end;
w ^= t;
}
x += 1;
if (x == bitset->arraysize) {
break;
}
base += 64;
w = bitset->array[x];
}
end:
if (howmany > 0) {
*startfrom = buffer[howmany - 1];
}
return howmany;
}
typedef bool (*bitset_iterator)(size_t value, void *param);
inline bool bitset_for_each(const bitset_t *b, bitset_iterator iterator,
void *ptr) {
size_t base = 0;
for (size_t i = 0; i < b->arraysize; ++i) {
uint64_t w = b->array[i];
while (w != 0) {
uint64_t t = w & (~w + 1);
int r = roaring_trailing_zeroes(w);
if (!iterator(r + base, ptr)) return false;
w ^= t;
}
base += 64;
}
return true;
}
inline void bitset_print(const bitset_t *b) {
printf("{");
for (size_t i = 0; bitset_next_set_bit(b, &i); i++) {
printf("%zu, ", i);
}
printf("}");
}
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef INCLUDE_CONTAINERS_CONTAINER_DEFS_H_
#define INCLUDE_CONTAINERS_CONTAINER_DEFS_H_
#ifdef __cplusplus
#include <type_traits>
#endif
#ifdef __cplusplus
namespace roaring {
namespace internal { #endif
typedef ROARING_CONTAINER_T container_t;
#if defined(__cplusplus)
#define STRUCT_CONTAINER(name) struct name : public container_t
#else
#define STRUCT_CONTAINER(name) struct name
#endif
#ifdef __cplusplus
#define CAST(type, value) static_cast<type>(value)
#define movable_CAST(type, value) movable_CAST_HELPER<type>(value)
template <typename PPDerived, typename Base>
PPDerived movable_CAST_HELPER(Base **ptr_to_ptr) {
typedef typename std::remove_pointer<PPDerived>::type PDerived;
typedef typename std::remove_pointer<PDerived>::type Derived;
static_assert(std::is_base_of<Base, Derived>::value,
"use movable_CAST() for container_t** => xxx_container_t**");
return reinterpret_cast<Derived **>(ptr_to_ptr);
}
#else
#define CAST(type, value) ((type)value)
#define movable_CAST(type, value) ((type)value)
#endif
#define movable_CAST_base(c) movable_CAST(container_t **, c)
#ifdef __cplusplus
}
} #endif
#endif
#ifndef CROARING_ARRAY_UTIL_H
#define CROARING_ARRAY_UTIL_H
#include <stddef.h>
#include <stdint.h>
#if CROARING_IS_X64
#ifndef CROARING_COMPILER_SUPPORTS_AVX512
#error "CROARING_COMPILER_SUPPORTS_AVX512 needs to be defined."
#endif #endif
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wuninitialized"
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
inline int32_t binarySearch(const uint16_t *array, int32_t lenarray,
uint16_t ikey) {
int32_t low = 0;
int32_t high = lenarray - 1;
while (low <= high) {
int32_t middleIndex = (low + high) >> 1;
uint16_t middleValue = array[middleIndex];
if (middleValue < ikey) {
low = middleIndex + 1;
} else if (middleValue > ikey) {
high = middleIndex - 1;
} else {
return middleIndex;
}
}
return -(low + 1);
}
static inline int32_t advanceUntil(const uint16_t *array, int32_t pos,
int32_t length, uint16_t min) {
int32_t lower = pos + 1;
if ((lower >= length) || (array[lower] >= min)) {
return lower;
}
int32_t spansize = 1;
while ((lower + spansize < length) && (array[lower + spansize] < min)) {
spansize <<= 1;
}
int32_t upper = (lower + spansize < length) ? lower + spansize : length - 1;
if (array[upper] == min) {
return upper;
}
if (array[upper] < min) {
return length;
}
lower += (spansize >> 1);
int32_t mid = 0;
while (lower + 1 != upper) {
mid = (lower + upper) >> 1;
if (array[mid] == min) {
return mid;
} else if (array[mid] < min) {
lower = mid;
} else {
upper = mid;
}
}
return upper;
}
static inline int32_t count_less(const uint16_t *array, int32_t lenarray,
uint16_t ikey) {
if (lenarray == 0) return 0;
int32_t pos = binarySearch(array, lenarray, ikey);
return pos >= 0 ? pos : -(pos + 1);
}
static inline int32_t count_greater(const uint16_t *array, int32_t lenarray,
uint16_t ikey) {
if (lenarray == 0) return 0;
int32_t pos = binarySearch(array, lenarray, ikey);
if (pos >= 0) {
return lenarray - (pos + 1);
} else {
return lenarray - (-pos - 1);
}
}
int32_t intersect_vector16(const uint16_t *__restrict__ A, size_t s_a,
const uint16_t *__restrict__ B, size_t s_b,
uint16_t *C);
int32_t intersect_vector16_inplace(uint16_t *__restrict__ A, size_t s_a,
const uint16_t *__restrict__ B, size_t s_b);
int array_container_to_uint32_array_vector16(void *vout, const uint16_t *array,
size_t cardinality, uint32_t base);
#if CROARING_COMPILER_SUPPORTS_AVX512
int avx512_array_container_to_uint32_array(void *vout, const uint16_t *array,
size_t cardinality, uint32_t base);
#endif
int32_t intersect_vector16_cardinality(const uint16_t *__restrict__ A,
size_t s_a,
const uint16_t *__restrict__ B,
size_t s_b);
int32_t intersect_skewed_uint16(const uint16_t *smallarray, size_t size_s,
const uint16_t *largearray, size_t size_l,
uint16_t *buffer);
int32_t intersect_skewed_uint16_cardinality(const uint16_t *smallarray,
size_t size_s,
const uint16_t *largearray,
size_t size_l);
bool intersect_skewed_uint16_nonempty(const uint16_t *smallarray, size_t size_s,
const uint16_t *largearray,
size_t size_l);
int32_t intersect_uint16(const uint16_t *A, const size_t lenA,
const uint16_t *B, const size_t lenB, uint16_t *out);
int32_t intersect_uint16_cardinality(const uint16_t *A, const size_t lenA,
const uint16_t *B, const size_t lenB);
bool intersect_uint16_nonempty(const uint16_t *A, const size_t lenA,
const uint16_t *B, const size_t lenB);
size_t union_uint16(const uint16_t *set_1, size_t size_1, const uint16_t *set_2,
size_t size_2, uint16_t *buffer);
int32_t xor_uint16(const uint16_t *array_1, int32_t card_1,
const uint16_t *array_2, int32_t card_2, uint16_t *out);
int difference_uint16(const uint16_t *a1, int length1, const uint16_t *a2,
int length2, uint16_t *a_out);
size_t intersection_uint32(const uint32_t *A, const size_t lenA,
const uint32_t *B, const size_t lenB, uint32_t *out);
size_t intersection_uint32_card(const uint32_t *A, const size_t lenA,
const uint32_t *B, const size_t lenB);
size_t union_uint32(const uint32_t *set_1, size_t size_1, const uint32_t *set_2,
size_t size_2, uint32_t *buffer);
uint32_t union_vector16(const uint16_t *__restrict__ set_1, uint32_t size_1,
const uint16_t *__restrict__ set_2, uint32_t size_2,
uint16_t *__restrict__ buffer);
uint32_t xor_vector16(const uint16_t *__restrict__ array1, uint32_t length1,
const uint16_t *__restrict__ array2, uint32_t length2,
uint16_t *__restrict__ output);
int32_t difference_vector16(const uint16_t *__restrict__ A, size_t s_a,
const uint16_t *__restrict__ B, size_t s_b,
uint16_t *C);
size_t union_uint32_card(const uint32_t *set_1, size_t size_1,
const uint32_t *set_2, size_t size_2);
size_t fast_union_uint16(const uint16_t *set_1, size_t size_1,
const uint16_t *set_2, size_t size_2,
uint16_t *buffer);
bool memequals(const void *s1, const void *s2, size_t n);
#ifdef __cplusplus
}
}
} #endif
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic pop
#endif
#endif
#ifndef CROARING_BITSET_UTIL_H
#define CROARING_BITSET_UTIL_H
#include <stdint.h>
#if CROARING_IS_X64
#ifndef CROARING_COMPILER_SUPPORTS_AVX512
#error "CROARING_COMPILER_SUPPORTS_AVX512 needs to be defined."
#endif #endif
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wuninitialized"
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
static inline void bitset_set_range(uint64_t *words, uint32_t start,
uint32_t end) {
if (start == end) return;
uint32_t firstword = start / 64;
uint32_t endword = (end - 1) / 64;
if (firstword == endword) {
words[firstword] |= ((~UINT64_C(0)) << (start % 64)) &
((~UINT64_C(0)) >> ((~end + 1) % 64));
return;
}
words[firstword] |= (~UINT64_C(0)) << (start % 64);
for (uint32_t i = firstword + 1; i < endword; i++) {
words[i] = ~UINT64_C(0);
}
words[endword] |= (~UINT64_C(0)) >> ((~end + 1) % 64);
}
static inline int bitset_lenrange_cardinality(const uint64_t *words,
uint32_t start,
uint32_t lenminusone) {
uint32_t firstword = start / 64;
uint32_t endword = (start + lenminusone) / 64;
if (firstword == endword) {
return roaring_hamming(words[firstword] &
((~UINT64_C(0)) >> ((63 - lenminusone) % 64))
<< (start % 64));
}
int answer =
roaring_hamming(words[firstword] & ((~UINT64_C(0)) << (start % 64)));
for (uint32_t i = firstword + 1; i < endword; i++) {
answer += roaring_hamming(words[i]);
}
answer += roaring_hamming(words[endword] &
(~UINT64_C(0)) >>
(((~start + 1) - lenminusone - 1) % 64));
return answer;
}
static inline bool bitset_lenrange_empty(const uint64_t *words, uint32_t start,
uint32_t lenminusone) {
uint32_t firstword = start / 64;
uint32_t endword = (start + lenminusone) / 64;
if (firstword == endword) {
return (words[firstword] & ((~UINT64_C(0)) >> ((63 - lenminusone) % 64))
<< (start % 64)) == 0;
}
if (((words[firstword] & ((~UINT64_C(0)) << (start % 64)))) != 0) {
return false;
}
for (uint32_t i = firstword + 1; i < endword; i++) {
if (words[i] != 0) {
return false;
}
}
if ((words[endword] &
(~UINT64_C(0)) >> (((~start + 1) - lenminusone - 1) % 64)) != 0) {
return false;
}
return true;
}
static inline void bitset_set_lenrange(uint64_t *words, uint32_t start,
uint32_t lenminusone) {
uint32_t firstword = start / 64;
uint32_t endword = (start + lenminusone) / 64;
if (firstword == endword) {
words[firstword] |= ((~UINT64_C(0)) >> ((63 - lenminusone) % 64))
<< (start % 64);
return;
}
uint64_t temp = words[endword];
words[firstword] |= (~UINT64_C(0)) << (start % 64);
for (uint32_t i = firstword + 1; i < endword; i += 2)
words[i] = words[i + 1] = ~UINT64_C(0);
words[endword] =
temp | (~UINT64_C(0)) >> (((~start + 1) - lenminusone - 1) % 64);
}
static inline void bitset_flip_range(uint64_t *words, uint32_t start,
uint32_t end) {
if (start == end) return;
uint32_t firstword = start / 64;
uint32_t endword = (end - 1) / 64;
words[firstword] ^= ~((~UINT64_C(0)) << (start % 64));
for (uint32_t i = firstword; i < endword; i++) {
words[i] = ~words[i];
}
words[endword] ^= ((~UINT64_C(0)) >> ((~end + 1) % 64));
}
static inline void bitset_reset_range(uint64_t *words, uint32_t start,
uint32_t end) {
if (start == end) return;
uint32_t firstword = start / 64;
uint32_t endword = (end - 1) / 64;
if (firstword == endword) {
words[firstword] &= ~(((~UINT64_C(0)) << (start % 64)) &
((~UINT64_C(0)) >> ((~end + 1) % 64)));
return;
}
words[firstword] &= ~((~UINT64_C(0)) << (start % 64));
for (uint32_t i = firstword + 1; i < endword; i++) {
words[i] = UINT64_C(0);
}
words[endword] &= ~((~UINT64_C(0)) >> ((~end + 1) % 64));
}
size_t bitset_extract_setbits_avx2(const uint64_t *words, size_t length,
uint32_t *out, size_t outcapacity,
uint32_t base);
size_t bitset_extract_setbits_avx512(const uint64_t *words, size_t length,
uint32_t *out, size_t outcapacity,
uint32_t base);
size_t bitset_extract_setbits(const uint64_t *words, size_t length,
uint32_t *out, uint32_t base);
size_t bitset_extract_setbits_sse_uint16(const uint64_t *words, size_t length,
uint16_t *out, size_t outcapacity,
uint16_t base);
size_t bitset_extract_setbits_avx512_uint16(const uint64_t *words,
size_t length, uint16_t *out,
size_t outcapacity, uint16_t base);
size_t bitset_extract_setbits_uint16(const uint64_t *words, size_t length,
uint16_t *out, uint16_t base);
size_t bitset_extract_intersection_setbits_uint16(
const uint64_t *__restrict__ words1, const uint64_t *__restrict__ words2,
size_t length, uint16_t *out, uint16_t base);
uint64_t bitset_set_list_withcard(uint64_t *words, uint64_t card,
const uint16_t *list, uint64_t length);
void bitset_set_list(uint64_t *words, const uint16_t *list, uint64_t length);
uint64_t bitset_clear_list(uint64_t *words, uint64_t card, const uint16_t *list,
uint64_t length);
uint64_t bitset_flip_list_withcard(uint64_t *words, uint64_t card,
const uint16_t *list, uint64_t length);
void bitset_flip_list(uint64_t *words, const uint16_t *list, uint64_t length);
#if CROARING_IS_X64
CROARING_TARGET_AVX2
static inline __m256i popcount256(__m256i v) {
const __m256i lookuppos = _mm256_setr_epi8(
4 + 0, 4 + 1, 4 + 1, 4 + 2,
4 + 1, 4 + 2, 4 + 2, 4 + 3,
4 + 1, 4 + 2, 4 + 2, 4 + 3,
4 + 2, 4 + 3, 4 + 3, 4 + 4,
4 + 0, 4 + 1, 4 + 1, 4 + 2,
4 + 1, 4 + 2, 4 + 2, 4 + 3,
4 + 1, 4 + 2, 4 + 2, 4 + 3,
4 + 2, 4 + 3, 4 + 3, 4 + 4);
const __m256i lookupneg = _mm256_setr_epi8(
4 - 0, 4 - 1, 4 - 1, 4 - 2,
4 - 1, 4 - 2, 4 - 2, 4 - 3,
4 - 1, 4 - 2, 4 - 2, 4 - 3,
4 - 2, 4 - 3, 4 - 3, 4 - 4,
4 - 0, 4 - 1, 4 - 1, 4 - 2,
4 - 1, 4 - 2, 4 - 2, 4 - 3,
4 - 1, 4 - 2, 4 - 2, 4 - 3,
4 - 2, 4 - 3, 4 - 3, 4 - 4);
const __m256i low_mask = _mm256_set1_epi8(0x0f);
const __m256i lo = _mm256_and_si256(v, low_mask);
const __m256i hi = _mm256_and_si256(_mm256_srli_epi16(v, 4), low_mask);
const __m256i popcnt1 = _mm256_shuffle_epi8(lookuppos, lo);
const __m256i popcnt2 = _mm256_shuffle_epi8(lookupneg, hi);
return _mm256_sad_epu8(popcnt1, popcnt2);
}
CROARING_UNTARGET_AVX2
CROARING_TARGET_AVX2
static inline void CSA(__m256i *h, __m256i *l, __m256i a, __m256i b,
__m256i c) {
const __m256i u = _mm256_xor_si256(a, b);
*h = _mm256_or_si256(_mm256_and_si256(a, b), _mm256_and_si256(u, c));
*l = _mm256_xor_si256(u, c);
}
CROARING_UNTARGET_AVX2
CROARING_TARGET_AVX2
inline static uint64_t avx2_harley_seal_popcount256(const __m256i *data,
const uint64_t size) {
__m256i total = _mm256_setzero_si256();
__m256i ones = _mm256_setzero_si256();
__m256i twos = _mm256_setzero_si256();
__m256i fours = _mm256_setzero_si256();
__m256i eights = _mm256_setzero_si256();
__m256i sixteens = _mm256_setzero_si256();
__m256i twosA, twosB, foursA, foursB, eightsA, eightsB;
const uint64_t limit = size - size % 16;
uint64_t i = 0;
for (; i < limit; i += 16) {
CSA(&twosA, &ones, ones, _mm256_lddqu_si256(data + i),
_mm256_lddqu_si256(data + i + 1));
CSA(&twosB, &ones, ones, _mm256_lddqu_si256(data + i + 2),
_mm256_lddqu_si256(data + i + 3));
CSA(&foursA, &twos, twos, twosA, twosB);
CSA(&twosA, &ones, ones, _mm256_lddqu_si256(data + i + 4),
_mm256_lddqu_si256(data + i + 5));
CSA(&twosB, &ones, ones, _mm256_lddqu_si256(data + i + 6),
_mm256_lddqu_si256(data + i + 7));
CSA(&foursB, &twos, twos, twosA, twosB);
CSA(&eightsA, &fours, fours, foursA, foursB);
CSA(&twosA, &ones, ones, _mm256_lddqu_si256(data + i + 8),
_mm256_lddqu_si256(data + i + 9));
CSA(&twosB, &ones, ones, _mm256_lddqu_si256(data + i + 10),
_mm256_lddqu_si256(data + i + 11));
CSA(&foursA, &twos, twos, twosA, twosB);
CSA(&twosA, &ones, ones, _mm256_lddqu_si256(data + i + 12),
_mm256_lddqu_si256(data + i + 13));
CSA(&twosB, &ones, ones, _mm256_lddqu_si256(data + i + 14),
_mm256_lddqu_si256(data + i + 15));
CSA(&foursB, &twos, twos, twosA, twosB);
CSA(&eightsB, &fours, fours, foursA, foursB);
CSA(&sixteens, &eights, eights, eightsA, eightsB);
total = _mm256_add_epi64(total, popcount256(sixteens));
}
total = _mm256_slli_epi64(total, 4); total = _mm256_add_epi64(
total, _mm256_slli_epi64(popcount256(eights), 3)); total = _mm256_add_epi64(
total, _mm256_slli_epi64(popcount256(fours), 2)); total = _mm256_add_epi64(
total, _mm256_slli_epi64(popcount256(twos), 1)); total = _mm256_add_epi64(total, popcount256(ones));
for (; i < size; i++)
total =
_mm256_add_epi64(total, popcount256(_mm256_lddqu_si256(data + i)));
return (uint64_t)(_mm256_extract_epi64(total, 0)) +
(uint64_t)(_mm256_extract_epi64(total, 1)) +
(uint64_t)(_mm256_extract_epi64(total, 2)) +
(uint64_t)(_mm256_extract_epi64(total, 3));
}
CROARING_UNTARGET_AVX2
#define CROARING_AVXPOPCNTFNC(opname, avx_intrinsic) \
static inline uint64_t avx2_harley_seal_popcount256_##opname( \
const __m256i *data1, const __m256i *data2, const uint64_t size) { \
__m256i total = _mm256_setzero_si256(); \
__m256i ones = _mm256_setzero_si256(); \
__m256i twos = _mm256_setzero_si256(); \
__m256i fours = _mm256_setzero_si256(); \
__m256i eights = _mm256_setzero_si256(); \
__m256i sixteens = _mm256_setzero_si256(); \
__m256i twosA, twosB, foursA, foursB, eightsA, eightsB; \
__m256i A1, A2; \
const uint64_t limit = size - size % 16; \
uint64_t i = 0; \
for (; i < limit; i += 16) { \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i), \
_mm256_lddqu_si256(data2 + i)); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 1), \
_mm256_lddqu_si256(data2 + i + 1)); \
CSA(&twosA, &ones, ones, A1, A2); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 2), \
_mm256_lddqu_si256(data2 + i + 2)); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 3), \
_mm256_lddqu_si256(data2 + i + 3)); \
CSA(&twosB, &ones, ones, A1, A2); \
CSA(&foursA, &twos, twos, twosA, twosB); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 4), \
_mm256_lddqu_si256(data2 + i + 4)); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 5), \
_mm256_lddqu_si256(data2 + i + 5)); \
CSA(&twosA, &ones, ones, A1, A2); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 6), \
_mm256_lddqu_si256(data2 + i + 6)); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 7), \
_mm256_lddqu_si256(data2 + i + 7)); \
CSA(&twosB, &ones, ones, A1, A2); \
CSA(&foursB, &twos, twos, twosA, twosB); \
CSA(&eightsA, &fours, fours, foursA, foursB); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 8), \
_mm256_lddqu_si256(data2 + i + 8)); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 9), \
_mm256_lddqu_si256(data2 + i + 9)); \
CSA(&twosA, &ones, ones, A1, A2); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 10), \
_mm256_lddqu_si256(data2 + i + 10)); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 11), \
_mm256_lddqu_si256(data2 + i + 11)); \
CSA(&twosB, &ones, ones, A1, A2); \
CSA(&foursA, &twos, twos, twosA, twosB); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 12), \
_mm256_lddqu_si256(data2 + i + 12)); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 13), \
_mm256_lddqu_si256(data2 + i + 13)); \
CSA(&twosA, &ones, ones, A1, A2); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 14), \
_mm256_lddqu_si256(data2 + i + 14)); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 15), \
_mm256_lddqu_si256(data2 + i + 15)); \
CSA(&twosB, &ones, ones, A1, A2); \
CSA(&foursB, &twos, twos, twosA, twosB); \
CSA(&eightsB, &fours, fours, foursA, foursB); \
CSA(&sixteens, &eights, eights, eightsA, eightsB); \
total = _mm256_add_epi64(total, popcount256(sixteens)); \
} \
total = _mm256_slli_epi64(total, 4); \
total = _mm256_add_epi64(total, \
_mm256_slli_epi64(popcount256(eights), 3)); \
total = \
_mm256_add_epi64(total, _mm256_slli_epi64(popcount256(fours), 2)); \
total = \
_mm256_add_epi64(total, _mm256_slli_epi64(popcount256(twos), 1)); \
total = _mm256_add_epi64(total, popcount256(ones)); \
for (; i < size; i++) { \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i), \
_mm256_lddqu_si256(data2 + i)); \
total = _mm256_add_epi64(total, popcount256(A1)); \
} \
return (uint64_t)(_mm256_extract_epi64(total, 0)) + \
(uint64_t)(_mm256_extract_epi64(total, 1)) + \
(uint64_t)(_mm256_extract_epi64(total, 2)) + \
(uint64_t)(_mm256_extract_epi64(total, 3)); \
} \
static inline uint64_t avx2_harley_seal_popcount256andstore_##opname( \
const __m256i *__restrict__ data1, const __m256i *__restrict__ data2, \
__m256i *__restrict__ out, const uint64_t size) { \
__m256i total = _mm256_setzero_si256(); \
__m256i ones = _mm256_setzero_si256(); \
__m256i twos = _mm256_setzero_si256(); \
__m256i fours = _mm256_setzero_si256(); \
__m256i eights = _mm256_setzero_si256(); \
__m256i sixteens = _mm256_setzero_si256(); \
__m256i twosA, twosB, foursA, foursB, eightsA, eightsB; \
__m256i A1, A2; \
const uint64_t limit = size - size % 16; \
uint64_t i = 0; \
for (; i < limit; i += 16) { \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i), \
_mm256_lddqu_si256(data2 + i)); \
_mm256_storeu_si256(out + i, A1); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 1), \
_mm256_lddqu_si256(data2 + i + 1)); \
_mm256_storeu_si256(out + i + 1, A2); \
CSA(&twosA, &ones, ones, A1, A2); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 2), \
_mm256_lddqu_si256(data2 + i + 2)); \
_mm256_storeu_si256(out + i + 2, A1); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 3), \
_mm256_lddqu_si256(data2 + i + 3)); \
_mm256_storeu_si256(out + i + 3, A2); \
CSA(&twosB, &ones, ones, A1, A2); \
CSA(&foursA, &twos, twos, twosA, twosB); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 4), \
_mm256_lddqu_si256(data2 + i + 4)); \
_mm256_storeu_si256(out + i + 4, A1); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 5), \
_mm256_lddqu_si256(data2 + i + 5)); \
_mm256_storeu_si256(out + i + 5, A2); \
CSA(&twosA, &ones, ones, A1, A2); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 6), \
_mm256_lddqu_si256(data2 + i + 6)); \
_mm256_storeu_si256(out + i + 6, A1); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 7), \
_mm256_lddqu_si256(data2 + i + 7)); \
_mm256_storeu_si256(out + i + 7, A2); \
CSA(&twosB, &ones, ones, A1, A2); \
CSA(&foursB, &twos, twos, twosA, twosB); \
CSA(&eightsA, &fours, fours, foursA, foursB); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 8), \
_mm256_lddqu_si256(data2 + i + 8)); \
_mm256_storeu_si256(out + i + 8, A1); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 9), \
_mm256_lddqu_si256(data2 + i + 9)); \
_mm256_storeu_si256(out + i + 9, A2); \
CSA(&twosA, &ones, ones, A1, A2); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 10), \
_mm256_lddqu_si256(data2 + i + 10)); \
_mm256_storeu_si256(out + i + 10, A1); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 11), \
_mm256_lddqu_si256(data2 + i + 11)); \
_mm256_storeu_si256(out + i + 11, A2); \
CSA(&twosB, &ones, ones, A1, A2); \
CSA(&foursA, &twos, twos, twosA, twosB); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 12), \
_mm256_lddqu_si256(data2 + i + 12)); \
_mm256_storeu_si256(out + i + 12, A1); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 13), \
_mm256_lddqu_si256(data2 + i + 13)); \
_mm256_storeu_si256(out + i + 13, A2); \
CSA(&twosA, &ones, ones, A1, A2); \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 14), \
_mm256_lddqu_si256(data2 + i + 14)); \
_mm256_storeu_si256(out + i + 14, A1); \
A2 = avx_intrinsic(_mm256_lddqu_si256(data1 + i + 15), \
_mm256_lddqu_si256(data2 + i + 15)); \
_mm256_storeu_si256(out + i + 15, A2); \
CSA(&twosB, &ones, ones, A1, A2); \
CSA(&foursB, &twos, twos, twosA, twosB); \
CSA(&eightsB, &fours, fours, foursA, foursB); \
CSA(&sixteens, &eights, eights, eightsA, eightsB); \
total = _mm256_add_epi64(total, popcount256(sixteens)); \
} \
total = _mm256_slli_epi64(total, 4); \
total = _mm256_add_epi64(total, \
_mm256_slli_epi64(popcount256(eights), 3)); \
total = \
_mm256_add_epi64(total, _mm256_slli_epi64(popcount256(fours), 2)); \
total = \
_mm256_add_epi64(total, _mm256_slli_epi64(popcount256(twos), 1)); \
total = _mm256_add_epi64(total, popcount256(ones)); \
for (; i < size; i++) { \
A1 = avx_intrinsic(_mm256_lddqu_si256(data1 + i), \
_mm256_lddqu_si256(data2 + i)); \
_mm256_storeu_si256(out + i, A1); \
total = _mm256_add_epi64(total, popcount256(A1)); \
} \
return (uint64_t)(_mm256_extract_epi64(total, 0)) + \
(uint64_t)(_mm256_extract_epi64(total, 1)) + \
(uint64_t)(_mm256_extract_epi64(total, 2)) + \
(uint64_t)(_mm256_extract_epi64(total, 3)); \
}
CROARING_TARGET_AVX2
CROARING_AVXPOPCNTFNC(or, _mm256_or_si256)
CROARING_UNTARGET_AVX2
CROARING_TARGET_AVX2
CROARING_AVXPOPCNTFNC(union, _mm256_or_si256)
CROARING_UNTARGET_AVX2
CROARING_TARGET_AVX2
CROARING_AVXPOPCNTFNC(and, _mm256_and_si256)
CROARING_UNTARGET_AVX2
CROARING_TARGET_AVX2
CROARING_AVXPOPCNTFNC(intersection, _mm256_and_si256)
CROARING_UNTARGET_AVX2
CROARING_TARGET_AVX2
CROARING_AVXPOPCNTFNC(xor, _mm256_xor_si256)
CROARING_UNTARGET_AVX2
CROARING_TARGET_AVX2
CROARING_AVXPOPCNTFNC(andnot, _mm256_andnot_si256)
CROARING_UNTARGET_AVX2
#define VPOPCNT_AND_ADD(ptr, i, accu) \
const __m512i v##i = _mm512_loadu_si512((const __m512i *)ptr + i); \
const __m512i p##i = _mm512_popcnt_epi64(v##i); \
accu = _mm512_add_epi64(accu, p##i);
#if CROARING_COMPILER_SUPPORTS_AVX512
CROARING_TARGET_AVX512
static inline uint64_t sum_epu64_256(const __m256i v) {
return (uint64_t)(_mm256_extract_epi64(v, 0)) +
(uint64_t)(_mm256_extract_epi64(v, 1)) +
(uint64_t)(_mm256_extract_epi64(v, 2)) +
(uint64_t)(_mm256_extract_epi64(v, 3));
}
static inline uint64_t simd_sum_epu64(const __m512i v) {
__m256i lo = _mm512_extracti64x4_epi64(v, 0);
__m256i hi = _mm512_extracti64x4_epi64(v, 1);
return sum_epu64_256(lo) + sum_epu64_256(hi);
}
static inline uint64_t avx512_vpopcount(const __m512i *data,
const uint64_t size) {
const uint64_t limit = size - size % 4;
__m512i total = _mm512_setzero_si512();
uint64_t i = 0;
for (; i < limit; i += 4) {
VPOPCNT_AND_ADD(data + i, 0, total);
VPOPCNT_AND_ADD(data + i, 1, total);
VPOPCNT_AND_ADD(data + i, 2, total);
VPOPCNT_AND_ADD(data + i, 3, total);
}
for (; i < size; i++) {
total = _mm512_add_epi64(
total, _mm512_popcnt_epi64(_mm512_loadu_si512(data + i)));
}
return simd_sum_epu64(total);
}
CROARING_UNTARGET_AVX512
#endif
#define CROARING_AVXPOPCNTFNC512(opname, avx_intrinsic) \
static inline uint64_t avx512_harley_seal_popcount512_##opname( \
const __m512i *data1, const __m512i *data2, const uint64_t size) { \
__m512i total = _mm512_setzero_si512(); \
const uint64_t limit = size - size % 4; \
uint64_t i = 0; \
for (; i < limit; i += 4) { \
__m512i a1 = avx_intrinsic(_mm512_loadu_si512(data1 + i), \
_mm512_loadu_si512(data2 + i)); \
total = _mm512_add_epi64(total, _mm512_popcnt_epi64(a1)); \
__m512i a2 = avx_intrinsic(_mm512_loadu_si512(data1 + i + 1), \
_mm512_loadu_si512(data2 + i + 1)); \
total = _mm512_add_epi64(total, _mm512_popcnt_epi64(a2)); \
__m512i a3 = avx_intrinsic(_mm512_loadu_si512(data1 + i + 2), \
_mm512_loadu_si512(data2 + i + 2)); \
total = _mm512_add_epi64(total, _mm512_popcnt_epi64(a3)); \
__m512i a4 = avx_intrinsic(_mm512_loadu_si512(data1 + i + 3), \
_mm512_loadu_si512(data2 + i + 3)); \
total = _mm512_add_epi64(total, _mm512_popcnt_epi64(a4)); \
} \
for (; i < size; i++) { \
__m512i a = avx_intrinsic(_mm512_loadu_si512(data1 + i), \
_mm512_loadu_si512(data2 + i)); \
total = _mm512_add_epi64(total, _mm512_popcnt_epi64(a)); \
} \
return simd_sum_epu64(total); \
} \
static inline uint64_t avx512_harley_seal_popcount512andstore_##opname( \
const __m512i *__restrict__ data1, const __m512i *__restrict__ data2, \
__m512i *__restrict__ out, const uint64_t size) { \
__m512i total = _mm512_setzero_si512(); \
const uint64_t limit = size - size % 4; \
uint64_t i = 0; \
for (; i < limit; i += 4) { \
__m512i a1 = avx_intrinsic(_mm512_loadu_si512(data1 + i), \
_mm512_loadu_si512(data2 + i)); \
_mm512_storeu_si512(out + i, a1); \
total = _mm512_add_epi64(total, _mm512_popcnt_epi64(a1)); \
__m512i a2 = avx_intrinsic(_mm512_loadu_si512(data1 + i + 1), \
_mm512_loadu_si512(data2 + i + 1)); \
_mm512_storeu_si512(out + i + 1, a2); \
total = _mm512_add_epi64(total, _mm512_popcnt_epi64(a2)); \
__m512i a3 = avx_intrinsic(_mm512_loadu_si512(data1 + i + 2), \
_mm512_loadu_si512(data2 + i + 2)); \
_mm512_storeu_si512(out + i + 2, a3); \
total = _mm512_add_epi64(total, _mm512_popcnt_epi64(a3)); \
__m512i a4 = avx_intrinsic(_mm512_loadu_si512(data1 + i + 3), \
_mm512_loadu_si512(data2 + i + 3)); \
_mm512_storeu_si512(out + i + 3, a4); \
total = _mm512_add_epi64(total, _mm512_popcnt_epi64(a4)); \
} \
for (; i < size; i++) { \
__m512i a = avx_intrinsic(_mm512_loadu_si512(data1 + i), \
_mm512_loadu_si512(data2 + i)); \
_mm512_storeu_si512(out + i, a); \
total = _mm512_add_epi64(total, _mm512_popcnt_epi64(a)); \
} \
return simd_sum_epu64(total); \
}
#if CROARING_COMPILER_SUPPORTS_AVX512
CROARING_TARGET_AVX512
CROARING_AVXPOPCNTFNC512(or, _mm512_or_si512)
CROARING_AVXPOPCNTFNC512(union, _mm512_or_si512)
CROARING_AVXPOPCNTFNC512(and, _mm512_and_si512)
CROARING_AVXPOPCNTFNC512(intersection, _mm512_and_si512)
CROARING_AVXPOPCNTFNC512(xor, _mm512_xor_si512)
CROARING_AVXPOPCNTFNC512(andnot, _mm512_andnot_si512)
CROARING_UNTARGET_AVX512
#endif
#endif
#ifdef __cplusplus
}
}
} #endif
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic pop
#endif
#endif
#ifndef INCLUDE_CONTAINERS_ARRAY_H_
#define INCLUDE_CONTAINERS_ARRAY_H_
#include <string.h>
#ifdef __cplusplus
extern "C" {
namespace roaring {
using api::roaring_iterator;
using api::roaring_iterator64;
namespace internal {
#endif
enum { DEFAULT_MAX_SIZE = 4096 };
STRUCT_CONTAINER(array_container_s) {
int32_t cardinality;
int32_t capacity;
uint16_t *array;
};
typedef struct array_container_s array_container_t;
#define CAST_array(c) CAST(array_container_t *, c)
#define const_CAST_array(c) CAST(const array_container_t *, c)
#define movable_CAST_array(c) movable_CAST(array_container_t **, c)
array_container_t *array_container_create(void);
array_container_t *array_container_create_given_capacity(int32_t size);
array_container_t *array_container_create_range(uint32_t min, uint32_t max);
int array_container_shrink_to_fit(array_container_t *src);
void array_container_free(array_container_t *array);
array_container_t *array_container_clone(const array_container_t *src);
CROARING_ALLOW_UNALIGNED
static inline int array_container_cardinality(const array_container_t *array) {
return array->cardinality;
}
static inline bool array_container_nonzero_cardinality(
const array_container_t *array) {
return array->cardinality > 0;
}
void array_container_copy(const array_container_t *src, array_container_t *dst);
void array_container_add_from_range(array_container_t *arr, uint32_t min,
uint32_t max, uint16_t step);
static inline bool array_container_empty(const array_container_t *array) {
return array->cardinality == 0;
}
static inline bool array_container_full(const array_container_t *array) {
return array->cardinality == array->capacity;
}
void array_container_union(const array_container_t *src_1,
const array_container_t *src_2,
array_container_t *dst);
void array_container_xor(const array_container_t *array_1,
const array_container_t *array_2,
array_container_t *out);
void array_container_intersection(const array_container_t *src_1,
const array_container_t *src_2,
array_container_t *dst);
bool array_container_intersect(const array_container_t *src_1,
const array_container_t *src_2);
int array_container_intersection_cardinality(const array_container_t *src_1,
const array_container_t *src_2);
void array_container_intersection_inplace(array_container_t *src_1,
const array_container_t *src_2);
int array_container_to_uint32_array(void *vout, const array_container_t *cont,
uint32_t base);
int32_t array_container_number_of_runs(const array_container_t *ac);
void array_container_printf(const array_container_t *v);
void array_container_printf_as_uint32_array(const array_container_t *v,
uint32_t base);
bool array_container_validate(const array_container_t *v, const char **reason);
static inline int32_t array_container_serialized_size_in_bytes(int32_t card) {
return card * sizeof(uint16_t);
}
void array_container_grow(array_container_t *container, int32_t min,
bool preserve);
bool array_container_iterate(const array_container_t *cont, uint32_t base,
roaring_iterator iterator, void *ptr);
bool array_container_iterate64(const array_container_t *cont, uint32_t base,
roaring_iterator64 iterator, uint64_t high_bits,
void *ptr);
int32_t array_container_write(const array_container_t *container, char *buf);
int32_t array_container_read(int32_t cardinality, array_container_t *container,
const char *buf);
CROARING_ALLOW_UNALIGNED
static inline int32_t array_container_size_in_bytes(
const array_container_t *container) {
return container->cardinality * sizeof(uint16_t);
}
CROARING_ALLOW_UNALIGNED
static inline bool array_container_equals(const array_container_t *container1,
const array_container_t *container2) {
if (container1->cardinality != container2->cardinality) {
return false;
}
return memequals(container1->array, container2->array,
container1->cardinality * 2);
}
bool array_container_is_subset(const array_container_t *container1,
const array_container_t *container2);
static inline bool array_container_select(const array_container_t *container,
uint32_t *start_rank, uint32_t rank,
uint32_t *element) {
int card = array_container_cardinality(container);
if (*start_rank + card <= rank) {
*start_rank += card;
return false;
} else {
*element = container->array[rank - *start_rank];
return true;
}
}
void array_container_andnot(const array_container_t *array_1,
const array_container_t *array_2,
array_container_t *out);
static inline void array_container_append(array_container_t *arr,
uint16_t pos) {
const int32_t capacity = arr->capacity;
if (array_container_full(arr)) {
array_container_grow(arr, capacity + 1, true);
}
arr->array[arr->cardinality++] = pos;
}
static inline int array_container_try_add(array_container_t *arr,
uint16_t value,
int32_t max_cardinality) {
const int32_t cardinality = arr->cardinality;
if ((array_container_empty(arr) || arr->array[cardinality - 1] < value) &&
cardinality < max_cardinality) {
array_container_append(arr, value);
return 1;
}
const int32_t loc = binarySearch(arr->array, cardinality, value);
if (loc >= 0) {
return 0;
} else if (cardinality < max_cardinality) {
if (array_container_full(arr)) {
array_container_grow(arr, arr->capacity + 1, true);
}
const int32_t insert_idx = -loc - 1;
memmove(arr->array + insert_idx + 1, arr->array + insert_idx,
(cardinality - insert_idx) * sizeof(uint16_t));
arr->array[insert_idx] = value;
arr->cardinality++;
return 1;
} else {
return -1;
}
}
static inline bool array_container_add(array_container_t *arr, uint16_t value) {
return array_container_try_add(arr, value, INT32_MAX) == 1;
}
static inline bool array_container_remove(array_container_t *arr,
uint16_t pos) {
const int32_t idx = binarySearch(arr->array, arr->cardinality, pos);
const bool is_present = idx >= 0;
if (is_present) {
memmove(arr->array + idx, arr->array + idx + 1,
(arr->cardinality - idx - 1) * sizeof(uint16_t));
arr->cardinality--;
}
return is_present;
}
inline bool array_container_contains(const array_container_t *arr,
uint16_t pos) {
int32_t low = 0;
const uint16_t *carr = (const uint16_t *)arr->array;
int32_t high = arr->cardinality - 1;
while (high >= low + 16) {
int32_t middleIndex = (low + high) >> 1;
uint16_t middleValue = carr[middleIndex];
if (middleValue < pos) {
low = middleIndex + 1;
} else if (middleValue > pos) {
high = middleIndex - 1;
} else {
return true;
}
}
for (int i = low; i <= high; i++) {
uint16_t v = carr[i];
if (v == pos) {
return true;
}
if (v > pos) return false;
}
return false;
}
void array_container_offset(const array_container_t *c, container_t **loc,
container_t **hic, uint16_t offset);
static inline bool array_container_contains_range(const array_container_t *arr,
uint32_t range_start,
uint32_t range_end) {
const int32_t range_count = range_end - range_start;
const uint16_t rs_included = (uint16_t)range_start;
const uint16_t re_included = (uint16_t)(range_end - 1);
if (range_count <= 0) {
return true;
}
if (range_count > arr->cardinality) {
return false;
}
const int32_t start =
binarySearch(arr->array, arr->cardinality, rs_included);
return (start >= 0) && (arr->cardinality >= start + range_count) &&
(arr->array[start + range_count - 1] == re_included);
}
inline uint16_t array_container_minimum(const array_container_t *arr) {
if (arr->cardinality == 0) return 0;
return arr->array[0];
}
inline uint16_t array_container_maximum(const array_container_t *arr) {
if (arr->cardinality == 0) return 0;
return arr->array[arr->cardinality - 1];
}
inline int array_container_rank(const array_container_t *arr, uint16_t x) {
const int32_t idx = binarySearch(arr->array, arr->cardinality, x);
const bool is_present = idx >= 0;
if (is_present) {
return idx + 1;
} else {
return -idx - 1;
}
}
inline uint32_t array_container_rank_many(const array_container_t *arr,
uint64_t start_rank,
const uint32_t *begin,
const uint32_t *end, uint64_t *ans) {
const uint16_t high = (uint16_t)((*begin) >> 16);
uint32_t pos = 0;
const uint32_t *iter = begin;
for (; iter != end; iter++) {
uint32_t x = *iter;
uint16_t xhigh = (uint16_t)(x >> 16);
if (xhigh != high) return iter - begin;
const int32_t idx =
binarySearch(arr->array + pos, arr->cardinality - pos, (uint16_t)x);
const bool is_present = idx >= 0;
if (is_present) {
*(ans++) = start_rank + pos + (idx + 1);
pos = idx + 1;
} else {
*(ans++) = start_rank + pos + (-idx - 1);
}
}
return iter - begin;
}
inline int array_container_get_index(const array_container_t *arr, uint16_t x) {
const int32_t idx = binarySearch(arr->array, arr->cardinality, x);
const bool is_present = idx >= 0;
if (is_present) {
return idx;
} else {
return -1;
}
}
inline int array_container_index_equalorlarger(const array_container_t *arr,
uint16_t x) {
const int32_t idx = binarySearch(arr->array, arr->cardinality, x);
const bool is_present = idx >= 0;
if (is_present) {
return idx;
} else {
int32_t candidate = -idx - 1;
if (candidate < arr->cardinality) return candidate;
return -1;
}
}
static inline void array_container_add_range_nvals(array_container_t *array,
uint32_t min, uint32_t max,
int32_t nvals_less,
int32_t nvals_greater) {
int32_t union_cardinality = nvals_less + (max - min + 1) + nvals_greater;
if (union_cardinality > array->capacity) {
array_container_grow(array, union_cardinality, true);
}
memmove(&(array->array[union_cardinality - nvals_greater]),
&(array->array[array->cardinality - nvals_greater]),
nvals_greater * sizeof(uint16_t));
for (uint32_t i = 0; i <= max - min; i++) {
array->array[nvals_less + i] = (uint16_t)(min + i);
}
array->cardinality = union_cardinality;
}
static inline void array_container_remove_range(array_container_t *array,
uint32_t pos, uint32_t count) {
if (count != 0) {
memmove(&(array->array[pos]), &(array->array[pos + count]),
(array->cardinality - pos - count) * sizeof(uint16_t));
array->cardinality -= count;
}
}
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef INCLUDE_CONTAINERS_BITSET_H_
#define INCLUDE_CONTAINERS_BITSET_H_
#include <stdbool.h>
#include <stdint.h>
#ifdef __cplusplus
extern "C" {
namespace roaring {
using api::roaring_iterator;
using api::roaring_iterator64;
namespace internal {
#endif
enum {
BITSET_CONTAINER_SIZE_IN_WORDS = (1 << 16) / 64,
BITSET_UNKNOWN_CARDINALITY = -1
};
STRUCT_CONTAINER(bitset_container_s) {
int32_t cardinality;
uint64_t *words;
};
typedef struct bitset_container_s bitset_container_t;
#define CAST_bitset(c) CAST(bitset_container_t *, c)
#define const_CAST_bitset(c) CAST(const bitset_container_t *, c)
#define movable_CAST_bitset(c) movable_CAST(bitset_container_t **, c)
bitset_container_t *bitset_container_create(void);
void bitset_container_free(bitset_container_t *bitset);
void bitset_container_clear(bitset_container_t *bitset);
void bitset_container_set_all(bitset_container_t *bitset);
bitset_container_t *bitset_container_clone(const bitset_container_t *src);
void bitset_container_set_range(bitset_container_t *bitset, uint32_t begin,
uint32_t end);
#if defined(CROARING_ASMBITMANIPOPTIMIZATION) && defined(__AVX2__)
static inline void bitset_container_set(bitset_container_t *bitset,
uint16_t pos) {
uint64_t shift = 6;
uint64_t offset;
uint64_t p = pos;
ASM_SHIFT_RIGHT(p, shift, offset);
uint64_t load = bitset->words[offset];
ASM_SET_BIT_INC_WAS_CLEAR(load, p, bitset->cardinality);
bitset->words[offset] = load;
}
static inline bool bitset_container_add(bitset_container_t *bitset,
uint16_t pos) {
uint64_t shift = 6;
uint64_t offset;
uint64_t p = pos;
ASM_SHIFT_RIGHT(p, shift, offset);
uint64_t load = bitset->words[offset];
const int32_t oldcard = bitset->cardinality;
ASM_SET_BIT_INC_WAS_CLEAR(load, p, bitset->cardinality);
bitset->words[offset] = load;
return bitset->cardinality - oldcard;
}
static inline bool bitset_container_remove(bitset_container_t *bitset,
uint16_t pos) {
uint64_t shift = 6;
uint64_t offset;
uint64_t p = pos;
ASM_SHIFT_RIGHT(p, shift, offset);
uint64_t load = bitset->words[offset];
const int32_t oldcard = bitset->cardinality;
ASM_CLEAR_BIT_DEC_WAS_SET(load, p, bitset->cardinality);
bitset->words[offset] = load;
return oldcard - bitset->cardinality;
}
inline bool bitset_container_get(const bitset_container_t *bitset,
uint16_t pos) {
uint64_t word = bitset->words[pos >> 6];
const uint64_t p = pos;
ASM_INPLACESHIFT_RIGHT(word, p);
return word & 1;
}
#else
static inline void bitset_container_set(bitset_container_t *bitset,
uint16_t pos) {
const uint64_t old_word = bitset->words[pos >> 6];
const int index = pos & 63;
const uint64_t new_word = old_word | (UINT64_C(1) << index);
bitset->cardinality += (uint32_t)((old_word ^ new_word) >> index);
bitset->words[pos >> 6] = new_word;
}
static inline bool bitset_container_add(bitset_container_t *bitset,
uint16_t pos) {
const uint64_t old_word = bitset->words[pos >> 6];
const int index = pos & 63;
const uint64_t new_word = old_word | (UINT64_C(1) << index);
const uint64_t increment = (old_word ^ new_word) >> index;
bitset->cardinality += (uint32_t)increment;
bitset->words[pos >> 6] = new_word;
return increment > 0;
}
static inline bool bitset_container_remove(bitset_container_t *bitset,
uint16_t pos) {
const uint64_t old_word = bitset->words[pos >> 6];
const int index = pos & 63;
const uint64_t new_word = old_word & (~(UINT64_C(1) << index));
const uint64_t increment = (old_word ^ new_word) >> index;
bitset->cardinality -= (uint32_t)increment;
bitset->words[pos >> 6] = new_word;
return increment > 0;
}
inline bool bitset_container_get(const bitset_container_t *bitset,
uint16_t pos) {
const uint64_t word = bitset->words[pos >> 6];
return (word >> (pos & 63)) & 1;
}
#endif
static inline bool bitset_container_get_range(const bitset_container_t *bitset,
uint32_t pos_start,
uint32_t pos_end) {
const uint32_t start = pos_start >> 6;
const uint32_t end = pos_end >> 6;
const uint64_t first = ~((1ULL << (pos_start & 0x3F)) - 1);
const uint64_t last = (1ULL << (pos_end & 0x3F)) - 1;
if (start == end)
return ((bitset->words[end] & first & last) == (first & last));
if ((bitset->words[start] & first) != first) return false;
if ((end < BITSET_CONTAINER_SIZE_IN_WORDS) &&
((bitset->words[end] & last) != last)) {
return false;
}
for (uint32_t i = start + 1;
(i < BITSET_CONTAINER_SIZE_IN_WORDS) && (i < end); ++i) {
if (bitset->words[i] != UINT64_C(0xFFFFFFFFFFFFFFFF)) return false;
}
return true;
}
inline bool bitset_container_contains(const bitset_container_t *bitset,
uint16_t pos) {
return bitset_container_get(bitset, pos);
}
static inline bool bitset_container_contains_range(
const bitset_container_t *bitset, uint32_t pos_start, uint32_t pos_end) {
return bitset_container_get_range(bitset, pos_start, pos_end);
}
CROARING_ALLOW_UNALIGNED
static inline int bitset_container_cardinality(
const bitset_container_t *bitset) {
return bitset->cardinality;
}
void bitset_container_copy(const bitset_container_t *source,
bitset_container_t *dest);
void bitset_container_add_from_range(bitset_container_t *bitset, uint32_t min,
uint32_t max, uint16_t step);
int bitset_container_compute_cardinality(const bitset_container_t *bitset);
static inline bool bitset_container_empty(const bitset_container_t *bitset) {
if (bitset->cardinality == BITSET_UNKNOWN_CARDINALITY) {
for (int i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i++) {
if ((bitset->words[i]) != 0) return false;
}
return true;
}
return bitset->cardinality == 0;
}
static inline bool bitset_container_const_nonzero_cardinality(
const bitset_container_t *bitset) {
return !bitset_container_empty(bitset);
}
bool bitset_container_intersect(const bitset_container_t *src_1,
const bitset_container_t *src_2);
int bitset_container_or(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int bitset_container_or_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
int bitset_container_union(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int bitset_container_union_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
int bitset_container_union_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int bitset_container_or_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int bitset_container_and(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int bitset_container_and_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
int bitset_container_intersection(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int bitset_container_intersection_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
int bitset_container_intersection_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int bitset_container_and_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int bitset_container_xor(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int bitset_container_xor_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
int bitset_container_xor_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int bitset_container_andnot(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int bitset_container_andnot_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
int bitset_container_andnot_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
void bitset_container_offset(const bitset_container_t *c, container_t **loc,
container_t **hic, uint16_t offset);
int bitset_container_to_uint32_array(uint32_t *out,
const bitset_container_t *bc,
uint32_t base);
void bitset_container_printf(const bitset_container_t *v);
void bitset_container_printf_as_uint32_array(const bitset_container_t *v,
uint32_t base);
bool bitset_container_validate(const bitset_container_t *v,
const char **reason);
static inline int32_t bitset_container_serialized_size_in_bytes(void) {
return BITSET_CONTAINER_SIZE_IN_WORDS * 8;
}
int bitset_container_number_of_runs(bitset_container_t *bc);
bool bitset_container_iterate(const bitset_container_t *cont, uint32_t base,
roaring_iterator iterator, void *ptr);
bool bitset_container_iterate64(const bitset_container_t *cont, uint32_t base,
roaring_iterator64 iterator, uint64_t high_bits,
void *ptr);
int32_t bitset_container_write(const bitset_container_t *container, char *buf);
int32_t bitset_container_read(int32_t cardinality,
bitset_container_t *container, const char *buf);
static inline int32_t bitset_container_size_in_bytes(
const bitset_container_t *container) {
(void)container;
return BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t);
}
bool bitset_container_equals(const bitset_container_t *container1,
const bitset_container_t *container2);
bool bitset_container_is_subset(const bitset_container_t *container1,
const bitset_container_t *container2);
bool bitset_container_select(const bitset_container_t *container,
uint32_t *start_rank, uint32_t rank,
uint32_t *element);
uint16_t bitset_container_minimum(const bitset_container_t *container);
uint16_t bitset_container_maximum(const bitset_container_t *container);
int bitset_container_rank(const bitset_container_t *container, uint16_t x);
uint32_t bitset_container_rank_many(const bitset_container_t *container,
uint64_t start_rank, const uint32_t *begin,
const uint32_t *end, uint64_t *ans);
int bitset_container_get_index(const bitset_container_t *container, uint16_t x);
int bitset_container_index_equalorlarger(const bitset_container_t *container,
uint16_t x);
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef INCLUDE_CONTAINERS_RUN_H_
#define INCLUDE_CONTAINERS_RUN_H_
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#ifdef __cplusplus
extern "C" {
namespace roaring {
using api::roaring_iterator;
using api::roaring_iterator64;
namespace internal {
#endif
struct rle16_s {
uint16_t value;
uint16_t length;
};
typedef struct rle16_s rle16_t;
#ifdef __cplusplus
#define CROARING_MAKE_RLE16(val, len) \
{ (uint16_t)(val), (uint16_t)(len) }
#else
#define CROARING_MAKE_RLE16(val, len) \
(rle16_t) { .value = (uint16_t)(val), .length = (uint16_t)(len) }
#endif
STRUCT_CONTAINER(run_container_s) {
int32_t n_runs;
int32_t capacity;
rle16_t *runs;
};
typedef struct run_container_s run_container_t;
#define CAST_run(c) CAST(run_container_t *, c)
#define const_CAST_run(c) CAST(const run_container_t *, c)
#define movable_CAST_run(c) movable_CAST(run_container_t **, c)
run_container_t *run_container_create(void);
run_container_t *run_container_create_given_capacity(int32_t size);
int run_container_shrink_to_fit(run_container_t *src);
void run_container_free(run_container_t *run);
run_container_t *run_container_clone(const run_container_t *src);
static inline void recoverRoomAtIndex(run_container_t *run, uint16_t index) {
memmove(run->runs + index, run->runs + (1 + index),
(run->n_runs - index - 1) * sizeof(rle16_t));
run->n_runs--;
}
inline int32_t interleavedBinarySearch(const rle16_t *array, int32_t lenarray,
uint16_t ikey) {
int32_t low = 0;
int32_t high = lenarray - 1;
while (low <= high) {
int32_t middleIndex = (low + high) >> 1;
uint16_t middleValue = array[middleIndex].value;
if (middleValue < ikey) {
low = middleIndex + 1;
} else if (middleValue > ikey) {
high = middleIndex - 1;
} else {
return middleIndex;
}
}
return -(low + 1);
}
static inline int32_t rle16_find_run(const rle16_t *array, int32_t lenarray,
uint16_t ikey) {
int32_t low = 0;
int32_t high = lenarray - 1;
while (low <= high) {
int32_t middleIndex = (low + high) >> 1;
uint16_t min = array[middleIndex].value;
uint16_t max = array[middleIndex].value + array[middleIndex].length;
if (ikey > max) {
low = middleIndex + 1;
} else if (ikey < min) {
high = middleIndex - 1;
} else {
return middleIndex;
}
}
return -(low + 1);
}
static inline int32_t rle16_count_less(const rle16_t *array, int32_t lenarray,
uint16_t key) {
if (lenarray == 0) return 0;
int32_t low = 0;
int32_t high = lenarray - 1;
while (low <= high) {
int32_t middleIndex = (low + high) >> 1;
uint16_t min_value = array[middleIndex].value;
uint16_t max_value =
array[middleIndex].value + array[middleIndex].length;
if (max_value + UINT32_C(1) < key) { low = middleIndex + 1;
} else if (key < min_value) {
high = middleIndex - 1;
} else {
return middleIndex;
}
}
return low;
}
static inline int32_t rle16_count_greater(const rle16_t *array,
int32_t lenarray, uint16_t key) {
if (lenarray == 0) return 0;
int32_t low = 0;
int32_t high = lenarray - 1;
while (low <= high) {
int32_t middleIndex = (low + high) >> 1;
uint16_t min_value = array[middleIndex].value;
uint16_t max_value =
array[middleIndex].value + array[middleIndex].length;
if (max_value < key) {
low = middleIndex + 1;
} else if (key + UINT32_C(1) < min_value) { high = middleIndex - 1;
} else {
return lenarray - (middleIndex + 1);
}
}
return lenarray - low;
}
void run_container_grow(run_container_t *run, int32_t min, bool copy);
static inline void makeRoomAtIndex(run_container_t *run, uint16_t index) {
if (run->n_runs + 1 > run->capacity)
run_container_grow(run, run->n_runs + 1, true);
memmove(run->runs + 1 + index, run->runs + index,
(run->n_runs - index) * sizeof(rle16_t));
run->n_runs++;
}
bool run_container_add(run_container_t *run, uint16_t pos);
static inline bool run_container_remove(run_container_t *run, uint16_t pos) {
int32_t index = interleavedBinarySearch(run->runs, run->n_runs, pos);
if (index >= 0) {
int32_t le = run->runs[index].length;
if (le == 0) {
recoverRoomAtIndex(run, (uint16_t)index);
} else {
run->runs[index].value++;
run->runs[index].length--;
}
return true;
}
index = -index - 2; if (index >= 0) { int32_t offset = pos - run->runs[index].value;
int32_t le = run->runs[index].length;
if (offset < le) {
run->runs[index].length = (uint16_t)(offset - 1);
uint16_t newvalue = pos + 1;
int32_t newlength = le - offset - 1;
makeRoomAtIndex(run, (uint16_t)(index + 1));
run->runs[index + 1].value = newvalue;
run->runs[index + 1].length = (uint16_t)newlength;
return true;
} else if (offset == le) {
run->runs[index].length--;
return true;
}
}
return false;
}
inline bool run_container_contains(const run_container_t *run, uint16_t pos) {
int32_t index = interleavedBinarySearch(run->runs, run->n_runs, pos);
if (index >= 0) return true;
index = -index - 2; if (index != -1) { int32_t offset = pos - run->runs[index].value;
int32_t le = run->runs[index].length;
if (offset <= le) return true;
}
return false;
}
static inline bool run_container_contains_range(const run_container_t *run,
uint32_t pos_start,
uint32_t pos_end) {
uint32_t count = 0;
int32_t index =
interleavedBinarySearch(run->runs, run->n_runs, (uint16_t)pos_start);
if (index < 0) {
index = -index - 2;
if ((index == -1) ||
((pos_start - run->runs[index].value) > run->runs[index].length)) {
return false;
}
}
for (int32_t i = index; i < run->n_runs; ++i) {
const uint32_t stop = run->runs[i].value + run->runs[i].length;
if (run->runs[i].value >= pos_end) break;
if (stop >= pos_end) {
count += (((pos_end - run->runs[i].value) > 0)
? (pos_end - run->runs[i].value)
: 0);
break;
}
const uint32_t min = (stop - pos_start) > 0 ? (stop - pos_start) : 0;
count += (min < run->runs[i].length) ? min : run->runs[i].length;
}
return count >= (pos_end - pos_start - 1);
}
int run_container_cardinality(const run_container_t *run);
static inline bool run_container_nonzero_cardinality(
const run_container_t *run) {
return run->n_runs > 0; }
static inline bool run_container_empty(const run_container_t *run) {
return run->n_runs == 0; }
void run_container_copy(const run_container_t *src, run_container_t *dst);
static inline void run_container_append(run_container_t *run, rle16_t vl,
rle16_t *previousrl) {
const uint32_t previousend = previousrl->value + previousrl->length;
if (vl.value > previousend + 1) { run->runs[run->n_runs] = vl;
run->n_runs++;
*previousrl = vl;
} else {
uint32_t newend = vl.value + vl.length + UINT32_C(1);
if (newend > previousend) { previousrl->length = (uint16_t)(newend - 1 - previousrl->value);
run->runs[run->n_runs - 1] = *previousrl;
}
}
}
static inline rle16_t run_container_append_first(run_container_t *run,
rle16_t vl) {
run->runs[run->n_runs] = vl;
run->n_runs++;
return vl;
}
static inline void run_container_append_value(run_container_t *run,
uint16_t val,
rle16_t *previousrl) {
const uint32_t previousend = previousrl->value + previousrl->length;
if (val > previousend + 1) { *previousrl = CROARING_MAKE_RLE16(val, 0);
run->runs[run->n_runs] = *previousrl;
run->n_runs++;
} else if (val == previousend + 1) { previousrl->length++;
run->runs[run->n_runs - 1] = *previousrl;
}
}
static inline rle16_t run_container_append_value_first(run_container_t *run,
uint16_t val) {
rle16_t newrle = CROARING_MAKE_RLE16(val, 0);
run->runs[run->n_runs] = newrle;
run->n_runs++;
return newrle;
}
static inline bool run_container_is_full(const run_container_t *run) {
rle16_t vl = run->runs[0];
return (run->n_runs == 1) && (vl.value == 0) && (vl.length == 0xFFFF);
}
void run_container_union(const run_container_t *src_1,
const run_container_t *src_2, run_container_t *dst);
void run_container_union_inplace(run_container_t *src_1,
const run_container_t *src_2);
void run_container_intersection(const run_container_t *src_1,
const run_container_t *src_2,
run_container_t *dst);
int run_container_intersection_cardinality(const run_container_t *src_1,
const run_container_t *src_2);
bool run_container_intersect(const run_container_t *src_1,
const run_container_t *src_2);
void run_container_xor(const run_container_t *src_1,
const run_container_t *src_2, run_container_t *dst);
int run_container_to_uint32_array(void *vout, const run_container_t *cont,
uint32_t base);
void run_container_printf(const run_container_t *v);
void run_container_printf_as_uint32_array(const run_container_t *v,
uint32_t base);
bool run_container_validate(const run_container_t *run, const char **reason);
static inline int32_t run_container_serialized_size_in_bytes(int32_t num_runs) {
return sizeof(uint16_t) +
sizeof(rle16_t) * num_runs; }
bool run_container_iterate(const run_container_t *cont, uint32_t base,
roaring_iterator iterator, void *ptr);
bool run_container_iterate64(const run_container_t *cont, uint32_t base,
roaring_iterator64 iterator, uint64_t high_bits,
void *ptr);
int32_t run_container_write(const run_container_t *container, char *buf);
int32_t run_container_read(int32_t cardinality, run_container_t *container,
const char *buf);
CROARING_ALLOW_UNALIGNED
static inline int32_t run_container_size_in_bytes(
const run_container_t *container) {
return run_container_serialized_size_in_bytes(container->n_runs);
}
CROARING_ALLOW_UNALIGNED
static inline bool run_container_equals(const run_container_t *container1,
const run_container_t *container2) {
if (container1->n_runs != container2->n_runs) {
return false;
}
return memequals(container1->runs, container2->runs,
container1->n_runs * sizeof(rle16_t));
}
bool run_container_is_subset(const run_container_t *container1,
const run_container_t *container2);
void run_container_smart_append_exclusive(run_container_t *src,
const uint16_t start,
const uint16_t length);
static inline run_container_t *run_container_create_range(uint32_t start,
uint32_t stop) {
run_container_t *rc = run_container_create_given_capacity(1);
if (rc) {
rle16_t r;
r.value = (uint16_t)start;
r.length = (uint16_t)(stop - start - 1);
run_container_append_first(rc, r);
}
return rc;
}
bool run_container_select(const run_container_t *container,
uint32_t *start_rank, uint32_t rank,
uint32_t *element);
void run_container_andnot(const run_container_t *src_1,
const run_container_t *src_2, run_container_t *dst);
void run_container_offset(const run_container_t *c, container_t **loc,
container_t **hic, uint16_t offset);
inline uint16_t run_container_minimum(const run_container_t *run) {
if (run->n_runs == 0) return 0;
return run->runs[0].value;
}
inline uint16_t run_container_maximum(const run_container_t *run) {
if (run->n_runs == 0) return 0;
return run->runs[run->n_runs - 1].value + run->runs[run->n_runs - 1].length;
}
int run_container_rank(const run_container_t *arr, uint16_t x);
uint32_t run_container_rank_many(const run_container_t *arr,
uint64_t start_rank, const uint32_t *begin,
const uint32_t *end, uint64_t *ans);
int run_container_get_index(const run_container_t *arr, uint16_t x);
inline int run_container_index_equalorlarger(const run_container_t *arr,
uint16_t x) {
int32_t index = interleavedBinarySearch(arr->runs, arr->n_runs, x);
if (index >= 0) return index;
index = -index - 2; if (index != -1) { int32_t offset = x - arr->runs[index].value;
int32_t le = arr->runs[index].length;
if (offset <= le) return index;
}
index += 1;
if (index < arr->n_runs) {
return index;
}
return -1;
}
static inline void run_container_add_range_nruns(run_container_t *run,
uint32_t min, uint32_t max,
int32_t nruns_less,
int32_t nruns_greater) {
int32_t nruns_common = run->n_runs - nruns_less - nruns_greater;
if (nruns_common == 0) {
makeRoomAtIndex(run, (uint16_t)nruns_less);
run->runs[nruns_less].value = (uint16_t)min;
run->runs[nruns_less].length = (uint16_t)(max - min);
} else {
uint32_t common_min = run->runs[nruns_less].value;
uint32_t common_max = run->runs[nruns_less + nruns_common - 1].value +
run->runs[nruns_less + nruns_common - 1].length;
uint32_t result_min = (common_min < min) ? common_min : min;
uint32_t result_max = (common_max > max) ? common_max : max;
run->runs[nruns_less].value = (uint16_t)result_min;
run->runs[nruns_less].length = (uint16_t)(result_max - result_min);
memmove(&(run->runs[nruns_less + 1]),
&(run->runs[run->n_runs - nruns_greater]),
nruns_greater * sizeof(rle16_t));
run->n_runs = nruns_less + 1 + nruns_greater;
}
}
static inline void run_container_shift_tail(run_container_t *run, int32_t count,
int32_t distance) {
if (distance > 0) {
if (run->capacity < count + distance) {
run_container_grow(run, count + distance, true);
}
}
int32_t srcpos = run->n_runs - count;
int32_t dstpos = srcpos + distance;
memmove(&(run->runs[dstpos]), &(run->runs[srcpos]),
sizeof(rle16_t) * count);
run->n_runs += distance;
}
static inline void run_container_remove_range(run_container_t *run,
uint32_t min, uint32_t max) {
int32_t first = rle16_find_run(run->runs, run->n_runs, (uint16_t)min);
int32_t last = rle16_find_run(run->runs, run->n_runs, (uint16_t)max);
if (first >= 0 && min > run->runs[first].value &&
max < ((uint32_t)run->runs[first].value +
(uint32_t)run->runs[first].length)) {
makeRoomAtIndex(run, (uint16_t)(first + 1));
run->runs[first + 1].value = (uint16_t)(max + 1);
run->runs[first + 1].length =
(uint16_t)((run->runs[first].value + run->runs[first].length) -
(max + 1));
run->runs[first].length =
(uint16_t)((min - 1) - run->runs[first].value);
return;
}
if (first >= 0) {
if (min > run->runs[first].value) {
run->runs[first].length =
(uint16_t)((min - 1) - run->runs[first].value);
first++;
}
} else {
first = -first - 1;
}
if (last >= 0) {
uint16_t run_max = run->runs[last].value + run->runs[last].length;
if (run_max > max) {
run->runs[last].value = (uint16_t)(max + 1);
run->runs[last].length = (uint16_t)(run_max - (max + 1));
last--;
}
} else {
last = (-last - 1) - 1;
}
if (first <= last) {
run_container_shift_tail(run, run->n_runs - (last + 1),
-(last - first + 1));
}
}
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef INCLUDE_CONTAINERS_CONVERT_H_
#define INCLUDE_CONTAINERS_CONVERT_H_
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
bitset_container_t *bitset_container_from_array(const array_container_t *arr);
bitset_container_t *bitset_container_from_run(const run_container_t *arr);
array_container_t *array_container_from_run(const run_container_t *arr);
array_container_t *array_container_from_bitset(const bitset_container_t *bits);
run_container_t *run_container_from_array(const array_container_t *c);
container_t *convert_to_bitset_or_array_container(run_container_t *rc,
int32_t card,
uint8_t *resulttype);
container_t *convert_run_optimize(container_t *c, uint8_t typecode_original,
uint8_t *typecode_after);
container_t *convert_run_to_efficient_container(run_container_t *c,
uint8_t *typecode_after);
container_t *convert_run_to_efficient_container_and_free(
run_container_t *c, uint8_t *typecode_after);
container_t *container_from_run_range(const run_container_t *run, uint32_t min,
uint32_t max, uint8_t *typecode_after);
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef CONTAINERS_MIXED_EQUAL_H_
#define CONTAINERS_MIXED_EQUAL_H_
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
bool array_container_equal_bitset(const array_container_t* container1,
const bitset_container_t* container2);
bool run_container_equals_array(const run_container_t* container1,
const array_container_t* container2);
bool run_container_equals_bitset(const run_container_t* container1,
const bitset_container_t* container2);
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef CONTAINERS_MIXED_SUBSET_H_
#define CONTAINERS_MIXED_SUBSET_H_
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
bool array_container_is_subset_bitset(const array_container_t* container1,
const bitset_container_t* container2);
bool run_container_is_subset_array(const run_container_t* container1,
const array_container_t* container2);
bool array_container_is_subset_run(const array_container_t* container1,
const run_container_t* container2);
bool run_container_is_subset_bitset(const run_container_t* container1,
const bitset_container_t* container2);
bool bitset_container_is_subset_run(const bitset_container_t* container1,
const run_container_t* container2);
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef INCLUDE_CONTAINERS_MIXED_ANDNOT_H_
#define INCLUDE_CONTAINERS_MIXED_ANDNOT_H_
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
void array_bitset_container_andnot(const array_container_t *src_1,
const bitset_container_t *src_2,
array_container_t *dst);
void array_bitset_container_iandnot(array_container_t *src_1,
const bitset_container_t *src_2);
bool bitset_array_container_andnot(const bitset_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
bool bitset_array_container_iandnot(bitset_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
bool run_bitset_container_andnot(const run_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
bool run_bitset_container_iandnot(run_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
bool bitset_run_container_andnot(const bitset_container_t *src_1,
const run_container_t *src_2,
container_t **dst);
bool bitset_run_container_iandnot(bitset_container_t *src_1,
const run_container_t *src_2,
container_t **dst);
int run_array_container_andnot(const run_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
int run_array_container_iandnot(run_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
void array_run_container_andnot(const array_container_t *src_1,
const run_container_t *src_2,
array_container_t *dst);
void array_run_container_iandnot(array_container_t *src_1,
const run_container_t *src_2);
int run_run_container_andnot(const run_container_t *src_1,
const run_container_t *src_2, container_t **dst);
int run_run_container_iandnot(run_container_t *src_1,
const run_container_t *src_2, container_t **dst);
void array_array_container_andnot(const array_container_t *src_1,
const array_container_t *src_2,
array_container_t *dst);
void array_array_container_iandnot(array_container_t *src_1,
const array_container_t *src_2);
bool bitset_bitset_container_andnot(const bitset_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
bool bitset_bitset_container_iandnot(bitset_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef INCLUDE_CONTAINERS_MIXED_INTERSECTION_H_
#define INCLUDE_CONTAINERS_MIXED_INTERSECTION_H_
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
void array_bitset_container_intersection(const array_container_t *src_1,
const bitset_container_t *src_2,
array_container_t *dst);
int array_bitset_container_intersection_cardinality(
const array_container_t *src_1, const bitset_container_t *src_2);
bool array_bitset_container_intersect(const array_container_t *src_1,
const bitset_container_t *src_2);
bool bitset_bitset_container_intersection(const bitset_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
void array_run_container_intersection(const array_container_t *src_1,
const run_container_t *src_2,
array_container_t *dst);
bool run_bitset_container_intersection(const run_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
int array_run_container_intersection_cardinality(const array_container_t *src_1,
const run_container_t *src_2);
int run_bitset_container_intersection_cardinality(
const run_container_t *src_1, const bitset_container_t *src_2);
bool array_run_container_intersect(const array_container_t *src_1,
const run_container_t *src_2);
bool run_bitset_container_intersect(const run_container_t *src_1,
const bitset_container_t *src_2);
bool bitset_bitset_container_intersection_inplace(
bitset_container_t *src_1, const bitset_container_t *src_2,
container_t **dst);
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef INCLUDE_CONTAINERS_MIXED_NEGATION_H_
#define INCLUDE_CONTAINERS_MIXED_NEGATION_H_
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
void array_container_negation(const array_container_t *src,
bitset_container_t *dst);
bool bitset_container_negation(const bitset_container_t *src,
container_t **dst);
bool bitset_container_negation_inplace(bitset_container_t *src,
container_t **dst);
int run_container_negation(const run_container_t *src, container_t **dst);
int run_container_negation_inplace(run_container_t *src, container_t **dst);
bool array_container_negation_range(const array_container_t *src,
const int range_start, const int range_end,
container_t **dst);
bool array_container_negation_range_inplace(array_container_t *src,
const int range_start,
const int range_end,
container_t **dst);
bool bitset_container_negation_range(const bitset_container_t *src,
const int range_start, const int range_end,
container_t **dst);
bool bitset_container_negation_range_inplace(bitset_container_t *src,
const int range_start,
const int range_end,
container_t **dst);
int run_container_negation_range(const run_container_t *src,
const int range_start, const int range_end,
container_t **dst);
int run_container_negation_range_inplace(run_container_t *src,
const int range_start,
const int range_end,
container_t **dst);
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef INCLUDE_CONTAINERS_MIXED_UNION_H_
#define INCLUDE_CONTAINERS_MIXED_UNION_H_
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
void array_bitset_container_union(const array_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
void array_bitset_container_lazy_union(const array_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
bool array_array_container_union(const array_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
bool array_array_container_inplace_union(array_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
bool array_array_container_lazy_union(const array_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
bool array_array_container_lazy_inplace_union(array_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
void array_run_container_union(const array_container_t *src_1,
const run_container_t *src_2,
run_container_t *dst);
void array_run_container_inplace_union(const array_container_t *src_1,
run_container_t *src_2);
void run_bitset_container_union(const run_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
void run_bitset_container_lazy_union(const run_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef INCLUDE_CONTAINERS_MIXED_XOR_H_
#define INCLUDE_CONTAINERS_MIXED_XOR_H_
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
bool array_bitset_container_xor(const array_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
void array_bitset_container_lazy_xor(const array_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
bool bitset_bitset_container_xor(const bitset_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
bool run_bitset_container_xor(const run_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
void run_bitset_container_lazy_xor(const run_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
int array_run_container_xor(const array_container_t *src_1,
const run_container_t *src_2, container_t **dst);
bool array_array_container_xor(const array_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
bool array_array_container_lazy_xor(const array_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
void array_run_container_lazy_xor(const array_container_t *src_1,
const run_container_t *src_2,
run_container_t *dst);
int run_run_container_xor(const run_container_t *src_1,
const run_container_t *src_2, container_t **dst);
bool bitset_array_container_ixor(bitset_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
bool bitset_bitset_container_ixor(bitset_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
bool array_bitset_container_ixor(array_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
bool run_bitset_container_ixor(run_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
bool bitset_run_container_ixor(bitset_container_t *src_1,
const run_container_t *src_2, container_t **dst);
int array_run_container_ixor(array_container_t *src_1,
const run_container_t *src_2, container_t **dst);
int run_array_container_ixor(run_container_t *src_1,
const array_container_t *src_2, container_t **dst);
bool array_array_container_ixor(array_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
int run_run_container_ixor(run_container_t *src_1, const run_container_t *src_2,
container_t **dst);
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef CONTAINERS_CONTAINERS_H
#define CONTAINERS_CONTAINERS_H
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
#define BITSET_CONTAINER_TYPE 1
#define ARRAY_CONTAINER_TYPE 2
#define RUN_CONTAINER_TYPE 3
#define SHARED_CONTAINER_TYPE 4
#define PAIR_CONTAINER_TYPES(type1, type2) (4 * (type1) + (type2))
#define CONTAINER_PAIR(name1, name2) \
(4 * (name1##_CONTAINER_TYPE) + (name2##_CONTAINER_TYPE))
STRUCT_CONTAINER(shared_container_s) {
container_t *container;
uint8_t typecode;
croaring_refcount_t counter; };
typedef struct shared_container_s shared_container_t;
#define CAST_shared(c) CAST(shared_container_t *, c)
#define const_CAST_shared(c) CAST(const shared_container_t *, c)
#define movable_CAST_shared(c) movable_CAST(shared_container_t **, c)
container_t *get_copy_of_container(container_t *container, uint8_t *typecode,
bool copy_on_write);
void shared_container_free(shared_container_t *container);
container_t *shared_container_extract_copy(shared_container_t *container,
uint8_t *typecode);
static inline const container_t *container_unwrap_shared(
const container_t *candidate_shared_container, uint8_t *type) {
if (*type == SHARED_CONTAINER_TYPE) {
*type = const_CAST_shared(candidate_shared_container)->typecode;
assert(*type != SHARED_CONTAINER_TYPE);
return const_CAST_shared(candidate_shared_container)->container;
} else {
return candidate_shared_container;
}
}
static inline container_t *container_mutable_unwrap_shared(container_t *c,
uint8_t *type) {
if (*type == SHARED_CONTAINER_TYPE) { *type = CAST_shared(c)->typecode;
assert(*type != SHARED_CONTAINER_TYPE);
return CAST_shared(c)->container; } else {
return c; }
}
static inline uint8_t get_container_type(const container_t *c, uint8_t type) {
if (type == SHARED_CONTAINER_TYPE) {
return const_CAST_shared(c)->typecode;
} else {
return type;
}
}
container_t *container_clone(const container_t *container, uint8_t typecode);
static inline container_t *get_writable_copy_if_shared(container_t *c,
uint8_t *type) {
if (*type == SHARED_CONTAINER_TYPE) { return shared_container_extract_copy(CAST_shared(c), type);
} else {
return c; }
}
static const char *container_names[] = {"bitset", "array", "run", "shared"};
static const char *shared_container_names[] = {
"bitset (shared)", "array (shared)", "run (shared)"};
static inline bitset_container_t *container_to_bitset(container_t *c,
uint8_t typecode) {
bitset_container_t *result = NULL;
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return CAST_bitset(c); case ARRAY_CONTAINER_TYPE:
result = bitset_container_from_array(CAST_array(c));
return result;
case RUN_CONTAINER_TYPE:
result = bitset_container_from_run(CAST_run(c));
return result;
case SHARED_CONTAINER_TYPE:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return 0; }
static inline const char *get_full_container_name(const container_t *c,
uint8_t typecode) {
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return container_names[0];
case ARRAY_CONTAINER_TYPE:
return container_names[1];
case RUN_CONTAINER_TYPE:
return container_names[2];
case SHARED_CONTAINER_TYPE:
switch (const_CAST_shared(c)->typecode) {
case BITSET_CONTAINER_TYPE:
return shared_container_names[0];
case ARRAY_CONTAINER_TYPE:
return shared_container_names[1];
case RUN_CONTAINER_TYPE:
return shared_container_names[2];
default:
assert(false);
roaring_unreachable;
return "unknown";
}
break;
default:
assert(false);
roaring_unreachable;
return "unknown";
}
roaring_unreachable;
return NULL;
}
static inline int container_get_cardinality(const container_t *c,
uint8_t typecode) {
c = container_unwrap_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return bitset_container_cardinality(const_CAST_bitset(c));
case ARRAY_CONTAINER_TYPE:
return array_container_cardinality(const_CAST_array(c));
case RUN_CONTAINER_TYPE:
return run_container_cardinality(const_CAST_run(c));
}
assert(false);
roaring_unreachable;
return 0; }
static inline bool container_is_full(const container_t *c, uint8_t typecode) {
c = container_unwrap_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return bitset_container_cardinality(const_CAST_bitset(c)) ==
(1 << 16);
case ARRAY_CONTAINER_TYPE:
return array_container_cardinality(const_CAST_array(c)) ==
(1 << 16);
case RUN_CONTAINER_TYPE:
return run_container_is_full(const_CAST_run(c));
}
assert(false);
roaring_unreachable;
return 0; }
static inline int container_shrink_to_fit(container_t *c, uint8_t type) {
c = container_mutable_unwrap_shared(c, &type);
switch (type) {
case BITSET_CONTAINER_TYPE:
return 0; case ARRAY_CONTAINER_TYPE:
return array_container_shrink_to_fit(CAST_array(c));
case RUN_CONTAINER_TYPE:
return run_container_shrink_to_fit(CAST_run(c));
}
assert(false);
roaring_unreachable;
return 0; }
static inline container_t *container_range_of_ones(uint32_t range_start,
uint32_t range_end,
uint8_t *result_type) {
assert(range_end >= range_start);
uint64_t cardinality = range_end - range_start + 1;
if (cardinality <= 2) {
*result_type = ARRAY_CONTAINER_TYPE;
return array_container_create_range(range_start, range_end);
} else {
*result_type = RUN_CONTAINER_TYPE;
return run_container_create_range(range_start, range_end);
}
}
static inline container_t *container_from_range(uint8_t *type, uint32_t min,
uint32_t max, uint16_t step) {
if (step == 0) return NULL; if (step == 1) {
return container_range_of_ones(min, max, type);
}
int size = (max - min + step - 1) / step;
if (size <= DEFAULT_MAX_SIZE) { *type = ARRAY_CONTAINER_TYPE;
array_container_t *array = array_container_create_given_capacity(size);
array_container_add_from_range(array, min, max, step);
assert(array->cardinality == size);
return array;
} else { *type = BITSET_CONTAINER_TYPE;
bitset_container_t *bitset = bitset_container_create();
bitset_container_add_from_range(bitset, min, max, step);
assert(bitset->cardinality == size);
return bitset;
}
}
static inline container_t *container_repair_after_lazy(container_t *c,
uint8_t *type) {
c = get_writable_copy_if_shared(c, type); container_t *result = NULL;
switch (*type) {
case BITSET_CONTAINER_TYPE: {
bitset_container_t *bc = CAST_bitset(c);
bc->cardinality = bitset_container_compute_cardinality(bc);
if (bc->cardinality <= DEFAULT_MAX_SIZE) {
result = array_container_from_bitset(bc);
bitset_container_free(bc);
*type = ARRAY_CONTAINER_TYPE;
return result;
}
return c;
}
case ARRAY_CONTAINER_TYPE:
return c; case RUN_CONTAINER_TYPE:
return convert_run_to_efficient_container_and_free(CAST_run(c),
type);
case SHARED_CONTAINER_TYPE:
assert(false);
}
assert(false);
roaring_unreachable;
return 0; }
static inline int32_t container_write(const container_t *c, uint8_t typecode,
char *buf) {
c = container_unwrap_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return bitset_container_write(const_CAST_bitset(c), buf);
case ARRAY_CONTAINER_TYPE:
return array_container_write(const_CAST_array(c), buf);
case RUN_CONTAINER_TYPE:
return run_container_write(const_CAST_run(c), buf);
}
assert(false);
roaring_unreachable;
return 0; }
static inline int32_t container_size_in_bytes(const container_t *c,
uint8_t typecode) {
c = container_unwrap_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return bitset_container_size_in_bytes(const_CAST_bitset(c));
case ARRAY_CONTAINER_TYPE:
return array_container_size_in_bytes(const_CAST_array(c));
case RUN_CONTAINER_TYPE:
return run_container_size_in_bytes(const_CAST_run(c));
}
assert(false);
roaring_unreachable;
return 0; }
void container_printf(const container_t *container, uint8_t typecode);
void container_printf_as_uint32_array(const container_t *container,
uint8_t typecode, uint32_t base);
bool container_internal_validate(const container_t *container, uint8_t typecode,
const char **reason);
static inline bool container_nonzero_cardinality(const container_t *c,
uint8_t typecode) {
c = container_unwrap_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return bitset_container_const_nonzero_cardinality(
const_CAST_bitset(c));
case ARRAY_CONTAINER_TYPE:
return array_container_nonzero_cardinality(const_CAST_array(c));
case RUN_CONTAINER_TYPE:
return run_container_nonzero_cardinality(const_CAST_run(c));
}
assert(false);
roaring_unreachable;
return 0; }
void container_free(container_t *container, uint8_t typecode);
static inline int container_to_uint32_array(uint32_t *output,
const container_t *c,
uint8_t typecode, uint32_t base) {
c = container_unwrap_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return bitset_container_to_uint32_array(output,
const_CAST_bitset(c), base);
case ARRAY_CONTAINER_TYPE:
return array_container_to_uint32_array(output, const_CAST_array(c),
base);
case RUN_CONTAINER_TYPE:
return run_container_to_uint32_array(output, const_CAST_run(c),
base);
}
assert(false);
roaring_unreachable;
return 0; }
static inline container_t *container_add(
container_t *c, uint16_t val,
uint8_t typecode, uint8_t *new_typecode) {
c = get_writable_copy_if_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
bitset_container_set(CAST_bitset(c), val);
*new_typecode = BITSET_CONTAINER_TYPE;
return c;
case ARRAY_CONTAINER_TYPE: {
array_container_t *ac = CAST_array(c);
if (array_container_try_add(ac, val, DEFAULT_MAX_SIZE) != -1) {
*new_typecode = ARRAY_CONTAINER_TYPE;
return ac;
} else {
bitset_container_t *bitset = bitset_container_from_array(ac);
bitset_container_add(bitset, val);
*new_typecode = BITSET_CONTAINER_TYPE;
return bitset;
}
} break;
case RUN_CONTAINER_TYPE:
run_container_add(CAST_run(c), val);
*new_typecode = RUN_CONTAINER_TYPE;
return c;
default:
assert(false);
roaring_unreachable;
return NULL;
}
}
static inline container_t *container_remove(
container_t *c, uint16_t val,
uint8_t typecode, uint8_t *new_typecode) {
c = get_writable_copy_if_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
if (bitset_container_remove(CAST_bitset(c), val)) {
int card = bitset_container_cardinality(CAST_bitset(c));
if (card <= DEFAULT_MAX_SIZE) {
*new_typecode = ARRAY_CONTAINER_TYPE;
return array_container_from_bitset(CAST_bitset(c));
}
}
*new_typecode = typecode;
return c;
case ARRAY_CONTAINER_TYPE:
*new_typecode = typecode;
array_container_remove(CAST_array(c), val);
return c;
case RUN_CONTAINER_TYPE:
run_container_remove(CAST_run(c), val);
*new_typecode = RUN_CONTAINER_TYPE;
return c;
default:
assert(false);
roaring_unreachable;
return NULL;
}
}
static inline bool container_contains(
const container_t *c, uint16_t val,
uint8_t typecode ) {
c = container_unwrap_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return bitset_container_get(const_CAST_bitset(c), val);
case ARRAY_CONTAINER_TYPE:
return array_container_contains(const_CAST_array(c), val);
case RUN_CONTAINER_TYPE:
return run_container_contains(const_CAST_run(c), val);
default:
assert(false);
roaring_unreachable;
return false;
}
}
static inline bool container_contains_range(
const container_t *c, uint32_t range_start, uint32_t range_end,
uint8_t typecode ) {
c = container_unwrap_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return bitset_container_get_range(const_CAST_bitset(c), range_start,
range_end);
case ARRAY_CONTAINER_TYPE:
return array_container_contains_range(const_CAST_array(c),
range_start, range_end);
case RUN_CONTAINER_TYPE:
return run_container_contains_range(const_CAST_run(c), range_start,
range_end);
default:
assert(false);
roaring_unreachable;
return false;
}
}
static inline bool container_equals(const container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2) {
c1 = container_unwrap_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
return bitset_container_equals(const_CAST_bitset(c1),
const_CAST_bitset(c2));
case CONTAINER_PAIR(BITSET, RUN):
return run_container_equals_bitset(const_CAST_run(c2),
const_CAST_bitset(c1));
case CONTAINER_PAIR(RUN, BITSET):
return run_container_equals_bitset(const_CAST_run(c1),
const_CAST_bitset(c2));
case CONTAINER_PAIR(BITSET, ARRAY):
return array_container_equal_bitset(const_CAST_array(c2),
const_CAST_bitset(c1));
case CONTAINER_PAIR(ARRAY, BITSET):
return array_container_equal_bitset(const_CAST_array(c1),
const_CAST_bitset(c2));
case CONTAINER_PAIR(ARRAY, RUN):
return run_container_equals_array(const_CAST_run(c2),
const_CAST_array(c1));
case CONTAINER_PAIR(RUN, ARRAY):
return run_container_equals_array(const_CAST_run(c1),
const_CAST_array(c2));
case CONTAINER_PAIR(ARRAY, ARRAY):
return array_container_equals(const_CAST_array(c1),
const_CAST_array(c2));
case CONTAINER_PAIR(RUN, RUN):
return run_container_equals(const_CAST_run(c1), const_CAST_run(c2));
default:
assert(false);
roaring_unreachable;
return false;
}
}
static inline bool container_is_subset(const container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2) {
c1 = container_unwrap_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
return bitset_container_is_subset(const_CAST_bitset(c1),
const_CAST_bitset(c2));
case CONTAINER_PAIR(BITSET, RUN):
return bitset_container_is_subset_run(const_CAST_bitset(c1),
const_CAST_run(c2));
case CONTAINER_PAIR(RUN, BITSET):
return run_container_is_subset_bitset(const_CAST_run(c1),
const_CAST_bitset(c2));
case CONTAINER_PAIR(BITSET, ARRAY):
return false;
case CONTAINER_PAIR(ARRAY, BITSET):
return array_container_is_subset_bitset(const_CAST_array(c1),
const_CAST_bitset(c2));
case CONTAINER_PAIR(ARRAY, RUN):
return array_container_is_subset_run(const_CAST_array(c1),
const_CAST_run(c2));
case CONTAINER_PAIR(RUN, ARRAY):
return run_container_is_subset_array(const_CAST_run(c1),
const_CAST_array(c2));
case CONTAINER_PAIR(ARRAY, ARRAY):
return array_container_is_subset(const_CAST_array(c1),
const_CAST_array(c2));
case CONTAINER_PAIR(RUN, RUN):
return run_container_is_subset(const_CAST_run(c1),
const_CAST_run(c2));
default:
assert(false);
roaring_unreachable;
return false;
}
}
static inline container_t *container_and(const container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type) {
c1 = container_unwrap_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
container_t *result = NULL;
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
*result_type =
bitset_bitset_container_intersection(
const_CAST_bitset(c1), const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, ARRAY):
result = array_container_create();
array_container_intersection(
const_CAST_array(c1), const_CAST_array(c2), CAST_array(result));
*result_type = ARRAY_CONTAINER_TYPE; return result;
case CONTAINER_PAIR(RUN, RUN):
result = run_container_create();
run_container_intersection(const_CAST_run(c1), const_CAST_run(c2),
CAST_run(result));
return convert_run_to_efficient_container_and_free(CAST_run(result),
result_type);
case CONTAINER_PAIR(BITSET, ARRAY):
result = array_container_create();
array_bitset_container_intersection(const_CAST_array(c2),
const_CAST_bitset(c1),
CAST_array(result));
*result_type = ARRAY_CONTAINER_TYPE; return result;
case CONTAINER_PAIR(ARRAY, BITSET):
result = array_container_create();
*result_type = ARRAY_CONTAINER_TYPE; array_bitset_container_intersection(const_CAST_array(c1),
const_CAST_bitset(c2),
CAST_array(result));
return result;
case CONTAINER_PAIR(BITSET, RUN):
*result_type =
run_bitset_container_intersection(
const_CAST_run(c2), const_CAST_bitset(c1), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, BITSET):
*result_type =
run_bitset_container_intersection(
const_CAST_run(c1), const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, RUN):
result = array_container_create();
*result_type = ARRAY_CONTAINER_TYPE; array_run_container_intersection(
const_CAST_array(c1), const_CAST_run(c2), CAST_array(result));
return result;
case CONTAINER_PAIR(RUN, ARRAY):
result = array_container_create();
*result_type = ARRAY_CONTAINER_TYPE; array_run_container_intersection(
const_CAST_array(c2), const_CAST_run(c1), CAST_array(result));
return result;
default:
assert(false);
roaring_unreachable;
return NULL;
}
}
static inline int container_and_cardinality(const container_t *c1,
uint8_t type1,
const container_t *c2,
uint8_t type2) {
c1 = container_unwrap_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
return bitset_container_and_justcard(const_CAST_bitset(c1),
const_CAST_bitset(c2));
case CONTAINER_PAIR(ARRAY, ARRAY):
return array_container_intersection_cardinality(
const_CAST_array(c1), const_CAST_array(c2));
case CONTAINER_PAIR(RUN, RUN):
return run_container_intersection_cardinality(const_CAST_run(c1),
const_CAST_run(c2));
case CONTAINER_PAIR(BITSET, ARRAY):
return array_bitset_container_intersection_cardinality(
const_CAST_array(c2), const_CAST_bitset(c1));
case CONTAINER_PAIR(ARRAY, BITSET):
return array_bitset_container_intersection_cardinality(
const_CAST_array(c1), const_CAST_bitset(c2));
case CONTAINER_PAIR(BITSET, RUN):
return run_bitset_container_intersection_cardinality(
const_CAST_run(c2), const_CAST_bitset(c1));
case CONTAINER_PAIR(RUN, BITSET):
return run_bitset_container_intersection_cardinality(
const_CAST_run(c1), const_CAST_bitset(c2));
case CONTAINER_PAIR(ARRAY, RUN):
return array_run_container_intersection_cardinality(
const_CAST_array(c1), const_CAST_run(c2));
case CONTAINER_PAIR(RUN, ARRAY):
return array_run_container_intersection_cardinality(
const_CAST_array(c2), const_CAST_run(c1));
default:
assert(false);
roaring_unreachable;
return 0;
}
}
static inline bool container_intersect(const container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2) {
c1 = container_unwrap_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
return bitset_container_intersect(const_CAST_bitset(c1),
const_CAST_bitset(c2));
case CONTAINER_PAIR(ARRAY, ARRAY):
return array_container_intersect(const_CAST_array(c1),
const_CAST_array(c2));
case CONTAINER_PAIR(RUN, RUN):
return run_container_intersect(const_CAST_run(c1),
const_CAST_run(c2));
case CONTAINER_PAIR(BITSET, ARRAY):
return array_bitset_container_intersect(const_CAST_array(c2),
const_CAST_bitset(c1));
case CONTAINER_PAIR(ARRAY, BITSET):
return array_bitset_container_intersect(const_CAST_array(c1),
const_CAST_bitset(c2));
case CONTAINER_PAIR(BITSET, RUN):
return run_bitset_container_intersect(const_CAST_run(c2),
const_CAST_bitset(c1));
case CONTAINER_PAIR(RUN, BITSET):
return run_bitset_container_intersect(const_CAST_run(c1),
const_CAST_bitset(c2));
case CONTAINER_PAIR(ARRAY, RUN):
return array_run_container_intersect(const_CAST_array(c1),
const_CAST_run(c2));
case CONTAINER_PAIR(RUN, ARRAY):
return array_run_container_intersect(const_CAST_array(c2),
const_CAST_run(c1));
default:
assert(false);
roaring_unreachable;
return 0;
}
}
static inline container_t *container_iand(container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type) {
c1 = get_writable_copy_if_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
container_t *result = NULL;
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
*result_type = bitset_bitset_container_intersection_inplace(
CAST_bitset(c1), const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, ARRAY):
array_container_intersection_inplace(CAST_array(c1),
const_CAST_array(c2));
*result_type = ARRAY_CONTAINER_TYPE;
return c1;
case CONTAINER_PAIR(RUN, RUN):
result = run_container_create();
run_container_intersection(const_CAST_run(c1), const_CAST_run(c2),
CAST_run(result));
return convert_run_to_efficient_container_and_free(CAST_run(result),
result_type);
case CONTAINER_PAIR(BITSET, ARRAY):
result = array_container_create();
array_bitset_container_intersection(const_CAST_array(c2),
const_CAST_bitset(c1),
CAST_array(result));
*result_type = ARRAY_CONTAINER_TYPE; return result;
case CONTAINER_PAIR(ARRAY, BITSET):
*result_type = ARRAY_CONTAINER_TYPE; array_bitset_container_intersection(
const_CAST_array(c1), const_CAST_bitset(c2),
CAST_array(c1)); return c1;
case CONTAINER_PAIR(BITSET, RUN):
*result_type = run_bitset_container_intersection(
const_CAST_run(c2), const_CAST_bitset(c1), &c1)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return c1;
case CONTAINER_PAIR(RUN, BITSET):
*result_type =
run_bitset_container_intersection(
const_CAST_run(c1), const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, RUN):
result = array_container_create();
*result_type = ARRAY_CONTAINER_TYPE; array_run_container_intersection(
const_CAST_array(c1), const_CAST_run(c2), CAST_array(result));
return result;
case CONTAINER_PAIR(RUN, ARRAY):
result = array_container_create();
*result_type = ARRAY_CONTAINER_TYPE; array_run_container_intersection(
const_CAST_array(c2), const_CAST_run(c1), CAST_array(result));
return result;
default:
assert(false);
roaring_unreachable;
return NULL;
}
}
static inline container_t *container_or(const container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type) {
c1 = container_unwrap_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
container_t *result = NULL;
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
result = bitset_container_create();
bitset_container_or(const_CAST_bitset(c1), const_CAST_bitset(c2),
CAST_bitset(result));
*result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, ARRAY):
*result_type =
array_array_container_union(const_CAST_array(c1),
const_CAST_array(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, RUN):
result = run_container_create();
run_container_union(const_CAST_run(c1), const_CAST_run(c2),
CAST_run(result));
*result_type = RUN_CONTAINER_TYPE;
result = convert_run_to_efficient_container_and_free(
CAST_run(result), result_type);
return result;
case CONTAINER_PAIR(BITSET, ARRAY):
result = bitset_container_create();
array_bitset_container_union(const_CAST_array(c2),
const_CAST_bitset(c1),
CAST_bitset(result));
*result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, BITSET):
result = bitset_container_create();
array_bitset_container_union(const_CAST_array(c1),
const_CAST_bitset(c2),
CAST_bitset(result));
*result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(BITSET, RUN):
if (run_container_is_full(const_CAST_run(c2))) {
result = run_container_create();
*result_type = RUN_CONTAINER_TYPE;
run_container_copy(const_CAST_run(c2), CAST_run(result));
return result;
}
result = bitset_container_create();
run_bitset_container_union(
const_CAST_run(c2), const_CAST_bitset(c1), CAST_bitset(result));
*result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, BITSET):
if (run_container_is_full(const_CAST_run(c1))) {
result = run_container_create();
*result_type = RUN_CONTAINER_TYPE;
run_container_copy(const_CAST_run(c1), CAST_run(result));
return result;
}
result = bitset_container_create();
run_bitset_container_union(
const_CAST_run(c1), const_CAST_bitset(c2), CAST_bitset(result));
*result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, RUN):
result = run_container_create();
array_run_container_union(const_CAST_array(c1), const_CAST_run(c2),
CAST_run(result));
result = convert_run_to_efficient_container_and_free(
CAST_run(result), result_type);
return result;
case CONTAINER_PAIR(RUN, ARRAY):
result = run_container_create();
array_run_container_union(const_CAST_array(c2), const_CAST_run(c1),
CAST_run(result));
result = convert_run_to_efficient_container_and_free(
CAST_run(result), result_type);
return result;
default:
assert(false);
roaring_unreachable;
return NULL; }
}
static inline container_t *container_lazy_or(const container_t *c1,
uint8_t type1,
const container_t *c2,
uint8_t type2,
uint8_t *result_type) {
c1 = container_unwrap_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
container_t *result = NULL;
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
result = bitset_container_create();
bitset_container_or_nocard(const_CAST_bitset(c1),
const_CAST_bitset(c2),
CAST_bitset(result)); *result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, ARRAY):
*result_type =
array_array_container_lazy_union(const_CAST_array(c1),
const_CAST_array(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, RUN):
result = run_container_create();
run_container_union(const_CAST_run(c1), const_CAST_run(c2),
CAST_run(result));
*result_type = RUN_CONTAINER_TYPE;
result = convert_run_to_efficient_container_and_free(
CAST_run(result), result_type);
return result;
case CONTAINER_PAIR(BITSET, ARRAY):
result = bitset_container_create();
array_bitset_container_lazy_union(const_CAST_array(c2),
const_CAST_bitset(c1),
CAST_bitset(result)); *result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, BITSET):
result = bitset_container_create();
array_bitset_container_lazy_union(const_CAST_array(c1),
const_CAST_bitset(c2),
CAST_bitset(result)); *result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(BITSET, RUN):
if (run_container_is_full(const_CAST_run(c2))) {
result = run_container_create();
*result_type = RUN_CONTAINER_TYPE;
run_container_copy(const_CAST_run(c2), CAST_run(result));
return result;
}
result = bitset_container_create();
run_bitset_container_lazy_union(const_CAST_run(c2),
const_CAST_bitset(c1),
CAST_bitset(result)); *result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, BITSET):
if (run_container_is_full(const_CAST_run(c1))) {
result = run_container_create();
*result_type = RUN_CONTAINER_TYPE;
run_container_copy(const_CAST_run(c1), CAST_run(result));
return result;
}
result = bitset_container_create();
run_bitset_container_lazy_union(const_CAST_run(c1),
const_CAST_bitset(c2),
CAST_bitset(result)); *result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, RUN):
result = run_container_create();
array_run_container_union(const_CAST_array(c1), const_CAST_run(c2),
CAST_run(result));
*result_type = RUN_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, ARRAY):
result = run_container_create();
array_run_container_union(const_CAST_array(c2), const_CAST_run(c1),
CAST_run(result)); *result_type = RUN_CONTAINER_TYPE;
return result;
default:
assert(false);
roaring_unreachable;
return NULL; }
}
static inline container_t *container_ior(container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type) {
c1 = get_writable_copy_if_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
container_t *result = NULL;
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
bitset_container_or(const_CAST_bitset(c1), const_CAST_bitset(c2),
CAST_bitset(c1));
#ifdef OR_BITSET_CONVERSION_TO_FULL
if (CAST_bitset(c1)->cardinality == (1 << 16)) { result = run_container_create_range(0, (1 << 16));
*result_type = RUN_CONTAINER_TYPE;
return result;
}
#endif
*result_type = BITSET_CONTAINER_TYPE;
return c1;
case CONTAINER_PAIR(ARRAY, ARRAY):
*result_type = array_array_container_inplace_union(
CAST_array(c1), const_CAST_array(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
if ((result == NULL) && (*result_type == ARRAY_CONTAINER_TYPE)) {
return c1; }
return result;
case CONTAINER_PAIR(RUN, RUN):
run_container_union_inplace(CAST_run(c1), const_CAST_run(c2));
return convert_run_to_efficient_container(CAST_run(c1),
result_type);
case CONTAINER_PAIR(BITSET, ARRAY):
array_bitset_container_union(
const_CAST_array(c2), const_CAST_bitset(c1), CAST_bitset(c1));
*result_type = BITSET_CONTAINER_TYPE; return c1;
case CONTAINER_PAIR(ARRAY, BITSET):
result = bitset_container_create();
*result_type = BITSET_CONTAINER_TYPE;
array_bitset_container_union(const_CAST_array(c1),
const_CAST_bitset(c2),
CAST_bitset(result));
return result;
case CONTAINER_PAIR(BITSET, RUN):
if (run_container_is_full(const_CAST_run(c2))) {
result = run_container_create();
*result_type = RUN_CONTAINER_TYPE;
run_container_copy(const_CAST_run(c2), CAST_run(result));
return result;
}
run_bitset_container_union(const_CAST_run(c2),
const_CAST_bitset(c1),
CAST_bitset(c1)); *result_type = BITSET_CONTAINER_TYPE;
return c1;
case CONTAINER_PAIR(RUN, BITSET):
if (run_container_is_full(const_CAST_run(c1))) {
*result_type = RUN_CONTAINER_TYPE;
return c1;
}
result = bitset_container_create();
run_bitset_container_union(
const_CAST_run(c1), const_CAST_bitset(c2), CAST_bitset(result));
*result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, RUN):
result = run_container_create();
array_run_container_union(const_CAST_array(c1), const_CAST_run(c2),
CAST_run(result));
result = convert_run_to_efficient_container_and_free(
CAST_run(result), result_type);
return result;
case CONTAINER_PAIR(RUN, ARRAY):
array_run_container_inplace_union(const_CAST_array(c2),
CAST_run(c1));
c1 = convert_run_to_efficient_container(CAST_run(c1), result_type);
return c1;
default:
assert(false);
roaring_unreachable;
return NULL;
}
}
static inline container_t *container_lazy_ior(container_t *c1, uint8_t type1,
const container_t *c2,
uint8_t type2,
uint8_t *result_type) {
assert(type1 != SHARED_CONTAINER_TYPE);
c2 = container_unwrap_shared(c2, &type2);
container_t *result = NULL;
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
#ifdef LAZY_OR_BITSET_CONVERSION_TO_FULL
bitset_container_or(const_CAST_bitset(c1), const_CAST_bitset(c2),
CAST_bitset(c1));
if (CAST_bitset(c1)->cardinality == (1 << 16)) { result = run_container_create_range(0, (1 << 16));
*result_type = RUN_CONTAINER_TYPE;
return result;
}
#else
bitset_container_or_nocard(const_CAST_bitset(c1),
const_CAST_bitset(c2), CAST_bitset(c1));
#endif
*result_type = BITSET_CONTAINER_TYPE;
return c1;
case CONTAINER_PAIR(ARRAY, ARRAY):
*result_type = array_array_container_lazy_inplace_union(
CAST_array(c1), const_CAST_array(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
if ((result == NULL) && (*result_type == ARRAY_CONTAINER_TYPE)) {
return c1; }
return result;
case CONTAINER_PAIR(RUN, RUN):
run_container_union_inplace(CAST_run(c1), const_CAST_run(c2));
*result_type = RUN_CONTAINER_TYPE;
return convert_run_to_efficient_container(CAST_run(c1),
result_type);
case CONTAINER_PAIR(BITSET, ARRAY):
array_bitset_container_lazy_union(const_CAST_array(c2),
const_CAST_bitset(c1),
CAST_bitset(c1)); *result_type = BITSET_CONTAINER_TYPE; return c1;
case CONTAINER_PAIR(ARRAY, BITSET):
result = bitset_container_create();
*result_type = BITSET_CONTAINER_TYPE;
array_bitset_container_lazy_union(const_CAST_array(c1),
const_CAST_bitset(c2),
CAST_bitset(result)); return result;
case CONTAINER_PAIR(BITSET, RUN):
if (run_container_is_full(const_CAST_run(c2))) {
result = run_container_create();
*result_type = RUN_CONTAINER_TYPE;
run_container_copy(const_CAST_run(c2), CAST_run(result));
return result;
}
run_bitset_container_lazy_union(
const_CAST_run(c2), const_CAST_bitset(c1),
CAST_bitset(c1)); *result_type = BITSET_CONTAINER_TYPE;
return c1;
case CONTAINER_PAIR(RUN, BITSET):
if (run_container_is_full(const_CAST_run(c1))) {
*result_type = RUN_CONTAINER_TYPE;
return c1;
}
result = bitset_container_create();
run_bitset_container_lazy_union(const_CAST_run(c1),
const_CAST_bitset(c2),
CAST_bitset(result)); *result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, RUN):
result = run_container_create();
array_run_container_union(const_CAST_array(c1), const_CAST_run(c2),
CAST_run(result));
*result_type = RUN_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, ARRAY):
array_run_container_inplace_union(const_CAST_array(c2),
CAST_run(c1));
*result_type = RUN_CONTAINER_TYPE;
return c1;
default:
assert(false);
roaring_unreachable;
return NULL;
}
}
static inline container_t *container_xor(const container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type) {
c1 = container_unwrap_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
container_t *result = NULL;
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
*result_type =
bitset_bitset_container_xor(const_CAST_bitset(c1),
const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, ARRAY):
*result_type =
array_array_container_xor(const_CAST_array(c1),
const_CAST_array(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, RUN):
*result_type = (uint8_t)run_run_container_xor(
const_CAST_run(c1), const_CAST_run(c2), &result);
return result;
case CONTAINER_PAIR(BITSET, ARRAY):
*result_type =
array_bitset_container_xor(const_CAST_array(c2),
const_CAST_bitset(c1), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, BITSET):
*result_type =
array_bitset_container_xor(const_CAST_array(c1),
const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(BITSET, RUN):
*result_type =
run_bitset_container_xor(const_CAST_run(c2),
const_CAST_bitset(c1), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, BITSET):
*result_type =
run_bitset_container_xor(const_CAST_run(c1),
const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, RUN):
*result_type = (uint8_t)array_run_container_xor(
const_CAST_array(c1), const_CAST_run(c2), &result);
return result;
case CONTAINER_PAIR(RUN, ARRAY):
*result_type = (uint8_t)array_run_container_xor(
const_CAST_array(c2), const_CAST_run(c1), &result);
return result;
default:
assert(false);
roaring_unreachable;
return NULL; }
}
static inline void container_add_offset(const container_t *c, uint8_t type,
container_t **lo, container_t **hi,
uint16_t offset) {
assert(offset != 0);
assert(container_nonzero_cardinality(c, type));
assert(lo != NULL || hi != NULL);
assert(lo == NULL || *lo == NULL);
assert(hi == NULL || *hi == NULL);
switch (type) {
case BITSET_CONTAINER_TYPE:
bitset_container_offset(const_CAST_bitset(c), lo, hi, offset);
break;
case ARRAY_CONTAINER_TYPE:
array_container_offset(const_CAST_array(c), lo, hi, offset);
break;
case RUN_CONTAINER_TYPE:
run_container_offset(const_CAST_run(c), lo, hi, offset);
break;
default:
assert(false);
roaring_unreachable;
break;
}
}
static inline container_t *container_lazy_xor(const container_t *c1,
uint8_t type1,
const container_t *c2,
uint8_t type2,
uint8_t *result_type) {
c1 = container_unwrap_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
container_t *result = NULL;
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
result = bitset_container_create();
bitset_container_xor_nocard(const_CAST_bitset(c1),
const_CAST_bitset(c2),
CAST_bitset(result)); *result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, ARRAY):
*result_type =
array_array_container_lazy_xor(const_CAST_array(c1),
const_CAST_array(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, RUN):
*result_type = (uint8_t)run_run_container_xor(
const_CAST_run(c1), const_CAST_run(c2), &result);
return result;
case CONTAINER_PAIR(BITSET, ARRAY):
result = bitset_container_create();
*result_type = BITSET_CONTAINER_TYPE;
array_bitset_container_lazy_xor(const_CAST_array(c2),
const_CAST_bitset(c1),
CAST_bitset(result));
return result;
case CONTAINER_PAIR(ARRAY, BITSET):
result = bitset_container_create();
*result_type = BITSET_CONTAINER_TYPE;
array_bitset_container_lazy_xor(const_CAST_array(c1),
const_CAST_bitset(c2),
CAST_bitset(result));
return result;
case CONTAINER_PAIR(BITSET, RUN):
result = bitset_container_create();
run_bitset_container_lazy_xor(
const_CAST_run(c2), const_CAST_bitset(c1), CAST_bitset(result));
*result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, BITSET):
result = bitset_container_create();
run_bitset_container_lazy_xor(
const_CAST_run(c1), const_CAST_bitset(c2), CAST_bitset(result));
*result_type = BITSET_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, RUN):
result = run_container_create();
array_run_container_lazy_xor(const_CAST_array(c1),
const_CAST_run(c2), CAST_run(result));
*result_type = RUN_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, ARRAY):
result = run_container_create();
array_run_container_lazy_xor(const_CAST_array(c2),
const_CAST_run(c1), CAST_run(result));
*result_type = RUN_CONTAINER_TYPE;
return result;
default:
assert(false);
roaring_unreachable;
return NULL; }
}
static inline container_t *container_ixor(container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type) {
c1 = get_writable_copy_if_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
container_t *result = NULL;
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
*result_type = bitset_bitset_container_ixor(
CAST_bitset(c1), const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, ARRAY):
*result_type = array_array_container_ixor(
CAST_array(c1), const_CAST_array(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, RUN):
*result_type = (uint8_t)run_run_container_ixor(
CAST_run(c1), const_CAST_run(c2), &result);
return result;
case CONTAINER_PAIR(BITSET, ARRAY):
*result_type = bitset_array_container_ixor(
CAST_bitset(c1), const_CAST_array(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, BITSET):
*result_type = array_bitset_container_ixor(
CAST_array(c1), const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(BITSET, RUN):
*result_type = bitset_run_container_ixor(
CAST_bitset(c1), const_CAST_run(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, BITSET):
*result_type = run_bitset_container_ixor(
CAST_run(c1), const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, RUN):
*result_type = (uint8_t)array_run_container_ixor(
CAST_array(c1), const_CAST_run(c2), &result);
return result;
case CONTAINER_PAIR(RUN, ARRAY):
*result_type = (uint8_t)run_array_container_ixor(
CAST_run(c1), const_CAST_array(c2), &result);
return result;
default:
assert(false);
roaring_unreachable;
return NULL;
}
}
static inline container_t *container_lazy_ixor(container_t *c1, uint8_t type1,
const container_t *c2,
uint8_t type2,
uint8_t *result_type) {
assert(type1 != SHARED_CONTAINER_TYPE);
c2 = container_unwrap_shared(c2, &type2);
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
bitset_container_xor_nocard(CAST_bitset(c1), const_CAST_bitset(c2),
CAST_bitset(c1)); *result_type = BITSET_CONTAINER_TYPE;
return c1;
default:
if (type1 == BITSET_CONTAINER_TYPE) {
bitset_container_t *bc = CAST_bitset(c1);
if (bc->cardinality == BITSET_UNKNOWN_CARDINALITY) {
bc->cardinality = bitset_container_compute_cardinality(bc);
}
}
return container_ixor(c1, type1, c2, type2, result_type);
}
}
static inline container_t *container_andnot(const container_t *c1,
uint8_t type1,
const container_t *c2,
uint8_t type2,
uint8_t *result_type) {
c1 = container_unwrap_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
container_t *result = NULL;
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
*result_type =
bitset_bitset_container_andnot(const_CAST_bitset(c1),
const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, ARRAY):
result = array_container_create();
array_array_container_andnot(
const_CAST_array(c1), const_CAST_array(c2), CAST_array(result));
*result_type = ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, RUN):
if (run_container_is_full(const_CAST_run(c2))) {
result = array_container_create();
*result_type = ARRAY_CONTAINER_TYPE;
return result;
}
*result_type = (uint8_t)run_run_container_andnot(
const_CAST_run(c1), const_CAST_run(c2), &result);
return result;
case CONTAINER_PAIR(BITSET, ARRAY):
*result_type =
bitset_array_container_andnot(const_CAST_bitset(c1),
const_CAST_array(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, BITSET):
result = array_container_create();
array_bitset_container_andnot(const_CAST_array(c1),
const_CAST_bitset(c2),
CAST_array(result));
*result_type = ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(BITSET, RUN):
if (run_container_is_full(const_CAST_run(c2))) {
result = array_container_create();
*result_type = ARRAY_CONTAINER_TYPE;
return result;
}
*result_type =
bitset_run_container_andnot(const_CAST_bitset(c1),
const_CAST_run(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, BITSET):
*result_type =
run_bitset_container_andnot(const_CAST_run(c1),
const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, RUN):
if (run_container_is_full(const_CAST_run(c2))) {
result = array_container_create();
*result_type = ARRAY_CONTAINER_TYPE;
return result;
}
result = array_container_create();
array_run_container_andnot(const_CAST_array(c1), const_CAST_run(c2),
CAST_array(result));
*result_type = ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, ARRAY):
*result_type = (uint8_t)run_array_container_andnot(
const_CAST_run(c1), const_CAST_array(c2), &result);
return result;
default:
assert(false);
roaring_unreachable;
return NULL; }
}
static inline container_t *container_iandnot(container_t *c1, uint8_t type1,
const container_t *c2,
uint8_t type2,
uint8_t *result_type) {
c1 = get_writable_copy_if_shared(c1, &type1);
c2 = container_unwrap_shared(c2, &type2);
container_t *result = NULL;
switch (PAIR_CONTAINER_TYPES(type1, type2)) {
case CONTAINER_PAIR(BITSET, BITSET):
*result_type = bitset_bitset_container_iandnot(
CAST_bitset(c1), const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, ARRAY):
array_array_container_iandnot(CAST_array(c1), const_CAST_array(c2));
*result_type = ARRAY_CONTAINER_TYPE;
return c1;
case CONTAINER_PAIR(RUN, RUN):
*result_type = (uint8_t)run_run_container_iandnot(
CAST_run(c1), const_CAST_run(c2), &result);
return result;
case CONTAINER_PAIR(BITSET, ARRAY):
*result_type = bitset_array_container_iandnot(
CAST_bitset(c1), const_CAST_array(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, BITSET):
*result_type = ARRAY_CONTAINER_TYPE;
array_bitset_container_iandnot(CAST_array(c1),
const_CAST_bitset(c2));
return c1;
case CONTAINER_PAIR(BITSET, RUN):
*result_type = bitset_run_container_iandnot(
CAST_bitset(c1), const_CAST_run(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(RUN, BITSET):
*result_type = run_bitset_container_iandnot(
CAST_run(c1), const_CAST_bitset(c2), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case CONTAINER_PAIR(ARRAY, RUN):
*result_type = ARRAY_CONTAINER_TYPE;
array_run_container_iandnot(CAST_array(c1), const_CAST_run(c2));
return c1;
case CONTAINER_PAIR(RUN, ARRAY):
*result_type = (uint8_t)run_array_container_iandnot(
CAST_run(c1), const_CAST_array(c2), &result);
return result;
default:
assert(false);
roaring_unreachable;
return NULL;
}
}
static inline bool container_iterate(const container_t *c, uint8_t type,
uint32_t base, roaring_iterator iterator,
void *ptr) {
c = container_unwrap_shared(c, &type);
switch (type) {
case BITSET_CONTAINER_TYPE:
return bitset_container_iterate(const_CAST_bitset(c), base,
iterator, ptr);
case ARRAY_CONTAINER_TYPE:
return array_container_iterate(const_CAST_array(c), base, iterator,
ptr);
case RUN_CONTAINER_TYPE:
return run_container_iterate(const_CAST_run(c), base, iterator,
ptr);
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return false;
}
static inline bool container_iterate64(const container_t *c, uint8_t type,
uint32_t base,
roaring_iterator64 iterator,
uint64_t high_bits, void *ptr) {
c = container_unwrap_shared(c, &type);
switch (type) {
case BITSET_CONTAINER_TYPE:
return bitset_container_iterate64(const_CAST_bitset(c), base,
iterator, high_bits, ptr);
case ARRAY_CONTAINER_TYPE:
return array_container_iterate64(const_CAST_array(c), base,
iterator, high_bits, ptr);
case RUN_CONTAINER_TYPE:
return run_container_iterate64(const_CAST_run(c), base, iterator,
high_bits, ptr);
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return false;
}
static inline container_t *container_not(const container_t *c, uint8_t type,
uint8_t *result_type) {
c = container_unwrap_shared(c, &type);
container_t *result = NULL;
switch (type) {
case BITSET_CONTAINER_TYPE:
*result_type =
bitset_container_negation(const_CAST_bitset(c), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case ARRAY_CONTAINER_TYPE:
result = bitset_container_create();
*result_type = BITSET_CONTAINER_TYPE;
array_container_negation(const_CAST_array(c), CAST_bitset(result));
return result;
case RUN_CONTAINER_TYPE:
*result_type =
(uint8_t)run_container_negation(const_CAST_run(c), &result);
return result;
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return NULL;
}
static inline container_t *container_not_range(const container_t *c,
uint8_t type,
uint32_t range_start,
uint32_t range_end,
uint8_t *result_type) {
c = container_unwrap_shared(c, &type);
container_t *result = NULL;
switch (type) {
case BITSET_CONTAINER_TYPE:
*result_type =
bitset_container_negation_range(const_CAST_bitset(c),
range_start, range_end, &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case ARRAY_CONTAINER_TYPE:
*result_type =
array_container_negation_range(const_CAST_array(c), range_start,
range_end, &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case RUN_CONTAINER_TYPE:
*result_type = (uint8_t)run_container_negation_range(
const_CAST_run(c), range_start, range_end, &result);
return result;
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return NULL;
}
static inline container_t *container_inot(container_t *c, uint8_t type,
uint8_t *result_type) {
c = get_writable_copy_if_shared(c, &type);
container_t *result = NULL;
switch (type) {
case BITSET_CONTAINER_TYPE:
*result_type =
bitset_container_negation_inplace(CAST_bitset(c), &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case ARRAY_CONTAINER_TYPE:
result = bitset_container_create();
*result_type = BITSET_CONTAINER_TYPE;
array_container_negation(CAST_array(c), CAST_bitset(result));
array_container_free(CAST_array(c));
return result;
case RUN_CONTAINER_TYPE:
*result_type =
(uint8_t)run_container_negation_inplace(CAST_run(c), &result);
return result;
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return NULL;
}
static inline container_t *container_inot_range(container_t *c, uint8_t type,
uint32_t range_start,
uint32_t range_end,
uint8_t *result_type) {
c = get_writable_copy_if_shared(c, &type);
container_t *result = NULL;
switch (type) {
case BITSET_CONTAINER_TYPE:
*result_type = bitset_container_negation_range_inplace(
CAST_bitset(c), range_start, range_end, &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case ARRAY_CONTAINER_TYPE:
*result_type = array_container_negation_range_inplace(
CAST_array(c), range_start, range_end, &result)
? BITSET_CONTAINER_TYPE
: ARRAY_CONTAINER_TYPE;
return result;
case RUN_CONTAINER_TYPE:
*result_type = (uint8_t)run_container_negation_range_inplace(
CAST_run(c), range_start, range_end, &result);
return result;
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return NULL;
}
static inline bool container_select(const container_t *c, uint8_t type,
uint32_t *start_rank, uint32_t rank,
uint32_t *element) {
c = container_unwrap_shared(c, &type);
switch (type) {
case BITSET_CONTAINER_TYPE:
return bitset_container_select(const_CAST_bitset(c), start_rank,
rank, element);
case ARRAY_CONTAINER_TYPE:
return array_container_select(const_CAST_array(c), start_rank, rank,
element);
case RUN_CONTAINER_TYPE:
return run_container_select(const_CAST_run(c), start_rank, rank,
element);
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return false;
}
static inline uint16_t container_maximum(const container_t *c, uint8_t type) {
c = container_unwrap_shared(c, &type);
switch (type) {
case BITSET_CONTAINER_TYPE:
return bitset_container_maximum(const_CAST_bitset(c));
case ARRAY_CONTAINER_TYPE:
return array_container_maximum(const_CAST_array(c));
case RUN_CONTAINER_TYPE:
return run_container_maximum(const_CAST_run(c));
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return false;
}
static inline uint16_t container_minimum(const container_t *c, uint8_t type) {
c = container_unwrap_shared(c, &type);
switch (type) {
case BITSET_CONTAINER_TYPE:
return bitset_container_minimum(const_CAST_bitset(c));
case ARRAY_CONTAINER_TYPE:
return array_container_minimum(const_CAST_array(c));
case RUN_CONTAINER_TYPE:
return run_container_minimum(const_CAST_run(c));
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return false;
}
static inline int container_rank(const container_t *c, uint8_t type,
uint16_t x) {
c = container_unwrap_shared(c, &type);
switch (type) {
case BITSET_CONTAINER_TYPE:
return bitset_container_rank(const_CAST_bitset(c), x);
case ARRAY_CONTAINER_TYPE:
return array_container_rank(const_CAST_array(c), x);
case RUN_CONTAINER_TYPE:
return run_container_rank(const_CAST_run(c), x);
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return false;
}
static inline uint32_t container_rank_many(const container_t *c, uint8_t type,
uint64_t start_rank,
const uint32_t *begin,
const uint32_t *end, uint64_t *ans) {
c = container_unwrap_shared(c, &type);
switch (type) {
case BITSET_CONTAINER_TYPE:
return bitset_container_rank_many(const_CAST_bitset(c), start_rank,
begin, end, ans);
case ARRAY_CONTAINER_TYPE:
return array_container_rank_many(const_CAST_array(c), start_rank,
begin, end, ans);
case RUN_CONTAINER_TYPE:
return run_container_rank_many(const_CAST_run(c), start_rank, begin,
end, ans);
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return 0;
}
static inline int container_get_index(const container_t *c, uint8_t type,
uint16_t x) {
c = container_unwrap_shared(c, &type);
switch (type) {
case BITSET_CONTAINER_TYPE:
return bitset_container_get_index(const_CAST_bitset(c), x);
case ARRAY_CONTAINER_TYPE:
return array_container_get_index(const_CAST_array(c), x);
case RUN_CONTAINER_TYPE:
return run_container_get_index(const_CAST_run(c), x);
default:
assert(false);
roaring_unreachable;
}
assert(false);
roaring_unreachable;
return false;
}
static inline container_t *container_add_range(container_t *c, uint8_t type,
uint32_t min, uint32_t max,
uint8_t *result_type) {
switch (type) {
case BITSET_CONTAINER_TYPE: {
bitset_container_t *bitset = CAST_bitset(c);
int32_t union_cardinality = 0;
union_cardinality += bitset->cardinality;
union_cardinality += max - min + 1;
union_cardinality -=
bitset_lenrange_cardinality(bitset->words, min, max - min);
if (union_cardinality == INT32_C(0x10000)) {
*result_type = RUN_CONTAINER_TYPE;
return run_container_create_range(0, INT32_C(0x10000));
} else {
*result_type = BITSET_CONTAINER_TYPE;
bitset_set_lenrange(bitset->words, min, max - min);
bitset->cardinality = union_cardinality;
return bitset;
}
}
case ARRAY_CONTAINER_TYPE: {
array_container_t *array = CAST_array(c);
int32_t nvals_greater =
count_greater(array->array, array->cardinality, (uint16_t)max);
int32_t nvals_less =
count_less(array->array, array->cardinality - nvals_greater,
(uint16_t)min);
int32_t union_cardinality =
nvals_less + (max - min + 1) + nvals_greater;
if (union_cardinality == INT32_C(0x10000)) {
*result_type = RUN_CONTAINER_TYPE;
return run_container_create_range(0, INT32_C(0x10000));
} else if (union_cardinality <= DEFAULT_MAX_SIZE) {
*result_type = ARRAY_CONTAINER_TYPE;
array_container_add_range_nvals(array, min, max, nvals_less,
nvals_greater);
return array;
} else {
*result_type = BITSET_CONTAINER_TYPE;
bitset_container_t *bitset = bitset_container_from_array(array);
bitset_set_lenrange(bitset->words, min, max - min);
bitset->cardinality = union_cardinality;
return bitset;
}
}
case RUN_CONTAINER_TYPE: {
run_container_t *run = CAST_run(c);
int32_t nruns_greater =
rle16_count_greater(run->runs, run->n_runs, (uint16_t)max);
int32_t nruns_less = rle16_count_less(
run->runs, run->n_runs - nruns_greater, (uint16_t)min);
int32_t run_size_bytes =
(nruns_less + 1 + nruns_greater) * sizeof(rle16_t);
int32_t bitset_size_bytes =
BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t);
if (run_size_bytes <= bitset_size_bytes) {
run_container_add_range_nruns(run, min, max, nruns_less,
nruns_greater);
*result_type = RUN_CONTAINER_TYPE;
return run;
} else {
return container_from_run_range(run, min, max, result_type);
}
}
default:
roaring_unreachable;
}
}
static inline container_t *container_remove_range(container_t *c, uint8_t type,
uint32_t min, uint32_t max,
uint8_t *result_type) {
switch (type) {
case BITSET_CONTAINER_TYPE: {
bitset_container_t *bitset = CAST_bitset(c);
int32_t result_cardinality =
bitset->cardinality -
bitset_lenrange_cardinality(bitset->words, min, max - min);
if (result_cardinality == 0) {
return NULL;
} else if (result_cardinality <= DEFAULT_MAX_SIZE) {
*result_type = ARRAY_CONTAINER_TYPE;
bitset_reset_range(bitset->words, min, max + 1);
bitset->cardinality = result_cardinality;
return array_container_from_bitset(bitset);
} else {
*result_type = BITSET_CONTAINER_TYPE;
bitset_reset_range(bitset->words, min, max + 1);
bitset->cardinality = result_cardinality;
return bitset;
}
}
case ARRAY_CONTAINER_TYPE: {
array_container_t *array = CAST_array(c);
int32_t nvals_greater =
count_greater(array->array, array->cardinality, (uint16_t)max);
int32_t nvals_less =
count_less(array->array, array->cardinality - nvals_greater,
(uint16_t)min);
int32_t result_cardinality = nvals_less + nvals_greater;
if (result_cardinality == 0) {
return NULL;
} else {
*result_type = ARRAY_CONTAINER_TYPE;
array_container_remove_range(
array, nvals_less, array->cardinality - result_cardinality);
return array;
}
}
case RUN_CONTAINER_TYPE: {
run_container_t *run = CAST_run(c);
if (run->n_runs == 0) {
return NULL;
}
if (min <= run_container_minimum(run) &&
max >= run_container_maximum(run)) {
return NULL;
}
run_container_remove_range(run, min, max);
return convert_run_to_efficient_container(run, result_type);
}
default:
roaring_unreachable;
}
}
#ifdef __cplusplus
using api::roaring_container_iterator_t;
#endif
roaring_container_iterator_t container_init_iterator(const container_t *c,
uint8_t typecode,
uint16_t *value);
roaring_container_iterator_t container_init_iterator_last(const container_t *c,
uint8_t typecode,
uint16_t *value);
inline bool container_iterator_next(const container_t *c, uint8_t typecode,
roaring_container_iterator_t *it,
uint16_t *value) {
switch (typecode) {
case BITSET_CONTAINER_TYPE: {
const bitset_container_t *bc = const_CAST_bitset(c);
it->index++;
uint32_t wordindex = it->index / 64;
if (wordindex >= BITSET_CONTAINER_SIZE_IN_WORDS) {
return false;
}
uint64_t word =
bc->words[wordindex] & (UINT64_MAX << (it->index % 64));
while (word == 0 &&
(wordindex + 1 < BITSET_CONTAINER_SIZE_IN_WORDS)) {
wordindex++;
word = bc->words[wordindex];
}
if (word != 0) {
it->index = wordindex * 64 + roaring_trailing_zeroes(word);
*value = it->index;
return true;
}
return false;
}
case ARRAY_CONTAINER_TYPE: {
const array_container_t *ac = const_CAST_array(c);
it->index++;
if (it->index < ac->cardinality) {
*value = ac->array[it->index];
return true;
}
return false;
}
case RUN_CONTAINER_TYPE: {
if (*value == UINT16_MAX) { return false;
}
const run_container_t *rc = const_CAST_run(c);
uint32_t limit =
rc->runs[it->index].value + rc->runs[it->index].length;
if (*value < limit) {
(*value)++;
return true;
}
it->index++;
if (it->index < rc->n_runs) {
*value = rc->runs[it->index].value;
return true;
}
return false;
}
default:
assert(false);
roaring_unreachable;
return false;
}
}
inline bool container_iterator_prev(const container_t *c, uint8_t typecode,
roaring_container_iterator_t *it,
uint16_t *value) {
switch (typecode) {
case BITSET_CONTAINER_TYPE: {
if (--it->index < 0) {
return false;
}
const bitset_container_t *bc = const_CAST_bitset(c);
int32_t wordindex = it->index / 64;
uint64_t word =
bc->words[wordindex] & (UINT64_MAX >> (63 - (it->index % 64)));
while (word == 0 && --wordindex >= 0) {
word = bc->words[wordindex];
}
if (word == 0) {
return false;
}
it->index = (wordindex * 64) + (63 - roaring_leading_zeroes(word));
*value = it->index;
return true;
}
case ARRAY_CONTAINER_TYPE: {
if (--it->index < 0) {
return false;
}
const array_container_t *ac = const_CAST_array(c);
*value = ac->array[it->index];
return true;
}
case RUN_CONTAINER_TYPE: {
if (*value == 0) {
return false;
}
const run_container_t *rc = const_CAST_run(c);
(*value)--;
if (*value >= rc->runs[it->index].value) {
return true;
}
if (--it->index < 0) {
return false;
}
*value = rc->runs[it->index].value + rc->runs[it->index].length;
return true;
}
default:
assert(false);
roaring_unreachable;
return false;
}
}
bool container_iterator_lower_bound(const container_t *c, uint8_t typecode,
roaring_container_iterator_t *it,
uint16_t *value_out, uint16_t val);
bool container_iterator_read_into_uint32(const container_t *c, uint8_t typecode,
roaring_container_iterator_t *it,
uint32_t high16, uint32_t *buf,
uint32_t count, uint32_t *consumed,
uint16_t *value_out);
bool container_iterator_read_into_uint64(const container_t *c, uint8_t typecode,
roaring_container_iterator_t *it,
uint64_t high48, uint64_t *buf,
uint32_t count, uint32_t *consumed,
uint16_t *value_out);
bool container_iterator_skip(const container_t *c, uint8_t typecode,
roaring_container_iterator_t *it,
uint32_t skip_count, uint32_t *consumed_count,
uint16_t *value_out);
bool container_iterator_skip_backward(const container_t *c, uint8_t typecode,
roaring_container_iterator_t *it,
uint32_t skip_count,
uint32_t *consumed_count,
uint16_t *value_out);
#ifdef __cplusplus
}
}
} #endif
#endif
#ifndef INCLUDE_ROARING_ARRAY_H
#define INCLUDE_ROARING_ARRAY_H
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#ifdef __cplusplus
extern "C" {
namespace roaring {
using api::roaring_array_t;
namespace internal {
#endif
enum {
SERIAL_COOKIE_NO_RUNCONTAINER = 12346,
SERIAL_COOKIE = 12347,
FROZEN_COOKIE = 13766,
NO_OFFSET_THRESHOLD = 4
};
roaring_array_t *ra_create(void);
bool ra_init_with_capacity(roaring_array_t *new_ra, uint32_t cap);
void ra_init(roaring_array_t *t);
bool ra_copy(const roaring_array_t *source, roaring_array_t *dest,
bool copy_on_write);
int ra_shrink_to_fit(roaring_array_t *ra);
bool ra_overwrite(const roaring_array_t *source, roaring_array_t *dest,
bool copy_on_write);
void ra_clear(roaring_array_t *r);
void ra_clear_without_containers(roaring_array_t *r);
void ra_clear_containers(roaring_array_t *ra);
inline int32_t ra_get_index(const roaring_array_t *ra, uint16_t x) {
if ((ra->size == 0) || ra->keys[ra->size - 1] == x) return ra->size - 1;
return binarySearch(ra->keys, (int32_t)ra->size, x);
}
inline container_t *ra_get_container_at_index(const roaring_array_t *ra,
uint16_t i, uint8_t *typecode) {
*typecode = ra->typecodes[i];
return ra->containers[i];
}
inline uint16_t ra_get_key_at_index(const roaring_array_t *ra, uint16_t i) {
return ra->keys[i];
}
void ra_insert_new_key_value_at(roaring_array_t *ra, int32_t i, uint16_t key,
container_t *c, uint8_t typecode);
void ra_append(roaring_array_t *ra, uint16_t key, container_t *c,
uint8_t typecode);
void ra_append_copy(roaring_array_t *ra, const roaring_array_t *sa,
uint16_t index, bool copy_on_write);
void ra_append_copy_range(roaring_array_t *ra, const roaring_array_t *sa,
int32_t start_index, int32_t end_index,
bool copy_on_write);
void ra_append_copies_until(roaring_array_t *ra, const roaring_array_t *sa,
uint16_t stopping_key, bool copy_on_write);
void ra_append_copies_after(roaring_array_t *ra, const roaring_array_t *sa,
uint16_t before_start, bool copy_on_write);
void ra_append_move_range(roaring_array_t *ra, roaring_array_t *sa,
int32_t start_index, int32_t end_index);
void ra_append_range(roaring_array_t *ra, roaring_array_t *sa,
int32_t start_index, int32_t end_index,
bool copy_on_write);
inline void ra_set_container_at_index(const roaring_array_t *ra, int32_t i,
container_t *c, uint8_t typecode) {
assert(i < ra->size);
ra->containers[i] = c;
ra->typecodes[i] = typecode;
}
container_t *ra_get_container(roaring_array_t *ra, uint16_t x,
uint8_t *typecode);
bool extend_array(roaring_array_t *ra, int32_t k);
inline int32_t ra_get_size(const roaring_array_t *ra) { return ra->size; }
static inline int32_t ra_advance_until(const roaring_array_t *ra, uint16_t x,
int32_t pos) {
return advanceUntil(ra->keys, pos, ra->size, x);
}
int32_t ra_advance_until_freeing(roaring_array_t *ra, uint16_t x, int32_t pos);
void ra_downsize(roaring_array_t *ra, int32_t new_length);
inline void ra_replace_key_and_container_at_index(roaring_array_t *ra,
int32_t i, uint16_t key,
container_t *c,
uint8_t typecode) {
assert(i < ra->size);
ra->keys[i] = key;
ra->containers[i] = c;
ra->typecodes[i] = typecode;
}
void ra_to_uint32_array(const roaring_array_t *ra, uint32_t *ans);
size_t ra_portable_serialize(const roaring_array_t *ra, char *buf);
bool ra_portable_deserialize(roaring_array_t *ra, const char *buf,
const size_t maxbytes, size_t *readbytes);
size_t ra_portable_deserialize_size(const char *buf, const size_t maxbytes);
size_t ra_portable_size_in_bytes(const roaring_array_t *ra);
bool ra_has_run_container(const roaring_array_t *ra);
uint32_t ra_portable_header_size(const roaring_array_t *ra);
static inline void ra_unshare_container_at_index(roaring_array_t *ra,
uint16_t i) {
assert(i < ra->size);
ra->containers[i] =
get_writable_copy_if_shared(ra->containers[i], &ra->typecodes[i]);
}
void ra_remove_at_index(roaring_array_t *ra, int32_t i);
void ra_reset(roaring_array_t *ra);
void ra_remove_at_index_and_free(roaring_array_t *ra, int32_t i);
void ra_copy_range(roaring_array_t *ra, uint32_t begin, uint32_t end,
uint32_t new_begin);
void ra_shift_tail(roaring_array_t *ra, int32_t count, int32_t distance);
#ifdef __cplusplus
} }
} #endif
#endif
#ifndef ROARING_H
#define ROARING_H
#include <stdbool.h>
#include <stddef.h>
#include <stdint.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);
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
#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
#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) {
#ifdef __cplusplus
using namespace ::roaring::internal;
#endif
const uint16_t hb = val >> 16;
int32_t i = ra_get_index(&r->high_low_container, hb);
if (i < 0) return false;
uint8_t typecode;
container_t *container = ra_get_container_at_index(&r->high_low_container,
(uint16_t)i, &typecode);
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);
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; const ROARING_CONTAINER_T *container; uint8_t typecode; int32_t container_index; uint32_t highbits; 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_skip(roaring_uint32_iterator_t *it,
uint32_t count);
uint32_t roaring_uint32_iterator_skip_backward(roaring_uint32_iterator_t *it,
uint32_t count);
#ifdef __cplusplus
}
}
} #endif
#endif
#ifdef __cplusplus
#if !defined(ROARING_API_NOT_IN_GLOBAL_NAMESPACE)
using namespace ::roaring::api;
#endif
#endif
#ifndef INCLUDE_ROARING_MEMORY_H_
#define INCLUDE_ROARING_MEMORY_H_
#include <stddef.h>
#ifdef __cplusplus
extern "C" {
#endif
typedef void* (*roaring_malloc_p)(size_t);
typedef void* (*roaring_realloc_p)(void*, size_t);
typedef void* (*roaring_calloc_p)(size_t, size_t);
typedef void (*roaring_free_p)(void*);
typedef void* (*roaring_aligned_malloc_p)(size_t, size_t);
typedef void (*roaring_aligned_free_p)(void*);
typedef struct roaring_memory_s {
roaring_malloc_p malloc;
roaring_realloc_p realloc;
roaring_calloc_p calloc;
roaring_free_p free;
roaring_aligned_malloc_p aligned_malloc;
roaring_aligned_free_p aligned_free;
} roaring_memory_t;
void roaring_init_memory_hook(roaring_memory_t memory_hook);
void* roaring_malloc(size_t);
void* roaring_realloc(void*, size_t);
void* roaring_calloc(size_t, size_t);
void roaring_free(void*);
void* roaring_aligned_malloc(size_t, size_t);
void roaring_aligned_free(void*);
#ifdef __cplusplus
}
#endif
#endif
#ifndef ROARING64_H
#define ROARING64_H
#include <stdbool.h>
#include <stddef.h>
#include <stdint.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);
roaring64_bitmap_t *roaring64_bitmap_of_ptr(size_t n_args,
const uint64_t *vals);
#ifdef __cplusplus
#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
#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_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_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);
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);
#ifdef __cplusplus
} } } #endif
#endif