CxxUtils::ConcurrentBitset::Impl Class Reference

Implementation object. More...

Collaboration diagram for CxxUtils::ConcurrentBitset::Impl:

Public Types
typedef void	operator_t(std::atomic< Block_t > &a, Block_t v)

Public Member Functions
void *	operator new (size_t, bit_t nbits)
	Allocate an Impl structure. More...
void	operator delete (void *p)
	Impl (bit_t nbits)
	Constructor. More...
	Impl (const Impl &other, bit_t nbits=0)
	Copy constructor. More...
Impl &	operator= (const Impl &)=delete
void	assign (const Impl &other)
	Copy from another instance. More...
bit_t	nbits () const
	Return the number of bits in the set. More...
bool	test (bit_t bit) const
	Test to see if a bit is set. More...
bit_t	count () const
	Count the number of 1 bits in the set. More...
bool	none () const
	Return true if there are no 1 bits in the set. More...
bool	all () const
	Return true if all bits in the set are 1. More...
std::atomic< Block_t > *	block (bit_t bit)
	Return a pointer to the block containing bit. More...
void	set (bit_t bit)
	Turn on one bit. More...
void	reset (bit_t bit)
	Turn off one bit. More...
void	flip (bit_t bit)
	Flip the value of one bit. More...
void	clear ()
	Clear all bits in the set. More...
void	set ()
	Turn on all bits in the set. More...
void	flip ()
	Flip the state of all bits in the set. More...
void	operate (operator_t op, const Impl &other)
	Apply a binary operation. More...
bool	operator== (const Impl &other) const
	Compare with another set. More...
const_iterator	begin () const
	Return an iterator referencing the first 1 bit. More...
const_iterator	end () const
	Return the end iterator. More...
const_iterator	find (bit_t bit) const
	If bit bit is set, return an iterator pointing to it. More...

Private Attributes
size_t	m_nbits
	Number of bits in the container. More...
size_t	m_nblocks
	Number of blocks in the container. More...
std::atomic< size_t >	m_hwm
	High-water mark: index of last block with a 1 bit. More...
std::atomic< Block_t >	m_data [1]
	The set data. More...

Detailed Description

Implementation object.

An instance of this holds the set data for a fixed size. If the set needs to be expanded, a new implementation object must be allocated and the data copied.

This object consists of a fixed header, followed by a variable-sized array containing the actual set data. In this class, the array is declared with a size of 1; however, we allocate these objects (using the newImpl function) with enough space to hold the entire set.

This class also contains the basic methods for operating on the set.

Definition at line 844 of file ConcurrentBitset.h.

Member Typedef Documentation

operator_t

typedef void CxxUtils::ConcurrentBitset::Impl::operator_t(std::atomic< Block_t > &a, Block_t v)

Definition at line 993 of file ConcurrentBitset.h.

Constructor & Destructor Documentation

Impl() [1/2]

CxxUtils::ConcurrentBitset::Impl::Impl

(

bit_t

nbits

)

Constructor.

Parameters

nbits

Number of bits in the set.

Impl() [2/2]

CxxUtils::ConcurrentBitset::Impl::Impl	(	const Impl &	other,
		bit_t	nbits = 0
	)

Copy constructor.

Other object to copy.

Number of bits to use for this container.

If nbits is smaller than the size of other, then the size of other will be used instead.

Member Function Documentation

all()

bool CxxUtils::ConcurrentBitset::Impl::all

(

)

const

Return true if all bits in the set are 1.

Definition at line 216 of file ConcurrentBitset.cxx.

{
  if (m_nblocks == 0) {
    return true;
  }
 
  // Check all blocks except the last.
  for (bit_t i = 0; i < m_nblocks-1; i++) {
    if (m_data[i] != ~static_cast<Block_t>(0)) return false;
  }
  // Special case for the last, since the last block may not be full.
  if (m_data[m_nblocks] != ones<Block_t> (m_nbits - (m_nblocks-1)*BLOCKSIZE)) {
    return false;
  }
  return true;
}

assign()

void CxxUtils::ConcurrentBitset::Impl::assign

(

const Impl &

other

)

Copy from another instance.

Parameters

other

Object from which to copy.

This does not change the size of the container. If This container is larger than other, then the remainder will be filled with zeros. If other is larger than this container, then the remainder will be ignored.

begin()

const_iterator CxxUtils::ConcurrentBitset::Impl::begin

(

)

const

Return an iterator referencing the first 1 bit.

block()

std::atomic<Block_t>* CxxUtils::ConcurrentBitset::Impl::block

(

bit_t

bit

)

Return a pointer to the block containing bit.

Parameters

bit	Desired bit number.

Returns nullptr if bit is past the end of the set.

