Skip to content

Self-evolving Context Database for AI Agents. Unify Agent Memory, Knowledge RAG and Skills.

65.4 KB
Raw Blame
// Created by amalgamation.sh on 2023-04-20T10:08:28Z

/*
 * The CRoaring project is under a dual license (Apache/MIT).
 * Users of the library may choose one or the other license.
 */
/*
 * Copyright 2016-2022 The CRoaring authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * SPDX-License-Identifier: Apache-2.0
 */
/*
 * MIT License
 *
 * Copyright 2016-2022 The CRoaring authors
 *
 * Permission is hereby granted, free of charge, to any
 * person obtaining a copy of this software and associated
 * documentation files (the "Software"), to deal in the
 * Software without restriction, including without
 * limitation the rights to use, copy, modify, merge,
 * publish, distribute, sublicense, and/or sell copies of
 * the Software, and to permit persons to whom the Software
 * is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice
 * shall be included in all copies or substantial portions
 * of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
 * ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
 * SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
 * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 *
 * SPDX-License-Identifier: MIT
 */

// copied from https://github.com/RoaringBitmap/CRoaring/blob/master/benchmarks/benchmark.h
#define RDTSC_START(cycles)                                                   \
    do {                                                                      \
        register unsigned cyc_high, cyc_low;                                  \
        __asm volatile(                                                       \
            "cpuid\n\t"                                                       \
            "rdtsc\n\t"                                                       \
            "mov %%edx, %0\n\t"                                               \
            "mov %%eax, %1\n\t"                                               \
            : "=r"(cyc_high), "=r"(cyc_low)::"%rax", "%rbx", "%rcx", "%rdx"); \
        (cycles) = ((uint64_t)cyc_high << 32) | cyc_low;                      \
    } while (0)

#define RDTSC_FINAL(cycles)                                                   \
    do {                                                                      \
        register unsigned cyc_high, cyc_low;                                  \
        __asm volatile(                                                       \
            "rdtscp\n\t"                                                      \
            "mov %%edx, %0\n\t"                                               \
            "mov %%eax, %1\n\t"                                               \
            "cpuid\n\t"                                                       \
            : "=r"(cyc_high), "=r"(cyc_low)::"%rax", "%rbx", "%rcx", "%rdx"); \
        (cycles) = ((uint64_t)cyc_high << 32) | cyc_low;                      \
    } while (0)

/* begin file include/roaring/roaring_version.h */
// /include/roaring/roaring_version.h automatically generated by release.py, do not change by hand 
#ifndef ROARING_INCLUDE_ROARING_VERSION 
#define ROARING_INCLUDE_ROARING_VERSION 
#define ROARING_VERSION "1.1.2"
enum { 
    ROARING_VERSION_MAJOR = 1,
    ROARING_VERSION_MINOR = 1,
    ROARING_VERSION_REVISION = 2
}; 
#endif // ROARING_INCLUDE_ROARING_VERSION 
/* end file include/roaring/roaring_version.h */
/* begin file include/roaring/roaring_types.h */
/*
  Typedefs used by various components
*/

#ifndef ROARING_TYPES_H
#define ROARING_TYPES_H

#include <stdbool.h>
#include <stdint.h>

#ifdef __cplusplus
extern "C" { namespace roaring { namespace api {
#endif


/**
 * When building .c files as C++, there's added compile-time checking if the
 * container types are derived from a `container_t` base class.  So long as
 * such a base class is empty, the struct will behave compatibly with C structs
 * despite the derivation.  This is due to the Empty Base Class Optimization:
 *
 * https://en.cppreference.com/w/cpp/language/ebo
 *
 * But since C isn't namespaced, taking `container_t` globally might collide
 * with other projects.  So roaring.h uses ROARING_CONTAINER_T, while internal
 * code #undefs that after declaring `typedef ROARING_CONTAINER_T container_t;`
 */
#if defined(__cplusplus)
    extern "C++" {
      struct container_s {};
    }
    #define ROARING_CONTAINER_T ::roaring::api::container_s
#else
    #define ROARING_CONTAINER_T void  // no compile-time checking
#endif

#define ROARING_FLAG_COW UINT8_C(0x1)
#define ROARING_FLAG_FROZEN UINT8_C(0x2)

/**
 * Roaring arrays are array-based key-value pairs having containers as values
 * and 16-bit integer keys. A roaring bitmap  might be implemented as such.
 */

// parallel arrays.  Element sizes quite different.
// Alternative is array
// of structs.  Which would have better
// cache performance through binary searches?

typedef struct roaring_array_s {
    int32_t size;
    int32_t allocation_size;
    ROARING_CONTAINER_T **containers;  // Use container_t in non-API files!
    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);

/**
*  (For advanced users.)
* The roaring_statistics_t can be used to collect detailed statistics about
* the composition of a roaring bitmap.
*/
typedef struct roaring_statistics_s {
    uint32_t n_containers; /* number of containers */

    uint32_t n_array_containers;  /* number of array containers */
    uint32_t n_run_containers;    /* number of run containers */
    uint32_t n_bitset_containers; /* number of bitmap containers */

    uint32_t
        n_values_array_containers;    /* number of values in array containers */
    uint32_t n_values_run_containers; /* number of values in run containers */
    uint32_t
        n_values_bitset_containers; /* number of values in  bitmap containers */

    uint32_t n_bytes_array_containers;  /* number of allocated bytes in array
                                           containers */
    uint32_t n_bytes_run_containers;    /* number of allocated bytes in run
                                           containers */
    uint32_t n_bytes_bitset_containers; /* number of allocated bytes in  bitmap
                                           containers */

    uint32_t
        max_value; /* the maximal value, undefined if cardinality is zero */
    uint32_t
        min_value; /* the minimal value, undefined if cardinality is zero */
    uint64_t sum_value; /* the sum of all values (could be used to compute
                           average) */

    uint64_t cardinality; /* total number of values stored in the bitmap */

    // and n_values_arrays, n_values_rle, n_values_bitmap
} roaring_statistics_t;

#ifdef __cplusplus
} } }  // extern "C" { namespace roaring { namespace api {
#endif

#endif /* ROARING_TYPES_H */
/* end file include/roaring/roaring_types.h */
/* begin file include/roaring/portability.h */
/*
 * portability.h
 *
 */

 /**
  * All macros should be prefixed with either CROARING or ROARING.
  * The library uses both ROARING_...
  * as well as CROAIRING_ as prefixes. The ROARING_ prefix is for
  * macros that are provided by the build system or that are closely
  * related to the format. The header macros may also use ROARING_.
  * The CROARING_ prefix is for internal macros that a user is unlikely
  * to ever interact with.
  */

#ifndef INCLUDE_PORTABILITY_H_
#define INCLUDE_PORTABILITY_H_

#ifndef _GNU_SOURCE
#define _GNU_SOURCE 1
#endif // _GNU_SOURCE
#ifndef __STDC_FORMAT_MACROS
#define __STDC_FORMAT_MACROS 1
#endif // __STDC_FORMAT_MACROS

#ifdef _MSC_VER
#define CROARING_VISUAL_STUDIO 1
/**
 * We want to differentiate carefully between
 * clang under visual studio and regular visual
 * studio.
 */
#ifdef __clang__
// clang under visual studio
#define CROARING_CLANG_VISUAL_STUDIO 1
#else
// just regular visual studio (best guess)
#define CROARING_REGULAR_VISUAL_STUDIO 1
#endif // __clang__
#endif // _MSC_VER

