souffle::SparseBitMap< BITS > Class Template Reference

A sparse bit-map is a bit map virtually assigning a bit value to every value if the uint32_t domain. More...

#include <Brie.h>

Collaboration diagram for souffle::SparseBitMap< BITS >:

Data Structures
struct	merge_op

Public Types
using	index_type = typename data_store_t::index_type
using	iterator = SparseBitMapIter< this_t >
using	op_context = typename data_store_t::op_context

Public Member Functions
void	addAll (const SparseBitMap &other)
	Sets all bits set in other to 1 within this bit map. More...
iterator	begin () const
	Obtains an iterator pointing to the first index set to 1. More...
void	clear ()
	Resets all contained bits to 0. More...
void	dump (bool detail=false, std::ostream &out=std::cout) const
	A debugging utility printing the internal structure of this map to the given output stream. More...
bool	empty () const
iterator	end () const
	Returns an iterator referencing the position after the last set bit. More...
iterator	find (index_type i) const
	Obtains an iterator referencing the position i if the corresponding bit is set, end() otherwise. More...
iterator	find (index_type i, op_context &ctxt) const
	Obtains an iterator referencing the position i if the corresponding bit is set, end() otherwise. More...
std::size_t	getMemoryUsage () const
	Computes the total memory usage of this data structure. More...
const data_store_t &	getStore () const
	Provides write-protected access to the internal store for running analysis on the data structure. More...
iterator	lower_bound (index_type i) const
	Locates an iterator to the first element in this sparse bit map not less than the given index. More...
SparseBitMap &	operator= (const SparseBitMap &)=default
SparseBitMap &	operator= (SparseBitMap &&)=default
bool	operator[] (index_type i) const
	Determines the whether the bit addressed by i is set or not. More...
bool	set (index_type i)
	Sets the bit addressed by i to 1. More...
bool	set (index_type i, op_context &ctxt)
	Sets the bit addressed by i to 1. More...
std::size_t	size () const
	Determines the number of bits set. More...
	SparseBitMap ()=default
	SparseBitMap (const SparseBitMap &)=default
	SparseBitMap (SparseBitMap &&)=default
bool	test (index_type i) const
	Determines the whether the bit addressed by i is set or not. More...
bool	test (index_type i, op_context &ctxt) const
	Determines the whether the bit addressed by i is set or not. More...
iterator	upper_bound (index_type i) const
	Locates an iterator to the first element in this sparse bit map than is greater than the given index. More...

Private Types
using	atomic_value_t = typename data_store_t::atomic_value_type
using	data_store_t = SparseArray< value_t, BITS, merge_op >
using	this_t = SparseBitMap< BITS >
using	value_t = uint64_t

Static Private Member Functions
static uint64_t	toMask (const value_t &value)

Private Attributes
data_store_t	store

Static Private Attributes
static constexpr size_t	BITS_PER_ENTRY = sizeof(value_t) * CHAR_BIT
static constexpr uint64_t	LEAF_INDEX_MASK = BITS_PER_ENTRY - 1
static constexpr size_t	LEAF_INDEX_WIDTH = __builtin_ctz(BITS_PER_ENTRY)

Friends
template<typename A >
class	detail::brie::SparseBitMapIter

Detailed Description

template<unsigned BITS = 4>
class souffle::SparseBitMap< BITS >

A sparse bit-map is a bit map virtually assigning a bit value to every value if the uint32_t domain.

However, only 1-bits are stored utilizing a nested sparse array structure.

Template Parameters

BITS	similar to the BITS parameter of the sparse array type

Definition at line 1637 of file Brie.h.

Member Typedef Documentation

atomic_value_t

template<unsigned BITS = 4>

using souffle::SparseBitMap< BITS >::atomic_value_t = typename data_store_t::atomic_value_type

private

Definition at line 1655 of file Brie.h.

data_store_t

template<unsigned BITS = 4>

using souffle::SparseBitMap< BITS >::data_store_t = SparseArray<value_t, BITS, merge_op>

private

Definition at line 1654 of file Brie.h.

index_type

template<unsigned BITS = 4>

using souffle::SparseBitMap< BITS >::index_type = typename data_store_t::index_type

Definition at line 1669 of file Brie.h.

iterator

template<unsigned BITS = 4>

using souffle::SparseBitMap< BITS >::iterator = SparseBitMapIter<this_t>

Definition at line 1810 of file Brie.h.

op_context

template<unsigned BITS = 4>

using souffle::SparseBitMap< BITS >::op_context = typename data_store_t::op_context

Definition at line 1697 of file Brie.h.

this_t

template<unsigned BITS = 4>

using souffle::SparseBitMap< BITS >::this_t = SparseBitMap<BITS>

private

Definition at line 1641 of file Brie.h.

value_t

template<unsigned BITS = 4>

using souffle::SparseBitMap< BITS >::value_t = uint64_t

private

Definition at line 1644 of file Brie.h.

Constructor & Destructor Documentation

SparseBitMap() [1/3]

