strat9_kernel/sync/
fixed_queue.rs

1use core::mem::MaybeUninit;
2
3/// Fixed-capacity FIFO queue with no heap allocation.
4pub struct FixedQueue<T, const N: usize> {
5    entries: [MaybeUninit<T>; N],
6    head: usize,
7    len: usize,
8}
9
10impl<T, const N: usize> FixedQueue<T, N> {
11    /// Creates a new empty queue.
12    pub const fn new() -> Self {
13        Self {
14            entries: [const { MaybeUninit::uninit() }; N],
15            head: 0,
16            len: 0,
17        }
18    }
19
20    /// Returns the number of elements currently stored.
21    #[inline]
22    pub fn len(&self) -> usize {
23        self.len
24    }
25
26    /// Returns whether the queue is empty.
27    #[inline]
28    pub fn is_empty(&self) -> bool {
29        self.len == 0
30    }
31
32    /// Returns whether the queue is full.
33    #[inline]
34    pub fn is_full(&self) -> bool {
35        self.len == N
36    }
37
38    /// Returns a shared reference to the element at `index` from the front.
39    pub fn get(&self, index: usize) -> Option<&T> {
40        if index >= self.len {
41            return None;
42        }
43
44        let idx = (self.head + index) % N;
45        // SAFETY: `idx` lies within the initialized window of the queue.
46        Some(unsafe { self.entries[idx].assume_init_ref() })
47    }
48
49    /// Returns a shared reference to the last element.
50    pub fn back(&self) -> Option<&T> {
51        self.len.checked_sub(1).and_then(|index| self.get(index))
52    }
53
54    /// Returns an iterator from front to back.
55    pub fn iter(&self) -> FixedQueueIter<'_, T, N> {
56        FixedQueueIter {
57            queue: self,
58            index: 0,
59        }
60    }
61
62    /// Appends an element to the tail of the queue.
63    pub fn push_back(&mut self, value: T) -> Result<(), T> {
64        if self.is_full() {
65            return Err(value);
66        }
67
68        let tail = (self.head + self.len) % N;
69        self.entries[tail].write(value);
70        self.len += 1;
71        Ok(())
72    }
73
74    /// Removes and returns the element at the head of the queue.
75    pub fn pop_front(&mut self) -> Option<T> {
76        if self.is_empty() {
77            return None;
78        }
79
80        let head = self.head;
81        self.head = (self.head + 1) % N;
82        self.len -= 1;
83
84        // SAFETY: `head` points to an initialized element while `len > 0`.
85        Some(unsafe { self.entries[head].assume_init_read() })
86    }
87
88    /// Removes the first element matching `predicate`.
89    pub fn remove_first_where<F>(&mut self, mut predicate: F) -> Option<T>
90    where
91        F: FnMut(&T) -> bool,
92    {
93        for offset in 0..self.len {
94            let idx = (self.head + offset) % N;
95            // SAFETY: `idx` is within the initialized window `[head, head+len)`.
96            let entry = unsafe { self.entries[idx].assume_init_ref() };
97            if predicate(entry) {
98                return Some(self.remove_at(offset));
99            }
100        }
101        None
102    }
103
104    fn remove_at(&mut self, offset: usize) -> T {
105        debug_assert!(offset < self.len);
106
107        let idx = (self.head + offset) % N;
108        // SAFETY: `idx` points to an initialized element by construction.
109        let removed = unsafe { self.entries[idx].assume_init_read() };
110
111        for shift in offset..(self.len - 1) {
112            let src = (self.head + shift + 1) % N;
113            let dst = (self.head + shift) % N;
114            // SAFETY: `src` points to an initialized element and `dst` stays
115            // within the queue storage.
116            let moved = unsafe { self.entries[src].assume_init_read() };
117            self.entries[dst].write(moved);
118        }
119
120        self.len -= 1;
121        if self.len == 0 {
122            self.head = 0;
123        }
124
125        removed
126    }
127}
128
129pub struct FixedQueueIter<'a, T, const N: usize> {
130    queue: &'a FixedQueue<T, N>,
131    index: usize,
132}
133
134impl<'a, T, const N: usize> Iterator for FixedQueueIter<'a, T, N> {
135    type Item = &'a T;
136
137    fn next(&mut self) -> Option<Self::Item> {
138        let item = self.queue.get(self.index);
139        if item.is_some() {
140            self.index += 1;
141        }
142        item
143    }
144}
145
146impl<T, const N: usize> Drop for FixedQueue<T, N> {
147    fn drop(&mut self) {
148        while self.pop_front().is_some() {}
149    }
150}
strat9_kernel/sync/fixed_queue.rs

strat9_kernel/sync/
fixed_queue.rs
