From 114b75703aab558995a250768de47378c57349d9 Mon Sep 17 00:00:00 2001
From: Christian Cunningham <c@localhost>
Date: Tue, 23 Aug 2022 21:29:16 -0700
Subject: Add queue structure

---
 src/util/lifo_queue.rs | 107 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 107 insertions(+)
 create mode 100644 src/util/lifo_queue.rs

(limited to 'src/util/lifo_queue.rs')

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);
+        })
+    }
+}
-- 
cgit v1.2.1