A set of aux data identifiers. More...

#include <AuxTypes.h>

Inheritance diagram for SG::auxid_set_t:

Collaboration diagram for SG::auxid_set_t:

Public Types
typedef size_t	bit_t
	A bit number.

Public Member Functions
	auxid_set_t (size_t nbits=auxid_set_size_hint)
	ConcurrentBitset (bit_t nbits=0)
	Constructor.
	ConcurrentBitset (const ConcurrentBitset &other)
	Copy constructor.
	ConcurrentBitset (std::initializer_list< bit_t > l, bit_t nbits=0)
	Constructor from an initializer list.
	ConcurrentBitset (ConcurrentBitset &&other)
	Move constructor.
Constructors, destructors, assignment.
void	emptyGarbage ()
	Clean up old versions of the set.
Size, bit testing
bit_t	capacity () const
	The number of bits that this container can hold.
bit_t	count () const
	Count the number of 1 bits in the set.
size_t	count (bit_t bit) const
	Test to see if a bit is set.
bit_t	size () const
	Count the number of 1 bits in the set.
bool	test (bit_t bit) const
	Test to see if a bit is set.
bool	empty () const
	Return true if there are no 1 bits in the set.
bool	none () const
	Return true if there are no 1 bits in the set.
bool	all () const
	Return true if all bits in the set are 1.
bool	any () const
	Return true if there are any 1 bits in the set.
Single-bit manipulation.
ConcurrentBitset &	set (bit_t bit)
	Turn on one bit.
ConcurrentBitset &	set (bit_t bit, bool val)
	Set the value of one bit.
ConcurrentBitset &	reset (bit_t bit)
	Turn off one bit.
ConcurrentBitset &	erase (bit_t bit)
	Turn off one bit.
ConcurrentBitset &	flip (bit_t bit)
	Flip the value of one bit.
Set operations.
ConcurrentBitset &	set ()
	Turn on all bits in the set.
ConcurrentBitset &	reset ()
	Clear all bits in the set.
ConcurrentBitset &	flip ()
	Flip the state of all bits in the set.
ConcurrentBitset &	clear ()
	Clear all bits in the set.
ConcurrentBitset &	operator&= (const ConcurrentBitset &other)
	AND this set with another set.
ConcurrentBitset &	operator\|= (const ConcurrentBitset &other)
	OR this set with another set.
ConcurrentBitset &	operator^= (const ConcurrentBitset &other)
	XOR this set with another set.
ConcurrentBitset &	operator-= (const ConcurrentBitset &other)
	Subtract another set from this set.
ConcurrentBitset	operator~ () const
	Return a new set that is the complement of this set.
Comparison.
bool	operator== (const ConcurrentBitset &other) const
	Test two sets for equality.
bool	operator!= (const ConcurrentBitset &other) const
	Test two sets for inequality.
Insert.
ConcurrentBitset &	insert (bit_t bit, bit_t new_nbits=0)
	Set a bit to 1.
template<class ITERATOR, typename = typename std::enable_if< std::is_base_of< typename std::forward_iterator_tag, typename std::iterator_traits<ITERATOR>::iterator_category >::value>>
ConcurrentBitset &	insert (ITERATOR beg, ITERATOR end, bit_t new_nbits=0)
	Set several bits to 1.
ConcurrentBitset &	insert (std::initializer_list< bit_t > l, bit_t new_nbits=0)
	Set several bits to 1.
ConcurrentBitset &	insert (const ConcurrentBitset &other)
	Turn on bits listed in another set.
Array-like element access.
bool	operator[] (bit_t bit) const
	Return the value of one bit.
reference	operator[] (bit_t bit)
	Return a reference to one bit.
Iterator operations.
const_iterator	begin () const
	Return a begin iterator.
const_iterator	end () const
	Return an end iterator.
const_iterator	find (bit_t bit) const
	If bit `bit` is set, return an iterator pointing to it.

Private Types
typedef unsigned long	Block_t
	Internal type used to hold the bitset data.

Static Private Attributes
static const size_t	BLOCKSIZE = sizeof(Block_t) * CHAR_BIT
	Size, in bits, of `Block_t`.
static const size_t	MASK = BLOCKSIZE-1
	Mask to select out the bit offset within one `Block_t`.

Implementation.
typedef std::mutex	mutex_t
	Mutex used for synchronization when switching to a new implementation object.