clear()

void CxxUtils::ConcurrentBitset::Impl::clear

(

)

Clear all bits in the set.

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

count()

ConcurrentBitset::bit_t CxxUtils::ConcurrentBitset::Impl::count

(

)

const

Count the number of 1 bits in the set.

Definition at line 191 of file ConcurrentBitset.cxx.

{
  bit_t n = 0;
  for (bit_t i=0; i<m_nblocks; i++) {
    n += std::popcount (m_data[i].load());
  }
  return n;
}

end()

const_iterator CxxUtils::ConcurrentBitset::Impl::end

(

)

const

Return the end iterator.

find()

const_iterator CxxUtils::ConcurrentBitset::Impl::find

(

bit_t

bit

)

const

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]

void CxxUtils::ConcurrentBitset::Impl::flip

(

)

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.

Definition at line 258 of file ConcurrentBitset.cxx.

{
  for (bit_t i=0; i<m_nblocks; i++) {
    m_data[i] ^= ~static_cast<Block_t>(0);
  }
  if (m_nblocks > 0) {
    m_hwm = m_nblocks-1;
  }
}

flip() [2/2]

void CxxUtils::ConcurrentBitset::Impl::flip

(

bit_t

bit

)

Flip the value of one bit.

Parameters

bit	The bit to turn flip.

Does nothing if bit beyond the end of the set.

nbits()

bit_t CxxUtils::ConcurrentBitset::Impl::nbits

(

)

const

Return the number of bits in the set.

none()

bool CxxUtils::ConcurrentBitset::Impl::none

(

)

const

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

Definition at line 204 of file ConcurrentBitset.cxx.

{
  for (bit_t i = 0; i < m_nblocks; i++) {
    if (m_data[i]) return false;
  }
  return true;
}

operate()

void CxxUtils::ConcurrentBitset::Impl::operate	(	operator_t	op,
		const Impl &	other
	)

Apply a binary operation.

Parameters

op	Operation to apply.
other	Second set for the operation.

Each block B in this set is replaced by B OP OTHER, where OTHER is the corresponding block in the other container. (If this set is larger than other, then the trailing blocks will be 0.)

operator delete()

void CxxUtils::ConcurrentBitset::Impl::operator delete

(

void *

p

)

operator new()

void* CxxUtils::ConcurrentBitset::Impl::operator new	(	size_t	,
		bit_t	nbits
	)

Allocate an Impl structure.

Parameters

sz	Size of an Impl structure.
nbits	Number of bits to allocate.

operator=()

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

delete

operator==()

bool CxxUtils::ConcurrentBitset::Impl::operator==

(

const Impl &

other

)

const

Compare with another set.

Parameters

other

Other set with which to compare.

reset()

void CxxUtils::ConcurrentBitset::Impl::reset

(

bit_t

bit

)

Turn off one bit.

Parameters

bit	The bit to turn off.

Does nothing if bit beyond the end of the set.

set() [1/2]

void CxxUtils::ConcurrentBitset::Impl::set

(

)

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.

Definition at line 240 of file ConcurrentBitset.cxx.

{
  for (bit_t i=0; i<m_nblocks; i++) {
    m_data[i].store (~static_cast<Block_t>(0), std::memory_order_relaxed);
  }
  std::atomic_thread_fence (std::memory_order_seq_cst);
  if (m_nblocks > 0) {
    m_hwm = m_nblocks-1;
  }
}

set() [2/2]

void CxxUtils::ConcurrentBitset::Impl::set

(

bit_t

bit

)

Turn on one bit.

Parameters

bit	The bit to turn on.

Does nothing if bit beyond the end of the set.

test()

bool CxxUtils::ConcurrentBitset::Impl::test

(

bit_t

bit

)

const

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

m_data

std::atomic<Block_t> CxxUtils::ConcurrentBitset::Impl::m_data[1]

private

The set data.

The implementation objects are allocated such that there are actually m_nblocks entries available in this array.

Definition at line 1047 of file ConcurrentBitset.h.

m_hwm

std::atomic<size_t> CxxUtils::ConcurrentBitset::Impl::m_hwm

private

High-water mark: index of last block with a 1 bit.

Definition at line 1042 of file ConcurrentBitset.h.

m_nbits

size_t CxxUtils::ConcurrentBitset::Impl::m_nbits

private

Number of bits in the container.

Definition at line 1036 of file ConcurrentBitset.h.

m_nblocks

size_t CxxUtils::ConcurrentBitset::Impl::m_nblocks

private

Number of blocks in the container.

Definition at line 1039 of file ConcurrentBitset.h.

---

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

• ConcurrentBitset.h
• ConcurrentBitset.cxx