roaring_bloom_filter/
lib.rs

1use std::hash::Hash;
2
3/// A scalable bloom filter implementation, based on VariantBloomFilter.
4///
5/// ```rust
6/// use roaring_bloom_filter::*;
7///
8/// let mut bf = ScalableBloomFilter::new(100, 0.001_f64);
9///
10/// bf.add(&10);
11/// bf.add(&'a');
12/// bf.add(&"a string");
13///
14/// bf.contains(&12);
15/// ```
16pub use scalable_bloom_filter::ScalableBloomFilter;
17/// Stable bloom filter, the best choice for small data set.
18/// In this structure, k hash functions share a global bitmap, whose max size is u64::MAX.
19/// Usage:
20/// ```rust
21/// use roaring_bloom_filter::*;
22///
23/// let mut bf = StableBloomFilter::new(100, 0.001_f64);
24///
25/// bf.add(&10);
26/// bf.add(&'a');
27/// bf.add(&"a string");
28///
29/// bf.contains(&12);
30/// ```
31pub use stable_bloom_filter::StableBloomFilter;
32/// A variant bloom filter, the best choice for bigger data set.
33/// In this structure, k hash functions all has it's own slice of bitmap, whose max size is u64::MAX.
34/// Usage:
35/// ```rust
36/// use roaring_bloom_filter::*;
37///
38/// let mut bf = VariantBloomFilter::new(100, 0.001_f64);
39///
40/// bf.add(&10);
41/// bf.add(&'a');
42/// bf.add(&"a string");
43///
44/// bf.contains(&12);
45/// ```
46pub use variant_bloom_filter::VariantBloomFilter;
47
48/// Interface for bloom filter.
49/// Define all the function a bloom filter should implement.
50pub trait BloomFilter {
51    /// Add new element into the bloom filter.
52    /// Return true when any key are inserted in a slice.
53    fn add<T>(&mut self, value: &T) -> bool where T: Hash;
54
55    /// Check if the bloom filter contains the specific key.
56    /// Return true when all key are present in all slices, which may contains false positive situation.
57    fn contains<T>(&self, value: &T) -> bool where T: Hash;
58
59    /// Get target false positive rate.
60    fn target_false_positive_rate(&self) -> f64;
61
62    /// Get current false positive rate.
63    fn current_false_positive_rate(&self) -> f64;
64
65    /// If this bloom filter is empty.
66    fn is_empty(&self) -> bool;
67
68    /// If this bloom filter is full.
69    fn is_full(&self) -> bool;
70
71    /// Get the number of inserted elements in this bloom filter.
72    fn size(&self) -> u64;
73
74    /// Get the number of inserted bits in all slices.
75    fn len(&self) -> u64;
76}
77
78mod stable_bloom_filter;
79
80mod variant_bloom_filter;
81
82mod scalable_bloom_filter;
83
84/// global utils function
85pub(crate) mod utils {
86    use std::collections::hash_map::DefaultHasher;
87    use std::hash::{Hash, Hasher};
88
89    pub fn get_hash<T: Hash>(value: &T, seed: u32) -> u64 {
90        let mut s = DefaultHasher::new();
91        value.hash(&mut s);
92        seed.hash(&mut s);
93        s.finish()
94    }
95}
roaring_bloom_filter/lib.rs

roaring_bloom_filter/
lib.rs
