nightly_test_db_page.rs

#![feature(generic_const_exprs)]
#![allow(incomplete_features)]
#![feature(iter_map_windows)]

# Cargo.toml
# [dependencies]
# crc = "3.3.0"


// 4KiB
const PAGE_SIZE: usize = 2_usize.pow(12);
const CRC_16: crc::Crc<u16> = crc::Crc::<u16>::new(&crc::CRC_16_IBM_SDLC);

#[repr(C, packed)]
pub struct Header<const S: usize = PAGE_SIZE> {
    free_space: u16,
    num_slots: u16,
    last_offset: u16,
    checksum: u16,
}

impl<const S: usize> Header<S> {
    pub fn init_empty_buffer(&mut self) {
        self.num_slots = 0;
        self.free_space = (S - std::mem::size_of::<Self>()) as u16;
        self.last_offset = (S - std::mem::size_of::<Self>()) as u16;
        self.checksum = 0;
    }
}

impl<const S: usize> Default for Header<S> {
    fn default() -> Self {
        Self {
            num_slots: 0,
            free_space: (S - std::mem::size_of::<Self>()) as u16,
            last_offset: (S - std::mem::size_of::<Self>()) as u16,
            checksum: 0,
        }
    }
}

#[repr(C, packed)]
struct Test<T: Sized, const S: usize>
where
    [u8; S - std::mem::size_of::<T>()]: Sized,
{
    header: T,
    buff: [u8; S - std::mem::size_of::<T>()],
}

union PackedTest<'a, T: Sized, const S: usize>
where
    [u8; S - std::mem::size_of::<T>()]: Sized,
{
    buff: &'a mut [u8; S],
    page: &'a mut Test<T, S>,
}

impl<T: Sized + Default, const S: usize> Default for Test<T, S>
where
    [(); S - std::mem::size_of::<T>()]: Sized,
{
    fn default() -> Self {
        Self {
            header: T::default(),
            buff: [0; S - std::mem::size_of::<T>()],
        }
    }
}

impl Test<Header, PAGE_SIZE> {
    #[inline]
    pub fn free_space(&self) -> usize {
        self.header.free_space as usize
    }

    #[inline]
    pub fn num_slots(&self) -> usize {
        self.header.num_slots as usize
    }

    pub fn check_checkum(&self) -> bool {
        self.header.checksum == CRC_16.checksum(&self.buff)
    }

    #[inline]
    fn try_get_slot_range(&self, index: usize) -> Option<std::ops::Range<usize>> {
        if index >= self.num_slots() {
            return None;
        }
        let start_index =
            u16::from_be_bytes([self.buff[index * 2], self.buff[index * 2 + 1]]) as usize;
        let end_index = if index == 0 {
            self.buff.len()
        } else {
            u16::from_be_bytes([self.buff[(index - 1) * 2], self.buff[(index - 1) * 2 + 1]])
                as usize
        };
        Some(start_index..end_index)
    }

    pub fn try_get_slot(&self, index: usize) -> Option<&[u8]> {
        let range = self.try_get_slot_range(index)?;
        Some(&self.buff[range])
    }

    pub fn try_get_slot_mut(&mut self, index: usize) -> Option<&mut [u8]> {
        let range = self.try_get_slot_range(index)?;
        Some(&mut self.buff[range])
    }

    pub fn iter_slots(&self) -> impl Iterator<Item = &[u8]> {
        [self.buff.len()]
            .into_iter()
            .chain((0..=self.num_slots()).map(|index| {
                u16::from_be_bytes([self.buff[index * 2], self.buff[index * 2 + 1]]) as usize
            }))
            .map_windows(move |&[prev_offset, next_offset]| &self.buff[next_offset..prev_offset])
    }

    pub fn try_add_slot(&mut self, data: &[u8]) -> Option<()> {
        // get data and comput if the buffer can be saved in the page
        let data_size = data.len() as u16;
        let size_needed = data_size + std::mem::size_of::<u16>() as u16;
        dbg!(size_needed);
        dbg!(self.header.free_space);
        if self.header.free_space < size_needed {
            return None;
        }

        // save the data to the buffer and modify the header values
        // and the offset in the offsets array
        self.header.num_slots += 1;
        self.header.free_space -= size_needed;
        let last_offset = self.header.last_offset;
        self.header.last_offset -= data_size;
        let index = (self.header.num_slots as usize - 1) * 2;
        dbg!(last_offset);
        dbg!(index);
        self.buff[index..=index + 1].copy_from_slice(&self.header.last_offset.to_be_bytes());
        self.buff[self.header.last_offset as usize..last_offset as usize].copy_from_slice(data);
        self.header.checksum = CRC_16.checksum(&self.buff);
        Some(())
    }
}