template<unsigned BITS = 4>

souffle::SparseBitMap< BITS >::SparseBitMap ( )

default

SparseBitMap() [2/3]

template<unsigned BITS = 4>

souffle::SparseBitMap< BITS >::SparseBitMap ( const SparseBitMap< BITS > &  )

default

SparseBitMap() [3/3]

template<unsigned BITS = 4>

souffle::SparseBitMap< BITS >::SparseBitMap ( SparseBitMap< BITS > &&  )

default

Member Function Documentation

addAll()

template<unsigned BITS = 4>

void souffle::SparseBitMap< BITS >::addAll ( const SparseBitMap< BITS > &  other )

inline

Sets all bits set in other to 1 within this bit map.

Definition at line 1798 of file Brie.h.

                           {
        auto it = store.begin();
        if (it.isEnd()) return end();
        return iterator(it);
    }

References souffle::SparseArray< T, BITS, merge_op, copy_op >::begin().

Here is the call graph for this function:

begin()

template<unsigned BITS = 4>

iterator souffle::SparseBitMap< BITS >::begin ( ) const

inline

Obtains an iterator pointing to the first index set to 1.

If there is no such bit, end() will be returned.

Definition at line 1816 of file Brie.h.

                                      {
        op_context ctxt;
        return find(i, ctxt);
    }

References i.

clear()

template<unsigned BITS = 4>

void souffle::SparseBitMap< BITS >::clear ( )

inline

Resets all contained bits to 0.

Definition at line 1771 of file Brie.h.

References souffle::SparseArray< T, BITS, merge_op, copy_op >::getMemoryUsage().

Here is the call graph for this function:

dump()

template<unsigned BITS = 4>

void souffle::SparseBitMap< BITS >::dump ( bool  detail = false, std::ostream &  out = std::cout  ) const

inline

A debugging utility printing the internal structure of this map to the given output stream.

