#![no_std]
pub mod btree;
pub const PAGE_SIZE: usize = 4096;
pub trait Storable: core::fmt::Debug {
fn compare<T: LoadPage>(&self, _txn: &T, _b: &Self) -> core::cmp::Ordering {
unimplemented!()
}
fn page_references(&self) -> Self::PageReferences;
type PageReferences: Iterator<Item = u64>;
}
#[macro_export]
macro_rules! direct_repr {
($t: ty) => {
impl Storable for $t {
type PageReferences = core::iter::Empty<u64>;
fn page_references(&self) -> Self::PageReferences {
core::iter::empty()
}
fn compare<T>(&self, _: &T, b: &Self) -> core::cmp::Ordering {
self.cmp(b)
}
}
impl UnsizedStorable for $t {
const ALIGN: usize = core::mem::align_of::<$t>();
fn size(&self) -> usize {
core::mem::size_of::<Self>()
}
unsafe fn onpage_size(_: *const u8) -> usize {
core::mem::size_of::<Self>()
}
unsafe fn write_to_page(&self, p: *mut u8) {
core::ptr::copy_nonoverlapping(self, p as *mut Self, 1)
}
unsafe fn from_raw_ptr<'a, T>(_: &T, p: *const u8) -> &'a Self {
&*(p as *const Self)
}
}
};
}
direct_repr!(());
direct_repr!(u8);
direct_repr!(i8);
direct_repr!(u16);
direct_repr!(i16);
direct_repr!(u32);
direct_repr!(i32);
direct_repr!(u64);
direct_repr!(i64);
direct_repr!([u8; 16]);
pub trait UnsizedStorable: Storable {
const ALIGN: usize;
fn size(&self) -> usize;
unsafe fn onpage_size(_: *const u8) -> usize;
unsafe fn write_to_page(&self, p: *mut u8);
unsafe fn from_raw_ptr<'a, T>(_: &T, p: *const u8) -> &'a Self;
}
impl Storable for [u8] {
type PageReferences = core::iter::Empty<u64>;
fn page_references(&self) -> Self::PageReferences {
core::iter::empty()
}
fn compare<T>(&self, _: &T, b: &Self) -> core::cmp::Ordering {
self.cmp(b)
}
}
impl UnsizedStorable for [u8] {
const ALIGN: usize = 2;
fn size(&self) -> usize {
2 + self.len()
}
unsafe fn from_raw_ptr<'a, T>(_: &T, p: *const u8) -> &'a Self {
let len = u16::from_le(*(p as *const u16));
assert_ne!(len, 0);
assert_eq!(len & 0xf000, 0);
core::slice::from_raw_parts(p.add(2), len as usize)
}
unsafe fn onpage_size(p: *const u8) -> usize {
let len = u16::from_le(*(p as *const u16));
2 + len as usize
}
unsafe fn write_to_page(&self, p: *mut u8) {
assert!(self.len() <= 510);
*(p as *mut u16) = (self.len() as u16).to_le();
core::ptr::copy_nonoverlapping(self.as_ptr(), p.add(2), self.len())
}
}
unsafe fn read<T: LoadPage, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(
_txn: &T,
k: *const u8,
) -> (*const u8, *const u8) {
let s = K::onpage_size(k);
let v = k.add(s);
let al = v.align_offset(V::ALIGN);
let v = v.add(al);
(k, v)
}
unsafe fn entry_size<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(
k: *const u8,
) -> usize {
let ks = K::onpage_size(k);
let va = V::ALIGN;
let v_off = (ks + va - 1) & !(va - 1);
let v_ptr = k.add(v_off);
let vs = V::onpage_size(v_ptr);
let ka = K::ALIGN.max(V::ALIGN);
let size = v_off + vs;
(size + ka - 1) & !(ka - 1)
}
#[derive(Debug)]
#[repr(C)]
pub struct CowPage {
pub data: *mut u8,
pub offset: u64,
}
#[derive(Debug, Clone, Copy)]
#[repr(C)]
pub struct Page<'a> {
pub data: &'a [u8; PAGE_SIZE],
pub offset: u64,
}
impl CowPage {
pub fn as_page(&self) -> Page {
Page {
data: unsafe { &*(self.data as *const [u8; PAGE_SIZE]) },
offset: self.offset,
}
}
#[cfg(feature = "crc32")]
pub fn crc(&self, hasher: &crc32fast::Hasher) -> u32 {
let mut hasher = hasher.clone();
hasher.reset();
unsafe {
hasher.update(core::slice::from_raw_parts(self.data, 4));
hasher.update(core::slice::from_raw_parts(
self.data.offset(8),
PAGE_SIZE - 8,
));
}
hasher.finalize()
}
#[cfg(feature = "crc32")]
pub fn crc_check(&self, hasher: &crc32fast::Hasher) -> bool {
let crc = unsafe { u32::from_le(*(self.data as *const u32)) };
self.crc(hasher) == crc
}
}
#[derive(Debug)]
pub struct MutPage(pub CowPage);
impl MutPage {
#[cfg(not(feature = "crc32"))]
pub fn clear_dirty(&mut self) {
unsafe { *self.0.data &= 0xfe }
}
#[cfg(feature = "crc32")]
pub fn clear_dirty(&mut self, hasher: &crc32fast::Hasher) {
unsafe {
*self.0.data &= 0xfe;
let crc = (self.0.data as *mut u32).offset(1);
*crc = self.0.crc(hasher)
}
}
}
impl CowPage {
pub fn is_dirty(&self) -> bool {
unsafe { (*self.data) & 1 != 0 }
}
}
pub trait LoadPage {
type Error;
fn load_page(&self, off: u64) -> Result<CowPage, Self::Error>;
fn rc(&self, _off: u64) -> Result<u64, Self::Error> {
Ok(0)
}
}
pub trait AllocPage: LoadPage {
fn alloc_page(&mut self) -> Result<MutPage, Self::Error>;
fn incr_rc(&mut self, off: u64) -> Result<usize, Self::Error>;
fn decr_rc(&mut self, off: u64) -> Result<usize, Self::Error>;
fn decr_rc_owned(&mut self, off: u64) -> Result<usize, Self::Error>;
}