Implements a small and efficient set over integers in the range of 0 to 63 (including). More...

#include <ADT.hpp>

Collaboration diagram for m::SmallBitset:

Data Structures
struct	iterator

struct	Proxy
	A proxy to access single elements in `SmallBitset`. More...

struct	reverse_iterator

Public Member Functions
	SmallBitset ()

	SmallBitset (uint64_t bits)

Proxy< true >	operator() (std::size_t offset) const
	Returns the `offset`-th bit.

Proxy< false >	operator() (std::size_t offset)
	Returns the `offset`-th bit.

Proxy< true >	operator[] (std::size_t offset) const
	Returns the `offset`-th bit.

Proxy< false >	operator[] (std::size_t offset)
	Returns the `offset`-th bit.

Proxy< true >	at (std::size_t offset) const
	Returns a proxy to the bit at offset `offset`.

Proxy< false >	at (std::size_t offset)
	Returns a proxy to the bit at offset `offset`.

constexpr std::size_t	capacity ()
	Returns the maximum capacity.

std::size_t	size () const
	Returns the number of elements in this `SmallBitset`.

bool	empty () const
	Returns `true` if there are no elements in this `SmallBitset`.

bool	is_singleton () const

SmallBitset	hi () const
	Returns the highest set bit as a `SmallBitset`.

auto	begin () const

auto	cbegin () const

auto	end () const

auto	cend () const

auto	rbegin () const

auto	crbegin () const

auto	rend () const

auto	crend () const

	operator uint64_t () const
	Convert the `SmallBitset` type to `uint64_t`.

	operator bool () const

bool	operator== (SmallBitset other) const

bool	operator!= (SmallBitset other) const

SmallBitset	operator~ () const
	Inverts all bits in the bitset.

bool	is_subset (SmallBitset other) const
	Returns `true` if the set represented by `this` is a subset of `other`, i.e. `this` ⊆ `other`.

SmallBitset	mask_to_lo () const
	Returns a mask up to and including the lowest set bit.

SmallBitset	singleton_to_lo_mask () const
	Converts a singleton set to a mask up to – but not including – the single, set bit.

SmallBitset &	operator\|= (SmallBitset other)

SmallBitset &	operator&= (SmallBitset other)

SmallBitset &	operator-= (SmallBitset other)

SmallBitset &	operator++ ()
	Treat this `SmallBitset` as an element of the power set of 2^n bits, where n is the number of bits that fit into `SmallBitset`.

SmallBitset	operator++ (int)
	Treat this `SmallBitset` as an element of the power set of 2^n bits, where n is the number of bits that fit into `SmallBitset`.

SmallBitset &	operator-- ()
	Treat this `SmallBitset` as an element of the power set of 2^n bits, where n is the number of bits that fit into `SmallBitset`.

SmallBitset	operator-- (int)
	Treat this `SmallBitset` as an element of the power set of 2^n bits, where n is the number of bits that fit into `SmallBitset`.

void	print_fixed_length (std::ostream &out, std::size_t size) const
	Print a textual representation of `this` with `size` bits to `out`.

void	dump (std::ostream &out) const

void	dump () const

Static Public Member Functions
static SmallBitset	All (std::size_t n)
	Factory method for creating a SmallBitset with first n bits set.

static SmallBitset	Singleton (std::size_t n)
	Factory method for creating a Singleton Smallbitset with `n` -th bit set.

Static Public Attributes
static constexpr std::size_t	CAPACITY = 64
	the maximum capacity of a `SmallBitset`

Private Attributes
uint64_t	bits_
	the bit vector representing the set

Friends
SmallBitset	unify (SmallBitset left, SmallBitset right)
	Returns the union of `left` and `right`, i.e. `left` ∪ `right`.

SmallBitset	intersect (SmallBitset left, SmallBitset right)
	Returns the intersection of `left` and `right`, i.e. `left` ∩ `right`.