#if defined(_POSIX_C_SOURCE) && (_POSIX_C_SOURCE < 200809L)
#undef _POSIX_C_SOURCE
#endif

#ifndef _POSIX_C_SOURCE
#define _POSIX_C_SOURCE 200809L
#endif // !(defined(_POSIX_C_SOURCE)) || (_POSIX_C_SOURCE < 200809L)
#if !(defined(_XOPEN_SOURCE)) || (_XOPEN_SOURCE < 700)
#define _XOPEN_SOURCE 700
#endif // !(defined(_XOPEN_SOURCE)) || (_XOPEN_SOURCE < 700)

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>  // will provide posix_memalign with _POSIX_C_SOURCE as defined above
#ifdef __GLIBC__
#include <malloc.h>  // this should never be needed but there are some reports that it is needed.
#endif

#ifdef __cplusplus
extern "C" {  // portability definitions are in global scope, not a namespace
#endif

#if CROARING_REGULAR_VISUAL_STUDIO && !defined(_WIN64) && !defined(CROARING_ACK_32BIT)
#pragma message( \
    "You appear to be attempting a 32-bit build under Visual Studio. We recommend a 64-bit build instead.")
#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 // __restrict__
#endif // CROARING_REGULAR_VISUAL_STUDIO



#if defined(__x86_64__) || defined(_M_X64)
// we have an x64 processor
#define CROARING_IS_X64 1

#if defined(_MSC_VER) && (_MSC_VER < 1910)
// Old visual studio systems won't support AVX2 well.
#undef CROARING_IS_X64
#endif

#if defined(__clang_major__) && (__clang_major__<= 8) && !defined(__AVX2__)
// Older versions of clang have a bug affecting us
// https://stackoverflow.com/questions/57228537/how-does-one-use-pragma-clang-attribute-push-with-c-namespaces
#undef CROARING_IS_X64
#endif

#ifdef CROARING_DISABLE_X64
#undef CROARING_IS_X64
#endif
// we include the intrinsic header
#if !CROARING_REGULAR_VISUAL_STUDIO
/* Non-Microsoft C/C++-compatible compiler */
#include <x86intrin.h>  // on some recent GCC, this will declare posix_memalign



#ifdef CROARING_CLANG_VISUAL_STUDIO

/**
 * You are not supposed, normally, to include these
 * headers directly. Instead you should either include intrin.h
 * or x86intrin.h. However, when compiling with clang
 * under Windows (i.e., when _MSC_VER is set), these headers
 * only get included *if* the corresponding features are detected
 * from macros:
 * e.g., if __AVX2__ is set... in turn,  we normally set these
 * macros by compiling against the corresponding architecture
 * (e.g., arch:AVX2, -mavx2, etc.) which compiles the whole
 * software with these advanced instructions. These headers would
 * normally guard against such usage, but we carefully included
 * <x86intrin.h>  (or <intrin.h>) before, so the headers
 * are fooled.
 */
#include <bmiintrin.h>   // for _blsr_u64
#include <lzcntintrin.h> // for  __lzcnt64
#include <immintrin.h>   // for most things (AVX2, AVX512, _popcnt64)
#include <smmintrin.h>
#include <tmmintrin.h>
#include <avxintrin.h>
#include <avx2intrin.h>
#include <wmmintrin.h>
// Important: we need the AVX-512 headers:
#include <avx512fintrin.h>
#include <avx512dqintrin.h>
#include <avx512cdintrin.h>
#include <avx512bwintrin.h>
#include <avx512vlintrin.h>
#include <avx512vbmiintrin.h>
#include <avx512vbmi2intrin.h>
#include <avx512vpopcntdqintrin.h>
// unfortunately, we may not get _blsr_u64, but, thankfully, clang
// has it as a macro.
#ifndef _blsr_u64
// we roll our own
#define _blsr_u64(n) ((n - 1) & n)
#endif //  _blsr_u64
#endif // SIMDJSON_CLANG_VISUAL_STUDIO


#endif // CROARING_REGULAR_VISUAL_STUDIO
#endif // defined(__x86_64__) || defined(_M_X64)

#if !defined(CROARING_USENEON) && !defined(DISABLENEON) && defined(__ARM_NEON)
#  define CROARING_USENEON
#endif
#if defined(CROARING_USENEON)
#  include <arm_neon.h>
#endif

#if !CROARING_REGULAR_VISUAL_STUDIO
/* Non-Microsoft C/C++-compatible compiler, assumes that it supports inline
 * assembly */
#define CROARING_INLINE_ASM 1
#endif  // _MSC_VER

#if CROARING_REGULAR_VISUAL_STUDIO
/* Microsoft C/C++-compatible compiler */
#include <intrin.h>

#ifndef __clang__  // if one compiles with MSVC *with* clang, then these
                   // intrinsics are defined!!!
#define CROARING_INTRINSICS 1
// sadly there is no way to check whether we are missing these intrinsics
// specifically.

/* wrappers for Visual Studio built-ins that look like gcc built-ins __builtin_ctzll */
/* result might be undefined when input_num is zero */
static inline int roaring_trailing_zeroes(unsigned long long input_num) {
    unsigned long index;
#ifdef _WIN64  // highly recommended!!!
    _BitScanForward64(&index, input_num);
#else  // if we must support 32-bit Windows
    if ((uint32_t)input_num != 0) {
        _BitScanForward(&index, (uint32_t)input_num);
    } else {
        _BitScanForward(&index, (uint32_t)(input_num >> 32));
        index += 32;
    }
#endif // _WIN64
    return index;
}

/* wrappers for Visual Studio built-ins that look like gcc built-ins __builtin_clzll */
/* result might be undefined when input_num is zero */
inline int roaring_leading_zeroes(unsigned long long input_num) {
    unsigned long index;
#ifdef _WIN64  // highly recommended!!!
    _BitScanReverse64(&index, input_num);
#else  // if we must support 32-bit Windows
    if (input_num > 0xFFFFFFFF) {
        _BitScanReverse(&index, (uint32_t)(input_num >> 32));
        index += 32;
    } else {
        _BitScanReverse(&index, (uint32_t)(input_num));
    }
#endif // _WIN64
    return 63 - index;
}

/* Use #define so this is effective even under /Ob0 (no inline) */
#define roaring_unreachable __assume(0)
#endif // __clang__

#endif // CROARING_REGULAR_VISUAL_STUDIO

#ifndef CROARING_INTRINSICS
#define CROARING_INTRINSICS 1
#define roaring_unreachable __builtin_unreachable()
static inline int roaring_trailing_zeroes(unsigned long long input_num) { return __builtin_ctzll(input_num); }
static 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 WARN_UNUSED __attribute__((warn_unused_result))
#else
#define WARN_UNUSED
#endif

#define IS_BIG_ENDIAN (*(uint16_t *)"\0\xff" < 0x100)

#ifdef CROARING_USENEON
// we can always compute the popcount fast.
#elif (defined(_M_ARM) || defined(_M_ARM64)) && ((defined(_WIN64) || defined(_WIN32)) && defined(CROARING_REGULAR_VISUAL_STUDIO) && CROARING_REGULAR_VISUAL_STUDIO)
// we will need this function:
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);
  // (int) _CountOneBits64(x); is unavailable
#else  // _M_ARM64
  return (int) __popcnt64(x);
#endif // _M_ARM64
#elif defined(_WIN32) && defined(CROARING_REGULAR_VISUAL_STUDIO) && CROARING_REGULAR_VISUAL_STUDIO
#ifdef _M_ARM
  return roaring_hamming_backup(x);
  // _CountOneBits is unavailable
