pasta::bit_vector  v1.0.0
Compact and Fast Rank and Select Data Structure for Bit Vectors
Configuration

Configuration that can be used to change the behavior of the algorithms. More...

Classes

struct  pasta::FlatRankSelectConfig
 Static configuration for FlatRank and FlatRankSelect. More...
 
struct  pasta::PopcntRankSelectConfig
 Static configuration for Rank and RankSelect. More...
 
struct  pasta::WideRankSelectConfig
 Static configuration for WideRank and WideRankSelect. More...
 

Enumerations

enum class  pasta::FindL2FlatWith { LINEAR_SEARCH , BINARY_SEARCH , INTRINSICS }
 Enum used to specify whether intrinsic functions should be used. More...
 
enum class  pasta::FindL2WideWith { LINEAR_SEARCH , BINARY_SEARCH }
 Enum used to specify whether intrinsic functions should be used. More...
 
enum class  pasta::OptimizedFor { OptimizedFor::DONT_CARE , OptimizedFor::ONE_QUERIES , OptimizedFor::ZERO_QUERIES }
 Enum used to specify which queries the rank (and select) data structures should be optimized for. More...
 

Functions

constexpr bool pasta::use_linear_search (FindL2FlatWith const find_with)
 Helper function indicating whether a linear search function should be used. More...
 
constexpr bool pasta::use_binary_search (FindL2FlatWith const find_with)
 Helper function indicating whether a binary search function should be used. More...
 
constexpr bool pasta::use_intrinsics (FindL2FlatWith const find_with)
 Helper function indicating whether intrinsic function should be used. More...
 
constexpr bool pasta::use_linear_search (FindL2WideWith const find_with)
 Helper function indicating whether a linear search function should be used. More...
 
constexpr bool pasta::use_binary_search (FindL2WideWith const find_with)
 Helper function indicating whether a binary search function should be used. More...
 
constexpr bool pasta::optimize_one_or_dont_care (OptimizedFor const optimized_for)
 Helper function indicating if queries should be optimized for one queries or the caller does not care. More...
 

Detailed Description

Configuration that can be used to change the behavior of the algorithms.

Enumeration Type Documentation

◆ FindL2FlatWith

enum class pasta::FindL2FlatWith
strong

Enum used to specify whether intrinsic functions should be used.

Note that this does not necessarily mean that intrinsic functions are faster. Please refer to the benchmarks for real world practical results obtained in experiments.

◆ FindL2WideWith

enum class pasta::FindL2WideWith
strong

Enum used to specify whether intrinsic functions should be used.

Note that this does not necessarily mean that intrinsic functions are faster. Please refer to the benchmarks for real world practical results obtained in experiments.

◆ OptimizedFor

enum class pasta::OptimizedFor
strong

Enum used to specify which queries the rank (and select) data structures should be optimized for.

Throughout the rank and select data structures, we store information about the number of ones or zeros in 512 bit blocks. If we store the information for ones, the queries for zeros are more complicated and vice versa. This option allows to specify which query the data structure should be optimized for.

Enumerator
DONT_CARE 

It does not matter (both types are called equally often).

ONE_QUERIES 

rank_1 and select_1 queries should be optimized.

ZERO_QUERIES 

rank_0 and select_9 queries should be optimized.

Function Documentation

◆ optimize_one_or_dont_care()

constexpr bool pasta::optimize_one_or_dont_care ( OptimizedFor const  optimized_for)
constexpr

Helper function indicating if queries should be optimized for one queries or the caller does not care.

Parameters
optimized_forParameter indicating for what type of queries the data structure should be optimized.
Returns
true if the data structure should be optimized for one queries or the caller does not care for what queries the data structure is optimized for. false otherwise.

◆ use_binary_search() [1/2]

constexpr bool pasta::use_binary_search ( FindL2FlatWith const  find_with)
constexpr

Helper function indicating whether a binary search function should be used.

Parameters
find_withFindL2FlatWith indicating whether intrinsics should be used.
Returns
true if intrinsics should be used and false otherwise.

◆ use_binary_search() [2/2]

constexpr bool pasta::use_binary_search ( FindL2WideWith const  find_with)
constexpr

Helper function indicating whether a binary search function should be used.

Parameters
find_withFindL2WideWith indicating whether intrinsics should be used.
Returns
true if intrinsics should be used and false otherwise.

◆ use_intrinsics()

constexpr bool pasta::use_intrinsics ( FindL2FlatWith const  find_with)
constexpr

Helper function indicating whether intrinsic function should be used.

Parameters
find_withFindL2FlatWith indicating whether intrinsics should be used.
Returns
true if intrinsics should be used and false otherwise.

◆ use_linear_search() [1/2]

constexpr bool pasta::use_linear_search ( FindL2FlatWith const  find_with)
constexpr

Helper function indicating whether a linear search function should be used.

Parameters
find_withFindL2FlatWith indicating whether intrinsics should be used.
Returns
true if intrinsics should be used and false otherwise.

◆ use_linear_search() [2/2]

constexpr bool pasta::use_linear_search ( FindL2WideWith const  find_with)
constexpr

Helper function indicating whether a linear search function should be used.

Parameters
find_withFindL2WideWith indicating whether intrinsics should be used.
Returns
true if intrinsics should be used and false otherwise.