The counting Bloom filter. More...

#include <counting.h>

Inheritance diagram for bf::counting_bloom_filter:

Public Member Functions
	counting_bloom_filter (hasher h, size_t cells, size_t width)
	Constructs a counting Bloom filter. More...

	counting_bloom_filter (counting_bloom_filter &&)=default
	Move-constructs a counting Bloom filter.

virtual void	add (object const &o) override
	Adds an element to the Bloom filter. More...

virtual size_t	lookup (object const &o) const override
	Retrieves the count of an element. More...

virtual void	clear () override
	Removes all items from the Bloom filter.

void	remove (object const &o)
	Removes an element. More...

template<typename T >
void	remove (T const &x)

Public Member Functions inherited from bf::bloom_filter
template<typename T >
void	add (T const &x)
	Adds an element to the Bloom filter. More...

template<typename T >
size_t	lookup (T const &x) const
	Retrieves the count of an element. More...

Protected Member Functions
std::vector< size_t >	find_indices (object const &o, bool part=false) const
	Maps an object to the indices in the underlying counter vector. More...

size_t	find_minimum (std::vector< size_t > const &indices) const
	Finds the minimum value in a list of arbitrary indices. More...

std::vector< size_t >	find_minima (std::vector< size_t > const &indices) const
	Finds one or more minimum indices for a list of arbitrary indices. More...

bool	increment (std::vector< size_t > const &indices, size_t value=1)
	Increments a given set of indices in the underlying counter vector. More...

bool	decrement (std::vector< size_t > const &indices, size_t value=1)
	Decrements a given set of indices in the underlying counter vector. More...

size_t	count (size_t index) const
	Retrieves the counter for given cell index. More...

Protected Attributes
hasher	hasher_

counter_vector	cells_

Private Attributes
friend	spectral_mi_bloom_filter

friend	spectral_rm_bloom_filter

Detailed Description

The counting Bloom filter.

Definition at line 14 of file counting.h.

Constructor & Destructor Documentation

bf::counting_bloom_filter::counting_bloom_filter	(	hasher	h,
		size_t	cells,
		size_t	width
	)

Constructs a counting Bloom filter.

Parameters

h	The hasher.
cells	The number of cells.
width	The number of bits per cell.

Definition at line 8 of file counting.cc.

Member Function Documentation

void bf::counting_bloom_filter::add ( object const & o )

overridevirtual

Adds an element to the Bloom filter.

Parameters

o	A wrapped object.

Implements bf::bloom_filter.

Reimplemented in bf::spectral_mi_bloom_filter, and bf::stable_bloom_filter.

Definition at line 15 of file counting.cc.

References find_indices(), and increment().

Here is the call graph for this function:

size_t bf::counting_bloom_filter::count ( size_t index ) const

protected

Retrieves the counter for given cell index.

Parameters

index The index of the counter vector.

Precondition: index < cells.size()

Definition at line 119 of file counting.cc.

References bf::counter_vector::count().

Referenced by bf::spectral_rm_bloom_filter::add(), and bf::spectral_rm_bloom_filter::lookup().

Here is the call graph for this function:

Here is the caller graph for this function:

bool bf::counting_bloom_filter::decrement	(	std::vector< size_t > const &	indices,
		size_t	value = `1`
	)

protected

Decrements a given set of indices in the underlying counter vector.

Parameters

indices The indices to decrement.

Returns: true iff no counter underflowed.

Definition at line 109 of file counting.cc.

References bf::counter_vector::decrement().

Referenced by remove(), and bf::spectral_rm_bloom_filter::remove().

Here is the call graph for this function:

Here is the caller graph for this function:

std::vector< size_t > bf::counting_bloom_filter::find_indices	(	object const &	o,
		bool	part = `false`
	)		const

protected

Maps an object to the indices in the underlying counter vector.

Parameters

o	The object to map.
part	If `false`, the function maps o uniformly into the counter vector modding each digest with the number of available cells. If `true`, the function partitions the counter vector into k distinct sub-vectors and mods each digest into one sub-vector.