#else // _M_ARM
    return (int) __popcnt(( unsigned int)x) + (int)  __popcnt(( unsigned int)(x>>32));
#endif // _M_ARM
#else
    return __builtin_popcountll(x);
#endif
}

#ifndef UINT64_C
#define UINT64_C(c) (c##ULL)
#endif // UINT64_C

#ifndef UINT32_C
#define UINT32_C(c) (c##UL)
#endif // UINT32_C

#ifdef __cplusplus
}  // extern "C" {
#endif // __cplusplus


// this is almost standard?
#undef STRINGIFY_IMPLEMENTATION_
#undef STRINGIFY
#define STRINGIFY_IMPLEMENTATION_(a) #a
#define STRINGIFY(a) STRINGIFY_IMPLEMENTATION_(a)

// Our fast kernels require 64-bit systems.
//
// On 32-bit x86, we lack 64-bit popcnt, lzcnt, blsr instructions.
// Furthermore, the number of SIMD registers is reduced.
//
// On 32-bit ARM, we would have smaller registers.
//
// The library should still have the fallback kernel. It is
// slower, but it should run everywhere.

//
// Enable valid runtime implementations, and select CROARING_BUILTIN_IMPLEMENTATION
//

// We are going to use runtime dispatch.
#if CROARING_IS_X64
#ifdef __clang__
// clang does not have GCC push pop
// warning: clang attribute push can't be used within a namespace in clang up
// til 8.0 so CROARING_TARGET_REGION and CROARING_UNTARGET_REGION must be *outside* of a
// namespace.
#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__)
// GCC is easier
#define CROARING_TARGET_REGION(T)                                                       \
  _Pragma("GCC push_options") _Pragma(STRINGIFY(GCC target(T)))
#define CROARING_UNTARGET_REGION _Pragma("GCC pop_options")
#endif // clang then gcc

#endif // CROARING_IS_X64

// Default target region macros don't do anything.
#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")
#define CROARING_TARGET_AVX512 CROARING_TARGET_REGION("bmi2,avx512f,avx512dq,avx512bw,avx512vbmi2,avx512bitalg,avx512vpopcntdq")
#define CROARING_UNTARGET_AVX2 CROARING_UNTARGET_REGION
#define CROARING_UNTARGET_AVX512 CROARING_UNTARGET_REGION

#ifdef __AVX2__
// No need for runtime dispatching.
// It is unnecessary and harmful to old clang to tag regions.
#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__)
// No need for runtime dispatching.
// It is unnecessary and harmful to old clang to tag regions.
#undef CROARING_TARGET_AVX512
#define CROARING_TARGET_AVX512
#undef CROARING_UNTARGET_AVX512
#define CROARING_UNTARGET_AVX512
#endif

// Allow unaligned memory access
#if defined(__GNUC__) || defined(__clang__)
#define ALLOW_UNALIGNED __attribute__((no_sanitize("alignment")))
#else
#define 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__) // defined __BYTE_ORDER__ && defined __ORDER_BIG_ENDIAN__
 #include <machine/endian.h>
 #elif defined(sun) || defined(__sun) // defined(__APPLE__) || defined(__FreeBSD__)
 #include <sys/byteorder.h>
 #else  // defined(__APPLE__) || defined(__FreeBSD__)

 #ifdef __has_include
 #if __has_include(<endian.h>)
 #include <endian.h>
 #endif //__has_include(<endian.h>)
 #endif //__has_include

 #endif // defined(__APPLE__) || defined(__FreeBSD__)


 #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 // __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
 #define CROARING_IS_BIG_ENDIAN 1
 #endif // __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
#endif

// We need portability.h to be included first,
// but we also always want isadetection.h to be
// included (right after).
// See https://github.com/RoaringBitmap/CRoaring/issues/394
// There is no scenario where we want portability.h to
// be included, but not isadetection.h: the latter is a
// strict requirement.
#endif /* INCLUDE_PORTABILITY_H_ */
/* end file include/roaring/portability.h */
/* begin file include/roaring/bitset/bitset.h */
#ifndef CBITSET_BITSET_H
#define CBITSET_BITSET_H

// For compatibility with MSVC with the use of `restrict`
#if (__STDC_VERSION__ >= 199901L) || \
    (defined(__GNUC__) && defined(__STDC_VERSION__))
#define CBITSET_RESTRICT restrict
#else
#define CBITSET_RESTRICT
#endif  // (__STDC_VERSION__ >= 199901L) || (defined(__GNUC__) &&
        // defined(__STDC_VERSION__ ))

#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 *CBITSET_RESTRICT array;
    /* For simplicity and performance, we prefer to have a size and a capacity that is a multiple of 64 bits.
     * Thus we only track the size and the capacity in terms of 64-bit words allocated */
    size_t arraysize;
    size_t capacity;
};

typedef struct bitset_s bitset_t;

/* Create a new bitset. Return NULL in case of failure. */
bitset_t *bitset_create(void);

/* Create a new bitset able to contain size bits. Return NULL in case of
 * failure. */
bitset_t *bitset_create_with_capacity(size_t size);

/* Free memory. */
void bitset_free(bitset_t *bitset);

/* Set all bits to zero. */
void bitset_clear(bitset_t *bitset);

/* Set all bits to one. */
void bitset_fill(bitset_t *bitset);

/* Create a copy */
bitset_t *bitset_copy(const bitset_t *bitset);

/* For advanced users: Resize the bitset so that it can support newarraysize * 64 bits.
 * Return true in case of success, false for failure. Pad
 * with zeroes new buffer areas if requested. */
bool bitset_resize(bitset_t *bitset, size_t newarraysize, bool padwithzeroes);

/* returns how many bytes of memory the backend buffer uses */
static inline size_t bitset_size_in_bytes(const bitset_t *bitset) {
    return bitset->arraysize * sizeof(uint64_t);
}

/* returns how many bits can be accessed */
static inline size_t bitset_size_in_bits(const bitset_t *bitset) {
    return bitset->arraysize * 64;
}

/* returns how many words (64-bit) of memory the backend buffer uses */
static inline size_t bitset_size_in_words(const bitset_t *bitset) {
    return bitset->arraysize;
}

/* For advanced users: Grow the bitset so that it can support newarraysize * 64 bits with padding.
 * Return true in case of success, false for failure. */
bool bitset_grow(bitset_t *bitset, size_t newarraysize);

/* attempts to recover unused memory, return false in case of roaring_reallocation
 * failure */
bool bitset_trim(bitset_t *bitset);

/* shifts all bits by 's' positions so that the bitset representing values
 * 1,2,10 would represent values 1+s, 2+s, 10+s */
void bitset_shift_left(bitset_t *bitset, size_t s);

/* shifts all bits by 's' positions so that the bitset representing values
 * 1,2,10 would represent values 1-s, 2-s, 10-s, negative values are deleted */
void bitset_shift_right(bitset_t *bitset, size_t s);

/* Set the ith bit. Attempts to resize the bitset if needed (may silently fail)
 */
static 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);
}

/* Set the ith bit to the specified value. Attempts to resize the bitset if
 * needed (may silently fail) */
static 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;
}

/* Get the value of the ith bit.  */
static 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;
}

/* Count number of bits set.  */
size_t bitset_count(const bitset_t *bitset);

/* Find the index of the first bit set. Or zero if the bitset is empty.  */
size_t bitset_minimum(const bitset_t *bitset);

/* Find the index of the last bit set. Or zero if the bitset is empty.  */
size_t bitset_maximum(const bitset_t *bitset);

