pasta::BigL12Type Struct Reference

Check that L12Type requires only 64 bits. More...

#include <l12_type.hpp>

Public Member Functions
	BigL12Type ()=default
	Constructor. Empty constructor required for tlx::SimpleVector.
	BigL12Type (uint64_t const _l1, std::array< uint16_t, 7 > &_l2)
	Constructor. Setting all values and packing the L2-block entries.
uint64_t	operator[] (size_t const index) const
	Access operator used to access the L2-block entries individually.
uint64_t	l1 () const
	Get the L1-value of the L12-block.

Public Attributes
__uint128_t	data
	All data of the BigL12Type packed into 128 bits.

Detailed Description

Check that L12Type requires only 64 bits.

Struct used to store L1- and L2-blocks for BitVectorFlatRank and BitVectorFlatRankSelect.

We store the L1-information of 8 L2-blocks in 40 bits and the corresponding seven L2-information in 12 bits each. Using 12 bits allows us to store the prefix sum of the popcounts in the 512-bit L2-blocks. All this can be stored in 128 bits. To be precise 124 bits would suffice, but the additional 4 bits allow for faster access and result in exactly the same overhead the non-flat popcount rank and select data structure has.

+---—+---—+---—+---—+---—+---—+—+---—+---—+-----—+ | 8bit | 8bit | 8bit | 8bit | 8bit | 8bit |...| 8bit | 8bit | 40 bit | +---—+---—+---—+---—+---—+---—+—+---—+---—+-----—+ | 3 * 12-bit integer | 3 * 12 bit integer |...| 12 bit int. | L1-info| +---—+---—+---—+---—+---—+---—+—+---—+---—+-----—+ | 8 | 4/4 | 8 | 8 | 4/4 | 8 |...| 8 | 4/4 + 40 Bit | +---—+---—+---—+---—+---—+---—+—+---—+---—+-----—+

The order of the 12-bit integers should remain the same (as they occur in the bit vector). This helps us to determine the correct block later on. To this end, we have to split

Constructor & Destructor Documentation

BigL12Type()

pasta::BigL12Type::BigL12Type ( uint64_t const _l1, std::array< uint16_t, 7 > & _l2 )

inline

Constructor. Setting all values and packing the L2-block entries.

Parameters

_l1	Value of the L1-block entry.
_l2	Values of the three L2-block entries ( asstd::array).

Member Function Documentation

l1()

uint64_t pasta::BigL12Type::l1 ( ) const

inline

Get the L1-value of the L12-block.

Returns

L1-value of the L12-block.

operator[]()

uint64_t pasta::BigL12Type::operator[] ( size_t const index ) const

inline

Access operator used to access the L2-block entries individually.

Parameters

index

The index (0 to 6) of the L2-block.

Returns

Popcount of the corresponding L2-block.

---

The documentation for this struct was generated from the following file:

• include/pasta/bit_vector/support/l12_type.hpp