SmallBitset	subtract (SmallBitset left, SmallBitset right)
	Returns the set where the elements of `right` have been subtracted from `left`, i.e. `left` - `right`.

SmallBitset	operator\| (SmallBitset left, SmallBitset right)
	Returns the union of `left` and `right`, i.e. `left` ∪ `right`.

SmallBitset	operator& (SmallBitset left, SmallBitset right)
	Returns the intersection of `left` and `right`, i.e. `left` ∩ `right`.

SmallBitset	operator- (SmallBitset left, SmallBitset right)
	Returns the set where the elements of `right` have been subtracted from `left`, i.e. `left` - `right`.

M_LCOV_EXCL_START friend std::ostream &	operator<< (std::ostream &out, SmallBitset s)
	Write a textual representation of `s` to `out`.

Detailed Description

Implements a small and efficient set over integers in the range of 0 to 63 (including).

Definition at line 25 of file ADT.hpp.

Constructor & Destructor Documentation

◆ SmallBitset() [1/2]

m::SmallBitset::SmallBitset ( )

inline

Definition at line 113 of file ADT.hpp.

Referenced by All(), m::SmallBitset::iterator::as_set(), mask_to_lo(), operator~(), Singleton(), and singleton_to_lo_mask().

◆ SmallBitset() [2/2]

m::SmallBitset::SmallBitset ( uint64_t bits )

inlineexplicit

Definition at line 114 of file ADT.hpp.

Member Function Documentation

◆ All()

static SmallBitset m::SmallBitset::All ( std::size_t n )

inlinestatic

Factory method for creating a SmallBitset with first n bits set.

Definition at line 117 of file ADT.hpp.

References CAPACITY, M_insist, and SmallBitset().

Referenced by m::pe::hs::search_states::EdgesBottomUp::compute_datasource_to_subproblem_index(), m::pe::hs::search_states::EdgePtrBottomUp::compute_datasource_to_subproblem_index(), m::Optimizer::construct_join_order(), m::GospersHack::enumerate_all(), generate_correlated_cardinalities(), generate_uncorrelated_cardinalities(), m::PlanTableBase< Actual >::get_final(), m::pe::hs::goo_path_completion(), m::pe::hs::heuristic_search(), m::Spn::learn_spn(), main(), m::AdjacencyMatrix::minimum_spanning_forest(), m::pe::hs::heuristics::avg_sel< PlanTable, State, BottomUp >::operator()(), m::pe::hs::heuristics::GOO< PlanTable, State, BottomUp >::operator()(), m::pe::hs::expansions::BottomUpComplete::operator()(), m::pe::hs::expansions::TopDownComplete::operator()(), m::pe::DPccp::operator()(), m::pe::TDGOO::operator()(), TDbasic::operator()(), TDMinCutAGaT::operator()(), m::Optimizer::optimize_join_order(), m::Optimizer::optimize_plan(), m::pe::hs::expansions::TopDown::reset_marked(), and m::pe::hs::search_states::SubproblemsArray::Top().

◆ at() [1/2]

Proxy< false > m::SmallBitset::at ( std::size_t offset )

inline

Returns a proxy to the bit at offset offset.

Throws m::out_of_range if offset is not in range [0; CAPACITY).

Definition at line 152 of file ADT.hpp.

References CAPACITY, and operator()().

◆ at() [2/2]

Proxy< true > m::SmallBitset::at ( std::size_t offset ) const

inline

Returns a proxy to the bit at offset offset.

Throws m::out_of_range if offset is not in range [0; CAPACITY).

Definition at line 144 of file ADT.hpp.

References CAPACITY, and operator()().

◆ begin()

auto m::SmallBitset::begin ( ) const

inline

Definition at line 173 of file ADT.hpp.

References bits_.