/* compute the union in-place (to b1), returns true if successful, to generate a
 * new bitset first call bitset_copy */
bool bitset_inplace_union(bitset_t *CBITSET_RESTRICT b1,
                          const bitset_t *CBITSET_RESTRICT b2);

/* report the size of the union (without materializing it) */
size_t bitset_union_count(const bitset_t *CBITSET_RESTRICT b1,
                          const bitset_t *CBITSET_RESTRICT b2);

/* compute the intersection in-place (to b1), to generate a new bitset first
 * call bitset_copy */
void bitset_inplace_intersection(bitset_t *CBITSET_RESTRICT b1,
                                 const bitset_t *CBITSET_RESTRICT b2);

/* report the size of the intersection (without materializing it) */
size_t bitset_intersection_count(const bitset_t *CBITSET_RESTRICT b1,
                                 const bitset_t *CBITSET_RESTRICT b2);

/* returns true if the bitsets contain no common elements */
bool bitsets_disjoint(const bitset_t *CBITSET_RESTRICT b1, const bitset_t *CBITSET_RESTRICT b2);

/* returns true if the bitsets contain any common elements */
bool bitsets_intersect(const bitset_t *CBITSET_RESTRICT b1, const bitset_t *CBITSET_RESTRICT b2);

/* returns true if b1 contains all of the set bits of b2 */
bool bitset_contains_all(const bitset_t *CBITSET_RESTRICT b1, const bitset_t *CBITSET_RESTRICT b2);

/* compute the difference in-place (to b1), to generate a new bitset first call
 * bitset_copy */
void bitset_inplace_difference(bitset_t *CBITSET_RESTRICT b1,
                               const bitset_t *CBITSET_RESTRICT b2);

/* compute the size of the difference */
size_t bitset_difference_count(const bitset_t *CBITSET_RESTRICT b1,
                               const bitset_t *CBITSET_RESTRICT b2);

/* compute the symmetric difference in-place (to b1), return true if successful,
 * to generate a new bitset first call bitset_copy */
bool bitset_inplace_symmetric_difference(bitset_t *CBITSET_RESTRICT b1,
                                         const bitset_t *CBITSET_RESTRICT b2);

/* compute the size of the symmetric difference  */
size_t bitset_symmetric_difference_count(const bitset_t *CBITSET_RESTRICT b1,
                                         const bitset_t *CBITSET_RESTRICT b2);

/* iterate over the set bits
 like so :
  for(size_t i = 0; bitset_next_set_bit(b,&i) ; i++) {
    //.....
  }
  */
static 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;
}

/* iterate over the set bits
 like so :
   size_t buffer[256];
   size_t howmany = 0;
  for(size_t startfrom = 0; (howmany = bitset_next_set_bits(b,buffer,256, &startfrom)) >
 0 ; startfrom++) {
    //.....
  }
  */
static 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;  // sanity check
    size_t x = *startfrom / 64;
    if (x >= bitset->arraysize) {
        return 0;  // nothing more to iterate over
    }
    uint64_t w = bitset->array[x];
    w >>= (*startfrom & 63);
    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);

// return true if uninterrupted
static 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;
}

static 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
} } } // extern "C" { namespace roaring { namespace api {
#endif

#endif
/* end file include/roaring/bitset/bitset.h */
/* begin file include/roaring/roaring.h */
/*
 * An implementation of Roaring Bitmaps in C.
 */

#ifndef ROARING_H
#define ROARING_H

#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>  // for `size_t`


