multi_stack_queue/
lib.rs

1//! A crate for stack-allocated fixed-length multiqueues. A multiqueue is an array of a given number of queues,
2//! each able to be accessed independently.
3//!
4//! In term, this crate should include a feature that enables the user to specify what the multiqueue must do
5//! in the case the `pop` or `push` method cannot operate (e.g. empty or full individual queue.).
6//! For instance, one could wish the operation is, in such a case, applied to the following queue.
7//!
8//! This crate was motivated by the creation of a multiple-round-robin-based scheduler in a toy micro-kernel.
9//! Each queue holds all the threads within the same priority level.
10//! Attempting to create a new thread in an already full priority level would simply decrease its priority
11//! until a suitable non-full queue is found.
12//!
13//! Based on an original idea from [Pollux3737](https://github.com/Pollux3737).
14
15use std::mem::MaybeUninit;
16
17/// Errors that may be encountered during use of the [`MultiStackQueue`]
18///
19/// * `QueueFull` - Returned by the `push` method when trying to append a value to a queue that is already full
20/// * `QueueEmpty` - Returned by the `pop` method when trying to pop a value from an empty queue
21/// * `QueueIndexOutOfBounds` - When trying to access a queue beyond the multiqueue
22/// * `UnknownError` - This should never happen. Used for development
23#[derive(Debug, Copy, Clone, Eq, PartialEq)]
24pub enum MSQError {
25    QueueFull,
26    QueueEmpty,
27    QueueIndexOutOfBounds,
28    UnknowmError,
29}
30
31/// An abstract structure containin multiple stack-allocated bounded queues.
32///
33/// Each queue is stored as an `[Option<T>; N]` and the multiqueue stores
34//// the complete data in an `[[Option<T>; N]; M].
35
36///
37/// # Usage
38///
39/// The generic definition is the following :
40///
41/// ```ignore
42/// MultiStackQueue<T, const N: usize, const M: usize>
43/// ```
44///
45/// With :
46///
47/// * `T` - type contained in the queues
48/// * `N` - length of each queue
49/// * `M` - number of queues
50///
51/// # Example usecases
52///
53/// * When writing a simple micro-kernel, the scheduler may need some sort of multiple Round-Robins.
54/// Having it allocated on the stack removes the need for a heap allocator, which can be useful
55/// when working on this kind of ressource-limited target.
56///
57/// # Examples
58///
59/// ```
60/// use multi_stack_queue::MultiStackQueue;
61///
62/// #[derive(Clone, Copy, Debug, PartialEq, Eq)]
63/// struct TestStruct {
64///     a: usize,
65///     b: bool,   
66/// }
67///
68/// let mut msq: MultiStackQueue<TestStruct, 16, 8> = MultiStackQueue::new();
69/// let value = TestStruct { a: 42, b: false };
70///
71/// msq.push(7, value).unwrap();
72///
73/// assert_eq!(msq.pop(7).unwrap(), value);
74/// ```
75///
76pub struct MultiStackQueue<T, const N: usize, const M: usize> {
77    data: [[Option<T>; N]; M],
78    ins: [usize; M],
79    outs: [usize; M],
80    empty: [bool; M],
81}
82
83impl<T, const N: usize, const M: usize> MultiStackQueue<T, N, M> {
84    /// Returns a new empty multiqueue.
85    ///
86    /// # Examples
87    ///
88    /// ```
89    /// use multi_stack_queue::MultiStackQueue;
90    /// // Returns a fresh empty multiqueue containing 8 queues of `usize` with size 16
91    /// let a: MultiStackQueue<usize, 16, 8> = MultiStackQueue::new();
92    ///
93    /// #[derive(Clone, Copy)]
94    /// struct TestStruct {
95    ///     a: usize,
96    ///     b: bool    
97    /// }
98    ///
99    /// let random_data = TestStruct { a: 42, b: false };
100    ///
101    /// let msq: MultiStackQueue<TestStruct, 4, 2> = MultiStackQueue::new();
102    /// ```
103    ///
104    pub fn new() -> Self {
105        let d: [[Option<T>; N]; M] = unsafe { MaybeUninit::uninit().assume_init() };
106        MultiStackQueue {
107            data: d,
108            ins: [0usize; M],
109            outs: [0usize; M],
110            empty: [true; M],
111        }
112    }
113    /// Appends a value to the multiqueue.
114    ///
115    /// # Examples
116    ///
117    /// ```
118    /// use multi_stack_queue::MultiStackQueue;
119    ///
120    /// #[derive(Clone, Copy)]
121    /// struct TestStruct {
122    ///     a: usize,
123    ///     b: bool    
124    /// }
125    ///
126    /// let random_data = TestStruct { a: 42, b: false };
127    ///
128    /// let mut msq: MultiStackQueue<TestStruct, 4, 2> = MultiStackQueue::new();
129    ///
130    /// msq.push(0, random_data).unwrap();
131    /// ```
132    ///
133    pub fn push(&mut self, id: usize, value: T) -> Result<(), MSQError> {
134        if id >= M {
135            return Err(MSQError::QueueIndexOutOfBounds);
136        }
137        self.try_and_push(id, value)
138    }
139    // Inner `push` function
140    fn try_and_push(&mut self, id: usize, value: T) -> Result<(), MSQError> {
141        if self.ins[id] == self.outs[id] && !self.empty[id] {
142            // Queue is full
143            Err(MSQError::QueueFull)
144        } else {
145            self.data[id][self.ins[id]] = Some(value);
146            self.ins[id] = (self.ins[id] + 1) % N;
147            self.empty[id] = false;
148            Ok(())
149        }
150    }
151    /// Pops a value from the multiqueue.
152    ///
153    /// # Examples
154    ///
155    /// ```
156    /// use multi_stack_queue::MultiStackQueue;
157    ///
158    /// #[derive(Clone, Copy)]
159    /// struct TestStruct {
160    ///     a: usize,
161    ///     b: bool    
162    /// }
163    ///
164    /// let random_data = TestStruct { a: 42, b: false };
165    ///
166    /// let mut msq: MultiStackQueue<TestStruct, 4, 2> = MultiStackQueue::new();
167    ///
168    /// msq.push(0, random_data).unwrap();
169    /// msq.pop(0).unwrap();
170    /// ```
171    ///
172    pub fn pop(&mut self, id: usize) -> Result<T, MSQError> {
173        if id >= M {
174            return Err(MSQError::QueueIndexOutOfBounds);
175        }
176        self.try_and_pop(id)
177    }
178    /// Inner `pop` function
179    fn try_and_pop(&mut self, id: usize) -> Result<T, MSQError> {
180        if self.empty[id] {
181            Err(MSQError::QueueEmpty)
182        } else {
183            // TODO The unwrap is not ideal
184            let res = self.data[id][self.outs[id]].take().unwrap();
185            self.outs[id] = (self.outs[id] + 1) % N;
186            if self.outs[id] == self.ins[id] {
187                self.empty[id] = true;
188            }
189            Ok(res)
190        }
191    }
192    /// Returns whether a particular queue is full
193    /// # Examples
194    ///
195    /// ```
196    /// use multi_stack_queue::MultiStackQueue;
197    ///
198    /// let mut msq: MultiStackQueue<usize, 4, 2> = MultiStackQueue::new();
199    ///
200    /// assert!(!msq.is_full(0));
201    /// for _ in 0..4 {
202    ///     msq.push(0, 0);
203    /// }
204    /// assert!(msq.is_full(0));
205    /// ```
206    ///
207    pub fn is_full(&self, id: usize) -> bool {
208        !self.empty[id] && self.ins[id] == self.outs[id]
209    }
210    /// Returns whether a particular queue is empty
211    /// # Examples
212    ///
213    /// ```
214    /// use multi_stack_queue::MultiStackQueue;
215    ///
216    /// let mut msq: MultiStackQueue<usize, 4, 2> = MultiStackQueue::new();
217    ///
218    /// assert!(msq.is_empty(0));
219    /// msq.push(0, 0);
220    /// assert!(!msq.is_empty(0));
221    /// ```
222    ///
223    pub fn is_empty(&self, id: usize) -> bool {
224        self.empty[id]
225    }
226}
227
228#[cfg(test)]
229mod tests {
230    use crate::MultiStackQueue;
231
232    /// Simple test structure
233    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
234    struct TestStruct {
235        a: usize,
236        b: bool,
237    }
238
239    /// Testing the creation of a MSQ
240    #[test]
241    fn creation() {
242        let a: MultiStackQueue<TestStruct, 16, 32> = MultiStackQueue::new();
243    }
244
245    /// Testing one `push` operation
246    #[test]
247    fn push_once() {
248        let mut a: MultiStackQueue<TestStruct, 16, 32> = MultiStackQueue::new();
249        let val = TestStruct { a: 42, b: true };
250        a.push(12, val).unwrap();
251    }
252
253    /// Testing one push-pop cycle
254    #[test]
255    fn push_and_pop_once() {
256        let mut a: MultiStackQueue<TestStruct, 16, 32> = MultiStackQueue::new();
257        let val = TestStruct { a: 42, b: true };
258        a.push(12, val).unwrap();
259        assert_eq!(a.pop(12).unwrap(), val);
260        assert!(a.is_empty(12));
261    }
262
263    /// Testing push-pop-pop
264    #[test]
265    #[should_panic]
266    fn push_and_pop_twice() {
267        let mut a: MultiStackQueue<TestStruct, 16, 32> = MultiStackQueue::new();
268        let val = TestStruct { a: 42, b: true };
269        a.push(12, val).unwrap();
270        a.pop(12).unwrap();
271        a.pop(12).unwrap();
272    }
273
274    /// testing a single pop operation
275    #[test]
276    #[should_panic]
277    fn pop_empty() {
278        let mut a: MultiStackQueue<TestStruct, 16, 32> = MultiStackQueue::new();
279        a.pop(12).unwrap();
280    }
281
282    /// Testing the filling of a queue
283    #[test]
284    fn fill() {
285        let mut a: MultiStackQueue<TestStruct, 16, 32> = MultiStackQueue::new();
286        let val = TestStruct { a: 42, b: true };
287        for _ in 0..16 {
288            a.push(12, val).unwrap();
289        }
290    }
291
292    /// Testing the overflow of a queue
293    #[test]
294    #[should_panic]
295    fn fill_overflow() {
296        let mut a: MultiStackQueue<TestStruct, 16, 32> = MultiStackQueue::new();
297        let val = TestStruct { a: 42, b: true };
298        for _ in 0..=16 {
299            a.push(12, val).unwrap();
300        }
301    }
302
303    /// Testing that the queue works as intended
304    #[test]
305    fn fifo() {
306        let mut a: MultiStackQueue<usize, 16, 32> = MultiStackQueue::new();
307        a.push(0, 1).unwrap();
308        a.push(0, 2).unwrap();
309        assert_eq!(a.pop(0).unwrap(), 1);
310        assert_eq!(a.pop(0).unwrap(), 2);
311    }
312}
multi_stack_queue/lib.rs

multi_stack_queue/
lib.rs
