use core::cell::Cell;
use std::io;
use crate::BStackRaiiAllocator;
use bstack::{BStack, BStackGenOp, BStackRange};
use super::hash::fnv1a;
use crate::io_core::dealloc_range;
use crate::primitives::checked_off_mul;
use crate::types::compiled::HEADER_SIZE;
use crate::util::{SmallBuf, get_u64, io_error, read_u64};
pub(super) fn w8(off: u64, val: u64) -> (u64, SmallBuf) {
(off, SmallBuf::Buf8(val.to_le_bytes()))
}
pub(super) struct WriteBuf<const N: usize> {
buf: [(u64, SmallBuf); N],
len: usize,
}
impl<const N: usize> WriteBuf<N> {
pub(super) fn new() -> Self {
Self {
buf: core::array::from_fn(|_| (0, SmallBuf::Buf8([0; 8]))),
len: 0,
}
}
pub(super) fn push(&mut self, item: (u64, SmallBuf)) {
self.buf[self.len] = item;
self.len += 1;
}
pub(super) fn len(&self) -> usize {
self.len
}
pub(super) fn as_slice(&self) -> &[(u64, SmallBuf)] {
&self.buf[..self.len]
}
}
pub(super) fn read_fields<const N: usize>(stack: &BStack, off: u64) -> io::Result<[u64; N]> {
debug_assert!(N <= 8, "read_fields: at most 8 u64 fields");
let buf = &mut [0u8; 64][..N * 8];
stack.get_into(off, buf)?;
let mut out = [0u64; N];
#[allow(unknown_lints, clippy::chunks_exact_to_as_chunks)]
for (dst, chunk) in out.iter_mut().zip(buf.chunks_exact(8)) {
*dst = get_u64(chunk);
}
Ok(out)
}
const SCRATCH_INLINE: usize = 1024;
pub(super) struct Scratch {
inline: [u8; SCRATCH_INLINE],
spill: Vec<u8>,
}
impl Scratch {
pub(super) fn new() -> Self {
Scratch {
inline: [0u8; SCRATCH_INLINE],
spill: Vec::new(),
}
}
pub(super) fn buf(&mut self, n: usize) -> &mut [u8] {
if n <= SCRATCH_INLINE {
&mut self.inline[..n]
} else {
if self.spill.len() < n {
self.spill.resize(n, 0);
}
&mut self.spill[..n]
}
}
}
pub(super) fn alloc_image<A: BStackRaiiAllocator>(
allocator: &A,
bytes: &[u8],
) -> io::Result<BStackRange> {
let mut slice = allocator.alloc(bytes.len() as u64)?;
if let Err(e) = slice.write_range(0, bytes) {
let _ = allocator.dealloc(slice);
return Err(e);
}
Ok(slice.as_range())
}
pub(super) fn atomic_update<'w, A, R2, W>(
allocator: &A,
reads1: &[u64],
reads2: R2,
plan: W,
) -> io::Result<()>
where
A: BStackRaiiAllocator,
R2: FnOnce(&[u64]) -> io::Result<Vec<u64>>,
W: FnOnce(&[u64], &[u64]) -> io::Result<&'w [(u64, SmallBuf)]>,
{
let mut buf1: Vec<[u8; 8]> = vec![[0u8; 8]; reads1.len()];
let mut vals1: Vec<u64> = Vec::new();
let mut offs2: Vec<u64> = Vec::new();
let mut buf2: Vec<[u8; 8]> = Vec::new();
let mut writes: &'w [(u64, SmallBuf)] = &[];
let mut plan_err: Option<io::Error> = None;
let mut read_err: Option<io::Error> = None;
let mut reads2 = Some(reads2);
let mut plan = Some(plan);
let mut r1 = 0usize;
let mut did_a = false;
let mut r2 = 0usize;
let mut did_b = false;
let mut w = 0usize;
allocator.stack().inplace_gen(|feedback| {
if let Err(e) = feedback {
read_err = Some(e);
return None; }
if r1 < reads1.len() {
let i = r1;
r1 += 1;
let b: &mut [u8] = unsafe { core::mem::transmute::<&mut [u8], _>(&mut buf1[i][..]) };
return Some(BStackGenOp::Read {
offset: reads1[i],
buf: b,
});
}
if !did_a {
did_a = true;
vals1 = buf1.iter().map(|x| u64::from_le_bytes(*x)).collect();
match (reads2.take().unwrap())(&vals1) {
Ok(offs) => offs2 = offs,
Err(e) => {
plan_err = Some(e);
return None; }
}
buf2 = vec![[0u8; 8]; offs2.len()];
}
if r2 < offs2.len() {
let i = r2;
r2 += 1;
let b: &mut [u8] = unsafe { core::mem::transmute::<&mut [u8], _>(&mut buf2[i][..]) };
return Some(BStackGenOp::Read {
offset: offs2[i],
buf: b,
});
}
if !did_b {
did_b = true;
let vals2: Vec<u64> = buf2.iter().map(|x| u64::from_le_bytes(*x)).collect();
match (plan.take().unwrap())(&vals1, &vals2) {
Ok(ws) => writes = ws,
Err(e) => {
plan_err = Some(e);
return None; }
}
}
if w < writes.len() {
let i = w;
w += 1;
let (off, ref bytes) = writes[i];
let d: &[u8] = unsafe { core::mem::transmute::<&[u8], _>(bytes.as_slice()) };
return Some(BStackGenOp::Write {
offset: off,
data: d,
});
}
None
})?;
match read_err.or(plan_err) {
Some(e) => Err(e),
None => Ok(()),
}
}
pub(super) struct Meta {
pub(super) table: u64,
pub(super) cap: u64,
pub(super) len: u64,
pub(super) used: u64,
}
pub(super) enum ProbeStep {
Continue,
Stop(io::Result<Vec<(u64, SmallBuf)>>),
}
pub(super) fn probe_commit<A, I, E>(
allocator: &A,
handle: u64,
stride: u64,
hash: u64,
mut inspect: I,
exhausted: E,
) -> io::Result<()>
where
A: BStackRaiiAllocator,
I: FnMut(&Meta, u64, &[u8]) -> ProbeStep,
E: FnOnce(&Meta) -> io::Result<Vec<(u64, SmallBuf)>>,
{
let mut meta_buf = [0u8; 32];
let mut bucket_buf = vec![0u8; stride as usize];
let mut writes: Vec<(u64, SmallBuf)> = Vec::new();
let mut meta_issued = false;
let mut meta: Option<Meta> = None;
let mut mask = 0u64;
let mut cur = 0u64;
let mut idx_at_read = 0u64;
let mut probe_pending = false;
let mut probed = 0u64;
let mut decided = false;
let mut exhausted = Some(exhausted);
let mut w = 0usize;
let mut probe_err: Option<io::Error> = None;
let mut read_err: Option<io::Error> = None;
allocator.stack().inplace_gen(|feedback| {
if let Err(e) = feedback {
read_err = Some(e);
return None; }
if !meta_issued {
meta_issued = true;
let b: &mut [u8] = unsafe { core::mem::transmute::<&mut [u8], _>(&mut meta_buf[..]) };
return Some(BStackGenOp::Read {
offset: handle + HEADER_SIZE,
buf: b,
});
}
if meta.is_none() {
let m = Meta {
table: get_u64(&meta_buf[0..8]),
cap: get_u64(&meta_buf[8..16]),
len: get_u64(&meta_buf[16..24]),
used: get_u64(&meta_buf[24..32]),
};
mask = m.cap.wrapping_sub(1);
cur = if m.cap == 0 { 0 } else { hash & mask };
meta = Some(m);
}
let m = meta.as_ref().unwrap();
if probe_pending {
probe_pending = false;
if let ProbeStep::Stop(ws) = inspect(m, idx_at_read, &bucket_buf) {
match ws {
Ok(ws) => writes = ws,
Err(e) => {
probe_err = Some(e);
return None; }
}
decided = true;
}
}
if !decided {
if m.cap == 0 || probed >= m.cap {
match (exhausted.take().unwrap())(m) {
Ok(ws) => writes = ws,
Err(e) => {
probe_err = Some(e);
return None; }
}
decided = true;
} else {
idx_at_read = cur;
probe_pending = true;
probed += 1;
cur = (cur + 1) & mask;
let off = match checked_off_mul(m.table, idx_at_read, stride) {
Ok(off) => off,
Err(e) => {
probe_err = Some(e);
return None; }
};
let b: &mut [u8] =
unsafe { core::mem::transmute::<&mut [u8], _>(&mut bucket_buf[..]) };
return Some(BStackGenOp::Read {
offset: off,
buf: b,
});
}
}
if w < writes.len() {
let i = w;
w += 1;
let (off, ref bytes) = writes[i];
let d: &[u8] = unsafe { core::mem::transmute::<&[u8], _>(bytes.as_slice()) };
return Some(BStackGenOp::Write {
offset: off,
data: d,
});
}
None
})?;
match read_err.or(probe_err) {
Some(e) => Err(e),
None => Ok(()),
}
}
pub(super) fn grow_table<A: BStackRaiiAllocator>(
allocator: &A,
handle: u64,
stride: u64,
ksz: usize,
occupied: u64,
min_cap: u64,
) -> io::Result<()> {
let cap0 = read_u64(allocator.stack(), handle + HEADER_SIZE + 8)?;
let newcap = if cap0 == 0 {
min_cap
} else {
cap0.saturating_mul(2)
};
let overflow_err = || io_error!("corrupt bucket table capacity");
let new_size = newcap.checked_mul(stride).ok_or_else(overflow_err)?;
let newtable = allocator.alloc(new_size)?.as_range().start();
let mut meta_buf = [0u8; 32];
let old_size = cap0.checked_mul(stride).ok_or_else(overflow_err)?;
let mut old_buf = vec![0u8; old_size as usize];
let mut new_image: Vec<u8> = Vec::new();
let grown = Cell::new(false);
let old_table = Cell::new(0u64);
let old_cap = Cell::new(0u64);
let mut meta_issued = false;
let mut meta: Option<Meta> = None;
let mut abort = false;
let mut read_i = 0u64;
let mut built = false;
let mut writes: WriteBuf<4> = WriteBuf::new();
let mut w = 0usize;
let mut grow_err: Option<io::Error> = None;
allocator.stack().inplace_gen(|feedback| {
if let Err(e) = feedback {
grow_err = Some(e);
return None;
}
if !meta_issued {
meta_issued = true;
let b: &mut [u8] = unsafe { core::mem::transmute::<&mut [u8], _>(&mut meta_buf[..]) };
return Some(BStackGenOp::Read {
offset: handle + HEADER_SIZE,
buf: b,
});
}
if meta.is_none() {
let m = Meta {
table: get_u64(&meta_buf[0..8]),
cap: get_u64(&meta_buf[8..16]),
len: get_u64(&meta_buf[16..24]),
used: get_u64(&meta_buf[24..32]),
};
if newcap <= m.cap {
abort = true;
}
meta = Some(m);
}
if abort {
return None; }
let m = meta.as_ref().unwrap();
if read_i < m.cap {
let i = read_i;
read_i += 1;
let lo = (i * stride) as usize;
let hi = lo + stride as usize;
if hi > old_buf.len() {
grow_err = Some(io_error!("bucket table capacity changed during grow"));
return None;
}
let off = match checked_off_mul(m.table, i, stride) {
Ok(off) => off,
Err(e) => {
grow_err = Some(e);
return None; }
};
let b: &mut [u8] =
unsafe { core::mem::transmute::<&mut [u8], _>(&mut old_buf[lo..hi]) };
return Some(BStackGenOp::Read {
offset: off,
buf: b,
});
}
if !built {
built = true;
grown.set(true);
old_table.set(m.table);
old_cap.set(m.cap);
new_image = vec![0u8; new_size as usize]; let newmask = newcap - 1;
for j in 0..m.cap {
let lo = (j * stride) as usize;
if get_u64(&old_buf[lo..lo + 8]) != occupied {
continue;
}
let kb = &old_buf[lo + 8..lo + 8 + ksz];
let rest = &old_buf[lo + 8 + ksz..lo + stride as usize];
let mut idx = fnv1a(kb) & newmask;
loop {
let nlo = (idx * stride) as usize;
if get_u64(&new_image[nlo..nlo + 8]) == 0 {
new_image[nlo..nlo + 8].copy_from_slice(&occupied.to_le_bytes());
new_image[nlo + 8..nlo + 8 + ksz].copy_from_slice(kb);
new_image[nlo + 8 + ksz..nlo + stride as usize].copy_from_slice(rest);
break;
}
idx = (idx + 1) & newmask;
}
}
writes.push((
newtable,
SmallBuf::Heap(std::mem::take(&mut new_image).into_boxed_slice()),
));
writes.push(w8(handle + HEADER_SIZE, newtable));
writes.push(w8(handle + HEADER_SIZE + 8, newcap));
writes.push(w8(handle + HEADER_SIZE + 24, m.len));
}
if w < writes.len() {
let i = w;
w += 1;
let (off, ref bytes) = writes.as_slice()[i];
let d: &[u8] = unsafe { core::mem::transmute::<&[u8], _>(bytes.as_slice()) };
return Some(BStackGenOp::Write {
offset: off,
data: d,
});
}
None
})?;
if let Some(e) = grow_err {
let _ = unsafe { dealloc_range(allocator, BStackRange::new(newtable, new_size)) };
return Err(e);
}
if grown.get() {
if old_cap.get() > 0 {
let _ = unsafe {
dealloc_range(
allocator,
BStackRange::new(old_table.get(), old_cap.get().saturating_mul(stride)),
)
};
}
} else {
let _ = unsafe { dealloc_range(allocator, BStackRange::new(newtable, new_size)) };
}
Ok(())
}