Ponca::BitSet< N, T > Class Template Reference

A simple BitSet implementation that mimics a set of indices. More...

#include <bitset.h>

Collaboration diagram for Ponca::BitSet< N, T >:

Public Member Functions
void	flip (int i)
	Toggles the value of a bit.
bool	erase (int value)
	Tries to insert a value in the set.
bool	insert (int value)
	Tries to insert a value in the set.
bool	contains (int value) const
	Search if the value was already inserted or not.
void	clear ()
	Sets all the bits to EMPTY.

Protected Attributes
T	m_data [ARRAY_SIZE] = {}
	An array of bytes.

Static Protected Attributes
static constexpr size_t	BIT_SIZE = sizeof(T) * 8
static constexpr size_t	ARRAY_SIZE = (N + BIT_SIZE - 1) / BIT_SIZE
	The number of bits in one element of the array.

Detailed Description

template<int N, typename T = unsigned long long>
class Ponca::BitSet< N, T >

A simple BitSet implementation that mimics a set of indices.

The internal logic of this bitset is similar to std::bitset, but is compatible with CUDA.

Allows to insert and search in O(1) complexity, but is memory expensive, because we allocate a single bit for each possible indices, to flag if it was inserted or not, which is not ideal for large amount of indices.

The memory use of the BitSet depending on N should be in theory :

BitSet size	Memory used
Bitset<10000>	1.25 KB
Bitset<1e6>	125 KB
Bitset<1e7>	1.25 MB

Template Parameters

N	Maximum number of indices
T	The data type of the array storing the bits. Default to 'unsigned long long' for 64 bits storage.

See also

BitSet::erase, BitSet::insert for set-index-like methods

HashSet For alternative data structure with compatible API

Warning

The inserted values must always be smaller than N, because we are using them as indices to store the bits inside the BitSet.

Definition at line 41 of file bitset.h.

Member Function Documentation

clear()

template<int N, typename T >

void Ponca::BitSet< N, T >::clear

(

)

Sets all the bits to EMPTY.

Definition at line 14 of file bitset.hpp.

contains()

template<int N, typename T >

bool Ponca::BitSet< N, T >::contains

(

int

value

)

const

Search if the value was already inserted or not.

Parameters

value

The value to search for (search is O(N) because it corresponds to the index in the BitSet)

Returns

Definition at line 45 of file bitset.hpp.

erase()

template<int N, typename T >

bool Ponca::BitSet< N, T >::erase

(

int

value

)

Tries to insert a value in the set.

Parameters

value

The value to be removed in the set. Must always be smaller than N, because we are using the values as indices inside the BitSet.

Returns

True if the value was removed successfully, and false if the value was already not inside the Set

Definition at line 20 of file bitset.hpp.

flip()

template<int N, typename T >

void Ponca::BitSet< N, T >::flip

(

int

i

)

Toggles the value of a bit.

Parameters

i	The bit to flip

Definition at line 57 of file bitset.hpp.

insert()

template<int N, typename T >

bool Ponca::BitSet< N, T >::insert

(

int

value

)

Tries to insert a value in the set.

Parameters

value

The value to be inserted in the HashSet. Must always be smaller than N, because we are using the values as indices inside the BitSet.

Returns

True if the value was inserted successfully, and false if the value was already inserted or if the HashSet is full

Definition at line 33 of file bitset.hpp.

Member Data Documentation

ARRAY_SIZE

template<int N, typename T = unsigned long long>

constexpr size_t Ponca::BitSet< N, T >::ARRAY_SIZE = (N + BIT_SIZE - 1) / BIT_SIZE

staticconstexprprotected

The number of bits in one element of the array.

The array size

Definition at line 82 of file bitset.h.

BIT_SIZE

template<int N, typename T = unsigned long long>

constexpr size_t Ponca::BitSet< N, T >::BIT_SIZE = sizeof(T) * 8

staticconstexprprotected

Definition at line 81 of file bitset.h.

m_data

template<int N, typename T = unsigned long long>

T Ponca::BitSet< N, T >::m_data[ARRAY_SIZE] = {}

protected

An array of bytes.

Definition at line 83 of file bitset.h.