range_filters/
bloom_filter.rs

1use fastbloom::BloomFilter as FastBloomFilter;
2
3use crate::Key;
4
5pub struct BloomFilter {
6    filter: FastBloomFilter,
7    fpr: f64,
8    num_keys: usize,
9}
10
11impl BloomFilter {
12    /// Create a new Bloom Filter with the given keys and false positive rate.
13    ///
14    /// # Arguments
15    /// * `keys` - A slice of keys to insert into the filter
16    /// * `fpr` - Target false positive rate (e.g., 0.01 for 1%)
17    ///
18    /// # Returns
19    /// A new `BloomFilter` instance containing all the provided keys
20    pub fn new_with_keys(keys: &[Key], fpr: f64) -> Self {
21        let num_keys = keys.len();
22
23        let mut filter = FastBloomFilter::with_false_pos(fpr).expected_items(num_keys);
24        for &key in keys {
25            filter.insert(&key.to_string());
26        }
27        Self {
28            filter,
29            fpr,
30            num_keys,
31        }
32    }
33
34    /// Perform a point query to check if a key might exist in the filter.
35    ///
36    /// # Arguments
37    /// * `key` - The key to search for
38    ///
39    /// # Returns
40    /// * `true` if the key might exist (with false positive rate `fpr`)
41    /// * `false` if the key definitely does not exist
42    pub fn point_query(&self, key: Key) -> bool {
43        self.filter.contains(&key.to_string())
44    }
45
46    /// Perform a range query to check if any key might exist in the given range [start, end] (inclusive).
47    ///
48    /// # Arguments
49    /// * `start` - The start of the range (inclusive)
50    /// * `end` - The end of the range (inclusive)
51    ///
52    /// # Returns
53    /// * `true` if at least one key in the range might exist (with false positive rate `fpr`)
54    /// * `false` if no keys in the range exist
55    pub fn range_query(&self, start: Key, end: Key) -> bool {
56        if start > end {
57            return false;
58        }
59
60        for key in start..=end {
61            if self.filter.contains(&key.to_string()) {
62                return true;
63            }
64        }
65        false
66    }
67
68    /// Get the configured false positive rate.
69    ///
70    /// # Returns
71    /// The false positive rate (e.g., 0.01 for 1%)
72    pub fn fpr(&self) -> f64 {
73        self.fpr
74    }
75
76    /// Get the number of keys inserted into the filter.
77    pub fn num_keys(&self) -> usize {
78        self.num_keys
79    }
80}
range_filters/bloom_filter.rs

range_filters/
bloom_filter.rs