Definition at line 1906 of file Brie.h.

                     {
 

empty()

template<unsigned BITS = 4>

bool souffle::SparseBitMap< BITS >::empty ( ) const

inline

Definition at line 1692 of file Brie.h.

                                             {

References souffle::SparseArray< T, BITS, merge_op, copy_op >::getAtomic(), and i.

Here is the call graph for this function:

end()

template<unsigned BITS = 4>

iterator souffle::SparseBitMap< BITS >::end ( ) const

inline

Returns an iterator referencing the position after the last set bit.

Definition at line 1825 of file Brie.h.

                                                        {

References souffle::SparseArray< T, BITS, merge_op, copy_op >::find(), and i.

Referenced by souffle::detail::brie::fix_first_nested< Dim >::operator()(), and souffle::detail::brie::fix_binding< 0, Dim, Dim >::operator()().

Here is the call graph for this function:

find() [1/2]

template<unsigned BITS = 4>

iterator souffle::SparseBitMap< BITS >::find ( index_type  i ) const

inline

Obtains an iterator referencing the position i if the corresponding bit is set, end() otherwise.

Definition at line 1833 of file Brie.h.

                                             {

Referenced by souffle::detail::brie::fix_first_nested< Dim >::operator()().

find() [2/2]

template<unsigned BITS = 4>

iterator souffle::SparseBitMap< BITS >::find ( index_type  i, op_context &  ctxt  ) const

inline

Obtains an iterator referencing the position i if the corresponding bit is set, end() otherwise.

An operation context can be provided to exploit temporal locality.

Definition at line 1843 of file Brie.h.

                                             {
        auto it = store.lowerBound(i >> LEAF_INDEX_WIDTH);
        if (it.isEnd()) return end();
 
        // check bit-set part
        uint64_t mask = toMask(it->second);
 
        // if there is no bit remaining in this mask, check next mask.
        if (!(mask & ((~uint64_t(0)) << (i & LEAF_INDEX_MASK)))) {
            index_type next = ((i >> LEAF_INDEX_WIDTH) + 1) << LEAF_INDEX_WIDTH;
            if (next < i) return end();

References i, and souffle::SparseArray< T, BITS, merge_op, copy_op >::lowerBound().

Here is the call graph for this function:

getMemoryUsage()

template<unsigned BITS = 4>

std::size_t souffle::SparseBitMap< BITS >::getMemoryUsage ( ) const

inline

Computes the total memory usage of this data structure.

Definition at line 1790 of file Brie.h.

                           {

getStore()

template<unsigned BITS = 4>

const data_store_t& souffle::SparseBitMap< BITS >::getStore ( ) const

inline

Provides write-protected access to the internal store for running analysis on the data structure.

Definition at line 1914 of file Brie.h.

                   {

lower_bound()

template<unsigned BITS = 4>

iterator souffle::SparseBitMap< BITS >::lower_bound ( index_type  i ) const

inline

Locates an iterator to the first element in this sparse bit map not less than the given index.

Definition at line 1861 of file Brie.h.

                                             {
        if (i == std::numeric_limits<index_type>::max()) {
            return end();
        }
        return lower_bound(i + 1);
    }
 
    /**
     * A debugging utility printing the internal structure of this map to the
     * given output stream.
     */

Referenced by souffle::detail::brie::fix_binding< 0, Dim, Dim >::operator()().

operator=() [1/2]

template<unsigned BITS = 4>

SparseBitMap& souffle::SparseBitMap< BITS >::operator= ( const SparseBitMap< BITS > &  )

default

operator=() [2/2]

template<unsigned BITS = 4>

SparseBitMap& souffle::SparseBitMap< BITS >::operator= ( SparseBitMap< BITS > &&  )

default

operator[]()

template<unsigned BITS = 4>

bool souffle::SparseBitMap< BITS >::operator[] ( index_type  i ) const

inline

Determines the whether the bit addressed by i is set or not.

Definition at line 1764 of file Brie.h.

                             : store) {
            res += __builtin_popcountll(cur.second);

set() [1/2]

template<unsigned BITS = 4>

bool souffle::SparseBitMap< BITS >::set ( index_type  i )

inline

Sets the bit addressed by i to 1.

Definition at line 1702 of file Brie.h.

                     {

set() [2/2]

template<unsigned BITS = 4>

bool souffle::SparseBitMap< BITS >::set ( index_type  i, op_context &  ctxt  )

inline

Sets the bit addressed by i to 1.

A context for exploiting temporal locality can be provided.

Definition at line 1711 of file Brie.h.

                                  {
        op_context ctxt;
        return test(i, ctxt);
    }
 
    /**
     * Determines the whether the bit addressed by i is set or not. A context for
     * exploiting temporal locality can be provided.
     */
    bool test(index_type i, op_context& ctxt) const {
        value_t bit = (1ull << (i & LEAF_INDEX_MASK));
        return store.lookup(i >> LEAF_INDEX_WIDTH, ctxt) & bit;

size()

template<unsigned BITS = 4>

std::size_t souffle::SparseBitMap< BITS >::size ( ) const

inline

Determines the number of bits set.

Definition at line 1778 of file Brie.h.

                                           {
        // nothing to do if it is a self-assignment
        if (this == &other) return;
 

References souffle::SparseArray< T, BITS, merge_op, copy_op >::addAll(), and souffle::SparseBitMap< BITS >::store.

Here is the call graph for this function:

test() [1/2]

template<unsigned BITS = 4>

bool souffle::SparseBitMap< BITS >::test ( index_type  i ) const

inline

Determines the whether the bit addressed by i is set or not.

Definition at line 1747 of file Brie.h.

                                        {
        return test(i);
    }

References i.

test() [2/2]

template<unsigned BITS = 4>

bool souffle::SparseBitMap< BITS >::test ( index_type  i, op_context &  ctxt  ) const

inline

Determines the whether the bit addressed by i is set or not.

A context for exploiting temporal locality can be provided.

Definition at line 1756 of file Brie.h.

toMask()

template<unsigned BITS = 4>

static uint64_t souffle::SparseBitMap< BITS >::toMask ( const value_t &  value )

inlinestaticprivate

Definition at line 1662 of file Brie.h.

                       {

Referenced by souffle::detail::brie::SparseBitMapIter< SparseBitMap >::operator*().

upper_bound()

template<unsigned BITS = 4>

iterator souffle::SparseBitMap< BITS >::upper_bound ( index_type  i ) const

inline

Locates an iterator to the first element in this sparse bit map than is greater than the given index.

Definition at line 1895 of file Brie.h.

                                         {
        return store;
    }

Friends And Related Function Documentation

detail::brie::SparseBitMapIter

template<unsigned BITS = 4>

template<typename A >

friend class detail::brie::SparseBitMapIter

friend

Definition at line 1639 of file Brie.h.

Field Documentation

BITS_PER_ENTRY

template<unsigned BITS = 4>

constexpr size_t souffle::SparseBitMap< BITS >::BITS_PER_ENTRY = sizeof(value_t) * CHAR_BIT

staticconstexprprivate

Definition at line 1658 of file Brie.h.

LEAF_INDEX_MASK

template<unsigned BITS = 4>

constexpr uint64_t souffle::SparseBitMap< BITS >::LEAF_INDEX_MASK = BITS_PER_ENTRY - 1

staticconstexprprivate

Definition at line 1660 of file Brie.h.

LEAF_INDEX_WIDTH

template<unsigned BITS = 4>

constexpr size_t souffle::SparseBitMap< BITS >::LEAF_INDEX_WIDTH = __builtin_ctz(BITS_PER_ENTRY)

staticconstexprprivate

Definition at line 1659 of file Brie.h.

Referenced by souffle::detail::brie::SparseBitMapIter< SparseBitMap >::operator*().

store

template<unsigned BITS = 4>

data_store_t souffle::SparseBitMap< BITS >::store

private

Definition at line 1673 of file Brie.h.

Referenced by souffle::SparseBitMap< BITS >::size().

---

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

• include/souffle/datastructure/Brie.h