Referenced by cbegin(), m::Optimizer::construct_join_order(), m::Spn::create_product_min_slice(), emit_query_slice(), m::CartesianProductEstimator::estimate_scan(), m::InjectionCardinalityEstimator::estimate_scan(), m::SpnEstimator::estimate_scan(), m::AdjacencyMatrix::for_each_CSG_undirected(), generate_uncorrelated_cardinalities(), m::AdjacencyMatrix::is_connected(), m::MinCutAGaT::min_cut_advanced_generate_and_test(), m::AdjacencyMatrix::minimum_spanning_forest(), m::pe::hs::expansions::BottomUpComplete::operator()(), m::CartesianProductEstimator::operator()(), m::InjectionCardinalityEstimator::operator()(), m::SpnEstimator::operator()(), m::MinCutAGaT::partition(), m::Spn::Product::print(), m::pe::hs::search_states::SubproblemsArray::SubproblemsArray(), m::Spn::Product::update(), and m::PartialPlanGenerator::write_partial_plans_JSON().

◆ capacity()

constexpr std::size_t m::SmallBitset::capacity ( )

inlineconstexpr

Returns the maximum capacity.

Definition at line 159 of file ADT.hpp.

References CAPACITY.

Referenced by PEall::operator()(), and DPsubOpt::operator()().

◆ cbegin()

auto m::SmallBitset::cbegin ( ) const

inline

Definition at line 174 of file ADT.hpp.

References begin().

◆ cend()

auto m::SmallBitset::cend ( ) const

inline

Definition at line 176 of file ADT.hpp.

References end().

◆ crbegin()

auto m::SmallBitset::crbegin ( ) const

inline

Definition at line 179 of file ADT.hpp.

References rbegin().

◆ crend()

auto m::SmallBitset::crend ( ) const

inline

Definition at line 181 of file ADT.hpp.

References rend().

◆ dump() [1/2]

void SmallBitset::dump ( ) const

Definition at line 8 of file ADT.cpp.

References dump().

Referenced by dump().

◆ dump() [2/2]

M_LCOV_EXCL_START void SmallBitset::dump ( std::ostream & out ) const

Definition at line 7 of file ADT.cpp.

◆ empty()

bool m::SmallBitset::empty ( ) const

inline

Returns true if there are no elements in this SmallBitset.

Definition at line 163 of file ADT.hpp.

References bits_.

Referenced by m::pe::hs::search_states::EdgesBottomUp::compute_datasource_to_subproblem_index(), m::pe::hs::search_states::EdgePtrBottomUp::compute_datasource_to_subproblem_index(), m::pe::TDGOO::for_each_join(), m::AdjacencyMatrix::is_connected(), mask_to_lo(), m::MinCutAGaT::min_cut_advanced_generate_and_test(), operator bool(), m::pe::hs::expansions::BottomUpComplete::operator()(), m::CartesianProductEstimator::operator()(), m::SpnEstimator::operator()(), m::MinCutAGaT::partition(), m::AdjacencyMatrix::tree_directed_away_from(), and m::PlanTableBase< Actual >::update().

◆ end()

auto m::SmallBitset::end ( ) const

inline

Definition at line 175 of file ADT.hpp.

Referenced by cend(), emit_query_slice(), m::AdjacencyMatrix::for_each_CSG_undirected(), generate_uncorrelated_cardinalities(), m::MinCutAGaT::min_cut_advanced_generate_and_test(), m::CartesianProductEstimator::operator()(), m::InjectionCardinalityEstimator::operator()(), m::SpnEstimator::operator()(), and m::Spn::Product::update().

◆ hi()

SmallBitset m::SmallBitset::hi ( ) const

inline

Returns the highest set bit as a SmallBitset.

Definition at line 168 of file ADT.hpp.

References bits_, and Singleton().

Referenced by m::AdjacencyMatrix::for_each_CSG_pair_undirected().

◆ is_singleton()

bool m::SmallBitset::is_singleton ( ) const

inline

Definition at line 165 of file ADT.hpp.

References size().