typedef std::lock_guard< mutex_t >	lock_t
std::atomic< Impl * >	m_impl
	The current implementation object.
std::vector< Impl * >	m_garbage
	Old implementation objects, pending deletion.
mutex_t	m_mutex
static bit_t	nBlocks (bit_t nbits)
	Find number of blocks needed to hold a given number of bits.
Impl *	newImpl (bit_t nbits)
	Create a new, uninitialized implementation object.
void	expand (bit_t new_nbits)
	Expand the container.
void	expandOol (bit_t new_nbits)
	Expand the container: out-of-line portion.

Detailed Description

A set of aux data identifiers.

This is a ConcurrentBitset, with the default size set to auxid_set_size_hint.

Definition at line 45 of file AuxTypes.h.

Member Typedef Documentation

◆ bit_t

typedef size_t CxxUtils::ConcurrentBitset::bit_t

inherited

A bit number.

Definition at line 167 of file ConcurrentBitset.h.

◆ Block_t

typedef unsigned long CxxUtils::ConcurrentBitset::Block_t

privateinherited

Internal type used to hold the bitset data.

The bitset is an array of std::atomic<Block_t>. This type should generally be the largest unsigned type for which std::atomic is lockless.

Definition at line 154 of file ConcurrentBitset.h.

◆ lock_t

typedef std::lock_guard<mutex_t> CxxUtils::ConcurrentBitset::lock_t

privateinherited

Definition at line 1063 of file ConcurrentBitset.h.

◆ mutex_t

typedef std::mutex CxxUtils::ConcurrentBitset::mutex_t

privateinherited

Mutex used for synchronization when switching to a new implementation object.

Definition at line 1062 of file ConcurrentBitset.h.

Constructor & Destructor Documentation

◆ auxid_set_t()

SG::auxid_set_t::auxid_set_t ( size_t nbits = auxid_set_size_hint )

inline

Definition at line 50 of file AuxTypes.h.

    : CxxUtils::ConcurrentBitset (nbits)
  {
  }

Member Function Documentation

◆ all()

bool CxxUtils::ConcurrentBitset::all ( ) const

inherited

Return true if all bits in the set are 1.

◆ any()

bool CxxUtils::ConcurrentBitset::any ( ) const

inherited

Return true if there are any 1 bits in the set.

◆ begin()

const_iterator CxxUtils::ConcurrentBitset::begin ( ) const

inherited

Return a begin iterator.

◆ capacity()

bit_t CxxUtils::ConcurrentBitset::capacity ( ) const

inherited

The number of bits that this container can hold.

◆ clear()

ConcurrentBitset & CxxUtils::ConcurrentBitset::clear ( )

inherited

Clear all bits in the set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

◆ ConcurrentBitset() [1/4]

CxxUtils::ConcurrentBitset::ConcurrentBitset ( bit_t nbits = 0 )

Constructor.

Parameters

nbits Initial number of bits to allocate for the map.

Definition at line 179 of file ConcurrentBitset.cxx.

  : m_impl (new (nbits) Impl (nbits))
{
}

◆ ConcurrentBitset() [2/4]

CxxUtils::ConcurrentBitset::ConcurrentBitset ( ConcurrentBitset && other )

Move constructor.

Parameters

other Container to move.

No concurrent access may be in progress on other. After this returns, other can only be deleted.

Definition at line 213 of file ConcurrentBitset.cxx.

{
  other.emptyGarbage();
  Impl* impl = other.m_impl;
  other.m_impl = nullptr;
  m_impl = impl;
}

◆ ConcurrentBitset() [3/4]

CxxUtils::ConcurrentBitset::ConcurrentBitset ( const ConcurrentBitset & other )

Copy constructor.

Parameters

other Container to copy.

The copy is not atomic. If a non-atomic update is simultaneously made to other, then the copy may have this update only partially completed.

Definition at line 189 of file ConcurrentBitset.cxx.

{
  // Be careful: don't read other.m_impl more than once.  It may change
  // at any time.
  const Impl* otherImpl = other.m_impl;
  // cppcheck-suppress useInitializationList
  m_impl = new (otherImpl->nbits()) Impl (*otherImpl);
}

◆ ConcurrentBitset() [4/4]

CxxUtils::ConcurrentBitset::ConcurrentBitset	(	std::initializer_list< bit_t >	l,
		bit_t	nbits = 0 )

Constructor from an initializer list.

Parameters

