|
|
| RankSelectSupport (const RankSelectSupport &)=default |
| |
|
| RankSelectSupport (RankSelectSupport &&) noexcept=default |
| |
|
RankSelectSupport & | operator= (const RankSelectSupport &)=default |
| |
|
RankSelectSupport & | operator= (RankSelectSupport &&) noexcept=default |
| |
| | RankSelectSupport (ReadOnlyStorageView source_storage, size_t num_bits, SelectSupport select_support=SelectSupport::kBoth, std::optional< size_t > one_count=std::nullopt) |
| | Construct support over a read-only storage view.
|
| |
| | RankSelectSupport (std::span< const uint64_t > source_words, size_t num_bits, SelectSupport select_support=SelectSupport::kBoth, std::optional< size_t > one_count=std::nullopt) |
| | Construct support over caller-owned packed 64-bit words.
|
| |
| template<StorageImplementation SourceStorage> |
| | RankSelectSupport (const SourceStorage &source_storage, size_t num_bits, SelectSupport select_support=SelectSupport::kBoth, std::optional< size_t > one_count=std::nullopt) |
| | Construct support over a Pixie storage implementation.
|
| |
|
size_t | size_impl () const |
| | Returns the number of valid bits.
|
| |
|
bool | supports_select1_impl () const |
| | Whether this index stores samples for select1 queries.
|
| |
|
bool | supports_select0_impl () const |
| | Whether this index stores samples for select0 queries.
|
| |
| size_t | memory_usage_bytes_impl () const |
| | Return owned auxiliary memory usage in bytes.
|
| |
| int | bit_impl (size_t pos) const |
| | Returns the bit at the given position.
|
| |
| uint64_t | rank_impl (size_t pos) const |
| | Rank of 1s up to position pos (exclusive).
|
| |
| uint64_t | select_impl (size_t rank) const |
| | Rank of 0s up to position pos (exclusive).
|
| |
| uint64_t | select0_impl (size_t rank0) const |
| | Select the position of the rank0-th 0-bit (1-indexed).
|
| |
|
void | serialize (pixie::OutputBitStream &bs) const |
| |
| std::size_t | size () const |
| | Return the number of valid bits.
|
| |
| bool | empty () const |
| | Check whether the bit vector is empty.
|
| |
| int | operator[] (std::size_t position) const |
| | Read a bit by zero-based position.
|
| |
| std::uint64_t | rank (std::size_t end_position) const |
| | Count one bits in the prefix [0, end_position).
|
| |
| std::uint64_t | rank0 (std::size_t end_position) const |
| | Count zero bits in the prefix [0, end_position).
|
| |
| std::uint64_t | select (std::size_t rank) const |
| | Return the position of the rank-th one bit.
|
| |
| std::uint64_t | select0 (std::size_t rank) const |
| | Return the position of the rank-th zero bit.
|
| |
| bool | supports_select1 () const |
| | Check whether select queries for one bits are enabled.
|
| |
| bool | supports_select0 () const |
| | Check whether select queries for zero bits are enabled.
|
| |
| std::size_t | memory_usage_bytes () const |
| | Return owned index memory usage when provided by the implementation.
|
| |
| std::string | to_string () const |
| | Convert the logical bits to a binary string.
|
| |
template<StorageImplementation MetadataStorage = AlignedStorage>
class pixie::RankSelectSupport< MetadataStorage >
Rank/select support over an external packed bit sequence.
This object does not own its source bits. It owns rank/select metadata through MetadataStorage and keeps a read-only storage view plus a validated 64-bit-word view of the caller-owned source.
Structure overview:
- Super blocks of 2^16 bits with 64-bit ranks (0.098% overhead).
- Basic blocks of 512 bits with 16-bit ranks (3.125% overhead).
- Optional 64-bit select samples every 2^14 occurrences. One enabled direction uses at most 0.391% overhead; when both directions are enabled, their combined asymptotic overhead is also 0.391%.
The rank metadata plus both select directions therefore use 3.613% asymptotic metadata overhead. These ratios exclude the object itself, sentinel entries, and 64-byte allocation rounding, which are included by memory_usage_bytes_impl().
Rank: 2 table lookups plus SIMD popcount in the 512-bit block.
Select:
- Start from a sampled super block.
- SIMD linear scan to find the super block.
- SIMD linear scan to find the basic block.
This variant does not interleave data and index, favoring simpler scans. Rank metadata and enabled select samples are built in one scan over the source words.
Public Member Functions inherited from pixie::RankSelectBase< RankSelectSupport< AlignedStorage > >
1.13.2