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::util::{WriteBuf, alloc_image, atomic_update, read_fields, w8};
use crate::handback::ReplaceError;
use crate::io_core::{ClonePlan, TryCloneIn, dealloc_range};
use crate::primitives::{EightCC, checked_off};
use crate::types::compiled::{BStackOwned, BlockHeader, HEADER_SIZE};
use crate::types::traits::{BStackBlock, BStackCast, BStackDrop};
use crate::util::{SmallBuf, io_error, read_u64};
#[repr(C)]
#[derive(Clone, Copy, Pod, Zeroable)]
pub struct ListOnDisk {
pub header: BlockHeader,
pub head: u64,
pub tail: u64,
pub len: u64,
}
#[repr(C)]
#[derive(Clone, Copy, Pod, Zeroable)]
pub struct NodeOnDisk {
pub header: BlockHeader,
pub prev: u64,
pub next: u64,
pub value: u64,
}
const HEAD_OFF: u64 = HEADER_SIZE; const TAIL_OFF: u64 = HEADER_SIZE + 8; const LEN_OFF: u64 = HEADER_SIZE + 16; const NPREV_OFF: u64 = HEADER_SIZE; const NNEXT_OFF: u64 = HEADER_SIZE + 8; const NVAL_OFF: u64 = HEADER_SIZE + 16;
const LIST_SIZE: u64 = size_of::<ListOnDisk>() as u64;
const NODE_SIZE: u64 = size_of::<NodeOnDisk>() as u64;
const _: () = assert!(
NODE_SIZE == 40,
"SmallBuf::Buf40 assumes a 40-byte NodeOnDisk"
);
pub struct BStackLinkedList<T: BStackBlock> {
range: BStackRange,
_marker: PhantomData<fn() -> T>,
}
impl<T: BStackBlock> BStackLinkedList<T> {
fn value_size() -> u64 {
size_of::<<T as BStackBlock>::OnDisk>() as u64
}
fn node_tag() -> EightCC {
const BASE: EightCC = EightCC::new([b'L', b'N', b'd', 0x80, 0x81, 0x82, 0x83, 0x84]);
BASE.mix(<T as BStackCast>::eightcc())
}
fn value_at(off: u64) -> T {
unsafe { <T as BStackBlock>::from_range(BStackRange::new(off, Self::value_size())) }
}
fn node_image(prev: u64, next: u64, value: u64) -> NodeOnDisk {
NodeOnDisk {
header: BlockHeader {
size: NODE_SIZE,
tag: Self::node_tag(),
},
prev,
next,
value,
}
}
pub fn new<A: BStackRaiiAllocator>(allocator: &A) -> io::Result<BStackOwned<Self>> {
let od = ListOnDisk {
header: BlockHeader {
size: LIST_SIZE,
tag: Self::eightcc(),
},
head: 0,
tail: 0,
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 push_back<A: BStackRaiiAllocator>(
&self,
allocator: &A,
value: BStackOwned<T>,
) -> Result<(), ReplaceError<BStackOwned<T>>> {
let list = self.range.start();
let value = value.auto(allocator);
let val_off = value.range().start();
let outcome: io::Result<()> = (|| {
let node = allocator.alloc(NODE_SIZE)?.as_range().start();
let mut w: WriteBuf<4> = WriteBuf::new();
let res = atomic_update(
allocator,
&[list + TAIL_OFF, list + LEN_OFF],
|_v1| Ok(Vec::new()),
|v1, _v2| {
let (old_tail, len) = (v1[0], v1[1]);
let image: [u8; 40] =
bytemuck::bytes_of(&Self::node_image(old_tail, 0, val_off))
.try_into()
.unwrap();
w.push((node, SmallBuf::Buf40(image)));
let link = if old_tail != 0 {
checked_off(old_tail, NNEXT_OFF)?
} else {
list + HEAD_OFF
};
w.push(w8(link, node));
w.push(w8(list + TAIL_OFF, node));
w.push(w8(list + LEN_OFF, len + 1));
Ok(w.as_slice())
},
);
if res.is_err() {
let _ = unsafe { dealloc_range(allocator, BStackRange::new(node, NODE_SIZE)) };
}
res
})();
value.finish_handback(outcome)
}
pub fn push_front<A: BStackRaiiAllocator>(
&self,
allocator: &A,
value: BStackOwned<T>,
) -> Result<(), ReplaceError<BStackOwned<T>>> {
let list = self.range.start();
let value = value.auto(allocator);
let val_off = value.range().start();
let outcome: io::Result<()> = (|| {
let node = allocator.alloc(NODE_SIZE)?.as_range().start();
let mut w: WriteBuf<4> = WriteBuf::new();
let res = atomic_update(
allocator,
&[list + HEAD_OFF, list + LEN_OFF],
|_v1| Ok(Vec::new()),
|v1, _v2| {
let (old_head, len) = (v1[0], v1[1]);
let image: [u8; 40] =
bytemuck::bytes_of(&Self::node_image(0, old_head, val_off))
.try_into()
.unwrap();
w.push((node, SmallBuf::Buf40(image)));
let link = if old_head != 0 {
checked_off(old_head, NPREV_OFF)?
} else {
list + TAIL_OFF
};
w.push(w8(link, node));
w.push(w8(list + HEAD_OFF, node));
w.push(w8(list + LEN_OFF, len + 1));
Ok(w.as_slice())
},
);
if res.is_err() {
let _ = unsafe { dealloc_range(allocator, BStackRange::new(node, NODE_SIZE)) };
}
res
})();
value.finish_handback(outcome)
}
pub fn pop_back<A: BStackRaiiAllocator>(
&self,
allocator: &A,
) -> io::Result<Option<BStackOwned<T>>> {
let list = self.range.start();
let node = Cell::new(0u64);
let val = Cell::new(0u64);
let mut w: WriteBuf<3> = WriteBuf::new();
atomic_update(
allocator,
&[list + TAIL_OFF, list + LEN_OFF],
|v1| {
let tail = v1[0];
if tail == 0 {
Ok(Vec::new())
} else {
Ok(vec![
checked_off(tail, NPREV_OFF)?,
checked_off(tail, NVAL_OFF)?,
])
}
},
|v1, v2| {
let (tail, len) = (v1[0], v1[1]);
if tail != 0 {
let (prev, value) = (v2[0], v2[1]);
node.set(tail);
val.set(value);
if prev != 0 {
w.push(w8(checked_off(prev, NNEXT_OFF)?, 0u64));
w.push(w8(list + TAIL_OFF, prev));
} else {
w.push(w8(list + HEAD_OFF, 0u64));
w.push(w8(list + TAIL_OFF, 0u64));
}
w.push(w8(list + LEN_OFF, len - 1));
}
Ok(w.as_slice())
},
)?;
if node.get() == 0 {
return Ok(None);
}
unsafe { dealloc_range(allocator, BStackRange::new(node.get(), NODE_SIZE))? };
Ok(Some(unsafe {
BStackOwned::from_raw(Self::value_at(val.get()))
}))
}
pub fn pop_front<A: BStackRaiiAllocator>(
&self,
allocator: &A,
) -> io::Result<Option<BStackOwned<T>>> {
let list = self.range.start();
let node = Cell::new(0u64);
let val = Cell::new(0u64);
let mut w: WriteBuf<3> = WriteBuf::new();
atomic_update(
allocator,
&[list + HEAD_OFF, list + LEN_OFF],
|v1| {
let head = v1[0];
if head == 0 {
Ok(Vec::new())
} else {
Ok(vec![
checked_off(head, NNEXT_OFF)?,
checked_off(head, NVAL_OFF)?,
])
}
},
|v1, v2| {
let (head, len) = (v1[0], v1[1]);
if head != 0 {
let (next, value) = (v2[0], v2[1]);
node.set(head);
val.set(value);
if next != 0 {
w.push(w8(checked_off(next, NPREV_OFF)?, 0u64));
w.push(w8(list + HEAD_OFF, next));
} else {
w.push(w8(list + HEAD_OFF, 0u64));
w.push(w8(list + TAIL_OFF, 0u64));
}
w.push(w8(list + LEN_OFF, len - 1));
}
Ok(w.as_slice())
},
)?;
if node.get() == 0 {
return Ok(None);
}
unsafe { dealloc_range(allocator, BStackRange::new(node.get(), NODE_SIZE))? };
Ok(Some(unsafe {
BStackOwned::from_raw(Self::value_at(val.get()))
}))
}
pub fn front(&self, stack: &BStack) -> io::Result<Option<T>> {
let head = read_u64(stack, self.range.start() + HEAD_OFF)?;
if head == 0 {
return Ok(None);
}
Ok(Some(Self::value_at(read_u64(
stack,
checked_off(head, NVAL_OFF)?,
)?)))
}
pub fn back(&self, stack: &BStack) -> io::Result<Option<T>> {
let tail = read_u64(stack, self.range.start() + TAIL_OFF)?;
if tail == 0 {
return Ok(None);
}
Ok(Some(Self::value_at(read_u64(
stack,
checked_off(tail, NVAL_OFF)?,
)?)))
}
pub fn to_vec(&self, stack: &BStack) -> io::Result<Vec<T>> {
let mut out = Vec::new();
let mut cur = read_u64(stack, self.range.start() + HEAD_OFF)?;
let mut remaining = self.len(stack)?;
while cur != 0 {
if remaining == 0 {
return Err(io_error!(
"linked list chain longer than its stored len (a next-pointer cycle?)"
));
}
remaining -= 1;
let [next, value] = read_fields::<2>(stack, checked_off(cur, NNEXT_OFF)?)?;
out.push(Self::value_at(value));
cur = next;
}
Ok(out)
}
pub fn iter<'a>(&self, stack: &'a BStack) -> io::Result<ListIter<'a, T>> {
let head = read_u64(stack, self.range.start() + HEAD_OFF)?;
let remaining = self.len(stack)?;
Ok(ListIter {
stack,
block_off: self.range.start(),
len0: remaining,
remaining,
cur: head,
_marker: PhantomData,
})
}
}
impl<T: BStackBlock> BStackCast for BStackLinkedList<T> {
fn eightcc() -> EightCC {
const BASE: EightCC = EightCC::new([b'L', b'i', b's', b't', 0x80, 0x81, 0x82, 0x83]);
BASE.mix(<T as BStackCast>::eightcc())
}
}
impl<T: BStackBlock> crate::types::traits::BStackEmbeddable for BStackLinkedList<T> {}
impl<T: BStackBlock> BStackBlock for BStackLinkedList<T> {
type OnDisk = ListOnDisk;
unsafe fn from_range(range: BStackRange) -> Self {
BStackLinkedList {
range,
_marker: PhantomData,
}
}
fn range(&self) -> BStackRange {
self.range
}
fn __bstack_drop_children<A: BStackRaiiAllocator>(
allocator: &A,
range: BStackRange,
) -> io::Result<()> {
let mut cur = read_u64(allocator.stack(), range.start() + HEAD_OFF)?;
let mut remaining = read_u64(allocator.stack(), range.start() + LEN_OFF)?;
while cur != 0 {
if remaining == 0 {
return Err(io_error!(
"linked list chain longer than its stored len (a next-pointer cycle?)"
));
}
remaining -= 1;
let next = read_u64(allocator.stack(), checked_off(cur, NNEXT_OFF)?)?;
let val = read_u64(allocator.stack(), checked_off(cur, NVAL_OFF)?)?;
if val != 0 {
let owned = unsafe { BStackOwned::from_raw(Self::value_at(val)) };
owned.bstack_drop(allocator)?;
}
unsafe { dealloc_range(allocator, BStackRange::new(cur, NODE_SIZE))? };
cur = next;
}
Ok(())
}
fn __bstack_clone_children_inplace<A: BStackRaiiAllocator>(
&self,
allocator: &A,
plan: &mut ClonePlan,
) -> io::Result<Self::OnDisk> {
let src = self.range.start();
let mut vals = Vec::new();
let mut cur = read_u64(allocator.stack(), src + HEAD_OFF)?;
let mut remaining = read_u64(allocator.stack(), src + LEN_OFF)?;
while cur != 0 {
if remaining == 0 {
return Err(io_error!(
"linked list chain longer than its stored len (a next-pointer cycle?)"
));
}
remaining -= 1;
vals.push(read_u64(allocator.stack(), checked_off(cur, NVAL_OFF)?)?);
cur = read_u64(allocator.stack(), checked_off(cur, NNEXT_OFF)?)?;
}
let n = vals.len();
let mut val_dsts = Vec::with_capacity(n);
for &v in &vals {
let dst = if v != 0 {
Self::value_at(v)
.__bstack_clone_into(allocator, plan)?
.start()
} else {
0
};
val_dsts.push(dst);
}
let mut node_dsts = Vec::with_capacity(n);
for _ in 0..n {
node_dsts.push(plan.alloc_raw(allocator, NODE_SIZE)?.start());
}
for i in 0..n {
let prev = if i > 0 { node_dsts[i - 1] } else { 0 };
let next = if i + 1 < n { node_dsts[i + 1] } else { 0 };
let od = Self::node_image(prev, next, val_dsts[i]);
plan.write(node_dsts[i], bytemuck::bytes_of(&od).to_vec());
}
let od = ListOnDisk {
header: BlockHeader {
size: LIST_SIZE,
tag: Self::eightcc(),
},
head: node_dsts.first().copied().unwrap_or(0),
tail: node_dsts.last().copied().unwrap_or(0),
len: n as u64,
};
Ok(od)
}
}
impl<T: BStackBlock> TryCloneIn for BStackLinkedList<T> {}
pub struct ListIter<'a, T: BStackBlock> {
stack: &'a BStack,
block_off: u64,
len0: u64,
cur: u64,
remaining: u64,
_marker: PhantomData<fn() -> T>,
}
impl<'a, T: BStackBlock> Iterator for ListIter<'a, T> {
type Item = io::Result<T>;
fn next(&mut self) -> Option<Self::Item> {
if self.cur == 0 {
return None;
}
match read_u64(self.stack, self.block_off + LEN_OFF) {
Ok(len) if len == self.len0 => {}
Ok(_) => {
self.cur = 0;
return Some(Err(io_error!(
"BStackLinkedList was mutated during iteration (its length changed); \
the iterator is invalidated"
)));
}
Err(e) => {
self.cur = 0;
return Some(Err(e));
}
}
if self.remaining == 0 {
self.cur = 0;
return Some(Err(io_error!(
"linked list chain longer than its stored len (a next-pointer cycle?)"
)));
}
self.remaining -= 1;
let off = match checked_off(self.cur, NNEXT_OFF) {
Ok(off) => off,
Err(e) => {
self.cur = 0;
return Some(Err(e));
}
};
match read_fields::<2>(self.stack, off) {
Ok([next, value]) => {
self.cur = next;
Some(Ok(BStackLinkedList::<T>::value_at(value)))
}
Err(e) => {
self.cur = 0;
Some(Err(e))
}
}
}
}