|
|
| RankSelectSupportCompressed ()=default |
| | Construct an empty index with no select directions enabled.
|
| |
|
| RankSelectSupportCompressed (const RankSelectSupportCompressed &)=default |
| | Duplicate metadata while borrowing the same immutable source.
|
| |
|
| RankSelectSupportCompressed (RankSelectSupportCompressed &&other) noexcept(kNothrowDefaultConstruction) |
| | Transfer metadata, leaving the source empty with select disabled.
|
| |
| RankSelectSupportCompressed & | operator= (const RankSelectSupportCompressed &other) |
| | Duplicate metadata while borrowing the assigned source.
|
| |
| RankSelectSupportCompressed & | operator= (RankSelectSupportCompressed &&other) noexcept(kNothrowDefaultConstruction) |
| | Transfer metadata, leaving the source empty with select disabled.
|
| |
| | RankSelectSupportCompressed (std::span< const std::uint64_t > source_words, std::size_t num_bits, SelectSupport select_support=SelectSupport::kBoth) |
| | Index caller-owned packed words, ignoring padding after valid bits.
|
| |
|
std::size_t | size_impl () const |
| | Return the logical source bit count.
|
| |
|
int | bit_impl (std::size_t position) const |
| | Read a zero-based bit; position must be below size().
|
| |
|
std::uint64_t | rank_impl (std::size_t end) const |
| | Count ones in [0, end), clamping end at size().
|
| |
|
std::uint64_t | rank0_impl (std::size_t end) const |
| | Count zeros in [0, end), clamping to the logical bit length.
|
| |
| std::uint64_t | select_impl (std::size_t rank) const |
| | Locate a one-based one occurrence as a zero-based bit position.
|
| |
| std::uint64_t | select0_impl (std::size_t rank) const |
| | Locate a one-based zero occurrence as a zero-based bit position.
|
| |
|
bool | supports_select1_impl () const |
| | Report whether one-select metadata was requested.
|
| |
|
bool | supports_select0_impl () const |
| | Report whether zero-select metadata was requested.
|
| |
|
std::size_t | memory_usage_bytes_impl () const |
| | Object plus allocated auxiliary bytes, excluding borrowed words.
|
| |
| 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, std::size_t SampleFrequency = 4096, std::size_t SearchThreshold = 16>
class pixie::RankSelectSupportCompressed< MetadataStorage, SampleFrequency, SearchThreshold >
Non-owning rank/select index with compressed interleaved metadata.
Source words must remain alive and immutable. Copies own independent metadata and borrow the same source; moves leave an empty, disabled index. Half-open rank, one-based select and sentinels follow RankSelectBase; rank boundaries beyond size() clamp to the total. Serialization is not provided.
Rank: one 64-byte record per 16,384 source bits (3.125% overhead)
+------------------+-------------------------------------------+
| global ones: 64b | 32 local prefix ends: 14b each (448b) |
+------------------+-------------------------------------------+
local prefix ends correspond to 512-bit source-block boundaries
Select: independent samples every SampleFrequency ones / zeros
coarse EF groups: descriptor -> [base | unary highs | low bits]
dense EF groups: [base | unary highs | wide map* | 32 low fields]
<---------- fixed stride ------------------>
wide map*: [directory prefix | bitmap], present for mixed shapes
coarse groups keep the wide map separately
wide directory: [begin, count] -> rank endpoints + occupied IDs*
occupied IDs* are omitted when all wide intervals are contiguous
Short intervals scan global ranks; wide intervals search stored endpoints. Dense samples store exact positions: decode both neighbors, prefetch an estimated source block, then validate against rank. A miss corrects by one block or falls back to the directory. Homogeneous regions use arithmetic. AlignedStorage aligns rank records to 64 bytes; custom backends need only uint64_t alignment. All retained arrays use MetadataStorage.
- Template Parameters
-
| MetadataStorage | Default-empty, owning contiguous storage with deep copies and nonthrowing move construction/assignment. Construction requires resize(bit_count), writable_bytes() and as_bytes(), exposing exactly the requested bytes with uint64_t alignment. Memory reporting requires allocated_bytes(). The borrowed source needs no cache-line alignment. |
| SampleFrequency | Positive power-of-two occurrence sampling interval. |
| SearchThreshold | Positive superblock-span threshold for wide indexing. |
Public Member Functions inherited from pixie::RankSelectBase< RankSelectSupportCompressed< AlignedStorage, 4096, 16 > >
1.13.2