Struct tinysearch_cuckoofilter::CuckooFilter

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

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

Examples

extern crate cuckoofilter;

let words = vec!["foo", "bar", "xylophone", "milagro"];
let mut cf = cuckoofilter::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());

Methods

impl CuckooFilter<DefaultHasher>

pub fn new() -> CuckooFilter<DefaultHasher>

Construct a CuckooFilter with default capacity and hasher.

impl<H> CuckooFilter<H> where
    H: Hasher + Default, 

pub fn with_capacity(cap: usize) -> CuckooFilter<H>

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.

Trait Implementations

impl Default for CuckooFilter<DefaultHasher>

fn default() -> Self

Returns the "default value" for a type.

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

fn from(exported: ExportedCuckooFilter) -> CuckooFilter<H>

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.

impl<'a, H> From<&'a CuckooFilter<H>> for ExportedCuckooFilter where
    H: Hasher + Default, 

fn from(cuckoo: &'a CuckooFilter<H>) -> ExportedCuckooFilter

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