libbf  0.1
 All Classes Functions Typedefs Friends Pages
Public Member Functions | Private Attributes | List of all members
bf::stable_bloom_filter Class Reference

A stable Bloom filter. More...

#include <stable.h>

Inheritance diagram for bf::stable_bloom_filter:
Inheritance graph

Public Member Functions

 stable_bloom_filter (hasher h, size_t cells, size_t width, size_t d)
 Constructs a stable Bloom filter. More...
 
virtual void add (object const &o) override
 Adds an item to the stable Bloom filter. More...
 
- Public Member Functions inherited from bf::counting_bloom_filter
 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 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...
 

Private Attributes

size_t d_
 
std::mt19937 generator_
 
std::uniform_int_distribution unif_
 

Additional Inherited Members

- Protected Member Functions inherited from bf::counting_bloom_filter
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 inherited from bf::counting_bloom_filter
hasher hasher_
 
counter_vector cells_
 

Detailed Description

A stable Bloom filter.

Definition at line 10 of file stable.h.

Constructor & Destructor Documentation

bf::stable_bloom_filter::stable_bloom_filter ( hasher  h,
size_t  cells,
size_t  width,
size_t  d 
)

Constructs a stable Bloom filter.

Parameters
hThe hasher.
cellsThe number of cells.
widthThe number of bits per cell.
dThe number of cells to decrement before adding an element.
Precondition
cells <= d

Definition at line 7 of file stable.cc.

Member Function Documentation

void bf::stable_bloom_filter::add ( object const &  o)
overridevirtual

Adds an item to the stable Bloom filter.

This invovles first decrementing k positions uniformly at random and then setting the counter of o to all 1s.

Parameters
oThe object to add.

Reimplemented from bf::counting_bloom_filter.

Definition at line 16 of file stable.cc.

References bf::counter_vector::decrement(), bf::counting_bloom_filter::find_indices(), bf::counting_bloom_filter::increment(), and bf::counter_vector::max().

Here is the call graph for this function:


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