Struct ofilter::SyncStream

pub struct SyncStream<T> { /* private fields */ }

Thread-safe streaming Bloom filter.

Same as the standard streaming Bloom filter, but safe to use in concurrent environments.

Examples

use std::thread;
use ofilter::SyncStream;

let filter: SyncStream<usize> = SyncStream::new(100);

let f = filter.clone();
let handle1 = thread::spawn(move || {
    for i in 0..10_000 {
        f.set(&i);
    }
});

let f = filter.clone();
let handle2 = thread::spawn(move || {
    for i in 0..10_000 {
        f.check(&i);
    }
});

handle1.join().unwrap();
handle2.join().unwrap();

Implementations

impl<T> SyncStream<T>

pub fn new(capacity: usize) -> Self

Create a new thread-safe streaming Bloom filter, with given capacity.

All other parameters are set to defaults, or aligned to match capacity.

This is different from a classic Bloom filter, it maintains a set of items, in this set you can be sure that the last capacity items are always kept in the filter. In other words, it works like a Bloom filter for the most recent items. Ancient items are progressively removed from the set.

Examples

use ofilter::SyncStream;

let filter: SyncStream<usize> = SyncStream::new(100);
assert_eq!(100, filter.capacity());

pub fn new_with_params(params: Params) -> Self

Create a new thread-safe streaming Bloom filter, with specific parameters.

Examples

use ofilter::{SyncStream, Params};

let filter: SyncStream<usize> = SyncStream::new_with_params(Params::with_nb_items_and_fp_rate(100, 0.1));
assert_eq!(100, filter.capacity());

pub fn params(&self) -> Params

Get filter params.

This can be useful because when creating the filter, the .adjust() func is called, and may decide to fine-tune some parameters. With this, one can know exactly what is used by the filter.

Examples

use ofilter::SyncStream;

let filter: SyncStream<usize> = SyncStream::new(100);
println!("{}", filter.params());

pub fn capacity(&self) -> usize

Get filter capacity.

Returns the value of params.nb_items, that is the number of items the filter is designed for.

use ofilter::{SyncStream, Params};

let filter: SyncStream<usize> = SyncStream::new_with_params(Params::with_bit_len(1_000_000));
assert_eq!(52681, filter.capacity());

pub fn clear(&self)

Clear the filter.

Clears the bit vector, but keeps parameters.

use ofilter::SyncStream;

// Does not need to be `mut`
let filter: SyncStream<usize> = SyncStream::new(1_000);
filter.set(&10);
assert!(filter.check(&10));
filter.clear();
assert!(!filter.check(&10));

pub fn is_empty(&self) -> bool

Returns true if filter is empty.

use ofilter::SyncStream;

// Does not need to be `mut`
let filter: SyncStream<usize> = SyncStream::new(1_000);
assert!(filter.is_empty());
filter.set(&10);
assert!(!filter.is_empty());

pub fn max_fp_rate(&self) -> f64

Returns the current max false positive rate.

In theory the false positive rate fp_rate is known at filter creation. But that, is the theoretical fp_rate that the filter reaches when it is “wasted” because it has too many entries. Until then, it performs better than that, statistically.

As this filter uses two filters under the hood, there are technically 2 values for the actual false positive rate.

This function returns the max value, which is usually the most significant, as it’s reflecting the current behavior of the filter.

use ofilter::SyncStream;

// Does not need to be `mut`
let filter: SyncStream<usize> = SyncStream::new(1_000);
assert_eq!(0.0, filter.max_fp_rate());
filter.set(&10);
assert!(filter.max_fp_rate() > 0.0); // will be params.fp_rate when filter is full

pub fn fp_rates(&self) -> (f64, f64)

Returns the current false positive rates.

In theory the false positive rate fp_rate is known at filter creation. But that, is the theoretical fp_rate that the filter reaches when it is “wasted” because it has too many entries. Until then, it performs better than that, statistically.

As this filter uses two filters under the hood, there are technically 2 values for the actual false positive rate.

This function returns both values, starting with the highest one, which is usually the most significant as it’s reflecting the current behavior of the filter.

use ofilter::SyncStream;

// Does not need to be `mut`
let filter: SyncStream<usize> = SyncStream::new(1_000);
assert_eq!((0.0, 0.0), filter.fp_rates());
filter.set(&10);
let fp_rates = filter.fp_rates();
assert!(fp_rates.0 > 0.0); // will be greater than params.fp_rate when filter is full
assert!(fp_rates.1 > 0.0); // will be params.fp_rate when filter is full

pub fn min_level(&self) -> f64

Returns the current ratios between real min fp_rate, and theoretical fp_rate..

