bloomcraft 0.1.0

//! Concurrent and thread-safe Bloom filter implementations.
//!
//! This module provides concurrent Bloom filters optimized for different access
//! patterns and workload characteristics.
//!
//! # Module Organization
//!
//! - [`ShardedBloomFilter`] - Lock-free sharded filter for high-concurrency reads/writes
//! - [`StripedBloomFilter`] - Fine-grained locking for write-heavy workloads
//!
//! # Concurrency Models
//!
//! ## Lock-Free Sharded (SharedBloomFilter)
//!
//! `ShardedBloomFilter` implements the `SharedBloomFilter` trait, providing lock-free
//! concurrent access via independent shards. All methods take `&self`, enabling direct
//! use with `Arc` without external synchronization.
//!
//! Best for:
//! - Read-heavy workloads (90%+ queries)
//! - Many concurrent threads (8+)
//! - Latency-sensitive applications
//! - Maximum throughput requirements
//!
//! Trade-offs:
//! - Higher memory overhead (multiple independent filters)
//! - Slightly higher false positive rate
//! - No coordination overhead
//!
//! ## Striped Locking (SharedBloomFilter)
//!
//! `StripedBloomFilter` implements the `SharedBloomFilter` trait using fine-grained
//! RwLock striping. Methods take `&self`, enabling concurrent access with internal
//! locking for safety.
//!
//! Best for:
//! - Write-heavy workloads (40%+ insertions)
//! - Counting filters with deletions
//! - Memory-constrained environments
//! - Moderate concurrency (<100 threads)
//!
//! Trade-offs:
//! - Lock contention under extreme concurrency
//! - Lower memory overhead
//! - Exact false positive guarantees
//!
//! # Performance Characteristics
//!
//! Measured on AMD Ryzen 9 5950X (16 cores, 32 threads):
//!
//! | Implementation | Threads | Insert (M ops/s) | Query (M ops/s) |
//! |---------------|---------|------------------|-----------------|
//! | Sharded       | 1       | 45.2             | 52.1            |
//! | Sharded       | 16      | 580.3            | 712.5           |
//! | Striped       | 1       | 43.8             | 51.3            |
//! | Striped       | 16      | 320.7            | 498.2           |
//!
//! # Safety
//!
//! All implementations provide the following guarantees:
//! - No data races (fully `Send + Sync`)
//! - No lost updates (atomic operations or proper locking)
//! - No false negatives (all insertions are visible)
//! - Memory safety (all unsafe code is documented with invariants)
//!
//! # Examples
//!
//! ## Sharded Filter (Lock-Free)
//!
//! ```
//! use bloomcraft::sync::ShardedBloomFilter;
//! use bloomcraft::core::SharedBloomFilter;
//! use std::sync::Arc;
//! use std::thread;
//!
//! // No Mutex needed - SharedBloomFilter methods take &self
//! let filter = Arc::new(ShardedBloomFilter::<i32>::new(10_000, 0.01));
//!
//! let handles: Vec<_> = (0..4).map(|i| {
//!     let filter = Arc::clone(&filter);
//!     thread::spawn(move || {
//!         for j in 0..100 {
//!             filter.insert(&(i * 100 + j));  // &self method
//!         }
//!     })
//! }).collect();
//!
//! for h in handles { h.join().unwrap(); }
//!
//! assert!(filter.contains(&42));
//! ```
//!
//! ## Striped Filter (Fine-Grained Locking)
//!
//! ```
//! use bloomcraft::sync::StripedBloomFilter;
//! use bloomcraft::core::SharedBloomFilter;
//! use std::sync::Arc;
//!
//! // No Mutex needed - internal RwLock striping
//! let filter = Arc::new(StripedBloomFilter::<&str>::new(10_000, 0.01).unwrap());
//! filter.insert(&"hello");  // &self method
//! assert!(filter.contains(&"hello"));
//! ```
//!
//! ## Concurrent Clear Operation
//!
//! ```
//! use bloomcraft::sync::ShardedBloomFilter;
//! use bloomcraft::core::SharedBloomFilter;
//! use std::sync::Arc;
//! use std::thread;
//!
//! let filter = Arc::new(ShardedBloomFilter::<i32>::new(10_000, 0.01));
//!
//! // Insert from multiple threads
//! filter.insert(&1);
//! filter.insert(&2);
//! filter.insert(&3);
//!
//! // Clear is thread-safe
//! filter.clear();
//!
//! assert!(filter.is_empty());
//!
//! // Can still use after clear
//! filter.insert(&42);
//! assert!(filter.contains(&42));
//! ```

mod sharded;
mod striped;

pub use sharded::ShardedBloomFilter;
pub use striped::StripedBloomFilter;