List	of values to set.
nbits	Number of bits to allocate for the map. If 0, then set the size based on the maximum value in the list.

This allows setting specific bits in the set, like

ConcurrentBitset bs { 1, 5, 10};

SG::auxid_set_t::ConcurrentBitset

ConcurrentBitset(bit_t nbits=0)

Constructor.

Definition ConcurrentBitset.cxx:27

Definition at line 203 of file ConcurrentBitset.cxx.

{
  if (nbits == 0) {
    // Set the size of the set based on the maximum value in the list.
    auto max_it = std::max_element (l.begin(), l.end());
    if (max_it != l.end()) {
      nbits = *max_it + 1;
    }
    // Round up.
    nbits = (nbits + BLOCKSIZE-1) & ~MASK;
  }
  m_impl = new (nbits) Impl (nbits);
  for (bit_t b : l) {
    set (b);
  }
}

◆ count() [1/2]

bit_t CxxUtils::ConcurrentBitset::count ( ) const

inherited

Count the number of 1 bits in the set.

◆ count() [2/2]

size_t CxxUtils::ConcurrentBitset::count ( bit_t bit ) const

inherited

Test to see if a bit is set.

Parameters

bit	Number of the bit to test.

Returns: 1 if the bit is set; 0 otherwise.

Returns 0 if bit is beyond the end of the set.

◆ empty()

bool CxxUtils::ConcurrentBitset::empty ( ) const

inherited

Return true if there are no 1 bits in the set.

◆ emptyGarbage()

void CxxUtils::ConcurrentBitset::emptyGarbage ( )

inherited

Clean up old versions of the set.

The insert and assignment operations may need to grow the set. The original version of the set is not deleted immediately, since other threads may still be accessing it. Call this when no other threads can be accessing old versions in order to clean them up.

Definition at line 153 of file ConcurrentBitset.cxx.

{
  lock_t lock (m_mutex);
  for (Impl* p : m_garbage) {
    free (p);
  }
  m_garbage.clear();
}

◆ end()

const_iterator CxxUtils::ConcurrentBitset::end ( ) const

inherited

Return an end iterator.

◆ erase()

ConcurrentBitset & CxxUtils::ConcurrentBitset::erase ( bit_t bit )

inherited

Turn off one bit.

Parameters

bit	The bit to turn off.

Does nothing if bit beyond the end of the set.

◆ expand()

void CxxUtils::ConcurrentBitset::expand ( bit_t new_nbits )

privateinherited

Expand the container.

Parameters

new_nbits The desired new size of the container.

◆ expandOol()

void CxxUtils::ConcurrentBitset::expandOol ( bit_t new_nbits )

privateinherited

Expand the container: out-of-line portion.

Parameters

new_nbits The desired new size of the container.

Definition at line 167 of file ConcurrentBitset.cxx.

{
  // Need to take out the lock.
  lock_t lock (m_mutex);
  // Check the size again while we're holding the lock.
  bit_t nbits = (*m_impl).nbits();
  if (new_nbits > nbits) {
    // We need to expand.  Allocate a new implementation and initialize it,
    // copying from the existing implementation.
    Impl* i = new (new_nbits) Impl (*m_impl, new_nbits);
 
    // Remember that we need to delete the old object.
    m_garbage.push_back (m_impl);
 
    // Publish the new one.
    m_impl = i;
  }
}

◆ find()

const_iterator CxxUtils::ConcurrentBitset::find ( bit_t bit ) const

inherited

If bit bit is set, return an iterator pointing to it.

Otherwise, return an end iterator.

Parameters

bit	Bit number to test.

◆ flip() [1/2]

ConcurrentBitset & CxxUtils::ConcurrentBitset::flip ( )

inherited

Flip the state of all bits in the set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

◆ flip() [2/2]

ConcurrentBitset & CxxUtils::ConcurrentBitset::flip ( bit_t bit )

inherited

Flip the value of one bit.

Parameters

bit	The bit to turn flip.

Does nothing if bit beyond the end of the set.

◆ insert() [1/4]

ConcurrentBitset & CxxUtils::ConcurrentBitset::insert	(	bit_t	bit,
		bit_t	new_nbits = 0 )

inherited

Set a bit to 1.

Expand the set if needed.

Parameters

bit	Number of the bit to set.
new_nbits	Hint for new size of set, if it needs to be expanded.

If bit is past the end of the container, then the container will be expanded as needed.

