/* 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;
}
for (uint32_t i = start + 1;
(i < BITSET_CONTAINER_SIZE_IN_WORDS) && (i < end); ++i) { if (bitset->words[i] != UINT64_C(0xFFFFFFFFFFFFFFFF)) returnfalse;
}
/* Get the number of bits set */
ALLOW_UNALIGNED staticinlineint bitset_container_cardinality( const bitset_container_t *bitset) { return bitset->cardinality;
}
/* Copy one container into another. We assume that they are distinct. */ staticvoid 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,.... */ staticvoid 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. *Toupdatethecardinality,youshoulddo
* bitset->cardinality = bitset_container_compute_cardinality(bitset).*/ staticint bitset_container_compute_cardinality(const bitset_container_t *bitset);
/* Check whether this bitset is empty,
* it never modifies the bitset struct. */ staticinlinebool 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) returnfalse;
} returntrue;
} 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 */ staticinlinebool bitset_container_const_nonzero_cardinality( const bitset_container_t *bitset) { return !bitset_container_empty(bitset);
}
/* Computes the union of bitsets `src_1' and `src_2' into `dst' and return the
* cardinality. */ staticint 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.
*/ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint 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. */ staticint bitset_container_andnot_nocard(const bitset_container_t *src_1, const bitset_container_t *src_2,
bitset_container_t *dst);
/* 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 */ staticint 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 */ staticint 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 */ staticint bitset_container_index_equalorlarger(const bitset_container_t *container,
uint16_t x);
#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);
/* Get the cardinality of `run'. Requires an actual computation. */ staticint run_container_cardinality(const run_container_t *run);
/* Card > 0?, see run_container_empty for the reverse */ staticinlinebool 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 */ staticinlinebool 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. */ staticvoid run_container_copy(const run_container_t *src, run_container_t *dst);
/* Check whether the container spans the whole chunk (cardinality = 1<<16).
* This check can be done in constant time (inexpensive). */ staticinlinebool 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'. */ staticvoid 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' */ staticvoid 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. */ staticvoid 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 . */ staticint 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'. */ staticvoid run_container_xor(const run_container_t *src_1, const run_container_t *src_2, run_container_t *dst);
/* Returns the smallest value (assumes not empty) */ staticinline uint16_t run_container_minimum(const run_container_t *run) { if (run->n_runs == 0) return0; return run->runs[0].value;
}
/* Returns the largest value (assumes not empty) */ staticinline uint16_t run_container_maximum(const run_container_t *run) { if (run->n_runs == 0) return0; 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 */ staticint 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 */ staticint 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 */ staticinlineint 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;
}
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 *containerand
* 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);
/* 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.*/ staticvoid 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,whichdoesnotinitiallyhaveavalidcontainer. *Returntrueforabitsetresult;falseforarray
*/
/* Compute the andnot of src_1 and src_2 and write the result to *dst(whichhasnocontainerinitially).Itwillmodifysrc_1 *tobedstiftheresultisabitset.Otherwise,itwill *freesrc_1anddstwillbeanewarraycontainer.Inboth *cases,thecallerisresponsiblefordeallocatingdst.
* Returns true iff dst is a bitset */
/* Compute the andnot of src_1 and src_2 and write the result to *dst.Resultmaybeeitherabitsetoranarraycontainer *(returns"resultisbitset").dstdoesnotinitiallyhave *anycontainer,butbecomeseitherabitsetcontainer(return *resulttrue)oranarraycontainer.
*/
/* Compute the andnot of src_1 and src_2 and write the result to *dst.Resultmaybeeitherabitsetoranarraycontainer *(returns"resultisbitset").dstdoesnotinitiallyhave *anycontainer,butbecomeseitherabitsetcontainer(return *resulttrue)oranarraycontainer.
*/
/* Compute the andnot of src_1 and src_2 and write the result to *dst.Resultmaybeeitherabitsetoranarraycontainer *(returns"resultisbitset").dstdoesnotinitiallyhave *anycontainer,butbecomeseitherabitsetcontainer(return *resulttrue)oranarraycontainer.
*/
/* Compute the andnot of src_1 and src_2 and write the result to *dst(whichhasnocontainerinitially).Itwillmodifysrc_1 *tobedstiftheresultisabitset.Otherwise,itwill *freesrc_1anddstwillbeanewarraycontainer.Inboth *cases,thecallerisresponsiblefordeallocatingdst.
* Returns true iff dst is a bitset */
/* Compute the andnot of src_1 and src_2 and write the result to *dst(whichhasnocontainerinitially).Itwillmodifysrc_1 *tobedstiftheresultisabitset.Otherwise,itwill *freesrc_1anddstwillbeanewarraycontainer.Inboth *cases,thecallerisresponsiblefordeallocatingdst.
* Returns true iff dst is a bitset */
/* Compute the andnot of src_1 and src_2 and write the result to *dst(whichhasnocontainerinitially).Itwillmodifysrc_1 *tobedstiftheresultisabitset.Otherwise,itwill *freesrc_1anddstwillbeanewarraycontainer.Inboth *cases,thecallerisresponsiblefordeallocatingdst.
* Returns true iff dst is a bitset */
/* inplace array-array andnot will always be able to reuse the space of
* src_1 */ staticvoid 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(whichhasnocontainerinitially).Returnvalueis *"dstisabitset"
*/
/* Compute the andnot of src_1 and src_2 and write the result to *dst(whichhasnocontainerinitially).Itwillmodifysrc_1 *tobedstiftheresultisabitset.Otherwise,itwill *freesrc_1anddstwillbeanewarraycontainer.Inboth *cases,thecallerisresponsiblefordeallocatingdst.
* Returns true iff dst is a bitset */
/* These functions appear to exclude cases where the *inputshavethesametypeandtheoutputisguaranteed *tohavethesametypeastheinputs.Eg,arrayintersection
*/
/* Compute the intersection of src_1 and src_2 and write the result to *dst.Itisallowedfordsttobeequaltosrc_1.Weassumethatdstisa
* valid container. */ staticvoid 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. */ staticint 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.Itisallowedfordsttobeequaltosrc_1.Weassumethatdstisa
* valid container. */ staticvoid 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.Iftheresultistruethentheresultisabitset_container_t *otherwiseisaarray_container_t. *If*dst==src_2,thenanin-placeintersectionisattempted
**/ staticbool 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 . */ staticint 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
**/ staticint 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. */ staticbool array_run_container_intersect(const array_container_t *src_1, const run_container_t *src_2);
/* Check that src_1 and src_2 intersect.
**/ staticbool run_bitset_container_intersect(const run_container_t *src_1, const bitset_container_t *src_2);
/* Negation across the entire range of the container. *Computethenegationofsrcandwritetheresult *to*dst.Thecomplementofa *sufficientlysparsesetwillalwaysbedenseandahenceabitmap *Weassumethatdstispre-allocatedandavalidbitsetcontainer *Therecanbenoin-placeversion.
*/ staticvoid array_container_negation(const array_container_t *src,
bitset_container_t *dst);
/* Negation across the entire range of the container *Computethenegationofsrcandwritetheresult *to*dst.Atruereturnvalueindicatesabitsetresult, *otherwisetheresultisanarraycontainer. *Weassumethatdstisnotpre-allocated.In *caseoffailure,*dstwillbeNULL.
*/ staticbool bitset_container_negation(const bitset_container_t *src,
container_t **dst);
/* Negation across the entire range of container *Computethenegationofsrcandwritetheresult *to*dst. *Returnvaluesarethe*_TYPECODESasdefined*incontainers.h *Weassumethatdstisnotpre-allocated.In *caseoffailure,*dstwillbeNULL.
*/ staticint run_container_negation(const run_container_t *src, container_t **dst);
/* Negation across a range of the container. *Computethenegationofsrcandwritetheresult *to*dst.Returnstrueiftheresultisabitsetcontainer *andfalseforanarraycontainer.*dstisnotpreallocated.
*/ staticbool array_container_negation_range(const array_container_t *src, constint range_start, constint range_end,
container_t **dst);
/* Even when the result would fit, it is unclear how to make an *inplaceversionwithoutinefficientcopying.Thusthisroutine *maybeawrapperforthenon-in-placeversion
*/ staticbool array_container_negation_range_inplace(array_container_t *src, constint range_start, constint range_end,
container_t **dst);
/* Negation across a range of the container *Computethenegationofsrcandwritetheresult *to*dst.Atruereturnvalueindicatesabitsetresult, *otherwisetheresultisanarraycontainer. *Weassumethatdstisnotpre-allocated.In *caseoffailure,*dstwillbeNULL.
*/ staticbool bitset_container_negation_range(const bitset_container_t *src, constint range_start, constint range_end,
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. */ staticvoid 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.Itisallowedforsrc_2tobedst.Thisversiondoesnot
* update the cardinality of dst (it is set to BITSET_UNKNOWN_CARDINALITY). */ staticvoid array_bitset_container_lazy_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.Weassumethatdstisa *validcontainer.Theresultmightneedtobefurtherconvertedtoarrayor *bitsetcontainer,
* the caller is responsible for the eventual conversion. */ staticvoid 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.Theresultmightneedtobefurtherconvertedtoarrayor *bitsetcontainer,
* the caller is responsible for the eventual conversion. */ staticvoid 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.Itisallowedfordsttobesrc_2. *Ifrun_container_is_full(src_1)istrue,youmustnotbecallingthis *function.
**/ staticvoid 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.Itisallowedfordsttobesrc_2.Thisversiondoesnot *updatethecardinalityofdst(itissettoBITSET_UNKNOWN_CARDINALITY). *Ifrun_container_is_full(src_1)istrue,youmustnotbecallingthis *function.
* */ staticvoid run_bitset_container_lazy_union(const run_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(whichhasnocontainerinitially).
* Result is true iff dst is a bitset */ staticbool 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.Itisallowedforsrc_2tobedst.Thisversiondoesnot *updatethecardinalityofdst(itissettoBITSET_UNKNOWN_CARDINALITY).
*/
staticvoid 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(whichhasnocontainerinitially).Returnvalueis *"dstisabitset"
*/
/* Compute the xor of src_1 and src_2 and write the result to *dst.Resultmaybeeitherabitsetoranarraycontainer *(returns"resultisbitset").dstdoesnotinitiallyhave *anycontainer,butbecomeseitherabitsetcontainer(return *resulttrue)oranarraycontainer.
*/
/* dst does not initially have a valid container. Creates either *anarrayorabitsetcontainer,indicatedbyreturncode. *Abitsetcontainerwillnothaveavalidcardinalityandthe *containertypemightnotbecorrectfortheactualcardinality
*/
/* INPLACE versions (initial implementation may not exploit all inplace *opportunities(ifany...)
*/
/* Compute the xor of src_1 and src_2 and write the result to *dst(whichhasnocontainerinitially).Itwillmodifysrc_1 *tobedstiftheresultisabitset.Otherwise,itwill *freesrc_1anddstwillbeanewarraycontainer.Inboth *cases,thecallerisresponsiblefordeallocatingdst.
* Returns true iff dst is a bitset */
/* Compute the xor of src_1 and src_2 and write the result to *dst.Resultmaybeeitherabitsetoranarraycontainer *(returns"resultisbitset").dstdoesnotinitiallyhave *anycontainer,butbecomeseitherabitsetcontainer(return *resulttrue)oranarraycontainer.
*/
/* Frees a shared container (actually decrement its counter and only frees when
* the counter falls to zero). */ staticvoid shared_container_free(shared_container_t *container);
/* extract a copy from the shared container, freeing the shared container if thereisjustoneinstanceleft, cloneinstanceswhenthecounterishigherthanone
*/
container_t *shared_container_extract_copy(shared_container_t *container,
uint8_t *typecode);
// 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 staticinline 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; return0; // unreached
}
staticinlineconstchar *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;
}
/** *Getthecontainercardinality(numberofelements),requiresatypecode
*/ staticinlineint 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; return0; // unreached
}
// returns true if a container is known to be full. Note that a lazy bitset // container // might be full without us knowing staticinlinebool 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; return0; // unreached
}
staticinlineint container_shrink_to_fit(container_t *c, uint8_t type) {
c = container_mutable_unwrap_shared(c, &type); switch (type) { case BITSET_CONTAINER_TYPE: return0; // 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; return0; // unreached
}
/** *makeacontainerwitharunofones
*/ /* initially always use a run container, even if an array might be *marginally
* smaller */ staticinline 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. */ staticinline 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"thecontainerafterlazyoperations.
*/ staticinline 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; return0; // unreached
}
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);
}
}
/** 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_t frames[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(); /**** *startofthemainvectorizedloop
*****/ 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. constint 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); constint 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++;
} elseif (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
/* Computes the intersection between one small and one large set of uint16_t. *Storestheresultintobufferandreturnthenumberofelements. *Processesthesmallsetinblocksof4valuescallingbinarySearch4 *andbinarySearch2.Thisapproachcanbeslightlysuperiortoaconventional *gallopingsearchinsomeinstances.
*/ 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? staticinline 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 staticint uint16_compare(constvoid *a, constvoid *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);
// working in-place, this function overwrites the repeated values // could be avoided? Warning: assumes len > 0 staticinline 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 /** *EndofSIMD16-bitXORcode
*/
// 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");
} returntrue;
}
// 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. staticvoid 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;
}
}
static uint64_t art_node_get_next_free(const art_t *art, art_ref_t ref) {
art_node_t *node = art_deref(art, ref);
art_typecode_t typecode = art_ref_typecode(ref); switch (typecode) { case CROARING_ART_LEAF_TYPE: return ((art_leaf_t *)node)->next_free; case CROARING_ART_NODE4_TYPE: return ((art_node4_t *)node)->next_free; case CROARING_ART_NODE16_TYPE: return ((art_node16_t *)node)->next_free; case CROARING_ART_NODE48_TYPE: return ((art_node48_t *)node)->next_free; case CROARING_ART_NODE256_TYPE: return ((art_node256_t *)node)->next_free; default:
assert(false); return0;
}
}
staticvoid art_node_set_next_free(art_node_t *node, art_typecode_t typecode,
uint64_t next_free) { switch (typecode) { case CROARING_ART_LEAF_TYPE:
((art_leaf_t *)node)->next_free = next_free; break; case CROARING_ART_NODE4_TYPE:
((art_node4_t *)node)->next_free = next_free; break; case CROARING_ART_NODE16_TYPE:
((art_node16_t *)node)->next_free = next_free; break; case CROARING_ART_NODE48_TYPE:
((art_node48_t *)node)->next_free = next_free; break; case CROARING_ART_NODE256_TYPE:
((art_node256_t *)node)->next_free = next_free; break; default:
assert(false);
}
}
// Marks the node as unoccopied and frees its index. staticvoid 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;
}
}
// With an integer representing the next free index, and an `x` representing // an occupied index, assume the following scenario at the start of this // function: // nodes = [1,2,5,x,x] // first_free = 0 // // We just moved a node from index 3 to 0: // nodes = [x,2,5,?,x] // // We need to modify the free list so that the free indices are ascending. // This can be done by traversing the list until we find a node with a // `next_free` greater than the index we copied the node from, and inserting // 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 current = next_free; while (next_free < from) {
current = next_free;
next_free =
art_node_get_next_free(art, art_to_ref(next_free, typecode));
}
art_node_set_next_free(art_deref(art, ref), typecode, next_free); if (current < from) {
art_node_set_next_free(art_get_node(art, current, typecode), typecode,
from);
}
art->first_free[typecode] =
from < initial_next_free ? from : initial_next_free; return art_to_ref(to, typecode);
}
/** *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;
}
staticvoid 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;
}
}
staticvoid 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) { return63 - roaring_leading_zeroes(w) + (k - 1) * 64;
}
} return0;
}
/* Returns true if bitsets share no common elements, false otherwise. *
* Performs early-out if common element found. */ staticbool 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) returnfalse;
} returntrue;
}
/* Returns true if bitsets contain at least 1 common element, false if they are *disjoint. *
* Performs early-out if common element found. */ staticbool 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) returntrue;
} returnfalse;
}
/* Returns true if b has any bits set in or after b->array[starting_loc]. */ staticbool any_bits_set(const bitset_t *b, size_t starting_loc) { if (starting_loc >= b->arraysize) { returnfalse;
} for (size_t k = starting_loc; k < b->arraysize; k++) { if (b->array[k] != 0) returntrue;
} returnfalse;
}
/* 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. */ staticbool 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]) { returnfalse;
}
} 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);
} returntrue;
}
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;
}
staticvoid 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 /* *Givenabitsetcontaining"length"64-bitwords,writeouttheposition *ofallthesetbitsto"out"as16-bitintegers,valuesstartat"base"(can *besettozero). * *The"out"pointershouldbesufficienttostoretheactualnumberofbits *set. * *Returnshowmanyvalueswereactuallydecoded. * *ThisfunctionusesSSEdecoding.
*/
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; constint numberofbytes = 2; // process two bytes at a time
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
/* *Givenabitsetcontaining"length"64-bitwords,writeouttheposition *ofallthesetbitsto"out",valuesstartat"base"(canbesettozero). * *The"out"pointershouldbesufficienttostoretheactualnumberofbits *set. * *Returnshowmanyvalueswereactuallydecoded.
*/ 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.1.474Bemerkung:
(vorverarbeitet am 2026-07-03)
¤
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.