Referenced by m::AdjacencyMatrix::for_each_CSG_undirected(), m::pe::TDGOO::for_each_join(), IKKBZ::linearize(), m::MinCutAGaT::min_cut_advanced_generate_and_test(), m::AdjacencyMatrix::minimum_spanning_forest(), m::pe::hs::heuristics::sqrt_sum< PlanTable, State, TopDown >::operator()(), m::pe::hs::heuristics::sum< PlanTable, State, TopDown >::operator()(), m::MinCutAGaT::partition(), m::PlanTableSmallOrDense::reset_costs(), singleton_to_lo_mask(), m::AdjacencyMatrix::tree_directed_away_from(), and m::PartialPlanGenerator::write_partial_plans_JSON().

◆ is_subset()

bool m::SmallBitset::is_subset ( SmallBitset other ) const

inline

Returns true if the set represented by this is a subset of other, i.e. this ⊆ other.

Definition at line 194 of file ADT.hpp.

References bits_.

Referenced by m::Optimizer::construct_join_order(), and m::MinCutAGaT::min_cut_advanced_generate_and_test().

◆ mask_to_lo()

SmallBitset m::SmallBitset::mask_to_lo ( ) const

inline

Returns a mask up to and including the lowest set bit.

Definition at line 197 of file ADT.hpp.

References bits_, empty(), M_insist, and SmallBitset().

Referenced by m::AdjacencyMatrix::for_each_CSG_pair_undirected(), and m::AdjacencyMatrix::for_each_CSG_undirected().

◆ operator bool()

m::SmallBitset::operator bool ( ) const

inlineexplicit

Definition at line 185 of file ADT.hpp.

References empty().

◆ operator uint64_t()

m::SmallBitset::operator uint64_t ( ) const

inlineexplicit

Convert the SmallBitset type to uint64_t.

Definition at line 184 of file ADT.hpp.

References bits_.

◆ operator!=()

bool m::SmallBitset::operator!= ( SmallBitset other ) const

inline

Definition at line 188 of file ADT.hpp.

References operator==().

◆ operator&=()

SmallBitset & m::SmallBitset::operator&= ( SmallBitset other )

inline

Definition at line 226 of file ADT.hpp.

◆ operator()() [1/2]

Proxy< false > m::SmallBitset::operator() ( std::size_t offset )

inline

Returns the offset-th bit.

Requires that offset is in range [0; CAPACITY).

Definition at line 134 of file ADT.hpp.

◆ operator()() [2/2]

Proxy< true > m::SmallBitset::operator() ( std::size_t offset ) const

inline

Returns the offset-th bit.

Requires that offset is in range [0; CAPACITY).

Definition at line 131 of file ADT.hpp.

Referenced by at(), and operator[]().

◆ operator++() [1/2]

SmallBitset & m::SmallBitset::operator++ ( )

inline

Treat this SmallBitset as an element of the power set of 2^n bits, where n is the number of bits that fit into SmallBitset.

Then this method advances to the next set in the power set. The behavior is undefined if all bits are already set.

Definition at line 232 of file ADT.hpp.

References bits_, and M_insist.

◆ operator++() [2/2]

SmallBitset m::SmallBitset::operator++ ( int )

inline

Treat this SmallBitset as an element of the power set of 2^n bits, where n is the number of bits that fit into SmallBitset.

Then this method advances to the next set in the power set. The behavior is undefined if all bits are already set.

Definition at line 236 of file ADT.hpp.

References operator++().

Referenced by operator++().

◆ operator--() [1/2]

SmallBitset & m::SmallBitset::operator-- ( )

inline

Treat this SmallBitset as an element of the power set of 2^n bits, where n is the number of bits that fit into SmallBitset.

Then this method advances to the previous set in the power set. The behavior is undefined if no bits are set.

Definition at line 241 of file ADT.hpp.

References bits_, and M_insist.

◆ operator--() [2/2]

SmallBitset m::SmallBitset::operator-- ( int )

