bevy_utils/
bloom_filter.rs

1use bevy_platform::hash::FixedHasher;
2use core::hash::{BuildHasher, Hash};
3
4/// A Bloom filter, parameterized by number of u64 segments `N` and number of hash functions `K`.
5///
6/// `N` should be based on how much you plan to insert into the filter.
7/// `N * 64` should be at least the number of items you plan to insert.
8///
9/// `K` if how little you can tolerate false positives.
10/// 2, the default, should work for most uses. Increase `K` to reduce false positives,
11/// at a pretty large compute cost.
12///
13/// # Examples
14///
15/// ```
16/// use bevy_utils::BloomFilter;
17///
18/// let mut filter = BloomFilter::<1>::new();
19/// filter.insert(&"hello");
20/// assert!(filter.contains(&"hello"));
21/// assert!(!filter.contains(&"world"));
22/// ```
23#[derive(Clone, Copy, Debug)]
24pub struct BloomFilter<const N: usize, const K: usize = 2> {
25    bits: [u64; N],
26}
27
28impl<const N: usize, const K: usize> Default for BloomFilter<N, K> {
29    fn default() -> Self {
30        Self::new()
31    }
32}
33
34impl<const N: usize, const K: usize> BloomFilter<N, K> {
35    /// Creates a new, empty filter.
36    pub const fn new() -> Self {
37        assert!(N > 0, "size must be at least 1");
38        Self { bits: [0; N] }
39    }
40
41    /// Inserts a value into the filter.
42    pub fn insert(&mut self, item: &impl Hash) {
43        let (h1, h2) = self.hash(item);
44        let m = (N * 64) as u64;
45        for i in 0..K {
46            let idx = (h1.wrapping_add((i as u64).wrapping_mul(h2))) % m;
47            self.bits[idx as usize / 64] |= 1 << (idx % 64);
48        }
49    }
50
51    /// Checks if the filter might contain the value.
52    pub fn contains(&self, item: &impl Hash) -> bool {
53        let (h1, h2) = self.hash(item);
54        let m = (N * 64) as u64;
55        for i in 0..K {
56            let idx = (h1.wrapping_add((i as u64).wrapping_mul(h2))) % m;
57            if self.bits[idx as usize / 64] & (1 << (idx % 64)) == 0 {
58                return false;
59            }
60        }
61        true
62    }
63
64    /// Combined [`Self::contains`] and [`Self::insert`].
65    ///
66    /// Returns `true` if the value was already in the filter.
67    /// Adds the value to the filter if it was not already present.
68    pub fn check_insert(&mut self, item: &impl Hash) -> bool {
69        let res = self.contains(item);
70        if !res {
71            self.insert(item);
72        }
73        res
74    }
75
76    fn hash(&self, item: &impl Hash) -> (u64, u64) {
77        let hash = FixedHasher.hash_one(item);
78        (hash as u32 as u64, hash >> 32)
79    }
80}
bevy_utils/bloom_filter.rs

bevy_utils/
bloom_filter.rs
