irox_tools/buf/
round.rs

1// SPDX-License-Identifier: MIT
2// Copyright 2025 IROX Contributors
3//
4#![allow(clippy::indexing_slicing)]
5#![allow(clippy::unwrap_used)]
6
7use crate::buf::Buffer;
8use crate::iterators::Moderator;
9use core::ops::{Index, IndexMut};
10use irox_bits::{Bits, BitsError, BitsErrorKind, Error, ErrorKind, MutBits};
11
12///
13/// Double-ended circular Buffer.  Basically a fixed size [`std::collections::VecDeque`]
14#[derive(Debug, Clone)]
15pub struct RoundBuffer<const N: usize, T: Sized> {
16    buf: [Option<T>; N],
17    head: usize,
18    tail: usize,
19    size: usize,
20    mod_count: u32,
21}
22
23impl<const N: usize, T: Default + Copy + Sized> RoundBuffer<N, T> {
24    pub fn pop_n_front<const L: usize>(&mut self) -> Option<[T; L]> {
25        if self.size < L || N < L {
26            return None;
27        }
28        self.size -= L;
29        self.mod_count = self.mod_count.wrapping_add(1);
30        let mut out = [T::default(); L];
31        for out in out.iter_mut().take(L) {
32            *out = self.buf[self.head].take().unwrap_or_default();
33            // move the head pointer forward one
34            // unless head == tail
35            if self.head != self.tail {
36                self.head += 1;
37            }
38            // if head >= N, then wrap around
39            if self.head >= N {
40                self.head = 0;
41            }
42        }
43        Some(out)
44    }
45}
46
47/// Circular buffer iterator, just calls `pop_front()` repeatedly
48pub struct RoundBufferIter<const N: usize, T: Sized> {
49    buf: RoundBuffer<N, T>,
50}
51
52impl<const N: usize, T: Sized> Iterator for RoundBufferIter<N, T> {
53    type Item = T;
54
55    fn next(&mut self) -> Option<Self::Item> {
56        self.buf.pop_front()
57    }
58}
59
60impl<const N: usize, T: Sized> IntoIterator for RoundBuffer<N, T> {
61    type Item = T;
62    type IntoIter = RoundBufferIter<N, T>;
63
64    fn into_iter(self) -> Self::IntoIter {
65        RoundBufferIter { buf: self }
66    }
67}
68pub struct Iter<'a, const N: usize, T: Sized> {
69    buf: &'a RoundBuffer<N, T>,
70    iter: Moderator,
71}
72impl<'a, const N: usize, T: Sized> Iterator for Iter<'a, N, T> {
73    type Item = &'a T;
74
75    fn next(&mut self) -> Option<Self::Item> {
76        let idx = self.iter.next()?;
77        self.buf.get(idx)
78    }
79}
80impl<const N: usize, T: Sized> RoundBuffer<N, T> {
81    const VAL: Option<T> = None;
82
83    pub fn new() -> Self {
84        RoundBuffer {
85            buf: [Self::VAL; N],
86            head: 0,
87            tail: 0,
88            size: 0,
89            mod_count: 0,
90        }
91    }
92    pub fn iter(&self) -> Iter<N, T> {
93        let iter = Moderator::new_limited(self.head, N, self.size);
94        Iter { buf: self, iter }
95    }
96    pub fn moderator(&self) -> Moderator {
97        Moderator::new_limited(self.head, N, self.size)
98    }
99    pub fn capacity(&self) -> usize {
100        N
101    }
102    pub fn len(&self) -> usize {
103        self.size
104    }
105    pub fn clear(&mut self) {}
106    pub fn is_empty(&self) -> bool {
107        self.size == 0
108    }
109    pub fn is_full(&self) -> bool {
110        self.size == N
111    }
112
113    ///
114    /// Provides access to the raw internal buffer.
115    pub fn raw_buf<R, F: FnMut(&[Option<T>]) -> R>(&self, mut f: F) -> R {
116        f(&self.buf)
117    }
118}
119
120impl<const N: usize, T: Sized> Default for RoundBuffer<N, T> {
121    fn default() -> Self {
122        Self::new()
123    }
124}
125
126impl<const N: usize, T> Drop for RoundBuffer<N, T> {
127    fn drop(&mut self) {
128        for val in &mut self.buf {
129            if let Some(v) = val.take() {
130                drop(v);
131            }
132        }
133    }
134}
135
136impl<const N: usize, T> Buffer<T> for RoundBuffer<N, T> {
137    fn get(&self, index: usize) -> Option<&T> {
138        if index >= N || index >= self.size {
139            return None;
140        }
141        self.buf[index].as_ref()
142    }
143
144    fn get_mut(&mut self, index: usize) -> Option<&mut T> {
145        if index >= N || index >= self.size {
146            return None;
147        }
148        self.buf[index].as_mut()
149    }
150
151    fn capacity(&self) -> usize {
152        N
153    }
154
155    fn len(&self) -> usize {
156        self.size
157    }
158
159    fn clear(&mut self) {
160        self.head = 0;
161        self.tail = 0;
162        self.size = 0;
163        self.mod_count = self.mod_count.wrapping_add(1);
164    }
165
166    fn front(&self) -> Option<&T> {
167        self.buf[self.head].as_ref()
168    }
169
170    fn front_mut(&mut self) -> Option<&mut T> {
171        self.buf[self.head].as_mut()
172    }
173
174    fn back(&self) -> Option<&T> {
175        self.buf[self.tail].as_ref()
176    }
177
178    fn back_mut(&mut self) -> Option<&mut T> {
179        self.buf[self.tail].as_mut()
180    }
181
182    fn pop_front(&mut self) -> Option<T> {
183        if self.size == 0 || N == 0 {
184            return None;
185        }
186        self.size -= 1;
187        self.mod_count = self.mod_count.wrapping_add(1);
188
189        let out = self.buf[self.head].take();
190        // move the head pointer forward one
191        // unless head == tail
192        if self.head != self.tail {
193            self.head += 1;
194        }
195        // if head >= N, then wrap around
196        if self.head >= N {
197            self.head = 0;
198        }
199        out
200    }
201
202    fn pop_back(&mut self) -> Option<T> {
203        if self.size == 0 || N == 0 {
204            // empty
205            return None;
206        }
207        let out = self.buf[self.tail].take();
208        self.mod_count = self.mod_count.wrapping_add(1);
209
210        self.size -= 1;
211        // move the tail pointer back
212        // unless head == tail
213        if self.head != self.tail {
214            // if tail == 0, wrap around
215            if self.tail == 0 {
216                self.tail = N - 1;
217            } else {
218                self.tail -= 1;
219            }
220        }
221        out
222    }
223
224    fn push_front(&mut self, value: T) -> Result<(), T> {
225        if self.size == N || N == 0 {
226            // full
227            Err(value)
228        } else if self.size == 0 {
229            self.mod_count = self.mod_count.wrapping_add(1);
230
231            self.head = 0;
232            self.tail = 0;
233            self.buf[0] = Some(value);
234            self.size = 1;
235            Ok(())
236        } else {
237            self.mod_count = self.mod_count.wrapping_add(1);
238
239            if self.head == 0 {
240                self.head = N - 1;
241            }
242            self.buf[self.head] = Some(value);
243            self.size += 1;
244            Ok(())
245        }
246    }
247
248    fn push_back(&mut self, value: T) -> Result<(), T> {
249        if self.size == N || N == 0 {
250            // full
251            Err(value)
252        } else if self.size == 0 {
253            self.mod_count = self.mod_count.wrapping_add(1);
254
255            // empty
256            self.head = 0;
257            self.tail = 0;
258            self.size = 1;
259            self.buf[0] = Some(value);
260            Ok(())
261        } else {
262            self.mod_count = self.mod_count.wrapping_add(1);
263
264            // mixed
265            self.size += 1;
266            self.tail += 1;
267            if self.tail == N {
268                self.tail = 0;
269            }
270            self.buf[self.tail] = Some(value);
271            Ok(())
272        }
273    }
274}
275
276impl<const N: usize> Bits for RoundBuffer<N, u8> {
277    fn next_u8(&mut self) -> Result<Option<u8>, Error> {
278        Ok(self.pop_front())
279    }
280
281    fn read_be_u32(&mut self) -> Result<u32, Error> {
282        let a = self
283            .pop_n_front::<4>()
284            .ok_or_else(|| BitsError::new(BitsErrorKind::UnexpectedEof, "EOF"))?;
285        Ok(u32::from_be_bytes(a))
286    }
287}
288impl<const N: usize> Bits for &mut RoundBuffer<N, u8> {
289    fn next_u8(&mut self) -> Result<Option<u8>, Error> {
290        Ok(self.pop_front())
291    }
292
293    fn read_be_u32(&mut self) -> Result<u32, Error> {
294        let a = self
295            .pop_n_front::<4>()
296            .ok_or_else(|| BitsError::new(BitsErrorKind::UnexpectedEof, "EOF"))?;
297        Ok(u32::from_be_bytes(a))
298    }
299}
300
301impl<const N: usize> MutBits for RoundBuffer<N, u8> {
302    fn write_u8(&mut self, val: u8) -> Result<(), Error> {
303        self.push_back(val)
304            .map_err(|_| ErrorKind::OutOfMemory.into())
305    }
306}
307
308impl<const N: usize> MutBits for &mut RoundBuffer<N, u8> {
309    fn write_u8(&mut self, val: u8) -> Result<(), Error> {
310        self.push_back(val)
311            .map_err(|_| ErrorKind::OutOfMemory.into())
312    }
313}
314
315#[allow(clippy::panic)]
316impl<const N: usize, T> Index<usize> for RoundBuffer<N, T> {
317    type Output = T;
318
319    fn index(&self, index: usize) -> &Self::Output {
320        assert!(index < self.size, "{index} >= {}", self.size);
321        let mut offset = self.head + index;
322        if offset >= N {
323            offset -= N;
324        }
325        let Some(Some(val)) = self.buf.get(offset) else {
326            panic!("expected value at offset {offset} but was empty!");
327        };
328        val
329    }
330}
331#[allow(clippy::panic)]
332impl<const N: usize, T> IndexMut<usize> for RoundBuffer<N, T>
333where
334    T: Default,
335{
336    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
337        assert!(index < N, "index {index} >= capacity {N}");
338        let mut offset = self.head + index;
339        if offset >= N {
340            offset -= N;
341        }
342        if self.buf[offset].is_none() {
343            self.size += 1;
344            self.buf[offset] = Some(Default::default());
345        }
346        self.buf[offset].as_mut().unwrap()
347    }
348}
349
350#[cfg(test)]
351mod tests {
352    use crate::buf::Buffer;
353
354    macro_rules! assert_empty {
355        ($buf:ident) => {
356            assert_eq!(0, $buf.len());
357            assert_eq!(None, $buf.pop_front());
358            assert_eq!(None, $buf.pop_back());
359        };
360    }
361
362    macro_rules! assert_full {
363        ($buf:ident, $sz:literal, $elem:expr) => {
364            assert_eq!($sz, $buf.len());
365            assert_eq!(Err($elem), $buf.push_back($elem));
366            assert_eq!($sz, $buf.len());
367            assert_eq!(Err($elem), $buf.push_front($elem));
368            assert_eq!($sz, $buf.len());
369        };
370    }
371
372    #[test]
373    pub fn test_push_some() -> Result<(), u32> {
374        let mut buf = crate::buf::RoundBuffer::<3, u32>::default();
375        assert_empty!(buf);
376
377        buf.push_back(10)?;
378        assert_eq!(1, buf.len());
379        assert_eq!(0, buf.head);
380        assert_eq!(0, buf.tail);
381
382        buf.push_back(15)?;
383        assert_eq!(2, buf.len());
384        assert_eq!(0, buf.head);
385        assert_eq!(1, buf.tail);
386
387        buf.push_back(20)?;
388        assert_eq!(3, buf.len());
389        assert_eq!(0, buf.head);
390        assert_eq!(2, buf.tail);
391
392        assert_full!(buf, 3, 25);
393
394        assert_eq!(Some(10), buf.pop_front());
395        assert_eq!(2, buf.len());
396        assert_eq!(1, buf.head);
397        assert_eq!(2, buf.tail);
398
399        buf.push_back(30)?;
400        assert_eq!(3, buf.len());
401        assert_eq!(1, buf.head);
402        assert_eq!(0, buf.tail);
403
404        assert_full!(buf, 3, 35);
405
406        assert_eq!(Some(15), buf.pop_front());
407        assert_eq!(2, buf.len());
408        assert_eq!(2, buf.head);
409        assert_eq!(0, buf.tail);
410
411        assert_eq!(Some(20), buf.pop_front());
412        assert_eq!(1, buf.len());
413        assert_eq!(0, buf.head);
414        assert_eq!(0, buf.tail);
415
416        assert_eq!(Some(30), buf.pop_front());
417        assert_eq!(0, buf.len());
418        assert_eq!(0, buf.head);
419        assert_eq!(0, buf.tail);
420
421        assert_empty!(buf);
422        assert_empty!(buf);
423
424        Ok(())
425    }
426}
irox_tools/buf/round.rs

irox_tools/buf/
round.rs