This operation is incompatible with any other simultaneous writes to the same set (reads are ok).

◆ insert() [2/4]

ConcurrentBitset & CxxUtils::ConcurrentBitset::insert ( const ConcurrentBitset & other )

inherited

Turn on bits listed in another set.

Parameters

other Set of bits to turn on.

This is the same as operator|=, except that if the size of other is larger than this set, then this set will be expanded to match other.

This operation is incompatible with any other simultaneous writes to the same set (reads are ok).

◆ insert() [3/4]

template<class ITERATOR, typename = typename std::enable_if< std::is_base_of< typename std::forward_iterator_tag, typename std::iterator_traits<ITERATOR>::iterator_category >::value>>

ConcurrentBitset & CxxUtils::ConcurrentBitset::insert	(	ITERATOR	beg,
		ITERATOR	end,
		bit_t	new_nbits = 0 )

inherited

Set several bits to 1.

Expand the set if needed.

Parameters

beg	Start of range of bits to set.
end	End of range of bits to set.
new_nbits	Hint for new size of set, if it needs to be expanded.

The iteration range should be over something convertible to bit_t. If any bit is past the end of the container, then the container will be expanded as needed.

This operation is incompatible with any other simultaneous writes to the same set (reads are ok).

Example:

std::vector<bit_t> bits { 4, 10, 12};
CxxUtils::ConcurrentBitset bs = ...;
bs.insert (bits.begin(), bits.end());

◆ insert() [4/4]

ConcurrentBitset & CxxUtils::ConcurrentBitset::insert	(	std::initializer_list< bit_t >	l,
		bit_t	new_nbits = 0 )

inherited

Set several bits to 1.

Expand the set if needed.

Parameters

l	List of bits to set.
new_nbits	Hint for new size of set, if it needs to be expanded.

If any bit is past the end of the container, then the container will be expanded as needed.

This operation is incompatible with any other simultaneous writes to the same set (reads are ok).

Example:

std::vector<bit_t> bits { 4, 10, 12};

bs.insert ({4, 10, 12});

◆ nBlocks()

bit_t CxxUtils::ConcurrentBitset::nBlocks ( bit_t nbits )

staticprivateinherited

Find number of blocks needed to hold a given number of bits.

Parameters

nbits The number of bits.

◆ newImpl()

Impl * CxxUtils::ConcurrentBitset::newImpl ( bit_t nbits )

privateinherited

Create a new, uninitialized implementation object.

Parameters

nbits Number of bits to allocate.

This will allocate memory for the Impl object, but will does not run the constructor.

◆ none()

bool CxxUtils::ConcurrentBitset::none ( ) const

inherited

Return true if there are no 1 bits in the set.

◆ operator!=()

bool CxxUtils::ConcurrentBitset::operator!= ( const ConcurrentBitset & other ) const

inherited

Test two sets for inequality.

Parameters

other The other set to test.

◆ operator&=()

ConcurrentBitset & CxxUtils::ConcurrentBitset::operator&= ( const ConcurrentBitset & other )

inherited

AND this set with another set.

Parameters

other The other set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

◆ operator-=()

ConcurrentBitset & CxxUtils::ConcurrentBitset::operator-= ( const ConcurrentBitset & other )

inherited

Subtract another set from this set.

Parameters

other The other set.

This is the same as (*this) &= ~other;

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

◆ operator==()

bool CxxUtils::ConcurrentBitset::operator== ( const ConcurrentBitset & other ) const

inherited

Test two sets for equality.

Parameters

other The other set to test.

◆ operator[]() [1/2]

reference CxxUtils::ConcurrentBitset::operator[] ( bit_t bit )

inherited

Return a reference to one bit.

Parameters

bit	The number of the bit to reference.

The reference will be invalidated by calls to insert() or operator=. Effects are undefined if bit is past the end of the set.

◆ operator[]() [2/2]

bool CxxUtils::ConcurrentBitset::operator[] ( bit_t bit ) const

inherited

Return the value of one bit.

Parameters

bit	The number of the bit to test.

◆ operator^=()

ConcurrentBitset & CxxUtils::ConcurrentBitset::operator^= ( const ConcurrentBitset & other )

inherited

XOR this set with another set.

Parameters

other The other set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

◆ operator|=()

ConcurrentBitset & CxxUtils::ConcurrentBitset::operator|= ( const ConcurrentBitset & other )

inherited

