- Generated by
1.9.1
|
CRoaring
4.2.1
Roaring bitmaps in C (and C++)
|
#include <stdbool.h>#include <stddef.h>#include <stdint.h>#include <roaring/roaring_types.h>#include <roaring/bitset/bitset.h>#include <roaring/memory.h>#include <roaring/portability.h>#include <roaring/roaring_version.h>#include <roaring/roaring64.h>Go to the source code of this file.
Classes | |
| struct | roaring_bitmap_s |
| struct | roaring_bulk_context_s |
| struct | roaring_uint32_iterator_s |
Macros | |
| #define | roaring_bitmap_from(...) |
Typedefs | |
| typedef struct roaring_bitmap_s | roaring_bitmap_t |
| typedef struct roaring_bulk_context_s | roaring_bulk_context_t |
| typedef struct roaring_uint32_iterator_s | roaring_uint32_iterator_t |
| #define roaring_bitmap_from | ( | ... | ) |
Creates a new bitmap which contains all values passed in as arguments.
To create a bitmap from a variable number of arguments, use the roaring_bitmap_of_ptr function instead.
| typedef struct roaring_bitmap_s roaring_bitmap_t |
| typedef struct roaring_bulk_context_s roaring_bulk_context_t |
A bit of context usable with roaring_bitmap_*_bulk() functions
Should be initialized with {0} (or memset() to all zeros). Callers should treat it as an opaque type.
A context may only be used with a single bitmap (unless re-initialized to zero), and any modification to a bitmap (other than modifications performed with _bulk() functions with the context passed) will invalidate any contexts associated with that bitmap.
| typedef struct roaring_uint32_iterator_s roaring_uint32_iterator_t |
What follows is code use to iterate through values in a roaring bitmap
roaring_bitmap_t *r =... roaring_uint32_iterator_t i; roaring_iterator_create(r, &i); while(i.has_value) { printf("value = %d\n", i.current_value); roaring_uint32_iterator_advance(&i); }
Obviously, if you modify the underlying bitmap, the iterator becomes invalid. So don't. A struct used to keep iterator state. Users should only access current_value and has_value, the rest of the type should be treated as opaque.
|
inlinestatic |
DEPRECATED, use roaring_uint32_iterator_advance.
Definition at line 1084 of file roaring.h.
References roaring_uint32_iterator_advance().
| void roaring_bitmap_add | ( | roaring_bitmap_t * | r, |
| uint32_t | x | ||
| ) |
Add value x
Referenced by roaring::Roaring::add().
| void roaring_bitmap_add_bulk | ( | roaring_bitmap_t * | r, |
| roaring_bulk_context_t * | context, | ||
| uint32_t | val | ||
| ) |
Add an item, using context from a previous insert for speed optimization.
context will be used to store information between calls to make bulk operations faster. *context should be zero-initialized before the first call to this function.
Modifying the bitmap in any way (other than -bulk suffixed functions) will invalidate the stored context, calling this function with a non-zero context after doing any modification invokes undefined behavior.
In order to exploit this optimization, the caller should call this function with values with the same "key" (high 16 bits of the value) consecutively.
Referenced by roaring::Roaring::addBulk().
| bool roaring_bitmap_add_checked | ( | roaring_bitmap_t * | r, |
| uint32_t | x | ||
| ) |
Add value x Returns true if a new value was added, false if the value already existed.
Referenced by roaring::Roaring::addChecked().
| void roaring_bitmap_add_many | ( | roaring_bitmap_t * | r, |
| size_t | n_args, | ||
| const uint32_t * | vals | ||
| ) |
Add value n_args from pointer vals, faster than repeatedly calling roaring_bitmap_add()
In order to exploit this optimization, the caller should attempt to keep values with the same "key" (high 16 bits of the value) as consecutive elements in vals
Referenced by roaring::Roaring::addMany(), and roaring::Roaring::Roaring().
| roaring_bitmap_t* roaring_bitmap_add_offset | ( | const roaring_bitmap_t * | bm, |
| int64_t | offset | ||
| ) |
|
inline |
Add all values in range [min, max)
Definition at line 388 of file roaring.h.
References roaring_bitmap_add_range_closed().
Referenced by roaring::Roaring::addRange().
| void roaring_bitmap_add_range_closed | ( | roaring_bitmap_t * | r, |
| uint32_t | min, | ||
| uint32_t | max | ||
| ) |
Add all values in range [min, max]
Referenced by roaring::Roaring::addRangeClosed(), and roaring_bitmap_add_range().
| roaring_bitmap_t* roaring_bitmap_and | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Computes the intersection between two bitmaps and returns new bitmap. The caller is responsible for memory management.
Performance hint: if you are computing the intersection between several bitmaps, two-by-two, it is best to start with the smallest bitmap. You may also rely on roaring_bitmap_and_inplace to avoid creating many temporary bitmaps.
Referenced by roaring::Roaring::operator&().
| uint64_t roaring_bitmap_and_cardinality | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Computes the size of the intersection between two bitmaps.
Referenced by roaring::Roaring::and_cardinality().
| void roaring_bitmap_and_inplace | ( | roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Inplace version of roaring_bitmap_and(), modifies r1 r1 == r2 is allowed.
Performance hint: if you are computing the intersection between several bitmaps, two-by-two, it is best to start with the smallest bitmap.
Referenced by roaring::Roaring::operator&=().
| roaring_bitmap_t* roaring_bitmap_andnot | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Computes the difference (andnot) between two bitmaps and returns new bitmap. Caller is responsible for freeing the result.
Referenced by roaring::Roaring::operator-().
| uint64_t roaring_bitmap_andnot_cardinality | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Computes the size of the difference (andnot) between two bitmaps.
Referenced by roaring::Roaring::andnot_cardinality().
| void roaring_bitmap_andnot_inplace | ( | roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Inplace version of roaring_bitmap_andnot, modifies r1, r1 != r2.
Referenced by roaring::Roaring::operator-=().
| void roaring_bitmap_clear | ( | roaring_bitmap_t * | r | ) |
Empties the bitmap. It will have no auxiliary allocations (so if the bitmap was initialized in client memory via roaring_bitmap_init(), then a call to roaring_bitmap_clear() would be enough to "free" it)
Referenced by roaring::Roaring::clear(), roaring::Roaring::operator=(), and roaring::Roaring::~Roaring().
| bool roaring_bitmap_contains | ( | const roaring_bitmap_t * | r, |
| uint32_t | val | ||
| ) |
Check if value is present
Referenced by roaring::Roaring::contains().
| bool roaring_bitmap_contains_bulk | ( | const roaring_bitmap_t * | r, |
| roaring_bulk_context_t * | context, | ||
| uint32_t | val | ||
| ) |
Check if an items is present, using context from a previous insert or search for speed optimization.
context will be used to store information between calls to make bulk operations faster. *context should be zero-initialized before the first call to this function.
Modifying the bitmap in any way (other than -bulk suffixed functions) will invalidate the stored context, calling this function with a non-zero context after doing any modification invokes undefined behavior.
In order to exploit this optimization, the caller should call this function with values with the same "key" (high 16 bits of the value) consecutively.
Referenced by roaring::Roaring::containsBulk().
| bool roaring_bitmap_contains_range | ( | const roaring_bitmap_t * | r, |
| uint64_t | range_start, | ||
| uint64_t | range_end | ||
| ) |
Check whether a range of values from range_start (included) to range_end (excluded) is present
Referenced by roaring::Roaring::containsRange().
| bool roaring_bitmap_contains_range_closed | ( | const roaring_bitmap_t * | r, |
| uint32_t | range_start, | ||
| uint32_t | range_end | ||
| ) |
Check whether a range of values from range_start (included) to range_end (included) is present
Referenced by roaring::Roaring::containsRangeClosed().
| roaring_bitmap_t* roaring_bitmap_copy | ( | const roaring_bitmap_t * | r | ) |
Copies a bitmap (this does memory allocation). The caller is responsible for memory management.
|
inline |
Dynamically allocates a new bitmap (initially empty). Returns NULL if the allocation fails. Client is responsible for calling roaring_bitmap_free().
Definition at line 43 of file roaring.h.
References roaring_bitmap_create_with_capacity().
| roaring_bitmap_t* roaring_bitmap_create_with_capacity | ( | uint32_t | cap | ) |
Dynamically allocates a new bitmap (initially empty). Returns NULL if the allocation fails. Capacity is a performance hint for how many "containers" the data will need. Client is responsible for calling roaring_bitmap_free().
Referenced by roaring_bitmap_create().
| roaring_bitmap_t* roaring_bitmap_deserialize | ( | const void * | buf | ) |
Use with roaring_bitmap_serialize().
(See roaring_bitmap_portable_deserialize() if you want a format that's compatible with Java and Go implementations).
This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x), the data format is going to be big-endian and not compatible with little-endian systems.
Referenced by roaring::Roaring::read().
| roaring_bitmap_t* roaring_bitmap_deserialize_safe | ( | const void * | buf, |
| size_t | maxbytes | ||
| ) |
Use with roaring_bitmap_serialize().
(See roaring_bitmap_portable_deserialize_safe() if you want a format that's compatible with Java and Go implementations).
This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x), the data format is going to be big-endian and not compatible with little-endian systems.
The difference with roaring_bitmap_deserialize() is that this function checks that the input buffer is a valid bitmap. If the buffer is too small, NULL is returned.
| bool roaring_bitmap_equals | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Return true if the two bitmaps contain the same elements.
Referenced by roaring::Roaring::operator==().
| roaring_bitmap_t* roaring_bitmap_flip | ( | const roaring_bitmap_t * | r1, |
| uint64_t | range_start, | ||
| uint64_t | range_end | ||
| ) |
Compute the negation of the bitmap in the interval [range_start, range_end). The number of negated values is range_end - range_start. Areas outside the range are passed through unchanged.
| roaring_bitmap_t* roaring_bitmap_flip_closed | ( | const roaring_bitmap_t * | x1, |
| uint32_t | range_start, | ||
| uint32_t | range_end | ||
| ) |
Compute the negation of the bitmap in the interval [range_start, range_end]. The number of negated values is range_end - range_start + 1. Areas outside the range are passed through unchanged.
| void roaring_bitmap_flip_inplace | ( | roaring_bitmap_t * | r1, |
| uint64_t | range_start, | ||
| uint64_t | range_end | ||
| ) |
compute (in place) the negation of the roaring bitmap within a specified interval: [range_start, range_end). The number of negated values is range_end - range_start. Areas outside the range are passed through unchanged.
Referenced by roaring::Roaring::flip().
| void roaring_bitmap_flip_inplace_closed | ( | roaring_bitmap_t * | r1, |
| uint32_t | range_start, | ||
| uint32_t | range_end | ||
| ) |
compute (in place) the negation of the roaring bitmap within a specified interval: [range_start, range_end]. The number of negated values is range_end - range_start + 1. Areas outside the range are passed through unchanged.
Referenced by roaring::Roaring::flipClosed().
| void roaring_bitmap_free | ( | const roaring_bitmap_t * | r | ) |
TODO: consider implementing:
"Compute the xor of 'number' bitmaps using a heap. This can sometimes be faster than roaring_bitmap_xor_many which uses a naive algorithm. Caller is responsible for freeing the result.""
roaring_bitmap_t *roaring_bitmap_xor_many_heap(uint32_t number, const roaring_bitmap_t **rs); Frees the memory.
Referenced by roaring::Roaring::~Roaring().
| roaring_bitmap_t* roaring_bitmap_from_range | ( | uint64_t | min, |
| uint64_t | max, | ||
| uint32_t | step | ||
| ) |
Add all the values between min (included) and max (excluded) that are at a distance k*step from min.
| void roaring_bitmap_frozen_serialize | ( | const roaring_bitmap_t * | r, |
| char * | buf | ||
| ) |
Serializes bitmap using frozen format. Buffer size must be at least roaring_bitmap_frozen_size_in_bytes().
This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x), the data format is going to be big-endian and not compatible with little-endian systems.
When serializing data to a file, we recommend that you also use checksums so that, at deserialization, you can be confident that you are recovering the correct data.
Referenced by roaring::Roaring::writeFrozen().
| size_t roaring_bitmap_frozen_size_in_bytes | ( | const roaring_bitmap_t * | r | ) |
Returns number of bytes required to serialize bitmap using frozen format.
Referenced by roaring::Roaring::getFrozenSizeInBytes().
| const roaring_bitmap_t* roaring_bitmap_frozen_view | ( | const char * | buf, |
| size_t | length | ||
| ) |
Creates constant bitmap that is a view of a given buffer. Buffer data should have been written by roaring_bitmap_frozen_serialize() Its beginning must also be aligned by 32 bytes. Length must be equal exactly to roaring_bitmap_frozen_size_in_bytes(). In case of failure, NULL is returned.
Bitmap returned by this function can be used in all readonly contexts. Bitmap must be freed as usual, by calling roaring_bitmap_free(). Underlying buffer must not be freed or modified while it backs any bitmaps.
This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x), the data format is going to be big-endian and not compatible with little-endian systems.
Referenced by roaring::Roaring::frozenView().
| uint64_t roaring_bitmap_get_cardinality | ( | const roaring_bitmap_t * | r | ) |
Get the cardinality of the bitmap (number of elements).
Referenced by roaring::Roaring::cardinality(), and roaring::Roaring::isFull().
|
inline |
Definition at line 84 of file roaring.h.
References roaring_bitmap_s::high_low_container.
Referenced by roaring::Roaring::getCopyOnWrite(), roaring::Roaring::operator=(), and roaring::Roaring::Roaring().
| int64_t roaring_bitmap_get_index | ( | const roaring_bitmap_t * | r, |
| uint32_t | x | ||
| ) |
Returns the index of x in the given roaring bitmap. If the roaring bitmap doesn't contain x , this function will return -1. The difference with rank function is that this function will return -1 when x is not the element of roaring bitmap, but the rank function will return a non-negative number.
Referenced by roaring::Roaring::getIndex().
|
inline |
Initialize a roaring bitmap structure in memory controlled by client. The bitmap will be in a "clear" state, with no auxiliary allocations. Since this performs no allocations, the function will not fail.
Definition at line 59 of file roaring.h.
References roaring_bitmap_init_with_capacity().
Referenced by roaring::Roaring::operator=(), and roaring::Roaring::Roaring().
| bool roaring_bitmap_init_with_capacity | ( | roaring_bitmap_t * | r, |
| uint32_t | cap | ||
| ) |
Initialize a roaring bitmap structure in memory controlled by client. Capacity is a performance hint for how many "containers" the data will need. Can return false if auxiliary allocations fail when capacity greater than 0.
Referenced by roaring_bitmap_init_cleared().
| bool roaring_bitmap_internal_validate | ( | const roaring_bitmap_t * | r, |
| const char ** | reason | ||
| ) |
Perform internal consistency checks. Returns true if the bitmap is consistent. It may be useful to call this after deserializing bitmaps from untrusted sources. If roaring_bitmap_internal_validate returns true, then the bitmap should be consistent and can be trusted not to cause crashes or memory corruption.
Note that some operations intentionally leave bitmaps in an inconsistent state temporarily, for example, roaring_bitmap_lazy_* functions, until roaring_bitmap_repair_after_lazy is called.
If reason is non-null, it will be set to a string describing the first inconsistency found if any.
| bool roaring_bitmap_intersect | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Check whether two bitmaps intersect.
Referenced by roaring::Roaring::intersect().
| bool roaring_bitmap_intersect_with_range | ( | const roaring_bitmap_t * | bm, |
| uint64_t | x, | ||
| uint64_t | y | ||
| ) |
Check whether a bitmap and an open range intersect.
| bool roaring_bitmap_is_empty | ( | const roaring_bitmap_t * | r | ) |
Returns true if the bitmap is empty (cardinality is zero).
Referenced by roaring::Roaring::isEmpty().
| bool roaring_bitmap_is_strict_subset | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Return true if all the elements of r1 are also in r2, and r2 is strictly greater than r1.
Referenced by roaring::Roaring::isStrictSubset().
| bool roaring_bitmap_is_subset | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Return true if all the elements of r1 are also in r2.
Referenced by roaring::Roaring::isSubset().
| double roaring_bitmap_jaccard_index | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Computes the Jaccard index between two bitmaps. (Also known as the Tanimoto distance, or the Jaccard similarity coefficient)
The Jaccard index is undefined if both bitmaps are empty.
Referenced by roaring::Roaring::jaccard_index().
| roaring_bitmap_t* roaring_bitmap_lazy_or | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2, | ||
| const bool | bitsetconversion | ||
| ) |
(For expert users who seek high performance.)
Computes the union between two bitmaps and returns new bitmap. The caller is responsible for memory management.
The lazy version defers some computations such as the maintenance of the cardinality counts. Thus you must call roaring_bitmap_repair_after_lazy() after executing "lazy" computations.
It is safe to repeatedly call roaring_bitmap_lazy_or_inplace on the result.
bitsetconversion is a flag which determines whether container-container operations force a bitset conversion.
| void roaring_bitmap_lazy_or_inplace | ( | roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2, | ||
| const bool | bitsetconversion | ||
| ) |
(For expert users who seek high performance.)
Inplace version of roaring_bitmap_lazy_or, modifies r1.
bitsetconversion is a flag which determines whether container-container operations force a bitset conversion.
| roaring_bitmap_t* roaring_bitmap_lazy_xor | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Computes the symmetric difference between two bitmaps and returns new bitmap. The caller is responsible for memory management.
The lazy version defers some computations such as the maintenance of the cardinality counts. Thus you must call roaring_bitmap_repair_after_lazy() after executing "lazy" computations.
It is safe to repeatedly call roaring_bitmap_lazy_xor_inplace() on the result.
| void roaring_bitmap_lazy_xor_inplace | ( | roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
(For expert users who seek high performance.)
Inplace version of roaring_bitmap_lazy_xor, modifies r1. r1 != r2
| uint32_t roaring_bitmap_maximum | ( | const roaring_bitmap_t * | r | ) |
Returns the greatest value in the set, or 0 if the set is empty.
Referenced by roaring::Roaring::maximum().
| uint32_t roaring_bitmap_minimum | ( | const roaring_bitmap_t * | r | ) |
Returns the smallest value in the set, or UINT32_MAX if the set is empty.
Referenced by roaring::Roaring::minimum().
| CROARING_DEPRECATED roaring_bitmap_t* roaring_bitmap_of | ( | size_t | n, |
| ... | |||
| ) |
Creates a new bitmap from a list of uint32_t integers
This function is deprecated, use roaring_bitmap_from instead, which doesn't require the number of elements to be passed in.
| roaring_bitmap_t* roaring_bitmap_of_ptr | ( | size_t | n_args, |
| const uint32_t * | vals | ||
| ) |
Creates a new bitmap from a pointer of uint32_t integers
| roaring_bitmap_t* roaring_bitmap_or | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Computes the union between two bitmaps and returns new bitmap. The caller is responsible for memory management.
Referenced by roaring::Roaring::operator|().
| uint64_t roaring_bitmap_or_cardinality | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Computes the size of the union between two bitmaps.
Referenced by roaring::Roaring::or_cardinality().
| void roaring_bitmap_or_inplace | ( | roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Inplace version of `roaring_bitmap_or(), modifies r1. TODO: decide whether r1 == r2 ok
Referenced by roaring::Roaring::operator|=().
| roaring_bitmap_t* roaring_bitmap_or_many | ( | size_t | number, |
| const roaring_bitmap_t ** | rs | ||
| ) |
Compute the union of 'number' bitmaps. Caller is responsible for freeing the result. See also roaring_bitmap_or_many_heap()
Referenced by roaring::Roaring::fastunion(), and roaring::Roaring64Map::fastunion().
| roaring_bitmap_t* roaring_bitmap_or_many_heap | ( | uint32_t | number, |
| const roaring_bitmap_t ** | rs | ||
| ) |
Compute the union of 'number' bitmaps using a heap. This can sometimes be faster than `roaring_bitmap_or_many() which uses a naive algorithm. Caller is responsible for freeing the result.
| bool roaring_bitmap_overwrite | ( | roaring_bitmap_t * | dest, |
| const roaring_bitmap_t * | src | ||
| ) |
Copies a bitmap from src to dest. It is assumed that the pointer dest is to an already allocated bitmap. The content of the dest bitmap is freed/deleted.
It might be preferable and simpler to call roaring_bitmap_copy except that roaring_bitmap_overwrite can save on memory allocations.
Returns true if successful, or false if there was an error. On failure, the dest bitmap is left in a valid, empty state (even if it was not empty before).
Referenced by roaring::Roaring::operator=(), and roaring::Roaring::Roaring().
| roaring_bitmap_t* roaring_bitmap_portable_deserialize | ( | const char * | buf | ) |
Read bitmap from a serialized buffer. In case of failure, NULL is returned.
This function is unsafe in the sense that if there is no valid serialized bitmap at the pointer, then many bytes could be read, possibly causing a buffer overflow. See also roaring_bitmap_portable_deserialize_safe().
This is meant to be compatible with the Java and Go versions: https://github.com/RoaringBitmap/RoaringFormatSpec
This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x), the data format is going to be big-endian and not compatible with little-endian systems.
Referenced by roaring::Roaring::read().
| roaring_bitmap_t* roaring_bitmap_portable_deserialize_frozen | ( | const char * | buf | ) |
Read bitmap from a serialized buffer. In case of failure, NULL is returned.
Bitmap returned by this function can be used in all readonly contexts. Bitmap must be freed as usual, by calling roaring_bitmap_free(). Underlying buffer must not be freed or modified while it backs any bitmaps.
The function is unsafe in the following ways: 1) It may execute unaligned memory accesses. 2) A buffer overflow may occur if buf does not point to a valid serialized bitmap.
This is meant to be compatible with the Java and Go versions: https://github.com/RoaringBitmap/RoaringFormatSpec
This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x), the data format is going to be big-endian and not compatible with little-endian systems.
Referenced by roaring::Roaring::portableDeserializeFrozen().
| roaring_bitmap_t* roaring_bitmap_portable_deserialize_safe | ( | const char * | buf, |
| size_t | maxbytes | ||
| ) |
Read bitmap from a serialized buffer safely (reading up to maxbytes). In case of failure, NULL is returned.
This is meant to be compatible with the Java and Go versions: https://github.com/RoaringBitmap/RoaringFormatSpec
The function itself is safe in the sense that it will not cause buffer overflows: it will not read beyond the scope of the provided buffer (buf,maxbytes).
However, for correct operations, it is assumed that the bitmap read was once serialized from a valid bitmap (i.e., it follows the format specification). If you provided an incorrect input (garbage), then the bitmap read may not be in a valid state and following operations may not lead to sensible results. In particular, the serialized array containers need to be in sorted order, and the run containers should be in sorted non-overlapping order. This is is guaranteed to happen when serializing an existing bitmap, but not for random inputs.
If the source is untrusted, you should call roaring_bitmap_internal_validate to check the validity of the bitmap prior to using it. Only after calling roaring_bitmap_internal_validate is the bitmap considered safe for use.
We also recommend that you use checksums to check that serialized data corresponds to the serialized bitmap. The CRoaring library does not provide checksumming.
This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x), the data format is going to be big-endian and not compatible with little-endian systems.
Referenced by roaring::Roaring::readSafe().
| size_t roaring_bitmap_portable_deserialize_size | ( | const char * | buf, |
| size_t | maxbytes | ||
| ) |
Check how many bytes would be read (up to maxbytes) at this pointer if there is a bitmap, returns zero if there is no valid bitmap.
This is meant to be compatible with the Java and Go versions: https://github.com/RoaringBitmap/RoaringFormatSpec
| size_t roaring_bitmap_portable_serialize | ( | const roaring_bitmap_t * | r, |
| char * | buf | ||
| ) |
Write a bitmap to a char buffer. The output buffer should refer to at least roaring_bitmap_portable_size_in_bytes(r) bytes of allocated memory.
Returns how many bytes were written which should match roaring_bitmap_portable_size_in_bytes(r).
This is meant to be compatible with the Java and Go versions: https://github.com/RoaringBitmap/RoaringFormatSpec
This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x), the data format is going to be big-endian and not compatible with little-endian systems.
When serializing data to a file, we recommend that you also use checksums so that, at deserialization, you can be confident that you are recovering the correct data.
Referenced by roaring::Roaring::write().
| size_t roaring_bitmap_portable_size_in_bytes | ( | const roaring_bitmap_t * | r | ) |
How many bytes are required to serialize this bitmap.
This is meant to be compatible with the Java and Go versions: https://github.com/RoaringBitmap/RoaringFormatSpec
Referenced by roaring::Roaring::getSizeInBytes().
| void roaring_bitmap_printf | ( | const roaring_bitmap_t * | r | ) |
Print the content of the bitmap.
Referenced by roaring::Roaring::printf().
| void roaring_bitmap_printf_describe | ( | const roaring_bitmap_t * | r | ) |
Describe the inner structure of the bitmap.
| uint64_t roaring_bitmap_range_cardinality | ( | const roaring_bitmap_t * | r, |
| uint64_t | range_start, | ||
| uint64_t | range_end | ||
| ) |
Returns the number of elements in the range [range_start, range_end).
| uint64_t roaring_bitmap_range_cardinality_closed | ( | const roaring_bitmap_t * | r, |
| uint32_t | range_start, | ||
| uint32_t | range_end | ||
| ) |
Returns the number of elements in the range [range_start, range_end].
| bool roaring_bitmap_range_uint32_array | ( | const roaring_bitmap_t * | r, |
| size_t | offset, | ||
| size_t | limit, | ||
| uint32_t * | ans | ||
| ) |
Convert the bitmap to a sorted array from offset by limit, output in ans.
Caller is responsible to ensure that there is enough memory allocated, e.g.
ans = malloc(roaring_bitmap_get_cardinality(limit) * sizeof(uint32_t));
Return false in case of failure (e.g., insufficient memory)
Referenced by roaring::Roaring::rangeUint32Array().
| uint64_t roaring_bitmap_rank | ( | const roaring_bitmap_t * | r, |
| uint32_t | x | ||
| ) |
roaring_bitmap_rank returns the number of integers that are smaller or equal to x. Thus if x is the first element, this function will return 1. If x is smaller than the smallest element, this function will return 0.
The indexing convention differs between roaring_bitmap_select and roaring_bitmap_rank: roaring_bitmap_select refers to the smallest value as having index 0, whereas roaring_bitmap_rank returns 1 when ranking the smallest value.
Referenced by roaring::Roaring::rank().
| void roaring_bitmap_rank_many | ( | const roaring_bitmap_t * | r, |
| const uint32_t * | begin, | ||
| const uint32_t * | end, | ||
| uint64_t * | ans | ||
| ) |
roaring_bitmap_rank_many is an Bulk version of roaring_bitmap_rank it puts rank value of each element in [begin .. end) to ans[]
the values in [begin .. end) must be sorted in Ascending order; Caller is responsible to ensure that there is enough memory allocated, e.g.
ans = malloc((end-begin) * sizeof(uint64_t));
Referenced by roaring::Roaring::rank_many().
| void roaring_bitmap_remove | ( | roaring_bitmap_t * | r, |
| uint32_t | x | ||
| ) |
Remove value x
Referenced by roaring::Roaring::remove().
| bool roaring_bitmap_remove_checked | ( | roaring_bitmap_t * | r, |
| uint32_t | x | ||
| ) |
Remove value x Returns true if a new value was removed, false if the value was not existing.
Referenced by roaring::Roaring::removeChecked().
| void roaring_bitmap_remove_many | ( | roaring_bitmap_t * | r, |
| size_t | n_args, | ||
| const uint32_t * | vals | ||
| ) |
Remove multiple values
|
inline |
Remove all values in range [min, max)
Definition at line 410 of file roaring.h.
References roaring_bitmap_remove_range_closed().
Referenced by roaring::Roaring::removeRange().
| void roaring_bitmap_remove_range_closed | ( | roaring_bitmap_t * | r, |
| uint32_t | min, | ||
| uint32_t | max | ||
| ) |
Remove all values in range [min, max]
Referenced by roaring::Roaring::removeRangeClosed(), and roaring_bitmap_remove_range().
| bool roaring_bitmap_remove_run_compression | ( | roaring_bitmap_t * | r | ) |
Remove run-length encoding even when it is more space efficient. Return whether a change was applied.
Referenced by roaring::Roaring::removeRunCompression().
| void roaring_bitmap_repair_after_lazy | ( | roaring_bitmap_t * | r1 | ) |
(For expert users who seek high performance.)
Execute maintenance on a bitmap created from roaring_bitmap_lazy_or() or modified with roaring_bitmap_lazy_or_inplace().
| bool roaring_bitmap_run_optimize | ( | roaring_bitmap_t * | r | ) |
Convert array and bitmap containers to run containers when it is more efficient; also convert from run containers when more space efficient.
Returns true if the result has at least one run container. Additional savings might be possible by calling shrinkToFit().
Referenced by roaring::Roaring::runOptimize().
| bool roaring_bitmap_select | ( | const roaring_bitmap_t * | r, |
| uint32_t | rank, | ||
| uint32_t * | element | ||
| ) |
Selects the element at index 'rank' where the smallest element is at index 0. If the size of the roaring bitmap is strictly greater than rank, then this function returns true and sets element to the element of given rank. Otherwise, it returns false.
Referenced by roaring::Roaring::select().
| size_t roaring_bitmap_serialize | ( | const roaring_bitmap_t * | r, |
| char * | buf | ||
| ) |
Write the bitmap to an output pointer, this output buffer should refer to at least roaring_bitmap_size_in_bytes(r) allocated bytes.
See roaring_bitmap_portable_serialize() if you want a format that's compatible with Java and Go implementations. This format can sometimes be more space efficient than the portable form, e.g. when the data is sparse.
Returns how many bytes written, should be roaring_bitmap_size_in_bytes(r).
This function is endian-sensitive. If you have a big-endian system (e.g., a mainframe IBM s390x), the data format is going to be big-endian and not compatible with little-endian systems.
When serializing data to a file, we recommend that you also use checksums so that, at deserialization, you can be confident that you are recovering the correct data.
Referenced by roaring::Roaring::write().
|
inline |
Definition at line 87 of file roaring.h.
References roaring_bitmap_s::high_low_container.
Referenced by roaring::Roaring::operator=(), roaring::Roaring::Roaring(), and roaring::Roaring::setCopyOnWrite().
| size_t roaring_bitmap_shrink_to_fit | ( | roaring_bitmap_t * | r | ) |
If needed, reallocate memory to shrink the memory usage. Returns the number of bytes saved.
Referenced by roaring::Roaring::shrinkToFit().
| size_t roaring_bitmap_size_in_bytes | ( | const roaring_bitmap_t * | r | ) |
How many bytes are required to serialize this bitmap (NOT compatible with Java and Go versions)
Referenced by roaring::Roaring::getSizeInBytes().
| void roaring_bitmap_statistics | ( | const roaring_bitmap_t * | r, |
| roaring_statistics_t * | stat | ||
| ) |
(For advanced users.)
Collect statistics about the bitmap, see roaring_types.h for a description of roaring_statistics_t
| bool roaring_bitmap_to_bitset | ( | const roaring_bitmap_t * | r, |
| bitset_t * | bitset | ||
| ) |
Store the bitmap to a bitset. This can be useful for people who need the performance and simplicity of a standard bitset. We assume that the input bitset is originally empty (does not have any set bit).
bitset_t * out = bitset_create(); // if the bitset has content in it, call "bitset_clear(out)" bool success = roaring_bitmap_to_bitset(mybitmap, out); // on failure, success will be false. // You can then query the bitset: bool is_present = bitset_get(out, 10011 ); // you must free the memory: bitset_free(out);
| void roaring_bitmap_to_uint32_array | ( | const roaring_bitmap_t * | r, |
| uint32_t * | ans | ||
| ) |
Convert the bitmap to a sorted array, output in ans.
Caller is responsible to ensure that there is enough memory allocated, e.g.
ans = malloc(roaring_bitmap_get_cardinality(bitmap) * sizeof(uint32_t));
Referenced by roaring::Roaring::toUint32Array().
| roaring_bitmap_t* roaring_bitmap_xor | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Computes the symmetric difference (xor) between two bitmaps and returns new bitmap. The caller is responsible for memory management.
Referenced by roaring::Roaring::operator^().
| uint64_t roaring_bitmap_xor_cardinality | ( | const roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Computes the size of the symmetric difference (xor) between two bitmaps.
Referenced by roaring::Roaring::xor_cardinality().
| void roaring_bitmap_xor_inplace | ( | roaring_bitmap_t * | r1, |
| const roaring_bitmap_t * | r2 | ||
| ) |
Inplace version of roaring_bitmap_xor, modifies r1, r1 != r2.
Referenced by roaring::Roaring::operator^=().
| roaring_bitmap_t* roaring_bitmap_xor_many | ( | size_t | number, |
| const roaring_bitmap_t ** | rs | ||
| ) |
Compute the xor of 'number' bitmaps. Caller is responsible for freeing the result.
|
inlinestatic |
DEPRECATED, use roaring_uint32_iterator_copy.
Definition at line 1130 of file roaring.h.
References roaring_uint32_iterator_copy().
|
inlinestatic |
DEPRECATED, use roaring_iterator_create.
Definition at line 1068 of file roaring.h.
References roaring_iterator_create().
|
inlinestatic |
DEPRECATED, use roaring_uint32_iterator_free.
Definition at line 1140 of file roaring.h.
References roaring_uint32_iterator_free().
|
inlinestatic |
DEPRECATED, use roaring_iterator_init.
Definition at line 1037 of file roaring.h.
References roaring_iterator_init().
|
inlinestatic |
DEPRECATED, use roaring_iterator_init_last.
Definition at line 1051 of file roaring.h.
References roaring_iterator_init_last().
| bool roaring_iterate | ( | const roaring_bitmap_t * | r, |
| roaring_iterator | iterator, | ||
| void * | ptr | ||
| ) |
Iterate over the bitmap elements. The function iterator is called once for all the values with ptr (can be NULL) as the second parameter of each call.
roaring_iterator is simply a pointer to a function that returns bool (true means that the iteration should continue while false means that it should stop), and takes (uint32_t,void*) as inputs.
Returns true if the roaring_iterator returned true throughout (so that all data points were necessarily visited).
Iteration is ordered: from the smallest to the largest elements.
Referenced by roaring::Roaring::iterate().
| bool roaring_iterate64 | ( | const roaring_bitmap_t * | r, |
| roaring_iterator64 | iterator, | ||
| uint64_t | high_bits, | ||
| void * | ptr | ||
| ) |
Referenced by roaring::Roaring64Map::iterate().
| roaring_uint32_iterator_t* roaring_iterator_create | ( | const roaring_bitmap_t * | r | ) |
Create an iterator object that can be used to iterate through the values. Caller is responsible for calling roaring_free_iterator().
The iterator is initialized (this function calls roaring_iterator_init()) If there is a value, then this iterator points to the first value and it->has_value is true. The value is in it->current_value.
Referenced by roaring_create_iterator().
| void roaring_iterator_init | ( | const roaring_bitmap_t * | r, |
| roaring_uint32_iterator_t * | newit | ||
| ) |
Initialize an iterator object that can be used to iterate through the values. If there is a value, then this iterator points to the first value and it->has_value is true. The value is in it->current_value.
Referenced by roaring::Roaring64MapSetBitBiDirectionalIterator::move_equalorlarger(), roaring::Roaring64MapSetBitBiDirectionalIterator::operator++(), roaring::Roaring64MapSetBitBiDirectionalIterator::Roaring64MapSetBitBiDirectionalIterator(), roaring_init_iterator(), and roaring::RoaringSetBitBiDirectionalIterator::RoaringSetBitBiDirectionalIterator().
| void roaring_iterator_init_last | ( | const roaring_bitmap_t * | r, |
| roaring_uint32_iterator_t * | newit | ||
| ) |
Initialize an iterator object that can be used to iterate through the values. If there is a value, then this iterator points to the last value and it->has_value is true. The value is in it->current_value.
Referenced by roaring::Roaring64MapSetBitBiDirectionalIterator::operator--(), and roaring_init_iterator_last().
|
inlinestatic |
DEPRECATED, use roaring_uint32_iterator_move_equalorlarger.
Definition at line 1116 of file roaring.h.
References roaring_uint32_iterator_move_equalorlarger().
|
inlinestatic |
DEPRECATED, use roaring_uint32_iterator_previous.
Definition at line 1101 of file roaring.h.
References roaring_uint32_iterator_previous().
|
inlinestatic |
DEPRECATED, use roaring_uint32_iterator_read.
Definition at line 1160 of file roaring.h.
References roaring_uint32_iterator_read().
| bool roaring_uint32_iterator_advance | ( | roaring_uint32_iterator_t * | it | ) |
Advance the iterator. If there is a new value, then it->has_value is true. The new value is in it->current_value. Values are traversed in increasing orders. For convenience, returns it->has_value.
Once it->has_value is false, roaring_uint32_iterator_advance should not be called on the iterator again. Calling roaring_uint32_iterator_previous is allowed.
Referenced by roaring::RoaringSetBitBiDirectionalIterator::operator++(), roaring::Roaring64MapSetBitBiDirectionalIterator::operator++(), and roaring_advance_uint32_iterator().
| roaring_uint32_iterator_t* roaring_uint32_iterator_copy | ( | const roaring_uint32_iterator_t * | it | ) |
Creates a copy of an iterator. Caller must free it.
Referenced by roaring_copy_uint32_iterator().
| void roaring_uint32_iterator_free | ( | roaring_uint32_iterator_t * | it | ) |
Free memory following roaring_iterator_create()
Referenced by roaring_free_uint32_iterator().
| bool roaring_uint32_iterator_move_equalorlarger | ( | roaring_uint32_iterator_t * | it, |
| uint32_t | val | ||
| ) |
Move the iterator to the first value >= val. If there is a such a value, then it->has_value is true. The new value is in it->current_value. For convenience, returns it->has_value.
Referenced by roaring::RoaringSetBitBiDirectionalIterator::equalorlarger(), roaring::Roaring64MapSetBitBiDirectionalIterator::move_equalorlarger(), roaring::RoaringSetBitBiDirectionalIterator::move_equalorlarger(), and roaring_move_uint32_iterator_equalorlarger().
| bool roaring_uint32_iterator_previous | ( | roaring_uint32_iterator_t * | it | ) |
Decrement the iterator. If there's a new value, then it->has_value is true. The new value is in it->current_value. Values are traversed in decreasing order. For convenience, returns it->has_value.
Once it->has_value is false, roaring_uint32_iterator_previous should not be called on the iterator again. Calling roaring_uint32_iterator_advance is allowed.
Referenced by roaring::RoaringSetBitBiDirectionalIterator::operator--(), roaring::Roaring64MapSetBitBiDirectionalIterator::operator--(), and roaring_previous_uint32_iterator().
| uint32_t roaring_uint32_iterator_read | ( | roaring_uint32_iterator_t * | it, |
| uint32_t * | buf, | ||
| uint32_t | count | ||
| ) |
Referenced by roaring_read_uint32_iterator().
1.9.1