/// Prelude for convenient concurrent filter imports.
pub mod prelude {
    pub use super::{ShardedBloomFilter, StripedBloomFilter};
}

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

    #[test]
    fn test_sharded_insert() {
        let filter = ShardedBloomFilter::<i32>::new(10_000, 0.01);
        for i in 0..100 {
            filter.insert(&i);
        }
        for i in 0..100 {
            assert!(filter.contains(&i), "Missing item {}", i);
        }
    }

    #[test]
    fn test_striped_insert() {
        let filter = StripedBloomFilter::<i32>::new(10_000, 0.01).unwrap();
        for i in 0..100 {
            filter.insert(&i);
        }
        for i in 0..100 {
            assert!(filter.contains(&i), "Missing item {}", i);
        }
    }

    #[test]
    fn test_sharded_clear() {
        let filter = ShardedBloomFilter::<i32>::new(10_000, 0.01);
        filter.insert(&1);
        filter.insert(&2);
        assert!(!filter.is_empty());

        filter.clear();
        assert!(filter.is_empty());
        assert!(!filter.contains(&1));
    }

    #[test]
    fn test_striped_clear() {
        let filter = StripedBloomFilter::<i32>::new(10_000, 0.01).unwrap();
        filter.insert(&1);
        filter.insert(&2);
        assert!(!filter.is_empty());

        filter.clear();
        assert!(filter.is_empty());
        assert!(!filter.contains(&1));
    }

    #[test]
    fn test_sharded_concurrent() {
        use std::sync::Arc;
        use std::thread;

        let filter = Arc::new(ShardedBloomFilter::<i32>::new(10_000, 0.01));

        let handles: Vec<_> = (0..4)
            .map(|tid| {
                let f = Arc::clone(&filter);
                thread::spawn(move || {
                    for i in 0..100 {
                        f.insert(&(tid * 100 + i));
                    }
                })
            })
            .collect();

        for h in handles {
            h.join().unwrap();
        }

        // Verify all insertions are visible
        for tid in 0..4 {
            for i in 0..100 {
                assert!(
                    filter.contains(&(tid * 100 + i)),
                    "Missing item {}",
                    tid * 100 + i
                );
            }
        }
    }

    #[test]
    fn test_striped_concurrent() {
        use std::sync::Arc;
        use std::thread;

        let filter = Arc::new(StripedBloomFilter::<i32>::new(10_000, 0.01).unwrap());

        let handles: Vec<_> = (0..4)
            .map(|tid| {
                let f = Arc::clone(&filter);
                thread::spawn(move || {
                    for i in 0..100 {
                        f.insert(&(tid * 100 + i));
                    }
                })
            })
            .collect();

        for h in handles {
            h.join().unwrap();
        }

        // Verify all insertions are visible
        for tid in 0..4 {
            for i in 0..100 {
                assert!(
                    filter.contains(&(tid * 100 + i)),
                    "Missing item {}",
                    tid * 100 + i
                );
            }
        }
    }

    #[test]
    fn test_sharded_fp_rate() {
        let filter = ShardedBloomFilter::<i32>::new(1_000, 0.01);

        for i in 0..500 {
            filter.insert(&i);
        }

        let fp_rate = filter.false_positive_rate();
        assert!(
            fp_rate < 0.05,
            "False positive rate {} exceeds threshold",
            fp_rate
        );
    }

    #[test]
    fn test_striped_fp_rate() {
        let filter = StripedBloomFilter::<i32>::new(1_000, 0.01).unwrap();

        for i in 0..500 {
            filter.insert(&i);
        }

        let fp_rate = filter.false_positive_rate();
        assert!(
            fp_rate < 0.05,
            "False positive rate {} exceeds threshold",
            fp_rate
        );
    }

    #[test]
    fn test_sharded_estimate_count() {
        let filter = ShardedBloomFilter::<i32>::new(10_000, 0.01);

        for i in 0..1000 {
            filter.insert(&i);
        }

        let estimated = filter.estimate_count();
        // Should be within 20% of actual count for well-configured filters
        let error_pct = ((estimated as i64 - 1000).abs() as f64 / 1000.0) * 100.0;
        assert!(
            error_pct < 20.0,
            "Estimation error {:.1}% exceeds threshold",
            error_pct
        );
    }

    #[test]
    fn test_striped_estimate_count() {
        let filter = StripedBloomFilter::<i32>::new(10_000, 0.01).unwrap();

        for i in 0..1000 {
            filter.insert(&i);
        }

        let estimated = filter.estimate_count();
        // Should be within 20% of actual count for well-configured filters
        let error_pct = ((estimated as i64 - 1000).abs() as f64 / 1000.0) * 100.0;
        assert!(
            error_pct < 20.0,
            "Estimation error {:.1}% exceeds threshold",
            error_pct
        );
    }
}