OR this set with another set.

Parameters

other The other set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

◆ operator~()

ConcurrentBitset CxxUtils::ConcurrentBitset::operator~ ( ) const

inherited

Return a new set that is the complement of this set.

◆ reset() [1/2]

ConcurrentBitset & CxxUtils::ConcurrentBitset::reset ( )

inherited

Clear all bits in the set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

◆ reset() [2/2]

ConcurrentBitset & CxxUtils::ConcurrentBitset::reset ( bit_t bit )

inherited

Turn off one bit.

Parameters

bit	The bit to turn off.

Does nothing if bit beyond the end of the set.

◆ set() [1/3]

ConcurrentBitset & CxxUtils::ConcurrentBitset::set ( )

inherited

Turn on all bits in the set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

◆ set() [2/3]

ConcurrentBitset & CxxUtils::ConcurrentBitset::set ( bit_t bit )

inherited

Turn on one bit.

Parameters

bit	The bit to turn on.

Does nothing if bit beyond the end of the set.

◆ set() [3/3]

ConcurrentBitset & CxxUtils::ConcurrentBitset::set	(	bit_t	bit,
		bool	val )

inherited

Set the value of one bit.

Parameters

bit	The bit to turn set.
val	The value to which to set it.

Does nothing if bit beyond the end of the set.

◆ size()

bit_t CxxUtils::ConcurrentBitset::size ( ) const

inherited

Count the number of 1 bits in the set.

Note: If you regard this like a std::bitset, you would expect this to return the number of bits that the set can hold, while if you regard this like a set<bit_t>, then you would expect this to return the number of 1 bits. We follow the latter here.

◆ test()

bool CxxUtils::ConcurrentBitset::test ( bit_t bit ) const

inherited

Test to see if a bit is set.

Parameters

bit	Number of the bit to test.

Returns: true if the bit is set; false otherwise.

Returns false if bit is beyond the end of the set.

Member Data Documentation

◆ BLOCKSIZE

const size_t CxxUtils::ConcurrentBitset::BLOCKSIZE = sizeof(Block_t) * CHAR_BIT

staticprivateinherited

Size, in bits, of Block_t.

Definition at line 157 of file ConcurrentBitset.h.

◆ m_garbage

std::vector<Impl*> CxxUtils::ConcurrentBitset::m_garbage

privateinherited

Old implementation objects, pending deletion.

Definition at line 1059 of file ConcurrentBitset.h.

◆ m_impl

std::atomic<Impl*> CxxUtils::ConcurrentBitset::m_impl

privateinherited

The current implementation object.

Definition at line 1056 of file ConcurrentBitset.h.

◆ m_mutex

mutex_t CxxUtils::ConcurrentBitset::m_mutex

privateinherited

Definition at line 1064 of file ConcurrentBitset.h.

◆ MASK

const size_t CxxUtils::ConcurrentBitset::MASK = BLOCKSIZE-1

staticprivateinherited

Mask to select out the bit offset within one Block_t.

Definition at line 160 of file ConcurrentBitset.h.

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

AuxTypes.h

Public Types

Public Member Functions

Private Types

Static Private Attributes

Implementation.

Detailed Description

Member Typedef Documentation

◆ bit_t

◆ Block_t

◆ lock_t

◆ mutex_t

Constructor & Destructor Documentation

◆ auxid_set_t()

Member Function Documentation

◆ all()

◆ any()

◆ begin()

◆ capacity()

◆ clear()

◆ ConcurrentBitset() [1/4]

◆ ConcurrentBitset() [2/4]

◆ ConcurrentBitset() [3/4]

◆ ConcurrentBitset() [4/4]

◆ count() [1/2]

◆ count() [2/2]

◆ empty()

◆ emptyGarbage()

◆ end()

◆ erase()

◆ expand()

◆ expandOol()

◆ find()

◆ flip() [1/2]

◆ flip() [2/2]

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ nBlocks()

◆ newImpl()

◆ none()

◆ operator!=()

◆ operator&=()

◆ operator-=()

◆ operator==()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ operator^=()

◆ operator|=()

◆ operator~()

◆ reset() [1/2]

◆ reset() [2/2]

◆ set() [1/3]

◆ set() [2/3]

◆ set() [3/3]

◆ size()

◆ test()

Member Data Documentation

◆ BLOCKSIZE

◆ m_garbage

◆ m_impl

◆ m_mutex

◆ MASK