#ifdef __cplusplus
extern "C" { namespace roaring { namespace api {
#endif

typedef struct roaring_bitmap_s {
    roaring_array_t high_low_container;
} roaring_bitmap_t;

/**
 * Dynamically allocates a new bitmap (initially empty).
 * Returns NULL if the allocation fails.
 * Capacity is a performance hint for how many "containers" the data will need.
 * Client is responsible for calling `roaring_bitmap_free()`.
 */
roaring_bitmap_t *roaring_bitmap_create_with_capacity(uint32_t cap);

/**
 * Dynamically allocates a new bitmap (initially empty).
 * Returns NULL if the allocation fails.
 * Client is responsible for calling `roaring_bitmap_free()`.
 */
static inline roaring_bitmap_t *roaring_bitmap_create(void)
  { return roaring_bitmap_create_with_capacity(0); }

/**
 * Initialize a roaring bitmap structure in memory controlled by client.
 * Capacity is a performance hint for how many "containers" the data will need.
 * Can return false if auxiliary allocations fail when capacity greater than 0.
 */
bool roaring_bitmap_init_with_capacity(roaring_bitmap_t *r, uint32_t cap);

/**
 * Initialize a roaring bitmap structure in memory controlled by client.
 * The bitmap will be in a "clear" state, with no auxiliary allocations.
 * Since this performs no allocations, the function will not fail.
 */
static inline void roaring_bitmap_init_cleared(roaring_bitmap_t *r)
  { roaring_bitmap_init_with_capacity(r, 0); }

/**
 * Add all the values between min (included) and max (excluded) that are at a
 * distance k*step from min.
*/
roaring_bitmap_t *roaring_bitmap_from_range(uint64_t min, uint64_t max,
                                            uint32_t step);

/**
 * Creates a new bitmap from a pointer of uint32_t integers
 */
roaring_bitmap_t *roaring_bitmap_of_ptr(size_t n_args, const uint32_t *vals);

/*
 * Whether you want to use copy-on-write.
 * Saves memory and avoids copies, but needs more care in a threaded context.
 * Most users should ignore this flag.
 *
 * Note: If you do turn this flag to 'true', enabling COW, then ensure that you
 * do so for all of your bitmaps, since interactions between bitmaps with and
 * without COW is unsafe.
 */
static inline bool roaring_bitmap_get_copy_on_write(const roaring_bitmap_t* r) {
    return r->high_low_container.flags & ROARING_FLAG_COW;
}
static 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 {
        r->high_low_container.flags &= ~ROARING_FLAG_COW;
    }
}

roaring_bitmap_t *roaring_bitmap_add_offset(const roaring_bitmap_t *bm,
                                            int64_t offset);
/**
 * Describe the inner structure of the bitmap.
 */
void roaring_bitmap_printf_describe(const roaring_bitmap_t *r);

/**
 * Creates a new bitmap from a list of uint32_t integers
 */
roaring_bitmap_t *roaring_bitmap_of(size_t n, ...);

/**
 * Copies a bitmap (this does memory allocation).
 * The caller is responsible for memory management.
 */
roaring_bitmap_t *roaring_bitmap_copy(const roaring_bitmap_t *r);

/**
 * Copies a bitmap from src to dest. It is assumed that the pointer dest
 * is to an already allocated bitmap. The content of the dest bitmap is
 * freed/deleted.
 *
 * It might be preferable and simpler to call roaring_bitmap_copy except
 * that roaring_bitmap_overwrite can save on memory allocations.
 */
bool roaring_bitmap_overwrite(roaring_bitmap_t *dest,
                              const roaring_bitmap_t *src);

/**
 * Print the content of the bitmap.
 */
void roaring_bitmap_printf(const roaring_bitmap_t *r);

/**
 * Computes the intersection between two bitmaps and returns new bitmap. The
 * caller is responsible for memory management.
 *
 * Performance hint: if you are computing the intersection between several
 * bitmaps, two-by-two, it is best to start with the smallest bitmap.
 * You may also rely on roaring_bitmap_and_inplace to avoid creating
 * many temporary bitmaps.
 */
roaring_bitmap_t *roaring_bitmap_and(const roaring_bitmap_t *r1,
                                     const roaring_bitmap_t *r2);

/**
 * Computes the size of the intersection between two bitmaps.
 */
uint64_t roaring_bitmap_and_cardinality(const roaring_bitmap_t *r1,
                                        const roaring_bitmap_t *r2);

/**
 * Check whether two bitmaps intersect.
 */
bool roaring_bitmap_intersect(const roaring_bitmap_t *r1,
                              const roaring_bitmap_t *r2);

/**
 * Check whether a bitmap and a closed range intersect.
 */
bool roaring_bitmap_intersect_with_range(const roaring_bitmap_t *bm,
                                         uint64_t x, uint64_t y);

/**
 * Computes the Jaccard index between two bitmaps. (Also known as the Tanimoto
 * distance, or the Jaccard similarity coefficient)
 *
 * The Jaccard index is undefined if both bitmaps are empty.
 */
double roaring_bitmap_jaccard_index(const roaring_bitmap_t *r1,
                                    const roaring_bitmap_t *r2);

/**
 * Computes the size of the union between two bitmaps.
 */
uint64_t roaring_bitmap_or_cardinality(const roaring_bitmap_t *r1,
                                       const roaring_bitmap_t *r2);

/**
 * Computes the size of the difference (andnot) between two bitmaps.
 */
uint64_t roaring_bitmap_andnot_cardinality(const roaring_bitmap_t *r1,
                                           const roaring_bitmap_t *r2);

/**
 * Computes the size of the symmetric difference (xor) between two bitmaps.
 */
uint64_t roaring_bitmap_xor_cardinality(const roaring_bitmap_t *r1,
                                        const roaring_bitmap_t *r2);

/**
 * Inplace version of `roaring_bitmap_and()`, modifies r1
 * r1 == r2 is allowed.
 *
 * Performance hint: if you are computing the intersection between several
 * bitmaps, two-by-two, it is best to start with the smallest bitmap.
 */
void roaring_bitmap_and_inplace(roaring_bitmap_t *r1,
                                const roaring_bitmap_t *r2);

/**
 * Computes the union between two bitmaps and returns new bitmap. The caller is
 * responsible for memory management.
 */
roaring_bitmap_t *roaring_bitmap_or(const roaring_bitmap_t *r1,
                                    const roaring_bitmap_t *r2);

/**
 * Inplace version of `roaring_bitmap_or(), modifies r1.
 * TODO: decide whether r1 == r2 ok
 */
void roaring_bitmap_or_inplace(roaring_bitmap_t *r1,
                               const roaring_bitmap_t *r2);

/**
 * Compute the union of 'number' bitmaps.
 * Caller is responsible for freeing the result.
 * See also `roaring_bitmap_or_many_heap()`
 */
roaring_bitmap_t *roaring_bitmap_or_many(size_t number,
                                         const roaring_bitmap_t **rs);

/**
 * Compute the union of 'number' bitmaps using a heap. This can sometimes be
 * faster than `roaring_bitmap_or_many() which uses a naive algorithm.
 * Caller is responsible for freeing the result.
 */
roaring_bitmap_t *roaring_bitmap_or_many_heap(uint32_t number,
                                              const roaring_bitmap_t **rs);

/**
 * Computes the symmetric difference (xor) between two bitmaps
 * and returns new bitmap. The caller is responsible for memory management.
 */
roaring_bitmap_t *roaring_bitmap_xor(const roaring_bitmap_t *r1,
                                     const roaring_bitmap_t *r2);

/**
 * Inplace version of roaring_bitmap_xor, modifies r1, r1 != r2.
 */
void roaring_bitmap_xor_inplace(roaring_bitmap_t *r1,
                                const roaring_bitmap_t *r2);

/**
 * Compute the xor of 'number' bitmaps.
 * Caller is responsible for freeing the result.
 */
roaring_bitmap_t *roaring_bitmap_xor_many(size_t number,
                                          const roaring_bitmap_t **rs);

/**
 * Computes the difference (andnot) between two bitmaps and returns new bitmap.
 * Caller is responsible for freeing the result.
 */
roaring_bitmap_t *roaring_bitmap_andnot(const roaring_bitmap_t *r1,
                                        const roaring_bitmap_t *r2);

/**
 * Inplace version of roaring_bitmap_andnot, modifies r1, r1 != r2.
 */
void roaring_bitmap_andnot_inplace(roaring_bitmap_t *r1,
                                   const roaring_bitmap_t *r2);

/**
 * TODO: consider implementing:
 *
 * "Compute the xor of 'number' bitmaps using a heap. This can sometimes be
 *  faster than roaring_bitmap_xor_many which uses a naive algorithm. Caller is
 *  responsible for freeing the result.""
 *
 * roaring_bitmap_t *roaring_bitmap_xor_many_heap(uint32_t number,
 *                                                const roaring_bitmap_t **rs);
 */

/**
 * Frees the memory.
 */
void roaring_bitmap_free(const roaring_bitmap_t *r);

/**
 * A bit of context usable with `roaring_bitmap_*_bulk()` functions
 *
 * Should be initialized with `{0}` (or `memset()` to all zeros).
 * Callers should treat it as an opaque type.
 *
 * A context may only be used with a single bitmap
 * (unless re-initialized to zero), and any modification to a bitmap
 * (other than modifications performed with `_bulk()` functions with the context
 * passed) will invalidate any contexts associated with that bitmap.
 */
typedef struct roaring_bulk_context_s {
    ROARING_CONTAINER_T *container;
    int idx;
    uint16_t key;
    uint8_t typecode;
} roaring_bulk_context_t;

/**
 * Add an item, using context from a previous insert for speed optimization.
 *
 * `context` will be used to store information between calls to make bulk
 * operations faster. `*context` should be zero-initialized before the first
 * call to this function.
 *
 * Modifying the bitmap in any way (other than `-bulk` suffixed functions)
 * will invalidate the stored context, calling this function with a non-zero
 * context after doing any modification invokes undefined behavior.
 *
 * In order to exploit this optimization, the caller should call this function
 * with values with the same "key" (high 16 bits of the value) consecutively.
 */
void roaring_bitmap_add_bulk(roaring_bitmap_t *r,
                             roaring_bulk_context_t *context, uint32_t val);

/**
 * Add value n_args from pointer vals, faster than repeatedly calling
 * `roaring_bitmap_add()`
 *
 * In order to exploit this optimization, the caller should attempt to keep
 * values with the same "key" (high 16 bits of the value) as consecutive
 * elements in `vals`
 */
void roaring_bitmap_add_many(roaring_bitmap_t *r, size_t n_args,
                             const uint32_t *vals);

/**
 * Add value x
 */
void roaring_bitmap_add(roaring_bitmap_t *r, uint32_t x);

/**
 * Add value x
 * Returns true if a new value was added, false if the value already existed.
 */
bool roaring_bitmap_add_checked(roaring_bitmap_t *r, uint32_t x);

/**
 * Add all values in range [min, max]
 */
void roaring_bitmap_add_range_closed(roaring_bitmap_t *r,
                                     uint32_t min, uint32_t max);

/**
 * Add all values in range [min, max)
 */
static inline void roaring_bitmap_add_range(roaring_bitmap_t *r,
                                            uint64_t min, uint64_t max) {
    if(max <= min) return;
    roaring_bitmap_add_range_closed(r, (uint32_t)min, (uint32_t)(max - 1));
}

/**
 * Remove value x
 */
void roaring_bitmap_remove(roaring_bitmap_t *r, uint32_t x);

/**
 * Remove all values in range [min, max]
 */
void roaring_bitmap_remove_range_closed(roaring_bitmap_t *r,
                                        uint32_t min, uint32_t max);

/**
 * Remove all values in range [min, max)
 */
static inline void roaring_bitmap_remove_range(roaring_bitmap_t *r,
                                               uint64_t min, uint64_t max) {
    if(max <= min) return;
    roaring_bitmap_remove_range_closed(r, (uint32_t)min, (uint32_t)(max - 1));
}

/**
 * Remove multiple values
 */
void roaring_bitmap_remove_many(roaring_bitmap_t *r, size_t n_args,
                                const uint32_t *vals);

/**
 * Remove value x
 * Returns true if a new value was removed, false if the value was not existing.
 */
bool roaring_bitmap_remove_checked(roaring_bitmap_t *r, uint32_t x);

/**
 * Check if value is present
 */
bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t val);

/**
 * Check whether a range of values from range_start (included)
 * to range_end (excluded) is present
 */
bool roaring_bitmap_contains_range(const roaring_bitmap_t *r,
                                   uint64_t range_start,
                                   uint64_t range_end);

/**
 * Check if an items is present, using context from a previous insert for speed
 * optimization.
 *
 * `context` will be used to store information between calls to make bulk
 * operations faster. `*context` should be zero-initialized before the first
 * call to this function.
 *
 * Modifying the bitmap in any way (other than `-bulk` suffixed functions)
 * will invalidate the stored context, calling this function with a non-zero
 * context after doing any modification invokes undefined behavior.
 *
 * In order to exploit this optimization, the caller should call this function
 * with values with the same "key" (high 16 bits of the value) consecutively.
 */
bool roaring_bitmap_contains_bulk(const roaring_bitmap_t *r,
                                  roaring_bulk_context_t *context,
                                  uint32_t val);

/**
 * Get the cardinality of the bitmap (number of elements).
 */
uint64_t roaring_bitmap_get_cardinality(const roaring_bitmap_t *r);

/**
 * Returns the number of elements in the range [range_start, range_end).
 */
uint64_t roaring_bitmap_range_cardinality(const roaring_bitmap_t *r,
                                          uint64_t range_start,
                                          uint64_t range_end);

/**
* Returns true if the bitmap is empty (cardinality is zero).
*/
bool roaring_bitmap_is_empty(const roaring_bitmap_t *r);


/**
 * Empties the bitmap.  It will have no auxiliary allocations (so if the bitmap
 * was initialized in client memory via roaring_bitmap_init(), then a call to
 * roaring_bitmap_clear() would be enough to "free" it)
 */
void roaring_bitmap_clear(roaring_bitmap_t *r);

/**
 * Convert the bitmap to a sorted array, output in `ans`.
 *
 * Caller is responsible to ensure that there is enough memory allocated, e.g.
 *
 *     ans = malloc(roaring_bitmap_get_cardinality(bitmap) * sizeof(uint32_t));
 */
void roaring_bitmap_to_uint32_array(const roaring_bitmap_t *r, uint32_t *ans);

/**
 * Store the bitmap to a bitset. This can be useful for people
 * who need the performance and simplicity of a standard bitset.
 * We assume that the input bitset is originally empty (does not
 * have any set bit).
 *
 *   bitset_t * out = bitset_create();
 *   // if the bitset has content in it, call "bitset_clear(out)"
 *   bool success = roaring_bitmap_to_bitset(mybitmap, out); 
 *   // on failure, success will be false.
 *   // You can then query the bitset:
 *   bool is_present = bitset_get(out,  10011 );
 *   // you must free the memory:
 *   bitset_free(out);
 *
 */
bool roaring_bitmap_to_bitset(const roaring_bitmap_t *r, bitset_t * bitset);

/**
 * Convert the bitmap to a sorted array from `offset` by `limit`, output in `ans`.
 *
 * Caller is responsible to ensure that there is enough memory allocated, e.g.
 *
 *     ans = malloc(roaring_bitmap_get_cardinality(limit) * sizeof(uint32_t));
 *
 * Return false in case of failure (e.g., insufficient memory)
 */
bool roaring_bitmap_range_uint32_array(const roaring_bitmap_t *r,
                                       size_t offset, size_t limit,
                                       uint32_t *ans);

/**
 * Remove run-length encoding even when it is more space efficient.
 * Return whether a change was applied.
 */
bool roaring_bitmap_remove_run_compression(roaring_bitmap_t *r);

/**
 * Convert array and bitmap containers to run containers when it is more
 * efficient; also convert from run containers when more space efficient.
 *
 * Returns true if the result has at least one run container.
 * Additional savings might be possible by calling `shrinkToFit()`.
 */
bool roaring_bitmap_run_optimize(roaring_bitmap_t *r);

/**
 * If needed, reallocate memory to shrink the memory usage.
 * Returns the number of bytes saved.
 */
size_t roaring_bitmap_shrink_to_fit(roaring_bitmap_t *r);

/**
 * Write the bitmap to an output pointer, this output buffer should refer to
 * at least `roaring_bitmap_size_in_bytes(r)` allocated bytes.
 *
 * See `roaring_bitmap_portable_serialize()` if you want a format that's
 * compatible with Java and Go implementations.  This format can sometimes be
 * more space efficient than the portable form, e.g. when the data is sparse.
 *
 * Returns how many bytes written, should be `roaring_bitmap_size_in_bytes(r)`.
 *
 * This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x),
 * the data format is going to be big-endian and not compatible with little-endian systems.
 */
size_t roaring_bitmap_serialize(const roaring_bitmap_t *r, char *buf);

/**
 * Use with `roaring_bitmap_serialize()`.
 *
 * (See `roaring_bitmap_portable_deserialize()` if you want a format that's
 * compatible with Java and Go implementations).
 *
 * This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x),
 * the data format is going to be big-endian and not compatible with little-endian systems.
 */
roaring_bitmap_t *roaring_bitmap_deserialize(const void *buf);

/**
 * How many bytes are required to serialize this bitmap (NOT compatible
 * with Java and Go versions)
 */
size_t roaring_bitmap_size_in_bytes(const roaring_bitmap_t *r);

/**
 * Read bitmap from a serialized buffer.
 * In case of failure, NULL is returned.
 *
 * This function is unsafe in the sense that if there is no valid serialized
 * bitmap at the pointer, then many bytes could be read, possibly causing a
 * buffer overflow.  See also roaring_bitmap_portable_deserialize_safe().
 *
 * This is meant to be compatible with the Java and Go versions:
 * https://github.com/RoaringBitmap/RoaringFormatSpec
*
 * This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x),
 * the data format is going to be big-endian and not compatible with little-endian systems.
 */
roaring_bitmap_t *roaring_bitmap_portable_deserialize(const char *buf);

/**
 * Read bitmap from a serialized buffer safely (reading up to maxbytes).
 * In case of failure, NULL is returned.
 *
 * This is meant to be compatible with the Java and Go versions:
 * https://github.com/RoaringBitmap/RoaringFormatSpec
 *
 * The function itself is safe in the sense that it will not cause buffer overflows.
 * However, for correct operations, it is assumed that the bitmap read was once
 * serialized from a valid bitmap (i.e., it follows the format specification).
 * If you provided an incorrect input (garbage), then the bitmap read may not be in
 * a valid state and following operations may not lead to sensible results.
 * In particular, the serialized array containers need to be in sorted order, and the
 * run containers should be in sorted non-overlapping order. This is is guaranteed to
 * happen when serializing an existing bitmap, but not for random inputs.
 *
 * This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x),
 * the data format is going to be big-endian and not compatible with little-endian systems.
 */
roaring_bitmap_t *roaring_bitmap_portable_deserialize_safe(const char *buf,
                                                           size_t maxbytes);

/**
 * Read bitmap from a serialized buffer.
 * In case of failure, NULL is returned.
 *
 * Bitmap returned by this function can be used in all readonly contexts.
 * Bitmap must be freed as usual, by calling roaring_bitmap_free().
 * Underlying buffer must not be freed or modified while it backs any bitmaps.
 *
 * The function is unsafe in the following ways:
 * 1) It may execute unaligned memory accesses.
 * 2) A buffer overflow may occur if buf does not point to a valid serialized
 *    bitmap.
 *
 * This is meant to be compatible with the Java and Go versions:
 * https://github.com/RoaringBitmap/RoaringFormatSpec
 *
 * This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x),
 * the data format is going to be big-endian and not compatible with little-endian systems.
 */
roaring_bitmap_t *roaring_bitmap_portable_deserialize_frozen(const char *buf);

/**
 * Check how many bytes would be read (up to maxbytes) at this pointer if there
 * is a bitmap, returns zero if there is no valid bitmap.
 *
 * This is meant to be compatible with the Java and Go versions:
 * https://github.com/RoaringBitmap/RoaringFormatSpec
 */
size_t roaring_bitmap_portable_deserialize_size(const char *buf,
                                                size_t maxbytes);

/**
 * How many bytes are required to serialize this bitmap.
 *
 * This is meant to be compatible with the Java and Go versions:
 * https://github.com/RoaringBitmap/RoaringFormatSpec
 */
size_t roaring_bitmap_portable_size_in_bytes(const roaring_bitmap_t *r);

/**
 * Write a bitmap to a char buffer.  The output buffer should refer to at least
 * `roaring_bitmap_portable_size_in_bytes(r)` bytes of allocated memory.
 *
 * Returns how many bytes were written which should match
 * `roaring_bitmap_portable_size_in_bytes(r)`.
 *
 * This is meant to be compatible with the Java and Go versions:
 * https://github.com/RoaringBitmap/RoaringFormatSpec
 *
 * This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x),
 * the data format is going to be big-endian and not compatible with little-endian systems.
 */
size_t roaring_bitmap_portable_serialize(const roaring_bitmap_t *r, char *buf);

/*
 * "Frozen" serialization format imitates memory layout of roaring_bitmap_t.
 * Deserialized bitmap is a constant view of the underlying buffer.
 * This significantly reduces amount of allocations and copying required during
 * deserialization.
 * It can be used with memory mapped files.
 * Example can be found in benchmarks/frozen_benchmark.c
 *
 *         [#####] const roaring_bitmap_t *
 *          | | |
 *     +----+ | +-+
 *     |      |   |
 * [#####################################] underlying buffer
 *
 * Note that because frozen serialization format imitates C memory layout
 * of roaring_bitmap_t, it is not fixed. It is different on big/little endian
 * platforms and can be changed in future.
 */

/**
 * Returns number of bytes required to serialize bitmap using frozen format.
 */
size_t roaring_bitmap_frozen_size_in_bytes(const roaring_bitmap_t *r);

/**
 * Serializes bitmap using frozen format.
 * Buffer size must be at least roaring_bitmap_frozen_size_in_bytes().
 *
 * This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x),
 * the data format is going to be big-endian and not compatible with little-endian systems.
 */
void roaring_bitmap_frozen_serialize(const roaring_bitmap_t *r, char *buf);

/**
 * Creates constant bitmap that is a view of a given buffer.
 * Buffer data should have been written by `roaring_bitmap_frozen_serialize()`
 * Its beginning must also be aligned by 32 bytes.
 * Length must be equal exactly to `roaring_bitmap_frozen_size_in_bytes()`.
 * In case of failure, NULL is returned.
 *
 * Bitmap returned by this function can be used in all readonly contexts.
 * Bitmap must be freed as usual, by calling roaring_bitmap_free().
 * Underlying buffer must not be freed or modified while it backs any bitmaps.
 *
 * This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x),
 * the data format is going to be big-endian and not compatible with little-endian systems.
 */
const roaring_bitmap_t *roaring_bitmap_frozen_view(const char *buf,
                                                   size_t length);

/**
 * Iterate over the bitmap elements. The function iterator is called once for
 * all the values with ptr (can be NULL) as the second parameter of each call.
 *
 * `roaring_iterator` is simply a pointer to a function that returns bool
 * (true means that the iteration should continue while false means that it
 * should stop), and takes (uint32_t,void*) as inputs.
 *
 * Returns true if the roaring_iterator returned true throughout (so that all
 * data points were necessarily visited).
 *
 * Iteration is ordered: from the smallest to the largest elements.
 */
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);

