xitca_unsafe_collection/bound_queue/
mod.rs

1//! Simple bounded ring buffers with FIFO queue.
2
3pub mod heap;
4pub mod stack;
5
6use core::fmt;
7
8pub trait Queueable {
9    type Item;
10
11    // capacity of Self for check bound
12    fn capacity(&self) -> usize;
13
14    /// # Safety
15    /// caller must make sure given index is not out of bound and properly initialized.
16    unsafe fn _get_unchecked(&self, idx: usize) -> &Self::Item;
17
18    /// # Safety
19    /// caller must make sure given index is not out of bound and properly initialized.
20    unsafe fn _get_mut_unchecked(&mut self, idx: usize) -> &mut Self::Item;
21
22    /// # Safety
23    /// caller must make sure given index is not out of bound and properly initialized.
24    unsafe fn _read_unchecked(&mut self, idx: usize) -> Self::Item;
25
26    /// # Safety
27    /// caller must make sure given index is not out of bound and properly initialized.
28    unsafe fn _write_unchecked(&mut self, idx: usize, item: Self::Item);
29}
30
31struct Bounded<Q>
32where
33    Q: Queueable,
34{
35    queue: Q,
36    next: usize,
37    len: usize,
38}
39
40impl<Q> Bounded<Q>
41where
42    Q: Queueable,
43{
44    const fn is_empty(&self) -> bool {
45        self.len == 0
46    }
47
48    fn is_full(&self) -> bool {
49        self.len == self.queue.capacity()
50    }
51
52    const fn len(&self) -> usize {
53        self.len
54    }
55
56    fn incr_tail_len(&mut self) {
57        self.next += 1;
58        self.len += 1;
59
60        if self.next == self.queue.capacity() {
61            self.next = 0;
62        }
63    }
64
65    fn front(&self) -> Option<&Q::Item> {
66        if self.is_empty() {
67            None
68        } else {
69            Some(unsafe { self.front_unchecked() })
70        }
71    }
72
73    // SAFETY:
74    // caller must make sure self is not empty
75    unsafe fn front_unchecked(&self) -> &Q::Item {
76        let idx = self.front_idx();
77        self.queue._get_unchecked(idx)
78    }
79
80    fn truncate(&mut self, n: usize) {
81        if self.len > n {
82            let delta = self.len - n;
83            self.len = n;
84            if delta > self.next {
85                self.next = self.queue.capacity() + self.next - delta;
86            } else {
87                self.next -= delta;
88            }
89        }
90    }
91
92    fn front_mut(&mut self) -> Option<&mut Q::Item> {
93        if self.is_empty() {
94            None
95        } else {
96            Some(unsafe { self.front_mut_unchecked() })
97        }
98    }
99
100    // SAFETY:
101    // caller must make sure self is not empty
102    unsafe fn front_mut_unchecked(&mut self) -> &mut Q::Item {
103        let idx = self.front_idx();
104        self.queue._get_mut_unchecked(idx)
105    }
106
107    fn clear(&mut self) {
108        while self.pop_front().is_some() {}
109        self.next = 0;
110        self.len = 0;
111    }
112
113    fn pop_front(&mut self) -> Option<Q::Item> {
114        if self.is_empty() {
115            None
116        } else {
117            unsafe { Some(self.pop_front_unchecked()) }
118        }
119    }
120
121    // SAFETY:
122    // caller must make sure self is not empty
123    unsafe fn pop_front_unchecked(&mut self) -> Q::Item {
124        let idx = self.front_idx();
125        self.len -= 1;
126        self.queue._read_unchecked(idx)
127    }
128
129    fn push_back(&mut self, item: Q::Item) -> Result<(), PushError<Q::Item>> {
130        if self.is_full() {
131            Err(PushError(item))
132        } else {
133            unsafe {
134                self.push_back_unchecked(item);
135            }
136            Ok(())
137        }
138    }
139
140    // SAFETY:
141    // caller must make sure self is not full.
142    unsafe fn push_back_unchecked(&mut self, item: Q::Item) {
143        self.queue._write_unchecked(self.next, item);
144        self.incr_tail_len();
145    }
146
147    const fn iter(&self) -> Iter<'_, Q> {
148        Iter {
149            queue: &self.queue,
150            tail: self.next,
151            len: self.len(),
152        }
153    }
154
155    fn front_idx(&self) -> usize {
156        if self.next >= self.len {
157            self.next - self.len
158        } else {
159            self.queue.capacity() + self.next - self.len
160        }
161    }
162}
163
164impl<Q> fmt::Debug for Bounded<Q>
165where
166    Q: Queueable,
167{
168    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
169        write!(f, "ArrayQueue")
170    }
171}
172
173impl<Q> Drop for Bounded<Q>
174where
175    Q: Queueable,
176{
177    fn drop(&mut self) {
178        self.clear();
179    }
180}
181
182pub struct PushError<T>(T);
183
184impl<T> PushError<T> {
185    pub fn into_inner(self) -> T {
186        self.0
187    }
188}
189
190impl<T> fmt::Debug for PushError<T> {
191    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
192        write!(f, "PushError(..)")
193    }
194}
195
196#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
197#[derive(Clone)]
198pub struct Iter<'a, Q>
199where
200    Q: Queueable,
201{
202    queue: &'a Q,
203    tail: usize,
204    len: usize,
205}
206
207impl<'a, Q> Iterator for Iter<'a, Q>
208where
209    Q: Queueable,
210{
211    type Item = &'a Q::Item;
212
213    #[inline]
214    fn next(&mut self) -> Option<&'a Q::Item> {
215        if self.len == 0 {
216            return None;
217        }
218
219        let idx = if self.tail >= self.len {
220            self.tail - self.len
221        } else {
222            self.queue.capacity() + self.tail - self.len
223        };
224
225        self.len -= 1;
226
227        unsafe { Some(self.queue._get_unchecked(idx)) }
228    }
229
230    #[inline]
231    fn size_hint(&self) -> (usize, Option<usize>) {
232        (self.len, Some(self.len))
233    }
234}
xitca_unsafe_collection/bound_queue/mod.rs

xitca_unsafe_collection/bound_queue/
mod.rs
