rotating-bloom-filter 0.1.1

// SPDX-FileCopyrightText: 2025-2026 eaon <eaon@posteo.net>
// SPDX-License-Identifier: EUPL-1.2

#![cfg_attr(docsrs, feature(doc_auto_cfg))]
#![doc = include_str!("../README.md")]
#![warn(missing_docs)]

use fastbloom::BloomFilter;
use rand_core::Rng;

/// A probabilistic data structure that rotates out old items to maintain recent membership.
///
/// `RotatingBloomFilter` provides membership testing for recently inserted items, with older items
/// automatically rotating out. Items are guaranteed to be retained for at least the minimum
/// retention period, and typically remain for up to twice that duration.
///
/// Uses a dual-buffer rotation mechanism where items are added to both buffers, and periodically
/// the older buffer is discarded, causing old items to rotate out.
///
/// # Examples
///
/// ```rust
/// # use rotating_bloom_filter::*;
/// # use rand::rngs::StdRng;
/// let mut csprng = rand::make_rng::<StdRng>();
/// let mut filter = RotatingBloomFilter::new(0.001, 1000, &mut csprng);
/// filter.insert("hello");
/// assert!(filter.contains("hello"));
/// // After 2000 more insertions, "hello" will rotate out
/// ```
pub struct RotatingBloomFilter {
    current: BloomFilter,
    next: BloomFilter,
    hashes: usize,
    min_retention: usize,
}

impl RotatingBloomFilter {
    /// Creates a new `RotatingBloomFilter` with a given false positive rate and minimum retention
    /// period.
    pub fn new(false_pos: f64, min_retention: usize, csprng: &mut impl Rng) -> Self {
        let mut seed_bytes = [0u8; 16];
        csprng.fill_bytes(&mut seed_bytes);
        let seed = u128::from_le_bytes(seed_bytes);

        Self {
            current: BloomFilter::with_false_pos(false_pos)
                .seed(&seed)
                .expected_items(min_retention * 2),
            next: BloomFilter::with_false_pos(false_pos)
                .seed(&seed)
                .expected_items(min_retention * 2),
            hashes: 0,
            min_retention,
        }
    }

    /// Inserts an item into the rotating filter.
    ///
    /// Items are guaranteed to be retained for at least the minimum retention period, typically
    /// remaining for up to twice that duration before rotating out.
    ///
    /// Returns a tuple: `(was_in_current, was_in_next)`
    #[inline]
    pub fn insert(&mut self, value: &(impl std::hash::Hash + ?Sized)) -> (bool, bool) {
        if self.hashes >= self.min_retention {
            std::mem::swap(&mut self.current, &mut self.next);
            self.next.clear();
            self.hashes = 0;
        };
        let hashed_value = self.current.source_hash(value);
        let presence = (
            self.current.insert_hash(hashed_value),
            self.next.insert_hash(hashed_value),
        );
        self.hashes += 1;

        presence
    }

    /// Tests whether an item might be present in the current rotation.
    ///
    /// May return false positives but never false negatives.
    #[inline]
    pub fn contains(&self, value: &(impl std::hash::Hash + ?Sized)) -> bool {
        let hashed_value = self.current.source_hash(value);
        self.current.contains_hash(hashed_value) || self.next.contains_hash(hashed_value)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    use proptest::prelude::*;
    use rand::SeedableRng;
    use rand::rngs::StdRng;

    fn seeded_filter(min_retention: usize) -> RotatingBloomFilter {
        let mut rng = StdRng::seed_from_u64(42);
        RotatingBloomFilter::new(1e-10, min_retention, &mut rng)
    }

    fn insert_dummy(filter: &mut RotatingBloomFilter, count: usize, offset: usize) {
        for i in offset..offset + count {
            filter.insert(&format!("dummy-{i}"));
        }
    }

    proptest! {
        #[test]
        fn absent_on_initial_insert(value: String) {
            let mut filter = seeded_filter(100);
            let (in_current, in_next) = filter.insert(&value);

            prop_assert!(!in_current);
            prop_assert!(!in_next);
        }

        #[test]
        fn present_on_reinsert(value: String) {
            let mut filter = seeded_filter(100);
            filter.insert(&value);
            let (in_current, in_next) = filter.insert(&value);

            prop_assert!(in_current);
            prop_assert!(in_next);
        }

        #[test]
        fn present_within_min_retention(min_retention in 10usize..200) {
            let mut filter = seeded_filter(min_retention);
            filter.insert("target");
            insert_dummy(&mut filter, min_retention - 1, 0);

            prop_assert!(filter.contains("target"));
        }

        #[test]
        fn present_after_one_rotation(min_retention in 10usize..200) {
            let mut filter = seeded_filter(min_retention);
            filter.insert("target");
            insert_dummy(&mut filter, min_retention, 0);

            prop_assert!(filter.contains("target"));
        }

        #[test]
        fn evicted_after_two_rotations(min_retention in 10usize..200) {
            let mut filter = seeded_filter(min_retention);
            filter.insert("target");
            insert_dummy(&mut filter, min_retention * 2, 0);

            prop_assert!(!filter.contains("target"));
        }

        #[test]
        fn counter_resets_after_rotation(min_retention in 10usize..200) {
            let mut filter = seeded_filter(min_retention);
            insert_dummy(&mut filter, min_retention, 0);
            filter.insert("post-rotation");

            insert_dummy(&mut filter, min_retention - 1, min_retention);
            prop_assert!(filter.contains("post-rotation"));

            insert_dummy(&mut filter, 1, min_retention * 2);
            prop_assert!(filter.contains("post-rotation"));
        }
    }
}