bf::fixed_width< Block, Allocator > Class Template Reference

The fixed width storage policy implements a bit vector where each cell itself is a counter with a fixed number of bits. More...

#include <store.h>

Inheritance diagram for bf::fixed_width< Block, Allocator >:

List of all members.

Public Types
typedef Block	block_type
typedef Allocator	allocator_type
typedef boost::dynamic_bitset < Block, Allocator >	bitset
typedef bitset::size_type	size_type
typedef std::vector< size_type >	pos_vector
typedef uint64_t	count_type
Public Member Functions
	fixed_width (unsigned cells, unsigned width)
	Construct a bit vector of size \(O(mw)\) where \(m\) is the number of cells and \(w\) the number of bits per cell.
template<typename B , typename A >
void	swap (fixed_width< B, A > &store)
bool	increment (size_type cell)
	Increment a cell counter.
bool	increment (size_type cell, count_type value)
	Increment a cell counter by a given value.
bool	decrement (size_type cell)
	Decrement a cell counter.
count_type	count (size_type cell) const
	Get the count of a cell.
void	set ()
	Set every bit in the bit vector.
void	set (size_type cell)
	Set a cell to all 1s.
void	set (size_type cell, count_type value)
	Set a cell to a given value.
void	reset ()
	Clear every bit in the bit vector.
void	reset (size_type cell)
	Clear the bit(s) of specific cell.
void	halve ()
	Shrink the number of cells in the bit vector by a factor of 2.
size_type	size () const
	Get the size of the underlying bit vector.
count_type	max () const
	Get the maximum counter value this store supports.
bool	none () const
	Test whether all bits are 0.
unsigned	width () const
	Get the counter width of a cell.
void	width (unsigned w)
	Set the cell width.
std::string	to_string () const
	Get a string representation of the storage.
template<typename F >
void	each (F f) const
	Apply a functor to each counter in the bit vector.
Private Attributes
bitset	bits_
unsigned	width_

---

Detailed Description

template<typename Block, typename Allocator>
class bf::fixed_width< Block, Allocator >

The fixed width storage policy implements a bit vector where each cell itself is a counter with a fixed number of bits.

Definition at line 37 of file store.h.

---

Constructor & Destructor Documentation

template<typename Block, typename Allocator>

bf::fixed_width< Block, Allocator >::fixed_width	(	unsigned	cells,
		unsigned	width
	)		[inline]

Construct a bit vector of size \(O(mw)\) where \(m\) is the number of cells and \(w\) the number of bits per cell.

Parameters:

cells	The number of cells in the bit vector.
width	The number of pits per cell.

Definition at line 53 of file store.h.

References bf::fixed_width< Block, Allocator >::max().

Here is the call graph for this function:

---

Member Function Documentation

template<typename Block, typename Allocator>

count_type bf::fixed_width< Block, Allocator >::count

(

size_type

cell

)

const [inline]

Get the count of a cell.

Parameters:

cell	The cell index.

Returns:

true if the decrement succeeded, false if all bits in the cell were already 0.

Definition at line 190 of file store.h.

References bf::fixed_width< Block, Allocator >::size().

Referenced by bf::fixed_width< Block, Allocator >::each(), and bf::fixed_width< Block, Allocator >::halve().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Block, typename Allocator>

bool bf::fixed_width< Block, Allocator >::decrement

(

size_type

cell

)

[inline]

Decrement a cell counter.

Parameters:

cell	The cell index.

Returns:

true if the decrement succeeded, false if all bits in the cell were already 0.

Definition at line 167 of file store.h.

References bf::fixed_width< Block, Allocator >::size().

Here is the call graph for this function:

template<typename Block, typename Allocator>

template<typename F >

void bf::fixed_width< Block, Allocator >::each

(

F

f

)

const [inline]

Apply a functor to each counter in the bit vector.

Template Parameters:

The	type of the unary functor.

Parameters:

f	An instance of type F.

Definition at line 355 of file store.h.

References bf::fixed_width< Block, Allocator >::count().

Here is the call graph for this function:

template<typename Block, typename Allocator>

bool bf::fixed_width< Block, Allocator >::increment

(

size_type

cell

)

[inline]

