vecdep/
lib.rs

1
2//! A very basic FiFo like structure, that is like std's VecDeque,
3//! and doesn't allocate on creation.
4//! 
5//! It can be used inside static variables.
6//! 
7//! This library uses unsafe code and is only testet minimaly, I can't
8//! promise that it works on anything else then x64 windows,
9//! It should be compatible with most architectures though.
10
11#[cfg(test)]
12mod tests;
13
14pub(crate) mod wrapping;
15
16use std::{alloc::{Layout, alloc, dealloc}, fmt::{Debug, Write}, ptr::null_mut};
17use wrapping::Wrapping;
18
19unsafe fn malloc<T>(size: usize) -> *mut T {
20    alloc(Layout::array::<T>(size).unwrap()) as *mut T
21}
22unsafe fn demalloc<T>(ptr: *mut T, size: usize) {
23    dealloc(ptr as *mut u8, Layout::array::<T>(size).unwrap());
24}
25
26/// A FiFo style queue, similar but not as powerful as std's VecDeque.
27/// 
28/// Poping and pushing can be done in O(1) time and
29/// doesn't require shifting the elements.
30/// The VecDep is backed by a ring buffer with a fixed size.
31/// If the buffer exceedes it's size limit, it starts deleting the oldest elements.
32/// The queue is not really tested for zero sized types or dynamically sized types, althoug ZSTs
33/// should work.
34pub struct VecDep<T> {
35    /* The content is layed out as follows:
36        teil 1 3 7 2 head - -
37        \___________________/
38              capacity
39    */
40    content: *mut T,
41    capacity: usize,
42    head: Wrapping,
43    tail: Wrapping,
44    len: usize,
45}
46
47impl<T> VecDep<T> {
48    
49    /// Construct a new VecDep queue
50    /// # Examples
51    /// 
52    /// ```
53    /// use vecdep::VecDep;
54    /// 
55    /// let mut queue: VecDep<u32> = VecDep::new(32);
56    /// 
57    /// queue.push(19);
58    /// queue.push(12);
59    /// 
60    /// assert!(queue.is_full());
61    /// 
62    /// assert!(queue.peek() == Some(&19));
63    /// assert!(queue.pop() == Some(19));
64    /// assert!(queue.pop() == Some(12));
65    /// 
66    /// assert!(queue.is_empty());
67    /// ```
68    /// 
69    #[inline]
70    pub const fn new(capacity: usize) -> Self {
71        Self {
72            content: null_mut(),
73            capacity,
74            head: Wrapping::new(0, capacity - 1),
75            tail: Wrapping::new(0, capacity - 1),
76            len: 0,
77        }
78    }
79
80    /// Push an element onto the queue.
81    #[inline]
82    pub fn push(&mut self, item: T) {
83        
84        // Allocate, if the space isn't intitialized yet
85        if self.content.is_null() { unsafe {
86            self.content = malloc::<T>(self.capacity);
87            if cfg!(test) { self.content.write_bytes(0, self.capacity) }; // for debugging purposes
88        } }
89
90        // If the buffer would be "filled" with values, start deleting the oldest one
91        if self.is_full() {
92            self.tail += 1;
93            // panic!("Buffer is full!");
94        }
95        // Increment the length only if the buffer isn't filled completely
96        else {
97            self.len += 1;
98        };
99
100        // Write the new element and increment the head index
101        unsafe { *self.content.add(*self.head) = item };
102
103        self.head += 1;
104
105    }
106
107    /// Pop the oldest element from the buffer.
108    #[inline]
109    pub fn pop(&mut self) -> Option<T> {
110
111        if self.is_empty() { return None };
112
113        let item = unsafe { self.content.add(*self.tail).read() };
114
115        self.tail += 1;
116        self.len -= 1;
117
118        Some(item)
119
120    }
121
122    /// Peek the oldest element without removing it
123    #[inline]
124    pub fn peek<'d>(&'d self) -> Option<&'d T> {
125
126        if self.is_empty() { return None };
127
128        let item = unsafe { self.content.add(*self.tail).as_ref().unwrap() };
129
130        Some(item)
131
132    }
133
134    /// Get the length of the stored elements.
135    #[inline(always)]
136    pub const fn len(&self) -> usize {
137        self.len
138    }
139    
140    /// The maximum capacity of this buffer.
141    #[inline(always)]
142    pub const fn capacity(&self) -> usize {
143        self.capacity
144    }
145
146    /// If the buffer is full.
147    #[inline(always)]
148    pub fn is_full(&self) -> bool {
149        self.len == self.capacity 
150    }
151    
152    /// If the buffer is empty.
153    #[inline(always)]
154    pub fn is_empty(&self) -> bool {
155        self.len == 0
156    }
157
158}
159
160impl<T> Drop for VecDep<T> {
161    
162    /// Deallocate the inner storage
163    fn drop(&mut self) {
164
165        unsafe { demalloc(self.content, self.capacity) };
166
167    }
168
169}
170
171impl<T: Debug> Debug for VecDep<T> {
172    
173    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
174        
175        if self.content.is_null() {
176
177            f.write_str("[unallocated]")
178
179        } else {
180            
181            f.write_char('[')?;
182            for idx in 0..self.capacity {
183                unsafe {  f.write_fmt(format_args!("{:?}", *self.content.add(idx)))? };
184                if idx == *self.tail { f.write_str(" (T)")? };
185                if idx == *self.head { f.write_str(" (H)")? };
186                if idx + 1 < self.capacity { f.write_str(", ")? };
187            }
188            f.write_char(']')
189
190            // f.write_fmt(format_args!(" (T = {}, H = {})", *self.tail, *self.head))
191
192        }
193
194    }
195
196}
vecdep/lib.rs

vecdep/
lib.rs
