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::util::{alloc_image, read_fields, w8};
use crate::handback::ReplaceError;
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 HeapOnDisk {
pub header: BlockHeader,
pub data: u64,
pub cap: u64,
pub len: u64,
}
const DATA_OFF: u64 = HEADER_SIZE; const CAP_OFF: u64 = HEADER_SIZE + 8; const LEN_OFF: u64 = HEADER_SIZE + 16; const HEAP_SIZE: u64 = size_of::<HeapOnDisk>() as u64;
const MIN_CAP: u64 = 4;
pub struct BStackBinaryHeap<K: Pod + Ord, V: BStackBlock> {
range: BStackRange,
_marker: PhantomData<fn() -> (K, V)>,
}
impl<K: Pod + Ord, V: BStackBlock> BStackBinaryHeap<K, V> {
fn ksize() -> usize {
size_of::<K>()
}
fn stride() -> u64 {
Self::ksize() as u64 + 8
}
fn slot_off(data: u64, i: u64) -> io::Result<u64> {
checked_off_mul(data, i, Self::stride())
}
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())) }
}
fn read_key(slot: &[u8]) -> K {
bytemuck::pod_read_unaligned::<K>(&slot[..Self::ksize()])
}
fn slot_val(slot: &[u8]) -> u64 {
get_u64(&slot[Self::ksize()..Self::ksize() + 8])
}
fn read_meta(stack: &BStack, handle: u64) -> io::Result<(u64, u64, u64)> {
let [data, cap, len] = read_fields::<3>(stack, handle + DATA_OFF)?;
Ok((data, cap, len))
}
fn read_slot(stack: &BStack, data: u64, i: u64) -> io::Result<Vec<u8>> {
let mut buf = vec![0u8; Self::stride() as usize];
stack.get_into(Self::slot_off(data, i)?, &mut buf)?;
Ok(buf)
}
pub fn new<A: BStackRaiiAllocator>(allocator: &A) -> io::Result<BStackOwned<Self>> {
Self::with_image(allocator, 0, 0)
}
pub fn with_capacity<A: BStackRaiiAllocator>(
allocator: &A,
cap: u64,
) -> io::Result<BStackOwned<Self>> {
if cap == 0 {
return Self::new(allocator);
}
let size = cap
.checked_mul(Self::stride())
.ok_or_else(|| io_error!("heap capacity overflow"))?;
let data = allocator.alloc(size)?.as_range().start();
match Self::with_image(allocator, data, cap) {
Ok(o) => Ok(o),
Err(e) => {
let _ = unsafe { dealloc_range(allocator, BStackRange::new(data, size)) };
Err(e)
}
}
}
fn with_image<A: BStackRaiiAllocator>(
allocator: &A,
data: u64,
cap: u64,
) -> io::Result<BStackOwned<Self>> {
let od = HeapOnDisk {
header: BlockHeader {
size: HEAP_SIZE,
tag: Self::eightcc(),
},
data,
cap,
len: 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 capacity(&self, stack: &BStack) -> io::Result<u64> {
read_u64(stack, self.range.start() + CAP_OFF)
}
pub fn peek(&self, stack: &BStack) -> io::Result<Option<(K, V)>> {
let (data, _cap, len) = Self::read_meta(stack, self.range.start())?;
if len == 0 {
return Ok(None);
}
let slot = Self::read_slot(stack, data, 0)?;
Ok(Some((
Self::read_key(&slot),
Self::value_at(Self::slot_val(&slot)),
)))
}
pub fn push<A: BStackRaiiAllocator>(
&self,
allocator: &A,
key: K,
value: BStackOwned<V>,
) -> Result<(), ReplaceError<BStackOwned<V>>> {
let handle = self.range.start();
let stride = Self::stride();
let value = value.auto(allocator);
let val_ref = value.range().start();
let key_bytes = bytemuck::bytes_of(&key).to_vec();
let outcome: io::Result<()> = (|| loop {
let (data, cap, len) = Self::read_meta(allocator.stack(), handle)?;
if data == 0 || len >= cap {
self.grow(allocator)?;
continue;
}
let mut new_slot = Vec::with_capacity(stride as usize);
new_slot.extend_from_slice(&key_bytes);
new_slot.extend_from_slice(&val_ref.to_le_bytes());
let mut hole = len;
let mut writes: Vec<(u64, SmallBuf)> = Vec::new();
while hole > 0 {
let parent = (hole - 1) / 2;
let parent_slot = Self::read_slot(allocator.stack(), data, parent)?;
if Self::read_key(&parent_slot) > key {
writes.push((
Self::slot_off(data, hole)?,
SmallBuf::Heap(parent_slot.into_boxed_slice()),
));
hole = parent;
} else {
break;
}
}
writes.push((
Self::slot_off(data, hole)?,
SmallBuf::Heap(new_slot.into_boxed_slice()),
));
writes.push(w8(handle + LEN_OFF, len + 1));
allocator.stack().set_batched(writes)?;
return Ok(());
})();
value.finish_handback(outcome)
}
pub fn pop<A: BStackRaiiAllocator>(
&self,
allocator: &A,
) -> io::Result<Option<(K, BStackOwned<V>)>> {
let handle = self.range.start();
let (data, _cap, len) = Self::read_meta(allocator.stack(), handle)?;
if len == 0 {
return Ok(None);
}
let min_slot = Self::read_slot(allocator.stack(), data, 0)?;
let min_key = Self::read_key(&min_slot);
let min_val = Self::slot_val(&min_slot);
if len == 1 {
allocator
.stack()
.set(handle + LEN_OFF, 0u64.to_le_bytes())?;
return Ok(Some((min_key, unsafe {
BStackOwned::from_raw(Self::value_at(min_val))
})));
}
let last_slot = Self::read_slot(allocator.stack(), data, len - 1)?;
let last_key = Self::read_key(&last_slot);
let newlen = len - 1;
let mut hole = 0u64;
let mut writes: Vec<(u64, SmallBuf)> = Vec::new();
loop {
let mut child = 2 * hole + 1;
if child >= newlen {
break;
}
let mut smaller = Self::read_slot(allocator.stack(), data, child)?;
let mut smaller_key = Self::read_key(&smaller);
if child + 1 < newlen {
let right = Self::read_slot(allocator.stack(), data, child + 1)?;
let right_key = Self::read_key(&right);
if right_key < smaller_key {
smaller = right;
smaller_key = right_key;
child += 1;
}
}
if smaller_key < last_key {
writes.push((
Self::slot_off(data, hole)?,
SmallBuf::Heap(smaller.into_boxed_slice()),
));
hole = child;
} else {
break;
}
}
writes.push((
Self::slot_off(data, hole)?,
SmallBuf::Heap(last_slot.into_boxed_slice()),
));
writes.push(w8(handle + LEN_OFF, newlen));
allocator.stack().set_batched(writes)?;
Ok(Some((min_key, unsafe {
BStackOwned::from_raw(Self::value_at(min_val))
})))
}
fn grow<A: BStackRaiiAllocator>(&self, allocator: &A) -> io::Result<()> {
let handle = self.range.start();
let stride = Self::stride();
let (data, cap, len) = Self::read_meta(allocator.stack(), handle)?;
let newcap = if cap == 0 {
MIN_CAP
} else {
cap.saturating_mul(2)
};
if newcap <= cap {
return Err(io_error!("corrupt heap capacity"));
}
let new_size = newcap
.checked_mul(stride)
.ok_or_else(|| io_error!("heap capacity overflow"))?;
let newdata = allocator.alloc(new_size)?.as_range().start();
if len > 0 {
let len_size = len
.checked_mul(stride)
.ok_or_else(|| io_error!("heap length overflow"))?;
let mut buf = vec![0u8; len_size as usize];
allocator.stack().get_into(data, &mut buf)?;
allocator.stack().set(newdata, buf)?;
}
let mut meta = [0u8; 16];
meta[0..8].copy_from_slice(&newdata.to_le_bytes());
meta[8..16].copy_from_slice(&newcap.to_le_bytes());
allocator.stack().set(handle + DATA_OFF, meta)?;
if data != 0 {
let _ = unsafe {
dealloc_range(
allocator,
BStackRange::new(data, cap.saturating_mul(stride)),
)
};
}
Ok(())
}
}
impl<K: Pod + Ord, V: BStackBlock> BStackCast for BStackBinaryHeap<K, V> {
fn eightcc() -> EightCC {
const BASE: EightCC = EightCC::new([b'H', b'e', 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 + Ord, V: BStackBlock> crate::types::traits::BStackEmbeddable
for BStackBinaryHeap<K, V>
{
}
impl<K: Pod + Ord, V: BStackBlock> BStackBlock for BStackBinaryHeap<K, V> {
type OnDisk = HeapOnDisk;
unsafe fn from_range(range: BStackRange) -> Self {
BStackBinaryHeap {
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 (data, cap, len) = Self::read_meta(allocator.stack(), handle)?;
for i in 0..len {
let slot = Self::read_slot(allocator.stack(), data, i)?;
let v = Self::slot_val(&slot);
if v != 0 {
let owned = unsafe { BStackOwned::from_raw(Self::value_at(v)) };
owned.bstack_drop(allocator)?;
}
}
if data != 0 {
let size = cap
.checked_mul(Self::stride())
.ok_or_else(|| io_error!("heap capacity overflow"))?;
unsafe { dealloc_range(allocator, BStackRange::new(data, size))? };
}
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 ksize = Self::ksize();
let (data, _cap, len) = Self::read_meta(allocator.stack(), handle)?;
let (new_data, new_cap) = if len > 0 {
let arr_size = len
.checked_mul(stride)
.ok_or_else(|| io_error!("heap length overflow"))?;
if arr_size > allocator.len()? {
return Err(io_error!("heap element array larger than the stack"));
}
let mut image = vec![0u8; arr_size as usize];
allocator.stack().get_into(data, &mut image)?;
for i in 0..len as usize {
let vo = i * stride as usize + ksize;
let vref = get_u64(&image[vo..vo + 8]);
let cloned = Self::value_at(vref)
.__bstack_clone_into(allocator, plan)?
.start();
image[vo..vo + 8].copy_from_slice(&cloned.to_le_bytes());
}
let dst = plan.alloc_raw(allocator, arr_size)?;
plan.write(dst.start(), image);
(dst.start(), len)
} else {
(0, 0)
};
let od = HeapOnDisk {
header: BlockHeader {
size: HEAP_SIZE,
tag: Self::eightcc(),
},
data: new_data,
cap: new_cap,
len,
};
Ok(od)
}
}
impl<K: Pod + Ord, V: BStackBlock> TryCloneIn for BStackBinaryHeap<K, V> {}