bloom_filters/
counting.rs

1use crate::buckets::Buckets;
2use crate::{BloomFilter, BuildHashKernels, HashKernels, RemovableBloomFilter};
3use std::hash::Hash;
4
5pub struct Filter<BHK: BuildHashKernels> {
6    buckets: Buckets,      // filter data
7    hash_kernels: BHK::HK, // hash kernels
8}
9
10impl<BHK: BuildHashKernels> Filter<BHK> {
11    /// Create a new bloom filter structure.
12    /// items_count is an estimation of the maximum number of items to store.
13    /// bucket_size is the specified number of bits
14    /// fp_rate is the wanted rate of false positives, in ]0.0, 1.0[
15    pub fn new(items_count: usize, bucket_size: u8, fp_rate: f64, build_hash_kernels: BHK) -> Self {
16        let buckets = Buckets::with_fp_rate(items_count, fp_rate, bucket_size);
17        let hash_kernels = build_hash_kernels.with_fp_rate(fp_rate, buckets.len());
18        Self { buckets, hash_kernels }
19    }
20}
21
22impl<BHK: BuildHashKernels> BloomFilter for Filter<BHK> {
23    fn insert<T: Hash>(&mut self, item: &T) {
24        self.hash_kernels.hash_iter(item).for_each(|i| self.buckets.increment(i, 1))
25    }
26
27    fn contains<T: Hash>(&self, item: &T) -> bool {
28        self.hash_kernels.hash_iter(item).all(|i| self.buckets.get(i) > 0)
29    }
30
31    fn reset(&mut self) {
32        self.buckets.reset()
33    }
34}
35
36impl<BHK: BuildHashKernels> RemovableBloomFilter for Filter<BHK> {
37    fn remove<T: Hash>(&mut self, item: &T) {
38        self.hash_kernels.hash_iter(item).for_each(|i| self.buckets.increment(i, -1))
39    }
40}
41
42#[cfg(test)]
43mod tests {
44    use super::*;
45    use crate::hash::DefaultBuildHashKernels;
46    use proptest::{collection::size_range, prelude::any, prelude::any_with, proptest};
47    use rand::random;
48    use std::collections::hash_map::RandomState;
49
50    fn _contains(items: &[usize]) {
51        let mut filter = Filter::new(100, 4, 0.03, DefaultBuildHashKernels::new(random(), RandomState::new()));
52        assert!(items.iter().all(|i| !filter.contains(i)));
53        items.iter().for_each(|i| filter.insert(i));
54        assert!(items.iter().all(|i| filter.contains(i)));
55    }
56
57    proptest! {
58        #[test]
59        fn contains(ref items in any_with::<Vec<usize>>(size_range(16).lift())) {
60            _contains(items)
61        }
62    }
63
64    fn _remove(item: usize) {
65        let mut filter = Filter::new(100, 4, 0.03, DefaultBuildHashKernels::new(random(), RandomState::new()));
66        filter.insert(&item);
67        filter.remove(&item);
68        assert!(!filter.contains(&item));
69    }
70
71    proptest! {
72        #[test]
73        fn remove(items in any::<usize>()) {
74            _remove(items)
75        }
76    }
77}
bloom_filters/counting.rs

bloom_filters/
counting.rs
