deterministic_bloom/
const_size.rs

1use crate::{
2    common::{Error, HashIndexIterator},
3    utils::{ByteArrayVisitor, HexFieldDebug},
4};
5use bitvec::prelude::BitArray;
6use serde::{Deserialize, Serialize};
7use std::{fmt::Debug, ops::Index};
8
9//------------------------------------------------------------------------------
10// Type Definitions
11//------------------------------------------------------------------------------
12
13/// The bloom filter is a probabilistic data structure that can be used to store a set of hashes.
14///
15/// `N` is the size of the bloom filter in bytes.
16///
17/// `K` is the number of bits to be set with each insert operation.
18///
19/// # Examples
20///
21/// ```
22/// use deterministic_bloom::const_size::BloomFilter;
23///
24/// let mut filter = BloomFilter::<256, 30>::default();
25/// filter.insert(&[0xF5u8; 32]);
26///
27/// assert!(filter.contains(&[0xF5u8; 32]));
28/// ```
29#[derive(Clone, PartialEq, Eq, PartialOrd)]
30pub struct BloomFilter<const N: usize, const K: usize> {
31    /// The underlying `BitArray`
32    pub bits: BitArray<[u8; N]>,
33}
34
35//------------------------------------------------------------------------------
36// Implementations
37//------------------------------------------------------------------------------
38
39impl<const N: usize, const K: usize> BloomFilter<N, K> {
40    /// Creates a new bloom filter with all bits unset.
41    ///
42    /// # Examples
43    ///
44    /// ```
45    /// use deterministic_bloom::const_size::BloomFilter;
46    ///
47    /// let mut filter = BloomFilter::<256, 30>::new();
48    /// filter.insert(&[0xF5u8; 32]);
49    ///
50    /// assert!(filter.contains(&[0xF5u8; 32]));
51    /// ```
52    pub fn new() -> Self {
53        Self {
54            bits: Default::default(),
55        }
56    }
57
58    /// Inserts an item to the bloom filter.
59    ///
60    /// # Examples
61    ///
62    /// ```
63    /// use deterministic_bloom::const_size::BloomFilter;
64    ///
65    /// let mut filter = BloomFilter::<256, 30>::default();
66    /// filter.insert(&[0xF5u8; 32]);
67    ///
68    /// assert!(filter.contains(&[0xF5u8; 32]));
69    /// ```
70    pub fn insert<T>(&mut self, item: &T)
71    where
72        T: AsRef<[u8]>,
73    {
74        for i in self.hash_indices(item) {
75            self.bits.set(i, true);
76        }
77    }
78
79    /// Returns the number of hash iterations the bloom filter uses to set bits.
80    ///
81    /// # Examples
82    ///
83    /// ```
84    /// use deterministic_bloom::const_size::BloomFilter;
85    ///
86    /// let mut filter = BloomFilter::<256, 30>::default();
87    ///
88    /// assert_eq!(filter.hash_count(), 30);
89    /// ```
90    pub const fn hash_count(&self) -> usize {
91        K
92    }
93
94    /// Checks if the item is in the bloom filter.
95    ///
96    /// # Examples
97    ///
98    /// ```
99    /// use deterministic_bloom::const_size::BloomFilter;
100    ///
101    /// let mut filter = BloomFilter::<256, 30>::default();
102    /// filter.insert(&[0xF5u8; 32]);
103    ///
104    /// assert!(filter.contains(&[0xF5u8; 32]));
105    /// ```
106    pub fn contains<T>(&self, item: &T) -> bool
107    where
108        T: AsRef<[u8]>,
109    {
110        self.hash_indices(item).all(|i| self.bits[i])
111    }
112
113    /// Counts the number of bits set in the bloom filter.
114    ///
115    /// # Examples
116    ///
117    /// ```
118    /// use deterministic_bloom::const_size::BloomFilter;
119    ///
120    /// let mut filter = BloomFilter::<256, 30>::default();
121    /// filter.insert(&[0xF5u8; 32]);
122    ///
123    /// assert_eq!(filter.count_ones(), 30);
124    /// ```
125    pub fn count_ones(&self) -> usize {
126        self.bits.count_ones()
127    }
128
129    /// Returns the indices of the bits that would be set if the item was inserted to the bloom filter.
130    ///
131    /// # Examples
132    ///
133    /// ```
134    /// use deterministic_bloom::const_size::BloomFilter;
135    ///
136    /// let filter = BloomFilter::<256, 30>::default();
137    /// let indices = filter.hash_indices(&[0xF5u8; 32]);
138    /// let indices = indices.collect::<Vec<_>>();
139    ///
140    /// assert_eq!(indices.len(), 30);
141    /// ```
142    #[inline]
143    pub fn hash_indices<'a, T>(&self, item: &'a T) -> impl Iterator<Item = usize> + 'a
144    where
145        T: AsRef<[u8]>,
146    {
147        HashIndexIterator::new(item, N * 8).take(self.hash_count())
148    }
149
150    /// Get the bytes of the bloom filter.
151    ///
152    /// # Examples
153    ///
154    /// ```
155    /// use deterministic_bloom::const_size::BloomFilter;
156    ///
157    /// let mut filter = BloomFilter::<256, 30>::default();
158    /// filter.insert(&[0xF5u8; 32]);
159    ///
160    /// let bytes = filter.as_bytes();
161    /// assert_eq!(bytes.len(), 256);
162    /// ```
163    #[inline]
164    pub fn as_bytes(&self) -> &[u8] {
165        self.bits.as_raw_slice()
166    }
167}
168
169impl<const N: usize, const K: usize> TryFrom<Vec<u8>> for BloomFilter<N, K> {
170    type Error = Error;
171
172    fn try_from(bytes: Vec<u8>) -> Result<Self, Self::Error> {
173        let bits = BitArray::<[u8; N]>::new(bytes.try_into().map_err(|vec: Vec<u8>| {
174            Error::VectorImportSizeMismatch {
175                expected: N,
176                actual: vec.len(),
177            }
178        })?);
179
180        Ok(Self { bits })
181    }
182}
183
184impl<const N: usize, const K: usize> Index<usize> for BloomFilter<N, K> {
185    type Output = bool;
186
187    fn index(&self, index: usize) -> &Self::Output {
188        &self.bits[index]
189    }
190}
191
192impl<const N: usize, const K: usize> Default for BloomFilter<N, K> {
193    #[inline]
194    fn default() -> Self {
195        Self::new()
196    }
197}
198
199impl<const N: usize, const K: usize> Serialize for BloomFilter<N, K> {
200    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
201    where
202        S: serde::Serializer,
203    {
204        serializer.serialize_bytes(self.bits.as_raw_slice())
205    }
206}
207
208impl<'de, const N: usize, const K: usize> Deserialize<'de> for BloomFilter<N, K> {
209    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
210    where
211        D: serde::Deserializer<'de>,
212    {
213        Ok(BloomFilter::<N, K> {
214            bits: BitArray::<[u8; N]>::new(deserializer.deserialize_bytes(ByteArrayVisitor::<N>)?),
215        })
216    }
217}
218
219impl<const N: usize, const K: usize> AsRef<[u8]> for &BloomFilter<N, K> {
220    fn as_ref(&self) -> &[u8] {
221        self.as_bytes()
222    }
223}
224
225impl<const N: usize, const K: usize> Debug for BloomFilter<N, K> {
226    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
227        f.debug_tuple("BloomFilter")
228            .field(&HexFieldDebug(self))
229            .finish()
230    }
231}
232
233//------------------------------------------------------------------------------
234// Tests
235//------------------------------------------------------------------------------
236
237#[cfg(test)]
238mod tests {
239    use super::*;
240
241    #[test]
242    fn bloom_filter_can_insert_and_validate_item_existence() {
243        let mut bloom = BloomFilter::<256, 30>::new();
244        let items: Vec<String> = vec!["first".into(), "second".into(), "third".into()];
245        items.iter().for_each(|item| {
246            bloom.insert(item);
247        });
248
249        items.iter().for_each(|item| {
250            assert!(bloom.contains(item));
251        });
252
253        assert!(!bloom.contains(b"irst"));
254        assert!(!bloom.contains(b"secnd"));
255        assert!(!bloom.contains(b"tird"));
256    }
257
258    #[test]
259    fn serialized_bloom_filter_can_be_deserialized_correctly() {
260        let mut bloom = BloomFilter::<256, 30>::new();
261        let items: Vec<String> = vec!["first".into(), "second".into(), "third".into()];
262        items.iter().for_each(|item| {
263            bloom.insert(item);
264        });
265
266        let ipld = libipld::serde::to_ipld(&bloom).unwrap();
267        let deserialized: BloomFilter<256, 30> = libipld::serde::from_ipld(ipld).unwrap();
268
269        assert_eq!(deserialized, bloom);
270    }
271}
272
273#[cfg(test)]
274mod proptests {
275    use super::BloomFilter;
276    use crate::common::HashIndexIterator;
277    use proptest::collection::vec;
278    use test_strategy::proptest;
279
280    #[proptest]
281    fn iterator_can_give_unbounded_number_of_indices(#[strategy(0usize..500)] count: usize) {
282        let iter = HashIndexIterator::new(&"hello", 200);
283
284        let indices = (0..20)
285            .map(|_| (iter.clone().take(count).collect::<Vec<_>>(), count))
286            .collect::<Vec<_>>();
287
288        for (indices, count) in indices {
289            assert_eq!(indices.len(), count);
290        }
291    }
292
293    #[proptest(cases = 1000)]
294    fn test_contains(#[strategy(vec(vec(0..255u8, 0..100), 26))] values: Vec<Vec<u8>>) {
295        let mut bloom = BloomFilter::<256, 30>::new();
296
297        for v in values.iter() {
298            bloom.insert(v);
299        }
300
301        for v in values.iter() {
302            assert!(bloom.contains(v));
303        }
304    }
305}
deterministic_bloom/const_size.rs

deterministic_bloom/
const_size.rs
