use core::marker::PhantomData;
use core::mem::size_of;
use std::io;
use crate::BStackRaiiAllocator;
use bstack::{BStack, BStackGenOp, BStackRange};
use bytemuck::{Pod, Zeroable};
use super::hash::double_hash;
use super::util::{alloc_image, read_fields, w8};
use crate::io_core::{ClonePlan, TryCloneIn, dealloc_range};
use crate::primitives::EightCC;
use crate::types::compiled::{BStackOwned, BlockHeader, HEADER_SIZE};
use crate::types::traits::{BStackBlock, BStackCast};
use crate::util::{SmallBuf, io_error, read_u64};
#[repr(C)]
#[derive(Clone, Copy, Pod, Zeroable)]
pub struct BloomOnDisk {
pub header: BlockHeader,
pub data: u64,
pub m: u64,
pub k: u64,
pub n: u64,
}
const DATA_OFF: u64 = HEADER_SIZE; const M_OFF: u64 = HEADER_SIZE + 8; const N_OFF: u64 = HEADER_SIZE + 24; const BLOOM_SIZE: u64 = size_of::<BloomOnDisk>() as u64;
pub struct BStackCountingBloomFilter<K: Pod> {
range: BStackRange,
_marker: PhantomData<fn() -> K>,
}
impl<K: Pod> BStackCountingBloomFilter<K> {
fn indices(m: u64, k: u64, key_bytes: &[u8]) -> io::Result<Vec<u64>> {
if m == 0 {
return Err(io_error!("corrupt bloom filter: zero counter count"));
}
let (h1, h2) = double_hash(key_bytes);
Ok((0..k)
.map(|i| h1.wrapping_add(i.wrapping_mul(h2)) % m)
.collect())
}
fn aggregate(mut idxs: Vec<u64>) -> Vec<(u64, u32)> {
idxs.sort_unstable();
let mut out: Vec<(u64, u32)> = Vec::new();
for x in idxs {
match out.last_mut() {
Some(last) if last.0 == x => last.1 += 1,
_ => out.push((x, 1)),
}
}
out
}
pub fn new<A: BStackRaiiAllocator>(
allocator: &A,
m: u64,
k: u64,
) -> io::Result<BStackOwned<Self>> {
let m = m.max(1);
let k = k.max(1);
let data = {
let mut slice = allocator.alloc(m)?;
if let Err(e) = slice.write_range(0, vec![0u8; m as usize]) {
let _ = allocator.dealloc(slice);
return Err(e);
}
slice.as_range().start()
};
let od = BloomOnDisk {
header: BlockHeader {
size: BLOOM_SIZE,
tag: Self::eightcc(),
},
data,
m,
k,
n: 0,
};
match alloc_image(allocator, bytemuck::bytes_of(&od)) {
Ok(range) => Ok(unsafe { BStackOwned::from_raw(Self::from_range(range)) }),
Err(e) => {
let _ = unsafe { dealloc_range(allocator, BStackRange::new(data, m)) };
Err(e)
}
}
}
pub fn with_capacity<A: BStackRaiiAllocator>(
allocator: &A,
expected_items: u64,
fp_rate: f64,
) -> io::Result<BStackOwned<Self>> {
let n = expected_items.max(1) as f64;
let p = fp_rate.clamp(1e-9, 0.5);
let ln2 = core::f64::consts::LN_2;
let m = (-(n * p.ln()) / (ln2 * ln2)).ceil().max(1.0) as u64;
let k = ((m as f64 / n) * ln2).round().clamp(1.0, 32.0) as u64;
Self::new(allocator, m, k)
}
pub fn count(&self, stack: &BStack) -> io::Result<u64> {
read_u64(stack, self.range.start() + N_OFF)
}
pub fn is_empty(&self, stack: &BStack) -> io::Result<bool> {
Ok(self.count(stack)? == 0)
}
pub fn estimated_fp_rate(&self, stack: &BStack) -> io::Result<f64> {
let handle = self.range.start();
let [m, k, n] = read_fields::<3>(stack, handle + M_OFF)?;
let (m, k, n) = (m as f64, k as f64, n as f64);
Ok((1.0 - (-k * n / m).exp()).powf(k))
}
pub fn insert<A: BStackRaiiAllocator>(&self, allocator: &A, key: &K) -> io::Result<()> {
self.adjust(allocator, key, true)
}
pub fn remove<A: BStackRaiiAllocator>(&self, allocator: &A, key: &K) -> io::Result<()> {
self.adjust(allocator, key, false)
}
pub fn contains(&self, stack: &BStack, key: &K) -> io::Result<bool> {
let handle = self.range.start();
let [data, m, k] = read_fields::<3>(stack, handle + DATA_OFF)?;
let key_bytes = bytemuck::bytes_of(key);
for idx in Self::indices(m, k, key_bytes)? {
let mut b = [0u8; 1];
let off = data
.checked_add(idx)
.ok_or_else(|| io_error!("bloom filter offset overflow"))?;
stack.get_into(off, &mut b)?;
if b[0] == 0 {
return Ok(false);
}
}
Ok(true)
}
pub fn clear<A: BStackRaiiAllocator>(&self, allocator: &A) -> io::Result<()> {
let handle = self.range.start();
let [data, m] = read_fields::<2>(allocator.stack(), handle + DATA_OFF)?;
if m > allocator.len()? {
return Err(io_error!(
"bloom filter counter array larger than the stack"
));
}
allocator.stack().set_batched([
(
data,
SmallBuf::Heap(vec![0u8; m as usize].into_boxed_slice()),
),
w8(handle + N_OFF, 0u64),
])
}
fn adjust<A: BStackRaiiAllocator>(&self, allocator: &A, key: &K, add: bool) -> io::Result<()> {
let handle = self.range.start();
let [data, m, k] = read_fields::<3>(allocator.stack(), handle + DATA_OFF)?;
let agg = Self::aggregate(Self::indices(m, k, bytemuck::bytes_of(key))?);
let cn = agg.len();
let offs: Vec<u64> = agg
.iter()
.map(|&(idx, _)| {
data.checked_add(idx)
.ok_or_else(|| io_error!("bloom filter offset overflow"))
})
.collect::<io::Result<Vec<u64>>>()?;
let mut read_c = vec![0u8; cn];
let mut n_buf = [0u8; 8];
let mut new_c = vec![0u8; cn];
let mut new_n = [0u8; 8];
let mut rc = 0usize;
let mut n_read = false;
let mut computed = false;
let mut wc = 0usize;
let mut n_written = false;
let mut read_err: Option<io::Error> = None;
let result = allocator.stack().inplace_gen(|feedback| {
if let Err(e) = feedback {
read_err = Some(e);
return None; }
if rc < cn {
let i = rc;
rc += 1;
let b: &mut [u8] =
unsafe { core::mem::transmute::<&mut [u8], _>(&mut read_c[i..i + 1]) };
return Some(BStackGenOp::Read {
offset: offs[i],
buf: b,
});
}
if !n_read {
n_read = true;
let b: &mut [u8] = unsafe { core::mem::transmute::<&mut [u8], _>(&mut n_buf[..]) };
return Some(BStackGenOp::Read {
offset: handle + N_OFF,
buf: b,
});
}
if !computed {
computed = true;
for i in 0..cn {
let mult = agg[i].1.min(255) as u8;
new_c[i] = if !add && read_c[i] == 255 {
255
} else if add {
read_c[i].saturating_add(mult)
} else {
read_c[i].saturating_sub(mult)
};
}
let n = u64::from_le_bytes(n_buf);
let nn = if add {
n.saturating_add(1)
} else {
n.saturating_sub(1)
};
new_n = nn.to_le_bytes();
}
if wc < cn {
let i = wc;
wc += 1;
let d: &[u8] = unsafe { core::mem::transmute::<&[u8], _>(&new_c[i..i + 1]) };
return Some(BStackGenOp::Write {
offset: offs[i],
data: d,
});
}
if !n_written {
n_written = true;
let d: &[u8] = unsafe { core::mem::transmute::<&[u8], _>(&new_n[..]) };
return Some(BStackGenOp::Write {
offset: handle + N_OFF,
data: d,
});
}
None
});
match read_err {
Some(e) => Err(e),
None => result,
}
}
}
impl<K: Pod> BStackCast for BStackCountingBloomFilter<K> {
fn eightcc() -> EightCC {
const BASE: EightCC = EightCC::new([b'B', b'l', b'm', 0x80, 0x81, 0x82, 0x83, 0x84]);
BASE.mix(EightCC::new((size_of::<K>() as u64).to_le_bytes()))
}
}
impl<K: Pod> crate::types::traits::BStackEmbeddable for BStackCountingBloomFilter<K> {}
impl<K: Pod> BStackBlock for BStackCountingBloomFilter<K> {
type OnDisk = BloomOnDisk;
unsafe fn from_range(range: BStackRange) -> Self {
BStackCountingBloomFilter {
range,
_marker: PhantomData,
}
}
fn range(&self) -> BStackRange {
self.range
}
fn __bstack_drop_children<A: BStackRaiiAllocator>(
allocator: &A,
range: BStackRange,
) -> io::Result<()> {
let [data, m] = read_fields::<2>(allocator.stack(), range.start() + DATA_OFF)?;
if data != 0 {
unsafe { dealloc_range(allocator, BStackRange::new(data, m))? };
}
Ok(())
}
fn __bstack_clone_children_inplace<A: BStackRaiiAllocator>(
&self,
allocator: &A,
plan: &mut ClonePlan,
) -> io::Result<Self::OnDisk> {
let handle = self.range.start();
let [data, m, k, n] = read_fields::<4>(allocator.stack(), handle + DATA_OFF)?;
let new_data = if m != 0 {
if m > allocator.len()? {
return Err(io_error!(
"bloom filter counter array larger than the stack"
));
}
let mut bytes = vec![0u8; m as usize];
allocator.stack().get_into(data, &mut bytes)?;
let dst = plan.alloc_raw(allocator, m)?;
plan.write(dst.start(), bytes);
dst.start()
} else {
0
};
let od = BloomOnDisk {
header: BlockHeader {
size: BLOOM_SIZE,
tag: Self::eightcc(),
},
data: new_data,
m,
k,
n,
};
Ok(od)
}
}
impl<K: Pod> TryCloneIn for BStackCountingBloomFilter<K> {}