vecdep 0.1.1

//! A very basic FiFo like structure, that is like std's VecDeque,
//! and doesn't allocate on creation.
//! 
//! It can be used inside static variables.
//! 
//! This library uses unsafe code and is only testet minimaly, I can't
//! promise that it works on anything else then x64 windows,
//! It should be compatible with most architectures though.

#[cfg(test)]
mod tests;

pub(crate) mod wrapping;

use std::{alloc::{Layout, alloc, dealloc}, fmt::{Debug, Write}, ptr::null_mut};
use wrapping::Wrapping;

unsafe fn malloc<T>(size: usize) -> *mut T {
    alloc(Layout::array::<T>(size).unwrap()) as *mut T
}
unsafe fn demalloc<T>(ptr: *mut T, size: usize) {
    dealloc(ptr as *mut u8, Layout::array::<T>(size).unwrap());
}

/// A FiFo style queue, similar but not as powerful as std's VecDeque.
/// 
/// Poping and pushing can be done in O(1) time and
/// doesn't require shifting the elements.
/// The VecDep is backed by a ring buffer with a fixed size.
/// If the buffer exceedes it's size limit, it starts deleting the oldest elements.
/// The queue is not really tested for zero sized types or dynamically sized types, althoug ZSTs
/// should work.
pub struct VecDep<T> {
    /* The content is layed out as follows:
        teil 1 3 7 2 head - -
        \___________________/
              capacity
    */
    content: *mut T,
    capacity: usize,
    head: Wrapping,
    tail: Wrapping,
    len: usize,
}

impl<T> VecDep<T> {
    
    /// Construct a new VecDep queue
    /// # Examples
    /// 
    /// ```
    /// use vecdep::VecDep;
    /// 
    /// let mut queue: VecDep<u32> = VecDep::new(32);
    /// 
    /// queue.push(19);
    /// queue.push(12);
    /// 
    /// assert!(queue.is_full());
    /// 
    /// assert!(queue.peek() == Some(&19));
    /// assert!(queue.pop() == Some(19));
    /// assert!(queue.pop() == Some(12));
    /// 
    /// assert!(queue.is_empty());
    /// ```
    /// 
    #[inline]
    pub const fn new(capacity: usize) -> Self {
        Self {
            content: null_mut(),
            capacity,
            head: Wrapping::new(0, capacity - 1),
            tail: Wrapping::new(0, capacity - 1),
            len: 0,
        }
    }

    /// Push an element onto the queue.
    #[inline]
    pub fn push(&mut self, item: T) {
        
        // Allocate, if the space isn't intitialized yet
        if self.content.is_null() { unsafe {
            self.content = malloc::<T>(self.capacity);
            if cfg!(test) { self.content.write_bytes(0, self.capacity) }; // for debugging purposes
        } }

        // If the buffer would be "filled" with values, start deleting the oldest one
        if self.is_full() {
            self.tail += 1;
            // panic!("Buffer is full!");
        }
        // Increment the length only if the buffer isn't filled completely
        else {
            self.len += 1;
        };

        // Write the new element and increment the head index
        unsafe { *self.content.add(*self.head) = item };

        self.head += 1;

    }

    /// Pop the oldest element from the buffer.
    #[inline]
    pub fn pop(&mut self) -> Option<T> {

        if self.is_empty() { return None };

        let item = unsafe { self.content.add(*self.tail).read() };

        self.tail += 1;
        self.len -= 1;

        Some(item)

    }

    /// Peek the oldest element without removing it
    #[inline]
    pub fn peek<'d>(&'d self) -> Option<&'d T> {

        if self.is_empty() { return None };

        let item = unsafe { self.content.add(*self.tail).as_ref().unwrap() };

        Some(item)

    }

    /// Get the length of the stored elements.
    #[inline(always)]
    pub const fn len(&self) -> usize {
        self.len
    }
    
    /// The maximum capacity of this buffer.
    #[inline(always)]
    pub const fn capacity(&self) -> usize {
        self.capacity
    }

    /// If the buffer is full.
    #[inline(always)]
    pub fn is_full(&self) -> bool {
        self.len == self.capacity 
    }
    
    /// If the buffer is empty.
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

}

impl<T> Drop for VecDep<T> {
    
    /// Deallocate the inner storage
    fn drop(&mut self) {

        unsafe { demalloc(self.content, self.capacity) };

    }

}

impl<T: Debug> Debug for VecDep<T> {
    
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        
        if self.content.is_null() {

            f.write_str("[unallocated]")

        } else {
            
            f.write_char('[')?;
            for idx in 0..self.capacity {
                unsafe {  f.write_fmt(format_args!("{:?}", *self.content.add(idx)))? };
                if idx == *self.tail { f.write_str(" (T)")? };
                if idx == *self.head { f.write_str(" (H)")? };
                if idx + 1 < self.capacity { f.write_str(", ")? };
            }
            f.write_char(']')

            // f.write_fmt(format_args!(" (T = {}, H = {})", *self.tail, *self.head))

        }

    }

}