Detailed Description

A simple bit vector of fixed size.

Contrary to standard implementations (like std::bitset, or QBitArray), this implementation provides an iterator.

Author: Peter Schäfer

Definition at line 16 of file bitset.h.

#include <bitset.h>

Classes
class	iterator
	an iterator over a BitSet More...

Public Member Functions
	BitSet ()
	default constructor; creates an empty set More...

	BitSet (int asize)
	constructor with size More...

	BitSet (const BitSet &that)
	copy constructor More...

	~BitSet ()
	destructor, releases all data More...

BitSet &	operator= (const BitSet &that)
	assigment operator More...

BitSet &	swap (BitSet &that)
	swap contents with other object More...

int	size () const

int	count () const
	This methods is expensive, as it scans the whole array. More...

void	clear ()
	assign false to all bits More...

bool	contains (int offset) const

void	add (int offset)
	assign true More...

void	remove (int offset)
	assign false More...

bool	operator[] (int offset) const

BitSet &	operator+= (int offset)
	assign true More...

BitSet &	operator-= (int offset)
	assign false More...

void	add_lf (int offset)
	lock-free add operator; not used and not tested! More...

void	remove_lf (int offset)
	lock-free add operator; not used and not tested! More...

iterator	begin () const

iterator	end () const

iterator	first () const

iterator	last () const

Private Member Functions
void	copyBits (const BitSet &that)
	copy data More...

void	stealBits (BitSet &&that)
	steal data More...

int	next (int index) const
	find next index with a set (true) bit More...

int	prev (int off) const
	find previos index with a set (true) bit More...

Static Private Member Functions
static int	numberOfTrailingZeros (uint64_t word)
	compute number of trailing zeros in a 64 bit word More...

static int	numberOfLeadingZeros (uint64_t word)
	compute number of leading zeros in a 64 bit word More...

static int	bitCount (uint64_t word)
	compute number of set bits in a 64 bit word More...

static int64_t	compare_and_swap (volatile int64_t *value, int64_t old_value, int64_t update_value)
	atomic compare-and-swap More...

Private Attributes
int	_size
	number of valid bits More...

int	numWords
	number of allocated words (1 word = 64 bits) More...

uint64_t *	bits
	bit data More...

Constructor & Destructor Documentation

◆ BitSet() [1/3]

BitSet::BitSet ( )

default constructor; creates an empty set

Definition at line 11 of file bitset.cpp.

◆ BitSet() [2/3]

BitSet::BitSet ( int asize )

constructor with size

Parameters

asize number of allocated bits; all bits are initialized to false.

Definition at line 13 of file bitset.cpp.

◆ BitSet() [3/3]

BitSet::BitSet ( const BitSet & that )

copy constructor

Parameters

that	objec to copy from

Definition at line 28 of file bitset.cpp.

◆ ~BitSet()

BitSet::~BitSet ( )

destructor, releases all data

Definition at line 33 of file bitset.cpp.

Member Function Documentation

◆ add()

void BitSet::add ( int offset )

assign true

Parameters

offset index into bit set

Definition at line 77 of file bitset.cpp.

◆ add_lf()

void BitSet::add_lf ( int offset )

lock-free add operator; not used and not tested!

Definition at line 89 of file bitset.cpp.

◆ begin()

BitSet::iterator BitSet::begin ( ) const

Returns: an iterator that points to the first set (true) bit

Definition at line 128 of file bitset.cpp.

◆ bitCount()

int BitSet::bitCount ( uint64_t word )

staticprivate

compute number of set bits in a 64 bit word

Parameters

word	a 64 bit word

Returns: number of set bits

Definition at line 329 of file bitset.cpp.

◆ clear()

void BitSet::clear ( )

assign false to all bits

Definition at line 67 of file bitset.cpp.

◆ compare_and_swap()

int64_t BitSet::compare_and_swap	(	volatile int64_t *	value,
		int64_t	old_value,
		int64_t	update_value
	)

staticprivate

atomic compare-and-swap

Parameters

value	pointer to current value
old_value	expected old value
update_value	update value

Returns: actual old value

Replaces current value with update value, if it is equal to the expected (old) value. If the current value is not equal to the expected value, do nothing and return the actual value.

Compare and update are performed atomically, i.e. without being interrupted by another thread.

Definition at line 298 of file bitset.cpp.

◆ contains()

bool BitSet::contains ( int offset ) const

Parameters

offset index into bit set

Returns: true if the bit at 'offset' is true

Definition at line 71 of file bitset.cpp.

◆ copyBits()

void BitSet::copyBits ( const BitSet & that )

private

copy data

Parameters

that	object to copy from

