|
|
| RmMBTree (const RmMBTree &)=default |
| |
|
| RmMBTree (RmMBTree &&) noexcept=default |
| |
|
RmMBTree & | operator= (const RmMBTree &)=default |
| |
|
RmMBTree & | operator= (RmMBTree &&) noexcept=default |
| |
| | RmMBTree (std::span< const std::uint64_t > words, std::size_t bit_count, std::size_t=kBlockBits) |
| | Construct an RmM btree over an external bit-vector span.
|
| |
| | RmMBTree (std::span< const std::uint64_t > words, std::size_t bit_count, RankSelectSupport<>::SelectSupport select_support, std::optional< std::size_t > one_count=std::nullopt, std::size_t=kBlockBits) |
| | Construct with explicit rank/select support options.
|
| |
|
std::size_t | size_impl () const |
| |
|
std::size_t | rank1_impl (std::size_t end_position) const |
| |
|
std::size_t | rank0_impl (std::size_t end_position) const |
| |
|
std::size_t | select1_impl (std::size_t rank) const |
| |
|
std::size_t | select0_impl (std::size_t rank) const |
| |
|
std::size_t | rank10_impl (std::size_t end_position) const |
| |
|
std::size_t | select10_impl (std::size_t rank) const |
| |
|
int | excess_impl (std::size_t end_position) const |
| |
|
std::size_t | fwdsearch_impl (std::size_t start_position, int delta) const |
| |
|
std::size_t | bwdsearch_impl (std::size_t start_position, int delta) const |
| |
|
std::size_t | range_min_query_pos_impl (std::size_t range_begin, std::size_t range_end) const |
| |
|
int | range_min_query_val_impl (std::size_t range_begin, std::size_t range_end) const |
| |
| RangeMinQueryResult | range_min_query_result (std::size_t range_begin, std::size_t range_end) const |
| | Return the first minimum position and value in one traversal.
|
| |
|
std::size_t | range_max_query_pos_impl (std::size_t range_begin, std::size_t range_end) const |
| |
|
int | range_max_query_val_impl (std::size_t range_begin, std::size_t range_end) const |
| |
| std::size_t | memory_usage_bytes () const |
| | Return owned auxiliary memory usage in bytes.
|
| |
|
std::size_t | mincount_impl (std::size_t range_begin, std::size_t range_end) const |
| |
|
std::size_t | minselect_impl (std::size_t range_begin, std::size_t range_end, std::size_t rank) const |
| |
|
std::size_t | close_impl (std::size_t open_position) const |
| |
|
std::size_t | open_impl (std::size_t close_position) const |
| |
|
std::size_t | enclose_impl (std::size_t position) const |
| |
|
std::size_t | size () const |
| | Number of bits in the represented sequence.
|
| |
|
std::size_t | rank1 (std::size_t end_position) const |
| | Count 1 bits in the prefix [0, end_position).
|
| |
|
std::size_t | rank0 (std::size_t end_position) const |
| | Count 0 bits in the prefix [0, end_position).
|
| |
| std::size_t | select1 (std::size_t rank) const |
| | Return the zero-based position of the rank-th 1 bit.
|
| |
| std::size_t | select0 (std::size_t rank) const |
| | Return the zero-based position of the rank-th 0 bit.
|
| |
| std::size_t | rank10 (std::size_t end_position) const |
| | Count "10" bit patterns fully contained in [0, end_position).
|
| |
| std::size_t | select10 (std::size_t rank) const |
| | Return the zero-based start position of the rank-th "10" pattern.
|
| |
|
int | excess (std::size_t end_position) const |
| | Prefix excess on [0, end_position): +1 for 1 bits, -1 for 0 bits.
|
| |
| std::size_t | fwdsearch (std::size_t start_position, int delta) const |
| | Forward excess search from a prefix boundary.
|
| |
| std::size_t | bwdsearch (std::size_t start_position, int delta) const |
| | Backward excess search from a prefix boundary.
|
| |
| std::size_t | range_min_query_pos (std::size_t range_begin, std::size_t range_end) const |
| | Position of the first minimum relative excess in [range_begin, range_end].
|
| |
| int | range_min_query_val (std::size_t range_begin, std::size_t range_end) const |
| | Minimum relative excess value over [range_begin, range_end].
|
| |
| std::size_t | range_max_query_pos (std::size_t range_begin, std::size_t range_end) const |
| | Position of the first maximum relative excess in [range_begin, range_end].
|
| |
| int | range_max_query_val (std::size_t range_begin, std::size_t range_end) const |
| | Maximum relative excess value over [range_begin, range_end].
|
| |
|
std::size_t | mincount (std::size_t range_begin, std::size_t range_end) const |
| | Count positions attaining the minimum relative excess in [range_begin, range_end].
|
| |
| std::size_t | minselect (std::size_t range_begin, std::size_t range_end, std::size_t rank) const |
| | Select a position attaining the minimum relative excess in [range_begin, range_end].
|
| |
| std::size_t | close (std::size_t open_position) const |
| | Matching closing parenthesis for the parenthesis at open_position.
|
| |
| std::size_t | open (std::size_t close_position) const |
| | Matching opening parenthesis for the parenthesis at close_position.
|
| |
| std::size_t | enclose (std::size_t open_position) const |
| | Closest opening parenthesis strictly enclosing position.
|
| |
|
int | bit (const size_t &position) const noexcept |
| | Read bit at position position (LSB-first across words).
|
| |
template<std::size_t HighCacheLines = 4, std::size_t LowFanout = 32>
class pixie::experimental::RmMBTree< HighCacheLines, LowFanout >
Cache-aligned btree implementation of the range min-max index.
RmMBTree is a non-owning succinct index over a little-endian bit sequence. It provides the RmMBase operations by combining a rank/select helper with a hierarchy of min-max summaries over fixed 512-bit blocks. Each summary stores subtree size, number of ones, total excess, minimum/maximum relative excess, and minimum multiplicity, which lets searches skip whole subtrees when the requested excess cannot occur there.
The internal layout has three layers:
- the original bit words, referenced by
std::span<const uint64_t>;
- level 0 block summaries, reconstructed from parent nodes and scanned with 128-bit chunk primitives inside each 512-bit block;
- higher btree levels stored as cache-line-aligned summary nodes. The first level above blocks uses compact
int16_t excess fields because one low node covers at most 512 * LowFanout bits. Higher levels use int64_t excess and count fields.
Low nodes are one-cache-line-aligned arrays of compact per-child summaries:
LowNode<LowFanout = 32>
+-----------------------+
| cumulative
excess | int16_t prefix_excess[32], prefix through child
+-----------------------+
| child relative min | int16_t min_excess[32]
+-----------------------+
| child relative max | int16_t max_excess[32]
+-----------------------+
| count of minima | uint16_t min_count[32]
+-----------------------+
int excess(std::size_t end_position) const
Definition rmm.h:92
High nodes have the same logical fields, but use wider lanes and a fanout chosen from HighCacheLines:
HighNode<kHighFanout>
+-----------------------+
| cumulative
excess | int64_t prefix_excess[kHighFanout], prefix
| | through child
+-----------------------+
| child relative min | int64_t min_excess[kHighFanout]
+-----------------------+
| child relative max | int64_t max_excess[kHighFanout]
+-----------------------+
| count of minima | uint64_t min_count[kHighFanout]
+-----------------------+
Forward and backward excess searches ascend from the starting block until a sibling summary can contain the target, then descend through matching child ranges. Node scans use SIMD helpers from bits.h when available: low nodes compare 16 int16_t lanes at a time, and high nodes compare four int64_t lanes at a time. Scalar fallbacks are kept for partial chunks and targets that cannot be represented in the low-node lane type.
- Template Parameters
-
| HighCacheLines | Number of 64-byte cache lines assigned to one high summary node. |
| LowFanout | Number of child summaries stored in one low-level node. |
Public Member Functions inherited from pixie::RmMBase< RmMBTree< 4, 32 > >
1.13.2