use super::bloom::{UrlBloom, BLOOM_DEFAULT_CAPACITY, BLOOM_TARGET_FPR};
use hashbrown::HashSet;
pub struct UrlInterner {
links_visited: HashSet<String>,
bloom: UrlBloom,
}
impl std::fmt::Debug for UrlInterner {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("UrlInterner")
.field("links_visited_len", &self.links_visited.len())
.field("bloom_len", &self.bloom.len())
.field("bloom_capacity", &self.bloom.capacity())
.finish()
}
}
impl Default for UrlInterner {
fn default() -> Self {
Self {
links_visited: HashSet::new(),
bloom: UrlBloom::new(BLOOM_DEFAULT_CAPACITY, BLOOM_TARGET_FPR),
}
}
}
impl UrlInterner {
pub fn new() -> Self {
Self::default()
}
pub fn with_capacity(capacity: usize) -> Self {
let cap = if capacity == 0 {
BLOOM_DEFAULT_CAPACITY
} else {
capacity
};
Self {
links_visited: HashSet::new(),
bloom: UrlBloom::new(cap, BLOOM_TARGET_FPR),
}
}
#[inline]
pub fn insert(&mut self, url: impl AsRef<str>) {
let url_ref = url.as_ref();
if self.links_visited.len() * 10 >= self.bloom.capacity() * 9 {
self.rebuild_bloom_scaled();
}
self.bloom.insert(url_ref);
self.links_visited.insert(url_ref.to_string());
}
fn rebuild_bloom_scaled(&mut self) {
let new_cap = self.bloom.capacity().saturating_mul(2);
let new_bloom = UrlBloom::new(new_cap, BLOOM_TARGET_FPR);
for url in &self.links_visited {
new_bloom.insert(url);
}
self.bloom = new_bloom;
}
#[inline]
pub fn extend<I, S>(&mut self, urls: I)
where
I: IntoIterator<Item = S>,
S: AsRef<str>,
{
for u in urls {
self.insert(u);
}
}
#[inline]
pub fn contains(&self, url: &str) -> bool {
if !self.bloom.contains(url) {
return false;
}
self.links_visited.contains(url)
}
#[inline]
pub fn definitely_absent(&self, url: &str) -> bool {
!self.bloom.contains(url)
}
#[inline]
pub fn remove(&mut self, url: &str) -> bool {
self.links_visited.remove(url)
}
#[inline]
pub fn len(&self) -> usize {
self.links_visited.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.links_visited.is_empty()
}
pub fn clear(&mut self) {
self.links_visited.clear();
self.bloom.clear();
}
pub fn get_links(&self) -> HashSet<String> {
self.links_visited.clone()
}
pub fn bloom(&self) -> &UrlBloom {
&self.bloom
}
}
impl Clone for UrlInterner {
fn clone(&self) -> Self {
let capability = self.bloom.capacity();
let bloom = UrlBloom::new(capability, BLOOM_TARGET_FPR);
for url in &self.links_visited {
bloom.insert(url);
}
Self {
links_visited: self.links_visited.clone(),
bloom,
}
}
}
impl PartialEq for UrlInterner {
fn eq(&self, other: &Self) -> bool {
self.links_visited == other.links_visited
}
}
impl Eq for UrlInterner {}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_new_is_empty() {
let interner = UrlInterner::new();
assert!(interner.is_empty());
assert_eq!(interner.len(), 0);
}
#[test]
fn test_interner_rebuilds_bloom_when_near_capacity() {
let mut interner = UrlInterner::with_capacity(16);
for i in 0..20 {
interner.insert(format!("https://example.com/page{i}"));
}
assert_eq!(
interner.bloom().capacity(),
32,
"bloom must double capacity once load passes 90% of 16"
);
assert_eq!(interner.bloom().len(), 20);
assert_eq!(interner.len(), 20, "HashSet count must be exact");
for i in 0..20 {
assert!(
interner.contains(&format!("https://example.com/page{i}")),
"rebuild must not introduce false negatives for page{i}"
);
}
}
#[test]
fn test_insert_contains() {
let mut interner = UrlInterner::new();
interner.insert("https://example.com");
assert!(interner.contains("https://example.com"));
assert!(!interner.contains("https://other.com"));
}
#[test]
fn test_definitely_absent() {
let mut interner = UrlInterner::new();
interner.insert("https://example.com");
assert!(!interner.definitely_absent("https://example.com"));
assert!(interner.definitely_absent("https://other.com"));
}
#[test]
fn test_len_after_insert() {
let mut interner = UrlInterner::new();
interner.insert("https://a.com");
interner.insert("https://b.com");
assert_eq!(interner.len(), 2);
}
#[test]
fn test_duplicate_insert_no_count_increase() {
let mut interner = UrlInterner::new();
interner.insert("https://a.com");
interner.insert("https://a.com");
assert_eq!(interner.len(), 1);
}
#[test]
fn test_extend() {
let mut interner = UrlInterner::new();
interner.extend(["https://a.com", "https://b.com", "https://c.com"]);
assert_eq!(interner.len(), 3);
assert!(interner.contains("https://a.com"));
assert!(interner.contains("https://b.com"));
assert!(interner.contains("https://c.com"));
}
#[test]
fn test_clear() {
let mut interner = UrlInterner::new();
interner.insert("https://a.com");
interner.insert("https://b.com");
assert_eq!(interner.len(), 2);
interner.clear();
assert!(interner.is_empty());
assert_eq!(interner.len(), 0);
assert!(interner.definitely_absent("https://a.com"));
}
#[test]
fn test_remove() {
let mut interner = UrlInterner::new();
interner.insert("https://a.com");
assert!(interner.contains("https://a.com"));
assert!(interner.remove("https://a.com"));
assert!(!interner.contains("https://a.com"));
}
#[test]
fn test_remove_nonexistent_returns_false() {
let mut interner = UrlInterner::new();
assert!(!interner.remove("https://nonexistent.com"));
}
#[test]
fn test_get_links() {
let mut interner = UrlInterner::new();
interner.insert("https://a.com");
interner.insert("https://b.com");
let links = interner.get_links();
assert_eq!(links.len(), 2);
assert!(links.contains("https://a.com"));
assert!(links.contains("https://b.com"));
}
#[test]
fn test_clone() {
let mut interner = UrlInterner::new();
interner.insert("https://a.com");
let cloned = interner.clone();
assert_eq!(cloned.len(), 1);
assert!(cloned.contains("https://a.com"));
}
#[test]
fn test_clone_independence() {
let mut interner = UrlInterner::new();
interner.insert("https://a.com");
let mut cloned = interner.clone();
cloned.insert("https://b.com");
assert!(!interner.contains("https://b.com"));
assert!(cloned.contains("https://b.com"));
}
#[test]
fn test_with_capacity() {
let interner = UrlInterner::with_capacity(1000);
assert!(interner.is_empty());
assert_eq!(interner.bloom().capacity(), 1000);
assert_eq!(interner.bloom().len(), 0);
}
#[test]
fn test_with_capacity_zero_normalized_to_default() {
let interner = UrlInterner::with_capacity(0);
assert!(interner.is_empty());
assert_eq!(interner.bloom().capacity(), BLOOM_DEFAULT_CAPACITY);
}
#[test]
fn test_large_insert_no_false_negatives() {
let mut interner = UrlInterner::with_capacity(5000);
let urls: Vec<String> = (0..5000)
.map(|i| format!("https://site.com/{}", i))
.collect();
for url in &urls {
interner.insert(url);
}
for url in &urls {
assert!(interner.contains(url), "False negative for {}", url);
}
}
#[test]
fn test_bloom_pre_check_skips_hashset() {
let mut interner = UrlInterner::new();
interner.insert("https://a.com");
assert!(interner.definitely_absent("https://b.com"));
assert!(interner.definitely_absent("https://c.com"));
assert!(!interner.definitely_absent("https://a.com"));
}
}