croaring-ffi-1.0: cbits/CRoaring/src/roaring64.c
#include <assert.h>
#include <stdarg.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <roaring/art/art.h>
#include <roaring/isadetection.h>
#include <roaring/portability.h>
#include <roaring/roaring64.h>
// For serialization / deserialization
#include <roaring/containers/array.h>
#include <roaring/containers/bitset.h>
#include <roaring/containers/run.h>
#include <roaring/roaring.h>
#include <roaring/roaring_array.h>
// containers.h last to avoid conflict with ROARING_CONTAINER_T.
#include <roaring/containers/containers.h>
#define CROARING_ALIGN_BUF(buf, alignment) \
(char *)(((uintptr_t)(buf) + ((alignment)-1)) & \
(ptrdiff_t)(~((alignment)-1)))
#define CROARING_BITSET_ALIGNMENT 64
#ifdef __cplusplus
using namespace ::roaring::internal;
extern "C" {
namespace roaring {
namespace api {
#endif
// TODO: Copy on write.
// TODO: Error on failed allocation.
typedef struct roaring64_bitmap_s {
art_t art;
uint8_t flags;
// The container slots. Every slot at or above end is free; the free slots
// below end (the holes) are kept in a min-heap, so that the lowest free
// slot, first_free, is found without scanning the slots. first_free is
// the top of the heap, or end if there are no holes (capacity if the
// slots are all taken).
uint64_t first_free;
uint64_t end;
uint64_t *holes; // min-heap of num_holes indices
uint64_t num_holes;
uint64_t holes_capacity;
uint64_t capacity;
container_t **containers;
// Parallel to containers[]. Live slots (non-NULL pointers) have the
// matching typecode; NULL slots are skipped and their typecodes ignored.
uint8_t *typecodes;
} roaring64_bitmap_t;
// Leaf type of the ART used to keep the high 48 bits of each entry.
// Low 8 bits: typecode
// High 56 bits: container index
typedef roaring64_leaf_t leaf_t;
// Iterator struct to hold iteration state.
typedef struct roaring64_iterator_s {
// The order here is deliberate: everything `roaring64_iterator_advance`
// touches per value is packed into the first 64 bytes, and `art_it` --
// 136 bytes, of which only `art_it.value` is read per value -- is last.
// Putting `art_it` earlier pushes the rest past the first cache line and
// costs ~18% on a scalar iteration loop.
// Must stay first, and must stay a `roaring64_iterator_public_t`: the
// inline `roaring64_iterator_value` / `roaring64_iterator_has_value` in
// the public header reach these two members by converting a
// `roaring64_iterator_t *` to a pointer to its initial member.
roaring64_iterator_public_t pub;
uint64_t high48; // Key that art_it points to.
roaring_container_iterator_t container_it;
// Forward-iteration cache for bitset containers. `container_iterator_next`
// recomputes the word index from `container_it.index`, reloads the word
// and re-masks it for every value; keeping the remaining bits of the
// current word here turns that into a `tzcnt` and a `blsr`. Array and run
// containers already advance by a single increment and gain nothing from
// a cache, so they stay on the ordinary path.
//
// Every field is a pure function of the ART position and
// `container_it.index`, so the cache describes where the iterator is
// exactly when both still match what it was built from. `fast_type` is
// BITSET_CONTAINER_TYPE, or 0 when there is no usable cache.
uint32_t fast_wordindex;
const art_val_t *fast_art_value;
const uint64_t *fast_words;
uint64_t fast_word;
int32_t fast_index;
uint8_t fast_type;
// If has_value is false, then the iterator is saturated. This field
// indicates the direction of saturation. If true, there are no more values
// in the forward direction. If false, there are no more values in the
// backward direction.
bool saturated_forward;
const roaring64_bitmap_t *r;
art_iterator_t art_it;
} roaring64_iterator_t;
static inline bool is_frozen64(const roaring64_bitmap_t *r) {
return r->flags & ROARING_FLAG_FROZEN;
}
static inline bool is_frozen_art64(const roaring64_bitmap_t *r) {
return r->flags & ROARING_FLAG_FROZEN_ART;
}
typedef union {
bitset_container_t bitset;
array_container_t array;
run_container_t run;
} frozen_container_header_t;
static void *roaring64_arena_alloc(char **arena, size_t num_bytes) {
char *res = *arena;
*arena += num_bytes;
return res;
}
static char *roaring64_arena_pad(char *cursor, const char *base,
size_t alignment) {
uint64_t off = (uint64_t)(cursor - base);
uint64_t aligned = (off + alignment - 1) & ~(uint64_t)(alignment - 1);
return (char *)base + aligned;
}
// Splits the given uint64 key into high 48 bit and low 16 bit components.
// Expects high48_out to be of length ART_KEY_BYTES.
static inline uint16_t split_key(uint64_t key, uint8_t high48_out[]) {
uint64_t tmp = croaring_htobe64(key);
memcpy(high48_out, (uint8_t *)(&tmp), ART_KEY_BYTES);
return (uint16_t)key;
}
// Recombines the high 48 bit and low 16 bit components into a uint64 key.
// Expects high48_out to be of length ART_KEY_BYTES.
static inline uint64_t combine_key(const uint8_t high48[], uint16_t low16) {
uint64_t result = 0;
memcpy((uint8_t *)(&result), high48, ART_KEY_BYTES);
return croaring_be64toh(result) | low16;
}
static inline uint64_t minimum(uint64_t a, uint64_t b) {
return (a < b) ? a : b;
}
static inline leaf_t create_leaf(uint64_t container_index, uint8_t typecode) {
return (container_index << 8) | typecode;
}
static inline uint8_t get_typecode(leaf_t leaf) { return (uint8_t)leaf; }
static inline uint64_t get_index(leaf_t leaf) { return leaf >> 8; }
static inline container_t *get_container(const roaring64_bitmap_t *r,
leaf_t leaf) {
return r->containers[get_index(leaf)];
}
// Writes the pointer and its typecode together so they cannot drift.
static inline void set_container_at(roaring64_bitmap_t *r, uint64_t index,
container_t *container, uint8_t typecode) {
r->containers[index] = container;
r->typecodes[index] = typecode;
}
// Replaces the container of `leaf` with the given container. Returns the
// modified leaf for convenience.
static inline leaf_t replace_container(roaring64_bitmap_t *r, leaf_t *leaf,
container_t *container,
uint8_t typecode) {
uint64_t index = get_index(*leaf);
set_container_at(r, index, container, typecode);
*leaf = create_leaf(index, typecode);
return *leaf;
}
/**
* Grows the array of container pointers (and the parallel typecode array) to
* `new_capacity` entries. Does nothing if `new_capacity` is not larger than
* the current capacity.
*/
static void grow_containers_to(roaring64_bitmap_t *r, uint64_t new_capacity) {
if (new_capacity <= r->capacity) {
return;
}
uint64_t increase = new_capacity - r->capacity;
r->containers = (container_t **)roaring_realloc(
r->containers, new_capacity * sizeof(container_t *));
memset(r->containers + r->capacity, 0, increase * sizeof(container_t *));
r->typecodes = (uint8_t *)roaring_realloc(r->typecodes,
new_capacity * sizeof(uint8_t));
r->capacity = new_capacity;
}
/**
* Extends the array of container pointers (and the parallel typecode array).
*/
static void extend_containers(roaring64_bitmap_t *r) {
uint64_t size = r->first_free;
if (size < r->capacity) {
return;
}
uint64_t new_capacity;
if (r->capacity == 0) {
new_capacity = 2;
} else if (r->capacity < 1024) {
new_capacity = 2 * r->capacity;
} else {
new_capacity = 5 * r->capacity / 4;
}
grow_containers_to(r, new_capacity);
}
/**
* Reserves room for `num_containers` containers in the ART and in the
* container array, so that a result of known maximum size can be built
* without repeatedly reallocating both. Intended for freshly created bitmaps.
*/
static void reserve_containers(roaring64_bitmap_t *r, uint64_t num_containers) {
art_reserve(&r->art, num_containers);
grow_containers_to(r, num_containers);
}
// The heap of holes: holes[0] is the smallest index, and every index is
// smaller than its children, holes[2i+1] and holes[2i+2].
static void holes_push(roaring64_bitmap_t *r, uint64_t index) {
if (r->num_holes == r->holes_capacity) {
uint64_t new_capacity =
r->holes_capacity < 16 ? 16 : 2 * r->holes_capacity;
r->holes = (uint64_t *)roaring_realloc(r->holes,
new_capacity * sizeof(uint64_t));
r->holes_capacity = new_capacity;
}
uint64_t i = r->num_holes++;
while (i > 0) {
uint64_t parent = (i - 1) / 2;
if (r->holes[parent] <= index) {
break;
}
r->holes[i] = r->holes[parent];
i = parent;
}
r->holes[i] = index;
}
static void holes_pop(roaring64_bitmap_t *r) {
uint64_t last = r->holes[--r->num_holes];
uint64_t n = r->num_holes;
uint64_t i = 0;
while (2 * i + 1 < n) {
uint64_t child = 2 * i + 1;
if (child + 1 < n && r->holes[child + 1] < r->holes[child]) {
child++;
}
if (last <= r->holes[child]) {
break;
}
r->holes[i] = r->holes[child];
i = child;
}
if (n > 0) {
r->holes[i] = last;
}
}
// Forgets every hole (the slots below end are then all taken).
static void holes_clear(roaring64_bitmap_t *r) { r->num_holes = 0; }
static inline void update_first_free(roaring64_bitmap_t *r) {
r->first_free = r->num_holes > 0 ? r->holes[0] : r->end;
}
// Takes the lowest free slot and returns its index. The caller fills it.
static uint64_t allocate_index(roaring64_bitmap_t *r) {
uint64_t first_free = r->first_free;
if (first_free == r->capacity) {
extend_containers(r);
}
if (r->num_holes > 0) {
holes_pop(r); // first_free is the top of the heap
} else {
r->end = first_free + 1; // first_free == end
}
update_first_free(r);
return first_free;
}
static leaf_t add_container(roaring64_bitmap_t *r, container_t *container,
uint8_t typecode) {
uint64_t index = allocate_index(r);
set_container_at(r, index, container, typecode);
return create_leaf(index, typecode);
}
static void ensure_container_capacity(roaring64_bitmap_t *r, uint64_t extra) {
uint64_t needed = r->first_free + extra;
if (needed <= r->capacity) {
return;
}
uint64_t new_capacity = r->capacity;
if (new_capacity == 0) {
new_capacity = 2;
}
while (new_capacity < needed) {
uint64_t grown;
if (new_capacity < 1024) {
grown = 2 * new_capacity;
} else {
grown = new_capacity + new_capacity / 4;
}
if (grown <= new_capacity) {
new_capacity = needed;
break;
}
new_capacity = grown;
}
uint64_t increase = new_capacity - r->capacity;
r->containers = (container_t **)roaring_realloc(
r->containers, new_capacity * sizeof(container_t *));
memset(r->containers + r->capacity, 0, increase * sizeof(container_t *));
r->typecodes = (uint8_t *)roaring_realloc(r->typecodes,
new_capacity * sizeof(uint8_t));
r->capacity = new_capacity;
}
// Frees a slot (it does not free the container in it).
static void free_index(roaring64_bitmap_t *r, uint64_t index) {
r->containers[index] = NULL;
if (index + 1 == r->end) {
// The holes, all below index, stay below end.
r->end = index;
} else {
holes_push(r, index);
}
update_first_free(r);
}
static void remove_container(roaring64_bitmap_t *r, leaf_t leaf) {
free_index(r, get_index(leaf));
}
// Copies the container referenced by `leaf` from `r1` to `r2`.
static inline leaf_t copy_leaf_container(const roaring64_bitmap_t *r1,
roaring64_bitmap_t *r2, leaf_t leaf) {
uint8_t typecode = get_typecode(leaf);
container_t *container = container_clone(get_container(r1, leaf), typecode);
return add_container(r2, container, typecode);
}
static inline int compare_high48(art_key_chunk_t key1[],
art_key_chunk_t key2[]) {
return art_compare_keys(key1, key2);
}
// Cache the current container so advance() need not re-read the ART leaf,
// reload the container pointer, or (for bitsets) re-mask the current word.
// Called after any positioning that sets container_it.index.
// fast_type is 0 when there is no usable cache (run containers, exhausted).
CROARING_ALLOW_UNALIGNED
static inline void roaring64_iterator_prime(roaring64_iterator_t *it) {
it->fast_type = 0;
if (it->art_it.value == NULL) {
return;
}
leaf_t leaf = (leaf_t)*it->art_it.value;
if (get_typecode(leaf) != BITSET_CONTAINER_TYPE) {
return;
}
const bitset_container_t *bc =
const_CAST_bitset(get_container(it->r, leaf));
int32_t index = it->container_it.index;
uint32_t wordindex = (uint32_t)index >> 6;
uint32_t bit = (uint32_t)index & 63u;
uint64_t word = bc->words[wordindex];
// Bits strictly after the current value in this word. A shift of 64 is
// undefined, so the last bit of a word is a special case.
it->fast_word =
(bit == 63u) ? UINT64_C(0) : (word & (UINT64_MAX << (bit + 1)));
it->fast_words = bc->words;
it->fast_wordindex = wordindex;
it->fast_index = index;
it->fast_art_value = it->art_it.value;
it->fast_type = BITSET_CONTAINER_TYPE;
}
static inline bool roaring64_iterator_init_at_leaf_first(
roaring64_iterator_t *it) {
it->high48 = combine_key(it->art_it.key, 0);
leaf_t leaf = (leaf_t)*it->art_it.value;
uint16_t low16 = 0;
it->container_it = container_init_iterator(get_container(it->r, leaf),
get_typecode(leaf), &low16);
it->pub.value = it->high48 | low16;
it->pub.has_value = true;
roaring64_iterator_prime(it);
return true;
}
static inline bool roaring64_iterator_init_at_leaf_last(
roaring64_iterator_t *it) {
it->high48 = combine_key(it->art_it.key, 0);
leaf_t leaf = (leaf_t)*it->art_it.value;
uint16_t low16 = 0;
it->container_it = container_init_iterator_last(get_container(it->r, leaf),
get_typecode(leaf), &low16);
it->pub.value = it->high48 | low16;
it->pub.has_value = true;
roaring64_iterator_prime(it);
return true;
}
static inline roaring64_iterator_t *roaring64_iterator_init_at(
const roaring64_bitmap_t *r, roaring64_iterator_t *it, bool first) {
it->r = r;
it->art_it = art_init_iterator((art_t *)&r->art, first);
it->pub.has_value = it->art_it.value != NULL;
if (it->pub.has_value) {
if (first) {
roaring64_iterator_init_at_leaf_first(it);
} else {
roaring64_iterator_init_at_leaf_last(it);
}
} else {
it->saturated_forward = first;
it->fast_type = 0;
}
return it;
}
roaring64_bitmap_t *roaring64_bitmap_create(void) {
roaring64_bitmap_t *r =
(roaring64_bitmap_t *)roaring_malloc(sizeof(roaring64_bitmap_t));
art_init_cleared(&r->art);
r->flags = 0;
r->capacity = 0;
r->first_free = 0;
r->end = 0;
r->holes = NULL;
r->num_holes = 0;
r->holes_capacity = 0;
r->containers = NULL;
r->typecodes = NULL;
return r;
}
void roaring64_bitmap_free(roaring64_bitmap_t *r) {
if (!r) {
return;
}
if (is_frozen64(r)) {
// Headers, containers[], and typecodes[] live in the same allocation
// as `r`. Payloads alias a caller buffer.
if (!is_frozen_art64(r)) {
art_free(&r->art);
}
roaring_free(r);
return;
}
art_iterator_t it = art_init_iterator(&r->art, /*first=*/true);
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
container_free(get_container(r, leaf), get_typecode(leaf));
art_iterator_next(&it);
}
art_free(&r->art);
roaring_free(r->containers);
roaring_free(r->typecodes);
roaring_free(r->holes);
roaring_free(r);
}
roaring64_bitmap_t *roaring64_bitmap_copy(const roaring64_bitmap_t *r) {
roaring64_bitmap_t *result = roaring64_bitmap_create();
reserve_containers(result, art_num_leaves(&r->art));
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
uint8_t result_typecode = get_typecode(leaf);
container_t *result_container =
container_clone(get_container(r, leaf), result_typecode);
leaf_t result_leaf =
add_container(result, result_container, result_typecode);
art_insert(&result->art, it.key, (art_val_t)result_leaf);
art_iterator_next(&it);
}
return result;
}
void roaring64_bitmap_overwrite(roaring64_bitmap_t *dest,
const roaring64_bitmap_t *src) {
if (dest == src) {
return;
}
// Free dest's containers.
art_iterator_t it = art_init_iterator(&dest->art, /*first=*/true);
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
container_free(get_container(dest, leaf), get_typecode(leaf));
art_iterator_next(&it);
}
art_free(&dest->art);
// Reinitialize dest.
art_init_cleared(&dest->art);
dest->flags = 0;
dest->first_free = 0;
dest->end = 0;
holes_clear(dest);
if (dest->capacity > 0) {
memset(dest->containers, 0,
sizeof(dest->containers[0]) * dest->capacity);
}
// Copy src's containers into dest.
it = art_init_iterator((art_t *)&src->art, /*first=*/true);
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
uint8_t typecode = get_typecode(leaf);
container_t *container =
container_clone(get_container(src, leaf), typecode);
leaf_t dest_leaf = add_container(dest, container, typecode);
art_insert(&dest->art, it.key, (art_val_t)dest_leaf);
art_iterator_next(&it);
}
}
/**
* Steal src's containers into dst at high_bits, copying those still shared.
*
* After calling this function, the original bitmap will be empty, and the
* returned bitmap will contain all the values from the original bitmap.
*/
static void move_from_roaring32_offset(roaring64_bitmap_t *dst,
roaring_bitmap_t *src,
uint32_t high_bits) {
uint64_t key_base = ((uint64_t)high_bits) << 32;
uint32_t r32_size = ra_get_size(&src->high_low_container);
ensure_container_capacity(dst, r32_size);
for (uint32_t i = 0; i < r32_size; ++i) {
uint16_t key = ra_get_key_at_index(&src->high_low_container, i);
uint8_t typecode;
container_t *container = ra_get_container_at_index(
&src->high_low_container, (uint16_t)i, &typecode);
container = get_writable_copy_if_shared(container, &typecode);
uint8_t high48[ART_KEY_BYTES];
uint64_t high48_bits = key_base | ((uint64_t)key << 16);
split_key(high48_bits, high48);
leaf_t leaf = add_container(dst, container, typecode);
art_insert(&dst->art, high48, (art_val_t)leaf);
}
// We stole all the containers, so leave behind a size of zero
src->high_low_container.size = 0;
}
roaring64_bitmap_t *roaring64_bitmap_move_from_roaring32(
roaring_bitmap_t *bitmap32) {
roaring64_bitmap_t *result = roaring64_bitmap_create();
move_from_roaring32_offset(result, bitmap32, 0);
return result;
}
roaring64_bitmap_t *roaring64_bitmap_from_range(uint64_t min, uint64_t max,
uint64_t step) {
if (step == 0 || max <= min) {
return NULL;
}
roaring64_bitmap_t *r = roaring64_bitmap_create();
if (step >= (1 << 16)) {
// Only one value per container.
for (uint64_t value = min; value < max; value += step) {
roaring64_bitmap_add(r, value);
if (value > UINT64_MAX - step) {
break;
}
}
return r;
}
do {
uint64_t high_bits = min & 0xFFFFFFFFFFFF0000;
uint16_t container_min = min & 0xFFFF;
uint32_t container_max = (uint32_t)minimum(max - high_bits, 1 << 16);
uint8_t typecode;
container_t *container = container_from_range(
&typecode, container_min, container_max, (uint16_t)step);
uint8_t high48[ART_KEY_BYTES];
split_key(min, high48);
leaf_t leaf = add_container(r, container, typecode);
art_insert(&r->art, high48, (art_val_t)leaf);
uint64_t gap = container_max - container_min + step - 1;
uint64_t increment = gap - (gap % step);
if (min > UINT64_MAX - increment) {
break;
}
min += increment;
} while (min < max);
return r;
}
roaring64_bitmap_t *roaring64_bitmap_of_ptr(size_t n_args,
const uint64_t *vals) {
roaring64_bitmap_t *r = roaring64_bitmap_create();
roaring64_bitmap_add_many(r, n_args, vals);
return r;
}
static inline leaf_t *containerptr_roaring64_bitmap_add(roaring64_bitmap_t *r,
uint8_t *high48,
uint16_t low16,
leaf_t *leaf) {
if (leaf != NULL) {
uint8_t typecode = get_typecode(*leaf);
container_t *container = get_container(r, *leaf);
uint8_t typecode2;
container_t *container2 =
container_add(container, low16, typecode, &typecode2);
if (container2 != container) {
container_free(container, typecode);
replace_container(r, leaf, container2, typecode2);
}
return leaf;
} else {
array_container_t *ac = array_container_create();
uint8_t typecode;
container_t *container =
container_add(ac, low16, ARRAY_CONTAINER_TYPE, &typecode);
assert(ac == container);
leaf_t new_leaf = add_container(r, container, typecode);
return (leaf_t *)art_insert(&r->art, high48, (art_val_t)new_leaf);
}
}
void roaring64_bitmap_add(roaring64_bitmap_t *r, uint64_t val) {
uint8_t high48[ART_KEY_BYTES];
uint16_t low16 = split_key(val, high48);
leaf_t *leaf = (leaf_t *)art_find(&r->art, high48);
containerptr_roaring64_bitmap_add(r, high48, low16, leaf);
}
bool roaring64_bitmap_add_checked(roaring64_bitmap_t *r, uint64_t val) {
uint8_t high48[ART_KEY_BYTES];
uint16_t low16 = split_key(val, high48);
leaf_t *leaf = (leaf_t *)art_find(&r->art, high48);
int old_cardinality = 0;
if (leaf != NULL) {
old_cardinality = container_get_cardinality(get_container(r, *leaf),
get_typecode(*leaf));
}
leaf = containerptr_roaring64_bitmap_add(r, high48, low16, leaf);
int new_cardinality =
container_get_cardinality(get_container(r, *leaf), get_typecode(*leaf));
return old_cardinality != new_cardinality;
}
void roaring64_bitmap_add_bulk(roaring64_bitmap_t *r,
roaring64_bulk_context_t *context,
uint64_t val) {
uint8_t high48[ART_KEY_BYTES];
uint16_t low16 = split_key(val, high48);
leaf_t *leaf = context->leaf;
if (leaf != NULL && compare_high48(context->high_bytes, high48) == 0) {
// We're at a container with the correct high bits.
uint8_t typecode1 = get_typecode(*leaf);
container_t *container1 = get_container(r, *leaf);
uint8_t typecode2;
container_t *container2 =
container_add(container1, low16, typecode1, &typecode2);
if (container2 != container1) {
container_free(container1, typecode1);
replace_container(r, leaf, container2, typecode2);
}
} else {
// We're not positioned anywhere yet or the high bits of the key
// differ.
leaf = (leaf_t *)art_find(&r->art, high48);
context->leaf =
containerptr_roaring64_bitmap_add(r, high48, low16, leaf);
memcpy(context->high_bytes, high48, ART_KEY_BYTES);
}
}
void roaring64_bitmap_add_many(roaring64_bitmap_t *r, size_t n_args,
const uint64_t *vals) {
if (n_args == 0) {
return;
}
const uint64_t *end = vals + n_args;
roaring64_bulk_context_t context = CROARING_ZERO_INITIALIZER;
for (const uint64_t *current_val = vals; current_val != end;
current_val++) {
roaring64_bitmap_add_bulk(r, &context, *current_val);
}
}
static inline void add_range_closed_at(roaring64_bitmap_t *r, art_t *art,
uint8_t *high48, uint16_t min,
uint16_t max) {
leaf_t *leaf = (leaf_t *)art_find(art, high48);
if (leaf != NULL) {
uint8_t typecode1 = get_typecode(*leaf);
container_t *container1 = get_container(r, *leaf);
uint8_t typecode2;
container_t *container2 =
container_add_range(container1, typecode1, min, max, &typecode2);
if (container2 != container1) {
container_free(container1, typecode1);
replace_container(r, leaf, container2, typecode2);
}
return;
}
uint8_t typecode;
// container_add_range is inclusive, but `container_range_of_ones` is
// exclusive.
container_t *container = container_range_of_ones(min, max + 1, &typecode);
leaf_t new_leaf = add_container(r, container, typecode);
art_insert(art, high48, (art_val_t)new_leaf);
}
void roaring64_bitmap_add_range(roaring64_bitmap_t *r, uint64_t min,
uint64_t max) {
if (min >= max) {
return;
}
roaring64_bitmap_add_range_closed(r, min, max - 1);
}
void roaring64_bitmap_add_range_closed(roaring64_bitmap_t *r, uint64_t min,
uint64_t max) {
if (min > max) {
return;
}
art_t *art = &r->art;
uint8_t min_high48[ART_KEY_BYTES];
uint16_t min_low16 = split_key(min, min_high48);
uint8_t max_high48[ART_KEY_BYTES];
uint16_t max_low16 = split_key(max, max_high48);
if (compare_high48(min_high48, max_high48) == 0) {
// Only populate range within one container.
add_range_closed_at(r, art, min_high48, min_low16, max_low16);
return;
}
// Populate a range across containers. Fill intermediate containers
// entirely.
add_range_closed_at(r, art, min_high48, min_low16, 0xffff);
uint64_t min_high_bits = min >> 16;
uint64_t max_high_bits = max >> 16;
for (uint64_t current = min_high_bits + 1; current < max_high_bits;
++current) {
uint8_t current_high48[ART_KEY_BYTES];
split_key(current << 16, current_high48);
add_range_closed_at(r, art, current_high48, 0, 0xffff);
}
add_range_closed_at(r, art, max_high48, 0, max_low16);
}
bool roaring64_bitmap_contains(const roaring64_bitmap_t *r, uint64_t val) {
uint8_t high48[ART_KEY_BYTES];
uint16_t low16 = split_key(val, high48);
leaf_t *leaf = (leaf_t *)art_find(&r->art, high48);
if (leaf != NULL) {
return container_contains(get_container(r, *leaf), low16,
get_typecode(*leaf));
}
return false;
}
bool roaring64_bitmap_contains_range(const roaring64_bitmap_t *r, uint64_t min,
uint64_t max) {
if (min >= max) {
return true;
}
return roaring64_bitmap_contains_range_closed(r, min, max - 1);
}
bool roaring64_bitmap_contains_range_closed(const roaring64_bitmap_t *r,
uint64_t min, uint64_t max) {
if (min > max) {
return true;
}
uint8_t min_high48[ART_KEY_BYTES];
uint16_t min_low16 = split_key(min, min_high48);
uint8_t max_high48[ART_KEY_BYTES];
uint16_t max_low16 = split_key(max, max_high48);
uint64_t max_high48_bits = max & 0xFFFFFFFFFFFF0000;
art_iterator_t it = art_lower_bound((art_t *)&r->art, min_high48);
if (it.value == NULL || combine_key(it.key, 0) > min) {
return false;
}
uint64_t prev_high48_bits = min & 0xFFFFFFFFFFFF0000;
while (it.value != NULL) {
uint64_t current_high48_bits = combine_key(it.key, 0);
if (current_high48_bits > max_high48_bits) {
// We've passed the end of the range. The range is contained only
// if the container holding max was checked.
break;
}
if (current_high48_bits - prev_high48_bits > 0x10000) {
// There is a gap in the iterator that falls in the range.
return false;
}
leaf_t leaf = (leaf_t)*it.value;
uint32_t container_min = 0;
if (compare_high48(it.key, min_high48) == 0) {
container_min = min_low16;
}
uint32_t container_max = 0xFFFF + 1; // Exclusive
if (compare_high48(it.key, max_high48) == 0) {
container_max = (uint32_t)max_low16 + 1;
}
// For the first and last containers we use container_contains_range,
// for the intermediate containers we can use container_is_full.
if (container_min == 0 && container_max == 0xFFFF + 1) {
if (!container_is_full(get_container(r, leaf),
get_typecode(leaf))) {
return false;
}
} else if (!container_contains_range(get_container(r, leaf),
container_min, container_max,
get_typecode(leaf))) {
return false;
}
prev_high48_bits = current_high48_bits;
art_iterator_next(&it);
}
return prev_high48_bits == max_high48_bits;
}
bool roaring64_bitmap_contains_bulk(const roaring64_bitmap_t *r,
roaring64_bulk_context_t *context,
uint64_t val) {
uint8_t high48[ART_KEY_BYTES];
uint16_t low16 = split_key(val, high48);
if (context->leaf == NULL ||
art_compare_keys(context->high_bytes, high48) != 0) {
// We're not positioned anywhere yet or the high bits of the key
// differ.
leaf_t *leaf = (leaf_t *)art_find(&r->art, high48);
if (leaf == NULL) {
return false;
}
context->leaf = leaf;
memcpy(context->high_bytes, high48, ART_KEY_BYTES);
}
return container_contains(get_container(r, *context->leaf), low16,
get_typecode(*context->leaf));
}
bool roaring64_bitmap_select(const roaring64_bitmap_t *r, uint64_t rank,
uint64_t *element) {
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
uint64_t start_rank = 0;
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
uint64_t cardinality = container_get_cardinality(get_container(r, leaf),
get_typecode(leaf));
if (start_rank + cardinality > rank) {
uint32_t uint32_start = 0;
uint32_t uint32_rank = rank - start_rank;
uint32_t uint32_element = 0;
if (container_select(get_container(r, leaf), get_typecode(leaf),
&uint32_start, uint32_rank, &uint32_element)) {
*element = combine_key(it.key, (uint16_t)uint32_element);
return true;
}
return false;
}
start_rank += cardinality;
art_iterator_next(&it);
}
return false;
}
uint64_t roaring64_bitmap_rank(const roaring64_bitmap_t *r, uint64_t val) {
uint8_t high48[ART_KEY_BYTES];
uint16_t low16 = split_key(val, high48);
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
uint64_t rank = 0;
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
int compare_result = compare_high48(it.key, high48);
if (compare_result < 0) {
rank += container_get_cardinality(get_container(r, leaf),
get_typecode(leaf));
} else if (compare_result == 0) {
return rank + container_rank(get_container(r, leaf),
get_typecode(leaf), low16);
} else {
return rank;
}
art_iterator_next(&it);
}
return rank;
}
bool roaring64_bitmap_get_index(const roaring64_bitmap_t *r, uint64_t val,
uint64_t *out_index) {
uint8_t high48[ART_KEY_BYTES];
uint16_t low16 = split_key(val, high48);
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
uint64_t index = 0;
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
int compare_result = compare_high48(it.key, high48);
if (compare_result < 0) {
index += container_get_cardinality(get_container(r, leaf),
get_typecode(leaf));
} else if (compare_result == 0) {
int index16 = container_get_index(get_container(r, leaf),
get_typecode(leaf), low16);
if (index16 < 0) {
return false;
}
*out_index = index + index16;
return true;
} else {
return false;
}
art_iterator_next(&it);
}
return false;
}
// Returns true if a container was removed.
static inline bool containerptr_roaring64_bitmap_remove(roaring64_bitmap_t *r,
uint8_t *high48,
uint16_t low16,
leaf_t *leaf) {
if (leaf == NULL) {
return false;
}
uint8_t typecode = get_typecode(*leaf);
container_t *container = get_container(r, *leaf);
uint8_t typecode2;
container_t *container2 =
container_remove(container, low16, typecode, &typecode2);
if (container2 != container) {
container_free(container, typecode);
replace_container(r, leaf, container2, typecode2);
}
if (!container_nonzero_cardinality(container2, typecode2)) {
container_free(container2, typecode2);
bool erased = art_erase(&r->art, high48, (art_val_t *)leaf);
assert(erased);
(void)erased;
remove_container(r, *leaf);
return true;
}
return false;
}
void roaring64_bitmap_remove(roaring64_bitmap_t *r, uint64_t val) {
art_t *art = &r->art;
uint8_t high48[ART_KEY_BYTES];
uint16_t low16 = split_key(val, high48);
leaf_t *leaf = (leaf_t *)art_find(art, high48);
containerptr_roaring64_bitmap_remove(r, high48, low16, leaf);
}
bool roaring64_bitmap_remove_checked(roaring64_bitmap_t *r, uint64_t val) {
art_t *art = &r->art;
uint8_t high48[ART_KEY_BYTES];
uint16_t low16 = split_key(val, high48);
leaf_t *leaf = (leaf_t *)art_find(art, high48);
if (leaf == NULL) {
return false;
}
int old_cardinality =
container_get_cardinality(get_container(r, *leaf), get_typecode(*leaf));
if (containerptr_roaring64_bitmap_remove(r, high48, low16, leaf)) {
return true;
}
int new_cardinality =
container_get_cardinality(get_container(r, *leaf), get_typecode(*leaf));
return new_cardinality != old_cardinality;
}
void roaring64_bitmap_remove_bulk(roaring64_bitmap_t *r,
roaring64_bulk_context_t *context,
uint64_t val) {
art_t *art = &r->art;
uint8_t high48[ART_KEY_BYTES];
uint16_t low16 = split_key(val, high48);
if (context->leaf != NULL &&
compare_high48(context->high_bytes, high48) == 0) {
// We're at a container with the correct high bits.
uint8_t typecode = get_typecode(*context->leaf);
container_t *container = get_container(r, *context->leaf);
uint8_t typecode2;
container_t *container2 =
container_remove(container, low16, typecode, &typecode2);
if (container2 != container) {
container_free(container, typecode);
replace_container(r, context->leaf, container2, typecode2);
}
if (!container_nonzero_cardinality(container2, typecode2)) {
container_free(container2, typecode2);
leaf_t leaf = 0;
bool erased = art_erase(art, high48, (art_val_t *)&leaf);
assert(erased);
(void)erased;
remove_container(r, leaf);
context->leaf = NULL;
}
} else {
// We're not positioned anywhere yet or the high bits of the key
// differ.
leaf_t *leaf = (leaf_t *)art_find(art, high48);
if (containerptr_roaring64_bitmap_remove(r, high48, low16, leaf)) {
context->leaf = NULL;
} else {
context->leaf = leaf;
memcpy(context->high_bytes, high48, ART_KEY_BYTES);
}
}
}
void roaring64_bitmap_remove_many(roaring64_bitmap_t *r, size_t n_args,
const uint64_t *vals) {
if (n_args == 0) {
return;
}
const uint64_t *end = vals + n_args;
roaring64_bulk_context_t context = CROARING_ZERO_INITIALIZER;
for (const uint64_t *current_val = vals; current_val != end;
current_val++) {
roaring64_bitmap_remove_bulk(r, &context, *current_val);
}
}
static inline void remove_range_closed_at(roaring64_bitmap_t *r, art_t *art,
uint8_t *high48, uint16_t min,
uint16_t max) {
leaf_t *leaf = (leaf_t *)art_find(art, high48);
if (leaf == NULL) {
return;
}
uint8_t typecode = get_typecode(*leaf);
container_t *container = get_container(r, *leaf);
uint8_t typecode2;
container_t *container2 =
container_remove_range(container, typecode, min, max, &typecode2);
if (container2 != container) {
container_free(container, typecode);
if (container2 != NULL) {
replace_container(r, leaf, container2, typecode2);
} else {
bool erased = art_erase(art, high48, NULL);
assert(erased);
(void)erased;
remove_container(r, *leaf);
}
}
}
void roaring64_bitmap_remove_range(roaring64_bitmap_t *r, uint64_t min,
uint64_t max) {
if (min >= max) {
return;
}
roaring64_bitmap_remove_range_closed(r, min, max - 1);
}
void roaring64_bitmap_remove_range_closed(roaring64_bitmap_t *r, uint64_t min,
uint64_t max) {
if (min > max) {
return;
}
art_t *art = &r->art;
uint8_t min_high48[ART_KEY_BYTES];
uint16_t min_low16 = split_key(min, min_high48);
uint8_t max_high48[ART_KEY_BYTES];
uint16_t max_low16 = split_key(max, max_high48);
if (compare_high48(min_high48, max_high48) == 0) {
// Only remove a range within one container.
remove_range_closed_at(r, art, min_high48, min_low16, max_low16);
return;
}
// Remove a range across containers. Remove intermediate containers
// entirely.
remove_range_closed_at(r, art, min_high48, min_low16, 0xffff);
art_iterator_t it = art_upper_bound(art, min_high48);
while (it.value != NULL && art_compare_keys(it.key, max_high48) < 0) {
leaf_t leaf = 0;
bool erased = art_iterator_erase(&it, (art_val_t *)&leaf);
assert(erased);
(void)erased;
container_free(get_container(r, leaf), get_typecode(leaf));
remove_container(r, leaf);
}
remove_range_closed_at(r, art, max_high48, 0, max_low16);
}
void roaring64_bitmap_clear(roaring64_bitmap_t *r) {
roaring64_bitmap_remove_range_closed(r, 0, UINT64_MAX);
}
uint64_t roaring64_bitmap_get_cardinality(const roaring64_bitmap_t *r) {
// Scan the pointer array rather than the ART: the arrays are sequential
// and the ART is not. first_free is a free-list head, not a size, so
// after deletes live containers can sit above it; skip NULL slots.
uint64_t cardinality = 0;
for (uint64_t i = 0; i < r->capacity; ++i) {
if (r->containers[i] != NULL) {
cardinality +=
container_get_cardinality(r->containers[i], r->typecodes[i]);
}
}
return cardinality;
}
uint64_t roaring64_bitmap_range_cardinality(const roaring64_bitmap_t *r,
uint64_t min, uint64_t max) {
if (min >= max) {
return 0;
}
// Convert to a closed range
// No underflow here: passing the above condition implies min < max, so
// there is a number less than max
return roaring64_bitmap_range_closed_cardinality(r, min, max - 1);
}
uint64_t roaring64_bitmap_range_closed_cardinality(const roaring64_bitmap_t *r,
uint64_t min, uint64_t max) {
if (min > max) {
return 0;
}
uint64_t cardinality = 0;
uint8_t min_high48[ART_KEY_BYTES];
uint16_t min_low16 = split_key(min, min_high48);
uint8_t max_high48[ART_KEY_BYTES];
uint16_t max_low16 = split_key(max, max_high48);
art_iterator_t it = art_lower_bound((art_t *)&r->art, min_high48);
while (it.value != NULL) {
int max_compare_result = compare_high48(it.key, max_high48);
if (max_compare_result > 0) {
// We're outside the range.
break;
}
leaf_t leaf = (leaf_t)*it.value;
uint8_t typecode = get_typecode(leaf);
container_t *container = get_container(r, leaf);
if (max_compare_result == 0) {
// We're at the max high key, add only the range up to the low
// 16 bits of max.
cardinality += container_rank(container, typecode, max_low16);
} else {
// We're not yet at the max high key, add the full container
// range.
cardinality += container_get_cardinality(container, typecode);
}
if (compare_high48(it.key, min_high48) == 0 && min_low16 > 0) {
// We're at the min high key, remove the range up to the low 16
// bits of min.
cardinality -= container_rank(container, typecode, min_low16 - 1);
}
art_iterator_next(&it);
}
return cardinality;
}
bool roaring64_bitmap_is_empty(const roaring64_bitmap_t *r) {
return art_is_empty(&r->art);
}
uint64_t roaring64_bitmap_minimum(const roaring64_bitmap_t *r) {
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
if (it.value == NULL) {
return UINT64_MAX;
}
leaf_t leaf = (leaf_t)*it.value;
return combine_key(
it.key, container_minimum(get_container(r, leaf), get_typecode(leaf)));
}
uint64_t roaring64_bitmap_maximum(const roaring64_bitmap_t *r) {
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/false);
if (it.value == NULL) {
return 0;
}
leaf_t leaf = (leaf_t)*it.value;
return combine_key(
it.key, container_maximum(get_container(r, leaf), get_typecode(leaf)));
}
bool roaring64_bitmap_remove_run_compression(roaring64_bitmap_t *r) {
art_iterator_t it = art_init_iterator(&r->art, /*first=*/true);
bool removed = false;
while (it.value != NULL) {
leaf_t *leaf = (leaf_t *)it.value;
if (get_typecode(*leaf) == RUN_CONTAINER_TYPE) {
run_container_t *run = CAST_run(get_container(r, *leaf));
int32_t card = run_container_cardinality(run);
uint8_t new_typecode;
container_t *new_container =
convert_to_bitset_or_array_container(run, card, &new_typecode);
run_container_free(run);
replace_container(r, leaf, new_container, new_typecode);
removed = true;
}
art_iterator_next(&it);
}
return removed;
}
bool roaring64_bitmap_run_optimize(roaring64_bitmap_t *r) {
art_iterator_t it = art_init_iterator(&r->art, /*first=*/true);
bool has_run_container = false;
while (it.value != NULL) {
leaf_t *leaf = (leaf_t *)it.value;
uint8_t new_typecode;
// We don't need to free the existing container if a new one was
// created, convert_run_optimize does that internally.
container_t *new_container = convert_run_optimize(
get_container(r, *leaf), get_typecode(*leaf), &new_typecode);
replace_container(r, leaf, new_container, new_typecode);
has_run_container |= new_typecode == RUN_CONTAINER_TYPE;
art_iterator_next(&it);
}
return has_run_container;
}
static void move_to_shrink(roaring64_bitmap_t *r, leaf_t *leaf) {
uint64_t idx = get_index(*leaf);
if (idx < r->first_free) {
return;
}
uint8_t typecode = get_typecode(*leaf);
container_t *c = get_container(r, *leaf);
uint64_t new_idx = allocate_index(r);
set_container_at(r, new_idx, c, typecode);
free_index(r, idx);
*leaf = create_leaf(new_idx, typecode);
}
static inline bool is_shrunken(const roaring64_bitmap_t *r) {
return art_is_shrunken(&r->art) && r->first_free == r->capacity;
}
size_t roaring64_bitmap_shrink_to_fit(roaring64_bitmap_t *r) {
size_t freed = art_shrink_to_fit(&r->art);
art_iterator_t it = art_init_iterator(&r->art, true);
while (it.value != NULL) {
leaf_t *leaf = (leaf_t *)it.value;
freed += container_shrink_to_fit(get_container(r, *leaf),
get_typecode(*leaf));
move_to_shrink(r, leaf);
art_iterator_next(&it);
}
// Every container now sits below first_free, and every slot below it is
// taken.
r->end = r->first_free;
holes_clear(r);
if (r->holes != NULL) {
freed += r->holes_capacity * sizeof(uint64_t);
roaring_free(r->holes);
r->holes = NULL;
r->holes_capacity = 0;
}
uint64_t new_capacity = r->first_free;
uint64_t capacity = r->capacity;
if (new_capacity == capacity) {
return freed;
}
size_t slack = (size_t)(capacity - new_capacity);
// A failed realloc keeps the larger block, valid under the smaller capacity
// since growth reallocs from the block; a later shrink does not retry it.
bool shrunk;
r->containers = (container_t **)croaring_realloc_shrink(
r->containers, new_capacity * sizeof(container_t *), &shrunk);
if (shrunk) freed += slack * sizeof(container_t *);
r->typecodes = (uint8_t *)croaring_realloc_shrink(
r->typecodes, new_capacity * sizeof(uint8_t), &shrunk);
if (shrunk) freed += slack * sizeof(uint8_t);
r->capacity = new_capacity;
return freed;
}
/**
* (For advanced users.)
* Collect statistics about the bitmap
*/
void roaring64_bitmap_statistics(const roaring64_bitmap_t *r,
roaring64_statistics_t *stat) {
memset(stat, 0, sizeof(*stat));
stat->min_value = roaring64_bitmap_minimum(r);
stat->max_value = roaring64_bitmap_maximum(r);
art_iterator_t it = art_init_iterator((art_t *)&r->art, true);
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
stat->n_containers++;
uint8_t truetype = get_typecode(leaf);
uint32_t card = container_get_cardinality(get_container(r, leaf),
get_typecode(leaf));
uint32_t sbytes =
container_size_in_bytes(get_container(r, leaf), get_typecode(leaf));
stat->cardinality += card;
switch (truetype) {
case BITSET_CONTAINER_TYPE:
stat->n_bitset_containers++;
stat->n_values_bitset_containers += card;
stat->n_bytes_bitset_containers += sbytes;
break;
case ARRAY_CONTAINER_TYPE:
stat->n_array_containers++;
stat->n_values_array_containers += card;
stat->n_bytes_array_containers += sbytes;
break;
case RUN_CONTAINER_TYPE:
stat->n_run_containers++;
stat->n_values_run_containers += card;
stat->n_bytes_run_containers += sbytes;
break;
default:
assert(false);
roaring_unreachable;
}
art_iterator_next(&it);
}
}
static bool roaring64_leaf_internal_validate(const art_val_t val,
const char **reason,
void *context) {
leaf_t leaf = (leaf_t)val;
roaring64_bitmap_t *r = (roaring64_bitmap_t *)context;
uint64_t index = get_index(leaf);
uint8_t typecode = get_typecode(leaf);
if (index >= r->capacity || r->containers[index] == NULL) {
*reason = "ART leaf points at an empty container slot";
return false;
}
if (r->typecodes[index] != typecode) {
*reason = "typecode array does not match ART leaf";
return false;
}
if (typecode == SHARED_CONTAINER_TYPE) {
*reason = "64-bit bitmaps cannot hold shared containers";
return false;
}
return container_internal_validate(r->containers[index], typecode, reason);
}
static int compare_uint64(const void *a, const void *b) {
uint64_t x = *(const uint64_t *)a, y = *(const uint64_t *)b;
return (x > y) - (x < y);
}
// Checks the bookkeeping of the container slots (see roaring64_bitmap_s).
static bool roaring64_slots_internal_validate(const roaring64_bitmap_t *r,
const char **reason) {
if (r->flags & ROARING_FLAG_FROZEN) {
return true; // read-only: every slot is marked as taken
}
if (r->end > r->capacity) {
*reason = "container slots end beyond capacity";
return false;
}
uint64_t free_below_end = 0;
for (uint64_t i = 0; i < r->capacity; ++i) {
if (r->containers[i] == NULL) {
free_below_end += i < r->end;
} else if (i >= r->end) {
*reason = "container slot in use at or above end";
return false;
}
}
if (free_below_end != r->num_holes) {
*reason = "wrong count of free container slots";
return false;
}
// Each hole must be a distinct free slot below end: since there are as
// many holes as free slots below end, they are then exactly those slots.
uint64_t lowest = r->end;
if (r->num_holes > 0) {
uint64_t *sorted =
(uint64_t *)roaring_malloc(r->num_holes * sizeof(uint64_t));
if (sorted == NULL) {
*reason = "out of memory";
return false;
}
memcpy(sorted, r->holes, r->num_holes * sizeof(uint64_t));
qsort(sorted, r->num_holes, sizeof(uint64_t), compare_uint64);
bool ok = true;
for (uint64_t i = 0; i < r->num_holes && ok; ++i) {
ok = sorted[i] < r->end && r->containers[sorted[i]] == NULL &&
(i == 0 || sorted[i - 1] < sorted[i]);
}
roaring_free(sorted);
if (!ok) {
*reason = "container slot hole list is wrong";
return false;
}
for (uint64_t i = 1; i < r->num_holes; ++i) {
if (r->holes[(i - 1) / 2] > r->holes[i]) {
*reason = "container slot holes are not a heap";
return false;
}
}
lowest = r->holes[0];
}
if (lowest != r->first_free) {
*reason = "first_free is not the lowest free container slot";
return false;
}
return true;
}
bool roaring64_bitmap_internal_validate(const roaring64_bitmap_t *r,
const char **reason) {
const char *reason_local;
if (reason == NULL) {
reason = &reason_local;
}
if (!roaring64_slots_internal_validate(r, reason)) {
return false;
}
return art_internal_validate(&r->art, reason,
roaring64_leaf_internal_validate, (void *)r);
}
bool roaring64_bitmap_equals(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
art_iterator_t it1 = art_init_iterator((art_t *)&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL && it2.value != NULL) {
if (compare_high48(it1.key, it2.key) != 0) {
return false;
}
leaf_t leaf1 = (leaf_t)*it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
if (!container_equals(get_container(r1, leaf1), get_typecode(leaf1),
get_container(r2, leaf2), get_typecode(leaf2))) {
return false;
}
art_iterator_next(&it1);
art_iterator_next(&it2);
}
return it1.value == NULL && it2.value == NULL;
}
bool roaring64_bitmap_is_subset(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
art_iterator_t it1 = art_init_iterator((art_t *)&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL) {
bool it2_present = it2.value != NULL;
int compare_result = 0;
if (it2_present) {
compare_result = compare_high48(it1.key, it2.key);
if (compare_result == 0) {
leaf_t leaf1 = (leaf_t)*it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
if (!container_is_subset(
get_container(r1, leaf1), get_typecode(leaf1),
get_container(r2, leaf2), get_typecode(leaf2))) {
return false;
}
art_iterator_next(&it1);
art_iterator_next(&it2);
}
}
if (!it2_present || compare_result < 0) {
return false;
} else if (compare_result > 0) {
art_iterator_lower_bound(&it2, it1.key);
}
}
return true;
}
bool roaring64_bitmap_is_strict_subset(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
return roaring64_bitmap_get_cardinality(r1) <
roaring64_bitmap_get_cardinality(r2) &&
roaring64_bitmap_is_subset(r1, r2);
}
roaring64_bitmap_t *roaring64_bitmap_and(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
roaring64_bitmap_t *result = roaring64_bitmap_create();
art_iterator_t it1 = art_init_iterator((art_t *)&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL && it2.value != NULL) {
// Cases:
// 1. it1 < it2 -> it1++
// 2. it1 == it1 -> output it1 & it2, it1++, it2++
// 3. it1 > it2 -> it2++
int compare_result = compare_high48(it1.key, it2.key);
if (compare_result == 0) {
// Case 2: iterators at the same high key position.
leaf_t leaf1 = (leaf_t)*it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
uint8_t result_typecode;
container_t *result_container =
container_and(get_container(r1, leaf1), get_typecode(leaf1),
get_container(r2, leaf2), get_typecode(leaf2),
&result_typecode);
if (container_nonzero_cardinality(result_container,
result_typecode)) {
leaf_t result_leaf =
add_container(result, result_container, result_typecode);
art_insert(&result->art, it1.key, (art_val_t)result_leaf);
} else {
container_free(result_container, result_typecode);
}
art_iterator_next(&it1);
art_iterator_next(&it2);
} else if (compare_result < 0) {
// Case 1: it1 is before it2.
art_iterator_lower_bound(&it1, it2.key);
} else {
// Case 3: it2 is before it1.
art_iterator_lower_bound(&it2, it1.key);
}
}
return result;
}
uint64_t roaring64_bitmap_and_cardinality(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
uint64_t result = 0;
art_iterator_t it1 = art_init_iterator((art_t *)&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL && it2.value != NULL) {
// Cases:
// 1. it1 < it2 -> it1++
// 2. it1 == it1 -> output cardinaltiy it1 & it2, it1++, it2++
// 3. it1 > it2 -> it2++
int compare_result = compare_high48(it1.key, it2.key);
if (compare_result == 0) {
// Case 2: iterators at the same high key position.
leaf_t leaf1 = (leaf_t)*it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
result += container_and_cardinality(
get_container(r1, leaf1), get_typecode(leaf1),
get_container(r2, leaf2), get_typecode(leaf2));
art_iterator_next(&it1);
art_iterator_next(&it2);
} else if (compare_result < 0) {
// Case 1: it1 is before it2.
art_iterator_lower_bound(&it1, it2.key);
} else {
// Case 3: it2 is before it1.
art_iterator_lower_bound(&it2, it1.key);
}
}
return result;
}
// Inplace and (modifies its first argument).
void roaring64_bitmap_and_inplace(roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
if (r1 == r2) {
return;
}
art_iterator_t it1 = art_init_iterator(&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL) {
// Cases:
// 1. !it2_present -> erase it1
// 2. it2_present
// a. it1 < it2 -> erase it1
// b. it1 == it2 -> output it1 & it2, it1++, it2++
// c. it1 > it2 -> it2++
bool it2_present = it2.value != NULL;
int compare_result = 0;
if (it2_present) {
compare_result = compare_high48(it1.key, it2.key);
if (compare_result == 0) {
// Case 2b: iterators at the same high key position.
leaf_t *leaf1 = (leaf_t *)it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
uint8_t typecode = get_typecode(*leaf1);
container_t *container = get_container(r1, *leaf1);
uint8_t typecode2;
container_t *container2 = container_iand(
container, typecode, get_container(r2, leaf2),
get_typecode(leaf2), &typecode2);
if (container2 != container) {
container_free(container, typecode);
}
if (!container_nonzero_cardinality(container2, typecode2)) {
container_free(container2, typecode2);
art_iterator_erase(&it1, NULL);
remove_container(r1, *leaf1);
} else {
if (container2 != container) {
replace_container(r1, leaf1, container2, typecode2);
}
// Only advance the iterator if we didn't delete the
// leaf, as erasing advances by itself.
art_iterator_next(&it1);
}
art_iterator_next(&it2);
}
}
if (!it2_present || compare_result < 0) {
// Cases 1 and 2a: it1 is the only iterator or is before it2.
leaf_t leaf = 0;
bool erased = art_iterator_erase(&it1, (art_val_t *)&leaf);
assert(erased);
(void)erased;
container_free(get_container(r1, leaf), get_typecode(leaf));
remove_container(r1, leaf);
} else if (compare_result > 0) {
// Case 2c: it1 is after it2.
art_iterator_lower_bound(&it2, it1.key);
}
}
}
bool roaring64_bitmap_intersect(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
art_iterator_t it1 = art_init_iterator((art_t *)&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL && it2.value != NULL) {
// Cases:
// 1. it1 < it2 -> it1++
// 2. it1 == it2 -> return true if the containers intersect,
// else it1++, it2++
// 3. it1 > it2 -> it2++
int compare_result = compare_high48(it1.key, it2.key);
if (compare_result == 0) {
// Case 2: iterators at the same high key position.
leaf_t leaf1 = (leaf_t)*it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
if (container_intersect(
get_container(r1, leaf1), get_typecode(leaf1),
get_container(r2, leaf2), get_typecode(leaf2))) {
return true;
}
art_iterator_next(&it1);
art_iterator_next(&it2);
} else if (compare_result < 0) {
// Case 1: it1 is before it2.
art_iterator_lower_bound(&it1, it2.key);
} else {
// Case 3: it2 is before it1.
art_iterator_lower_bound(&it2, it1.key);
}
}
return false;
}
bool roaring64_bitmap_intersect_with_range(const roaring64_bitmap_t *r,
uint64_t min, uint64_t max) {
if (min >= max) {
return false;
}
roaring64_iterator_t it;
roaring64_iterator_init_at(r, &it, /*first=*/true);
if (!roaring64_iterator_move_equalorlarger(&it, min)) {
return false;
}
return roaring64_iterator_has_value(&it) &&
roaring64_iterator_value(&it) < max;
}
double roaring64_bitmap_jaccard_index(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
uint64_t c1 = roaring64_bitmap_get_cardinality(r1);
uint64_t c2 = roaring64_bitmap_get_cardinality(r2);
uint64_t inter = roaring64_bitmap_and_cardinality(r1, r2);
return (double)inter / (double)(c1 + c2 - inter);
}
roaring64_bitmap_t *roaring64_bitmap_or(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
roaring64_bitmap_t *result = roaring64_bitmap_create();
// The result has at least max(n1, n2) containers and at most n1 + n2, so
// reserving the upper bound is at most a 2x overestimate.
reserve_containers(result,
art_num_leaves(&r1->art) + art_num_leaves(&r2->art));
art_iterator_t it1 = art_init_iterator((art_t *)&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL || it2.value != NULL) {
bool it1_present = it1.value != NULL;
bool it2_present = it2.value != NULL;
// Cases:
// 1. it1_present && !it2_present -> output it1, it1++
// 2. !it1_present && it2_present -> output it2, it2++
// 3. it1_present && it2_present
// a. it1 < it2 -> output it1, it1++
// b. it1 == it2 -> output it1 | it2, it1++, it2++
// c. it1 > it2 -> output it2, it2++
int compare_result = 0;
if (it1_present && it2_present) {
compare_result = compare_high48(it1.key, it2.key);
if (compare_result == 0) {
// Case 3b: iterators at the same high key position.
leaf_t leaf1 = (leaf_t)*it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
uint8_t result_typecode;
container_t *result_container =
container_or(get_container(r1, leaf1), get_typecode(leaf1),
get_container(r2, leaf2), get_typecode(leaf2),
&result_typecode);
leaf_t result_leaf =
add_container(result, result_container, result_typecode);
art_insert(&result->art, it1.key, (art_val_t)result_leaf);
art_iterator_next(&it1);
art_iterator_next(&it2);
}
}
if ((it1_present && !it2_present) || compare_result < 0) {
// Cases 1 and 3a: it1 is the only iterator or is before it2.
leaf_t result_leaf =
copy_leaf_container(r1, result, (leaf_t)*it1.value);
art_insert(&result->art, it1.key, (art_val_t)result_leaf);
art_iterator_next(&it1);
} else if ((!it1_present && it2_present) || compare_result > 0) {
// Cases 2 and 3c: it2 is the only iterator or is before it1.
leaf_t result_leaf =
copy_leaf_container(r2, result, (leaf_t)*it2.value);
art_insert(&result->art, it2.key, (art_val_t)result_leaf);
art_iterator_next(&it2);
}
}
return result;
}
uint64_t roaring64_bitmap_or_cardinality(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
uint64_t c1 = roaring64_bitmap_get_cardinality(r1);
uint64_t c2 = roaring64_bitmap_get_cardinality(r2);
uint64_t inter = roaring64_bitmap_and_cardinality(r1, r2);
return c1 + c2 - inter;
}
void roaring64_bitmap_or_inplace(roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
if (r1 == r2) {
return;
}
art_iterator_t it1 = art_init_iterator(&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL || it2.value != NULL) {
bool it1_present = it1.value != NULL;
bool it2_present = it2.value != NULL;
// Cases:
// 1. it1_present && !it2_present -> it1++
// 2. !it1_present && it2_present -> add it2, it2++
// 3. it1_present && it2_present
// a. it1 < it2 -> it1++
// b. it1 == it2 -> it1 | it2, it1++, it2++
// c. it1 > it2 -> add it2, it2++
int compare_result = 0;
if (it1_present && it2_present) {
compare_result = compare_high48(it1.key, it2.key);
if (compare_result == 0) {
// Case 3b: iterators at the same high key position.
leaf_t *leaf1 = (leaf_t *)it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
uint8_t typecode1 = get_typecode(*leaf1);
container_t *container1 = get_container(r1, *leaf1);
uint8_t typecode2;
container_t *container2 = container_ior(
container1, typecode1, get_container(r2, leaf2),
get_typecode(leaf2), &typecode2);
if (container2 != container1) {
container_free(container1, typecode1);
replace_container(r1, leaf1, container2, typecode2);
}
art_iterator_next(&it1);
art_iterator_next(&it2);
}
}
if ((it1_present && !it2_present) || compare_result < 0) {
// Cases 1 and 3a: it1 is the only iterator or is before it2.
art_iterator_next(&it1);
} else if ((!it1_present && it2_present) || compare_result > 0) {
// Cases 2 and 3c: it2 is the only iterator or is before it1.
leaf_t result_leaf =
copy_leaf_container(r2, r1, (leaf_t)*it2.value);
art_iterator_insert(&it1, it2.key, (art_val_t)result_leaf);
art_iterator_next(&it2);
}
}
}
roaring64_bitmap_t *roaring64_bitmap_xor(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
roaring64_bitmap_t *result = roaring64_bitmap_create();
art_iterator_t it1 = art_init_iterator((art_t *)&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL || it2.value != NULL) {
bool it1_present = it1.value != NULL;
bool it2_present = it2.value != NULL;
// Cases:
// 1. it1_present && !it2_present -> output it1, it1++
// 2. !it1_present && it2_present -> output it2, it2++
// 3. it1_present && it2_present
// a. it1 < it2 -> output it1, it1++
// b. it1 == it2 -> output it1 ^ it2, it1++, it2++
// c. it1 > it2 -> output it2, it2++
int compare_result = 0;
if (it1_present && it2_present) {
compare_result = compare_high48(it1.key, it2.key);
if (compare_result == 0) {
// Case 3b: iterators at the same high key position.
leaf_t leaf1 = (leaf_t)*it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
uint8_t result_typecode;
container_t *result_container =
container_xor(get_container(r1, leaf1), get_typecode(leaf1),
get_container(r2, leaf2), get_typecode(leaf2),
&result_typecode);
if (container_nonzero_cardinality(result_container,
result_typecode)) {
leaf_t result_leaf = add_container(result, result_container,
result_typecode);
art_insert(&result->art, it1.key, (art_val_t)result_leaf);
} else {
container_free(result_container, result_typecode);
}
art_iterator_next(&it1);
art_iterator_next(&it2);
}
}
if ((it1_present && !it2_present) || compare_result < 0) {
// Cases 1 and 3a: it1 is the only iterator or is before it2.
leaf_t result_leaf =
copy_leaf_container(r1, result, (leaf_t)*it1.value);
art_insert(&result->art, it1.key, (art_val_t)result_leaf);
art_iterator_next(&it1);
} else if ((!it1_present && it2_present) || compare_result > 0) {
// Cases 2 and 3c: it2 is the only iterator or is before it1.
leaf_t result_leaf =
copy_leaf_container(r2, result, (leaf_t)*it2.value);
art_insert(&result->art, it2.key, (art_val_t)result_leaf);
art_iterator_next(&it2);
}
}
return result;
}
uint64_t roaring64_bitmap_xor_cardinality(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
uint64_t c1 = roaring64_bitmap_get_cardinality(r1);
uint64_t c2 = roaring64_bitmap_get_cardinality(r2);
uint64_t inter = roaring64_bitmap_and_cardinality(r1, r2);
return c1 + c2 - 2 * inter;
}
void roaring64_bitmap_xor_inplace(roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
assert(r1 != r2);
art_iterator_t it1 = art_init_iterator(&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL || it2.value != NULL) {
bool it1_present = it1.value != NULL;
bool it2_present = it2.value != NULL;
// Cases:
// 1. it1_present && !it2_present -> it1++
// 2. !it1_present && it2_present -> add it2, it2++
// 3. it1_present && it2_present
// a. it1 < it2 -> it1++
// b. it1 == it2 -> it1 ^ it2, it1++, it2++
// c. it1 > it2 -> add it2, it2++
int compare_result = 0;
if (it1_present && it2_present) {
compare_result = compare_high48(it1.key, it2.key);
if (compare_result == 0) {
// Case 3b: iterators at the same high key position.
leaf_t *leaf1 = (leaf_t *)it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
uint8_t typecode1 = get_typecode(*leaf1);
container_t *container1 = get_container(r1, *leaf1);
uint8_t typecode2;
container_t *container2 = container_ixor(
container1, typecode1, get_container(r2, leaf2),
get_typecode(leaf2), &typecode2);
if (!container_nonzero_cardinality(container2, typecode2)) {
container_free(container2, typecode2);
bool erased = art_iterator_erase(&it1, NULL);
assert(erased);
(void)erased;
remove_container(r1, *leaf1);
} else {
if (container2 != container1) {
replace_container(r1, leaf1, container2, typecode2);
}
// Only advance the iterator if we didn't delete the
// leaf, as erasing advances by itself.
art_iterator_next(&it1);
}
art_iterator_next(&it2);
}
}
if ((it1_present && !it2_present) || compare_result < 0) {
// Cases 1 and 3a: it1 is the only iterator or is before it2.
art_iterator_next(&it1);
} else if ((!it1_present && it2_present) || compare_result > 0) {
// Cases 2 and 3c: it2 is the only iterator or is before it1.
leaf_t result_leaf =
copy_leaf_container(r2, r1, (leaf_t)*it2.value);
if (it1_present) {
art_iterator_insert(&it1, it2.key, (art_val_t)result_leaf);
art_iterator_next(&it1);
} else {
art_insert(&r1->art, it2.key, (art_val_t)result_leaf);
}
art_iterator_next(&it2);
}
}
}
roaring64_bitmap_t *roaring64_bitmap_andnot(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
roaring64_bitmap_t *result = roaring64_bitmap_create();
art_iterator_t it1 = art_init_iterator((art_t *)&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL) {
// Cases:
// 1. it1_present && !it2_present -> output it1, it1++
// 2. it1_present && it2_present
// a. it1 < it2 -> output it1, it1++
// b. it1 == it2 -> output it1 - it2, it1++, it2++
// c. it1 > it2 -> it2++
bool it2_present = it2.value != NULL;
int compare_result = 0;
if (it2_present) {
compare_result = compare_high48(it1.key, it2.key);
if (compare_result == 0) {
// Case 2b: iterators at the same high key position.
leaf_t *leaf1 = (leaf_t *)it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
uint8_t result_typecode;
container_t *result_container = container_andnot(
get_container(r1, *leaf1), get_typecode(*leaf1),
get_container(r2, leaf2), get_typecode(leaf2),
&result_typecode);
if (container_nonzero_cardinality(result_container,
result_typecode)) {
leaf_t result_leaf = add_container(result, result_container,
result_typecode);
art_insert(&result->art, it1.key, (art_val_t)result_leaf);
} else {
container_free(result_container, result_typecode);
}
art_iterator_next(&it1);
art_iterator_next(&it2);
}
}
if (!it2_present || compare_result < 0) {
// Cases 1 and 2a: it1 is the only iterator or is before it2.
leaf_t result_leaf =
copy_leaf_container(r1, result, (leaf_t)*it1.value);
art_insert(&result->art, it1.key, (art_val_t)result_leaf);
art_iterator_next(&it1);
} else if (compare_result > 0) {
// Case 2c: it1 is after it2.
art_iterator_next(&it2);
}
}
return result;
}
uint64_t roaring64_bitmap_andnot_cardinality(const roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
uint64_t c1 = roaring64_bitmap_get_cardinality(r1);
uint64_t inter = roaring64_bitmap_and_cardinality(r1, r2);
return c1 - inter;
}
void roaring64_bitmap_andnot_inplace(roaring64_bitmap_t *r1,
const roaring64_bitmap_t *r2) {
art_iterator_t it1 = art_init_iterator(&r1->art, /*first=*/true);
art_iterator_t it2 = art_init_iterator((art_t *)&r2->art, /*first=*/true);
while (it1.value != NULL) {
// Cases:
// 1. it1_present && !it2_present -> it1++
// 2. it1_present && it2_present
// a. it1 < it2 -> it1++
// b. it1 == it2 -> it1 - it2, it1++, it2++
// c. it1 > it2 -> it2++
bool it2_present = it2.value != NULL;
int compare_result = 0;
if (it2_present) {
compare_result = compare_high48(it1.key, it2.key);
if (compare_result == 0) {
// Case 2b: iterators at the same high key position.
leaf_t *leaf1 = (leaf_t *)it1.value;
leaf_t leaf2 = (leaf_t)*it2.value;
uint8_t typecode1 = get_typecode(*leaf1);
container_t *container1 = get_container(r1, *leaf1);
uint8_t typecode2;
container_t *container2 = container_iandnot(
container1, typecode1, get_container(r2, leaf2),
get_typecode(leaf2), &typecode2);
if (!container_nonzero_cardinality(container2, typecode2)) {
container_free(container2, typecode2);
bool erased = art_iterator_erase(&it1, NULL);
assert(erased);
(void)erased;
remove_container(r1, *leaf1);
} else {
if (container2 != container1) {
replace_container(r1, leaf1, container2, typecode2);
}
// Only advance the iterator if we didn't delete the
// leaf, as erasing advances by itself.
art_iterator_next(&it1);
}
art_iterator_next(&it2);
}
}
if (!it2_present || compare_result < 0) {
// Cases 1 and 2a: it1 is the only iterator or is before it2.
art_iterator_next(&it1);
} else if (compare_result > 0) {
// Case 2c: it1 is after it2.
art_iterator_next(&it2);
}
}
}
/**
* Flips the leaf at high48 in the range [min, max), adding the result to
* `r2`. If the high48 key is not found in `r1`, a new container is created.
*/
static void roaring64_flip_leaf(const roaring64_bitmap_t *r1,
roaring64_bitmap_t *r2, uint8_t high48[],
uint32_t min, uint32_t max) {
leaf_t *leaf1 = (leaf_t *)art_find(&r1->art, high48);
uint8_t typecode2;
container_t *container2;
if (leaf1 == NULL) {
// No container at this key, create a full container.
container2 = container_range_of_ones(min, max, &typecode2);
} else if (min == 0 && max > 0xFFFF) {
// Flip whole container.
container2 = container_not(get_container(r1, *leaf1),
get_typecode(*leaf1), &typecode2);
} else {
// Partially flip a container.
container2 =
container_not_range(get_container(r1, *leaf1), get_typecode(*leaf1),
min, max, &typecode2);
}
if (container_nonzero_cardinality(container2, typecode2)) {
leaf_t leaf2 = add_container(r2, container2, typecode2);
art_insert(&r2->art, high48, (art_val_t)leaf2);
} else {
container_free(container2, typecode2);
}
}
/**
* Flips the leaf at high48 in the range [min, max). If the high48 key is
* not found in the bitmap, a new container is created. Deletes the leaf and
* associated container if the negation results in an empty range.
*/
static void roaring64_flip_leaf_inplace(roaring64_bitmap_t *r, uint8_t high48[],
uint32_t min, uint32_t max) {
leaf_t *leaf = (leaf_t *)art_find(&r->art, high48);
container_t *container2;
uint8_t typecode2;
if (leaf == NULL) {
// No container at this key, insert a full container.
container2 = container_range_of_ones(min, max, &typecode2);
leaf_t new_leaf = add_container(r, container2, typecode2);
art_insert(&r->art, high48, (art_val_t)new_leaf);
return;
}
if (min == 0 && max > 0xFFFF) {
// Flip whole container.
container2 = container_inot(get_container(r, *leaf),
get_typecode(*leaf), &typecode2);
} else {
// Partially flip a container.
container2 = container_inot_range(
get_container(r, *leaf), get_typecode(*leaf), min, max, &typecode2);
}
if (container_nonzero_cardinality(container2, typecode2)) {
replace_container(r, leaf, container2, typecode2);
} else {
bool erased = art_erase(&r->art, high48, NULL);
assert(erased);
(void)erased;
container_free(container2, typecode2);
remove_container(r, *leaf);
}
}
roaring64_bitmap_t *roaring64_bitmap_flip(const roaring64_bitmap_t *r,
uint64_t min, uint64_t max) {
if (min >= max) {
return roaring64_bitmap_copy(r);
}
return roaring64_bitmap_flip_closed(r, min, max - 1);
}
roaring64_bitmap_t *roaring64_bitmap_flip_closed(const roaring64_bitmap_t *r1,
uint64_t min, uint64_t max) {
if (min > max) {
return roaring64_bitmap_copy(r1);
}
uint8_t min_high48_key[ART_KEY_BYTES];
uint16_t min_low16 = split_key(min, min_high48_key);
uint8_t max_high48_key[ART_KEY_BYTES];
uint16_t max_low16 = split_key(max, max_high48_key);
uint64_t min_high48_bits = (min & 0xFFFFFFFFFFFF0000ULL) >> 16;
uint64_t max_high48_bits = (max & 0xFFFFFFFFFFFF0000ULL) >> 16;
roaring64_bitmap_t *r2 = roaring64_bitmap_create();
art_iterator_t it = art_init_iterator((art_t *)&r1->art, /*first=*/true);
// Copy the containers before min unchanged.
while (it.value != NULL && compare_high48(it.key, min_high48_key) < 0) {
leaf_t leaf1 = (leaf_t)*it.value;
uint8_t typecode2 = get_typecode(leaf1);
container_t *container2 =
container_clone(get_container(r1, leaf1), typecode2);
leaf_t leaf2 = add_container(r2, container2, typecode2);
art_insert(&r2->art, it.key, (art_val_t)leaf2);
art_iterator_next(&it);
}
// Flip the range (including non-existent containers!) between min and
// max.
for (uint64_t high48_bits = min_high48_bits; high48_bits <= max_high48_bits;
high48_bits++) {
uint8_t current_high48_key[ART_KEY_BYTES];
split_key(high48_bits << 16, current_high48_key);
uint32_t min_container = 0;
if (high48_bits == min_high48_bits) {
min_container = min_low16;
}
uint32_t max_container = 0xFFFF + 1; // Exclusive range.
if (high48_bits == max_high48_bits) {
max_container = max_low16 + 1; // Exclusive.
}
roaring64_flip_leaf(r1, r2, current_high48_key, min_container,
max_container);
}
// Copy the containers after max unchanged.
it = art_upper_bound((art_t *)&r1->art, max_high48_key);
while (it.value != NULL) {
leaf_t leaf1 = (leaf_t)*it.value;
uint8_t typecode2 = get_typecode(leaf1);
container_t *container2 =
container_clone(get_container(r1, leaf1), typecode2);
leaf_t leaf2 = add_container(r2, container2, typecode2);
art_insert(&r2->art, it.key, (art_val_t)leaf2);
art_iterator_next(&it);
}
return r2;
}
void roaring64_bitmap_flip_inplace(roaring64_bitmap_t *r, uint64_t min,
uint64_t max) {
if (min >= max) {
return;
}
roaring64_bitmap_flip_closed_inplace(r, min, max - 1);
}
void roaring64_bitmap_flip_closed_inplace(roaring64_bitmap_t *r, uint64_t min,
uint64_t max) {
if (min > max) {
return;
}
uint16_t min_low16 = (uint16_t)min;
uint16_t max_low16 = (uint16_t)max;
uint64_t min_high48_bits = (min & 0xFFFFFFFFFFFF0000ULL) >> 16;
uint64_t max_high48_bits = (max & 0xFFFFFFFFFFFF0000ULL) >> 16;
// Flip the range (including non-existent containers!) between min and
// max.
for (uint64_t high48_bits = min_high48_bits; high48_bits <= max_high48_bits;
high48_bits++) {
uint8_t current_high48_key[ART_KEY_BYTES];
split_key(high48_bits << 16, current_high48_key);
uint32_t min_container = 0;
if (high48_bits == min_high48_bits) {
min_container = min_low16;
}
uint32_t max_container = 0xFFFF + 1; // Exclusive range.
if (high48_bits == max_high48_bits) {
max_container = max_low16 + 1; // Exclusive.
}
roaring64_flip_leaf_inplace(r, current_high48_key, min_container,
max_container);
}
}
roaring64_bitmap_t *roaring64_bitmap_add_offset_signed(
const roaring64_bitmap_t *r, bool positive, uint64_t offset) {
if (offset == 0) {
return roaring64_bitmap_copy(r);
}
roaring64_bitmap_t *answer = roaring64_bitmap_create();
// Decompose the offset into a signed container-level shift and an
// intra-container shift. For negative offsets the low 16 bits wrap: e.g.
// -1 = container_offset(-1) + in_offset(0xffff), because shifting by -1
// container is a shift of -0x1_0000, so we need to shift up within
// containers to get back to -1
uint16_t low16 = (uint16_t)offset;
int64_t container_offset;
uint16_t in_offset;
if (positive) {
container_offset = (int64_t)(offset >> 16);
in_offset = low16;
} else if (low16 == 0) {
container_offset = -(int64_t)(offset >> 16);
in_offset = 0;
} else {
container_offset = -(int64_t)(offset >> 16) - 1;
in_offset = (uint16_t)-low16;
}
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
if (in_offset == 0) {
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
int64_t k =
(int64_t)(combine_key(it.key, 0) >> 16) + container_offset;
if ((uint64_t)k < (uint64_t)1 << 48) {
uint8_t new_high48[ART_KEY_BYTES];
split_key((uint64_t)k << 16, new_high48);
uint8_t typecode = get_typecode(leaf);
container_t *container =
container_clone(get_container(r, leaf), typecode);
leaf_t new_leaf = add_container(answer, container, typecode);
art_insert(&answer->art, new_high48, (art_val_t)new_leaf);
}
art_iterator_next(&it);
}
return answer;
}
// Track the most recently inserted hi container so that the next
// iteration's lo can merge with it without re-searching the ART.
leaf_t *prev_hi_leaf = NULL;
int64_t prev_hi_k = -1;
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
int64_t k = (int64_t)(combine_key(it.key, 0) >> 16) + container_offset;
container_t *lo = NULL, *hi = NULL;
container_t **lo_ptr = NULL, **hi_ptr = NULL;
if ((uint64_t)k < (uint64_t)1 << 48) {
lo_ptr = &lo;
}
if ((uint64_t)(k + 1) < (uint64_t)1 << 48) {
hi_ptr = &hi;
}
if (lo_ptr == NULL && hi_ptr == NULL) {
art_iterator_next(&it);
continue;
}
uint8_t typecode = get_typecode(leaf);
const container_t *c = get_container(r, leaf);
container_add_offset(c, typecode, lo_ptr, hi_ptr, in_offset);
if (lo != NULL) {
if (prev_hi_leaf != NULL && prev_hi_k == k) {
uint8_t existing_type = get_typecode(*prev_hi_leaf);
container_t *existing_c = get_container(answer, *prev_hi_leaf);
uint8_t merged_type;
container_t *merged_c = container_ior(
existing_c, existing_type, lo, typecode, &merged_type);
if (merged_c != existing_c) {
container_free(existing_c, existing_type);
}
replace_container(answer, prev_hi_leaf, merged_c, merged_type);
container_free(lo, typecode);
} else {
uint8_t lo_high48[ART_KEY_BYTES];
split_key((uint64_t)k << 16, lo_high48);
leaf_t new_leaf = add_container(answer, lo, typecode);
art_insert(&answer->art, lo_high48, (art_val_t)new_leaf);
}
}
prev_hi_leaf = NULL;
if (hi != NULL) {
uint8_t hi_high48[ART_KEY_BYTES];
split_key((uint64_t)(k + 1) << 16, hi_high48);
leaf_t new_leaf = add_container(answer, hi, typecode);
prev_hi_leaf = (leaf_t *)art_insert(&answer->art, hi_high48,
(art_val_t)new_leaf);
prev_hi_k = k + 1;
}
art_iterator_next(&it);
}
// Repair containers (e.g., convert low-cardinality bitset containers to
// array containers after lazy union operations).
art_iterator_t repair_it = art_init_iterator(&answer->art, /*first=*/true);
while (repair_it.value != NULL) {
leaf_t *leaf_ptr = (leaf_t *)repair_it.value;
uint8_t typecode = get_typecode(*leaf_ptr);
container_t *repaired = container_repair_after_lazy(
get_container(answer, *leaf_ptr), &typecode);
replace_container(answer, leaf_ptr, repaired, typecode);
art_iterator_next(&repair_it);
}
return answer;
}
size_t roaring64_bitmap_portable_size_in_bytes(const roaring64_bitmap_t *r) {
// https://github.com/RoaringBitmap/RoaringFormatSpec#extension-for-64-bit-implementations
size_t size = 0;
// Write as uint64 the distinct number of "buckets", where a bucket is
// defined as the most significant 32 bits of an element.
uint64_t high32_count;
size += sizeof(high32_count);
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
// Iterate through buckets ordered by increasing keys.
while (it.value != NULL) {
uint32_t current_high32 = (uint32_t)(combine_key(it.key, 0) >> 32);
// Write as uint32 the most significant 32 bits of the bucket.
size += sizeof(current_high32);
// Write the 32-bit Roaring bitmaps representing the least significant
// bits of a set of elements: the header from
// ra_portable_header_size_from_counts plus the size of each container.
int32_t containers_with_high32 = 0;
bool hasrun = false;
bool bucket_done = false;
while (!bucket_done) {
// Read the containers in batches, so that their cache misses
// overlap instead of each one waiting behind the tree walk.
enum { LEAF_BATCH_SIZE = 64 };
leaf_t leaves[LEAF_BATCH_SIZE];
int32_t num_leaves = 0;
do {
leaves[num_leaves++] = (leaf_t)*it.value;
art_iterator_next(&it);
bucket_done =
it.value == NULL ||
(uint32_t)(combine_key(it.key, 0) >> 32) != current_high32;
} while (!bucket_done && num_leaves < LEAF_BATCH_SIZE);
for (int32_t i = 0; i < num_leaves; ++i) {
const container_t *container = get_container(r, leaves[i]);
uint8_t typecode = get_typecode(leaves[i]);
hasrun |= typecode == RUN_CONTAINER_TYPE;
size += container_size_in_bytes(container, typecode);
}
containers_with_high32 += num_leaves;
}
size +=
ra_portable_header_size_from_counts(containers_with_high32, hasrun);
}
return size;
}
size_t roaring64_bitmap_portable_serialize(const roaring64_bitmap_t *r,
char *buf) {
// https://github.com/RoaringBitmap/RoaringFormatSpec#extension-for-64-bit-implementations
if (buf == NULL) {
return 0;
}
const char *initial_buf = buf;
// Write as uint64 the distinct number of "buckets", where a bucket is
// defined as the most significant 32 bits of an element. The count is
// only known after the loop, so we reserve its place for now.
char *high32_count_buf = buf;
buf += sizeof(uint64_t);
uint64_t high32_count = 0;
// A 32-bit roaring array that borrows the containers of the current
// bucket. It is reused across buckets to avoid allocating per bucket.
roaring_array_t bucket;
ra_init(&bucket);
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
// Iterate through buckets ordered by increasing keys.
while (it.value != NULL) {
uint32_t current_high32 = (uint32_t)(combine_key(it.key, 0) >> 32);
bucket.size = 0;
do {
leaf_t leaf = (leaf_t)*it.value;
ra_append(&bucket, (uint16_t)(combine_key(it.key, 0) >> 16),
get_container(r, leaf), get_typecode(leaf));
art_iterator_next(&it);
} while (it.value != NULL &&
(uint32_t)(combine_key(it.key, 0) >> 32) == current_high32);
// Write as uint32 the most significant 32 bits of the bucket.
uint32_t current_high32_le = croaring_htole32(current_high32);
memcpy(buf, ¤t_high32_le, sizeof(current_high32_le));
buf += sizeof(current_high32);
// Write the 32-bit Roaring bitmaps representing the least
// significant bits of a set of elements.
buf += ra_portable_serialize(&bucket, buf);
high32_count++;
}
ra_clear_without_containers(&bucket);
uint64_t high32_count_le = croaring_htole64(high32_count);
memcpy(high32_count_buf, &high32_count_le, sizeof(high32_count_le));
return buf - initial_buf;
}
size_t roaring64_bitmap_portable_deserialize_size(const char *buf,
size_t maxbytes) {
// https://github.com/RoaringBitmap/RoaringFormatSpec#extension-for-64-bit-implementations
if (buf == NULL) {
return 0;
}
size_t read_bytes = 0;
// Read as uint64 the distinct number of "buckets", where a bucket is
// defined as the most significant 32 bits of an element.
uint64_t buckets;
if (read_bytes + sizeof(buckets) > maxbytes) {
return 0;
}
memcpy(&buckets, buf, sizeof(buckets));
buckets = croaring_letoh64(buckets);
buf += sizeof(buckets);
read_bytes += sizeof(buckets);
// Buckets should be 32 bits with 4 bits of zero padding.
if (buckets > UINT32_MAX) {
return 0;
}
// Iterate through buckets ordered by increasing keys.
for (uint64_t bucket = 0; bucket < buckets; ++bucket) {
// Read as uint32 the most significant 32 bits of the bucket.
uint32_t high32;
if (read_bytes + sizeof(high32) > maxbytes) {
return 0;
}
buf += sizeof(high32);
read_bytes += sizeof(high32);
// Read the 32-bit Roaring bitmaps representing the least
// significant bits of a set of elements.
size_t bitmap32_size = roaring_bitmap_portable_deserialize_size(
buf, maxbytes - read_bytes);
if (bitmap32_size == 0) {
return 0;
}
buf += bitmap32_size;
read_bytes += bitmap32_size;
}
return read_bytes;
}
roaring64_bitmap_t *roaring64_bitmap_portable_deserialize_safe(
const char *buf, size_t maxbytes) {
// https://github.com/RoaringBitmap/RoaringFormatSpec#extension-for-64-bit-implementations
if (buf == NULL) {
return NULL;
}
size_t read_bytes = 0;
// Read as uint64 the distinct number of "buckets", where a bucket is
// defined as the most significant 32 bits of an element.
uint64_t buckets;
if (read_bytes + sizeof(buckets) > maxbytes) {
return NULL;
}
memcpy(&buckets, buf, sizeof(buckets));
buckets = croaring_letoh64(buckets);
buf += sizeof(buckets);
read_bytes += sizeof(buckets);
// Buckets should be 32 bits with 4 bits of zero padding.
if (buckets > UINT32_MAX) {
return NULL;
}
roaring64_bitmap_t *r = roaring64_bitmap_create();
// Iterate through buckets ordered by increasing keys.
int64_t previous_high32 = -1;
for (uint64_t bucket = 0; bucket < buckets; ++bucket) {
// Read as uint32 the most significant 32 bits of the bucket.
uint32_t high32;
if (read_bytes + sizeof(high32) > maxbytes) {
roaring64_bitmap_free(r);
return NULL;
}
memcpy(&high32, buf, sizeof(high32));
high32 = croaring_letoh32(high32);
buf += sizeof(high32);
read_bytes += sizeof(high32);
// High 32 bits must be strictly increasing.
if (high32 <= previous_high32) {
roaring64_bitmap_free(r);
return NULL;
}
previous_high32 = high32;
// Read the 32-bit Roaring bitmaps representing the least
// significant bits of a set of elements. ra_portable_deserialize
// already reports bytes consumed, so we do not walk the 32-bit
// format a second time with deserialize_size.
roaring_bitmap_t *bitmap32 =
(roaring_bitmap_t *)roaring_malloc(sizeof(roaring_bitmap_t));
if (bitmap32 == NULL) {
roaring64_bitmap_free(r);
return NULL;
}
size_t bytesread = 0;
bool is_ok = ra_portable_deserialize(&bitmap32->high_low_container, buf,
maxbytes - read_bytes, &bytesread);
if (!is_ok) {
roaring_free(bitmap32);
roaring64_bitmap_free(r);
return NULL;
}
buf += bytesread;
read_bytes += bytesread;
// While we don't attempt to validate much, we must ensure that there
// is no duplication in the high 48 bits - inserting into the ART
// assumes (or UB) no duplicate keys. The top 32 bits must be unique
// because we check for strict increasing values of high32, but we
// must also ensure the top 16 bits within each 32-bit bitmap are also
// at least unique (we ensure they're strictly increasing as well,
// which they must be for a _valid_ bitmap, since it's cheaper to check)
int32_t last_bitmap_key = -1;
for (int i = 0; i < bitmap32->high_low_container.size; i++) {
uint16_t key = bitmap32->high_low_container.keys[i];
if (key <= last_bitmap_key) {
roaring_bitmap_free(bitmap32);
roaring64_bitmap_free(r);
return NULL;
}
last_bitmap_key = key;
}
// Insert all containers of the 32-bit bitmap into the 64-bit bitmap.
move_from_roaring32_offset(r, bitmap32, high32);
roaring_bitmap_free(bitmap32);
}
return r;
}
// Returns an "element count" for the given container. This has a different
// meaning for each container type, but the purpose is the minimal information
// required to serialize the container metadata.
static inline uint32_t container_get_element_count(const container_t *c,
uint8_t typecode) {
switch (typecode) {
case BITSET_CONTAINER_TYPE: {
return ((bitset_container_t *)c)->cardinality;
}
case ARRAY_CONTAINER_TYPE: {
return ((array_container_t *)c)->cardinality;
}
case RUN_CONTAINER_TYPE: {
return ((run_container_t *)c)->n_runs;
}
default: {
assert(false);
roaring_unreachable;
return 0;
}
}
}
static inline size_t container_get_frozen_size(const container_t *c,
uint8_t typecode) {
switch (typecode) {
case BITSET_CONTAINER_TYPE: {
return BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t);
}
case ARRAY_CONTAINER_TYPE: {
return container_get_element_count(c, typecode) * sizeof(uint16_t);
}
case RUN_CONTAINER_TYPE: {
return container_get_element_count(c, typecode) * sizeof(rle16_t);
}
default: {
assert(false);
roaring_unreachable;
return 0;
}
}
}
uint64_t align_size(uint64_t size, uint64_t alignment) {
return (size + alignment - 1) & ~(alignment - 1);
}
size_t roaring64_bitmap_frozen_size_in_bytes(const roaring64_bitmap_t *r) {
if (!is_shrunken(r)) {
return 0;
}
// Flags.
uint64_t size = sizeof(r->flags);
// Container count.
size += sizeof(r->capacity);
// Container element counts.
size += r->capacity * sizeof(uint16_t);
// Total container sizes.
size += 3 * sizeof(uint64_t);
// ART (8 byte aligned).
size = align_size(size, 8);
size += art_size_in_bytes(&r->art);
uint64_t total_sizes[4] =
CROARING_ZERO_INITIALIZER; // Indexed by typecode.
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
uint8_t typecode = get_typecode(leaf);
total_sizes[typecode] +=
container_get_frozen_size(get_container(r, leaf), typecode);
art_iterator_next(&it);
}
// Containers (aligned).
size = align_size(size, CROARING_BITSET_ALIGNMENT);
size += total_sizes[BITSET_CONTAINER_TYPE];
size = align_size(size, alignof(rle16_t));
size += total_sizes[ARRAY_CONTAINER_TYPE];
size = align_size(size, alignof(uint16_t));
size += total_sizes[RUN_CONTAINER_TYPE];
// Padding to make overall size a multiple of required alignment.
size = align_size(size, CROARING_BITSET_ALIGNMENT);
return size;
}
// The output cursors are byte pointers rather than typed pointers: the output
// buffer itself need not be aligned (only `roaring64_bitmap_frozen_view`
// requires alignment), and forming a misaligned typed pointer is undefined
// behavior even if it is only ever passed to memcpy.
static inline void container_frozen_serialize(const container_t *container,
uint8_t typecode, char **bitsets,
char **arrays, char **runs) {
size_t size = container_get_frozen_size(container, typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE: {
bitset_container_t *bitset = (bitset_container_t *)container;
memcpy(*bitsets, bitset->words, size);
*bitsets += size;
break;
}
case ARRAY_CONTAINER_TYPE: {
array_container_t *array = (array_container_t *)container;
memcpy(*arrays, array->array, size);
*arrays += size;
break;
}
case RUN_CONTAINER_TYPE: {
run_container_t *run = (run_container_t *)container;
memcpy(*runs, run->runs, size);
*runs += size;
break;
}
default: {
assert(false);
roaring_unreachable;
}
}
}
static inline char *pad_align(char *buf, const char *initial_buf,
size_t alignment) {
uint64_t buf_size = buf - initial_buf;
uint64_t pad = align_size(buf_size, alignment) - buf_size;
memset(buf, 0, pad);
return buf + pad;
}
size_t roaring64_bitmap_frozen_serialize(const roaring64_bitmap_t *r,
char *buf) {
if (buf == NULL) {
return 0;
}
if (!is_shrunken(r)) {
return 0;
}
const char *initial_buf = buf;
// Flags.
memcpy(buf, &r->flags, sizeof(r->flags));
buf += sizeof(r->flags);
// Container count.
memcpy(buf, &r->capacity, sizeof(r->capacity));
buf += sizeof(r->capacity);
// Container element counts.
uint64_t total_sizes[4] =
CROARING_ZERO_INITIALIZER; // Indexed by typecode.
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
uint8_t typecode = get_typecode(leaf);
container_t *container = get_container(r, leaf);
uint32_t elem_count = container_get_element_count(container, typecode);
uint16_t compressed_elem_count = (uint16_t)(elem_count - 1);
memcpy(buf, &compressed_elem_count, sizeof(compressed_elem_count));
buf += sizeof(compressed_elem_count);
total_sizes[typecode] += container_get_frozen_size(container, typecode);
art_iterator_next(&it);
}
// Total container sizes.
memcpy(buf, &(total_sizes[BITSET_CONTAINER_TYPE]), sizeof(uint64_t));
buf += sizeof(uint64_t);
memcpy(buf, &(total_sizes[RUN_CONTAINER_TYPE]), sizeof(uint64_t));
buf += sizeof(uint64_t);
memcpy(buf, &(total_sizes[ARRAY_CONTAINER_TYPE]), sizeof(uint64_t));
buf += sizeof(uint64_t);
// ART.
buf = pad_align(buf, initial_buf, 8);
buf += art_serialize(&r->art, buf);
// Containers (aligned).
// Runs before arrays as run elements are larger than array elements and
// smaller than bitset elements.
buf = pad_align(buf, initial_buf, CROARING_BITSET_ALIGNMENT);
char *bitsets = buf;
buf += total_sizes[BITSET_CONTAINER_TYPE];
buf = pad_align(buf, initial_buf, alignof(rle16_t));
char *runs = buf;
buf += total_sizes[RUN_CONTAINER_TYPE];
buf = pad_align(buf, initial_buf, alignof(uint16_t));
char *arrays = buf;
buf += total_sizes[ARRAY_CONTAINER_TYPE];
it = art_init_iterator((art_t *)&r->art, /*first=*/true);
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
uint8_t typecode = get_typecode(leaf);
container_t *container = get_container(r, leaf);
container_frozen_serialize(container, typecode, &bitsets, &arrays,
&runs);
art_iterator_next(&it);
}
// Padding to make overall size a multiple of required alignment.
buf = pad_align(buf, initial_buf, CROARING_BITSET_ALIGNMENT);
return buf - initial_buf;
}
static roaring64_bitmap_t *alloc_frozen_bitmap(
uint64_t capacity, frozen_container_header_t **headers_out) {
if (capacity > SIZE_MAX / sizeof(frozen_container_header_t)) {
return NULL;
}
size_t ptrs = (size_t)capacity * sizeof(container_t *);
size_t codes = (size_t)capacity * sizeof(uint8_t);
size_t headers = (size_t)capacity * sizeof(frozen_container_header_t);
size_t pad = alignof(container_t *) + alignof(frozen_container_header_t);
if (sizeof(roaring64_bitmap_t) > SIZE_MAX - ptrs ||
sizeof(roaring64_bitmap_t) + ptrs > SIZE_MAX - codes ||
sizeof(roaring64_bitmap_t) + ptrs + codes > SIZE_MAX - headers ||
sizeof(roaring64_bitmap_t) + ptrs + codes + headers > SIZE_MAX - pad) {
return NULL;
}
size_t sz = sizeof(roaring64_bitmap_t) + ptrs + codes + headers + pad;
char *base = (char *)roaring_malloc(sz);
if (base == NULL) {
return NULL;
}
char *cursor = base;
roaring64_bitmap_t *r = (roaring64_bitmap_t *)roaring64_arena_alloc(
&cursor, sizeof(roaring64_bitmap_t));
art_init_cleared(&r->art);
r->flags = ROARING_FLAG_FROZEN;
r->capacity = capacity;
r->first_free = 0;
r->end = 0;
r->holes = NULL;
r->num_holes = 0;
r->holes_capacity = 0;
cursor = roaring64_arena_pad(cursor, base, alignof(container_t *));
if (capacity == 0) {
r->containers = NULL;
r->typecodes = NULL;
if (headers_out != NULL) {
*headers_out = NULL;
}
return r;
}
r->containers = (container_t **)roaring64_arena_alloc(&cursor, ptrs);
memset(r->containers, 0, ptrs);
r->typecodes = (uint8_t *)roaring64_arena_alloc(&cursor, codes);
cursor =
roaring64_arena_pad(cursor, base, alignof(frozen_container_header_t));
frozen_container_header_t *hdrs =
(frozen_container_header_t *)roaring64_arena_alloc(&cursor, headers);
if (headers_out != NULL) {
*headers_out = hdrs;
}
return r;
}
static container_t *container_frozen_view_at(
frozen_container_header_t *header, uint8_t typecode, uint32_t elem_count,
const uint64_t **bitsets, const uint16_t **arrays, const rle16_t **runs) {
switch (typecode) {
case BITSET_CONTAINER_TYPE: {
bitset_container_t *c = &header->bitset;
c->cardinality = elem_count;
c->words = (uint64_t *)*bitsets;
*bitsets += BITSET_CONTAINER_SIZE_IN_WORDS;
return (container_t *)c;
}
case ARRAY_CONTAINER_TYPE: {
array_container_t *c = &header->array;
c->cardinality = elem_count;
c->capacity = elem_count;
c->array = (uint16_t *)*arrays;
*arrays += elem_count;
return (container_t *)c;
}
case RUN_CONTAINER_TYPE: {
run_container_t *c = &header->run;
c->n_runs = elem_count;
c->capacity = elem_count;
c->runs = (rle16_t *)*runs;
*runs += elem_count;
return (container_t *)c;
}
default:
return NULL;
}
}
roaring64_bitmap_t *roaring64_bitmap_frozen_view(const char *buf,
size_t maxbytes) {
if (buf == NULL) {
return NULL;
}
if ((uintptr_t)buf % CROARING_BITSET_ALIGNMENT != 0) {
return NULL;
}
uint8_t flags;
uint64_t capacity;
if (maxbytes < sizeof(flags) + sizeof(capacity)) {
return NULL;
}
memcpy(&flags, buf, sizeof(flags));
buf += sizeof(flags);
maxbytes -= sizeof(flags);
memcpy(&capacity, buf, sizeof(capacity));
buf += sizeof(capacity);
maxbytes -= sizeof(capacity);
// The element counts alone need two bytes per container, so a capacity
// larger than that cannot be satisfied by this buffer. Checked before
// allocating, so a short buffer claiming a huge count cannot make us
// reserve (and clear) an arena sized from attacker-controlled bytes.
if (capacity > maxbytes / sizeof(uint16_t)) {
return NULL;
}
frozen_container_header_t *headers = NULL;
roaring64_bitmap_t *r = alloc_frozen_bitmap(capacity, &headers);
if (r == NULL) {
return NULL;
}
// Only flags the format actually defines; the byte comes from the buffer.
r->flags = (uint8_t)(flags & ROARING_FLAG_COW) | ROARING_FLAG_FROZEN |
ROARING_FLAG_FROZEN_ART;
// Container element counts.
if (maxbytes < capacity * sizeof(uint16_t)) {
roaring64_bitmap_free(r);
return NULL;
}
const char *elem_counts = buf;
buf += capacity * sizeof(uint16_t);
maxbytes -= capacity * sizeof(uint16_t);
// Total container sizes.
uint64_t total_sizes[4];
if (maxbytes < sizeof(uint64_t) * 3) {
roaring64_bitmap_free(r);
return NULL;
}
memcpy(&(total_sizes[BITSET_CONTAINER_TYPE]), buf, sizeof(uint64_t));
buf += sizeof(uint64_t);
maxbytes -= sizeof(uint64_t);
memcpy(&(total_sizes[RUN_CONTAINER_TYPE]), buf, sizeof(uint64_t));
buf += sizeof(uint64_t);
maxbytes -= sizeof(uint64_t);
memcpy(&(total_sizes[ARRAY_CONTAINER_TYPE]), buf, sizeof(uint64_t));
buf += sizeof(uint64_t);
maxbytes -= sizeof(uint64_t);
// ART (8 byte aligned).
buf = CROARING_ALIGN_BUF(buf, 8);
size_t art_size = art_frozen_view(buf, maxbytes, &r->art);
if (art_size == 0) {
roaring64_bitmap_free(r);
return NULL;
}
buf += art_size;
maxbytes -= art_size;
// Containers (aligned).
const char *before_containers = buf;
buf = CROARING_ALIGN_BUF(buf, CROARING_BITSET_ALIGNMENT);
const uint64_t *bitsets = (const uint64_t *)buf;
buf += total_sizes[BITSET_CONTAINER_TYPE];
buf = CROARING_ALIGN_BUF(buf, alignof(rle16_t));
const rle16_t *runs = (const rle16_t *)buf;
buf += total_sizes[RUN_CONTAINER_TYPE];
buf = CROARING_ALIGN_BUF(buf, alignof(uint16_t));
const uint16_t *arrays = (const uint16_t *)buf;
buf += total_sizes[ARRAY_CONTAINER_TYPE];
if (maxbytes < (uint64_t)(buf - before_containers)) {
roaring64_bitmap_free(r);
return NULL;
}
maxbytes -= buf - before_containers;
// Deserialize in ART iteration order.
art_iterator_t it = art_init_iterator(&r->art, /*first=*/true);
for (size_t i = 0; it.value != NULL; ++i) {
if (i >= capacity) {
roaring64_bitmap_free(r);
return NULL;
}
leaf_t leaf = (leaf_t)*it.value;
uint8_t typecode = get_typecode(leaf);
uint16_t compressed_elem_count;
memcpy(&compressed_elem_count, elem_counts + (i * sizeof(uint16_t)),
sizeof(compressed_elem_count));
uint32_t elem_count = (uint32_t)(compressed_elem_count) + 1;
// The container index is unrelated to the iteration order.
uint64_t index = get_index(leaf);
if (index >= capacity) {
roaring64_bitmap_free(r);
return NULL;
}
container_t *c = container_frozen_view_at(
headers + index, typecode, elem_count, &bitsets, &arrays, &runs);
if (c == NULL) {
roaring64_bitmap_free(r);
return NULL;
}
set_container_at(r, index, c, typecode);
art_iterator_next(&it);
}
// Padding to make overall size a multiple of required alignment.
buf = CROARING_ALIGN_BUF(buf, CROARING_BITSET_ALIGNMENT);
// A frozen view is read-only: mark every slot as taken.
r->first_free = r->capacity;
r->end = r->capacity;
return r;
}
#if !CROARING_IS_BIG_ENDIAN
// Only used by roaring64_bitmap_portable_deserialize_frozen, which refuses to
// run on big-endian systems.
static bool view_one_portable32(roaring64_bitmap_t *r,
frozen_container_header_t *headers,
uint32_t high32, const char *buf,
size_t maxbytes, size_t *consumed) {
*consumed = roaring_bitmap_portable_deserialize_size(buf, maxbytes);
if (*consumed == 0 || *consumed > maxbytes) {
return false;
}
const char *start = buf;
size_t remaining = *consumed;
uint32_t cookie;
memcpy(&cookie, buf, sizeof(cookie));
cookie = croaring_letoh32(cookie);
buf += sizeof(cookie);
remaining -= sizeof(cookie);
int32_t num_containers;
const char *run_flag_bitset = NULL;
bool hasrun = false;
bool has_offsets;
if (cookie == SERIAL_COOKIE_NO_RUNCONTAINER) {
if (remaining < sizeof(uint32_t)) {
return false;
}
uint32_t n_le;
memcpy(&n_le, buf, sizeof(n_le));
num_containers = (int32_t)croaring_letoh32(n_le);
buf += sizeof(uint32_t);
remaining -= sizeof(uint32_t);
has_offsets = true;
} else if ((cookie & 0xFFFF) == SERIAL_COOKIE) {
num_containers = (int32_t)(cookie >> 16) + 1;
hasrun = true;
int32_t run_flag_bitset_size = (num_containers + 7) / 8;
if (num_containers < 0 || remaining < (size_t)run_flag_bitset_size) {
return false;
}
run_flag_bitset = buf;
buf += run_flag_bitset_size;
remaining -= (size_t)run_flag_bitset_size;
has_offsets = num_containers >= NO_OFFSET_THRESHOLD;
} else {
return false;
}
if (num_containers < 0 || num_containers > (1 << 16)) {
return false;
}
size_t desc_bytes = (size_t)num_containers * 2 * sizeof(uint16_t);
if (remaining < desc_bytes) {
return false;
}
const char *keyscards = buf;
buf += desc_bytes;
remaining -= desc_bytes;
const char *offset_bytes = NULL;
if (has_offsets) {
size_t off_bytes = (size_t)num_containers * sizeof(uint32_t);
if (remaining < off_bytes) {
return false;
}
offset_bytes = buf;
buf += off_bytes;
remaining -= off_bytes;
}
int32_t last_key = -1;
uint64_t key_base = ((uint64_t)high32) << 32;
for (int32_t i = 0; i < num_containers; ++i) {
uint16_t key, card_m1;
memcpy(&key, keyscards + 4 * (size_t)i, sizeof(key));
key = croaring_letoh16(key);
memcpy(&card_m1, keyscards + 4 * (size_t)i + 2, sizeof(card_m1));
card_m1 = croaring_letoh16(card_m1);
if ((int32_t)key <= last_key) {
return false;
}
last_key = (int32_t)key;
uint32_t cardinality = (uint32_t)card_m1 + 1;
bool isbitmap = cardinality > DEFAULT_MAX_SIZE;
bool isrun = false;
if (hasrun && (run_flag_bitset[i / 8] & (1 << (i % 8))) != 0) {
isbitmap = false;
isrun = true;
}
const char *payload;
if (offset_bytes != NULL) {
uint32_t off;
memcpy(&off, offset_bytes + (size_t)i * sizeof(uint32_t),
sizeof(off));
off = croaring_letoh32(off);
if ((size_t)off >= *consumed) {
return false;
}
payload = start + off;
} else {
payload = buf;
}
uint8_t typecode;
size_t payload_size;
if (isbitmap) {
typecode = BITSET_CONTAINER_TYPE;
payload_size = BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t);
} else if (isrun) {
typecode = RUN_CONTAINER_TYPE;
if ((size_t)(payload - start) + sizeof(uint16_t) > *consumed) {
return false;
}
uint16_t n_runs;
memcpy(&n_runs, payload, sizeof(n_runs));
n_runs = croaring_letoh16(n_runs);
payload_size = sizeof(uint16_t) + (size_t)n_runs * sizeof(rle16_t);
} else {
typecode = ARRAY_CONTAINER_TYPE;
payload_size = (size_t)cardinality * sizeof(uint16_t);
}
if ((size_t)(payload - start) + payload_size > *consumed) {
return false;
}
if (r->first_free >= r->capacity) {
return false;
}
uint64_t index = allocate_index(r);
frozen_container_header_t *header = headers + index;
container_t *c;
if (isbitmap) {
header->bitset.cardinality = (int32_t)cardinality;
header->bitset.words = (uint64_t *)payload;
c = (container_t *)&header->bitset;
} else if (isrun) {
uint16_t n_runs;
memcpy(&n_runs, payload, sizeof(n_runs));
n_runs = croaring_letoh16(n_runs);
header->run.n_runs = n_runs;
header->run.capacity = n_runs;
header->run.runs = (rle16_t *)(payload + sizeof(uint16_t));
c = (container_t *)&header->run;
} else {
header->array.cardinality = (int32_t)cardinality;
header->array.capacity = (int32_t)cardinality;
header->array.array = (uint16_t *)payload;
c = (container_t *)&header->array;
}
set_container_at(r, index, c, typecode);
uint8_t high48[ART_KEY_BYTES];
uint64_t high48_bits = key_base | ((uint64_t)key << 16);
split_key(high48_bits, high48);
art_insert(&r->art, high48, (art_val_t)create_leaf(index, typecode));
if (offset_bytes == NULL) {
buf += payload_size;
remaining -= payload_size;
}
}
return true;
}
#endif // !CROARING_IS_BIG_ENDIAN
CROARING_ALLOW_UNALIGNED
roaring64_bitmap_t *roaring64_bitmap_portable_deserialize_frozen(
const char *buf, size_t maxbytes) {
if (buf == NULL) {
return NULL;
}
#if CROARING_IS_BIG_ENDIAN
// The portable format is little-endian and this function uses the payload
// bytes where they sit, so there is no correct view of them here. Refuse
// rather than hand back a bitmap that silently reads byte-swapped values.
(void)maxbytes;
return NULL;
#else
size_t remaining = maxbytes;
if (remaining < sizeof(uint64_t)) {
return NULL;
}
uint64_t buckets;
memcpy(&buckets, buf, sizeof(buckets));
buckets = croaring_letoh64(buckets);
buf += sizeof(buckets);
remaining -= sizeof(buckets);
if (buckets > UINT32_MAX) {
return NULL;
}
uint64_t ncontainers = 0;
const char *count_buf = buf;
size_t count_remaining = remaining;
int64_t previous_high32 = -1;
for (uint64_t bucket = 0; bucket < buckets; ++bucket) {
if (count_remaining < sizeof(uint32_t)) {
return NULL;
}
uint32_t high32;
memcpy(&high32, count_buf, sizeof(high32));
high32 = croaring_letoh32(high32);
count_buf += sizeof(high32);
count_remaining -= sizeof(high32);
if (high32 <= previous_high32) {
return NULL;
}
previous_high32 = high32;
size_t bitmap32_size = roaring_bitmap_portable_deserialize_size(
count_buf, count_remaining);
if (bitmap32_size == 0) {
return NULL;
}
uint32_t cookie;
if (count_remaining < sizeof(cookie)) {
return NULL;
}
memcpy(&cookie, count_buf, sizeof(cookie));
cookie = croaring_letoh32(cookie);
int32_t size;
if ((cookie & 0xFFFF) == SERIAL_COOKIE) {
size = (int32_t)(cookie >> 16) + 1;
} else if (cookie == SERIAL_COOKIE_NO_RUNCONTAINER) {
if (count_remaining < 2 * sizeof(uint32_t)) {
return NULL;
}
uint32_t size_le;
memcpy(&size_le, count_buf + sizeof(uint32_t), sizeof(size_le));
size = (int32_t)croaring_letoh32(size_le);
} else {
return NULL;
}
if (size < 0) {
return NULL;
}
ncontainers += (uint64_t)size;
count_buf += bitmap32_size;
count_remaining -= bitmap32_size;
}
frozen_container_header_t *headers = NULL;
roaring64_bitmap_t *r = alloc_frozen_bitmap(ncontainers, &headers);
if (r == NULL) {
return NULL;
}
// ART is owned; payloads alias buf.
r->flags = ROARING_FLAG_FROZEN;
previous_high32 = -1;
for (uint64_t bucket = 0; bucket < buckets; ++bucket) {
if (remaining < sizeof(uint32_t)) {
roaring64_bitmap_free(r);
return NULL;
}
uint32_t high32;
memcpy(&high32, buf, sizeof(high32));
high32 = croaring_letoh32(high32);
buf += sizeof(high32);
remaining -= sizeof(high32);
if (high32 <= previous_high32) {
roaring64_bitmap_free(r);
return NULL;
}
previous_high32 = high32;
size_t consumed = 0;
if (!view_one_portable32(r, headers, high32, buf, remaining,
&consumed)) {
roaring64_bitmap_free(r);
return NULL;
}
buf += consumed;
remaining -= consumed;
}
return r;
#endif
}
bool roaring64_bitmap_iterate(const roaring64_bitmap_t *r,
roaring_iterator64 iterator, void *ptr) {
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
while (it.value != NULL) {
uint64_t high48 = combine_key(it.key, 0);
uint64_t high32 = high48 & 0xFFFFFFFF00000000ULL;
uint32_t low32 = high48;
leaf_t leaf = (leaf_t)*it.value;
if (!container_iterate64(get_container(r, leaf), get_typecode(leaf),
low32, iterator, high32, ptr)) {
return false;
}
art_iterator_next(&it);
}
return true;
}
// Whether bitset_container_to_uint32_array picks a vectorized decoder for
// `bc` (keep in sync with it). Only then does decoding to 32 bits and widening
// beat decoding directly to 64 bits.
static inline bool roaring64_bitset_decodes_vectorized(
const bitset_container_t *bc) {
#if CROARING_IS_X64
int support = croaring_hardware_support();
#if CROARING_COMPILER_SUPPORTS_AVX512
if (support & ROARING_SUPPORTS_AVX512) {
return true;
}
#endif
return (support & ROARING_SUPPORTS_AVX2) && bc->cardinality >= 8192;
#else
(void)bc;
return false;
#endif
}
// The containers of a portable frozen view may be unaligned: see
// roaring64_bitmap_portable_deserialize_frozen.
CROARING_ALLOW_UNALIGNED
static uint64_t *roaring64_bitset_to_uint64_array(const bitset_container_t *bc,
uint64_t high48,
uint64_t *out) {
for (int32_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; ++i) {
uint64_t w = bc->words[i];
uint64_t base = high48 + (uint64_t)i * 64;
while (w != 0) {
*out++ = base + roaring_trailing_zeroes(w);
w &= w - 1;
}
}
return out;
}
static void roaring64_bitmap_to_uint64_array_iterator(
const roaring64_bitmap_t *r, uint64_t *out) {
roaring64_iterator_t it; // gets initialized in the next line
roaring64_iterator_init_at(r, &it, /*first=*/true);
roaring64_iterator_read(&it, out, UINT64_MAX);
}
CROARING_ALLOW_UNALIGNED
void roaring64_bitmap_to_uint64_array(const roaring64_bitmap_t *r,
uint64_t *out) {
// Where vectorized 32-bit bitset decoders are available, decoding into a
// scratch buffer and widening is several times faster than decoding value
// by value.
uint64_t *const start = out;
uint32_t *scratch = NULL;
art_iterator_t it = art_init_iterator((art_t *)&r->art, /*first=*/true);
while (it.value != NULL) {
leaf_t leaf = (leaf_t)*it.value;
uint64_t high48 = combine_key(it.key, 0);
uint8_t typecode = get_typecode(leaf);
const container_t *c = get_container(r, leaf);
switch (typecode) {
case BITSET_CONTAINER_TYPE: {
const bitset_container_t *bc = const_CAST_bitset(c);
if (!roaring64_bitset_decodes_vectorized(bc)) {
out = roaring64_bitset_to_uint64_array(bc, high48, out);
break;
}
if (scratch == NULL) {
scratch = (uint32_t *)roaring_malloc((1 << 16) *
sizeof(uint32_t));
if (scratch == NULL) {
roaring64_bitmap_to_uint64_array_iterator(r, start);
return;
}
}
int n = bitset_container_to_uint32_array(scratch, bc, 0);
for (int i = 0; i < n; ++i) {
out[i] = high48 | scratch[i];
}
out += n;
break;
}
case ARRAY_CONTAINER_TYPE: {
const array_container_t *ac = const_CAST_array(c);
for (int32_t i = 0; i < ac->cardinality; ++i) {
out[i] = high48 | ac->array[i];
}
out += ac->cardinality;
break;
}
case RUN_CONTAINER_TYPE: {
const run_container_t *rc = const_CAST_run(c);
for (int32_t i = 0; i < rc->n_runs; ++i) {
uint64_t value = high48 | rc->runs[i].value;
for (uint32_t j = 0; j <= rc->runs[i].length; ++j) {
*out++ = value + j;
}
}
break;
}
default:
assert(false);
roaring_unreachable;
}
art_iterator_next(&it);
}
roaring_free(scratch);
}
roaring64_iterator_t *roaring64_iterator_create(const roaring64_bitmap_t *r) {
roaring64_iterator_t *it =
(roaring64_iterator_t *)roaring_malloc(sizeof(roaring64_iterator_t));
return roaring64_iterator_init_at(r, it, /*first=*/true);
}
roaring64_iterator_t *roaring64_iterator_create_last(
const roaring64_bitmap_t *r) {
roaring64_iterator_t *it =
(roaring64_iterator_t *)roaring_malloc(sizeof(roaring64_iterator_t));
return roaring64_iterator_init_at(r, it, /*first=*/false);
}
void roaring64_iterator_reinit(const roaring64_bitmap_t *r,
roaring64_iterator_t *it) {
roaring64_iterator_init_at(r, it, /*first=*/true);
}
void roaring64_iterator_reinit_last(const roaring64_bitmap_t *r,
roaring64_iterator_t *it) {
roaring64_iterator_init_at(r, it, /*first=*/false);
}
roaring64_iterator_t *roaring64_iterator_copy(const roaring64_iterator_t *it) {
roaring64_iterator_t *new_it =
(roaring64_iterator_t *)roaring_malloc(sizeof(roaring64_iterator_t));
memcpy(new_it, it, sizeof(*it));
return new_it;
}
void roaring64_iterator_free(roaring64_iterator_t *it) { roaring_free(it); }
CROARING_STATIC_ASSERT(offsetof(roaring64_iterator_t, pub) == 0,
"the public members must be first in the iterator");
extern inline bool roaring64_iterator_has_value(const roaring64_iterator_t *it);
extern inline uint64_t roaring64_iterator_value(const roaring64_iterator_t *it);
// The current container is exhausted: step the ART to the next leaf.
static inline bool roaring64_iterator_next_leaf(roaring64_iterator_t *it) {
if (art_iterator_next(&it->art_it)) {
return roaring64_iterator_init_at_leaf_first(it);
}
it->saturated_forward = true;
it->fast_type = 0;
return (it->pub.has_value = false);
}
// Everything `advance` needs when the bitset cache does not describe where the
// iterator is: a restart, or a step through the container iterator.
static inline bool roaring64_iterator_advance_slow(roaring64_iterator_t *it) {
if (it->art_it.value == NULL) {
if (it->saturated_forward) {
return (it->pub.has_value = false);
}
roaring64_iterator_init_at(it->r, it, /*first=*/true);
return it->pub.has_value;
}
leaf_t leaf = (leaf_t)*it->art_it.value;
uint8_t typecode = get_typecode(leaf);
uint16_t low16 = (uint16_t)it->pub.value;
if (container_iterator_next(get_container(it->r, leaf), typecode,
&it->container_it, &low16)) {
it->pub.value = it->high48 | low16;
it->pub.has_value = true;
if (typecode == BITSET_CONTAINER_TYPE) {
// Only reached when the cache was stale, i.e. something else moved
// the cursor. Array and run containers never have a cache, and
// priming them would cost a leaf load per value.
roaring64_iterator_prime(it);
}
return true;
}
return roaring64_iterator_next_leaf(it);
}
bool roaring64_iterator_advance(roaring64_iterator_t *it) {
// Matching both the leaf and `container_it.index` is enough to know the
// cache describes where the iterator actually is: within a container the
// index determines the position. Anything that moved the cursor --
// `previous`, `move_equalorlarger`, any of the `read` variants -- moved one
// of them, and drops through to the slow path, which rebuilds the cache.
if (it->fast_type != 0 && it->fast_art_value == it->art_it.value &&
it->fast_index == it->container_it.index) {
uint64_t word = it->fast_word;
uint32_t wi = it->fast_wordindex;
while (word == 0) {
if (++wi >= BITSET_CONTAINER_SIZE_IN_WORDS) {
return roaring64_iterator_next_leaf(it);
}
word = it->fast_words[wi];
it->fast_wordindex = wi;
}
uint32_t index = wi * 64 + (uint32_t)roaring_trailing_zeroes(word);
it->fast_word = word & (word - 1);
it->fast_index = (int32_t)index;
it->container_it.index = (int32_t)index;
it->pub.value = it->high48 | index;
return (it->pub.has_value = true);
}
return roaring64_iterator_advance_slow(it);
}
bool roaring64_iterator_previous(roaring64_iterator_t *it) {
if (it->art_it.value == NULL) {
if (!it->saturated_forward) {
// Saturated backward.
return (it->pub.has_value = false);
}
roaring64_iterator_init_at(it->r, it, /*first=*/false);
return it->pub.has_value;
}
leaf_t leaf = (leaf_t)*it->art_it.value;
uint16_t low16 = (uint16_t)it->pub.value;
if (container_iterator_prev(get_container(it->r, leaf), get_typecode(leaf),
&it->container_it, &low16)) {
it->pub.value = it->high48 | low16;
it->pub.has_value = true;
it->fast_type = 0;
return true;
}
if (art_iterator_prev(&it->art_it)) {
return roaring64_iterator_init_at_leaf_last(it);
}
it->saturated_forward = false; // Saturated backward.
it->fast_type = 0;
return (it->pub.has_value = false);
}
bool roaring64_iterator_move_equalorlarger(roaring64_iterator_t *it,
uint64_t val) {
uint8_t val_high48[ART_KEY_BYTES];
uint16_t val_low16 = split_key(val, val_high48);
if (!it->pub.has_value || it->high48 != (val & 0xFFFFFFFFFFFF0000)) {
// The ART iterator is before or after the high48 bits of `val` (or
// beyond the ART altogether), so we need to move to a leaf with a
// key equal or greater.
if (!art_iterator_lower_bound(&it->art_it, val_high48)) {
// Only smaller keys found.
it->saturated_forward = true;
it->fast_type = 0;
return (it->pub.has_value = false);
}
it->high48 = combine_key(it->art_it.key, 0);
// Fall through to the next if statement.
}
if (it->high48 == (val & 0xFFFFFFFFFFFF0000)) {
// We're at equal high bits, check if a suitable value can be found
// in this container.
leaf_t leaf = (leaf_t)*it->art_it.value;
uint16_t low16 = (uint16_t)it->pub.value;
if (container_iterator_lower_bound(
get_container(it->r, leaf), get_typecode(leaf),
&it->container_it, &low16, val_low16)) {
it->pub.value = it->high48 | low16;
it->pub.has_value = true;
it->fast_type = 0;
return true;
}
// Only smaller entries in this container, move to the next.
if (!art_iterator_next(&it->art_it)) {
it->saturated_forward = true;
it->fast_type = 0;
return (it->pub.has_value = false);
}
}
// We're at a leaf with high bits greater than `val`, so the first entry
// in this container is our result.
return roaring64_iterator_init_at_leaf_first(it);
}
uint64_t roaring64_iterator_read(roaring64_iterator_t *it, uint64_t *buf,
uint64_t count) {
uint64_t consumed = 0;
while (it->pub.has_value && consumed < count) {
uint32_t container_consumed;
leaf_t leaf = (leaf_t)*it->art_it.value;
uint16_t low16 = (uint16_t)it->pub.value;
uint32_t container_count = UINT32_MAX;
if (count - consumed < (uint64_t)UINT32_MAX) {
container_count = count - consumed;
}
bool has_value = container_iterator_read_into_uint64(
get_container(it->r, leaf), get_typecode(leaf), &it->container_it,
it->high48, buf, container_count, &container_consumed, &low16);
consumed += container_consumed;
buf += container_consumed;
if (has_value) {
it->pub.has_value = true;
it->pub.value = it->high48 | low16;
it->fast_type = 0;
assert(consumed == count);
return consumed;
}
it->pub.has_value = art_iterator_next(&it->art_it);
if (it->pub.has_value) {
roaring64_iterator_init_at_leaf_first(it);
} else {
it->saturated_forward = true;
it->fast_type = 0;
}
}
return consumed;
}
uint64_t roaring64_iterator_read_backward(roaring64_iterator_t *it,
uint64_t *buf, uint64_t count) {
uint64_t consumed = 0;
while (it->pub.has_value && consumed < count) {
uint32_t container_consumed;
leaf_t leaf = *it->art_it.value;
uint16_t low16 = (uint16_t)it->pub.value;
uint32_t container_count = UINT32_MAX;
if (count - consumed < (uint64_t)UINT32_MAX) {
container_count = count - consumed;
}
bool has_value = container_iterator_read_backward_into_uint64(
get_container(it->r, leaf), get_typecode(leaf), &it->container_it,
it->high48, buf, container_count, &container_consumed, &low16);
consumed += container_consumed;
buf += container_consumed;
if (has_value) {
it->pub.has_value = true;
it->pub.value = it->high48 | low16;
assert(consumed == count);
return consumed;
}
it->pub.has_value = art_iterator_prev(&it->art_it);
if (it->pub.has_value) {
roaring64_iterator_init_at_leaf_last(it);
} else {
it->saturated_forward = false;
}
}
return consumed;
}
size_t roaring64_iterator_read_ranges(roaring64_iterator_t *it,
roaring64_range_closed_t *buf,
size_t count) {
size_t ret = 0;
while (it->pub.has_value && ret < count) {
buf[ret].min = it->pub.value;
for (;;) {
uint16_t low16 = (uint16_t)it->pub.value;
leaf_t leaf = (leaf_t)*it->art_it.value;
bool container_has_more;
uint16_t run_end_low16 = container_iterator_find_run_end(
get_container(it->r, leaf), get_typecode(leaf),
&it->container_it, &low16, &container_has_more);
buf[ret].max = it->high48 | run_end_low16;
if (container_has_more) {
it->pub.value = it->high48 | low16;
break;
}
// Move to next leaf
it->pub.has_value = art_iterator_next(&it->art_it);
if (it->pub.has_value) {
roaring64_iterator_init_at_leaf_first(it);
} else {
it->saturated_forward = true;
break;
}
// Continue merging only if the run reached the container
// boundary and the next leaf starts exactly at max+1.
if (run_end_low16 != UINT16_MAX ||
it->pub.value != buf[ret].max + 1) {
break;
}
}
ret++;
}
return ret;
}
size_t roaring64_iterator_read_prev_ranges(roaring64_iterator_t *it,
roaring64_range_closed_t *buf,
size_t count) {
size_t ret = 0;
while (it->pub.has_value && ret < count) {
buf[ret].max = it->pub.value;
for (;;) {
uint16_t low16 = (uint16_t)it->pub.value;
leaf_t leaf = (leaf_t)*it->art_it.value;
bool container_has_more;
uint16_t run_start_low16 = container_iterator_find_run_start(
get_container(it->r, leaf), get_typecode(leaf),
&it->container_it, &low16, &container_has_more);
buf[ret].min = it->high48 | run_start_low16;
if (container_has_more) {
it->pub.value = it->high48 | low16;
break;
}
// Move to previous leaf
it->pub.has_value = art_iterator_prev(&it->art_it);
if (it->pub.has_value) {
roaring64_iterator_init_at_leaf_last(it);
} else {
it->saturated_forward = false;
break;
}
// Continue merging only if the run reached the container
// boundary and the previous leaf ends exactly at min-1.
if (run_start_low16 != 0 || it->pub.value != buf[ret].min - 1) {
break;
}
}
ret++;
}
return ret;
}
#ifdef __cplusplus
} // extern "C"
} // namespace roaring
} // namespace api
#endif