FIFO Queue

1 files changed, 126 insertions, 0 deletions

diff --git a/src/util/fifo_queue.rs b/src/util/fifo_queue.rs
new file mode 100644
index 0000000..3e27fc3
--- /dev/null
+++ b/src/util/fifo_queue.rs
@@ -0,0 +1,126 @@
+//! # FIFO Queue
+//!
+//! Provides the FIFO queue structure for allocations
+use crate::sync::NullLock;
+use crate::sync::interface::Mutex;
+use crate::util::node::*;
+use core::fmt;
+use core::fmt::{Debug,Formatter};
+
+/// # Initialize Queue
+/// - Name: Symbol name
+/// - Size: Number of elements
+/// - Default: Default value
+/// - Type: Data Type
+#[macro_export]
+macro_rules! init_fifo_queue {
+	($name:tt,$size:tt,$default:tt,$type:ty) => {
+		init_queue!{@gen [$name,$size,$default,$type,concat!("# ", stringify!($type), " Queue Allocator")]}
+	};
+	(@gen [$name:tt,$size:tt,$default:tt,$type:ty,$doc:expr]) => {
+		#[doc = $doc]
+		#[link_section = ".data.alloc"]
+		pub static $name: FifoQueue<'static, $type, {$size+1}> = FifoQueue::new(NullLock::new([Node::new($default); {$size+1}]));
+	};
+}
+
+/// # Queue Allocator
+///
+/// Structure to store a pool of allocated data structures.
+pub struct FifoQueue<'a, T: Sized, const COUNT: usize> {
+	/// # Synchronized Pool of items
+	///
+	/// Stores synchronization wrapper around the data pool
+	pub inner: NullLock<[Node<'a, T>;COUNT]>,
+}
+
+impl<'a, T: Sized, const COUNT: usize> FifoQueue<'a, T, COUNT> {
+    /// # Create new Fifo Queue
+    pub const fn new(initial: NullLock<[Node<'a, T>; COUNT]>) -> Self {
+        Self { inner: initial }
+    }
+}
+
+/// # Sharing Thread Safety for FifoQueue
+unsafe impl<T,const COUNT: usize> Send for FifoQueue<'_,T,COUNT> {}
+
+impl<'a, T: Sized,const COUNT: usize> FifoQueue<'a, T, COUNT> {
+	/// # Initialization of Fixed-Size Pool
+	/// 
+	/// Establishes the header and footer of the queue
+	/// as the first and second elements respectively.
+	/// All of the internal elements point to the next
+	/// one and the final element points to `None`
+	pub fn init(&self) {
+		self.inner.lock(|queue| {
+			for idx in 2..COUNT {
+				if idx != COUNT-1 {
+					queue[idx].next = Some(&mut queue[idx+1] as *mut Node<'a, T>);
+				} else {
+					queue[idx].next = None;
+				}
+			}
+			queue[0].next = Some(&mut queue[2] as *mut Node<'a, T>);
+			queue[1].next = Some(&mut queue[COUNT-1] as *mut Node<'a, T>);
+		});
+	}
+
+	/// # Allocate Data
+	///
+	/// If there is a data chunk available,
+	/// return it, otherwise return `None`
+	#[allow(dead_code)]
+	pub fn alloc(&self) -> Option<&mut Node<'a,T>> {
+		return self.inner.lock(|pool| {
+			if let Some(entry) = pool[0].next {
+				pool[0].next = unsafe { (*entry).next };
+				unsafe {
+					(*entry).next = None;
+				}
+				match pool[0].next {
+					None => {
+						pool[1].next = None
+					}
+					_ => {}
+				}
+				return Some(unsafe{&mut *entry as &mut Node<'a,T>});
+			} else {
+				return None;
+			}
+		});
+	}
+
+	/// # Free
+	///
+	/// Add the item to the end of the queue.
+	/// If there were no items, set it as the head.
+	#[allow(dead_code)]
+	pub fn free(&self, freed_item: &mut Node<'a,T>) {
+		self.inner.lock(|pool| {
+			freed_item.next = None;
+			match pool[1].next {
+				None => {
+					pool[0].next = Some(freed_item as *mut Node<'a,T>);
+				}
+				Some(entry) => {
+					unsafe {
+						(*entry).next = Some(freed_item as *mut Node<'a,T>);
+					}
+				}
+			}
+			pool[1].next = Some(freed_item as *mut Node<'a,T>);
+		});
+	}
+}
+
+impl<T: Debug,const COUNT: usize> Debug for FifoQueue<'_,T,COUNT> {
+	/// # Debug Formatted Output
+	///
+	/// Output each data point in the array with
+	/// its debug formatter.
+	fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+		self.inner.lock(|queue| {
+			return write!(f, "{:?}", queue);
+		})
+	}
+}