/* used for http://dmalloc.com/ Dmalloc - Debug Malloc Library */ #ifdef DMALLOC #include"dmalloc.h" #endif
#include"roaring.h"/* include public API definitions */ /* begin file include/roaring/isadetection.h */ #ifndef ROARING_ISADETECTION_H #define ROARING_ISADETECTION_H #ifdefined(__x86_64__) || defined(_M_AMD64) // x64
#ifndef CROARING_COMPILER_SUPPORTS_AVX512 #ifdef __has_include // We want to make sure that the AVX-512 functions are only built on compilers // fully supporting AVX-512. #if __has_include(<avx512vbmi2intrin.h>) #define CROARING_COMPILER_SUPPORTS_AVX512 1 #endif// #if __has_include(<avx512vbmi2intrin.h>) #endif// #ifdef __has_include
// Visual Studio 2019 and up support AVX-512 #ifdef _MSC_VER #if _MSC_VER >= 1920 #define CROARING_COMPILER_SUPPORTS_AVX512 1 #endif// #if _MSC_VER >= 1920 #endif// #ifdef _MSC_VER #endif// #ifndef CROARING_COMPILER_SUPPORTS_AVX512
/* default initial size of a run container
setting it to zero delays the malloc.*/ enum { RUN_DEFAULT_INIT_SIZE = 0 };
/* default initial size of an array container
setting it to zero delays the malloc */ enum { ARRAY_DEFAULT_INIT_SIZE = 0 };
/* automatic bitset conversion during lazy or */ #ifndef LAZY_OR_BITSET_CONVERSION #define LAZY_OR_BITSET_CONVERSION true #endif
/* automatically attempt to convert a bitset to a full run during lazy
* evaluation */ #ifndef LAZY_OR_BITSET_CONVERSION_TO_FULL #define LAZY_OR_BITSET_CONVERSION_TO_FULL true #endif
/* automatically attempt to convert a bitset to a full run */ #ifndef OR_BITSET_CONVERSION_TO_FULL #define OR_BITSET_CONVERSION_TO_FULL true #endif
/* Computes the intersection between one small and one large set of uint16_t.
* Stores the result into buffer and return the number of elements. */ static int32_t intersect_skewed_uint16(const uint16_t *smallarray, size_t size_s, const uint16_t *largearray, size_t size_l,
uint16_t *buffer);
/* Computes the size of the intersection between one small and one large set of
* uint16_t. */ static int32_t intersect_skewed_uint16_cardinality(const uint16_t *smallarray,
size_t size_s, const uint16_t *largearray,
size_t size_l);
/* Check whether the size of the intersection between one small and one large
* set of uint16_t is non-zero. */ staticbool intersect_skewed_uint16_nonempty(const uint16_t *smallarray, size_t size_s, const uint16_t *largearray,
size_t size_l); /** *Genericintersectionfunction.
*/ static int32_t intersect_uint16(const uint16_t *A, const size_t lenA, const uint16_t *B, const size_t lenB, uint16_t *out); /** *Computethesizeoftheintersection(generic).
*/ static int32_t intersect_uint16_cardinality(const uint16_t *A, const size_t lenA, const uint16_t *B, const size_t lenB);
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)));
}
#define CAST_array(c) CAST(array_container_t *, c) // safer downcast #define const_CAST_array(c) CAST(const array_container_t *, c) #define movable_CAST_array(c) movable_CAST(array_container_t **, c)
/* Create a new array with default. Return NULL in case of failure. See also
* array_container_create_given_capacity. */ static array_container_t *array_container_create(void);
/* Create a new array with a specified capacity size. Return NULL in case of
* failure. */ static array_container_t *array_container_create_given_capacity(int32_t size);
/* Create a new array containing all values in [min,max). */ static array_container_t *array_container_create_range(uint32_t min, uint32_t max);
/* Copy one container into another. We assume that they are distinct. */ staticvoid array_container_copy(const array_container_t *src, array_container_t *dst);
/* Add all the values in [min,max) (included) at a distance k*step from min. ThecontainermusthaveasizelessorequaltoDEFAULT_MAX_SIZEafterthis
addition. */ staticvoid array_container_add_from_range(array_container_t *arr, uint32_t min,
uint32_t max, uint16_t step);
/* check whether the cardinality is equal to the capacity (this does not mean
* that it contains 1<<16 elements) */ staticinlinebool array_container_full(const array_container_t *array) { return array->cardinality == array->capacity;
}
/* Compute the union of `src_1' and `src_2' and write the result to `dst'
* It is assumed that `dst' is distinct from both `src_1' and `src_2'. */ staticvoid array_container_union(const array_container_t *src_1, const array_container_t *src_2,
array_container_t *dst);
/* Computes the intersection of src_1 and src_2 and write the result to
* dst. It is assumed that dst is distinct from both src_1 and src_2. */ staticvoid array_container_intersection(const array_container_t *src_1, const array_container_t *src_2,
array_container_t *dst);
/* computers the size of the intersection between two arrays.
*/ staticint array_container_intersection_cardinality(const array_container_t *src_1, const array_container_t *src_2);
/* computes the intersection of array1 and array2 and write the result to *array1.
* */ staticvoid array_container_intersection_inplace(array_container_t *src_1, const array_container_t *src_2);
/* Computes the difference of array1 and array2 and write the result *toarrayout. *Arrayoutdoesnotneedtobedistinctfromarray_1
*/ staticvoid array_container_andnot(const array_container_t *array_1, const array_container_t *array_2,
array_container_t *out);
/* Append x to the set. Assumes that the value is larger than any preceding
* values. */ staticinlinevoid 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);
}
/* Add value to the set. Returns true if x was not already present. */ staticinlinebool array_container_add(array_container_t *arr, uint16_t value) { return array_container_try_add(arr, value, INT32_MAX) == 1;
}
/* Remove x from the set. Returns true if x was present. */ staticinlinebool array_container_remove(array_container_t *arr,
uint16_t pos) { const int32_t idx = binarySearch(arr->array, arr->cardinality, pos); constbool 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;
}
/* Check whether x is present. */ staticinlinebool array_container_contains(const array_container_t *arr,
uint16_t pos) { // return binarySearch(arr->array, arr->cardinality, pos) >= 0; // binary search with fallback to linear search for short ranges
int32_t low = 0; const uint16_t *carr = (const uint16_t *)arr->array;
int32_t high = arr->cardinality - 1; // while (high - low >= 0) { while (high >= low + 16) {
int32_t middleIndex = (low + high) >> 1;
uint16_t middleValue = carr[middleIndex]; if (middleValue < pos) {
low = middleIndex + 1;
} elseif (middleValue > pos) {
high = middleIndex - 1;
} else { returntrue;
}
}
for (int i = low; i <= high; i++) {
uint16_t v = carr[i]; if (v == pos) { returntrue;
} if (v > pos) returnfalse;
} returnfalse;
}
//* Check whether a range of values from range_start (included) to range_end //(excluded) is present. */ staticinlinebool 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);
// Empty range is always included if (range_count <= 0) { returntrue;
} if (range_count > arr->cardinality) { returnfalse;
}
const int32_t start =
binarySearch(arr->array, arr->cardinality, rs_included); // If this sorted array contains all items in the range: // * the start item must be found // * the last item in range range_count must exist, and be the expected end // value return (start >= 0) && (arr->cardinality >= start + range_count) &&
(arr->array[start + range_count - 1] == re_included);
}
/* Returns the smallest value (assumes not empty) */ staticinline uint16_t array_container_minimum(const array_container_t *arr) { if (arr->cardinality == 0) return0; return arr->array[0];
}
/* Returns the largest value (assumes not empty) */ staticinline uint16_t array_container_maximum(const array_container_t *arr) { if (arr->cardinality == 0) return0; return arr->array[arr->cardinality - 1];
}
/* Returns the number of values equal or smaller than x */ staticinlineint array_container_rank(const array_container_t *arr, uint16_t x) { const int32_t idx = binarySearch(arr->array, arr->cardinality, x); constbool is_present = idx >= 0; if (is_present) { return idx + 1;
} else { return -idx - 1;
}
}
/* bulk version of array_container_rank(); return number of consumed elements
*/ staticinline 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; // stop at next container
/* Set the bit in [begin,end). WARNING: as of April 2016, this method is slow *and
* should not be used in performance-sensitive code. Ever. */ staticvoid bitset_container_set_range(bitset_container_t *bitset, uint32_t begin,
uint32_t end);
/* Unset the ith bit. Currently unused. Could be used for optimization. */ /*static inline void bitset_container_unset(bitset_container_t *bitset, uint16_tpos){ uint64_tshift=6; uint64_toffset; uint64_tp=pos; ASM_SHIFT_RIGHT(p,shift,offset); uint64_tload=bitset->words[offset]; ASM_CLEAR_BIT_DEC_WAS_SET(load,p,bitset->cardinality); bitset->words[offset]=load;
}*/
/* Add `pos' to `bitset'. Returns true if `pos' was not present. Might be slower
* than bitset_container_set. */ staticinlinebool 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]; // could be possibly slightly further optimized const int32_t oldcard = bitset->cardinality;
ASM_SET_BIT_INC_WAS_CLEAR(load, p, bitset->cardinality);
bitset->words[offset] = load; return bitset->cardinality - oldcard;
}
/* Remove `pos' from `bitset'. Returns true if `pos' was present. Might be
* slower than bitset_container_unset. */ staticinlinebool 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]; // could be possibly slightly further optimized const int32_t oldcard = bitset->cardinality;
ASM_CLEAR_BIT_DEC_WAS_SET(load, p, bitset->cardinality);
bitset->words[offset] = load; return oldcard - bitset->cardinality;
}
/* Get the value of the ith bit. */ staticinlinebool 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;
}
/* Get the value of the ith bit. */
static 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
/*
* Check if all bits are set in a range of positions from pos_start (included)
* to pos_end (excluded).
*/
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;
for (uint32_t i = start + 1;
(i < BITSET_CONTAINER_SIZE_IN_WORDS) && (i < end); ++i) {
if (bitset->words[i] != UINT64_C(0xFFFFFFFFFFFFFFFF)) return false;
}
/*
* Check whether a range of bits from position `pos_start' (included) to
* `pos_end' (excluded) is present in `bitset'. Calls bitset_container_get_all.
*/
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);
}
/* Get the number of bits set */
ALLOW_UNALIGNED
static inline int bitset_container_cardinality(
const bitset_container_t *bitset) {
return bitset->cardinality;
}
/* Copy one container into another. We assume that they are distinct. */
static void bitset_container_copy(const bitset_container_t *source,
bitset_container_t *dest);
/* Add all the values [min,max) at a distance k*step from min: min,
* min+step,.... */
static void bitset_container_add_from_range(bitset_container_t *bitset, uint32_t min,
uint32_t max, uint16_t step);
/* Get the number of bits set (force computation). This does not modify bitset.
* To update the cardinality, you should do
* bitset->cardinality = bitset_container_compute_cardinality(bitset).*/
static int bitset_container_compute_cardinality(const bitset_container_t *bitset);
/* Check whether this bitset is empty,
* it never modifies the bitset struct. */
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;
}
/* Get whether there is at least one bit set (see bitset_container_empty for
the reverse), the bitset is never modified */
static inline bool bitset_container_const_nonzero_cardinality(
const bitset_container_t *bitset) {
return !bitset_container_empty(bitset);
}
/*
* Check whether the two bitsets intersect
*/
static bool bitset_container_intersect(const bitset_container_t *src_1,
const bitset_container_t *src_2);
/* Computes the union of bitsets `src_1' and `src_2' into `dst' and return the
* cardinality. */
static int bitset_container_or(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Computes the union of bitsets `src_1' and `src_2' and return the cardinality.
*/
static int bitset_container_or_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
/* Computes the union of bitsets `src_1' and `src_2' into `dst' and return the
* cardinality. Same as bitset_container_or. */
static int bitset_container_union(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Computes the union of bitsets `src_1' and `src_2' and return the
* cardinality. Same as bitset_container_or_justcard. */
static int bitset_container_union_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
/* Computes the union of bitsets `src_1' and `src_2' into `dst', but does
* not update the cardinality. Provided to optimize chained operations. */
static int bitset_container_union_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Computes the union of bitsets `src_1' and `src_2' into `dst', but does not
* update the cardinality. Provided to optimize chained operations. */
static int bitset_container_or_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Computes the intersection of bitsets `src_1' and `src_2' into `dst' and
* return the cardinality. */
static int bitset_container_and(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Computes the intersection of bitsets `src_1' and `src_2' and return the
* cardinality. */
static int bitset_container_and_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
/* Computes the intersection of bitsets `src_1' and `src_2' into `dst' and
* return the cardinality. Same as bitset_container_and. */
static int bitset_container_intersection(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Computes the intersection of bitsets `src_1' and `src_2' and return the
* cardinality. Same as bitset_container_and_justcard. */
static int bitset_container_intersection_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
/* Computes the intersection of bitsets `src_1' and `src_2' into `dst', but does
* not update the cardinality. Provided to optimize chained operations. */
static int bitset_container_intersection_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Computes the intersection of bitsets `src_1' and `src_2' into `dst', but does
* not update the cardinality. Provided to optimize chained operations. */
static int bitset_container_and_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Computes the exclusive or of bitsets `src_1' and `src_2' into `dst' and
* return the cardinality. */
static int bitset_container_xor(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Computes the exclusive or of bitsets `src_1' and `src_2' and return the
* cardinality. */
static int bitset_container_xor_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
/* Computes the exclusive or of bitsets `src_1' and `src_2' into `dst', but does
* not update the cardinality. Provided to optimize chained operations. */
static int bitset_container_xor_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Computes the and not of bitsets `src_1' and `src_2' into `dst' and return the
* cardinality. */
static int bitset_container_andnot(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Computes the and not of bitsets `src_1' and `src_2' and return the
* cardinality. */
static int bitset_container_andnot_justcard(const bitset_container_t *src_1,
const bitset_container_t *src_2);
/* Computes the and not or of bitsets `src_1' and `src_2' into `dst', but does
* not update the cardinality. Provided to optimize chained operations. */
static int bitset_container_andnot_nocard(const bitset_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
static void bitset_container_offset(const bitset_container_t *c, container_t **loc,
container_t **hic, uint16_t offset);
/*
* Write out the 16-bit integers contained in this container as a list of 32-bit
* integers using base
* as the starting value (it might be expected that base has zeros in its 16
* least significant bits).
* The function returns the number of values written.
* The caller is responsible for allocating enough memory in out.
* The out pointer should point to enough memory (the cardinality times 32
* bits).
*/
static int bitset_container_to_uint32_array(uint32_t *out,
const bitset_container_t *bc,
uint32_t base);
/*
* Print this container using printf (useful for debugging).
*/
static void bitset_container_printf(const bitset_container_t *v);
/*
* Print this container using printf as a comma-separated list of 32-bit
* integers starting at base.
*/
static void bitset_container_printf_as_uint32_array(const bitset_container_t *v,
uint32_t base);
/**
* Writes the underlying array to buf, outputs how many bytes were written.
* This is meant to be byte-by-byte compatible with the Java and Go versions of
* Roaring.
* The number of bytes written should be
* bitset_container_size_in_bytes(container).
*/
static int32_t bitset_container_write(const bitset_container_t *container, char *buf);
/**
* Reads the instance from buf, outputs how many bytes were read.
* This is meant to be byte-by-byte compatible with the Java and Go versions of
* Roaring.
* The number of bytes read should be bitset_container_size_in_bytes(container).
* You need to provide the (known) cardinality.
*/
static int32_t bitset_container_read(int32_t cardinality,
bitset_container_t *container, const char *buf);
/**
* Return the serialized size in bytes of a container (see
* bitset_container_write).
* This is meant to be compatible with the Java and Go versions of Roaring and
* assumes
* that the cardinality of the container is already known or can be computed.
*/
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);
}
/**
* Return true if the two containers have the same content.
*/
static bool bitset_container_equals(const bitset_container_t *container1,
const bitset_container_t *container2);
/**
* Return true if container1 is a subset of container2.
*/
static bool bitset_container_is_subset(const bitset_container_t *container1,
const bitset_container_t *container2);
/**
* If the element of given rank is in this container, supposing that the first
* element has rank start_rank, then the function returns true and sets element
* accordingly.
* Otherwise, it returns false and update start_rank.
*/
static bool bitset_container_select(const bitset_container_t *container,
uint32_t *start_rank, uint32_t rank,
uint32_t *element);
/* Returns the smallest value (assumes not empty) */
static uint16_t bitset_container_minimum(const bitset_container_t *container);
/* Returns the largest value (assumes not empty) */
static uint16_t bitset_container_maximum(const bitset_container_t *container);
/* Returns the number of values equal or smaller than x */
static int bitset_container_rank(const bitset_container_t *container, uint16_t x);
/* bulk version of bitset_container_rank(); return number of consumed elements
*/
static 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);
/* Returns the index of x , if not exsist return -1 */
static int bitset_container_get_index(const bitset_container_t *container, uint16_t x);
/* Returns the index of the first value equal or larger than x, or -1 */
static int bitset_container_index_equalorlarger(const bitset_container_t *container,
uint16_t x);
// Note: in pure C++ code, you should avoid putting `using` in header files
using api::roaring_iterator;
using api::roaring_iterator64;
namespace internal {
#endif
/* struct rle16_s - run length pair
*
* @value: start position of the run
* @length: length of the run is `length + 1`
*
* An RLE pair {v, l} would represent the integers between the interval
* [v, v+l+1], e.g. {3, 2} = [3, 4, 5].
*/
struct rle16_s {
uint16_t value;
uint16_t length;
};
/* struct run_container_s - run container bitmap
*
* @n_runs: number of rle_t pairs in `runs`.
* @capacity: capacity in rle_t pairs `runs` can hold.
* @runs: pairs of rle_t.
*/
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) // safer downcast
#define const_CAST_run(c) CAST(const run_container_t *, c)
#define movable_CAST_run(c) movable_CAST(run_container_t **, c)
/* Create a new run container. Return NULL in case of failure. */
static run_container_t *run_container_create(void);
/* Create a new run container with given capacity. Return NULL in case of
* failure. */
static run_container_t *run_container_create_given_capacity(int32_t size);
/*
* Shrink the capacity to the actual size, return the number of bytes saved.
*/
static int run_container_shrink_to_fit(run_container_t *src);
/*
* Effectively deletes the value at index index, repacking data.
*/
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--;
}
/**
* Good old binary search through rle data
*/
static 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);
}
/*
* Returns index of the run which contains $ikey
*/
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);
}
/**
* Returns number of runs which can'be be merged with the key because they
* are less than the key.
* Note that [5,6,7,8] can be merged with the key 9 and won't be counted.
*/
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) { // uint32 arithmetic
low = middleIndex + 1;
} else if (key < min_value) {
high = middleIndex - 1;
} else {
return middleIndex;
}
}
return low;
}
/**
* increase capacity to at least min. Whether the
* existing data needs to be copied over depends on copy. If "copy" is false,
* then the new content will be uninitialized, otherwise a copy is made.
*/
static void run_container_grow(run_container_t *run, int32_t min, bool copy);
/**
* Moves the data so that we can write data at index
*/
static inline void makeRoomAtIndex(run_container_t *run, uint16_t index) {
/* This function calls realloc + memmove sequentially to move by one index.
* Potentially copying twice the array.
*/
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++;
}
/* Add `pos' to `run'. Returns true if `pos' was not present. */
static bool run_container_add(run_container_t *run, uint16_t pos);
/* Remove `pos' from `run'. Returns true if `pos' was present. */
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; // points to preceding value, possibly -1
if (index >= 0) { // possible match
int32_t offset = pos - run->runs[index].value;
int32_t le = run->runs[index].length;
if (offset < le) {
// need to break in two
run->runs[index].length = (uint16_t)(offset - 1);
// need to insert
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;
}
}
// no match
return false;
}
/* Check whether `pos' is present in `run'. */
static 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; // points to preceding value, possibly -1
if (index != -1) { // possible match
int32_t offset = pos - run->runs[index].value;
int32_t le = run->runs[index].length;
if (offset <= le) return true;
}
return false;
}
/*
* Check whether all positions in a range of positions from pos_start (included)
* to pos_end (excluded) is present in `run'.
*/
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);
}
/* Get the cardinality of `run'. Requires an actual computation. */
static int run_container_cardinality(const run_container_t *run);
/* Card > 0?, see run_container_empty for the reverse */
static inline bool run_container_nonzero_cardinality(
const run_container_t *run) {
return run->n_runs > 0; // runs never empty
}
/* Card == 0?, see run_container_nonzero_cardinality for the reverse */
static inline bool run_container_empty(const run_container_t *run) {
return run->n_runs == 0; // runs never empty
}
/* Copy one container into another. We assume that they are distinct. */
static void run_container_copy(const run_container_t *src, run_container_t *dst);
/**
* Append run described by vl to the run container, possibly merging.
* It is assumed that the run would be inserted at the end of the container, no
* check is made.
* It is assumed that the run container has the necessary capacity: caller is
* responsible for checking memory capacity.
*
*
* This is not a safe function, it is meant for performance: use with care.
*/
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) { // we add a new one
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) { // we merge
previousrl->length = (uint16_t)(newend - 1 - previousrl->value);
run->runs[run->n_runs - 1] = *previousrl;
}
}
}
/**
* Like run_container_append but it is assumed that the content of run is empty.
*/
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;
}
/**
* append a single value given by val to the run container, possibly merging.
* It is assumed that the value would be inserted at the end of the container,
* no check is made.
* It is assumed that the run container has the necessary capacity: caller is
* responsible for checking memory capacity.
*
* This is not a safe function, it is meant for performance: use with care.
*/
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) { // we add a new one
*previousrl = CROARING_MAKE_RLE16(val, 0);
run->runs[run->n_runs] = *previousrl;
run->n_runs++;
} else if (val == previousend + 1) { // we merge
previousrl->length++;
run->runs[run->n_runs - 1] = *previousrl;
}
}
/**
* Like run_container_append_value but it is assumed that the content of run is
* empty.
*/
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;
}
/* Check whether the container spans the whole chunk (cardinality = 1<<16).
* This check can be done in constant time (inexpensive). */
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);
}
/* Compute the union of `src_1' and `src_2' and write the result to `dst'
* It is assumed that `dst' is distinct from both `src_1' and `src_2'. */
static void run_container_union(const run_container_t *src_1,
const run_container_t *src_2, run_container_t *dst);
/* Compute the union of `src_1' and `src_2' and write the result to `src_1' */
static void run_container_union_inplace(run_container_t *src_1,
const run_container_t *src_2);
/* Compute the intersection of src_1 and src_2 and write the result to
* dst. It is assumed that dst is distinct from both src_1 and src_2. */
static void run_container_intersection(const run_container_t *src_1,
const run_container_t *src_2,
run_container_t *dst);
/* Compute the size of the intersection of src_1 and src_2 . */
static int run_container_intersection_cardinality(const run_container_t *src_1,
const run_container_t *src_2);
/* Compute the symmetric difference of `src_1' and `src_2' and write the result
* to `dst'
* It is assumed that `dst' is distinct from both `src_1' and `src_2'. */
static void run_container_xor(const run_container_t *src_1,
const run_container_t *src_2, run_container_t *dst);
/*
* Write out the 16-bit integers contained in this container as a list of 32-bit
* integers using base
* as the starting value (it might be expected that base has zeros in its 16
* least significant bits).
* The function returns the number of values written.
* The caller is responsible for allocating enough memory in out.
*/
static int run_container_to_uint32_array(void *vout, const run_container_t *cont,
uint32_t base);
/*
* Print this container using printf (useful for debugging).
*/
static void run_container_printf(const run_container_t *v);
/*
* Print this container using printf as a comma-separated list of 32-bit
* integers starting at base.
*/
static void run_container_printf_as_uint32_array(const run_container_t *v,
uint32_t base);
/**
* Return the serialized size in bytes of a container having "num_runs" runs.
*/
static inline int32_t run_container_serialized_size_in_bytes(int32_t num_runs) {
return sizeof(uint16_t) +
sizeof(rle16_t) * num_runs; // each run requires 22-byte entries.
}
/**
* Writes the underlying array to buf, outputs how many bytes were written.
* This is meant to be byte-by-byte compatible with the Java and Go versions of
* Roaring.
* The number of bytes written should be run_container_size_in_bytes(container).
*/
static int32_t run_container_write(const run_container_t *container, char *buf);
/**
* Reads the instance from buf, outputs how many bytes were read.
* This is meant to be byte-by-byte compatible with the Java and Go versions of
* Roaring.
* The number of bytes read should be bitset_container_size_in_bytes(container).
* The cardinality parameter is provided for consistency with other containers,
* but
* it might be effectively ignored..
*/
static int32_t run_container_read(int32_t cardinality, run_container_t *container,
const char *buf);
/**
* Return the serialized size in bytes of a container (see run_container_write).
* This is meant to be compatible with the Java and Go versions of Roaring.
*/
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);
}
/**
* Return true if the two containers have the same content.
*/
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));
}
/**
* Return true if container1 is a subset of container2.
*/
static bool run_container_is_subset(const run_container_t *container1,
const run_container_t *container2);
/**
* Used in a start-finish scan that appends segments, for XOR and NOT
*/
/**
* The new container consists of a single run [start,stop).
* It is required that stop>start, the caller is responsability for this check.
* It is required that stop <= (1<<16), the caller is responsability for this
* check. The cardinality of the created container is stop - start. Returns NULL
* on failure
*/
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;
}
/**
* If the element of given rank is in this container, supposing that the first
* element has rank start_rank, then the function returns true and sets element
* accordingly.
* Otherwise, it returns false and update start_rank.
*/
static bool run_container_select(const run_container_t *container,
uint32_t *start_rank, uint32_t rank,
uint32_t *element);
/* Compute the difference of src_1 and src_2 and write the result to
* dst. It is assumed that dst is distinct from both src_1 and src_2. */
/* Returns the smallest value (assumes not empty) */
static inline uint16_t run_container_minimum(const run_container_t *run) {
if (run->n_runs == 0) return 0;
return run->runs[0].value;
}
/* Returns the largest value (assumes not empty) */
static 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;
}
/* Returns the number of values equal or smaller than x */
static int run_container_rank(const run_container_t *arr, uint16_t x);
/* bulk version of run_container_rank(); return number of consumed elements */
static 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);
/* Returns the index of x, if not exsist return -1 */
static int run_container_get_index(const run_container_t *arr, uint16_t x);
/* Returns the index of the first run containing a value at least as large as x,
* or -1 */
static 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; // points to preceding run, possibly -1
if (index != -1) { // possible match
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;
}
/**
* Add all values in range [min, max]. This function is currently unused
* and left as documentation.
*/
/*static inline void run_container_add_range(run_container_t* run,
uint32_t min, uint32_t max) {
int32_t nruns_greater = rle16_count_greater(run->runs, run->n_runs, max);
int32_t nruns_less = rle16_count_less(run->runs, run->n_runs -
nruns_greater, min); run_container_add_range_nruns(run, min, max, nruns_less,
nruns_greater);
}*/
/**
* Shifts last $count elements either left (distance < 0) or right (distance >
* 0)
*/
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;
}
/**
* Remove all elements in range [min, max]
*/
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)) {
// split this run into two adjacent runs
/* Convert an array into a bitset. The input container is not freed or modified.
*/
static bitset_container_t *bitset_container_from_array(const array_container_t *arr);
/* Convert a run into a bitset. The input container is not freed or modified. */
static bitset_container_t *bitset_container_from_run(const run_container_t *arr);
/* Convert a run into an array. The input container is not freed or modified. */
static array_container_t *array_container_from_run(const run_container_t *arr);
/* Convert a bitset into an array. The input container is not freed or modified.
*/
static array_container_t *array_container_from_bitset(const bitset_container_t *bits);
/* Convert an array into a run. The input container is not freed or modified.
*/
static run_container_t *run_container_from_array(const array_container_t *c);
/* convert a run into either an array or a bitset
* might free the container. This does not free the input run container. */
static container_t *convert_to_bitset_or_array_container(run_container_t *rc,
int32_t card,
uint8_t *resulttype);
/* convert containers to and from runcontainers, as is most space efficient.
* The container might be freed. */
static container_t *convert_run_optimize(container_t *c, uint8_t typecode_original,
uint8_t *typecode_after);
/* converts a run container to either an array or a bitset, IF it saves space.
*/
/* If a conversion occurs, the caller is responsible to free the original
* container and
* he becomes reponsible to free the new one. */
static container_t *convert_run_to_efficient_container(run_container_t *c,
uint8_t *typecode_after);
// like convert_run_to_efficient_container but frees the old result if needed
static container_t *convert_run_to_efficient_container_and_free(
run_container_t *c, uint8_t *typecode_after);
/**
* Create new container which is a union of run container and
* range [min, max]. Caller is responsible for freeing run container.
*/
static container_t *container_from_run_range(const run_container_t *run, uint32_t min,
uint32_t max, uint8_t *typecode_after);
/**
* Return true if the two containers have the same content.
*/
static bool array_container_equal_bitset(const array_container_t* container1,
const bitset_container_t* container2);
/**
* Return true if the two containers have the same content.
*/
static bool run_container_equals_array(const run_container_t* container1,
const array_container_t* container2);
/**
* Return true if the two containers have the same content.
*/
static bool run_container_equals_bitset(const run_container_t* container1,
const bitset_container_t* container2);
/**
* Return true if container1 is a subset of container2.
*/
static bool array_container_is_subset_bitset(const array_container_t* container1,
const bitset_container_t* container2);
/**
* Return true if container1 is a subset of container2.
*/
static bool run_container_is_subset_array(const run_container_t* container1,
const array_container_t* container2);
/**
* Return true if container1 is a subset of container2.
*/
static bool array_container_is_subset_run(const array_container_t* container1,
const run_container_t* container2);
/**
* Return true if container1 is a subset of container2.
*/
static bool run_container_is_subset_bitset(const run_container_t* container1,
const bitset_container_t* container2);
/**
* Return true if container1 is a subset of container2.
*/
static bool bitset_container_is_subset_run(const bitset_container_t* container1,
const run_container_t* container2);
/* Compute the andnot of src_1 and src_2 and write the result to
* dst, a valid array container that could be the same as dst.*/
static void array_bitset_container_andnot(const array_container_t *src_1,
const bitset_container_t *src_2,
array_container_t *dst);
/* Compute the andnot of src_1 and src_2 and write the result to
* src_1 */
/* Compute the andnot of src_1 and src_2 and write the result to
* dst, which does not initially have a valid container.
* Return true for a bitset result; false for array
*/
/* Compute the andnot of src_1 and src_2 and write the result to
* dst (which has no container initially). It will modify src_1
* to be dst if the result is a bitset. Otherwise, it will
* free src_1 and dst will be a new array container. In both
* cases, the caller is responsible for deallocating dst.
* Returns true iff dst is a bitset */
/* Compute the andnot of src_1 and src_2 and write the result to
* dst. Result may be either a bitset or an array container
* (returns "result is bitset"). dst does not initially have
* any container, but becomes either a bitset container (return
* result true) or an array container.
*/
/* Compute the andnot of src_1 and src_2 and write the result to
* dst. Result may be either a bitset or an array container
* (returns "result is bitset"). dst does not initially have
* any container, but becomes either a bitset container (return
* result true) or an array container.
*/
/* Compute the andnot of src_1 and src_2 and write the result to
* dst. Result may be either a bitset or an array container
* (returns "result is bitset"). dst does not initially have
* any container, but becomes either a bitset container (return
* result true) or an array container.
*/
/* Compute the andnot of src_1 and src_2 and write the result to
* dst (which has no container initially). It will modify src_1
* to be dst if the result is a bitset. Otherwise, it will
* free src_1 and dst will be a new array container. In both
* cases, the caller is responsible for deallocating dst.
* Returns true iff dst is a bitset */
/* dst does not indicate a valid container initially. Eventually it
* can become any type of container.
*/
static int run_array_container_andnot(const run_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
/* Compute the andnot of src_1 and src_2 and write the result to
* dst (which has no container initially). It will modify src_1
* to be dst if the result is a bitset. Otherwise, it will
* free src_1 and dst will be a new array container. In both
* cases, the caller is responsible for deallocating dst.
* Returns true iff dst is a bitset */
static int run_array_container_iandnot(run_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
/* dst must be a valid array container, allowed to be src_1 */
/* dst does not indicate a valid container initially. Eventually it
* can become any kind of container.
*/
static int run_run_container_andnot(const run_container_t *src_1,
const run_container_t *src_2, container_t **dst);
/* Compute the andnot of src_1 and src_2 and write the result to
* dst (which has no container initially). It will modify src_1
* to be dst if the result is a bitset. Otherwise, it will
* free src_1 and dst will be a new array container. In both
* cases, the caller is responsible for deallocating dst.
* Returns true iff dst is a bitset */
static int run_run_container_iandnot(run_container_t *src_1,
const run_container_t *src_2, container_t **dst);
/*
* dst is a valid array container and may be the same as src_1
*/
/* inplace array-array andnot will always be able to reuse the space of
* src_1 */
static void array_array_container_iandnot(array_container_t *src_1,
const array_container_t *src_2);
/* Compute the andnot of src_1 and src_2 and write the result to
* dst (which has no container initially). Return value is
* "dst is a bitset"
*/
/* Compute the andnot of src_1 and src_2 and write the result to
* dst (which has no container initially). It will modify src_1
* to be dst if the result is a bitset. Otherwise, it will
* free src_1 and dst will be a new array container. In both
* cases, the caller is responsible for deallocating dst.
* Returns true iff dst is a bitset */
/* These functions appear to exclude cases where the
* inputs have the same type and the output is guaranteed
* to have the same type as the inputs. Eg, array intersection
*/
/* Compute the intersection of src_1 and src_2 and write the result to
* dst. It is allowed for dst to be equal to src_1. We assume that dst is a
* valid container. */
static void array_bitset_container_intersection(const array_container_t *src_1,
const bitset_container_t *src_2,
array_container_t *dst);
/* Compute the size of the intersection of src_1 and src_2. */
static int array_bitset_container_intersection_cardinality(
const array_container_t *src_1, const bitset_container_t *src_2);
/*
* Compute the intersection between src_1 and src_2 and write the result
* to *dst. If the return function is true, the result is a bitset_container_t
* otherwise is a array_container_t. We assume that dst is not pre-allocated. In
* case of failure, *dst will be NULL.
*/
static bool bitset_bitset_container_intersection(const bitset_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
/* Compute the intersection between src_1 and src_2 and write the result to
* dst. It is allowed for dst to be equal to src_1. We assume that dst is a
* valid container. */
static void array_run_container_intersection(const array_container_t *src_1,
const run_container_t *src_2,
array_container_t *dst);
/* Compute the intersection between src_1 and src_2 and write the result to
* *dst. If the result is true then the result is a bitset_container_t
* otherwise is a array_container_t.
* If *dst == src_2, then an in-place intersection is attempted
**/
static bool run_bitset_container_intersection(const run_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
/* Compute the size of the intersection between src_1 and src_2 . */
static int array_run_container_intersection_cardinality(const array_container_t *src_1,
const run_container_t *src_2);
/* Compute the size of the intersection between src_1 and src_2
**/
static int run_bitset_container_intersection_cardinality(
const run_container_t *src_1, const bitset_container_t *src_2);
/* Check that src_1 and src_2 intersect. */
static bool array_run_container_intersect(const array_container_t *src_1,
const run_container_t *src_2);
/* Check that src_1 and src_2 intersect.
**/
static bool run_bitset_container_intersect(const run_container_t *src_1,
const bitset_container_t *src_2);
/*
* Same as bitset_bitset_container_intersection except that if the output is to
* be a
* bitset_container_t, then src_1 is modified and no allocation is made.
* If the output is to be an array_container_t, then caller is responsible
* to free the container.
* In all cases, the result is in *dst.
*/
static bool bitset_bitset_container_intersection_inplace(
bitset_container_t *src_1, const bitset_container_t *src_2,
container_t **dst);
/* Negation across the entire range of the container.
* Compute the negation of src and write the result
* to *dst. The complement of a
* sufficiently sparse set will always be dense and a hence a bitmap
* We assume that dst is pre-allocated and a valid bitset container
* There can be no in-place version.
*/
static void array_container_negation(const array_container_t *src,
bitset_container_t *dst);
/* Negation across the entire range of the container
* Compute the negation of src and write the result
* to *dst. A true return value indicates a bitset result,
* otherwise the result is an array container.
* We assume that dst is not pre-allocated. In
* case of failure, *dst will be NULL.
*/
static bool bitset_container_negation(const bitset_container_t *src,
container_t **dst);
/* inplace version */
/*
* Same as bitset_container_negation except that if the output is to
* be a
* bitset_container_t, then src is modified and no allocation is made.
* If the output is to be an array_container_t, then caller is responsible
* to free the container.
* In all cases, the result is in *dst.
*/
static bool bitset_container_negation_inplace(bitset_container_t *src,
container_t **dst);
/* Negation across the entire range of container
* Compute the negation of src and write the result
* to *dst.
* Return values are the *_TYPECODES as defined * in containers.h
* We assume that dst is not pre-allocated. In
* case of failure, *dst will be NULL.
*/
static int run_container_negation(const run_container_t *src, container_t **dst);
/*
* Same as run_container_negation except that if the output is to
* be a
* run_container_t, and has the capacity to hold the result,
* then src is modified and no allocation is made.
* In all cases, the result is in *dst.
*/
static int run_container_negation_inplace(run_container_t *src, container_t **dst);
/* Negation across a range of the container.
* Compute the negation of src and write the result
* to *dst. Returns true if the result is a bitset container
* and false for an array container. *dst is not preallocated.
*/
static bool array_container_negation_range(const array_container_t *src,
const int range_start, const int range_end,
container_t **dst);
/* Even when the result would fit, it is unclear how to make an
* inplace version without inefficient copying. Thus this routine
* may be a wrapper for the non-in-place version
*/
static bool array_container_negation_range_inplace(array_container_t *src,
const int range_start,
const int range_end,
container_t **dst);
/* Negation across a range of the container
* Compute the negation of src and write the result
* to *dst. A true return value indicates a bitset result,
* otherwise the result is an array container.
* We assume that dst is not pre-allocated. In
* case of failure, *dst will be NULL.
*/
static bool bitset_container_negation_range(const bitset_container_t *src,
const int range_start, const int range_end,
container_t **dst);
/* inplace version */
/*
* Same as bitset_container_negation except that if the output is to
* be a
* bitset_container_t, then src is modified and no allocation is made.
* If the output is to be an array_container_t, then caller is responsible
* to free the container.
* In all cases, the result is in *dst.
*/
static bool bitset_container_negation_range_inplace(bitset_container_t *src,
const int range_start,
const int range_end,
container_t **dst);
/* Negation across a range of container
* Compute the negation of src and write the result
* to *dst. Return values are the *_TYPECODES as defined * in containers.h
* We assume that dst is not pre-allocated. In
* case of failure, *dst will be NULL.
*/
static int run_container_negation_range(const run_container_t *src,
const int range_start, const int range_end,
container_t **dst);
/*
* Same as run_container_negation except that if the output is to
* be a
* run_container_t, and has the capacity to hold the result,
* then src is modified and no allocation is made.
* In all cases, the result is in *dst.
*/
static int run_container_negation_range_inplace(run_container_t *src,
const int range_start,
const int range_end,
container_t **dst);
/* These functions appear to exclude cases where the
* inputs have the same type and the output is guaranteed
* to have the same type as the inputs. Eg, bitset unions
*/
/* Compute the union of src_1 and src_2 and write the result to
* dst. It is allowed for src_2 to be dst. */
static void array_bitset_container_union(const array_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Compute the union of src_1 and src_2 and write the result to
* dst. It is allowed for src_2 to be dst. This version does not
* update the cardinality of dst (it is set to BITSET_UNKNOWN_CARDINALITY). */
static void array_bitset_container_lazy_union(const array_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/*
* Compute the union between src_1 and src_2 and write the result
* to *dst. If the return function is true, the result is a bitset_container_t
* otherwise is a array_container_t. We assume that dst is not pre-allocated. In
* case of failure, *dst will be NULL.
*/
static bool array_array_container_union(const array_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
/*
* Compute the union between src_1 and src_2 and write the result
* to *dst if it cannot be written to src_1. If the return function is true,
* the result is a bitset_container_t
* otherwise is a array_container_t. When the result is an array_container_t, it
* it either written to src_1 (if *dst is null) or to *dst.
* If the result is a bitset_container_t and *dst is null, then there was a
* failure.
*/
static bool array_array_container_inplace_union(array_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
/*
* Same as array_array_container_union except that it will more eagerly produce
* a bitset.
*/
static bool array_array_container_lazy_union(const array_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
/*
* Same as array_array_container_inplace_union except that it will more eagerly
* produce a bitset.
*/
static bool array_array_container_lazy_inplace_union(array_container_t *src_1,
const array_container_t *src_2,
container_t **dst);
/* Compute the union of src_1 and src_2 and write the result to
* dst. We assume that dst is a
* valid container. The result might need to be further converted to array or
* bitset container,
* the caller is responsible for the eventual conversion. */
static void array_run_container_union(const array_container_t *src_1,
const run_container_t *src_2,
run_container_t *dst);
/* Compute the union of src_1 and src_2 and write the result to
* src2. The result might need to be further converted to array or
* bitset container,
* the caller is responsible for the eventual conversion. */
static void array_run_container_inplace_union(const array_container_t *src_1,
run_container_t *src_2);
/* Compute the union of src_1 and src_2 and write the result to
* dst. It is allowed for dst to be src_2.
* If run_container_is_full(src_1) is true, you must not be calling this
*function.
**/
static void run_bitset_container_union(const run_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Compute the union of src_1 and src_2 and write the result to
* dst. It is allowed for dst to be src_2. This version does not
* update the cardinality of dst (it is set to BITSET_UNKNOWN_CARDINALITY).
* If run_container_is_full(src_1) is true, you must not be calling this
* function.
* */
static void run_bitset_container_lazy_union(const run_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* These functions appear to exclude cases where the
* inputs have the same type and the output is guaranteed
* to have the same type as the inputs. Eg, bitset unions
*/
/*
* Java implementation (as of May 2016) for array_run, run_run
* and bitset_run don't do anything different for inplace.
* (They are not truly in place.)
*/
/* Compute the xor of src_1 and src_2 and write the result to
* dst (which has no container initially).
* Result is true iff dst is a bitset */
static bool array_bitset_container_xor(const array_container_t *src_1,
const bitset_container_t *src_2,
container_t **dst);
/* Compute the xor of src_1 and src_2 and write the result to
* dst. It is allowed for src_2 to be dst. This version does not
* update the cardinality of dst (it is set to BITSET_UNKNOWN_CARDINALITY).
*/
static void array_bitset_container_lazy_xor(const array_container_t *src_1,
const bitset_container_t *src_2,
bitset_container_t *dst);
/* Compute the xor of src_1 and src_2 and write the result to
* dst (which has no container initially). Return value is
* "dst is a bitset"
*/
/* Compute the xor of src_1 and src_2 and write the result to
* dst. Result may be either a bitset or an array container
* (returns "result is bitset"). dst does not initially have
* any container, but becomes either a bitset container (return
* result true) or an array container.
*/
/* lazy xor. Dst is initialized and may be equal to src_2.
* Result is left as a bitset container, even if actual
* cardinality would dictate an array container.
*/
/* dst does not initially have a valid container. Creates either
* an array or a bitset container, indicated by return code.
* A bitset container will not have a valid cardinality and the
* container type might not be correct for the actual cardinality
*/
/* dst does not indicate a valid container initially. Eventually it
* can become any kind of container.
*/
static int run_run_container_xor(const run_container_t *src_1,
const run_container_t *src_2, container_t **dst);
/* INPLACE versions (initial implementation may not exploit all inplace
* opportunities (if any...)
*/
/* Compute the xor of src_1 and src_2 and write the result to
* dst (which has no container initially). It will modify src_1
* to be dst if the result is a bitset. Otherwise, it will
* free src_1 and dst will be a new array container. In both
* cases, the caller is responsible for deallocating dst.
* Returns true iff dst is a bitset */
/* Compute the xor of src_1 and src_2 and write the result to
* dst. Result may be either a bitset or an array container
* (returns "result is bitset"). dst does not initially have
* any container, but becomes either a bitset container (return
* result true) or an array container.
*/
/**
* The switch case statements follow
* BITSET_CONTAINER_TYPE -- ARRAY_CONTAINER_TYPE -- RUN_CONTAINER_TYPE
* so it makes more sense to number them 1, 2, 3 (in the vague hope that the
* compiler might exploit this ordering).
*/
/**
* Macros for pairing container type codes, suitable for switch statements.
* Use PAIR_CONTAINER_TYPES() for the switch, CONTAINER_PAIR() for the cases:
*
* switch (PAIR_CONTAINER_TYPES(type1, type2)) {
* case CONTAINER_PAIR(BITSET,ARRAY):
* ...
* }
*/
#define PAIR_CONTAINER_TYPES(type1, type2) (4 * (type1) + (type2))
/**
* A shared container is a wrapper around a container
* with reference counting.
*/
STRUCT_CONTAINER(shared_container_s) {
container_t *container;
uint8_t typecode;
croaring_refcount_t counter; // to be managed atomically
};
#define CAST_shared(c) CAST(shared_container_t *, c) // safer downcast
#define const_CAST_shared(c) CAST(const shared_container_t *, c)
#define movable_CAST_shared(c) movable_CAST(shared_container_t **, c)
/*
* With copy_on_write = true
* Create a new shared container if the typecode is not SHARED_CONTAINER_TYPE,
* otherwise, increase the count
* If copy_on_write = false, then clone.
* Return NULL in case of failure.
**/
container_t *get_copy_of_container(container_t *container, uint8_t *typecode,
bool copy_on_write);
/* Frees a shared container (actually decrement its counter and only frees when
* the counter falls to zero). */
static void shared_container_free(shared_container_t *container);
/* extract a copy from the shared container, freeing the shared container if
there is just one instance left,
clone instances when the counter is higher than one
*/
container_t *shared_container_extract_copy(shared_container_t *container,
uint8_t *typecode);
/* access to container underneath */
static inline container_t *container_mutable_unwrap_shared(container_t *c,
uint8_t *type) {
if (*type == SHARED_CONTAINER_TYPE) { // the passed in container is shared
*type = CAST_shared(c)->typecode;
assert(*type != SHARED_CONTAINER_TYPE);
return CAST_shared(c)->container; // return the enclosed container
} else {
return c; // wasn't shared, so return as-is
}
}
/* access to container underneath and queries its type */
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;
}
}
/**
* Copies a container, requires a typecode. This allocates new memory, caller
* is responsible for deallocation. If the container is not shared, then it is
* physically cloned. Sharable containers are not cloneable.
*/
container_t *container_clone(const container_t *container, uint8_t typecode);
/* access to container underneath, cloning it if needed */
static inline container_t *get_writable_copy_if_shared(container_t *c,
uint8_t *type) {
if (*type == SHARED_CONTAINER_TYPE) { // shared, return enclosed container
return shared_container_extract_copy(CAST_shared(c), type);
} else {
return c; // not shared, so return as-is
}
}
// no matter what the initial container was, convert it to a bitset
// if a new container is produced, caller responsible for freeing the previous
// one
// container should not be a shared container
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); // nothing to do
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; // unreached
}
/**
* Get the container name from the typecode
* (unused at time of writing)
*/
/*static inline const char *get_container_name(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:
return container_names[3];
default:
assert(false);
roaring_unreachable;
return "unknown";
}
}*/
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;
}
/**
* Get the container cardinality (number of elements), requires a typecode
*/
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; // unreached
}
// returns true if a container is known to be full. Note that a lazy bitset
// container
// might be full without us knowing
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; // unreached
}
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; // no shrinking possible
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; // unreached
}
/**
* make a container with a run of ones
*/
/* initially always use a run container, even if an array might be
* marginally
* smaller */
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);
}
}
/* Create a container with all the values between in [min,max) at a
distance k*step from min. */
static inline container_t *container_from_range(uint8_t *type, uint32_t min,
uint32_t max, uint16_t step) {
if (step == 0) return NULL; // being paranoid
if (step == 1) {
return container_range_of_ones(min, max, type);
// Note: the result is not always a run (need to check the cardinality)
//*type = RUN_CONTAINER_TYPE;
// return run_container_create_range(min, max);
}
int size = (max - min + step - 1) / step;
if (size <= DEFAULT_MAX_SIZE) { // array container
*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 { // bitset container
*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;
}
}
/**
* "repair" the container after lazy operations.
*/
static inline container_t *container_repair_after_lazy(container_t *c,
uint8_t *type) {
c = get_writable_copy_if_shared(c, type); // !!! unnecessary cloning
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; // nothing to do
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; // unreached
}
/**
* Writes the underlying array to buf, outputs how many bytes were written.
* This is meant to be byte-by-byte compatible with the Java and Go versions of
* Roaring.
* The number of bytes written should be
* container_write(container, buf).
*
*/ staticinline 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; return0; // unreached
}
/** *Getthecontainersizeinbytesunderportableserialization(see *container_write),requiresa *typecode
*/ staticinline 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; return0; // unreached
}
caseCONTAINER_PAIR(ARRAY,):
java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 2
const_CAST_array(c1), const_CAST_array(c2));
case CONTAINER_PAIRRUNRUN) return(const_CAST_run()java.lang.StringIndexOutOfBoundsException: Index 77 out of bounds for length 77
const_CAST_runc2);
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));
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)); // as of January 2016, Java code used non-in-place intersection for // two runcontainers return convert_run_to_efficient_container_and_free(CAST_run(result),
result_type);
case CONTAINER_PAIR(BITSET, ARRAY): // c1 is a bitmap so no inplace possible
result = array_container_create();
array_bitset_container_intersection(const_CAST_array(c2),
const_CAST_bitset(c1),
CAST_array(result));
*result_type = ARRAY_CONTAINER_TYPE; // never bitset return result;
case CONTAINER_PAIR(ARRAY, BITSET):
*result_type = ARRAY_CONTAINER_TYPE; // never bitset
array_bitset_container_intersection(
const_CAST_array(c1), const_CAST_bitset(c2),
CAST_array(c1)); // result is allowed to be same as c1 return c1;
case CONTAINER_PAIR(BITSET, RUN): // will attempt in-place computation
*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, RUN):
result = run_container_create();
run_container_union(const_CAST_run(c1), const_CAST_run(c2),
CAST_run(result));
*result_type = RUN_CONTAINER_TYPE; // todo: could be optimized since will never convert to array
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;
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; // we are being lazy
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)); // is lazy
*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)); // is lazy
*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)); // is lazy
*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)); // is lazy
*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; // next line skipped since we are lazy // result = convert_run_to_efficient_container(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)); // TODO make lazy
*result_type = RUN_CONTAINER_TYPE; // next line skipped since we are lazy // result = convert_run_to_efficient_container(result, result_type); return result;
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; // the computation was done in-place!
} 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; // never array return c1;
case CONTAINER_PAIR(ARRAY, BITSET): // c1 is an array, so no in-place possible
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)); // allowed
*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;
/** *Computetheunionbetweentwocontainers,withresultinthefirstcontainer. *Ifthereturnedpointerisidenticaltoc1,thenthecontainerhasbeen *modified. *Ifthereturnedpointerisdifferentfromc1,thenanewcontainerhasbeen *createdandthecallerisresponsibleforfreeingit. *Thetypeofthefirstcontainermaychange.Returnsthemodified *(andpossiblynew)container * *Thislazyversiondelayssomeoperationssuchasthemaintenanceofthe *cardinality.Itrequiresrepairlateronthegeneratedcontainers.
*/ staticinline 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); // 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): #ifdef LAZY_OR_BITSET_CONVERSION_TO_FULL // if we have two bitsets, we might as well compute the cardinality
bitset_container_or(const_CAST_bitset(c1), const_CAST_bitset(c2),
CAST_bitset(c1)); // it is possible that two bitsets can lead to a full container if (CAST_bitset(c1)->cardinality == (1 << 16)) { // we convert
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));
case CONTAINER_PAIR(BITSET, ARRAY):
array_bitset_container_lazy_union(const_CAST_array(c2),
const_CAST_bitset(c1),
CAST_bitset(c1)); // is lazy
*result_type = BITSET_CONTAINER_TYPE; // never array return c1;
case CONTAINER_PAIR(ARRAY, BITSET): // c1 is an array, so no in-place possible
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)); // is lazy 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)); // allowed // lazy
*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)); // lazy
*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; // next line skipped since we are lazy // result = convert_run_to_efficient_container_and_free(result, // result_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; // next line skipped since we are lazy // result = convert_run_to_efficient_container_and_free(result, // result_type); return c1;
case CONTAINER_PAIR(RUN, RUN): // nothing special done yet.
*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; // next line skipped since we are lazy // result = convert_run_to_efficient_container(result, result_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; // next line skipped since we are lazy // result = convert_run_to_efficient_container(result, result_type); return result;
// TODO: other cases being lazy, esp. when we know inplace not likely // could see the corresponding code for union default: // we may have a dirty bitset (without a precomputed cardinality) // and calling container_ixor on it might be unsafe. 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);
}
}
staticinline container_t *container_inot(container_t *c, uint8_t type copyright notice andthis permission notice appear in all copies.
uint8_t*result_type)java.lang.StringIndexOutOfBoundsException: Index 65 out of bounds for length 65
c = get_writable_copy_if_shared(c, &type);
container_t *result = NULL;
*java.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
bitset_container_negation_inplace(CAST_bitset(c), &result)
? BITSET_CONTAINER_TYPE #debug.
result; case: // will never be inplace
(;
*java.lang.StringIndexOutOfBoundsException: Index 19 out of bounds for length 17 ':
java.lang.StringIndexOutOfBoundsException: Index 21 out of bounds for length 21
result case
result_type=
(CAST_run) r) return;
/** appends from sa to ra, ending with the greatest key that is *islessorequalstopping_key
*/ staticvoid ra_append_copies_until(roaring_array_t *ra, const roaring_array_t *sa,
uint16_t stopping_key, bool copy_on_write);
/** appends from sa to ra, starting with the smallest key that is *isstrictlygreaterthanbefore_start
*/
// used in inplace andNot only, to slide left the containers from // the mutated RoaringBitmap that are after the largest container of // the argument RoaringBitmap. It is followed by a call to resize. // staticvoid ra_copy_range(roaring_array_t *ra, uint32_t begin, uint32_t end,
uint32_t new_begin);
// Internal node reference type. Contains the node typecode in the low 8 bits, // and the index in the relevant node array in the high 48 bits. Has a value of // CROARING_ART_NULL_REF when pointing to a non-existent node. typedef uint64_t art_ref_t;
// Indexed by node typecode, thus 1 larger than they need to be for // convenience. `first_free` indicates the index where the first free node // lives, which may be equal to the capacity.
uint64_t first_free[6];
uint64_t capacities[6];
art_node_t *nodes[6];
} art_t;
// State for each node in the ART the iterator has travelled from the root. // This is `ART_KEY_BYTES + 1` because it includes state for the leaf too. art_iterator_frame_tframes[ART_KEY_BYTES+1]; }art_iterator_t;
CROARING_TARGET_AVX2 ///////// // Warning: // This function may not be safe if A == C or B == C. ///////// static 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) { // we handle the degenerate case if (s_a == 0) return0; if (s_b == 0) { if (A != C) memcpy(C, A, sizeof(uint16_t) * s_a); return (int32_t)s_a;
} // handle the leading zeroes, it is messy but it allows us to use the fast // _mm_cmpistrm instrinsic safely
int32_t count = 0; if ((A[0] == 0) || (B[0] == 0)) { if ((A[0] == 0) && (B[0] == 0)) {
A++;
s_a--;
B++;
s_b--;
} elseif (A[0] == 0) {
C[count++] = 0;
A++;
s_a--;
} else {
B++;
s_b--;
}
}
// at this point, we have two non-empty arrays, made of non-zero
// increasing values.
size_t i_a = 0, i_b = 0;
const size_t vectorlength = sizeof(__m128i) / sizeof(uint16_t);
const size_t st_a = (s_a / vectorlength) * vectorlength;
const size_t st_b = (s_b / vectorlength) * vectorlength;
if ((i_a < st_a) && (i_b < st_b)) { // this is the vectorized code path
__m128i v_a, v_b; //, v_bmax;
// we load a vector from A and a vector from B
v_a = _mm_lddqu_si128((__m128i *)&A[i_a]);
v_b = _mm_lddqu_si128((__m128i *)&B[i_b]);
// we have a runningmask which indicates which values from A have been
// spotted in B, these don't get written out.
__m128i runningmask_a_found_in_b = _mm_setzero_si128();
/****
* start of the main vectorized loop
*****/
while (true) {
// afoundinb will contain a mask indicate for each entry in A
// whether it is seen
// in B
const __m128i a_found_in_b = _mm_cmpistrm(
v_b, v_a,
_SIDD_UWORD_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK);
runningmask_a_found_in_b =
_mm_or_si128(runningmask_a_found_in_b, a_found_in_b);
// we always compare the last values of A and B
const uint16_t a_max = A[i_a + vectorlength - 1];
const uint16_t b_max = B[i_b + vectorlength - 1];
if (a_max <= b_max) {
// Ok. In this code path, we are ready to write our v_a
// because there is no need to read more from B, they will
// all be large values.
const int bitmask_belongs_to_difference =
_mm_extract_epi32(runningmask_a_found_in_b, 0) ^ 0xFF;
/*** next few lines are probably expensive *****/
__m128i sm16 = _mm_loadu_si128((const __m128i *)shuffle_mask16 +
bitmask_belongs_to_difference);
__m128i p = _mm_shuffle_epi8(v_a, sm16);
_mm_storeu_si128((__m128i *)&C[count], p); // can overflow
count += _mm_popcnt_u32(bitmask_belongs_to_difference);
// we advance a
i_a += vectorlength;
if (i_a == st_a) // no more
break;
runningmask_a_found_in_b = _mm_setzero_si128();
v_a = _mm_lddqu_si128((__m128i *)&A[i_a]);
}
if (b_max <= a_max) {
// in this code path, the current v_b has become useless
i_b += vectorlength;
if (i_b == st_b) break;
v_b = _mm_lddqu_si128((__m128i *)&B[i_b]);
}
}
// at this point, either we have i_a == st_a, which is the end of the
// vectorized processing,
// or we have i_b == st_b, and we are not done processing the vector...
// so we need to finish it off.
if (i_a < st_a) { // we have unfinished business...
uint16_t buffer[8]; // buffer to do a masked load
memset(buffer, 0, 8 * sizeof(uint16_t));
memcpy(buffer, B + i_b, (s_b - i_b) * sizeof(uint16_t));
v_b = _mm_lddqu_si128((__m128i *)buffer);
const __m128i a_found_in_b = _mm_cmpistrm(
v_b, v_a,
_SIDD_UWORD_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK);
runningmask_a_found_in_b =
_mm_or_si128(runningmask_a_found_in_b, a_found_in_b);
const int bitmask_belongs_to_difference =
_mm_extract_epi32(runningmask_a_found_in_b, 0) ^ 0xFF;
__m128i sm16 = _mm_loadu_si128((const __m128i *)shuffle_mask16 +
bitmask_belongs_to_difference);
__m128i p = _mm_shuffle_epi8(v_a, sm16);
_mm_storeu_si128((__m128i *)&C[count], p); // can overflow
count += _mm_popcnt_u32(bitmask_belongs_to_difference);
i_a += vectorlength;
}
// at this point we should have i_a == st_a and i_b == st_b
}
// do the tail using scalar code
while (i_a < s_a && i_b < s_b) {
uint16_t a = A[i_a];
uint16_t b = B[i_b];
if (b < a) {
i_b++;
} else if (a < b) {
C[count] = a;
count++;
i_a++;
} else { //==
i_a++;
i_b++;
}
}
if (i_a < s_a) {
if (C == A) {
assert((size_t)count <= i_a);
if ((size_t)count < i_a) {
memmove(C + count, A + i_a, sizeof(uint16_t) * (s_a - i_a));
}
} else {
for (size_t i = 0; i < (s_a - i_a); i++) {
C[count + i] = A[i + i_a];
}
}
count += (int32_t)(s_a - i_a);
}
return count;
}
CROARING_UNTARGET_AVX2
#endif // CROARING_IS_X64
/**
* Branchless binary search going after 4 values at once.
* Assumes that array is sorted.
* You have that array[*index1] >= target1, array[*index12] >= target2, ...
* except when *index1 = n, in which case you know that all values in array are
* smaller than target1, and so forth.
* It has logarithmic complexity.
*/
static void binarySearch4(const uint16_t *array, int32_t n, uint16_t target1,
uint16_t target2, uint16_t target3, uint16_t target4,
int32_t *index1, int32_t *index2, int32_t *index3,
int32_t *index4) {
const uint16_t *base1 = array;
const uint16_t *base2 = array;
const uint16_t *base3 = array;
const uint16_t *base4 = array;
if (n == 0) return;
while (n > 1) {
int32_t half = n >> 1;
base1 = (base1[half] < target1) ? &base1[half] : base1;
base2 = (base2[half] < target2) ? &base2[half] : base2;
base3 = (base3[half] < target3) ? &base3[half] : base3;
base4 = (base4[half] < target4) ? &base4[half] : base4;
n -= half;
}
*index1 = (int32_t)((*base1 < target1) + base1 - array);
*index2 = (int32_t)((*base2 < target2) + base2 - array);
*index3 = (int32_t)((*base3 < target3) + base3 - array);
*index4 = (int32_t)((*base4 < target4) + base4 - array);
}
/**
* Branchless binary search going after 2 values at once.
* Assumes that array is sorted.
* You have that array[*index1] >= target1, array[*index12] >= target2.
* except when *index1 = n, in which case you know that all values in array are
* smaller than target1, and so forth.
* It has logarithmic complexity.
*/
static void binarySearch2(const uint16_t *array, int32_t n, uint16_t target1,
uint16_t target2, int32_t *index1, int32_t *index2) {
const uint16_t *base1 = array;
const uint16_t *base2 = array;
if (n == 0) return;
while (n > 1) {
int32_t half = n >> 1;
base1 = (base1[half] < target1) ? &base1[half] : base1;
base2 = (base2[half] < target2) ? &base2[half] : base2;
n -= half;
}
*index1 = (int32_t)((*base1 < target1) + base1 - array);
*index2 = (int32_t)((*base2 < target2) + base2 - array);
}
/* Computes the intersection between one small and one large set of uint16_t.
* Stores the result into buffer and return the number of elements.
* Processes the small set in blocks of 4 values calling binarySearch4
* and binarySearch2. This approach can be slightly superior to a conventional
* galloping search in some instances.
*/
static int32_t intersect_skewed_uint16(const uint16_t *small, size_t size_s,
const uint16_t *large, size_t size_l,
uint16_t *buffer) {
size_t pos = 0, idx_l = 0, idx_s = 0;
// working in-place, this function overwrites the repeated values
// could be avoided?
static inline uint32_t unique(uint16_t *out, uint32_t len) {
uint32_t pos = 1;
for (uint32_t i = 1; i < len; ++i) {
if (out[i] != out[i - 1]) {
out[pos++] = out[i];
}
}
return pos;
}
// use with qsort, could be avoided
static int uint16_compare(const void *a, const void *b) {
return (*(uint16_t *)a - *(uint16_t *)b);
}
CROARING_TARGET_AVX2
// a one-pass SSE union algorithm
// This function may not be safe if array1 == output or array2 == output.
static uint32_t union_vector16(const uint16_t *__restrict__ array1, uint32_t length1,
const uint16_t *__restrict__ array2, uint32_t length2,
uint16_t *__restrict__ output) {
if ((length1 < 8) || (length2 < 8)) {
return (uint32_t)union_uint16(array1, length1, array2, length2, output);
}
__m128i vA, vB, V, vecMin, vecMax;
__m128i laststore;
uint16_t *initoutput = output;
uint32_t len1 = length1 / 8;
uint32_t len2 = length2 / 8;
uint32_t pos1 = 0;
uint32_t pos2 = 0;
// we start the machine
vA = _mm_lddqu_si128((const __m128i *)array1 + pos1);
pos1++;
vB = _mm_lddqu_si128((const __m128i *)array2 + pos2);
pos2++;
sse_merge(&vA, &vB, &vecMin, &vecMax);
laststore = _mm_set1_epi16(-1);
output += store_unique(laststore, vecMin, output);
laststore = vecMin;
if ((pos1 < len1) && (pos2 < len2)) {
uint16_t curA, curB;
curA = array1[8 * pos1];
curB = array2[8 * pos2];
while (true) {
if (curA <= curB) {
V = _mm_lddqu_si128((const __m128i *)array1 + pos1);
pos1++;
if (pos1 < len1) {
curA = array1[8 * pos1];
} else {
break;
}
} else {
V = _mm_lddqu_si128((const __m128i *)array2 + pos2);
pos2++;
if (pos2 < len2) {
curB = array2[8 * pos2];
} else {
break;
}
}
sse_merge(&V, &vecMax, &vecMin, &vecMax);
output += store_unique(laststore, vecMin, output);
laststore = vecMin;
}
sse_merge(&V, &vecMax, &vecMin, &vecMax);
output += store_unique(laststore, vecMin, output);
laststore = vecMin;
}
// we finish the rest off using a scalar algorithm
// could be improved?
//
// copy the small end on a tmp buffer
uint32_t len = (uint32_t)(output - initoutput);
uint16_t buffer[16];
uint32_t leftoversize = store_unique(laststore, vecMax, buffer);
if (pos1 == len1) {
memcpy(buffer + leftoversize, array1 + 8 * pos1,
(length1 - 8 * len1) * sizeof(uint16_t));
leftoversize += length1 - 8 * len1;
qsort(buffer, leftoversize, sizeof(uint16_t), uint16_compare);
CROARING_TARGET_AVX2
// write vector new, while omitting repeated values assuming that previously
// written vector was "old"
static inline int store_unique_xor(__m128i old, __m128i newval,
uint16_t *output) {
__m128i vecTmp1 = _mm_alignr_epi8(newval, old, 16 - 4);
__m128i vecTmp2 = _mm_alignr_epi8(newval, old, 16 - 2);
__m128i equalleft = _mm_cmpeq_epi16(vecTmp2, vecTmp1);
__m128i equalright = _mm_cmpeq_epi16(vecTmp2, newval);
__m128i equalleftoright = _mm_or_si128(equalleft, equalright);
int M = _mm_movemask_epi8(
_mm_packs_epi16(equalleftoright, _mm_setzero_si128()));
int numberofnewvalues = 8 - _mm_popcnt_u32(M);
__m128i key = _mm_lddqu_si128((const __m128i *)uniqshuf + M);
__m128i val = _mm_shuffle_epi8(vecTmp2, key);
_mm_storeu_si128((__m128i *)output, val);
return numberofnewvalues;
}
CROARING_UNTARGET_AVX2
// working in-place, this function overwrites the repeated values
// could be avoided? Warning: assumes len > 0
static inline uint32_t unique_xor(uint16_t *out, uint32_t len) {
uint32_t pos = 1;
for (uint32_t i = 1; i < len; ++i) {
if (out[i] != out[i - 1]) {
out[pos++] = out[i];
} else
pos--; // if it is identical to previous, delete it
}
return pos;
}
CROARING_TARGET_AVX2
// a one-pass SSE xor algorithm
static uint32_t xor_vector16(const uint16_t *__restrict__ array1, uint32_t length1,
const uint16_t *__restrict__ array2, uint32_t length2,
uint16_t *__restrict__ output) {
if ((length1 < 8) || (length2 < 8)) {
return xor_uint16(array1, length1, array2, length2, output);
}
__m128i vA, vB, V, vecMin, vecMax;
__m128i laststore;
uint16_t *initoutput = output;
uint32_t len1 = length1 / 8;
uint32_t len2 = length2 / 8;
uint32_t pos1 = 0;
uint32_t pos2 = 0;
// we start the machine
vA = _mm_lddqu_si128((const __m128i *)array1 + pos1);
pos1++;
vB = _mm_lddqu_si128((const __m128i *)array2 + pos2);
pos2++;
sse_merge(&vA, &vB, &vecMin, &vecMax);
laststore = _mm_set1_epi16(-1);
uint16_t buffer[17];
output += store_unique_xor(laststore, vecMin, output);
laststore = vecMin;
if ((pos1 < len1) && (pos2 < len2)) {
uint16_t curA, curB;
curA = array1[8 * pos1];
curB = array2[8 * pos2];
while (true) {
if (curA <= curB) {
V = _mm_lddqu_si128((const __m128i *)array1 + pos1);
pos1++;
if (pos1 < len1) {
curA = array1[8 * pos1];
} else {
break;
}
} else {
V = _mm_lddqu_si128((const __m128i *)array2 + pos2);
pos2++;
if (pos2 < len2) {
curB = array2[8 * pos2];
} else {
break;
}
}
sse_merge(&V, &vecMax, &vecMin, &vecMax);
// conditionally stores the last value of laststore as well as all
// but the
// last value of vecMin
output += store_unique_xor(laststore, vecMin, output);
laststore = vecMin;
}
sse_merge(&V, &vecMax, &vecMin, &vecMax);
// conditionally stores the last value of laststore as well as all but
// the
// last value of vecMin
output += store_unique_xor(laststore, vecMin, output);
laststore = vecMin;
}
uint32_t len = (uint32_t)(output - initoutput);
// we finish the rest off using a scalar algorithm
// could be improved?
// conditionally stores the last value of laststore as well as all but the
// last value of vecMax,
// we store to "buffer"
int leftoversize = store_unique_xor(laststore, vecMax, buffer);
uint16_t vec7 = (uint16_t)_mm_extract_epi16(vecMax, 7);
uint16_t vec6 = (uint16_t)_mm_extract_epi16(vecMax, 6);
if (vec7 != vec6) buffer[leftoversize++] = vec7;
if (pos1 == len1) {
memcpy(buffer + leftoversize, array1 + 8 * pos1,
(length1 - 8 * len1) * sizeof(uint16_t));
leftoversize += length1 - 8 * len1;
if (leftoversize == 0) { // trivial case
memcpy(output, array2 + 8 * pos2,
(length2 - 8 * pos2) * sizeof(uint16_t));
len += (length2 - 8 * pos2);
} else {
qsort(buffer, leftoversize, sizeof(uint16_t), uint16_compare);
leftoversize = unique_xor(buffer, leftoversize);
len += xor_uint16(buffer, leftoversize, array2 + 8 * pos2,
length2 - 8 * pos2, output);
}
} else {
memcpy(buffer + leftoversize, array2 + 8 * pos2,
(length2 - 8 * len2) * sizeof(uint16_t));
leftoversize += length2 - 8 * len2;
if (leftoversize == 0) { // trivial case
memcpy(output, array1 + 8 * pos1,
(length1 - 8 * pos1) * sizeof(uint16_t));
len += (length1 - 8 * pos1);
} else {
qsort(buffer, leftoversize, sizeof(uint16_t), uint16_compare);
leftoversize = unique_xor(buffer, leftoversize);
len += xor_uint16(buffer, leftoversize, array1 + 8 * pos1,
length1 - 8 * pos1, output);
}
}
return len;
}
CROARING_UNTARGET_AVX2
/**
* End of SIMD 16-bit XOR code
*/
// Node48 placeholder value to indicate no child is present at this key index. #define CROARING_ART_NODE48_EMPTY_VAL 48 #define CROARING_NODE48_AVAILABLE_CHILDREN_MASK ((UINT64_C(1) << 48) - 1)
// Gives the byte difference needed to align the current buffer to the // alignment, relative to the start of the buffer. #define CROARING_ART_ALIGN_SIZE_RELATIVE(buf_cur, buf_start, alignment) \
((((ptrdiff_t)((buf_cur) - (buf_start)) + ((alignment)-1)) & \
(ptrdiff_t)(~((alignment)-1))) - \
(ptrdiff_t)((buf_cur) - (buf_start)))
// Inner node, with prefix. // // We use a fixed-length array as a pointer would be larger than the array. typedefstruct art_inner_node_s {
uint8_t prefix_size;
uint8_t prefix[ART_KEY_BYTES - 1];
} art_inner_node_t;
// Inner node types.
// Node4: key[i] corresponds with children[i]. Keys are sorted. typedefstruct art_node4_s { union { struct {
art_inner_node_t base;
uint8_t count;
uint8_t keys[4];
art_ref_t children[4];
};
uint64_t next_free;
};
} art_node4_t;
// Node16: key[i] corresponds with children[i]. Keys are sorted. typedefstruct art_node16_s { union { struct {
art_inner_node_t base;
uint8_t count;
uint8_t keys[16];
art_ref_t children[16];
};
uint64_t next_free;
};
} art_node16_t;
// Node48: key[i] corresponds with children[key[i]] if key[i] != // CROARING_ART_NODE48_EMPTY_VAL. Keys are naturally sorted due to direct // indexing. typedefstruct art_node48_s { union { struct {
art_inner_node_t base;
uint8_t count; // Bitset where the ith bit is set if children[i] is available // Because there are at most 48 children, only the bottom 48 bits // are used.
uint64_t available_children;
uint8_t keys[256];
art_ref_t children[48];
};
uint64_t next_free;
};
} art_node48_t;
// Node256: children[i] is directly indexed by key chunk. A child is present if // children[i] != NULL. typedefstruct art_node256_s { union { struct {
art_inner_node_t base;
uint16_t count;
art_ref_t children[256];
};
uint64_t next_free;
};
} art_node256_t;
// Size of each node type, indexed by typecode for convenience. staticconst size_t ART_NODE_SIZES[] = { 0, sizeof(art_leaf_t), sizeof(art_node4_t), sizeof(art_node16_t), sizeof(art_node48_t), sizeof(art_node256_t),
};
// Helper struct to refer to a child within a node at a specific index. typedefstruct art_indexed_child_s {
art_ref_t child;
uint8_t index;
art_key_chunk_t key_chunk;
} art_indexed_child_t;
staticbool art_node48_internal_validate(const art_t *art, const art_node48_t *node,
art_internal_validate_t validator) { if (node->count <= 16) { return art_validate_fail(&validator, "Node48 has too few children");
} if (node->count > 48) { return art_validate_fail(&validator, "Node48 has too many children");
}
uint64_t used_children = 0; for (int i = 0; i < 256; ++i) {
uint8_t child_idx = node->keys[i]; if (child_idx != CROARING_ART_NODE48_EMPTY_VAL) { if (used_children & (UINT64_C(1) << child_idx)) { return art_validate_fail(
&validator, "Node48 keys point to the same child index");
}
art_ref_t child = node->children[child_idx]; if (child == CROARING_ART_NULL_REF) { return art_validate_fail(&validator, "Node48 has a NULL child");
}
used_children |= UINT64_C(1) << child_idx;
}
}
uint64_t expected_used_children =
(node->available_children) ^ CROARING_NODE48_AVAILABLE_CHILDREN_MASK; if (used_children != expected_used_children) { return art_validate_fail(
&validator, "Node48 available_children does not match actual children");
} while (used_children != 0) {
uint8_t child_idx = roaring_trailing_zeroes(used_children);
used_children &= used_children - 1;
staticbool art_node256_internal_validate(const art_t *art, const art_node256_t *node,
art_internal_validate_t validator) { if (node->count <= 48) { return art_validate_fail(&validator, "Node256 has too few children");
} if (node->count > 256) { return art_validate_fail(&validator, "Node256 has too many children");
}
validator.depth++; int actual_count = 0; for (int i = 0; i < 256; ++i) { if (node->children[i] != CROARING_ART_NULL_REF) {
actual_count++;
for (int j = i + 1; j < 256; ++j) { if (node->children[i] == node->children[j]) { return art_validate_fail(&validator, "Node256 has duplicate children");
}
}
validator.current_key[validator.depth - 1] = i; if (!art_internal_validate_at(art, node->children[i], validator)) { returnfalse;
}
}
}
if (actual_count != node->count) {
return art_validate_fail(
&validator, "Node256 count does not match actual children");
}
return true;
}
// Finds the child with the given key chunk in the inner node, returns NULL if
// no such child is found.
static art_ref_t art_find_child(const art_inner_node_t *node,
art_typecode_t typecode,
art_key_chunk_t key_chunk) {
switch (typecode) {
case CROARING_ART_NODE4_TYPE:
return art_node4_find_child((art_node4_t *)node, key_chunk);
case CROARING_ART_NODE16_TYPE:
return art_node16_find_child((art_node16_t *)node, key_chunk);
case CROARING_ART_NODE48_TYPE:
return art_node48_find_child((art_node48_t *)node, key_chunk);
case CROARING_ART_NODE256_TYPE:
return art_node256_find_child((art_node256_t *)node, key_chunk);
default:
assert(false);
return CROARING_ART_NULL_REF;
}
}
// Replaces the child with the given key chunk in the inner node.
static void art_replace(art_inner_node_t *node, art_typecode_t typecode,
art_key_chunk_t key_chunk, art_ref_t new_child) {
switch (typecode) {
case CROARING_ART_NODE4_TYPE:
art_node4_replace((art_node4_t *)node, key_chunk, new_child);
break;
case CROARING_ART_NODE16_TYPE:
art_node16_replace((art_node16_t *)node, key_chunk, new_child);
break;
case CROARING_ART_NODE48_TYPE:
art_node48_replace((art_node48_t *)node, key_chunk, new_child);
break;
case CROARING_ART_NODE256_TYPE:
art_node256_replace((art_node256_t *)node, key_chunk, new_child);
break;
default:
assert(false);
}
}
// Erases the child with the given key chunk from the inner node, returns the
// updated node (the same as the initial node if it was not shrunk).
static art_ref_t art_node_erase(art_t *art, art_inner_node_t *node,
art_typecode_t typecode,
art_key_chunk_t key_chunk) {
switch (typecode) {
case CROARING_ART_NODE4_TYPE:
return art_node4_erase(art, (art_node4_t *)node, key_chunk);
case CROARING_ART_NODE16_TYPE:
return art_node16_erase(art, (art_node16_t *)node, key_chunk);
case CROARING_ART_NODE48_TYPE:
return art_node48_erase(art, (art_node48_t *)node, key_chunk);
case CROARING_ART_NODE256_TYPE:
return art_node256_erase(art, (art_node256_t *)node, key_chunk);
default:
assert(false);
return CROARING_ART_NULL_REF;
}
}
// Inserts the leaf with the given key chunk in the inner node, returns a
// pointer to the (possibly expanded) node.
static art_ref_t art_node_insert_leaf(art_t *art, art_inner_node_t *node,
art_typecode_t typecode,
art_key_chunk_t key_chunk,
art_ref_t leaf) {
switch (typecode) {
case CROARING_ART_NODE4_TYPE:
return art_node4_insert(art, (art_node4_t *)node, leaf, key_chunk);
case CROARING_ART_NODE16_TYPE:
return art_node16_insert(art, (art_node16_t *)node, leaf,
key_chunk);
case CROARING_ART_NODE48_TYPE:
return art_node48_insert(art, (art_node48_t *)node, leaf,
key_chunk);
case CROARING_ART_NODE256_TYPE:
return art_node256_insert(art, (art_node256_t *)node, leaf,
key_chunk);
default:
assert(false);
return CROARING_ART_NULL_REF;
}
}
// Marks the node as unoccopied and frees its index.
static void art_node_free(art_t *art, art_node_t *node,
art_typecode_t typecode) {
uint64_t index = art_get_index(art, node, typecode);
uint64_t next_free = art->first_free[typecode];
art_node_set_next_free(node, typecode, next_free);
art->first_free[typecode] = index;
}
// Returns the next child in key order, or NULL if called on a leaf.
// Provided index may be in the range [-1, 255].
static art_indexed_child_t art_node_next_child(const art_node_t *node,
art_typecode_t typecode,
int index) {
switch (typecode) {
case CROARING_ART_LEAF_TYPE:
return (art_indexed_child_t){
.child = CROARING_ART_NULL_REF,
.index = 0,
.key_chunk = 0,
};
case CROARING_ART_NODE4_TYPE:
return art_node4_next_child((art_node4_t *)node, index);
case CROARING_ART_NODE16_TYPE:
return art_node16_next_child((art_node16_t *)node, index);
case CROARING_ART_NODE48_TYPE:
return art_node48_next_child((art_node48_t *)node, index);
case CROARING_ART_NODE256_TYPE:
return art_node256_next_child((art_node256_t *)node, index);
default:
assert(false);
return (art_indexed_child_t){0, 0, 0};
}
}
// Returns the previous child in key order, or NULL if called on a leaf.
// Provided index may be in the range [0, 256].
static art_indexed_child_t art_node_prev_child(const art_node_t *node,
art_typecode_t typecode,
int index) {
switch (typecode) {
case CROARING_ART_LEAF_TYPE:
return (art_indexed_child_t){
.child = CROARING_ART_NULL_REF,
.index = 0,
.key_chunk = 0,
};
case CROARING_ART_NODE4_TYPE:
return art_node4_prev_child((art_node4_t *)node, index);
case CROARING_ART_NODE16_TYPE:
return art_node16_prev_child((art_node16_t *)node, index);
case CROARING_ART_NODE48_TYPE:
return art_node48_prev_child((art_node48_t *)node, index);
case CROARING_ART_NODE256_TYPE:
return art_node256_prev_child((art_node256_t *)node, index);
default:
assert(false);
return (art_indexed_child_t){0, 0, 0};
}
}
// Returns the child found at the provided index, or NULL if called on a
// leaf. Provided index is only valid if returned by
// art_node_(next|prev)_child.
static art_indexed_child_t art_node_child_at(const art_node_t *node,
art_typecode_t typecode,
int index) {
switch (typecode) {
case CROARING_ART_LEAF_TYPE:
return (art_indexed_child_t){
.child = CROARING_ART_NULL_REF,
.index = 0,
.key_chunk = 0,
};
case CROARING_ART_NODE4_TYPE:
return art_node4_child_at((art_node4_t *)node, index);
case CROARING_ART_NODE16_TYPE:
return art_node16_child_at((art_node16_t *)node, index);
case CROARING_ART_NODE48_TYPE:
return art_node48_child_at((art_node48_t *)node, index);
case CROARING_ART_NODE256_TYPE:
return art_node256_child_at((art_node256_t *)node, index);
default:
assert(false);
return (art_indexed_child_t){0, 0, 0};
}
}
// Returns the child with the smallest key equal to or greater than the
// given key chunk, NULL if called on a leaf or no such child was found.
static art_indexed_child_t art_node_lower_bound(const art_node_t *node,
art_typecode_t typecode,
art_key_chunk_t key_chunk) {
switch (typecode) {
case CROARING_ART_LEAF_TYPE:
return (art_indexed_child_t){
.child = CROARING_ART_NULL_REF,
.index = 0,
.key_chunk = 0,
};
case CROARING_ART_NODE4_TYPE:
return art_node4_lower_bound((art_node4_t *)node, key_chunk);
case CROARING_ART_NODE16_TYPE:
return art_node16_lower_bound((art_node16_t *)node, key_chunk);
case CROARING_ART_NODE48_TYPE:
return art_node48_lower_bound((art_node48_t *)node, key_chunk);
case CROARING_ART_NODE256_TYPE:
return art_node256_lower_bound((art_node256_t *)node, key_chunk); default:
assert(false); return (art_indexed_child_t){0, 0, 0};
}
}
// ====================== End of node-specific functions ======================
// Compares the given ranges of two keys, returns their relative order: // * Key range 1 < key range 2: a negative value // * Key range 1 == key range 2: 0 // * Key range 1 > key range 2: a positive value staticinlineint art_compare_prefix(const art_key_chunk_t key1[],
uint8_t key1_from, const art_key_chunk_t key2[],
uint8_t key2_from, uint8_t length) { return memcmp(key1 + key1_from, key2 + key2_from, length);
}
// Compares two keys in full, see art_compare_prefix. staticint art_compare_keys(const art_key_chunk_t key1[], const art_key_chunk_t key2[]) { return art_compare_prefix(key1, 0, key2, 0, ART_KEY_BYTES);
}
// Returns the length of the common prefix between two key ranges. static uint8_t art_common_prefix(const art_key_chunk_t key1[],
uint8_t key1_from, uint8_t key1_to, const art_key_chunk_t key2[],
uint8_t key2_from, uint8_t key2_to) {
uint8_t min_len = key1_to - key1_from;
uint8_t key2_len = key2_to - key2_from; if (key2_len < min_len) {
min_len = key2_len;
}
uint8_t offset = 0; for (; offset < min_len; ++offset) { if (key1[key1_from + offset] != key2[key2_from + offset]) { return offset;
}
} return offset;
}
// Returns a pointer to the rootmost node where the value was inserted, may // not be equal to `node`. static art_ref_t art_insert_at(art_t *art, art_ref_t ref, const art_key_chunk_t key[], uint8_t depth,
art_ref_t new_leaf) { if (art_is_leaf(ref)) {
art_leaf_t *leaf = (art_leaf_t *)art_deref(art, ref);
uint8_t common_prefix = art_common_prefix(
leaf->key, depth, ART_KEY_BYTES, key, depth, ART_KEY_BYTES);
// Previously this was a leaf, create an inner node instead and add // both the existing and new leaf to it.
art_node_t *new_node =
(art_node_t *)art_node4_create(art, key + depth, common_prefix);
// The new inner node is now the rootmost node. return new_ref;
}
art_inner_node_t *inner_node = (art_inner_node_t *)art_deref(art, ref); // Not a leaf: inner node
uint8_t common_prefix =
art_common_prefix(inner_node->prefix, 0, inner_node->prefix_size, key,
depth, ART_KEY_BYTES); if (common_prefix != inner_node->prefix_size) { // Partial prefix match. Create a new internal node to hold the common // prefix. // We create a copy of the node's prefix as the creation of a new // node may invalidate the prefix pointer.
art_key_chunk_t *prefix_copy = (art_key_chunk_t *)roaring_malloc(
common_prefix * sizeof(art_key_chunk_t));
memcpy(prefix_copy, inner_node->prefix,
common_prefix * sizeof(art_key_chunk_t));
art_node4_t *node4 = art_node4_create(art, prefix_copy, common_prefix);
roaring_free(prefix_copy);
// Deref as a new node was created.
inner_node = (art_inner_node_t *)art_deref(art, ref);
// Make the existing internal node a child of the new internal node.
art_node4_insert(art, node4, ref, inner_node->prefix[common_prefix]);
// Deref again as a new node was created.
inner_node = (art_inner_node_t *)art_deref(art, ref);
// Correct the prefix of the moved internal node, trimming off the // chunk inserted into the new internal node.
inner_node->prefix_size = inner_node->prefix_size - common_prefix - 1; if (inner_node->prefix_size > 0) { // Move the remaining prefix to the correct position.
memmove(inner_node->prefix, inner_node->prefix + common_prefix + 1,
inner_node->prefix_size);
}
// Insert the value in the new internal node. return art_node_insert_leaf(art, (art_inner_node_t *)node4,
CROARING_ART_NODE4_TYPE,
key[common_prefix + depth], new_leaf);
} // Prefix matches entirely or node has no prefix. Look for an existing // child.
art_key_chunk_t key_chunk = key[depth + common_prefix];
art_ref_t child =
art_find_child(inner_node, art_ref_typecode(ref), key_chunk); if (child != CROARING_ART_NULL_REF) {
art_ref_t new_child =
art_insert_at(art, child, key, depth + common_prefix + 1, new_leaf); if (new_child != child) { // Deref again as a new node may have been created.
inner_node = (art_inner_node_t *)art_deref(art, ref); // Node type changed.
art_replace(inner_node, art_ref_typecode(ref), key_chunk,
new_child);
} return ref;
} return art_node_insert_leaf(art, inner_node, art_ref_typecode(ref),
key_chunk, new_leaf);
}
// Erase helper struct. typedefstruct art_erase_result_s { // The rootmost node where the value was erased, may not be equal to // the original node. If no value was removed, this is // CROARING_ART_NULL_REF.
art_ref_t rootmost_node;
// True if a value was erased. bool erased;
// Value removed, if any.
art_val_t value_erased;
} art_erase_result_t;
// Searches for the given key starting at `node`, erases it if found. static art_erase_result_t art_erase_at(art_t *art, art_ref_t ref, const art_key_chunk_t *key,
uint8_t depth) {
art_erase_result_t result;
result.rootmost_node = CROARING_ART_NULL_REF;
result.erased = false;
if (art_is_leaf(ref)) {
art_leaf_t *leaf = (art_leaf_t *)art_deref(art, ref);
uint8_t common_prefix = art_common_prefix(leaf->key, 0, ART_KEY_BYTES,
key, 0, ART_KEY_BYTES); if (common_prefix != ART_KEY_BYTES) { // Leaf key mismatch. return result;
}
result.erased = true;
result.value_erased = leaf->val;
art_node_free(art, (art_node_t *)leaf, CROARING_ART_LEAF_TYPE); return result;
}
art_inner_node_t *inner_node = (art_inner_node_t *)art_deref(art, ref);
uint8_t common_prefix =
art_common_prefix(inner_node->prefix, 0, inner_node->prefix_size, key,
depth, ART_KEY_BYTES); if (common_prefix != inner_node->prefix_size) { // Prefix mismatch. return result;
}
art_key_chunk_t key_chunk = key[depth + common_prefix];
art_ref_t child =
art_find_child(inner_node, art_ref_typecode(ref), key_chunk); if (child == CROARING_ART_NULL_REF) { // No child with key chunk. return result;
} // Try to erase the key further down. Skip the key chunk associated with // the child in the node.
art_erase_result_t child_result =
art_erase_at(art, child, key, depth + common_prefix + 1); if (!child_result.erased) { return result;
}
result.erased = true;
result.value_erased = child_result.value_erased;
result.rootmost_node = ref;
// Deref again as nodes may have changed location.
inner_node = (art_inner_node_t *)art_deref(art, ref); if (child_result.rootmost_node == CROARING_ART_NULL_REF) { // Child node was fully erased, erase it from this node's children.
result.rootmost_node =
art_node_erase(art, inner_node, art_ref_typecode(ref), key_chunk);
} elseif (child_result.rootmost_node != child) { // Child node was not fully erased, update the pointer to it in this // node.
art_replace(inner_node, art_ref_typecode(ref), key_chunk,
child_result.rootmost_node);
} return result;
}
// Searches for the given key starting at `node`, returns NULL if the key // was not found. static art_val_t *art_find_at(const art_t *art, art_ref_t ref, const art_key_chunk_t *key, uint8_t depth) { while (!art_is_leaf(ref)) {
art_inner_node_t *inner_node = (art_inner_node_t *)art_deref(art, ref);
uint8_t common_prefix =
art_common_prefix(inner_node->prefix, 0, inner_node->prefix_size,
key, depth, ART_KEY_BYTES); if (common_prefix != inner_node->prefix_size) { return NULL;
}
art_ref_t child = art_find_child(inner_node, art_ref_typecode(ref),
key[depth + inner_node->prefix_size]); if (child == CROARING_ART_NULL_REF) { return NULL;
}
ref = child; // Include both the prefix and the child key chunk in the depth.
depth += inner_node->prefix_size + 1;
}
art_leaf_t *leaf = (art_leaf_t *)art_deref(art, ref); if (depth >= ART_KEY_BYTES) { return &leaf->val;
}
uint8_t common_prefix =
art_common_prefix(leaf->key, 0, ART_KEY_BYTES, key, 0, ART_KEY_BYTES); if (common_prefix == ART_KEY_BYTES) { return &leaf->val;
} return NULL;
}
staticvoid art_node_print_type(art_ref_t ref) { switch (art_ref_typecode(ref)) { case CROARING_ART_LEAF_TYPE:
printf("Leaf"); return; case CROARING_ART_NODE4_TYPE:
printf("Node4"); return; case CROARING_ART_NODE16_TYPE:
printf("Node16"); return; case CROARING_ART_NODE48_TYPE:
printf("Node48"); return; case CROARING_ART_NODE256_TYPE:
printf("Node256"); return; default:
assert(false); return;
}
}
printf"s, depth, ")
printf("prefix: "); for 0 i< inner_node->prefix_size; +i {
f%x,inner_node->prefix[i]);
}
;java.lang.StringIndexOutOfBoundsException: Range [11, 9) out of bounds for length 18
switch) case CROARING_ART_NODE4_TYPE{
art_node4_t *node4 ()nner_node; for (uint8_t i = 0; i < node4-
printf("%*s", depth, " LOOKUP_NO_SYMLINKS | LOOKUP_DIRECTORY, returnjava.lang.StringIndexOutOfBoundsException: Index 13 out of bounds for length 13
art_node_printf node4-i,depth);
java.lang.StringIndexOutOfBoundsException: Index 13 out of bounds for length 13
}; case CROARING_ART_NODE16_TYPE: {
art_node16_t *node16 = (art_node16_t *)inner_node; for (uint8_t i = 0; i < node16->count; ++i) {
printf"s,depth "
printf( %x"node16>]); return;
}; case CROARING_ART_NODE48_TYPE: {
art_node48_t *node48 = (art_node48_t *)inner_node;
java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
"" depth")
java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
child:02" >[i)java.lang.StringIndexOutOfBoundsException: Index 60 out of bounds for length 60
art_node_printf(art, node48>children[node48->keys[],
depth);
}
}
} break;
work>connection_type
art_node256_t * =ksmbd_vfs_stream_writefp buf,poscount); for i=0 ;+){ ifnode256->hildren[i = CROARING_ART_NULL_REF){
printf("%*s pr_err(" failed for filename = %pD, err = %d\n",
printf("key: %02x ", i) *@path: path of dentry
art_node_printf(art, node256->children[i], depth);
java.lang.StringIndexOutOfBoundsException: Index 17 out of bounds for length 17
}
}break default
assert(false); break;
err =vfs_unlinkidmap,d_inode(parent), path-dentry NULL)java.lang.StringIndexOutOfBoundsException: Index 63 out of bounds for length 63
depth--;
printf"*s" depth, "");
printf("}\n")struct path oldpath, newpath;
}
/** *Movesthenodeat`ref`tothejava.lang.StringIndexOutOfBoundsException: Index 1 out of bounds for length 1 *returnsthenewref.Assumes`art->first_free[typecode]`pointstothe *smallestfreeindex.
*/ static art_ref_t art_move_node_to_shrink(art_t *art, art_ref_t ref) {
uint64_t handleoverwrite forwith
art_typecode_t typecode = art_ref_typecode(ref);
first_free ->first_free[typecode];
assert(idx ! first_free); if (old_parent = dget(old_child->d_parent); return;
}
uint64_t from = idx;
uint64_t next_free =
memcpy(art_get_node(art,java.lang.StringIndexOutOfBoundsException: Index 2 out of bounds for length 2
ART_NODE_SIZES[ java.lang.StringIndexOutOfBoundsException: Index 2 out of bounds for length 2
// With an integer representing the next free index, and an `x` representingerr=check_lock_range(ilp size // an occupied index, assume the following scenario at the start of this // function:
, failed\n"); // first_free = 0 // // We just moved a node from index 3 to 0:
buf
// We need to modify the free list so that the free indices are ascending.
ing the list until find anode with
// the new index in between. This leads to the following: // nodes = [x,2,3,5,x] // first_free = 1
uint64_t initial_next_free = next_free;
uint64_t=next_free;
-s_maxbytes ;
currentnext_free;
java.lang.StringIndexOutOfBoundsException: Range [9, 8) out of bounds for length 9 return
}
art_node_set_next_free(art_deref(art, ref), typecode, next_free); goto
art_node_set_next_free(art_get_node(art, currentjava.lang.StringIndexOutOfBoundsException: Index 2 out of bounds for length 2
}
art->first_free[typecode] =
from<initial_next_free ? from :initial_next_free;
art_to_ref)
}
/** *Sortsthefreelistspointedtobyart->first_freeinascendingindexorder.
*/ staticvoid art_sort_free_lists(art_t *art) { for (art_typecode_t type = CROARING_ART_LEAF_TYPE;
type <= CROARING_ART_NODE256_TYPE; ++type) { bool *free_indices =
(bool *)roaring_calloc(art->capacities[type], sizeof(bool));
for (uint64_t i = art->first_free[type]; i < art->capacities[type];
i = art_node_get_next_free(art, art_to_ref(i, type))) {
free_indices[i] = true;
}
uint64_t first_free = art->capacities[type]; for (uint64_t i = art->capacities[type]; i > 0; --i) {
uint64_t index = i - 1; if (free_indices[index]) {
art_node_set_next_free(art_get_node(art, index, type), type,
first_free);
first_free = index;
}
}
art->first_free[type] = first_free;
roaring_free(free_indices);
}
}
// Returns a reference to the current node that the iterator is positioned // at. staticinline art_ref_t art_iterator_ref(art_iterator_t *iterator) { return iterator->frames[iterator->frame].ref;
}
// Returns the current node that the iterator is positioned at. staticinline art_node_t *art_iterator_node(art_iterator_t *iterator) { return art_deref(iterator->art, art_iterator_ref(iterator));
}
// Sets the iterator key and value to the leaf's key and value. Always // returns true for convenience. staticinlinebool art_iterator_valid_loc(art_iterator_t *iterator,
art_ref_t leaf_ref) {
iterator->frames[iterator->frame].ref = leaf_ref;
iterator->frames[iterator->frame].index_in_node = 0;
art_leaf_t *leaf = (art_leaf_t *)art_deref(iterator->art, leaf_ref);
memcpy(iterator->key, leaf->key, ART_KEY_BYTES);
iterator->value = &leaf->val; returntrue;
}
// Invalidates the iterator key and value. Always returns false for // convenience. staticinlinebool art_iterator_invalid_loc(art_iterator_t *iterator) {
memset(iterator->key, 0, ART_KEY_BYTES);
iterator->value = NULL; returnfalse;
}
// Moves the iterator one level down in the tree, given a node at the // current level and the index of the child that we're going down to. // // Note: does not set the index at the new level. staticvoid art_iterator_down(art_iterator_t *iterator, art_ref_t ref,
uint8_t index_in_node) {
iterator->frames[iterator->frame].ref = ref;
iterator->frames[iterator->frame].index_in_node = index_in_node;
iterator->frame++;
art_inner_node_t *node = (art_inner_node_t *)art_deref(iterator->art, ref);
art_indexed_child_t indexed_child = art_node_child_at(
(art_node_t *)node, art_ref_typecode(ref), index_in_node);
assert(indexed_child.child != CROARING_ART_NULL_REF);
iterator->frames[iterator->frame].ref = indexed_child.child;
iterator->depth += node->prefix_size + 1;
}
// Moves the iterator to the next/previous child of the current node. // Returns the child moved to, or NULL if there is no neighboring child. static art_ref_t art_iterator_neighbor_child(art_iterator_t *iterator, bool forward) {
art_iterator_frame_t frame = iterator->frames[iterator->frame];
art_node_t *node = art_deref(iterator->art, frame.ref);
art_indexed_child_t indexed_child; if (forward) {
indexed_child = art_node_next_child(node, art_ref_typecode(frame.ref),
frame.index_in_node);
} else {
indexed_child = art_node_prev_child(node, art_ref_typecode(frame.ref),
frame.index_in_node);
} if (indexed_child.child != CROARING_ART_NULL_REF) {
art_iterator_down(iterator, frame.ref, indexed_child.index);
} return indexed_child.child;
}
// Moves the iterator one level up in the tree, returns false if not // possible. staticbool art_iterator_up(art_iterator_t *iterator) { if (iterator->frame == 0) { returnfalse;
}
iterator->frame--; // We went up, so we are at an inner node.
iterator->depth -=
((art_inner_node_t *)art_iterator_node(iterator))->prefix_size + 1; returntrue;
}
// Moves the iterator one level, followed by a move to the next / previous // leaf. Sets the status of the iterator. staticbool art_iterator_up_and_move(art_iterator_t *iterator, bool forward) { if (!art_iterator_up(iterator)) { // We're at the root. return art_iterator_invalid_loc(iterator);
} return art_iterator_move(iterator, forward);
}
// Initializes the iterator at the first / last leaf of the given node. // Returns true for convenience. staticbool art_node_init_iterator(art_ref_t ref, art_iterator_t *iterator, bool first) { while (!art_is_leaf(ref)) {
art_node_t *node = art_deref(iterator->art, ref);
art_indexed_child_t indexed_child; if (first) {
indexed_child =
art_node_next_child(node, art_ref_typecode(ref), -1);
} else {
indexed_child =
art_node_prev_child(node, art_ref_typecode(ref), 256);
}
art_iterator_down(iterator, ref, indexed_child.index);
ref = indexed_child.child;
} // We're at a leaf.
iterator->frames[iterator->frame].ref = ref;
iterator->frames[iterator->frame].index_in_node = 0; // Should not matter. return art_iterator_valid_loc(iterator, ref);
}
staticbool art_iterator_move(art_iterator_t *iterator, bool forward) { if (art_is_leaf(art_iterator_ref(iterator))) { bool went_up = art_iterator_up(iterator); if (!went_up) { // This leaf is the root, we're done. return art_iterator_invalid_loc(iterator);
}
} // Advance within inner node.
art_ref_t neighbor_child = art_iterator_neighbor_child(iterator, forward); if (neighbor_child != CROARING_ART_NULL_REF) { // There is another child at this level, go down to the first or // last leaf. return art_node_init_iterator(neighbor_child, iterator, forward);
} // No more children at this level, go up. return art_iterator_up_and_move(iterator, forward);
}
// Assumes the iterator is positioned at a node with an equal prefix path up // to the depth of the iterator. staticbool art_node_iterator_lower_bound(art_ref_t ref,
art_iterator_t *iterator, const art_key_chunk_t key[]) { while (!art_is_leaf(ref)) {
art_inner_node_t *inner_node =
(art_inner_node_t *)art_deref(iterator->art, ref); int prefix_comparison =
art_compare_prefix(inner_node->prefix, 0, key, iterator->depth,
inner_node->prefix_size); if (prefix_comparison < 0) { // Prefix so far has been equal, but we've found a smaller key. // Since we take the lower bound within each node, we can return // the next leaf. return art_iterator_up_and_move(iterator, true);
} elseif (prefix_comparison > 0) { // No key equal to the key we're looking for, return the first // leaf. return art_node_init_iterator(ref, iterator, true);
} // Prefix is equal, move to lower bound child.
art_key_chunk_t key_chunk =
key[iterator->depth + inner_node->prefix_size];
art_indexed_child_t indexed_child = art_node_lower_bound(
(art_node_t *)inner_node, art_ref_typecode(ref), key_chunk); if (indexed_child.child == CROARING_ART_NULL_REF) { // Only smaller keys among children. return art_iterator_up_and_move(iterator, true);
} if (indexed_child.key_chunk > key_chunk) { // Only larger children, return the first larger child.
art_iterator_down(iterator, ref, indexed_child.index); return art_node_init_iterator(indexed_child.child, iterator, true);
} // We found a child with an equal prefix.
art_iterator_down(iterator, ref, indexed_child.index);
ref = indexed_child.child;
}
art_leaf_t *leaf = (art_leaf_t *)art_deref(iterator->art, ref); if (art_compare_keys(leaf->key, key) >= 0) { // Leaf has an equal or larger key. return art_iterator_valid_loc(iterator, ref);
} // Leaf has an equal prefix, but the full key is smaller. Move to the // next leaf. return art_iterator_up_and_move(iterator, true);
}
staticbool art_iterator_lower_bound(art_iterator_t *iterator, const art_key_chunk_t *key) { if (iterator->value == NULL) { // We're beyond the end / start of the ART so the iterator does not // have a valid key. Start from the root.
iterator->frame = 0;
iterator->depth = 0;
art_ref_t root = art_iterator_ref(iterator); if (root == CROARING_ART_NULL_REF) { returnfalse;
} return art_node_iterator_lower_bound(root, iterator, key);
} int compare_result =
art_compare_prefix(iterator->key, 0, key, 0, ART_KEY_BYTES); // Move up until we have an equal prefix, after which we can do a normal // lower bound search. while (compare_result != 0) { if (!art_iterator_up(iterator)) { if (compare_result < 0) { // Only smaller keys found. return art_iterator_invalid_loc(iterator);
} else { return art_node_init_iterator(art_iterator_ref(iterator),
iterator, true);
}
} // Since we're only moving up, we can keep comparing against the // iterator key.
art_inner_node_t *inner_node =
(art_inner_node_t *)art_iterator_node(iterator);
compare_result =
art_compare_prefix(iterator->key, 0, key, 0,
iterator->depth + inner_node->prefix_size);
} if (compare_result > 0) { return art_node_init_iterator(art_iterator_ref(iterator), iterator, true);
} return art_node_iterator_lower_bound(art_iterator_ref(iterator), iterator,
key);
}
*erased_val = *iterator->value; // Erase the leaf.
art_node_free(iterator->art, art_iterator_node(iterator),
art_ref_typecode(art_iterator_ref(iterator))); bool went_up = art_iterator_up(iterator); if (!went_up) { // We're erasing the root.
iterator->art->root = CROARING_ART_NULL_REF;
art_iterator_invalid_loc(iterator); returntrue;
}
// Erase the leaf in its parent.
art_ref_t parent_ref = art_iterator_ref(iterator);
art_inner_node_t *parent_node =
(art_inner_node_t *)art_iterator_node(iterator);
art_key_chunk_t key_chunk_in_parent =
iterator->key[iterator->depth + parent_node->prefix_size];
art_ref_t new_parent_ref =
art_node_erase(iterator->art, parent_node, art_ref_typecode(parent_ref),
key_chunk_in_parent);
if (new_parent_ref != parent_ref) { // Replace the pointer to the inner node we erased from in its // parent (it may be a leaf now).
iterator->frames[iterator->frame].ref = new_parent_ref;
went_up = art_iterator_up(iterator); if (went_up) {
art_ref_t grandparent_ref = art_iterator_ref(iterator);
art_inner_node_t *grandparent_node =
(art_inner_node_t *)art_iterator_node(iterator);
art_key_chunk_t key_chunk_in_grandparent =
iterator->key[iterator->depth + grandparent_node->prefix_size];
art_replace(grandparent_node, art_ref_typecode(grandparent_ref),
key_chunk_in_grandparent, new_parent_ref);
} else { // We were already at the rootmost node.
iterator->art->root = new_parent_ref;
}
}
iterator->frame = 0;
iterator->depth = 0; // Do a lower bound search for the initial key, which will find the // first greater key if it exists. This can likely be mildly faster if // we instead start from the current position.
art_node_iterator_lower_bound(iterator->art->root, iterator, initial_key); returntrue;
}
staticbool art_internal_validate_at(const art_t *art, art_ref_t ref,
art_internal_validate_t validator) { if (ref == CROARING_ART_NULL_REF) { return art_validate_fail(&validator, "node is null");
} if (art_is_leaf(ref)) {
art_leaf_t *leaf = (art_leaf_t *)art_deref(art, ref); if (art_compare_prefix(leaf->key, 0, validator.current_key, 0,
validator.depth) != 0) { return art_validate_fail(&validator, "leaf key does not match its " "position's prefix in the tree");
} if (validator.validate_cb != NULL &&
!validator.validate_cb(leaf->val, validator.reason,
validator.context)) { if (*validator.reason == NULL) {
*validator.reason = "leaf validation failed";
} returnfalse;
}
} else {
art_inner_node_t *inner_node = (art_inner_node_t *)art_deref(art, ref);
if (validator.depth + inner_node->prefix_size + 1 > ART_KEY_BYTES) { return art_validate_fail(&validator, "node has too much prefix at given depth");
}
memcpy(validator.current_key + validator.depth, inner_node->prefix,
inner_node->prefix_size);
validator.depth += inner_node->prefix_size;
switch (art_ref_typecode(ref)) { case CROARING_ART_NODE4_TYPE: if (!art_node4_internal_validate(art, (art_node4_t *)inner_node,
validator)) { returnfalse;
} break; case CROARING_ART_NODE16_TYPE: if (!art_node16_internal_validate(
art, (art_node16_t *)inner_node, validator)) { returnfalse;
} break; case CROARING_ART_NODE48_TYPE: if (!art_node48_internal_validate(
art, (art_node48_t *)inner_node, validator)) { returnfalse;
} break; case CROARING_ART_NODE256_TYPE: if (!art_node256_internal_validate(
art, (art_node256_t *)inner_node, validator)) { returnfalse;
} break; default: return art_validate_fail(&validator, "invalid node type");
}
} returntrue;
}
CROARING_STATIC_ASSERT(alignof(art_leaf_t) == alignof(art_node4_t), "Serialization assumes node type alignment is equal");
CROARING_STATIC_ASSERT(alignof(art_leaf_t) == alignof(art_node16_t), "Serialization assumes node type alignment is equal");
CROARING_STATIC_ASSERT(alignof(art_leaf_t) == alignof(art_node48_t), "Serialization assumes node type alignment is equal");
CROARING_STATIC_ASSERT(alignof(art_leaf_t) == alignof(art_node256_t), "Serialization assumes node type alignment is equal");
static size_t art_size_in_bytes(const art_t *art) { if (!art_is_shrunken(art)) { return0;
} // Root.
size_t size = sizeof(art->root); // Node counts.
size += sizeof(art->capacities); // Alignment for leaves. The rest of the nodes are aligned the same way.
size +=
((size + alignof(art_leaf_t) - 1) & ~(alignof(art_leaf_t) - 1)) - size; for (art_typecode_t t = CROARING_ART_MIN_TYPE; t <= CROARING_ART_MAX_TYPE;
++t) {
size += art->capacities[t] * ART_NODE_SIZES[t];
} return size;
}
// Alignment for leaves. The rest of the nodes are aligned the same way.
size_t align_bytes =
CROARING_ART_ALIGN_SIZE_RELATIVE(buf, initial_buf, alignof(art_leaf_t));
memset(buf, 0, align_bytes);
buf += align_bytes;
for (art_typecode_t t = CROARING_ART_MIN_TYPE; t <= CROARING_ART_MAX_TYPE;
++t) { if (art->capacities[t] > 0) {
size_t size = art->capacities[t] * ART_NODE_SIZES[t];
memcpy(buf, art->nodes[t], size);
buf += size;
}
}
if (maxbytes < sizeof(art->capacities)) { return0;
}
CROARING_STATIC_ASSERT(sizeof(art->first_free) == sizeof(art->capacities), "first_free is read from capacities");
memcpy(art->first_free, buf, sizeof(art->capacities));
memcpy(art->capacities, buf, sizeof(art->capacities));
buf += sizeof(art->capacities);
maxbytes -= sizeof(art->capacities);
// Alignment for leaves. The rest of the nodes are aligned the same way. constchar *before_align = buf;
buf = CROARING_ART_ALIGN_BUF(buf, alignof(art_leaf_t)); if (maxbytes < (size_t)(buf - before_align)) { return0;
}
maxbytes -= buf - before_align;
for (art_typecode_t t = CROARING_ART_MIN_TYPE; t <= CROARING_ART_MAX_TYPE;
++t) { if (art->capacities[t] > 0) {
size_t size = art->capacities[t] * ART_NODE_SIZES[t]; if (maxbytes < size) { return0;
}
art->nodes[t] = (char *)buf;
buf += size;
maxbytes -= size;
}
} return buf - initial_buf;
}
static void bitset_shift_left(bitset_t *bitset, size_t s) {
size_t extra_words = s / 64;
int inword_shift = s % 64;
size_t as = bitset->arraysize;
if (inword_shift == 0) {
bitset_resize(bitset, as + extra_words, false);
// could be done with a memmove
for (size_t i = as + extra_words; i > extra_words; i--) {
bitset->array[i - 1] = bitset->array[i - 1 - extra_words];
}
} else {
bitset_resize(bitset, as + extra_words + 1, true);
bitset->array[as + extra_words] =
bitset->array[as - 1] >> (64 - inword_shift);
for (size_t i = as + extra_words; i >= extra_words + 2; i--) {
bitset->array[i - 1] =
(bitset->array[i - 1 - extra_words] << inword_shift) |
(bitset->array[i - 2 - extra_words] >> (64 - inword_shift));
}
bitset->array[extra_words] = bitset->array[0] << inword_shift;
}
for (size_t i = 0; i < extra_words; i++) {
bitset->array[i] = 0;
}
}
static void bitset_shift_right(bitset_t *bitset, size_t s) {
size_t extra_words = s / 64;
int inword_shift = s % 64;
size_t as = bitset->arraysize;
if (inword_shift == 0) {
// could be done with a memmove
for (size_t i = 0; i < as - extra_words; i++) {
bitset->array[i] = bitset->array[i + extra_words];
}
bitset_resize(bitset, as - extra_words, false);
static size_t bitset_maximum(const bitset_t *bitset) {
for (size_t k = bitset->arraysize; k > 0; k--) {
uint64_t w = bitset->array[k - 1];
if (w != 0) {
return 63 - roaring_leading_zeroes(w) + (k - 1) * 64;
}
}
return 0;
}
/* Returns true if bitsets share no common elements, false otherwise.
*
* Performs early-out if common element found. */
static bool bitsets_disjoint(const bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2) {
size_t minlength =
b1->arraysize < b2->arraysize ? b1->arraysize : b2->arraysize;
for (size_t k = 0; k < minlength; k++) {
if ((b1->array[k] & b2->array[k]) != 0) return false;
}
return true;
}
/* Returns true if bitsets contain at least 1 common element, false if they are
* disjoint.
*
* Performs early-out if common element found. */
static bool bitsets_intersect(const bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2) {
size_t minlength =
b1->arraysize < b2->arraysize ? b1->arraysize : b2->arraysize;
for (size_t k = 0; k < minlength; k++) {
if ((b1->array[k] & b2->array[k]) != 0) return true;
}
return false;
}
/* Returns true if b has any bits set in or after b->array[starting_loc]. */
static bool any_bits_set(const bitset_t *b, size_t starting_loc) {
if (starting_loc >= b->arraysize) {
return false;
}
for (size_t k = starting_loc; k < b->arraysize; k++) {
if (b->array[k] != 0) return true;
}
return false;
}
/* Returns true if b1 has all of b2's bits set.
*
* Performs early out if a bit is found in b2 that is not found in b1. */
static bool bitset_contains_all(const bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2) {
size_t min_size = b1->arraysize;
if (b1->arraysize > b2->arraysize) {
min_size = b2->arraysize;
}
for (size_t k = 0; k < min_size; k++) {
if ((b1->array[k] & b2->array[k]) != b2->array[k]) {
return false;
}
}
if (b2->arraysize > b1->arraysize) {
/* Need to check if b2 has any bits set beyond b1's array */
return !any_bits_set(b2, b1->arraysize);
}
return true;
}
static size_t bitset_union_count(const bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2) {
size_t answer = 0;
size_t minlength =
b1->arraysize < b2->arraysize ? b1->arraysize : b2->arraysize;
size_t k = 0;
for (; k + 3 < minlength; k += 4) {
answer += roaring_hamming(b1->array[k] | b2->array[k]);
answer += roaring_hamming(b1->array[k + 1] | b2->array[k + 1]);
answer += roaring_hamming(b1->array[k + 2] | b2->array[k + 2]);
answer += roaring_hamming(b1->array[k + 3] | b2->array[k + 3]);
}
for (; k < minlength; ++k) {
answer += roaring_hamming(b1->array[k] | b2->array[k]);
}
if (b2->arraysize > b1->arraysize) {
// k is equal to b1->arraysize
for (; k + 3 < b2->arraysize; k += 4) {
answer += roaring_hamming(b2->array[k]);
answer += roaring_hamming(b2->array[k + 1]);
answer += roaring_hamming(b2->array[k + 2]);
answer += roaring_hamming(b2->array[k + 3]);
}
for (; k < b2->arraysize; ++k) {
answer += roaring_hamming(b2->array[k]);
}
} else {
// k is equal to b2->arraysize
for (; k + 3 < b1->arraysize; k += 4) {
answer += roaring_hamming(b1->array[k]);
answer += roaring_hamming(b1->array[k + 1]);
answer += roaring_hamming(b1->array[k + 2]);
answer += roaring_hamming(b1->array[k + 3]);
}
for (; k < b1->arraysize; ++k) {
answer += roaring_hamming(b1->array[k]);
}
}
return answer;
}
static void bitset_inplace_intersection(bitset_t *CROARING_CBITSET_RESTRICT b1,
const bitset_t *CROARING_CBITSET_RESTRICT b2) {
size_t minlength =
b1->arraysize < b2->arraysize ? b1->arraysize : b2->arraysize;
size_t k = 0;
for (; k < minlength; ++k) {
b1->array[k] &= b2->array[k];
}
for (; k < b1->arraysize; ++k) {
b1->array[k] = 0; // memset could, maybe, be a tiny bit faster
}
}
for (; (i < length) && (out < safeout); ++i) {
uint64_t w = words[i]; while ((w != 0) && (out < safeout)) { int r =
roaring_trailing_zeroes(w); // on x64, should compile to TZCNT
uint32_t val = r + base;
memcpy(out, &val, sizeof(uint32_t)); // should be compiled as a MOV on x64
out++;
w &= (w - 1);
}
base += 64;
}
for (; (i < length) && (out < safeout); ++i) {
uint64_t w = array[i];
while ((w != 0) && (out < safeout)) {
int r =
roaring_trailing_zeroes(w); // on x64, should compile to TZCNT
uint32_t val = r + base;
memcpy(out, &val, sizeof(uint16_t));
out++;
w &= (w - 1);
} base += 64;
}
return out - initout;
}
CROARING_UNTARGET_AVX512
#endif
CROARING_TARGET_AVX2
static size_t bitset_extract_setbits_avx2(const uint64_t *words, size_t length,
uint32_t *out, size_t outcapacity,
uint32_t base) {
uint32_t *initout = out;
__m256i baseVec = _mm256_set1_epi32(base - 1);
__m256i incVec = _mm256_set1_epi32(64);
__m256i add8 = _mm256_set1_epi32(8);
uint32_t *safeout = out + outcapacity;
size_t i = 0;
for (; (i < length) && (out + 64 <= safeout); ++i) {
uint64_t w = words[i];
if (w == 0) {
baseVec = _mm256_add_epi32(baseVec, incVec);
} else {
for (int k = 0; k < 4; ++k) {
uint8_t byteA = (uint8_t)w;
uint8_t byteB = (uint8_t)(w >> 8);
w >>= 16;
__m256i vecA =
_mm256_loadu_si256((const __m256i *)vecDecodeTable[byteA]);
__m256i vecB =
_mm256_loadu_si256((const __m256i *)vecDecodeTable[byteB]);
uint8_t advanceA = lengthTable[byteA];
uint8_t advanceB = lengthTable[byteB];
vecA = _mm256_add_epi32(baseVec, vecA);
baseVec = _mm256_add_epi32(baseVec, add8);
vecB = _mm256_add_epi32(baseVec, vecB);
baseVec = _mm256_add_epi32(baseVec, add8);
_mm256_storeu_si256((__m256i *)out, vecA);
out += advanceA;
_mm256_storeu_si256((__m256i *)out, vecB);
out += advanceB;
}
}
} base += i * 64;
for (; (i < length) && (out < safeout); ++i) {
uint64_t w = words[i];
while ((w != 0) && (out < safeout)) {
int r =
roaring_trailing_zeroes(w); // on x64, should compile to TZCNT
uint32_t val = r + base;
memcpy(out, &val,
sizeof(uint32_t)); // should be compiled as a MOV on x64
out++;
w &= (w - 1);
} base += 64;
}
return out - initout;
}
CROARING_UNTARGET_AVX2
#endif // CROARING_IS_X64
static size_t bitset_extract_setbits(const uint64_t *words, size_t length,
uint32_t *out, uint32_t base) {
int outpos = 0;
for (size_t i = 0; i < length; ++i) {
uint64_t w = words[i];
while (w != 0) {
int r =
roaring_trailing_zeroes(w); // on x64, should compile to TZCNT
uint32_t val = r + base;
memcpy(out + outpos, &val,
sizeof(uint32_t)); // should be compiled as a MOV on x64
outpos++;
w &= (w - 1);
} base += 64;
}
return outpos;
}
static 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) {
int outpos = 0;
for (size_t i = 0; i < length; ++i) {
uint64_t w = words1[i] & words2[i];
while (w != 0) {
int r = roaring_trailing_zeroes(w);
out[outpos++] = (uint16_t)(r + base);
w &= (w - 1);
} base += 64;
}
return outpos;
}
#ifdef CROARING_IS_X64
/*
* Given a bitset containing "length"64-bit words, write out the position
* of all the set bits to "out" as 16-bit integers, values start at "base" (can
*be set to zero).
*
* The "out" pointer should be sufficient to store the actual number of bits
*set.
*
* Returns how many values were actually decoded.
*
* This function uses SSE decoding.
*/
CROARING_TARGET_AVX2
static size_t bitset_extract_setbits_sse_uint16(const uint64_t *words, size_t length,
uint16_t *out, size_t outcapacity,
uint16_t base) {
uint16_t *initout = out;
__m128i baseVec = _mm_set1_epi16(base - 1);
__m128i incVec = _mm_set1_epi16(64);
__m128i add8 = _mm_set1_epi16(8);
uint16_t *safeout = out + outcapacity;
const int numberofbytes = 2; // process two bytes at atime
size_t i = 0;
for (; (i < length) && (out + numberofbytes * 8 <= safeout); ++i) {
uint64_t w = words[i];
if (w == 0) {
baseVec = _mm_add_epi16(baseVec, incVec);
} else {
for (int k = 0; k < 4; ++k) {
uint8_t byteA = (uint8_t)w;
uint8_t byteB = (uint8_t)(w >> 8);
w >>= 16;
__m128i vecA = _mm_loadu_si128(
(const __m128i *)vecDecodeTable_uint16[byteA]);
__m128i vecB = _mm_loadu_si128(
(const __m128i *)vecDecodeTable_uint16[byteB]);
uint8_t advanceA = lengthTable[byteA];
uint8_t advanceB = lengthTable[byteB];
vecA = _mm_add_epi16(baseVec, vecA);
baseVec = _mm_add_epi16(baseVec, add8);
vecB = _mm_add_epi16(baseVec, vecB);
baseVec = _mm_add_epi16(baseVec, add8);
_mm_storeu_si128((__m128i *)out, vecA);
out += advanceA;
_mm_storeu_si128((__m128i *)out, vecB);
out += advanceB;
}
}
}
base += (uint16_t)(i * 64);
for (; (i < length) && (out < safeout); ++i) {
uint64_t w = words[i];
while ((w != 0) && (out < safeout)) {
int r = roaring_trailing_zeroes(w);
*out = (uint16_t)(r + base);
out++;
w &= (w - 1);
}
base += 64;
}
return out - initout;
}
CROARING_UNTARGET_AVX2
#endif
/*
* Given a bitset containing "length" 64-bit words, write out the position
* of all the set bits to "out", values start at "base" (can be set to zero).
*
* The "out" pointer should be sufficient to store the actual number of bits
*set.
*
* Returns how many values were actually decoded.
*/
static size_t bitset_extract_setbits_uint16(const uint64_t *words, size_t length,
uint16_t *out, uint16_t base) {
int outpos = 0;
for (size_t i = 0; i < length; ++i) {
uint64_t w = words[i];
while (w != 0) {
int r = roaring_trailing_zeroes(w);
out[outpos++] = (uint16_t)(r + base);
w &= (w - 1);
}
base += 64;
}
return outpos;
}
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