/**
 * Return true if the two bitmaps contain the same elements.
 */
bool roaring_bitmap_equals(const roaring_bitmap_t *r1,
                           const roaring_bitmap_t *r2);

/**
 * Return true if all the elements of r1 are also in r2.
 */
bool roaring_bitmap_is_subset(const roaring_bitmap_t *r1,
                              const roaring_bitmap_t *r2);

/**
 * Return true if all the elements of r1 are also in r2, and r2 is strictly
 * greater than r1.
 */
bool roaring_bitmap_is_strict_subset(const roaring_bitmap_t *r1,
                                     const roaring_bitmap_t *r2);

/**
 * (For expert users who seek high performance.)
 *
 * Computes the union between two bitmaps and returns new bitmap. The caller is
 * responsible for memory management.
 *
 * The lazy version defers some computations such as the maintenance of the
 * cardinality counts. Thus you must call `roaring_bitmap_repair_after_lazy()`
 * after executing "lazy" computations.
 *
 * It is safe to repeatedly call roaring_bitmap_lazy_or_inplace on the result.
 *
 * `bitsetconversion` is a flag which determines whether container-container
 * operations force a bitset conversion.
 */
roaring_bitmap_t *roaring_bitmap_lazy_or(const roaring_bitmap_t *r1,
                                         const roaring_bitmap_t *r2,
                                         const bool bitsetconversion);

