turi::dense_bitset Class Reference

#include <core/util/dense_bitset.hpp>

Public Member Functions
	dense_bitset ()
	Constructs a bitset of 0 length.
	dense_bitset (size_t size)
	Constructs a bitset with 'size' bits. All bits will be cleared.
	dense_bitset (const dense_bitset &db)
	Make a copy of the bitset db.
	~dense_bitset ()
	destructor
dense_bitset &	operator= (const dense_bitset &db)
	Make a copy of the bitset db.
void	resize (size_t n)
void	clear ()
	Sets all bits to 0.
void	fill ()
	Sets all bits to 1.
void	prefetch (size_t b) const
	Prefetches the word containing the bit b.
bool	get (size_t b) const
	Returns the value of the bit b.
bool	set_bit (size_t b)
	Atomically sets the bit at position b to true returning the old value.
bool	xor_bit (size_t b)
	Atomically xors a bit with 1.
size_t	containing_word (size_t b)
	Returns the value of the word containing the bit b.
size_t	get_containing_word_and_zero (size_t b)
	Returns the value of the word containing the bit b.
void	transfer_approximate_unsafe (dense_bitset &other, size_t &start, size_t &b)
	Transfers approximately b bits from another bitset to this bitset. More...
bool	set_bit_unsync (size_t b)
bool	set (size_t b, bool value)
	Atomically sets the state of the bit to the new value returning the old value.
bool	set_unsync (size_t b, bool value)
bool	clear_bit (size_t b)
	Atomically set the bit at b to false returning the old value.
bool	clear_bit_unsync (size_t b)
void	clear_word_unsync (size_t b)
bool	first_bit (size_t &b) const
bool	first_zero_bit (size_t &b) const
bool	next_bit (size_t &b) const
bool	next_zero_bit (size_t &b) const
size_t	size () const
	Returns the number of bits in this bitset.
void	save (oarchive &oarc) const
	Serializes this bitset to an archive.
void	load (iarchive &iarc)
	Deserializes this bitset from an archive.

Detailed Description

Implements an atomic dense bitset

Definition at line 23 of file dense_bitset.hpp.

Member Function Documentation

clear_bit_unsync()

bool turi::dense_bitset::clear_bit_unsync ( size_t  b )

inline

Clears the state of the bit returning the old value. This version uses a non-atomic set which is faster, but is unsafe if accessed by multiple threads.

Definition at line 234 of file dense_bitset.hpp.

clear_word_unsync()

void turi::dense_bitset::clear_word_unsync ( size_t  b )

inline

Clears the word containing the bit b. This version is useful for quickly clearing an entire array when only a few bits are on.

This version uses a non-atomic set which is faster, but is unsafe if accessed by multiple threads.

Definition at line 252 of file dense_bitset.hpp.

first_bit()

bool turi::dense_bitset::first_bit ( size_t &  b ) const

inline

Returns true with b containing the position of the first bit set to true. If such a bit does not exist, this function returns false.

Definition at line 310 of file dense_bitset.hpp.

first_zero_bit()

bool turi::dense_bitset::first_zero_bit ( size_t &  b ) const

inline

Returns true with b containing the position of the first bit set to false. If such a bit does not exist, this function returns false.

Definition at line 325 of file dense_bitset.hpp.

next_bit()

bool turi::dense_bitset::next_bit ( size_t &  b ) const

inline

Where b is a bit index, this function will return in b, the position of the next bit set to true, and return true. If all bits after b are false, this function returns false.

Definition at line 339 of file dense_bitset.hpp.

next_zero_bit()

bool turi::dense_bitset::next_zero_bit ( size_t &  b ) const

inline

Where b is a bit index, this function will return in b, the position of the next bit set to false, and return true. If all bits after b are true, this function returns false.

Definition at line 364 of file dense_bitset.hpp.

resize()

void turi::dense_bitset::resize ( size_t  n )

inline

Resizes the current bitset to hold n bits. Existing bits will not be changed. If the array size is increased, the value of the new bits are undefined.

When shirnking, the current implementation may still leave the "deleted" bits in place which will mess up the popcount.

Definition at line 62 of file dense_bitset.hpp.

set_bit_unsync()

bool turi::dense_bitset::set_bit_unsync ( size_t  b )

inline

Set the bit at position b to true returning the old value. Unlike set_bit(), this uses a non-atomic set which is faster, but is unsafe if accessed by multiple threads.

Definition at line 194 of file dense_bitset.hpp.

set_unsync()

bool turi::dense_bitset::set_unsync ( size_t  b, bool  value  )

inline

Set the state of the bit returning the old value. This version uses a non-atomic set which is faster, but is unsafe if accessed by multiple threads.

Definition at line 214 of file dense_bitset.hpp.

transfer_approximate_unsafe()

void turi::dense_bitset::transfer_approximate_unsafe ( dense_bitset &  other, size_t &  start, size_t &  b  )

inline

Transfers approximately b bits from another bitset to this bitset.

"Moves" at least b bits from the other bitset to this bitset starting from the given position. At return, b will contain the actual number of bits moved, and start will point to the end of the transfered region.

Semantically what this accomplishes is something like:

idx = start;
if other.get_bit(idx) == false {
   idx = next true bit after idx in other (with loop around)
}
for(transferred = 0; transferred < b; transferred++) {
   other.clear_bit(idx);
   this->set_bit(idx);
   idx = next true bit after idx in other.
   if no more bits, return
}

However, the implementation here may transfer more than b bits. ( up to b + 2 * wordsize_in_bits )

Definition at line 163 of file dense_bitset.hpp.

---

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

• core/util/dense_bitset.hpp