Increment a cell counter.

Parameters:

cell	The cell index.

Returns:

true if the increment succeeded, false if all bits in the cell were already 1.

Definition at line 79 of file store.h.

References bf::fixed_width< Block, Allocator >::size().

Here is the call graph for this function:

template<typename Block, typename Allocator>

bool bf::fixed_width< Block, Allocator >::increment	(	size_type	cell,
		count_type	value
	)		[inline]

Increment a cell counter by a given value.

If the value is larger than or equal to max(), All bits are set to 1.

Parameters:

cell	The cell index.
value	The value that is added to the current cell value.

Returns:

- true if the increment succeeded, false if all bits in the cell were already 1.

Definition at line 103 of file store.h.

References bf::fixed_width< Block, Allocator >::max(), and bf::fixed_width< Block, Allocator >::size().

Here is the call graph for this function:

template<typename Block, typename Allocator>

count_type bf::fixed_width< Block, Allocator >::max

(

)

const [inline]

Get the maximum counter value this store supports.

Returns:

The maximum counter value.

Definition at line 276 of file store.h.

References bf::fixed_width< Block, Allocator >::width().

Referenced by bf::fixed_width< Block, Allocator >::fixed_width(), bf::fixed_width< Block, Allocator >::increment(), and bf::fixed_width< Block, Allocator >::set().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Block, typename Allocator>

bool bf::fixed_width< Block, Allocator >::none

(

)

const [inline]

Test whether all bits are 0.

Returns:

true iff all bits in the bit vector are 0.

Definition at line 284 of file store.h.

template<typename Block, typename Allocator>

void bf::fixed_width< Block, Allocator >::reset

(

size_type

cell

)

[inline]

Clear the bit(s) of specific cell.

Parameters:

cell	The cell to clear.

Definition at line 242 of file store.h.

References bf::fixed_width< Block, Allocator >::size().

Here is the call graph for this function:

template<typename Block, typename Allocator>

void bf::fixed_width< Block, Allocator >::set	(	size_type	cell,
		count_type	value
	)		[inline]

Set a cell to a given value.

Parameters:

cell	The cell whose value changes.
value	The new value of the cell.

Definition at line 223 of file store.h.

References bf::fixed_width< Block, Allocator >::max(), and bf::fixed_width< Block, Allocator >::size().

Here is the call graph for this function:

template<typename Block, typename Allocator>

void bf::fixed_width< Block, Allocator >::set

(

size_type

cell

)

[inline]

Set a cell to all 1s.

Parameters:

cell	The cell to set to all 1s.

Definition at line 211 of file store.h.

References bf::fixed_width< Block, Allocator >::size().

Here is the call graph for this function:

template<typename Block, typename Allocator>

size_type bf::fixed_width< Block, Allocator >::size

(

)

const [inline]

Get the size of the underlying bit vector.

Returns:

The size of the bit vector in number of cells.

Definition at line 269 of file store.h.

Referenced by bf::fixed_width< Block, Allocator >::count(), bf::fixed_width< Block, Allocator >::decrement(), bf::fixed_width< Block, Allocator >::increment(), bf::fixed_width< Block, Allocator >::reset(), and bf::fixed_width< Block, Allocator >::set().

Here is the caller graph for this function:

template<typename Block, typename Allocator>

std::string bf::fixed_width< Block, Allocator >::to_string

(

)

const [inline]

Get a string representation of the storage.

The output reads from left to right. That is, for each cell the least-significant bit corresponds to the left-most bit.

Parameters:

A	string of the underlying bit vector.

Definition at line 341 of file store.h.

template<typename Block, typename Allocator>

void bf::fixed_width< Block, Allocator >::width

(

unsigned

w

)

[inline]

Set the cell width.

Parameters:

w	The new value of the cell width.

Todo:

Write unit tests.

Definition at line 299 of file store.h.

template<typename Block, typename Allocator>

unsigned bf::fixed_width< Block, Allocator >::width

(

)

const [inline]

Get the counter width of a cell.

Returns:

The number of bits per cell.

Definition at line 291 of file store.h.

Referenced by bf::fixed_width< Block, Allocator >::max().

Here is the caller graph for this function:

---

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

• store.h