bf::counter_vector Class Reference

The fixed width storage policy implements a bit vector where each cell represents a counter having a fixed number of bits. More...

#include <counter_vector.h>

Public Member Functions
	counter_vector (size_t cells, size_t width)
	Construct a counter vector of size \(O(mw)\) where *m is the number of cells and *w the number of bits per cell. More...
bool	increment (size_t cell, size_t value=1)
	Increments a cell counter by a given value. More...
bool	decrement (size_t cell, size_t value=1)
	Decrements a cell counter. More...
size_t	count (size_t cell) const
	Retrieves the counter of a cell. More...
void	set (size_t cell, size_t value)
	Sets a cell to a given value. More...
void	clear ()
	Sets all counter values to 0.
size_t	size () const
	Retrieves the number of cells. More...
size_t	max () const
	Retrieves the maximum possible counter value. More...
size_t	width () const
	Retrieves the counter width. More...

Private Attributes
bitvector	bits_
size_t	width_

Friends
std::string	to_string (counter_vector const &, bool, size_t)
	Generates a string representation of a counter vector. More...

Detailed Description

The fixed width storage policy implements a bit vector where each cell represents a counter having a fixed number of bits.

Definition at line 12 of file counter_vector.h.

Constructor & Destructor Documentation

bf::counter_vector::counter_vector	(	size_t	cells,
		size_t	width
	)

Construct a counter 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.
width	The number of bits per cell.

Precondition

cells > 0 && width > 0

Definition at line 7 of file counter_vector.cc.

Member Function Documentation

size_t bf::counter_vector::count

(

size_t

cell

)

const

Retrieves the counter of a cell.

Parameters

cell	The cell index.

Returns

The counter associated with cell.

Definition at line 62 of file counter_vector.cc.

References size().

Referenced by bf::counting_bloom_filter::count(), bf::counting_bloom_filter::find_minima(), bf::counting_bloom_filter::find_minimum(), and bf::counting_bloom_filter::lookup().

Here is the call graph for this function:

Here is the caller graph for this function:

bool bf::counter_vector::decrement	(	size_t	cell,
		size_t	value = 1
	)

Decrements a cell counter.

Parameters

cell	The cell index.

Returns

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

Definition at line 46 of file counter_vector.cc.

References size().

Referenced by bf::stable_bloom_filter::add(), and bf::counting_bloom_filter::decrement().

Here is the call graph for this function:

Here is the caller graph for this function:

bool bf::counter_vector::increment	(	size_t	cell,
		size_t	value = 1
	)

Increments 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 14 of file counter_vector.cc.

References max(), and size().

Referenced by bf::counting_bloom_filter::increment().

Here is the call graph for this function:

Here is the caller graph for this function:

size_t bf::counter_vector::max

(

)

const

Retrieves the maximum possible counter value.

Returns

The maximum counter value constrained by the cell width.

Definition at line 93 of file counter_vector.cc.

References width().

Referenced by bf::stable_bloom_filter::add(), bf::counting_bloom_filter::find_minima(), bf::counting_bloom_filter::find_minimum(), increment(), bf::counting_bloom_filter::lookup(), and set().

Here is the call graph for this function:

Here is the caller graph for this function:

void bf::counter_vector::set	(	size_t	cell,
		size_t	value
	)

Sets a cell to a given value.

Parameters

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

Definition at line 73 of file counter_vector.cc.

References max(), and size().

Here is the call graph for this function:

size_t bf::counter_vector::size

(

)

const

Retrieves the number of cells.

Returns

The number of cells in the counter vector.

Definition at line 88 of file counter_vector.cc.

References bf::bitvector::size().

Referenced by count(), decrement(), bf::counting_bloom_filter::find_indices(), increment(), and set().

Here is the call graph for this function:

Here is the caller graph for this function:

size_t bf::counter_vector::width

(

)

const

Retrieves the counter width.

Returns

The number of bits per cell.

Definition at line 99 of file counter_vector.cc.

Referenced by max().

Here is the caller graph for this function:

Friends And Related Function Documentation

std::string to_string ( counter_vector const &  , bool  , size_t    )

friend

Generates a string representation of a counter vector.

The arguments have the same meaning as in bf::bitvector.

Definition at line 104 of file counter_vector.cc.

---

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

• counter_vector.h
• counter_vector.cc