/**
 * (For expert users who seek high performance.)
 *
 * Inplace version of roaring_bitmap_lazy_or, modifies r1.
 *
 * `bitsetconversion` is a flag which determines whether container-container
 * operations force a bitset conversion.
 */
void roaring_bitmap_lazy_or_inplace(roaring_bitmap_t *r1,
                                    const roaring_bitmap_t *r2,
                                    const bool bitsetconversion);

/**
 * (For expert users who seek high performance.)
 *
 * Execute maintenance on a bitmap created from `roaring_bitmap_lazy_or()`
 * or modified with `roaring_bitmap_lazy_or_inplace()`.
 */
void roaring_bitmap_repair_after_lazy(roaring_bitmap_t *r1);

/**
 * Computes the symmetric difference between two bitmaps and returns new bitmap.
 * The caller is responsible for memory management.
 *
 * The lazy version defers some computations such as the maintenance of the
 * cardinality counts. Thus you must call `roaring_bitmap_repair_after_lazy()`
 * after executing "lazy" computations.
 *
 * It is safe to repeatedly call `roaring_bitmap_lazy_xor_inplace()` on
 * the result.
 */
roaring_bitmap_t *roaring_bitmap_lazy_xor(const roaring_bitmap_t *r1,
                                          const roaring_bitmap_t *r2);

