use super::block::Loc;
use crate::types::PieceHash;
const EMPTY: [u8; 32] = [0u8; 32];
#[derive(Clone, Copy)]
struct Slot {
hash: [u8; 32],
loc: Loc,
}
pub struct DedupTable {
slots: Vec<Slot>,
mask: usize,
len: usize,
zero: Option<Loc>,
}
impl DedupTable {
pub fn new() -> DedupTable {
DedupTable::with_capacity(1 << 12)
}
pub fn with_capacity(cap_pow2: usize) -> DedupTable {
let cap = cap_pow2.next_power_of_two().max(16);
DedupTable {
slots: vec![Slot { hash: EMPTY, loc: Loc::default() }; cap],
mask: cap - 1,
len: 0,
zero: None,
}
}
pub fn len(&self) -> usize {
self.len + usize::from(self.zero.is_some())
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn heap_bytes(&self) -> usize {
self.slots.len() * std::mem::size_of::<Slot>()
}
#[inline]
fn probe_start(&self, h: &[u8; 32]) -> usize {
(u64::from_le_bytes(h[0..8].try_into().unwrap()) as usize) & self.mask
}
pub fn get(&self, hash: &PieceHash) -> Option<Loc> {
if hash.0 == EMPTY {
return self.zero;
}
let mut i = self.probe_start(&hash.0);
loop {
let s = &self.slots[i];
if s.hash == EMPTY {
return None;
}
if s.hash == hash.0 {
return Some(s.loc);
}
i = (i + 1) & self.mask;
}
}
pub fn insert(&mut self, hash: PieceHash, loc: Loc) {
if hash.0 == EMPTY {
self.zero = Some(loc);
return;
}
if (self.len + 1) * 4 > self.slots.len() * 3 {
self.grow();
}
self.insert_raw(hash.0, loc);
}
fn insert_raw(&mut self, hash: [u8; 32], loc: Loc) {
let mut i = self.probe_start(&hash);
loop {
if self.slots[i].hash == EMPTY {
self.slots[i] = Slot { hash, loc };
self.len += 1;
return;
}
if self.slots[i].hash == hash {
return; }
i = (i + 1) & self.mask;
}
}
fn grow(&mut self) {
let bigger = vec![Slot { hash: EMPTY, loc: Loc::default() }; self.slots.len() * 2];
let old = std::mem::replace(&mut self.slots, bigger);
self.mask = self.slots.len() - 1;
self.len = 0;
for s in old {
if s.hash != EMPTY {
self.insert_raw(s.hash, s.loc);
}
}
}
pub fn clear(&mut self) {
for s in &mut self.slots {
s.hash = EMPTY;
}
self.len = 0;
self.zero = None;
}
}
impl Default for DedupTable {
fn default() -> Self {
DedupTable::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn loc(block_id: u32) -> Loc {
Loc { block_id, in_off: 0, raw: 20 }
}
#[test]
fn insert_get_and_miss() {
let mut t = DedupTable::with_capacity(16);
let a = PieceHash::of(b"alpha");
let b = PieceHash::of(b"beta");
assert!(t.get(&a).is_none());
t.insert(a, loc(48));
assert_eq!(t.get(&a), Some(loc(48)));
assert!(t.get(&b).is_none(), "a miss must not alias to another entry");
assert_eq!(t.len(), 1);
}
#[test]
fn survives_growth_with_no_loss_or_aliasing() {
let mut t = DedupTable::with_capacity(16);
let mut expect = Vec::new();
for i in 0..2000u32 {
let h = PieceHash::of(format!("piece-{i}").as_bytes());
t.insert(h, loc(48 + i));
expect.push((h, loc(48 + i)));
}
assert_eq!(t.len(), 2000);
for (h, l) in &expect {
assert_eq!(t.get(h), Some(*l), "entry lost or moved across growth");
}
for i in 2000..2100u32 {
let h = PieceHash::of(format!("piece-{i}").as_bytes());
assert!(t.get(&h).is_none(), "false positive — the one forbidden failure");
}
}
#[test]
fn reinsert_keeps_first_location() {
let mut t = DedupTable::new();
let h = PieceHash::of(b"same bytes");
t.insert(h, loc(100));
t.insert(h, loc(999));
assert_eq!(t.get(&h), Some(loc(100)));
assert_eq!(t.len(), 1);
}
#[test]
fn all_zero_hash_is_held_aside_not_confused_with_empty() {
let mut t = DedupTable::with_capacity(16);
let z = PieceHash([0u8; 32]);
assert!(t.get(&z).is_none());
t.insert(z, loc(7));
assert_eq!(t.get(&z), Some(loc(7)), "the empty marker must not swallow a real entry");
assert_eq!(t.len(), 1);
let other = PieceHash::of(b"other");
assert!(t.get(&other).is_none());
}
#[test]
fn clear_releases_the_window() {
let mut t = DedupTable::new();
let h = PieceHash::of(b"x");
t.insert(h, loc(1));
t.clear();
assert!(t.is_empty());
assert!(t.get(&h).is_none());
}
}