use core::cell::Cell;
use core::marker::PhantomData;
use core::mem::size_of;
use std::io;
use crate::BStackRaiiAllocator;
use bstack::{BStack, BStackRange};
use bytemuck::{Pod, Zeroable};
use super::hash::fnv1a;
use super::util::{
Meta, ProbeStep, Scratch, alloc_image, grow_table, probe_commit, read_fields, w8,
};
use crate::handback::ReplaceError;
use crate::io_core::{ClonePlan, TryCloneIn, dealloc_range};
use crate::primitives::{EightCC, checked_off, checked_off_mul};
use crate::types::compiled::{BStackOwned, BlockHeader, HEADER_SIZE};
use crate::types::traits::{BStackBlock, BStackCast, BStackDrop};
use crate::util::{SmallBuf, get_u64, io_error, read_u64};
#[repr(C)]
#[derive(Clone, Copy, Pod, Zeroable)]
pub struct MapOnDisk {
pub header: BlockHeader,
pub table: u64,
pub cap: u64,
pub len: u64,
pub used: u64,
}
const TABLE_OFF: u64 = HEADER_SIZE; const CAP_OFF: u64 = HEADER_SIZE + 8; const LEN_OFF: u64 = HEADER_SIZE + 16; const USED_OFF: u64 = HEADER_SIZE + 24;
const MAP_SIZE: u64 = size_of::<MapOnDisk>() as u64;
const MIN_CAP: u64 = 4;
const EMPTY: u64 = 0;
const OCCUPIED: u64 = 1;
const TOMBSTONE: u64 = 2;
struct NewEntry<'a> {
handle: u64,
stride: u64,
ksz: usize,
key_bytes: &'a [u8],
val_ref: u64,
}
fn new_bucket_writes(
e: &NewEntry,
m: &Meta,
target: u64,
slot_was_empty: bool,
) -> io::Result<Vec<(u64, SmallBuf)>> {
let mut img = Vec::with_capacity(16 + e.ksz);
img.extend_from_slice(&OCCUPIED.to_le_bytes());
img.extend_from_slice(e.key_bytes);
img.extend_from_slice(&e.val_ref.to_le_bytes());
let off = checked_off_mul(m.table, target, e.stride)?;
let mut w = vec![
(off, SmallBuf::Heap(img.into_boxed_slice())),
w8(e.handle + LEN_OFF, m.len + 1),
];
if slot_was_empty {
w.push(w8(e.handle + USED_OFF, m.used + 1));
}
Ok(w)
}
pub struct BStackHashMap<K: Pod, V: BStackBlock> {
range: BStackRange,
_marker: PhantomData<fn() -> (K, V)>,
}
impl<K: Pod, V: BStackBlock> BStackHashMap<K, V> {
fn ksize() -> usize {
size_of::<K>()
}
fn stride() -> u64 {
16 + Self::ksize() as u64
}
fn value_size() -> u64 {
size_of::<<V as BStackBlock>::OnDisk>() as u64
}
fn value_at(off: u64) -> V {
unsafe { <V as BStackBlock>::from_range(BStackRange::new(off, Self::value_size())) }
}
pub fn new<A: BStackRaiiAllocator>(allocator: &A) -> io::Result<BStackOwned<Self>> {
let od = MapOnDisk {
header: BlockHeader {
size: MAP_SIZE,
tag: Self::eightcc(),
},
table: 0,
cap: 0,
len: 0,
used: 0,
};
let range = alloc_image(allocator, bytemuck::bytes_of(&od))?;
Ok(unsafe { BStackOwned::from_raw(Self::from_range(range)) })
}
pub fn len(&self, stack: &BStack) -> io::Result<u64> {
read_u64(stack, self.range.start() + LEN_OFF)
}
pub fn is_empty(&self, stack: &BStack) -> io::Result<bool> {
Ok(self.len(stack)? == 0)
}
pub fn insert<A: BStackRaiiAllocator>(
&self,
allocator: &A,
key: K,
value: BStackOwned<V>,
) -> Result<Option<BStackOwned<V>>, ReplaceError<BStackOwned<V>>> {
let handle = self.range.start();
let stride = Self::stride();
let ksz = Self::ksize();
let key_bytes = bytemuck::bytes_of(&key).to_vec();
let value = value.auto(allocator);
let val_ref = value.range().start();
let hash = fnv1a(&key_bytes);
let entry = NewEntry {
handle,
stride,
ksz,
key_bytes: &key_bytes,
val_ref,
};
let outcome: io::Result<Option<BStackOwned<V>>> = (|| loop {
let [cap, _len, used] = read_fields::<3>(allocator.stack(), handle + CAP_OFF)?;
if cap == 0 || (used as u128 + 1) * 4 > cap as u128 * 3 {
self.grow(allocator)?;
continue;
}
let first_tomb: Cell<Option<u64>> = Cell::new(None);
let is_new = Cell::new(false);
let need_grow = Cell::new(false);
let old_value = Cell::new(0u64);
probe_commit(
allocator,
handle,
stride,
hash,
|m, idx, buf| {
let state = get_u64(&buf[0..8]);
if state == EMPTY {
let target = first_tomb.get().unwrap_or(idx);
let slot_was_empty = first_tomb.get().is_none();
is_new.set(true);
ProbeStep::Stop(new_bucket_writes(&entry, m, target, slot_was_empty))
} else if state == OCCUPIED && buf[8..8 + ksz] == key_bytes[..] {
old_value.set(get_u64(&buf[8 + ksz..8 + ksz + 8]));
is_new.set(false);
let step = checked_off_mul(m.table, idx, stride)
.and_then(|b| checked_off(b, 8 + ksz as u64))
.map(|value_off| vec![w8(value_off, val_ref)]);
ProbeStep::Stop(step)
} else {
if state == TOMBSTONE && first_tomb.get().is_none() {
first_tomb.set(Some(idx));
}
ProbeStep::Continue
}
},
|m| {
if let Some(t) = first_tomb.get() {
is_new.set(true);
new_bucket_writes(&entry, m, t, false)
} else {
need_grow.set(true);
Ok(Vec::new())
}
},
)?;
if need_grow.get() {
self.grow(allocator)?;
continue;
}
return if is_new.get() {
Ok(None)
} else {
Ok(Some(unsafe {
BStackOwned::from_raw(Self::value_at(old_value.get()))
}))
};
})();
value.finish_handback(outcome)
}
pub fn remove<A: BStackRaiiAllocator>(
&self,
allocator: &A,
key: &K,
) -> io::Result<Option<BStackOwned<V>>> {
let handle = self.range.start();
let stride = Self::stride();
let ksz = Self::ksize();
let key_bytes = bytemuck::bytes_of(key).to_vec();
let hash = fnv1a(&key_bytes);
let found = Cell::new(false);
let old_value = Cell::new(0u64);
probe_commit(
allocator,
handle,
stride,
hash,
|m, idx, buf| {
let state = get_u64(&buf[0..8]);
if state == EMPTY {
ProbeStep::Stop(Ok(Vec::new())) } else if state == OCCUPIED && buf[8..8 + ksz] == key_bytes[..] {
found.set(true);
old_value.set(get_u64(&buf[8 + ksz..8 + ksz + 8]));
let step = checked_off_mul(m.table, idx, stride)
.map(|off| vec![w8(off, TOMBSTONE), w8(handle + LEN_OFF, m.len - 1)]);
ProbeStep::Stop(step)
} else {
ProbeStep::Continue
}
},
|_m| Ok(Vec::new()),
)?;
if found.get() {
Ok(Some(unsafe {
BStackOwned::from_raw(Self::value_at(old_value.get()))
}))
} else {
Ok(None)
}
}
pub fn get(&self, stack: &BStack, key: &K) -> io::Result<Option<V>> {
let handle = self.range.start();
let stride = Self::stride();
let ksz = Self::ksize();
let [table, cap] = read_fields::<2>(stack, handle + TABLE_OFF)?;
if cap == 0 {
return Ok(None);
}
let key_bytes = bytemuck::bytes_of(key);
let mask = cap - 1;
let mut idx = fnv1a(key_bytes) & mask;
let mut scratch = Scratch::new();
for _ in 0..cap {
let bucket = checked_off_mul(table, idx, stride)?;
let buf = scratch.buf(stride as usize);
stack.get_into(bucket, buf)?;
let state = get_u64(&buf[0..8]);
if state == EMPTY {
return Ok(None);
}
if state == OCCUPIED && buf[8..8 + ksz] == *key_bytes {
return Ok(Some(Self::value_at(get_u64(&buf[8 + ksz..8 + ksz + 8]))));
}
idx = (idx + 1) & mask;
}
Ok(None)
}
pub fn contains_key(&self, stack: &BStack, key: &K) -> io::Result<bool> {
Ok(self.get(stack, key)?.is_some())
}
pub fn get_or_insert_with<A, F>(&self, allocator: &A, key: K, f: F) -> io::Result<(V, bool)>
where
A: BStackRaiiAllocator,
F: FnOnce() -> io::Result<BStackOwned<V>>,
{
if let Some(v) = self.get(allocator.stack(), &key)? {
return Ok((v, false));
}
let value = f()?;
let vref = value.handle().range().start();
if let Some(old) = self
.insert(allocator, key, value)
.map_err(|e| e.discard_freeing(allocator))?
{
old.bstack_drop(allocator)?;
}
Ok((Self::value_at(vref), true))
}
pub fn get_or_insert<A: BStackRaiiAllocator>(
&self,
allocator: &A,
key: K,
default: BStackOwned<V>,
) -> io::Result<(V, bool)> {
if let Some(v) = self.get(allocator.stack(), &key)? {
default.bstack_drop(allocator)?;
return Ok((v, false));
}
let vref = default.handle().range().start();
if let Some(old) = self
.insert(allocator, key, default)
.map_err(|e| e.discard_freeing(allocator))?
{
old.bstack_drop(allocator)?;
}
Ok((Self::value_at(vref), true))
}
pub fn iter<'a>(&self, stack: &'a BStack) -> io::Result<HashMapIter<'a, K, V>> {
let [table, cap, len] = read_fields::<3>(stack, self.range.start() + TABLE_OFF)?;
Ok(HashMapIter {
stack,
block_off: self.range.start(),
table,
cap,
len,
stride: Self::stride(),
ksz: Self::ksize(),
idx: 0,
scratch: Scratch::new(),
_marker: PhantomData,
})
}
fn grow<A: BStackRaiiAllocator>(&self, allocator: &A) -> io::Result<()> {
grow_table(
allocator,
self.range.start(),
Self::stride(),
Self::ksize(),
OCCUPIED,
MIN_CAP,
)
}
}
impl<K: Pod, V: BStackBlock> BStackCast for BStackHashMap<K, V> {
fn eightcc() -> EightCC {
const BASE: EightCC = EightCC::new([b'M', b'a', b'p', 0x80, 0x81, 0x82, 0x83, 0x84]);
BASE.mix(EightCC::new((size_of::<K>() as u64).to_le_bytes()))
.mix(<V as BStackCast>::eightcc())
}
}
impl<K: Pod, V: BStackBlock> crate::types::traits::BStackEmbeddable for BStackHashMap<K, V> {}
impl<K: Pod, V: BStackBlock> BStackBlock for BStackHashMap<K, V> {
type OnDisk = MapOnDisk;
unsafe fn from_range(range: BStackRange) -> Self {
BStackHashMap {
range,
_marker: PhantomData,
}
}
fn range(&self) -> BStackRange {
self.range
}
fn __bstack_drop_children<A: BStackRaiiAllocator>(
allocator: &A,
range: BStackRange,
) -> io::Result<()> {
let stride = Self::stride();
let ksz = Self::ksize();
let handle = range.start();
let [table, cap] = read_fields::<2>(allocator.stack(), handle + TABLE_OFF)?;
if table == 0 {
return Ok(());
}
let table_size = cap
.checked_mul(stride)
.ok_or_else(|| io_error!("hash map capacity overflow"))?;
if table_size > allocator.len()? {
return Err(io_error!("hash map bucket block larger than the stack"));
}
let mut image = vec![0u8; table_size as usize];
allocator.stack().get_into(table, &mut image)?;
for j in 0..cap as usize {
let lo = j * stride as usize;
if get_u64(&image[lo..lo + 8]) == OCCUPIED {
let vref = get_u64(&image[lo + 8 + ksz..lo + 16 + ksz]);
if vref != 0 {
let owned = unsafe { BStackOwned::from_raw(Self::value_at(vref)) };
owned.bstack_drop(allocator)?;
}
}
}
unsafe { dealloc_range(allocator, BStackRange::new(table, table_size))? };
Ok(())
}
fn __bstack_clone_children_inplace<A: BStackRaiiAllocator>(
&self,
allocator: &A,
plan: &mut ClonePlan,
) -> io::Result<Self::OnDisk> {
let stride = Self::stride();
let ksz = Self::ksize();
let handle = self.range.start();
let [table, cap, len, used] = read_fields::<4>(allocator.stack(), handle + TABLE_OFF)?;
let (new_table, new_cap, new_used) = if cap == 0 {
(0, 0, 0)
} else {
let table_size = cap
.checked_mul(stride)
.ok_or_else(|| io_error!("hash map capacity overflow"))?;
if table_size > allocator.len()? {
return Err(io_error!("hash map bucket block larger than the stack"));
}
let mut image = vec![0u8; table_size as usize];
allocator.stack().get_into(table, &mut image)?;
for j in 0..cap as usize {
let lo = j * stride as usize;
if get_u64(&image[lo..lo + 8]) != OCCUPIED {
continue;
}
let vref = get_u64(&image[lo + 8 + ksz..lo + 16 + ksz]);
let cloned = Self::value_at(vref)
.__bstack_clone_into(allocator, plan)?
.start();
image[lo + 8 + ksz..lo + 16 + ksz].copy_from_slice(&cloned.to_le_bytes());
}
let dst = plan.alloc_raw(allocator, table_size)?;
plan.write(dst.start(), image);
(dst.start(), cap, used)
};
let od = MapOnDisk {
header: BlockHeader {
size: MAP_SIZE,
tag: Self::eightcc(),
},
table: new_table,
cap: new_cap,
len,
used: new_used,
};
Ok(od)
}
}
impl<K: Pod, V: BStackBlock> TryCloneIn for BStackHashMap<K, V> {}
pub struct HashMapIter<'a, K: Pod, V: BStackBlock> {
stack: &'a BStack,
block_off: u64,
table: u64,
cap: u64,
len: u64,
stride: u64,
ksz: usize,
idx: u64,
scratch: Scratch,
_marker: PhantomData<fn() -> (K, V)>,
}
impl<'a, K: Pod, V: BStackBlock> Iterator for HashMapIter<'a, K, V> {
type Item = io::Result<(K, V)>;
fn next(&mut self) -> Option<Self::Item> {
if self.idx < self.cap {
match read_fields::<3>(self.stack, self.block_off + TABLE_OFF) {
Ok([table, cap, len])
if table == self.table && cap == self.cap && len == self.len => {}
Ok(_) => {
self.idx = self.cap;
return Some(Err(io_error!(
"BStackHashMap was mutated during iteration (its table/len \
changed); the iterator is invalidated"
)));
}
Err(e) => {
self.idx = self.cap;
return Some(Err(e));
}
}
}
while self.idx < self.cap {
let i = self.idx;
self.idx += 1;
let buf = self.scratch.buf(self.stride as usize);
let bucket = match checked_off_mul(self.table, i, self.stride) {
Ok(b) => b,
Err(e) => {
self.idx = self.cap;
return Some(Err(e));
}
};
if let Err(e) = self.stack.get_into(bucket, buf) {
self.idx = self.cap;
return Some(Err(e));
}
if get_u64(&buf[0..8]) == OCCUPIED {
let k = bytemuck::pod_read_unaligned::<K>(&buf[8..8 + self.ksz]);
let vref = get_u64(&buf[8 + self.ksz..8 + self.ksz + 8]);
return Some(Ok((k, BStackHashMap::<K, V>::value_at(vref))));
}
}
None
}
}