inline

Treat this SmallBitset as an element of the power set of 2^n bits, where n is the number of bits that fit into SmallBitset.

Then this method advances to the previous set in the power set. The behavior is undefined if no bits are set.

Definition at line 245 of file ADT.hpp.

References operator--().

Referenced by operator--().

◆ operator-=()

SmallBitset & m::SmallBitset::operator-= ( SmallBitset other )

inline

Definition at line 227 of file ADT.hpp.

◆ operator==()

bool m::SmallBitset::operator== ( SmallBitset other ) const

inline

Definition at line 187 of file ADT.hpp.

References bits_.

Referenced by operator!=().

◆ operator[]() [1/2]

Proxy< false > m::SmallBitset::operator[] ( std::size_t offset )

inline

Returns the offset-th bit.

Requires that offset is in range [0; CAPACITY).

Definition at line 140 of file ADT.hpp.

References operator()().

◆ operator[]() [2/2]

Proxy< true > m::SmallBitset::operator[] ( std::size_t offset ) const

inline

Returns the offset-th bit.

Requires that offset is in range [0; CAPACITY).

Definition at line 137 of file ADT.hpp.

References operator()().

◆ operator|=()

SmallBitset & m::SmallBitset::operator|= ( SmallBitset other )

inline

Definition at line 225 of file ADT.hpp.

◆ operator~()

SmallBitset m::SmallBitset::operator~ ( ) const

inline

Inverts all bits in the bitset.

Definition at line 191 of file ADT.hpp.

References bits_, and SmallBitset().

◆ print_fixed_length()

void m::SmallBitset::print_fixed_length	(	std::ostream &	out,
		std::size_t	size
	)		const

inline

Print a textual representation of this with size bits to out.

Definition at line 256 of file ADT.hpp.

References size().

◆ rbegin()

auto m::SmallBitset::rbegin ( ) const

inline

Definition at line 178 of file ADT.hpp.

References bits_.

Referenced by crbegin().

◆ rend()

auto m::SmallBitset::rend ( ) const

inline

Definition at line 180 of file ADT.hpp.

Referenced by crend().

◆ Singleton()

static SmallBitset m::SmallBitset::Singleton ( std::size_t n )

inlinestatic

Factory method for creating a Singleton Smallbitset with n -th bit set.

Definition at line 125 of file ADT.hpp.

References CAPACITY, M_insist, and SmallBitset().

Referenced by m::SmallBitset::reverse_iterator::as_set(), m::pe::hs::search_states::SubproblemsArray::Bottom(), m::pe::hs::search_states::EdgesBottomUp::compute_datasource_to_subproblem_index(), m::pe::hs::search_states::EdgePtrBottomUp::compute_datasource_to_subproblem_index(), generate_uncorrelated_cardinalities(), hi(), IKKBZ::linearize(), main(), m::AdjacencyMatrix::minimum_spanning_forest(), m::pe::GOO::operator()(), PEall::operator()(), DPsubOpt::operator()(), IKKBZ::operator()(), m::Optimizer::optimize_source_plans(), m::pe::hs::search_states::SubproblemTableBottomUp::SubproblemTableBottomUp(), and m::AdjacencyMatrix::transitive_closure_directed().

◆ singleton_to_lo_mask()

SmallBitset m::SmallBitset::singleton_to_lo_mask ( ) const

inline

Converts a singleton set to a mask up to – but not including – the single, set bit.

Definition at line 207 of file ADT.hpp.

References bits_, is_singleton(), M_insist, and SmallBitset().

◆ size()

std::size_t m::SmallBitset::size ( ) const

inline

Returns the number of elements in this SmallBitset.

Definition at line 161 of file ADT.hpp.

References bits_.

