#include <graphlab/util/dense_bitset.hpp>

Public Types
typedef bit_pos_iterator	iterator
typedef bit_pos_iterator	const_iterator

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.
bool	empty () const
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.
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)
bit_pos_iterator	begin () const
bit_pos_iterator	end () const
bool	first_bit (size_t &b) const
bool	first_zero_bit (size_t &b) const
bool	next_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.
size_t	popcount () const
dense_bitset	operator& (const dense_bitset &other) const
dense_bitset	operator\| (const dense_bitset &other) const
dense_bitset	operator- (const dense_bitset &other) const
dense_bitset &	operator&= (const dense_bitset &other)
dense_bitset &	operator\|= (const dense_bitset &other)
dense_bitset &	operator-= (const dense_bitset &other)
void	invert ()

Detailed Description

Implements an atomic dense bitset

Definition at line 40 of file dense_bitset.hpp.

Member Function Documentation

bool graphlab::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 244 of file dense_bitset.hpp.

bool graphlab::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 306 of file dense_bitset.hpp.

bool graphlab::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 321 of file dense_bitset.hpp.

bool graphlab::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 335 of file dense_bitset.hpp.

void graphlab::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 80 of file dense_bitset.hpp.

bool graphlab::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 204 of file dense_bitset.hpp.

bool graphlab::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 224 of file dense_bitset.hpp.

void graphlab::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 173 of file dense_bitset.hpp.

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

graphlab/util/dense_bitset.hpp

Public Types

Public Member Functions

Detailed Description

Member Function Documentation