This is a helper to quickly compare the real min fp_rate with the theoretical fp_rate. It compares the min value and not the max, as it is when the min value reaches 1.0 that the filters are swapped after one is cleared.

When this value greater than 1.0, the filter should soon “age” and clear the most filled underlying Bloom filter.

use ofilter::SyncStream;

// Does not need to be `mut`
let filter: SyncStream<usize> = SyncStream::new(1_000);
assert_eq!((0.0, 0.0), filter.levels());
filter.set(&10);
let levels = filter.levels();
assert!(levels.0 > 0.0); // will be greater than 1.0 when filter is full
assert!(levels.1 > 0.0); // will be 1.0 when filter is full

pub fn levels(&self) -> (f64, f64)

Returns the current ratios between real fp_rates, and theoretical fp_rates.

This is a helper to quickly compare the real fp_rates with the theoretical fp_rates.

When both of these values are greater than 1.0, the filter should soon “age” and clear the most filled underlying Bloom filter.

use ofilter::SyncStream;

// Does not need to be `mut`
let filter: SyncStream<usize> = SyncStream::new(1_000);
assert_eq!((0.0, 0.0), filter.levels());
filter.set(&10);
let levels = filter.levels();
assert!(levels.0 > 0.0); // will be greater than 1.0 when filter is full
assert!(levels.1 > 0.0); // will be 1.0 when filter is full

pub fn age(&self) -> usize

Returns the age of the filter.

The age is the number of times the underlying Bloom filters have been cleared and swapped.

In the beginning this is 0, then when filters are full, one of them is cleared, and age becomes one. Everytime this happens again, age increases.

As a consequence, the age gives a raw estimation of how many different items have been through the cache. With a given capacity, the number of different items the cache has seen is roughly age * capacity. This is just an approximation.

use ofilter::{SyncStream, Params};

let params = Params{
    nb_hash: 2,
    bit_len: 0,
    nb_items: 1_000,
    fp_rate: 0.1,
    predict: true,
};
// Does not need to be `mut`
let filter: SyncStream<usize> = SyncStream::new_with_params(params);
assert_eq!(0, filter.age());
for i in 0..100_000 {
    filter.set(&i);
}
println!("{}", filter.age());
assert!(filter.age() >= 90);
assert!(filter.age() <= 100);

pub fn resize(&self, capacity: usize)

Resize the filter.

As the underlying Bloom filters are recycled in a streaming filter, it is possible to resize it.

What it means is that next time the filter ages, the new created Bloom filter will have the new size. It will keep the same number of hash nb_hash and false positive rate fp_rate. Only the number of bits bit_len and number of items nb_items change.

use ofilter::SyncStream;

// Does not need to be `mut`
let filter: SyncStream<usize> = SyncStream::new(1_000);
filter.set(&1);
filter.resize(100);
assert_eq!(100, filter.capacity());
assert!(filter.check(&1));

impl<T> SyncStream<T>where
    T: Hash,

pub fn set(&self, item: &T)

Record an item in the set.

Once this has been called, any call to check() will return true, as there are no false negatives. However some other items may test positive as a consequence of recording this one.

However, after some time, the item will ultimately disappear from the set and be replaced by new entries. Only the most recent entries are guaranteed to be here.

use ofilter::SyncStream;

// Does not need to be `mut`
let filter: SyncStream<usize> = SyncStream::new(1_000);
filter.set(&42);

pub fn check(&self, item: &T) -> bool

Guess whether an item is likely to be in the set.

If set() has been called before with value, then this returns true, as there are no false negatives. However it may respond true even if the item has never been recorded in the set.

However, if set() has been called too long ago and too many items have been added since, it will test negative anyway.

use ofilter::SyncStream;

// Does not need to be `mut`
let filter: SyncStream<usize> = SyncStream::new(1_000);
filter.set(&42);
assert!(filter.check(&42));

pub fn check_and_set(&self, item: &T) -> bool

Record an item in the set and returns its previous value.

Equivalent to calling get() then set() but performs hash lookup only once so it’s a bit more efficient.

use ofilter::SyncStream;

// Does not need to be `mut`
let filter: SyncStream<usize> = SyncStream::new(1_000);
assert!(!filter.check_and_set(&42));
assert!(filter.check(&42));

Trait Implementations

impl<T: Clone> Clone for SyncStream<T>

fn clone(&self) -> SyncStream<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for SyncStream<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Display for SyncStream<T>where
    T: Hash,

Pretty-print the filter.

Examples

use ofilter::SyncStream;

let filter: SyncStream<usize> = SyncStream::new(100);

assert_eq!("[sync] { age: 0, fp_rates: (0.000000, 0.000000), params: { nb_hash: 2, bit_len: 1899, nb_items: 100, fp_rate: 0.009992, predict: false } }" , format!("{}", filter));

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.