fn main() {
    let mut buff = [0_u8; PAGE_SIZE];
    unsafe {
        let test = PackedTest::<Header, PAGE_SIZE> { buff: &mut buff };
        test.page.header.init_empty_buffer();
        println!("{}", test.page.free_space());
        test.page.try_add_slot(&[1, 2, 3, 4, 5]).unwrap();
        println!("{}", test.page.free_space());
        println!("{:?}", test.page.try_get_slot(0));
        if let Some(page) = test.page.try_get_slot_mut(0) {
            page[2] = 2;
        }
        println!("{:?}", test.page.try_get_slot(0));
    }
}

stable_test_db_page.rs

# Cargo.toml
# [dependencies]
# crc = "3.3.0"

use std::{alloc::Layout, ptr::NonNull};

// 4KiB
const PAGE_SIZE: usize = 2_usize.pow(12);
const PAGE_HEADER_SIZE: usize = std::mem::size_of::<PageHeader>();
const SLOT_HEADER_SIZE: usize = std::mem::size_of::<u16>();
const CRC_16: crc::Crc<u16> = crc::Crc::<u16>::new(&crc::CRC_16_IBM_SDLC);

#[repr(C, packed)]
pub struct PageHeader {
    free_space: u16,
    num_slots: u16,
    last_offset: u16,
    checksum: u16,
}
impl PageHeader {
    pub fn from_slice(slice: &[u8; PAGE_HEADER_SIZE]) -> Self {
        unsafe { Self::from_slice_unchecked(slice) }
    }

    pub unsafe fn from_slice_unchecked(slice: &[u8]) -> Self {
        Self {
            free_space: u16::from_le_bytes([slice[0], slice[1]]),
            num_slots: u16::from_le_bytes([slice[2], slice[3]]),
            last_offset: u16::from_le_bytes([slice[4], slice[5]]),
            checksum: u16::from_le_bytes([slice[6], slice[7]]),
        }
    }
    pub unsafe fn write_to_slice_unchecked(&self, slice: &mut [u8]) {
        slice[0..2].copy_from_slice(&self.free_space.to_le_bytes());
        slice[2..4].copy_from_slice(&self.num_slots.to_le_bytes());
        slice[4..6].copy_from_slice(&self.last_offset.to_le_bytes());
        slice[6..8].copy_from_slice(&self.checksum.to_le_bytes());
    }

    pub fn write_to_slice(&self, slice: &mut [u8; PAGE_HEADER_SIZE]) {
        unsafe {
            self.write_to_slice_unchecked(slice);
        }
    }
}

pub struct SlotsIter<'a> {
    page: &'a Page,
    curr_slot: usize,
}
impl<'a> SlotsIter<'a> {
    pub fn new(page: &'a Page) -> Self {
        Self { page, curr_slot: 0 }
    }
}
impl<'a> Iterator for SlotsIter<'a> {
    type Item = &'a [u8];
    fn next(&mut self) -> Option<Self::Item> {
        if self.curr_slot >= self.page.header.num_slots as usize {
            return None;
        }
        let res = self.page.try_get_slot(self.curr_slot);
        self.curr_slot += 1;
        res
    }
}

#[repr(C)]
pub struct Page {
    page: NonNull<u8>,
    header: PageHeader,
    size: usize,
}
  
impl Page {
    pub fn new() -> Self {
        Default::default()
    }

    pub fn free_space(&self) -> usize {
        self.header.free_space as usize
    }

    pub fn as_slice(&self) -> &[u8] {
        unsafe { std::slice::from_raw_parts(self.page.as_ptr(), self.size) }
    }

    pub fn with_size(size: usize) -> Self {
        assert!(
            size >= PAGE_SIZE,
            "size={size} should be at least {PAGE_SIZE}"
        );
        assert!(
            size <= u16::MAX as usize,
            "size={size} should not be larger that u16::MAX"
        );
        assert!(
            size % PAGE_SIZE == 0,
            "size={size} should be a multiple of {PAGE_SIZE}"
        );
        let layout = Layout::array::<u8>(size).unwrap();
        let page = match NonNull::new(unsafe { std::alloc::alloc(layout) }) {
            Some(p) => p,
            None => std::alloc::handle_alloc_error(layout),
        };
        let header = PageHeader {
            free_space: (size - PAGE_HEADER_SIZE) as u16,
            num_slots: 0,
            last_offset: (size - PAGE_HEADER_SIZE) as u16,
            checksum: 0,
        };
        Self { page, size, header }
    }

