heapless/
histbuf.rs

Help
1use core::fmt;
2use core::mem::MaybeUninit;
3use core::ops::Deref;
4use core::ptr;
5use core::slice;
6
7/// A "history buffer", similar to a write-only ring buffer of fixed length.
8///
9/// This buffer keeps a fixed number of elements.  On write, the oldest element
10/// is overwritten. Thus, the buffer is useful to keep a history of values with
11/// some desired depth, and for example calculate a rolling average.
12///
13/// # Examples
14/// ```
15/// use heapless::HistoryBuffer;
16///
17/// // Initialize a new buffer with 8 elements.
18/// let mut buf = HistoryBuffer::<_, 8>::new();
19///
20/// // Starts with no data
21/// assert_eq!(buf.recent(), None);
22///
23/// buf.write(3);
24/// buf.write(5);
25/// buf.extend(&[4, 4]);
26///
27/// // The most recent written element is a four.
28/// assert_eq!(buf.recent(), Some(&4));
29///
30/// // To access all elements in an unspecified order, use `as_slice()`.
31/// for el in buf.as_slice() { println!("{:?}", el); }
32///
33/// // Now we can prepare an average of all values, which comes out to 4.
34/// let avg = buf.as_slice().iter().sum::<usize>() / buf.len();
35/// assert_eq!(avg, 4);
36/// ```
37pub struct HistoryBuffer<T, const N: usize> {
38    data: [MaybeUninit<T>; N],
39    write_at: usize,
40    filled: bool,
41}
42
43impl<T, const N: usize> HistoryBuffer<T, N> {
44    const INIT: MaybeUninit<T> = MaybeUninit::uninit();
45
46    /// Constructs a new history buffer.
47    ///
48    /// The construction of a `HistoryBuffer` works in `const` contexts.
49    ///
50    /// # Examples
51    ///
52    /// ```
53    /// use heapless::HistoryBuffer;
54    ///
55    /// // Allocate a 16-element buffer on the stack
56    /// let x: HistoryBuffer<u8, 16> = HistoryBuffer::new();
57    /// assert_eq!(x.len(), 0);
58    /// ```
59    #[inline]
60    pub const fn new() -> Self {
61        // Const assert
62        crate::sealed::greater_than_0::<N>();
63
64        Self {
65            data: [Self::INIT; N],
66            write_at: 0,
67            filled: false,
68        }
69    }
70
71    /// Clears the buffer, replacing every element with the default value of
72    /// type `T`.
73    pub fn clear(&mut self) {
74        *self = Self::new();
75    }
76}
77
78impl<T, const N: usize> HistoryBuffer<T, N>
79where
80    T: Copy + Clone,
81{
82    /// Constructs a new history buffer, where every element is the given value.
83    ///
84    /// # Examples
85    ///
86    /// ```
87    /// use heapless::HistoryBuffer;
88    ///
89    /// // Allocate a 16-element buffer on the stack
90    /// let mut x: HistoryBuffer<u8, 16> = HistoryBuffer::new_with(4);
91    /// // All elements are four
92    /// assert_eq!(x.as_slice(), [4; 16]);
93    /// ```
94    #[inline]
95    pub fn new_with(t: T) -> Self {
96        Self {
97            data: [MaybeUninit::new(t); N],
98            write_at: 0,
99            filled: true,
100        }
101    }
102
103    /// Clears the buffer, replacing every element with the given value.
104    pub fn clear_with(&mut self, t: T) {
105        *self = Self::new_with(t);
106    }
107}
108
109impl<T, const N: usize> HistoryBuffer<T, N> {
110    /// Returns the current fill level of the buffer.
111    #[inline]
112    pub fn len(&self) -> usize {
113        if self.filled {
114            N
115        } else {
116            self.write_at
117        }
118    }
119
120    /// Returns the capacity of the buffer, which is the length of the
121    /// underlying backing array.
122    #[inline]
123    pub fn capacity(&self) -> usize {
124        N
125    }
126
127    /// Writes an element to the buffer, overwriting the oldest value.
128    pub fn write(&mut self, t: T) {
129        if self.filled {
130            // Drop the old before we overwrite it.
131            unsafe { ptr::drop_in_place(self.data[self.write_at].as_mut_ptr()) }
132        }
133        self.data[self.write_at] = MaybeUninit::new(t);
134
135        self.write_at += 1;
136        if self.write_at == self.capacity() {
137            self.write_at = 0;
138            self.filled = true;
139        }
140    }
141
142    /// Clones and writes all elements in a slice to the buffer.
143    ///
144    /// If the slice is longer than the buffer, only the last `self.len()`
145    /// elements will actually be stored.
146    pub fn extend_from_slice(&mut self, other: &[T])
147    where
148        T: Clone,
149    {
150        for item in other {
151            self.write(item.clone());
152        }
153    }
154
155    /// Returns a reference to the most recently written value.
156    ///
157    /// # Examples
158    ///
159    /// ```
160    /// use heapless::HistoryBuffer;
161    ///
162    /// let mut x: HistoryBuffer<u8, 16> = HistoryBuffer::new();
163    /// x.write(4);
164    /// x.write(10);
165    /// assert_eq!(x.recent(), Some(&10));
166    /// ```
167    pub fn recent(&self) -> Option<&T> {
168        if self.write_at == 0 {
169            if self.filled {
170                Some(unsafe { &*self.data[self.capacity() - 1].as_ptr() })
171            } else {
172                None
173            }
174        } else {
175            Some(unsafe { &*self.data[self.write_at - 1].as_ptr() })
176        }
177    }
178
179    /// Returns the array slice backing the buffer, without keeping track
180    /// of the write position. Therefore, the element order is unspecified.
181    pub fn as_slice(&self) -> &[T] {
182        unsafe { slice::from_raw_parts(self.data.as_ptr() as *const _, self.len()) }
183    }
184
185    /// Returns an iterator for iterating over the buffer from oldest to newest.
186    ///
187    /// # Examples
188    ///
189    /// ```
190    /// use heapless::HistoryBuffer;
191    ///
192    /// let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
193    /// buffer.extend([0, 0, 0, 1, 2, 3, 4, 5, 6]);
194    /// let expected = [1, 2, 3, 4, 5, 6];
195    /// for (x, y) in buffer.oldest_ordered().zip(expected.iter()) {
196    ///     assert_eq!(x, y)
197    /// }
198    ///
199    /// ```
200    pub fn oldest_ordered<'a>(&'a self) -> OldestOrdered<'a, T, N> {
201        if self.filled {
202            OldestOrdered {
203                buf: self,
204                cur: self.write_at,
205                wrapped: false,
206            }
207        } else {
208            // special case: act like we wrapped already to handle empty buffer.
209            OldestOrdered {
210                buf: self,
211                cur: 0,
212                wrapped: true,
213            }
214        }
215    }
216}
217
218impl<T, const N: usize> Extend<T> for HistoryBuffer<T, N> {
219    fn extend<I>(&mut self, iter: I)
220    where
221        I: IntoIterator<Item = T>,
222    {
223        for item in iter.into_iter() {
224            self.write(item);
225        }
226    }
227}
228
229impl<'a, T, const N: usize> Extend<&'a T> for HistoryBuffer<T, N>
230where
231    T: 'a + Clone,
232{
233    fn extend<I>(&mut self, iter: I)
234    where
235        I: IntoIterator<Item = &'a T>,
236    {
237        self.extend(iter.into_iter().cloned())
238    }
239}
240
241impl<T, const N: usize> Drop for HistoryBuffer<T, N> {
242    fn drop(&mut self) {
243        unsafe {
244            ptr::drop_in_place(ptr::slice_from_raw_parts_mut(
245                self.data.as_mut_ptr() as *mut T,
246                self.len(),
247            ))
248        }
249    }
250}
251
252impl<T, const N: usize> Deref for HistoryBuffer<T, N> {
253    type Target = [T];
254
255    fn deref(&self) -> &[T] {
256        self.as_slice()
257    }
258}
259
260impl<T, const N: usize> AsRef<[T]> for HistoryBuffer<T, N> {
261    #[inline]
262    fn as_ref(&self) -> &[T] {
263        self
264    }
265}
266
267impl<T, const N: usize> fmt::Debug for HistoryBuffer<T, N>
268where
269    T: fmt::Debug,
270{
271    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
272        <[T] as fmt::Debug>::fmt(self, f)
273    }
274}
275
276impl<T, const N: usize> Default for HistoryBuffer<T, N> {
277    fn default() -> Self {
278        Self::new()
279    }
280}
281
282/// An iterator on the underlying buffer ordered from oldest data to newest
283#[derive(Clone)]
284pub struct OldestOrdered<'a, T, const N: usize> {
285    buf: &'a HistoryBuffer<T, N>,
286    cur: usize,
287    wrapped: bool,
288}
289
290impl<'a, T, const N: usize> Iterator for OldestOrdered<'a, T, N> {
291    type Item = &'a T;
292
293    fn next(&mut self) -> Option<&'a T> {
294        if self.cur == self.buf.len() && self.buf.filled {
295            // roll-over
296            self.cur = 0;
297            self.wrapped = true;
298        }
299
300        if self.cur == self.buf.write_at && self.wrapped {
301            return None;
302        }
303
304        let item = &self.buf[self.cur];
305        self.cur += 1;
306        Some(item)
307    }
308}
309
310#[cfg(test)]
311mod tests {
312    use crate::HistoryBuffer;
313    use core::fmt::Debug;
314
315    #[test]
316    fn new() {
317        let x: HistoryBuffer<u8, 4> = HistoryBuffer::new_with(1);
318        assert_eq!(x.len(), 4);
319        assert_eq!(x.as_slice(), [1; 4]);
320        assert_eq!(*x, [1; 4]);
321
322        let x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
323        assert_eq!(x.as_slice(), []);
324    }
325
326    #[test]
327    fn write() {
328        let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
329        x.write(1);
330        x.write(4);
331        assert_eq!(x.as_slice(), [1, 4]);
332
333        x.write(5);
334        x.write(6);
335        x.write(10);
336        assert_eq!(x.as_slice(), [10, 4, 5, 6]);
337
338        x.extend([11, 12].iter());
339        assert_eq!(x.as_slice(), [10, 11, 12, 6]);
340    }
341
342    #[test]
343    fn clear() {
344        let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new_with(1);
345        x.clear();
346        assert_eq!(x.as_slice(), []);
347
348        let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
349        x.clear_with(1);
350        assert_eq!(x.as_slice(), [1; 4]);
351    }
352
353    #[test]
354    fn recent() {
355        let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
356        assert_eq!(x.recent(), None);
357
358        x.write(1);
359        x.write(4);
360        assert_eq!(x.recent(), Some(&4));
361
362        x.write(5);
363        x.write(6);
364        x.write(10);
365        assert_eq!(x.recent(), Some(&10));
366    }
367
368    #[test]
369    fn as_slice() {
370        let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
371
372        assert_eq!(x.as_slice(), []);
373
374        x.extend([1, 2, 3, 4, 5].iter());
375
376        assert_eq!(x.as_slice(), [5, 2, 3, 4]);
377    }
378
379    #[test]
380    fn ordered() {
381        // test on an empty buffer
382        let buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
383        let mut iter = buffer.oldest_ordered();
384        assert_eq!(iter.next(), None);
385        assert_eq!(iter.next(), None);
386
387        // test on a un-filled buffer
388        let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
389        buffer.extend([1, 2, 3]);
390        assert_eq!(buffer.len(), 3);
391        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3]);
392
393        // test on a filled buffer
394        let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
395        buffer.extend([0, 0, 0, 1, 2, 3, 4, 5, 6]);
396        assert_eq!(buffer.len(), 6);
397        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3, 4, 5, 6]);
398
399        // comprehensive test all cases
400        for n in 0..50 {
401            const N: usize = 7;
402            let mut buffer: HistoryBuffer<u8, N> = HistoryBuffer::new();
403            buffer.extend(0..n);
404            assert_eq_iter(
405                buffer.oldest_ordered().copied(),
406                n.saturating_sub(N as u8)..n,
407            );
408        }
409    }
410
411    /// Compares two iterators item by item, making sure they stop at the same time.
412    fn assert_eq_iter<I: Eq + Debug>(
413        a: impl IntoIterator<Item = I>,
414        b: impl IntoIterator<Item = I>,
415    ) {
416        let mut a = a.into_iter();
417        let mut b = b.into_iter();
418
419        let mut i = 0;
420        loop {
421            let a_item = a.next();
422            let b_item = b.next();
423
424            assert_eq!(a_item, b_item, "{}", i);
425
426            i += 1;
427
428            if b_item.is_none() {
429                break;
430            }
431        }
432    }
433}
heapless/histbuf.rs

heapless/
histbuf.rs
