Pixie
Loading...
Searching...
No Matches
Public Member Functions | Static Public Attributes | List of all members
pixie::experimental::RmMBTree< HighCacheLines, LowFanout > Class Template Reference

Cache-aligned btree implementation of the range min-max index. More...

#include <rmm_btree.h>

Inheritance diagram for pixie::experimental::RmMBTree< HighCacheLines, LowFanout >:
pixie::RmMBase< RmMBTree< 4, 32 > >

Public Member Functions

 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.
 
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
 
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 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
 
- Public Member Functions inherited from pixie::RmMBase< RmMBTree< 4, 32 > >
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).
 

Static Public Attributes

static constexpr std::size_t npos
 
static constexpr std::size_t kBlockBits = 512
 
static constexpr std::size_t kBlockWords = kBlockBits / 64
 
static constexpr std::size_t kCacheLineBytes = 64
 
static constexpr std::size_t kLowFanout = LowFanout
 
static constexpr std::size_t kHighFanout
 
static constexpr std::size_t kMaxFanout = std::max(kLowFanout, kHighFanout)
 
- Static Public Attributes inherited from pixie::RmMBase< RmMBTree< 4, 32 > >
static constexpr std::size_t npos
 Sentinel returned by position queries when no valid answer exists.
 

Detailed Description

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]
+-----------------------+
pixie::RmMBase< RmMBTree< 4, 32 > >::excess
int excess(std::size_t end_position) const
Definition rmm_base.h:81

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
HighCacheLinesNumber of 64-byte cache lines assigned to one high summary node.
LowFanoutNumber of child summaries stored in one low-level node.

Constructor & Destructor Documentation

◆ RmMBTree()

template<std::size_t HighCacheLines = 4, std::size_t LowFanout = 32>
pixie::experimental::RmMBTree< HighCacheLines, LowFanout >::RmMBTree ( std::span< const std::uint64_t > words,
std::size_t bit_count,
std::size_t = kBlockBits )
inlineexplicit

Construct an RmM btree over an external bit-vector span.

The tree stores a non-owning view of words and builds its rank/select helper plus min-max summaries over the first bit_count bits. The optional block-size argument is accepted for API compatibility; this implementation uses the fixed 512-bit block size.

Parameters
wordsExternal little-endian 64-bit words that contain the bit sequence.
bit_countNumber of valid bits in words.

Member Data Documentation

◆ kHighFanout

template<std::size_t HighCacheLines = 4, std::size_t LowFanout = 32>
std::size_t pixie::experimental::RmMBTree< HighCacheLines, LowFanout >::kHighFanout
staticconstexpr
Initial value:
=
std::max<std::size_t>(2, (512 * HighCacheLines) / (4 * 64))

◆ npos

template<std::size_t HighCacheLines = 4, std::size_t LowFanout = 32>
std::size_t pixie::experimental::RmMBTree< HighCacheLines, LowFanout >::npos
staticconstexpr
Initial value:
=
RmMBase<RmMBTree<HighCacheLines, LowFanout>>::npos
pixie::RmMBase
CRTP facade for rank/select and range min-max tree operations.
Definition rmm_base.h:18
The documentation for this class was generated from the following file: