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::bloom::{BStackCountingBloomFilter, BloomOnDisk};
use super::hash::fnv1a;
use super::util::{
Meta, ProbeStep, Scratch, alloc_image, grow_table, probe_commit, read_fields, w8,
};
use crate::io_core::{ClonePlan, TryCloneIn, dealloc_range};
use crate::primitives::{EightCC, 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 HashSetOnDisk {
pub header: BlockHeader,
pub table: u64,
pub cap: u64,
pub len: u64,
pub used: u64,
pub bloom: 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 BLOOM_OFF: u64 = HEADER_SIZE + 32; const SET_SIZE: u64 = size_of::<HashSetOnDisk>() as u64;
const BLOOM_SIZE: u64 = size_of::<BloomOnDisk>() as u64;
const MIN_CAP: u64 = 4;
const EMPTY: u64 = 0;
const OCCUPIED: u64 = 1;
const TOMBSTONE: u64 = 2;
const DEFAULT_ITEMS: u64 = 1024;
const DEFAULT_FP: f64 = 0.01;
fn place_writes(
handle: u64,
stride: u64,
m: &Meta,
target: u64,
slot_was_empty: bool,
key_bytes: &[u8],
) -> io::Result<Vec<(u64, SmallBuf)>> {
let mut img = Vec::with_capacity(8 + key_bytes.len());
img.extend_from_slice(&OCCUPIED.to_le_bytes());
img.extend_from_slice(key_bytes);
let off = checked_off_mul(m.table, target, stride)?;
let mut w = vec![
(off, SmallBuf::Heap(img.into_boxed_slice())),
w8(handle + LEN_OFF, m.len + 1),
];
if slot_was_empty {
w.push(w8(handle + USED_OFF, m.used + 1));
}
Ok(w)
}
pub struct BStackHashSet<K: Pod> {
range: BStackRange,
_marker: PhantomData<fn() -> K>,
}
impl<K: Pod> BStackHashSet<K> {
fn ksize() -> usize {
size_of::<K>()
}
fn stride() -> u64 {
8 + Self::ksize() as u64
}
fn bloom(&self, stack: &BStack) -> io::Result<BStackCountingBloomFilter<K>> {
let off = read_u64(stack, self.range.start() + BLOOM_OFF)?;
Ok(unsafe {
<BStackCountingBloomFilter<K> as BStackBlock>::from_range(BStackRange::new(
off, BLOOM_SIZE,
))
})
}
pub fn new<A: BStackRaiiAllocator>(allocator: &A) -> io::Result<BStackOwned<Self>> {
Self::with_capacity(allocator, DEFAULT_ITEMS, DEFAULT_FP)
}
pub fn with_capacity<A: BStackRaiiAllocator>(
allocator: &A,
expected_items: u64,
fp_rate: f64,
) -> io::Result<BStackOwned<Self>> {
let bloom =
BStackCountingBloomFilter::<K>::with_capacity(allocator, expected_items, fp_rate)?;
let bloom_off = bloom.into_inner().range().start();
let od = HashSetOnDisk {
header: BlockHeader {
size: SET_SIZE,
tag: Self::eightcc(),
},
table: 0,
cap: 0,
len: 0,
used: 0,
bloom: bloom_off,
};
match alloc_image(allocator, bytemuck::bytes_of(&od)) {
Ok(range) => Ok(unsafe { BStackOwned::from_raw(Self::from_range(range)) }),
Err(e) => {
let bloom = unsafe {
<BStackCountingBloomFilter<K> as BStackBlock>::from_range(BStackRange::new(
bloom_off, BLOOM_SIZE,
))
};
let _ = unsafe { BStackOwned::from_raw(bloom) }.bstack_drop(allocator);
Err(e)
}
}
}
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) -> io::Result<bool> {
let key_bytes = bytemuck::bytes_of(&key).to_vec();
let hash = fnv1a(&key_bytes);
let bloom = self.bloom(allocator.stack())?;
bloom.insert(allocator, &key)?;
let was_new = self.table_insert(allocator, &key_bytes, hash)?;
if !was_new {
bloom.remove(allocator, &key)?;
}
Ok(was_new)
}
pub fn remove<A: BStackRaiiAllocator>(&self, allocator: &A, key: &K) -> io::Result<bool> {
let key_bytes = bytemuck::bytes_of(key).to_vec();
let hash = fnv1a(&key_bytes);
let was_present = self.table_remove(allocator, &key_bytes, hash)?;
if was_present {
let _ = self
.bloom(allocator.stack())
.and_then(|b| b.remove(allocator, key));
}
Ok(was_present)
}
pub fn contains(&self, stack: &BStack, key: &K) -> io::Result<bool> {
if !self.bloom(stack)?.contains(stack, key)? {
return Ok(false);
}
let key_bytes = bytemuck::bytes_of(key);
self.table_contains(stack, key_bytes, fnv1a(key_bytes))
}
pub fn iter<'a>(&self, stack: &'a BStack) -> io::Result<HashSetIter<'a, K>> {
let [table, cap, len] = read_fields::<3>(stack, self.range.start() + TABLE_OFF)?;
Ok(HashSetIter {
stack,
block_off: self.range.start(),
table,
cap,
len,
stride: Self::stride(),
ksz: Self::ksize(),
idx: 0,
scratch: Scratch::new(),
_marker: PhantomData,
})
}
fn table_insert<A: BStackRaiiAllocator>(
&self,
allocator: &A,
key_bytes: &[u8],
hash: u64,
) -> io::Result<bool> {
let handle = self.range.start();
let stride = Self::stride();
let ksz = Self::ksize();
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);
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(place_writes(
handle,
stride,
m,
target,
slot_was_empty,
key_bytes,
))
} else if state == OCCUPIED && buf[8..8 + ksz] == *key_bytes {
ProbeStep::Stop(Ok(Vec::new())) } 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);
place_writes(handle, stride, m, t, false, key_bytes)
} else {
need_grow.set(true);
Ok(Vec::new())
}
},
)?;
if need_grow.get() {
self.grow(allocator)?;
continue;
}
return Ok(is_new.get());
}
}
fn table_remove<A: BStackRaiiAllocator>(
&self,
allocator: &A,
key_bytes: &[u8],
hash: u64,
) -> io::Result<bool> {
let handle = self.range.start();
let stride = Self::stride();
let ksz = Self::ksize();
let found = Cell::new(false);
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);
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()),
)?;
Ok(found.get())
}
fn table_contains(&self, stack: &BStack, key_bytes: &[u8], hash: u64) -> io::Result<bool> {
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(false);
}
let mask = cap - 1;
let mut idx = hash & 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(false);
}
if state == OCCUPIED && buf[8..8 + ksz] == *key_bytes {
return Ok(true);
}
idx = (idx + 1) & mask;
}
Ok(false)
}
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> BStackCast for BStackHashSet<K> {
fn eightcc() -> EightCC {
const BASE: EightCC = EightCC::new([b'H', b'S', b't', 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 BStackHashSet<K> {}
impl<K: Pod> BStackBlock for BStackHashSet<K> {
type OnDisk = HashSetOnDisk;
unsafe fn from_range(range: BStackRange) -> Self {
BStackHashSet {
range,
_marker: PhantomData,
}
}
fn range(&self) -> BStackRange {
self.range
}
fn __bstack_drop_children<A: BStackRaiiAllocator>(
allocator: &A,
range: BStackRange,
) -> io::Result<()> {
let handle = range.start();
let [table, cap, _len, _used, bloom_off] =
read_fields::<5>(allocator.stack(), handle + TABLE_OFF)?;
if table != 0 {
let table_size = cap
.checked_mul(Self::stride())
.ok_or_else(|| io_error!("hash set capacity overflow"))?;
if table_size > allocator.len()? {
return Err(io_error!("hash set bucket block larger than the stack"));
}
unsafe { dealloc_range(allocator, BStackRange::new(table, table_size))? };
}
if bloom_off != 0 {
let bloom = unsafe {
<BStackCountingBloomFilter<K> as BStackBlock>::from_range(BStackRange::new(
bloom_off, BLOOM_SIZE,
))
};
unsafe { BStackOwned::from_raw(bloom) }.bstack_drop(allocator)?;
}
Ok(())
}
fn __bstack_clone_children_inplace<A: BStackRaiiAllocator>(
&self,
allocator: &A,
plan: &mut ClonePlan,
) -> io::Result<Self::OnDisk> {
let handle = self.range.start();
let stride = Self::stride();
let [table, cap, len, used, bloom_off] =
read_fields::<5>(allocator.stack(), handle + TABLE_OFF)?;
let new_table = if cap != 0 {
let table_size = cap
.checked_mul(stride)
.ok_or_else(|| io_error!("hash set capacity overflow"))?;
if table_size > allocator.len()? {
return Err(io_error!("hash set bucket block larger than the stack"));
}
let mut image = vec![0u8; table_size as usize];
allocator.stack().get_into(table, &mut image)?;
let dst = plan.alloc_raw(allocator, table_size)?;
plan.write(dst.start(), image);
dst.start()
} else {
0
};
let bloom = unsafe {
<BStackCountingBloomFilter<K> as BStackBlock>::from_range(BStackRange::new(
bloom_off, BLOOM_SIZE,
))
};
let new_bloom = bloom.__bstack_clone_into(allocator, plan)?.start();
let od = HashSetOnDisk {
header: BlockHeader {
size: SET_SIZE,
tag: Self::eightcc(),
},
table: new_table,
cap,
len,
used,
bloom: new_bloom,
};
Ok(od)
}
}
impl<K: Pod> TryCloneIn for BStackHashSet<K> {}
pub struct HashSetIter<'a, K: Pod> {
stack: &'a BStack,
block_off: u64,
table: u64,
cap: u64,
len: u64,
stride: u64,
ksz: usize,
idx: u64,
scratch: Scratch,
_marker: PhantomData<fn() -> K>,
}
impl<'a, K: Pod> Iterator for HashSetIter<'a, K> {
type Item = io::Result<K>;
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!(
"BStackHashSet 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 {
return Some(Ok(bytemuck::pod_read_unaligned::<K>(&buf[8..8 + self.ksz])));
}
}
None
}
}