Add queue structure

3 files changed, 157 insertions, 0 deletions

diff --git a/src/util/lifo_queue.rs b/src/util/lifo_queue.rs
new file mode 100644
index 0000000..cac1a7d
--- /dev/null
+++ b/src/util/lifo_queue.rs
@@ -0,0 +1,107 @@
+//! # Queue
+//!
+//! Queue structure
+use crate::sync::interface::Mutex;
+use crate::sync::NullLock;
+use crate::util::node::*;
+use core::fmt;
+use core::fmt::{Debug, Formatter};
+use core::marker::Sized;
+
+/// # Initialize Queue
+/// - Name: Symbol name
+/// - Size: Number of elements
+/// - Default: Default value
+/// - Type: Data Type
+#[macro_export]
+macro_rules! init_lifo_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: LifoQueue<'static, $type, {$size+1}> = LifoQueue::new(NullLock::new([Node::new($default); {$size+1}]));
+	};
+}
+
+/// # Queue Allocator
+///
+/// Structure to store a pool of allocated data structures.
+pub struct LifoQueue<'a, T: Sized, const COUNT: usize> {
+    /// # Synchronized Pool of items
+    ///
+    /// Stores synchronization wrapper around the data pool
+    inner: NullLock<[Node<'a, T>; COUNT]>,
+}
+
+impl<'a, T: Sized, const COUNT: usize> LifoQueue<'a, T, COUNT> {
+    pub const fn new(initial: NullLock<[Node<'a, T>; COUNT]>) -> Self {
+        Self { inner: initial }
+    }
+}
+
+/// # Sharing Thread Safety for LifoQueue
+unsafe impl<T, const COUNT: usize> Send for LifoQueue<'_, T, COUNT> {}
+
+impl<'a, T: Sized, const COUNT: usize> LifoQueue<'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 1..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[1] as *mut Node<'a, T>);
+        });
+    }
+
+    /// # Pop
+    ///
+    /// Get an item from the queue
+    #[allow(dead_code)]
+    pub fn pop(&self) -> Option<&mut Node<'a, T>> {
+        return self.inner.lock(|pool| {
+            if let Some(entry) = pool[0].next {
+                unsafe {
+                    pool[0].next = (*entry).next;
+                    (*entry).next = None;
+                    return Some(&mut *entry as &mut Node<'a, T>);
+                }
+            } else {
+                return None;
+            }
+        });
+    }
+
+    /// # Push
+    ///
+    /// Add the item to the start of the queue.
+    #[allow(dead_code)]
+    pub fn push(&self, freed_item: &mut Node<'a, T>) {
+        self.inner.lock(|pool| {
+            freed_item.next = pool[0].next;
+            pool[0].next = Some(freed_item as *mut Node<'a, T>);
+        });
+    }
+}
+
+impl<T: Debug, const COUNT: usize> Debug for LifoQueue<'_, 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);
+        })
+    }
+}
diff --git a/src/util/mod.rs b/src/util/mod.rs
new file mode 100644
index 0000000..fb16c26
--- /dev/null
+++ b/src/util/mod.rs
@@ -0,0 +1,3 @@
+//! # Utilities module
+pub mod lifo_queue;
+pub mod node;
diff --git a/src/util/node.rs b/src/util/node.rs
new file mode 100644
index 0000000..a22e395
--- /dev/null
+++ b/src/util/node.rs
@@ -0,0 +1,47 @@
+//! # Node type
+//!
+//! Provides a type that holds data and a pointer to the next structure.
+use core::fmt;
+use core::fmt::{Debug, Formatter};
+
+/// # Node
+///
+/// Encapsulates a data element and a pointer to the next `Queue` item
+#[derive(Copy, Clone)]
+pub struct Node<'a, T: Sized> {
+    /// # Data
+    ///
+    /// The encapsulated data
+    pub data: T,
+    /// # Pointer to the next item
+    pub next: Option<*mut Node<'a, T>>,
+}
+
+impl<T> Node<'_, T> {
+    /// # Constructor
+    pub const fn new(data: T) -> Self {
+        Self { data, next: None }
+    }
+    /// # Get the inner data
+    ///
+    /// Returns a borrow of the underlying data.
+    pub fn inner(&mut self) -> &mut T {
+        &mut self.data
+    }
+    /// # Get pointer to inner data
+    pub fn ptr(&mut self) -> *mut u8 {
+        self.inner() as *mut T as *mut u8
+    }
+}
+
+/// # Sharing Thread Safety for Node
+unsafe impl<T> Send for Node<'_, T> {}
+
+impl<T: Debug> Debug for Node<'_, T> {
+    /// # Debug formatter for `Node`
+    ///
+    /// Output the encapsulated data
+    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+        return write!(f, "{:?}", self.data);
+    }
+}