Referenced by m::Optimizer::construct_join_order(), m::CartesianProductEstimator::estimate_scan(), m::InjectionCardinalityEstimator::estimate_scan(), m::SpnEstimator::estimate_scan(), m::PlanTableSmallOrDense::has_plan(), m::PlanTableLargeAndSparse::has_plan(), is_singleton(), m::MinCutAGaT::min_cut_advanced_generate_and_test(), PEall::operator()(), DPsub::operator()(), DPsubOpt::operator()(), print_fixed_length(), and m::SubsetEnumerator::SubsetEnumerator().

Friends And Related Function Documentation

◆ intersect

SmallBitset intersect	(	SmallBitset	left,
		SmallBitset	right
	)

friend

Returns the intersection of left and right, i.e. left ∩ right.

Definition at line 215 of file ADT.hpp.

◆ operator&

SmallBitset operator&	(	SmallBitset	left,
		SmallBitset	right
	)

friend

Returns the intersection of left and right, i.e. left ∩ right.

Definition at line 221 of file ADT.hpp.

◆ operator-

SmallBitset operator-	(	SmallBitset	left,
		SmallBitset	right
	)

friend

Returns the set where the elements of right have been subtracted from left, i.e. left - right.

Definition at line 223 of file ADT.hpp.

◆ operator<<

M_LCOV_EXCL_START friend std::ostream & operator<<	(	std::ostream &	out,
		SmallBitset	s
	)

friend

Write a textual representation of s to out.

Definition at line 249 of file ADT.hpp.

◆ operator|

SmallBitset operator\|	(	SmallBitset	left,
		SmallBitset	right
	)

friend

Returns the union of left and right, i.e. left ∪ right.

Definition at line 219 of file ADT.hpp.

◆ subtract

SmallBitset subtract	(	SmallBitset	left,
		SmallBitset	right
	)

friend

Returns the set where the elements of right have been subtracted from left, i.e. left - right.

Definition at line 217 of file ADT.hpp.

◆ unify

SmallBitset unify	(	SmallBitset	left,
		SmallBitset	right
	)

friend

Returns the union of left and right, i.e. left ∪ right.

Definition at line 213 of file ADT.hpp.

Field Documentation

◆ bits_

uint64_t m::SmallBitset::bits_

private

the bit vector representing the set

Definition at line 57 of file ADT.hpp.

Referenced by begin(), empty(), hi(), is_subset(), mask_to_lo(), operator uint64_t(), operator++(), operator--(), operator==(), operator~(), rbegin(), singleton_to_lo_mask(), and size().

◆ CAPACITY

constexpr std::size_t m::SmallBitset::CAPACITY = 64

staticconstexpr

the maximum capacity of a SmallBitset

Definition at line 27 of file ADT.hpp.

Referenced by All(), at(), capacity(), m::SmallBitset::Proxy< C >::Proxy(), and Singleton().

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

include/mutable/util/ADT.hpp
src/util/ADT.cpp

Data Structures

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ SmallBitset() [1/2]

◆ SmallBitset() [2/2]

Member Function Documentation

◆ All()

◆ at() [1/2]

◆ at() [2/2]

◆ begin()

◆ capacity()

◆ cbegin()

◆ cend()

◆ crbegin()

◆ crend()

◆ dump() [1/2]

◆ dump() [2/2]

◆ empty()

◆ end()

◆ hi()

◆ is_singleton()

◆ is_subset()

◆ mask_to_lo()

◆ operator bool()

◆ operator uint64_t()

◆ operator!=()

◆ operator&=()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ operator++() [1/2]

◆ operator++() [2/2]

◆ operator--() [1/2]

◆ operator--() [2/2]

◆ operator-=()

◆ operator==()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ operator|=()

◆ operator~()

◆ print_fixed_length()

◆ rbegin()

◆ rend()

◆ Singleton()

◆ singleton_to_lo_mask()

◆ size()

Friends And Related Function Documentation

◆ intersect

◆ operator&

◆ operator-

◆ operator<<

◆ operator|

◆ subtract

◆ unify

Field Documentation

◆ bits_

◆ CAPACITY