pub const BLOOM_DEFAULT_CAPACITY: usize = 1_000_000;
pub const BLOOM_TARGET_FPR: f64 = 0.01;
pub type UrlBloom = oxcache::features::BloomFilter;
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_default_constants() {
assert_eq!(BLOOM_DEFAULT_CAPACITY, 1_000_000);
assert_eq!(BLOOM_TARGET_FPR, 0.01);
}
#[test]
fn test_new_params_recorded() {
let bloom = UrlBloom::new(BLOOM_DEFAULT_CAPACITY, BLOOM_TARGET_FPR);
assert_eq!(bloom.capacity(), 1_000_000);
assert!((bloom.false_positive_rate() - 0.01).abs() < f64::EPSILON);
assert!(bloom.is_empty());
assert_eq!(bloom.len(), 0);
}
#[test]
fn test_insert_contains() {
let bloom = UrlBloom::new(1000, BLOOM_TARGET_FPR);
bloom.insert("https://example.com");
assert!(bloom.contains("https://example.com"));
assert!(!bloom.contains("https://other.com"));
}
#[test]
fn test_empty() {
let bloom = UrlBloom::new(1000, BLOOM_TARGET_FPR);
assert!(bloom.is_empty());
assert_eq!(bloom.len(), 0);
assert!(!bloom.contains("anything"));
}
#[test]
fn test_clear() {
let bloom = UrlBloom::new(1000, BLOOM_TARGET_FPR);
bloom.insert("https://example.com");
assert!(bloom.contains("https://example.com"));
bloom.clear();
assert!(bloom.is_empty());
assert!(!bloom.contains("https://example.com"));
}
#[test]
fn test_false_positive_rate_under_1_5_percent() {
let n = 100_000usize;
let bloom = UrlBloom::new(n, BLOOM_TARGET_FPR);
for i in 0..n {
bloom.insert(&format!("url-{i}"));
}
assert_eq!(bloom.len(), n as u64);
let probe = 100_000usize;
let mut false_positives = 0;
for i in n..(n + probe) {
if bloom.contains(&format!("url-{i}")) {
false_positives += 1;
}
}
let fp_rate = false_positives as f64 / probe as f64;
assert!(
fp_rate < 0.015,
"false positive rate too high: {:.3}%",
fp_rate * 100.0
);
}
#[test]
fn test_no_false_negatives_at_full_capacity() {
let n = 1_000_000usize;
let bloom = UrlBloom::new(n, BLOOM_TARGET_FPR);
for i in 0..n {
bloom.insert(&format!("https://site.com/{i}"));
}
for i in 0..n {
assert!(
bloom.contains(&format!("https://site.com/{i}")),
"false negative for key {i}"
);
}
}
#[test]
fn test_clone_shares_state() {
let bloom = UrlBloom::new(1000, BLOOM_TARGET_FPR);
bloom.insert("https://a.com");
let cloned = bloom.clone();
assert!(cloned.contains("https://a.com"));
cloned.insert("https://b.com");
assert!(bloom.contains("https://b.com"), "clone 共享位图状态");
}
#[test]
fn test_observable_stats_after_insert() {
let bloom = UrlBloom::new(1000, BLOOM_TARGET_FPR);
assert_eq!(bloom.set_bits(), 0, "空过滤器无置位");
bloom.insert("https://a.com");
assert!(bloom.set_bits() > 0, "插入后应有置位");
assert!(bloom.hash_count() > 0);
assert!(bloom.load_factor() > 0.0);
}
#[test]
fn test_concurrent_insert_lookup_no_data_race() {
use std::sync::Arc;
use std::thread;
let bloom = Arc::new(UrlBloom::new(50_000, BLOOM_TARGET_FPR));
let threads = 4usize;
let per_thread = 10_000usize;
let mut handles = Vec::new();
for t in 0..threads {
let bloom = Arc::clone(&bloom);
handles.push(thread::spawn(move || {
for i in 0..per_thread {
let key = format!("https://t{t}.com/{i}");
bloom.insert(&key);
assert!(bloom.contains(&key), "insert 后必须可查: {key}");
}
}));
}
for handle in handles {
handle.join().expect("thread must not panic");
}
for t in 0..threads {
for i in 0..per_thread {
assert!(
bloom.contains(&format!("https://t{t}.com/{i}")),
"并发写入后丢失: t{t}/{i}"
);
}
}
assert_eq!(bloom.len(), (threads * per_thread) as u64);
}
}