heapless/
histbuf.rs

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 a pair of slices which contain, in order, the contents of the buffer.
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]);
194    /// buffer.extend([1, 2, 3, 4, 5, 6]);
195    /// assert_eq!(buffer.as_slices(), (&[1, 2, 3][..], &[4, 5, 6][..]));
196    /// ```
197    pub fn as_slices(&self) -> (&[T], &[T]) {
198        let buffer = self.as_slice();
199
200        if !self.filled {
201            (buffer, &[])
202        } else {
203            (&buffer[self.write_at..], &buffer[..self.write_at])
204        }
205    }
206
207    /// Returns an iterator for iterating over the buffer from oldest to newest.
208    ///
209    /// # Examples
210    ///
211    /// ```
212    /// use heapless::HistoryBuffer;
213    ///
214    /// let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
215    /// buffer.extend([0, 0, 0, 1, 2, 3, 4, 5, 6]);
216    /// let expected = [1, 2, 3, 4, 5, 6];
217    /// for (x, y) in buffer.oldest_ordered().zip(expected.iter()) {
218    ///     assert_eq!(x, y)
219    /// }
220    ///
221    /// ```
222    pub fn oldest_ordered<'a>(&'a self) -> OldestOrdered<'a, T, N> {
223        if self.filled {
224            OldestOrdered {
225                buf: self,
226                cur: self.write_at,
227                wrapped: false,
228            }
229        } else {
230            // special case: act like we wrapped already to handle empty buffer.
231            OldestOrdered {
232                buf: self,
233                cur: 0,
234                wrapped: true,
235            }
236        }
237    }
238}
239
240impl<T, const N: usize> Extend<T> for HistoryBuffer<T, N> {
241    fn extend<I>(&mut self, iter: I)
242    where
243        I: IntoIterator<Item = T>,
244    {
245        for item in iter.into_iter() {
246            self.write(item);
247        }
248    }
249}
250
251impl<'a, T, const N: usize> Extend<&'a T> for HistoryBuffer<T, N>
252where
253    T: 'a + Clone,
254{
255    fn extend<I>(&mut self, iter: I)
256    where
257        I: IntoIterator<Item = &'a T>,
258    {
259        self.extend(iter.into_iter().cloned())
260    }
261}
262
263impl<T, const N: usize> Clone for HistoryBuffer<T, N>
264where
265    T: Clone,
266{
267    fn clone(&self) -> Self {
268        let mut ret = Self::new();
269        for (new, old) in ret.data.iter_mut().zip(self.as_slice()) {
270            new.write(old.clone());
271        }
272        ret.filled = self.filled;
273        ret.write_at = self.write_at;
274        ret
275    }
276}
277
278impl<T, const N: usize> Drop for HistoryBuffer<T, N> {
279    fn drop(&mut self) {
280        unsafe {
281            ptr::drop_in_place(ptr::slice_from_raw_parts_mut(
282                self.data.as_mut_ptr() as *mut T,
283                self.len(),
284            ))
285        }
286    }
287}
288
289impl<T, const N: usize> Deref for HistoryBuffer<T, N> {
290    type Target = [T];
291
292    fn deref(&self) -> &[T] {
293        self.as_slice()
294    }
295}
296
297impl<T, const N: usize> AsRef<[T]> for HistoryBuffer<T, N> {
298    #[inline]
299    fn as_ref(&self) -> &[T] {
300        self
301    }
302}
303
304impl<T, const N: usize> fmt::Debug for HistoryBuffer<T, N>
305where
306    T: fmt::Debug,
307{
308    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
309        <[T] as fmt::Debug>::fmt(self, f)
310    }
311}
312
313impl<T, const N: usize> Default for HistoryBuffer<T, N> {
314    fn default() -> Self {
315        Self::new()
316    }
317}
318
319impl<T, const N: usize> PartialEq for HistoryBuffer<T, N>
320where
321    T: PartialEq,
322{
323    fn eq(&self, other: &Self) -> bool {
324        self.oldest_ordered().eq(other.oldest_ordered())
325    }
326}
327
328/// An iterator on the underlying buffer ordered from oldest data to newest
329#[derive(Clone)]
330pub struct OldestOrdered<'a, T, const N: usize> {
331    buf: &'a HistoryBuffer<T, N>,
332    cur: usize,
333    wrapped: bool,
334}
335
336impl<'a, T, const N: usize> Iterator for OldestOrdered<'a, T, N> {
337    type Item = &'a T;
338
339    fn next(&mut self) -> Option<&'a T> {
340        if self.cur == self.buf.len() && self.buf.filled {
341            // roll-over
342            self.cur = 0;
343            self.wrapped = true;
344        }
345
346        if self.cur == self.buf.write_at && self.wrapped {
347            return None;
348        }
349
350        let item = &self.buf[self.cur];
351        self.cur += 1;
352        Some(item)
353    }
354}
355
356#[cfg(test)]
357mod tests {
358    use crate::HistoryBuffer;
359    use core::fmt::Debug;
360    use core::sync::atomic::{AtomicUsize, Ordering};
361
362    #[test]
363    fn new() {
364        let x: HistoryBuffer<u8, 4> = HistoryBuffer::new_with(1);
365        assert_eq!(x.len(), 4);
366        assert_eq!(x.as_slice(), [1; 4]);
367        assert_eq!(*x, [1; 4]);
368
369        let x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
370        assert_eq!(x.as_slice(), []);
371    }
372
373    #[test]
374    fn write() {
375        let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
376        x.write(1);
377        x.write(4);
378        assert_eq!(x.as_slice(), [1, 4]);
379
380        x.write(5);
381        x.write(6);
382        x.write(10);
383        assert_eq!(x.as_slice(), [10, 4, 5, 6]);
384
385        x.extend([11, 12].iter());
386        assert_eq!(x.as_slice(), [10, 11, 12, 6]);
387    }
388
389    #[test]
390    fn clear() {
391        let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new_with(1);
392        x.clear();
393        assert_eq!(x.as_slice(), []);
394
395        let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
396        x.clear_with(1);
397        assert_eq!(x.as_slice(), [1; 4]);
398    }
399
400    #[test]
401    fn clone() {
402        let mut x: HistoryBuffer<u8, 3> = HistoryBuffer::new();
403        for i in 0..10 {
404            assert_eq!(x.as_slice(), x.clone().as_slice());
405            x.write(i);
406        }
407
408        // Records number of clones locally and globally.
409        static GLOBAL: AtomicUsize = AtomicUsize::new(0);
410        #[derive(Default, PartialEq, Debug)]
411        struct InstrumentedClone(usize);
412
413        impl Clone for InstrumentedClone {
414            fn clone(&self) -> Self {
415                GLOBAL.fetch_add(1, Ordering::Relaxed);
416                Self(self.0 + 1)
417            }
418        }
419
420        let mut y: HistoryBuffer<InstrumentedClone, 2> = HistoryBuffer::new();
421        let _ = y.clone();
422        assert_eq!(GLOBAL.load(Ordering::Relaxed), 0);
423        y.write(InstrumentedClone(0));
424        assert_eq!(GLOBAL.load(Ordering::Relaxed), 0);
425        assert_eq!(y.clone().as_slice(), [InstrumentedClone(1)]);
426        assert_eq!(GLOBAL.load(Ordering::Relaxed), 1);
427        y.write(InstrumentedClone(0));
428        assert_eq!(GLOBAL.load(Ordering::Relaxed), 1);
429        assert_eq!(
430            y.clone().as_slice(),
431            [InstrumentedClone(1), InstrumentedClone(1)]
432        );
433        assert_eq!(GLOBAL.load(Ordering::Relaxed), 3);
434        assert_eq!(
435            y.clone().clone().clone().as_slice(),
436            [InstrumentedClone(3), InstrumentedClone(3)]
437        );
438        assert_eq!(GLOBAL.load(Ordering::Relaxed), 9);
439    }
440
441    #[test]
442    fn recent() {
443        let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
444        assert_eq!(x.recent(), None);
445
446        x.write(1);
447        x.write(4);
448        assert_eq!(x.recent(), Some(&4));
449
450        x.write(5);
451        x.write(6);
452        x.write(10);
453        assert_eq!(x.recent(), Some(&10));
454    }
455
456    #[test]
457    fn as_slice() {
458        let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
459
460        assert_eq!(x.as_slice(), []);
461
462        x.extend([1, 2, 3, 4, 5].iter());
463
464        assert_eq!(x.as_slice(), [5, 2, 3, 4]);
465    }
466
467    /// Test whether .as_slices() behaves as expected.
468    #[test]
469    fn as_slices() {
470        let mut buffer: HistoryBuffer<u8, 4> = HistoryBuffer::new();
471        let mut extend_then_assert = |extend: &[u8], assert: (&[u8], &[u8])| {
472            buffer.extend(extend);
473            assert_eq!(buffer.as_slices(), assert);
474        };
475
476        extend_then_assert(b"a", (b"a", b""));
477        extend_then_assert(b"bcd", (b"abcd", b""));
478        extend_then_assert(b"efg", (b"d", b"efg"));
479        extend_then_assert(b"h", (b"efgh", b""));
480        extend_then_assert(b"123456", (b"34", b"56"));
481    }
482
483    /// Test whether .as_slices() and .oldest_ordered() produce elements in the same order.
484    #[test]
485    fn as_slices_equals_ordered() {
486        let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
487
488        for n in 0..20 {
489            buffer.write(n);
490            let (head, tail) = buffer.as_slices();
491            assert_eq_iter(
492                [head, tail].iter().copied().flatten(),
493                buffer.oldest_ordered(),
494            )
495        }
496    }
497
498    #[test]
499    fn ordered() {
500        // test on an empty buffer
501        let buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
502        let mut iter = buffer.oldest_ordered();
503        assert_eq!(iter.next(), None);
504        assert_eq!(iter.next(), None);
505
506        // test on a un-filled buffer
507        let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
508        buffer.extend([1, 2, 3]);
509        assert_eq!(buffer.len(), 3);
510        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3]);
511
512        // test on a filled buffer
513        let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
514        buffer.extend([0, 0, 0, 1, 2, 3, 4, 5, 6]);
515        assert_eq!(buffer.len(), 6);
516        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3, 4, 5, 6]);
517
518        // comprehensive test all cases
519        for n in 0..50 {
520            const N: usize = 7;
521            let mut buffer: HistoryBuffer<u8, N> = HistoryBuffer::new();
522            buffer.extend(0..n);
523            assert_eq_iter(
524                buffer.oldest_ordered().copied(),
525                n.saturating_sub(N as u8)..n,
526            );
527        }
528    }
529
530    /// Compares two iterators item by item, making sure they stop at the same time.
531    fn assert_eq_iter<I: Eq + Debug>(
532        a: impl IntoIterator<Item = I>,
533        b: impl IntoIterator<Item = I>,
534    ) {
535        let mut a = a.into_iter();
536        let mut b = b.into_iter();
537
538        let mut i = 0;
539        loop {
540            let a_item = a.next();
541            let b_item = b.next();
542
543            assert_eq!(a_item, b_item, "{}", i);
544
545            i += 1;
546
547            if b_item.is_none() {
548                break;
549            }
550        }
551    }
552
553    #[test]
554    fn partial_eq() {
555        let mut x: HistoryBuffer<u8, 3> = HistoryBuffer::new();
556        let mut y: HistoryBuffer<u8, 3> = HistoryBuffer::new();
557        assert_eq!(x, y);
558        x.write(1);
559        assert_ne!(x, y);
560        y.write(1);
561        assert_eq!(x, y);
562        for _ in 0..4 {
563            x.write(2);
564            assert_ne!(x, y);
565            for i in 0..5 {
566                x.write(i);
567                y.write(i);
568            }
569            assert_eq!(
570                x,
571                y,
572                "{:?} {:?}",
573                x.iter().collect::<Vec<_>>(),
574                y.iter().collect::<Vec<_>>()
575            );
576        }
577    }
578}
heapless/histbuf.rs

heapless/
histbuf.rs
