|
libbf
0.1
|
A stable Bloom filter. More...
#include <stable.h>
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_ |
| bf::stable_bloom_filter::stable_bloom_filter | ( | hasher | h, |
| size_t | cells, | ||
| size_t | width, | ||
| size_t | d | ||
| ) |
|
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.
| o | The 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().
1.8.3.1
