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_mul};
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 DequeOnDisk {
pub header: BlockHeader,
pub data: u64,
pub cap: u64,
pub head: u64,
pub len: u64,
}
const DATA_OFF: u64 = HEADER_SIZE; const CAP_OFF: u64 = HEADER_SIZE + 8; const HEAD_OFF: u64 = HEADER_SIZE + 16; const LEN_OFF: u64 = HEADER_SIZE + 24;
const DEQUE_SIZE: u64 = size_of::<DequeOnDisk>() as u64;
const MIN_CAP: u64 = 4;
pub struct BStackDeque<T: BStackBlock> {
range: BStackRange,
_marker: PhantomData<fn() -> T>,
}
impl<T: BStackBlock> BStackDeque<T> {
fn value_size() -> u64 {
size_of::<<T as BStackBlock>::OnDisk>() as u64
}
fn value_at(off: u64) -> T {
unsafe { <T as BStackBlock>::from_range(BStackRange::new(off, Self::value_size())) }
}
fn read_meta(stack: &BStack, handle: u64) -> io::Result<(u64, u64, u64, u64)> {
let [data, cap, head, len] = read_fields::<4>(stack, handle + DATA_OFF)?;
Ok((head, len, cap, data))
}
fn ring_index(head: u64, x: u64, cap: u64) -> io::Result<u64> {
if cap == 0 {
return Err(io_error!(
"corrupt deque: zero capacity with a nonzero length"
));
}
Ok(head.wrapping_add(x) % cap)
}
fn slot_addr(data: u64, idx: u64) -> io::Result<u64> {
checked_off_mul(data, idx, 8)
}
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.saturating_mul(8);
let ring = allocator.alloc(size)?.as_range().start();
match Self::with_image(allocator, ring, cap) {
Ok(owned) => Ok(owned),
Err(e) => {
let _ = unsafe { dealloc_range(allocator, BStackRange::new(ring, size)) };
Err(e)
}
}
}
fn with_image<A: BStackRaiiAllocator>(
allocator: &A,
data: u64,
cap: u64,
) -> io::Result<BStackOwned<Self>> {
let od = DequeOnDisk {
header: BlockHeader {
size: DEQUE_SIZE,
tag: Self::eightcc(),
},
data,
cap,
head: 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 capacity(&self, stack: &BStack) -> io::Result<u64> {
read_u64(stack, self.range.start() + CAP_OFF)
}
pub fn push_back<A: BStackRaiiAllocator>(
&self,
allocator: &A,
value: BStackOwned<T>,
) -> Result<(), ReplaceError<BStackOwned<T>>> {
let handle = self.range.start();
let value = value.auto(allocator);
let val_off = value.range().start();
let outcome: io::Result<()> = (|| {
loop {
let full = Cell::new(false);
let mut w: WriteBuf<2> = WriteBuf::new();
atomic_update(
allocator,
&[
handle + HEAD_OFF,
handle + LEN_OFF,
handle + CAP_OFF,
handle + DATA_OFF,
],
|_v1| Ok(Vec::new()),
|v1, _v2| {
let (head, len, cap, data) = (v1[0], v1[1], v1[2], v1[3]);
if len < cap {
let idx = head.wrapping_add(len) % cap;
let slot = Self::slot_addr(data, idx)?;
w.push(w8(slot, val_off));
w.push(w8(handle + LEN_OFF, len + 1));
} else {
full.set(true);
}
Ok(w.as_slice())
},
)?;
if !full.get() {
return Ok(());
}
self.grow(allocator)?;
}
})();
value.finish_handback(outcome)
}
pub fn push_front<A: BStackRaiiAllocator>(
&self,
allocator: &A,
value: BStackOwned<T>,
) -> Result<(), ReplaceError<BStackOwned<T>>> {
let handle = self.range.start();
let value = value.auto(allocator);
let val_off = value.range().start();
let outcome: io::Result<()> = (|| {
loop {
let full = Cell::new(false);
let mut w: WriteBuf<3> = WriteBuf::new();
atomic_update(
allocator,
&[
handle + HEAD_OFF,
handle + LEN_OFF,
handle + CAP_OFF,
handle + DATA_OFF,
],
|_v1| Ok(Vec::new()),
|v1, _v2| {
let (head, len, cap, data) = (v1[0], v1[1], v1[2], v1[3]);
if len < cap {
let idx = head.wrapping_add(cap - 1) % cap;
let slot = Self::slot_addr(data, idx)?;
w.push(w8(slot, val_off));
w.push(w8(handle + HEAD_OFF, idx));
w.push(w8(handle + LEN_OFF, len + 1));
} else {
full.set(true);
}
Ok(w.as_slice())
},
)?;
if !full.get() {
return Ok(());
}
self.grow(allocator)?;
}
})();
value.finish_handback(outcome)
}
pub fn pop_back<A: BStackRaiiAllocator>(
&self,
allocator: &A,
) -> io::Result<Option<BStackOwned<T>>> {
let handle = self.range.start();
let got = Cell::new(false);
let val = Cell::new(0u64);
let mut w: WriteBuf<1> = WriteBuf::new();
atomic_update(
allocator,
&[
handle + HEAD_OFF,
handle + LEN_OFF,
handle + CAP_OFF,
handle + DATA_OFF,
],
|v1| {
let (head, len, cap, data) = (v1[0], v1[1], v1[2], v1[3]);
if len == 0 {
Ok(Vec::new())
} else {
Ok(vec![Self::slot_addr(
data,
Self::ring_index(head, len - 1, cap)?,
)?])
}
},
|v1, v2| {
let len = v1[1];
if len != 0 {
got.set(true);
val.set(v2[0]);
w.push(w8(handle + LEN_OFF, len - 1));
}
Ok(w.as_slice())
},
)?;
if !got.get() {
return Ok(None);
}
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 handle = self.range.start();
let got = Cell::new(false);
let val = Cell::new(0u64);
let mut w: WriteBuf<2> = WriteBuf::new();
atomic_update(
allocator,
&[
handle + HEAD_OFF,
handle + LEN_OFF,
handle + CAP_OFF,
handle + DATA_OFF,
],
|v1| {
let (head, len, cap, data) = (v1[0], v1[1], v1[2], v1[3]);
if len == 0 {
Ok(Vec::new())
} else {
Ok(vec![Self::slot_addr(
data,
Self::ring_index(head, 0, cap)?,
)?])
}
},
|v1, v2| {
let (head, len, cap) = (v1[0], v1[1], v1[2]);
if len != 0 {
got.set(true);
val.set(v2[0]);
w.push(w8(handle + HEAD_OFF, Self::ring_index(head, 1, cap)?));
w.push(w8(handle + LEN_OFF, len - 1));
}
Ok(w.as_slice())
},
)?;
if !got.get() {
return Ok(None);
}
Ok(Some(unsafe {
BStackOwned::from_raw(Self::value_at(val.get()))
}))
}
fn grow<A: BStackRaiiAllocator>(&self, allocator: &A) -> io::Result<()> {
let handle = self.range.start();
let cap0 = read_u64(allocator.stack(), handle + CAP_OFF)?;
let newcap = if cap0 == 0 {
MIN_CAP
} else {
cap0.saturating_mul(2)
};
let new_size = newcap
.checked_mul(8)
.ok_or_else(|| io_error!("deque capacity overflow"))?;
let newring = allocator.alloc(new_size)?.as_range().start();
let grown = Cell::new(false);
let old_ring = Cell::new(0u64);
let old_cap = Cell::new(0u64);
let abort = |_head: u64, len: u64, cap: u64| (cap != 0 && len < cap) || newcap <= cap;
let mut w: Vec<(u64, SmallBuf)> = Vec::new();
atomic_update(
allocator,
&[
handle + HEAD_OFF,
handle + LEN_OFF,
handle + CAP_OFF,
handle + DATA_OFF,
],
|v1| {
let (head, len, cap, data) = (v1[0], v1[1], v1[2], v1[3]);
if abort(head, len, cap) {
Ok(Vec::new())
} else {
(0..len)
.map(|i| Self::slot_addr(data, Self::ring_index(head, i, cap)?))
.collect::<io::Result<Vec<u64>>>()
}
},
|v1, v2| {
let (head, len, cap, data) = (v1[0], v1[1], v1[2], v1[3]);
if !abort(head, len, cap) {
grown.set(true);
old_ring.set(data);
old_cap.set(cap);
w.reserve(v2.len() + 3);
for (i, &r) in v2.iter().enumerate() {
let off = newring
.checked_add(
(i as u64)
.checked_mul(8)
.ok_or_else(|| io_error!("deque offset overflow"))?,
)
.ok_or_else(|| io_error!("deque offset overflow"))?;
w.push(w8(off, r));
}
w.push(w8(handle + DATA_OFF, newring));
w.push(w8(handle + CAP_OFF, newcap));
w.push(w8(handle + HEAD_OFF, 0u64));
}
Ok(w.as_slice())
},
)?;
if grown.get() {
if old_cap.get() > 0 {
let _ = unsafe {
dealloc_range(
allocator,
BStackRange::new(old_ring.get(), old_cap.get().saturating_mul(8)),
)
};
}
} else {
let _ = unsafe { dealloc_range(allocator, BStackRange::new(newring, new_size)) };
}
Ok(())
}
pub fn front(&self, stack: &BStack) -> io::Result<Option<T>> {
let (head, len, cap, data) = Self::read_meta(stack, self.range.start())?;
if len == 0 {
return Ok(None);
}
let off = Self::slot_addr(data, Self::ring_index(head, 0, cap)?)?;
Ok(Some(Self::value_at(read_u64(stack, off)?)))
}
pub fn back(&self, stack: &BStack) -> io::Result<Option<T>> {
let (head, len, cap, data) = Self::read_meta(stack, self.range.start())?;
if len == 0 {
return Ok(None);
}
let off = Self::slot_addr(data, Self::ring_index(head, len - 1, cap)?)?;
Ok(Some(Self::value_at(read_u64(stack, off)?)))
}
pub fn to_vec(&self, stack: &BStack) -> io::Result<Vec<T>> {
let (head, len, cap, data) = Self::read_meta(stack, self.range.start())?;
let ring_bytes = len
.checked_mul(8)
.ok_or_else(|| io_error!("deque length overflow"))?;
if ring_bytes > stack.len()? {
return Err(io_error!("deque length larger than the stack"));
}
let mut out = Vec::with_capacity(len as usize);
for i in 0..len {
let off = Self::slot_addr(data, Self::ring_index(head, i, cap)?)?;
out.push(Self::value_at(read_u64(stack, off)?));
}
Ok(out)
}
pub fn iter<'a>(&self, stack: &'a BStack) -> io::Result<DequeIter<'a, T>> {
let (head, len, cap, data) = Self::read_meta(stack, self.range.start())?;
Ok(DequeIter {
stack,
block_off: self.range.start(),
data,
cap,
head,
len,
pos: 0,
_marker: PhantomData,
})
}
}
impl<T: BStackBlock> BStackCast for BStackDeque<T> {
fn eightcc() -> EightCC {
const BASE: EightCC = EightCC::new([b'D', b'e', b'q', 0x80, 0x81, 0x82, 0x83, 0x84]);
BASE.mix(<T as BStackCast>::eightcc())
}
}
impl<T: BStackBlock> crate::types::traits::BStackEmbeddable for BStackDeque<T> {}
impl<T: BStackBlock> BStackBlock for BStackDeque<T> {
type OnDisk = DequeOnDisk;
unsafe fn from_range(range: BStackRange) -> Self {
BStackDeque {
range,
_marker: PhantomData,
}
}
fn range(&self) -> BStackRange {
self.range
}
fn __bstack_drop_children<A: BStackRaiiAllocator>(
allocator: &A,
range: BStackRange,
) -> io::Result<()> {
let (head, len, cap, data) = Self::read_meta(allocator.stack(), range.start())?;
for i in 0..len {
let off = Self::slot_addr(data, Self::ring_index(head, i, cap)?)?;
let r = read_u64(allocator.stack(), off)?;
if r != 0 {
let owned = unsafe { BStackOwned::from_raw(Self::value_at(r)) };
owned.bstack_drop(allocator)?;
}
}
if data != 0 {
let size = cap
.checked_mul(8)
.ok_or_else(|| io_error!("deque 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 (head, len, cap, data) = Self::read_meta(allocator.stack(), self.range.start())?;
let ring_bytes = len
.checked_mul(8)
.ok_or_else(|| io_error!("deque length overflow"))?;
if ring_bytes > allocator.len()? {
return Err(io_error!("deque length larger than the stack"));
}
let mut dsts = Vec::with_capacity(len as usize);
for i in 0..len {
let off = Self::slot_addr(data, Self::ring_index(head, i, cap)?)?;
let r = read_u64(allocator.stack(), off)?;
let dst = if r != 0 {
Self::value_at(r)
.__bstack_clone_into(allocator, plan)?
.start()
} else {
0
};
dsts.push(dst);
}
let (new_data, new_cap) = if len > 0 {
let ring = plan.alloc_raw(allocator, ring_bytes)?;
let mut bytes = Vec::with_capacity(dsts.len() * 8);
for d in &dsts {
bytes.extend_from_slice(&d.to_le_bytes());
}
plan.write(ring.start(), bytes);
(ring.start(), len)
} else {
(0, 0)
};
Ok(DequeOnDisk {
header: BlockHeader {
size: DEQUE_SIZE,
tag: Self::eightcc(),
},
data: new_data,
cap: new_cap,
head: 0,
len,
})
}
}
impl<T: BStackBlock> TryCloneIn for BStackDeque<T> {}
pub struct DequeIter<'a, T: BStackBlock> {
stack: &'a BStack,
block_off: u64,
data: u64,
cap: u64,
head: u64,
len: u64,
pos: u64,
_marker: PhantomData<fn() -> T>,
}
impl<'a, T: BStackBlock> Iterator for DequeIter<'a, T> {
type Item = io::Result<T>;
fn next(&mut self) -> Option<Self::Item> {
if self.pos >= self.len {
return None;
}
match BStackDeque::<T>::read_meta(self.stack, self.block_off) {
Ok((head, len, cap, data))
if data == self.data && cap == self.cap && head == self.head && len == self.len => {
}
Ok(_) => {
self.pos = self.len;
return Some(Err(io_error!(
"BStackDeque was mutated during iteration (its head/len/ring \
changed); the iterator is invalidated"
)));
}
Err(e) => {
self.pos = self.len;
return Some(Err(e));
}
}
let slot = match BStackDeque::<T>::ring_index(self.head, self.pos, self.cap)
.and_then(|idx| BStackDeque::<T>::slot_addr(self.data, idx))
{
Ok(off) => off,
Err(e) => {
self.pos = self.len; return Some(Err(e));
}
};
self.pos += 1;
match read_u64(self.stack, slot) {
Ok(vref) => Some(Ok(BStackDeque::<T>::value_at(vref))),
Err(e) => {
self.pos = self.len; Some(Err(e))
}
}
}
}