Definition at line 130 of file bitset.cpp.

◆ count()

int BitSet::count ( ) const

This methods is expensive, as it scans the whole array.

Returns: number of set (true) bits

Definition at line 58 of file bitset.cpp.

◆ end()

iterator frechet::data::BitSet::end ( ) const

inline

Returns: an iterator that points one beyond the end of this BitSet. This iterator is invalid, but can be decremented.

Definition at line 167 of file bitset.h.

◆ first()

iterator frechet::data::BitSet::first ( ) const

inline

Returns: an iterator that points to the first set (true) bit

Definition at line 170 of file bitset.h.

◆ last()

iterator frechet::data::BitSet::last ( ) const

inline

Returns: an iterator that points to the last set (true) bit

Definition at line 172 of file bitset.h.

◆ next()

int BitSet::next ( int index ) const

private

find next index with a set (true) bit

Parameters

index start index

Definition at line 151 of file bitset.cpp.

◆ numberOfLeadingZeros()

int BitSet::numberOfLeadingZeros ( uint64_t word )

staticprivate

compute number of leading zeros in a 64 bit word

Parameters

word	a 64 bit word

Returns: number of leading zeros

Definition at line 321 of file bitset.cpp.

◆ numberOfTrailingZeros()

int BitSet::numberOfTrailingZeros ( uint64_t word )

staticprivate

compute number of trailing zeros in a 64 bit word

Parameters

word	a 64 bit word

Returns: number of trailing zeros

Definition at line 313 of file bitset.cpp.

◆ operator+=()

BitSet& frechet::data::BitSet::operator+= ( int offset )

inline

assign true

Parameters

offset index into bit set

Returns: this object, after adding a bit

Definition at line 73 of file bitset.h.

◆ operator-=()

BitSet& frechet::data::BitSet::operator-= ( int offset )

inline

assign false

Parameters

offset index into bit set

Returns: this object, after clearing a bit

Definition at line 77 of file bitset.h.

◆ operator=()

BitSet & BitSet::operator= ( const BitSet & that )

assigment operator

Parameters

that	object to copy from

Returns: this object, after assigning a copy

Definition at line 38 of file bitset.cpp.

◆ operator[]()

bool frechet::data::BitSet::operator[] ( int offset ) const

inline

Parameters

offset index into bit set

Returns: true if the bit at 'offset' is true

Definition at line 69 of file bitset.h.

◆ prev()

int BitSet::prev ( int off ) const

private

find previos index with a set (true) bit

Parameters

off	start index

Definition at line 174 of file bitset.cpp.

◆ remove()

void BitSet::remove ( int offset )

assign false

Parameters

offset index into bit set

Definition at line 83 of file bitset.cpp.

◆ remove_lf()

void BitSet::remove_lf ( int offset )

lock-free add operator; not used and not tested!

Definition at line 108 of file bitset.cpp.

◆ size()

int BitSet::size ( ) const

Returns: number of valid bits

Definition at line 56 of file bitset.cpp.

◆ stealBits()

void BitSet::stealBits ( BitSet && that )

private

steal data

Parameters

that	object to copy from; is empty on return

Definition at line 144 of file bitset.cpp.

◆ swap()

BitSet & BitSet::swap ( BitSet & that )

swap contents with other object

Parameters

that	object to copy from

Returns: this object, after exchanging content with 'that'

Definition at line 44 of file bitset.cpp.

Member Data Documentation

◆ _size

int frechet::data::BitSet::_size

private

number of valid bits

Definition at line 19 of file bitset.h.

◆ bits

uint64_t* frechet::data::BitSet::bits

private

bit data

Definition at line 23 of file bitset.h.

◆ numWords

int frechet::data::BitSet::numWords

private

number of allocated words (1 word = 64 bits)

Definition at line 21 of file bitset.h.

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

include/data/bitset.h
src/data/bitset.cpp

Detailed Description

Classes

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Constructor & Destructor Documentation

◆ BitSet() [1/3]

◆ BitSet() [2/3]

◆ BitSet() [3/3]

◆ ~BitSet()

Member Function Documentation

◆ add()

◆ add_lf()

◆ begin()

◆ bitCount()

◆ clear()

◆ compare_and_swap()

◆ contains()

◆ copyBits()

◆ count()

◆ end()

◆ first()

◆ last()

◆ next()

◆ numberOfLeadingZeros()

◆ numberOfTrailingZeros()

◆ operator+=()

◆ operator-=()

◆ operator=()

◆ operator[]()

◆ prev()

◆ remove()

◆ remove_lf()

◆ size()

◆ stealBits()

◆ swap()

Member Data Documentation

◆ _size

◆ bits

◆ numWords