Struct CuckooFilter 

pub struct CuckooFilter<H> { /* private fields */ }

A cuckoo filter class exposes a Bloomier filter interface, providing methods of add, delete, contains.

Examples

use bugu;

let words = vec!["foo", "bar", "xylophone", "milagro"];
let mut cf = bugu::CuckooFilter::new();

let mut insertions = 0;
for s in &words {
    if cf.test_and_add(s).unwrap() {
        insertions += 1;
    }
}

assert_eq!(insertions, words.len());
assert_eq!(cf.len(), words.len());

// Re-add the first element.
cf.add(words[0]);

assert_eq!(cf.len(), words.len() + 1);

for s in &words {
    cf.delete(s);
}

assert_eq!(cf.len(), 1);
assert!(!cf.is_empty());

cf.delete(words[0]);

assert_eq!(cf.len(), 0);
assert!(cf.is_empty());

for s in &words {
    if cf.test_and_add(s).unwrap() {
        insertions += 1;
    }
}

cf.clear();

assert!(cf.is_empty());

Implementations

impl CuckooFilter<DefaultHasher>

pub fn new() -> Self

Construct a CuckooFilter with default capacity and hasher.

impl<H> CuckooFilter<H>

where H: Hasher + Default,

pub fn with_capacity(cap: usize) -> Self

Constructs a Cuckoo Filter with a given max capacity

pub fn contains<T: ?Sized + Hash>(&self, data: &T) -> bool

Checks if data is in the filter.

pub fn add<T: ?Sized + Hash>(&mut self, data: &T) -> Result<(), CuckooError>

Adds data to the filter. Returns Ok if the insertion was successful, but could fail with a NotEnoughSpace error, especially when the filter is nearing its capacity. Note that while you can put any hashable type in the same filter, beware for side effects like that the same number can have diferent hashes depending on the type. So for the filter, 4711i64 isn’t the same as 4711u64.

Note: When this returns NotEnoughSpace, the element given was actually added to the filter, but some random other element was removed. This might improve in the future.

pub fn test_and_add<T: ?Sized + Hash>( &mut self, data: &T, ) -> Result<bool, CuckooError>

Adds data to the filter if it does not exist in the filter yet. Returns Ok(true) if data was not yet present in the filter and added successfully.

pub fn len(&self) -> usize

Number of items in the filter.

pub fn export(&self) -> ExportedCuckooFilter

Exports fingerprints in all buckets, along with the filter’s length for storage. The filter can be recovered by passing the ExportedCuckooFilter struct to the from method of CuckooFilter.

pub fn memory_usage(&self) -> usize

Number of bytes the filter occupies in memory

pub fn is_empty(&self) -> bool

Check if filter is empty

pub fn delete<T: ?Sized + Hash>(&mut self, data: &T) -> bool

Deletes data from the filter. Returns true if data existed in the filter before.

pub fn clear(&mut self)

Empty all the buckets in a filter and reset the number of items.

Trait Implementations

impl Default for CuckooFilter<DefaultHasher>

fn default() -> Self

Returns the “default value” for a type.

impl<H> From<&CuckooFilter<H>> for ExportedCuckooFilter

where H: Hasher + Default,

fn from(cuckoo: &CuckooFilter<H>) -> Self

Converts a CuckooFilter into a simplified version which can be serialized and stored for later use.

impl<H> From<ExportedCuckooFilter> for CuckooFilter<H>

fn from(exported: ExportedCuckooFilter) -> Self

Converts a simplified representation of a filter used for export to a fully functioning version.

Contents

• values - A serialized version of the CuckooFilter’s memory, where the fingerprints in each bucket are chained one after another, then in turn all buckets are chained together.
• length - The number of valid fingerprints inside the CuckooFilter. This value is used as a time saving method, otherwise all fingerprints would need to be checked for equivalence against the null pattern.