/**
 * (For expert users who seek high performance.)
 *
 * Inplace version of roaring_bitmap_lazy_xor, modifies r1. r1 != r2
 */
void roaring_bitmap_lazy_xor_inplace(roaring_bitmap_t *r1,
                                     const roaring_bitmap_t *r2);

/**
 * Compute the negation of the bitmap in the interval [range_start, range_end).
 * The number of negated values is range_end - range_start.
 * Areas outside the range are passed through unchanged.
 */
roaring_bitmap_t *roaring_bitmap_flip(const roaring_bitmap_t *r1,
                                      uint64_t range_start, uint64_t range_end);

/**
 * compute (in place) the negation of the roaring bitmap within a specified
 * interval: [range_start, range_end). The number of negated values is
 * range_end - range_start.
 * Areas outside the range are passed through unchanged.
 */
void roaring_bitmap_flip_inplace(roaring_bitmap_t *r1, uint64_t range_start,
                                 uint64_t range_end);

/**
 * Selects the element at index 'rank' where the smallest element is at index 0.
 * If the size of the roaring bitmap is strictly greater than rank, then this
 * function returns true and sets element to the element of given rank.
 * Otherwise, it returns false.
 */
bool roaring_bitmap_select(const roaring_bitmap_t *r, uint32_t rank,
                           uint32_t *element);

/**
 * roaring_bitmap_rank returns the number of integers that are smaller or equal
 * to x. Thus if x is the first element, this function will return 1. If
 * x is smaller than the smallest element, this function will return 0.
 *
 * The indexing convention differs between roaring_bitmap_select and
 * roaring_bitmap_rank: roaring_bitmap_select refers to the smallest value
 * as having index 0, whereas roaring_bitmap_rank returns 1 when ranking
 * the smallest value.
 */
uint64_t roaring_bitmap_rank(const roaring_bitmap_t *r, uint32_t x);

/**
 * Returns the smallest value in the set, or UINT32_MAX if the set is empty.
 */
uint32_t roaring_bitmap_minimum(const roaring_bitmap_t *r);

/**
 * Returns the greatest value in the set, or 0 if the set is empty.
 */
uint32_t roaring_bitmap_maximum(const roaring_bitmap_t *r);

/**
 * (For advanced users.)
 *
 * Collect statistics about the bitmap, see roaring_types.h for
 * a description of roaring_statistics_t
 */
void roaring_bitmap_statistics(const roaring_bitmap_t *r,
                               roaring_statistics_t *stat);

/*********************
* What follows is code use to iterate through values in a roaring bitmap

roaring_bitmap_t *r =...
roaring_uint32_iterator_t i;
roaring_create_iterator(r, &i);
while(i.has_value) {
  printf("value = %d\n", i.current_value);
  roaring_advance_uint32_iterator(&i);
}

Obviously, if you modify the underlying bitmap, the iterator
becomes invalid. So don't.
*/

typedef struct roaring_uint32_iterator_s {
    const roaring_bitmap_t *parent;  // owner
    int32_t container_index;         // point to the current container index
    int32_t in_container_index;  // for bitset and array container, this is out
                                 // index
    int32_t run_index;           // for run container, this points  at the run

    uint32_t current_value;
    bool has_value;

    const ROARING_CONTAINER_T
        *container;  // should be:
                     // parent->high_low_container.containers[container_index];
    uint8_t typecode;  // should be:
                       // parent->high_low_container.typecodes[container_index];
    uint32_t highbits;  // should be:
                        // parent->high_low_container.keys[container_index]) <<
                        // 16;

} roaring_uint32_iterator_t;

/**
 * Initialize an iterator object that can be used to iterate through the
 * values. If there is a  value, then this iterator points to the first value
 * and `it->has_value` is true. The value is in `it->current_value`.
 */
void roaring_init_iterator(const roaring_bitmap_t *r,
                           roaring_uint32_iterator_t *newit);

/**
 * Initialize an iterator object that can be used to iterate through the
 * values. If there is a value, then this iterator points to the last value
 * and `it->has_value` is true. The value is in `it->current_value`.
 */
void roaring_init_iterator_last(const roaring_bitmap_t *r,
                                roaring_uint32_iterator_t *newit);

/**
 * Create an iterator object that can be used to iterate through the values.
 * Caller is responsible for calling `roaring_free_iterator()`.
 *
 * The iterator is initialized (this function calls `roaring_init_iterator()`)
 * If there is a value, then this iterator points to the first value and
 * `it->has_value` is true.  The value is in `it->current_value`.
 */
roaring_uint32_iterator_t *roaring_create_iterator(const roaring_bitmap_t *r);

/**
* Advance the iterator. If there is a new value, then `it->has_value` is true.
* The new value is in `it->current_value`. Values are traversed in increasing
* orders. For convenience, returns `it->has_value`.
*/
bool roaring_advance_uint32_iterator(roaring_uint32_iterator_t *it);

/**
* Decrement the iterator. If there's a new value, then `it->has_value` is true.
* The new value is in `it->current_value`. Values are traversed in decreasing
* order. For convenience, returns `it->has_value`.
*/
bool roaring_previous_uint32_iterator(roaring_uint32_iterator_t *it);

/**
 * Move the iterator to the first value >= `val`. If there is a such a value,
 * then `it->has_value` is true. The new value is in `it->current_value`.
 * For convenience, returns `it->has_value`.
 */
bool roaring_move_uint32_iterator_equalorlarger(roaring_uint32_iterator_t *it,
                                                uint32_t val);

/**
 * Creates a copy of an iterator.
 * Caller must free it.
 */
roaring_uint32_iterator_t *roaring_copy_uint32_iterator(
    const roaring_uint32_iterator_t *it);

/**
 * Free memory following `roaring_create_iterator()`
 */
void roaring_free_uint32_iterator(roaring_uint32_iterator_t *it);

/*
 * Reads next ${count} values from iterator into user-supplied ${buf}.
 * Returns the number of read elements.
 * This number can be smaller than ${count}, which means that iterator is drained.
 *
 * This function satisfies semantics of iteration and can be used together with
 * other iterator functions.
 *  - first value is copied from ${it}->current_value
 *  - after function returns, iterator is positioned at the next element
 */
uint32_t roaring_read_uint32_iterator(roaring_uint32_iterator_t *it,
                                      uint32_t* buf, uint32_t count);

#ifdef __cplusplus
} } }  // extern "C" { namespace roaring { namespace api {
#endif

#endif  /* ROARING_H */

#ifdef __cplusplus
    /**
     * Best practices for C++ headers is to avoid polluting global scope.
     * But for C compatibility when just `roaring.h` is included building as
     * C++, default to global access for the C public API.
     *
     * BUT when `roaring.hh` is included instead, it sets this flag.  That way
     * explicit namespacing must be used to get the C functions.
     *
     * This is outside the include guard so that if you include BOTH headers,
     * the order won't matter; you still get the global definitions.
     */
    #if !defined(ROARING_API_NOT_IN_GLOBAL_NAMESPACE)
        using namespace ::roaring::api;
    #endif
#endif
/* end file include/roaring/roaring.h */
/* begin file include/roaring/memory.h */
#ifndef INCLUDE_ROARING_MEMORY_H_
#define INCLUDE_ROARING_MEMORY_H_

#ifdef __cplusplus
extern "C" {
#endif

#include <stddef.h>  // for size_t

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  // INCLUDE_ROARING_MEMORY_H_
/* end file include/roaring/memory.h */