    pub fn try_from_raw(ptr: *mut u8, size: usize) -> Option<Self> {
        assert!(
            size >= PAGE_SIZE,
            "size={size} should be at least {PAGE_SIZE}"
        );
        assert!(
            size <= u16::MAX as usize,
            "size={size} should not be larger that u16::MAX"
        );
        assert!(
            size % PAGE_SIZE == 0,
            "size={size} should be a multiple of {PAGE_SIZE}"
        );
        let page = NonNull::new(ptr)?;
        let header = unsafe {
            PageHeader::from_slice_unchecked(std::slice::from_raw_parts(
                page.as_ptr(),
                PAGE_HEADER_SIZE,
            ))
        };
        Some(Self { page, size, header })
    }

    fn save_header(&mut self) {
        unsafe {
            self.header
                .write_to_slice_unchecked(std::slice::from_raw_parts_mut(
                    self.page.as_ptr(),
                    PAGE_HEADER_SIZE,
                ))
        }
    }

    fn get_data(&self) -> &[u8] {
        unsafe {
            std::slice::from_raw_parts(
                self.page.add(PAGE_HEADER_SIZE).as_ptr(),
                self.size - PAGE_HEADER_SIZE,
            )
        }
    }

    fn get_data_mut(&mut self) -> &mut [u8] {
        unsafe {
            std::slice::from_raw_parts_mut(
                self.page.add(PAGE_HEADER_SIZE).as_ptr(),
                self.size - PAGE_HEADER_SIZE,
            )
        }
    }

    #[inline]
    fn try_get_slot_range(&self, index: usize) -> Option<std::ops::Range<usize>> {
        if index as u16 >= self.header.num_slots {
            return None;
        }
        let buff = self.get_data();
        let start_index = u16::from_be_bytes([buff[index * 2], buff[index * 2 + 1]]) as usize;
        let end_index = if index == 0 {
            buff.len()
        } else {
            u16::from_be_bytes([buff[(index - 1) * 2], buff[(index - 1) * 2 + 1]]) as usize
        };
        Some(start_index..end_index)
    }

    pub fn try_get_slot(&self, index: usize) -> Option<&[u8]> {
        let range = self.try_get_slot_range(index)?;
        Some(&self.get_data()[range])
    }

    pub fn try_modify_slot(&mut self, index: usize, func: impl FnOnce(&mut [u8])) -> bool {
        if let Some(range) = self.try_get_slot_range(index) {
            func(&mut self.get_data_mut()[range]);
            self.header.checksum = CRC_16.checksum(self.get_data());
            self.save_header();
            true
        } else {
            false
        }
    }

    pub fn try_save_slot<'a>(&'a mut self, data: &'a [u8]) -> Option<usize> {
        let data_size = data.len();
        let size_needed = data_size + SLOT_HEADER_SIZE;
        if size_needed > self.header.free_space as usize {
            return None;
        }
        // save the data to the buffer and modify the header values
        // and the offset in the offsets array
        let last_offset = self.header.last_offset;
        let new_offset = self.header.last_offset - data_size as u16;

        let index = self.header.num_slots as usize * 2;
        let buff = self.get_data_mut();
        buff.get_mut(index..=index + 1)?
            .copy_from_slice(new_offset.to_be_bytes().as_slice());
        buff.get_mut(new_offset as usize..last_offset as usize)?
            .copy_from_slice(data);
        self.header.free_space -= size_needed as u16;
        self.header.num_slots += 1;
        self.header.last_offset = new_offset;
        self.header.checksum = CRC_16.checksum(self.get_data());
        self.save_header();
        Some((self.header.num_slots - 1) as usize)
    }

    pub fn iter_slots(&self) -> impl Iterator<Item = &[u8]> {
        SlotsIter::new(self)
    }
}

impl Drop for Page {
    fn drop(&mut self) {
        if self.size > 0 {
            let layout = Layout::array::<u8>(self.size).unwrap();
            unsafe {
                std::alloc::dealloc(self.page.as_ptr(), layout);
            }
        }
    }
}

impl Default for Page {
    fn default() -> Self {
        Self::with_size(PAGE_SIZE)
    }
}

fn main() {
    let mut page = Page::default();
    println!("{}", page.free_space());
    let slot_id = page.try_save_slot(&[1, 2, 3, 4]).unwrap();
    println!("{}", page.free_space());
    println!("{:?}", page.try_get_slot(slot_id));
    page.try_modify_slot(slot_id, |x| x[0] = 0);
    println!("{:?}", page.try_get_slot(slot_id));
}