heapless/
history_buf.rs

1//! A "history buffer", similar to a write-only ring buffer of fixed length.
2//!
3//! This buffer keeps a fixed number of elements.  On write, the oldest element
4//! is overwritten. Thus, the buffer is useful to keep a history of values with
5//! some desired depth, and for example calculate a rolling average.
6//!
7//! # Examples
8//! ```
9//! use heapless::HistoryBuf;
10//!
11//! // Initialize a new buffer with 8 elements.
12//! let mut buf = HistoryBuf::<_, 8>::new();
13//!
14//! // Starts with no data
15//! assert_eq!(buf.recent(), None);
16//!
17//! buf.write(3);
18//! buf.write(5);
19//! buf.extend(&[4, 4]);
20//!
21//! // The most recent written element is a four.
22//! assert_eq!(buf.recent(), Some(&4));
23//!
24//! // To access all elements in an unspecified order, use `as_slice()`.
25//! for el in buf.as_slice() {
26//!     println!("{:?}", el);
27//! }
28//!
29//! // Now we can prepare an average of all values, which comes out to 4.
30//! let avg = buf.as_slice().iter().sum::<usize>() / buf.len();
31//! assert_eq!(avg, 4);
32//! ```
33
34use core::{fmt, marker::PhantomData, mem::MaybeUninit, ops::Deref, ptr, slice};
35
36#[cfg(feature = "zeroize")]
37use zeroize::Zeroize;
38
39mod storage {
40    use super::{HistoryBufInner, HistoryBufView};
41    use core::mem::MaybeUninit;
42    #[cfg(feature = "zeroize")]
43    use zeroize::Zeroize;
44
45    /// Trait defining how data for a container is stored.
46    ///
47    /// There's two implementations available:
48    ///
49    /// - [`OwnedHistoryBufStorage`]: stores the data in an array `[T; N]` whose size is known at
50    ///   compile time.
51    /// - [`ViewHistoryBufStorage`]: stores the data in an unsized `[T]`.
52    ///
53    /// This allows [`HistoryBuf`] to be generic over either sized or unsized storage. The
54    /// [`histbuf`] module contains a [`HistoryBufInner`] struct that's generic on
55    /// [`HistoryBufStorage`], and two type aliases for convenience:
56    ///
57    /// - [`HistoryBuf<T, N>`](super::HistoryBuf) = `HistoryBufInner<T, OwnedHistoryBufStorage<T,
58    ///   N>>`
59    /// - [`HistoryBufView<T>`](super::HistoryBufView) = `HistoryBufInner<T,
60    ///   ViewHistoryBufStorage<T>>`
61    ///
62    /// `HistoryBuf` can be unsized into `HistoryBufView`, either by unsizing coercions such as
63    /// `&mut HistoryBuf -> &mut HistoryBufView` or `Box<HistoryBuf> -> Box<HistoryBufView>`, or
64    /// explicitly with [`.as_view()`](super::HistoryBuf::as_view) or
65    /// [`.as_mut_view()`](super::HistoryBuf::as_mut_view).
66    ///
67    /// This trait is sealed, so you cannot implement it for your own types. You can only use
68    /// the implementations provided by this crate.
69    ///
70    /// [`HistoryBufInner`]: super::HistoryBufInner
71    /// [`HistoryBuf`]: super::HistoryBuf
72    /// [`HistoryBufView`]: super::HistoryBufView
73    /// [`histbuf`]: super
74    #[allow(private_bounds)]
75    pub trait HistoryBufStorage<T>: HistoryBufSealedStorage<T> {}
76
77    pub trait HistoryBufSealedStorage<T> {
78        // part of the sealed trait so that no trait is publicly implemented by
79        // `OwnedHistoryBufStorage` besides `Storage`
80        fn borrow(&self) -> &[MaybeUninit<T>];
81        fn borrow_mut(&mut self) -> &mut [MaybeUninit<T>];
82        fn as_hist_buf_view(this: &HistoryBufInner<T, Self>) -> &HistoryBufView<T>
83        where
84            Self: HistoryBufStorage<T>;
85        fn as_hist_buf_mut_view(this: &mut HistoryBufInner<T, Self>) -> &mut HistoryBufView<T>
86        where
87            Self: HistoryBufStorage<T>;
88    }
89
90    // One sealed layer of indirection to hide the internal details (The MaybeUninit).
91    #[cfg_attr(feature = "zeroize", derive(Zeroize))]
92    pub struct HistoryBufStorageInner<T: ?Sized> {
93        pub(crate) buffer: T,
94    }
95
96    /// Implementation of [`HistoryBufStorage`] that stores the data in an array `[T; N]` whose size
97    /// is known at compile time.
98    pub type OwnedHistoryBufStorage<T, const N: usize> =
99        HistoryBufStorageInner<[MaybeUninit<T>; N]>;
100    /// Implementation of [`HistoryBufStorage`] that stores the data in an unsized `[T]`.
101    pub type ViewHistoryBufStorage<T> = HistoryBufStorageInner<[MaybeUninit<T>]>;
102
103    impl<T, const N: usize> HistoryBufSealedStorage<T> for OwnedHistoryBufStorage<T, N> {
104        fn borrow(&self) -> &[MaybeUninit<T>] {
105            &self.buffer
106        }
107        fn borrow_mut(&mut self) -> &mut [MaybeUninit<T>] {
108            &mut self.buffer
109        }
110        fn as_hist_buf_view(this: &HistoryBufInner<T, Self>) -> &HistoryBufView<T>
111        where
112            Self: HistoryBufStorage<T>,
113        {
114            this
115        }
116        fn as_hist_buf_mut_view(this: &mut HistoryBufInner<T, Self>) -> &mut HistoryBufView<T>
117        where
118            Self: HistoryBufStorage<T>,
119        {
120            this
121        }
122    }
123    impl<T, const N: usize> HistoryBufStorage<T> for OwnedHistoryBufStorage<T, N> {}
124
125    impl<T> HistoryBufSealedStorage<T> for ViewHistoryBufStorage<T> {
126        fn borrow(&self) -> &[MaybeUninit<T>] {
127            &self.buffer
128        }
129        fn borrow_mut(&mut self) -> &mut [MaybeUninit<T>] {
130            &mut self.buffer
131        }
132        fn as_hist_buf_view(this: &HistoryBufInner<T, Self>) -> &HistoryBufView<T>
133        where
134            Self: HistoryBufStorage<T>,
135        {
136            this
137        }
138        fn as_hist_buf_mut_view(this: &mut HistoryBufInner<T, Self>) -> &mut HistoryBufView<T>
139        where
140            Self: HistoryBufStorage<T>,
141        {
142            this
143        }
144    }
145    impl<T> HistoryBufStorage<T> for ViewHistoryBufStorage<T> {}
146}
147
148pub use storage::{HistoryBufStorage, OwnedHistoryBufStorage, ViewHistoryBufStorage};
149
150use storage::HistoryBufStorageInner;
151
152use self::storage::HistoryBufSealedStorage;
153
154/// Base struct for [`HistoryBuf`] and [`HistoryBufView`], generic over the [`HistoryBufStorage`].
155///
156/// In most cases you should use [`HistoryBuf`] or [`HistoryBufView`] directly. Only use this
157/// struct if you want to write code that's generic over both.
158#[cfg_attr(feature = "zeroize", derive(Zeroize))]
159pub struct HistoryBufInner<T, S: HistoryBufStorage<T> + ?Sized> {
160    // This phantomdata is required because otherwise rustc thinks that `T` is not used
161    phantom: PhantomData<T>,
162    write_at: usize,
163    filled: bool,
164    data: S,
165}
166
167/// A "history buffer", similar to a write-only ring buffer of fixed length.
168///
169/// This buffer keeps a fixed number of elements.  On write, the oldest element
170/// is overwritten. Thus, the buffer is useful to keep a history of values with
171/// some desired depth, and for example calculate a rolling average.
172///
173/// # Examples
174/// ```
175/// use heapless::HistoryBuf;
176///
177/// // Initialize a new buffer with 8 elements.
178/// let mut buf = HistoryBuf::<_, 8>::new();
179///
180/// // Starts with no data
181/// assert_eq!(buf.recent(), None);
182///
183/// buf.write(3);
184/// buf.write(5);
185/// buf.extend(&[4, 4]);
186///
187/// // The most recent written element is a four.
188/// assert_eq!(buf.recent(), Some(&4));
189///
190/// // To access all elements in an unspecified order, use `as_slice()`.
191/// for el in buf.as_slice() {
192///     println!("{:?}", el);
193/// }
194///
195/// // Now we can prepare an average of all values, which comes out to 4.
196/// let avg = buf.as_slice().iter().sum::<usize>() / buf.len();
197/// assert_eq!(avg, 4);
198/// ```
199pub type HistoryBuf<T, const N: usize> = HistoryBufInner<T, OwnedHistoryBufStorage<T, N>>;
200
201/// A "view" into a [`HistoryBuf`]
202///
203/// Unlike [`HistoryBuf`], it doesn't have the `const N: usize` in its type signature.
204///
205/// # Examples
206/// ```
207/// use heapless::history_buf::{HistoryBuf, HistoryBufView};
208///
209/// // Initialize a new buffer with 8 elements.
210/// let mut owned_buf = HistoryBuf::<_, 8>::new();
211/// let buf: &mut HistoryBufView<_> = &mut owned_buf;
212///
213/// // Starts with no data
214/// assert_eq!(buf.recent(), None);
215///
216/// buf.write(3);
217/// buf.write(5);
218/// buf.extend(&[4, 4]);
219///
220/// // The most recent written element is a four.
221/// assert_eq!(buf.recent(), Some(&4));
222///
223/// // To access all elements in an unspecified order, use `as_slice()`.
224/// for el in buf.as_slice() {
225///     println!("{:?}", el);
226/// }
227///
228/// // Now we can prepare an average of all values, which comes out to 4.
229/// let avg = buf.as_slice().iter().sum::<usize>() / buf.len();
230/// assert_eq!(avg, 4);
231/// ```
232pub type HistoryBufView<T> = HistoryBufInner<T, ViewHistoryBufStorage<T>>;
233
234impl<T, const N: usize> HistoryBuf<T, N> {
235    const INIT: MaybeUninit<T> = MaybeUninit::uninit();
236
237    /// Constructs a new history buffer.
238    ///
239    /// The construction of a `HistoryBuf` works in `const` contexts.
240    ///
241    /// # Examples
242    ///
243    /// ```
244    /// use heapless::HistoryBuf;
245    ///
246    /// // Allocate a 16-element buffer on the stack
247    /// let x: HistoryBuf<u8, 16> = HistoryBuf::new();
248    /// assert_eq!(x.len(), 0);
249    /// ```
250    #[inline]
251    pub const fn new() -> Self {
252        const {
253            assert!(N > 0);
254        }
255
256        Self {
257            phantom: PhantomData,
258            data: HistoryBufStorageInner {
259                buffer: [Self::INIT; N],
260            },
261            write_at: 0,
262            filled: false,
263        }
264    }
265}
266
267impl<T, const N: usize> HistoryBuf<T, N>
268where
269    T: Copy + Clone,
270{
271    /// Constructs a new history buffer, where every element is the given value.
272    ///
273    /// # Examples
274    ///
275    /// ```
276    /// use heapless::HistoryBuf;
277    ///
278    /// // Allocate a 16-element buffer on the stack
279    /// let mut x: HistoryBuf<u8, 16> = HistoryBuf::new_with(4);
280    /// // All elements are four
281    /// assert_eq!(x.as_slice(), [4; 16]);
282    /// ```
283    #[inline]
284    pub fn new_with(t: T) -> Self {
285        Self {
286            phantom: PhantomData,
287            data: HistoryBufStorageInner {
288                buffer: [MaybeUninit::new(t); N],
289            },
290            write_at: 0,
291            filled: true,
292        }
293    }
294}
295
296impl<T: Copy, S: HistoryBufStorage<T> + ?Sized> HistoryBufInner<T, S> {
297    /// Get a reference to the `HistoryBuf`, erasing the `N` const-generic.
298    #[inline]
299    pub fn as_view(&self) -> &HistoryBufView<T> {
300        S::as_hist_buf_view(self)
301    }
302
303    /// Get a mutable reference to the `HistoryBuf`, erasing the `N` const-generic.
304    #[inline]
305    pub fn as_mut_view(&mut self) -> &mut HistoryBufView<T> {
306        S::as_hist_buf_mut_view(self)
307    }
308
309    /// Clears the buffer, replacing every element with the given value.
310    pub fn clear_with(&mut self, t: T) {
311        // SAFETY: we reset the values just after
312        unsafe { self.drop_contents() };
313        self.write_at = 0;
314        self.filled = true;
315
316        for d in self.data.borrow_mut() {
317            *d = MaybeUninit::new(t);
318        }
319    }
320}
321
322impl<T, S: HistoryBufStorage<T> + ?Sized> HistoryBufInner<T, S> {
323    /// Clears the buffer
324    pub fn clear(&mut self) {
325        // SAFETY: we reset the values just after
326        unsafe { self.drop_contents() };
327        self.write_at = 0;
328        self.filled = false;
329    }
330}
331
332impl<T, S: HistoryBufStorage<T> + ?Sized> HistoryBufInner<T, S> {
333    unsafe fn drop_contents(&mut self) {
334        unsafe {
335            ptr::drop_in_place(ptr::slice_from_raw_parts_mut(
336                self.data.borrow_mut().as_mut_ptr().cast::<T>(),
337                self.len(),
338            ));
339        }
340    }
341
342    /// Returns the current fill level of the buffer.
343    #[inline]
344    pub fn len(&self) -> usize {
345        if self.filled {
346            self.capacity()
347        } else {
348            self.write_at
349        }
350    }
351
352    /// Returns true if the buffer is empty.
353    ///
354    /// # Examples
355    ///
356    /// ```
357    /// use heapless::HistoryBuf;
358    ///
359    /// let x: HistoryBuf<u8, 16> = HistoryBuf::new();
360    /// assert!(x.is_empty());
361    /// ```
362    #[inline]
363    pub fn is_empty(&self) -> bool {
364        self.len() == 0
365    }
366
367    /// Returns the capacity of the buffer, which is the length of the
368    /// underlying backing array.
369    #[inline]
370    pub fn capacity(&self) -> usize {
371        self.data.borrow().len()
372    }
373
374    /// Returns whether the buffer is full
375    #[inline]
376    pub fn is_full(&self) -> bool {
377        self.filled
378    }
379
380    /// Writes an element to the buffer, overwriting the oldest value.
381    pub fn write(&mut self, t: T) {
382        if self.filled {
383            // Drop the old before we overwrite it.
384            unsafe { ptr::drop_in_place(self.data.borrow_mut()[self.write_at].as_mut_ptr()) }
385        }
386        self.data.borrow_mut()[self.write_at] = MaybeUninit::new(t);
387
388        self.write_at += 1;
389        if self.write_at == self.capacity() {
390            self.write_at = 0;
391            self.filled = true;
392        }
393    }
394
395    /// Clones and writes all elements in a slice to the buffer.
396    ///
397    /// If the slice is longer than the buffer, only the last `self.len()`
398    /// elements will actually be stored.
399    pub fn extend_from_slice(&mut self, other: &[T])
400    where
401        T: Clone,
402    {
403        for item in other {
404            self.write(item.clone());
405        }
406    }
407
408    /// Returns a reference to the most recently written value.
409    ///
410    /// # Examples
411    ///
412    /// ```
413    /// use heapless::HistoryBuf;
414    ///
415    /// let mut x: HistoryBuf<u8, 16> = HistoryBuf::new();
416    /// x.write(4);
417    /// x.write(10);
418    /// assert_eq!(x.recent(), Some(&10));
419    /// ```
420    pub fn recent(&self) -> Option<&T> {
421        self.recent_index()
422            .map(|i| unsafe { &*self.data.borrow()[i].as_ptr() })
423    }
424
425    /// Returns index of the most recently written value in the underlying slice.
426    ///
427    /// # Examples
428    ///
429    /// ```
430    /// use heapless::HistoryBuf;
431    ///
432    /// let mut x: HistoryBuf<u8, 16> = HistoryBuf::new();
433    /// x.write(4);
434    /// x.write(10);
435    /// assert_eq!(x.recent_index(), Some(1));
436    /// ```
437    pub fn recent_index(&self) -> Option<usize> {
438        if self.write_at == 0 {
439            if self.filled {
440                Some(self.capacity() - 1)
441            } else {
442                None
443            }
444        } else {
445            Some(self.write_at - 1)
446        }
447    }
448
449    /// Returns a reference to the oldest value in the buffer.
450    ///
451    /// # Examples
452    ///
453    /// ```
454    /// use heapless::HistoryBuf;
455    ///
456    /// let mut x: HistoryBuf<u8, 16> = HistoryBuf::new();
457    /// x.write(4);
458    /// x.write(10);
459    /// assert_eq!(x.oldest(), Some(&4));
460    /// ```
461    pub fn oldest(&self) -> Option<&T> {
462        self.oldest_index()
463            .map(|i| unsafe { &*self.data.borrow()[i].as_ptr() })
464    }
465
466    /// Returns index of the oldest value in the underlying slice.
467    ///
468    /// # Examples
469    ///
470    /// ```
471    /// use heapless::HistoryBuf;
472    ///
473    /// let mut x: HistoryBuf<u8, 16> = HistoryBuf::new();
474    /// x.write(4);
475    /// x.write(10);
476    /// assert_eq!(x.oldest_index(), Some(0));
477    /// ```
478    pub fn oldest_index(&self) -> Option<usize> {
479        if self.filled {
480            Some(self.write_at)
481        } else if self.write_at == 0 {
482            None
483        } else {
484            Some(0)
485        }
486    }
487
488    /// Returns the array slice backing the buffer, without keeping track
489    /// of the write position. Therefore, the element order is unspecified.
490    pub fn as_slice(&self) -> &[T] {
491        unsafe { slice::from_raw_parts(self.data.borrow().as_ptr().cast(), self.len()) }
492    }
493
494    /// Returns a pair of slices which contain, in order, the contents of the buffer.
495    ///
496    /// # Examples
497    ///
498    /// ```
499    /// use heapless::HistoryBuf;
500    ///
501    /// let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
502    /// buffer.extend([0, 0, 0]);
503    /// buffer.extend([1, 2, 3, 4, 5, 6]);
504    /// assert_eq!(buffer.as_slices(), (&[1, 2, 3][..], &[4, 5, 6][..]));
505    /// ```
506    pub fn as_slices(&self) -> (&[T], &[T]) {
507        let buffer = self.as_slice();
508
509        if self.filled {
510            (&buffer[self.write_at..], &buffer[..self.write_at])
511        } else {
512            (buffer, &[])
513        }
514    }
515
516    /// Returns double ended iterator for iterating over the buffer from
517    /// the oldest to the newest and back.
518    ///
519    /// # Examples
520    ///
521    /// ```
522    /// use heapless::HistoryBuf;
523    ///
524    /// let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
525    /// buffer.extend([0, 0, 0, 1, 2, 3, 4, 5, 6]);
526    /// let expected = [1, 2, 3, 4, 5, 6];
527    /// for (x, y) in buffer.oldest_ordered().zip(expected.iter()) {
528    ///     assert_eq!(x, y)
529    /// }
530    /// ```
531    pub fn oldest_ordered(&self) -> OldestOrdered<'_, T> {
532        let (old, new) = self.as_slices();
533        OldestOrdered {
534            inner: old.iter().chain(new),
535        }
536    }
537}
538
539impl<T, S: HistoryBufStorage<T> + ?Sized> Extend<T> for HistoryBufInner<T, S> {
540    fn extend<I>(&mut self, iter: I)
541    where
542        I: IntoIterator<Item = T>,
543    {
544        for item in iter.into_iter() {
545            self.write(item);
546        }
547    }
548}
549
550impl<'a, T, S: HistoryBufStorage<T> + ?Sized> Extend<&'a T> for HistoryBufInner<T, S>
551where
552    T: 'a + Clone,
553{
554    fn extend<I>(&mut self, iter: I)
555    where
556        I: IntoIterator<Item = &'a T>,
557    {
558        self.extend(iter.into_iter().cloned());
559    }
560}
561
562impl<T, const N: usize> Clone for HistoryBuf<T, N>
563where
564    T: Clone,
565{
566    fn clone(&self) -> Self {
567        let mut ret = Self::new();
568        for (new, old) in ret.data.borrow_mut().iter_mut().zip(self.as_slice()) {
569            new.write(old.clone());
570        }
571        ret.filled = self.filled;
572        ret.write_at = self.write_at;
573        ret
574    }
575}
576
577impl<T, S: HistoryBufStorage<T> + ?Sized> Drop for HistoryBufInner<T, S> {
578    fn drop(&mut self) {
579        unsafe { self.drop_contents() }
580    }
581}
582
583impl<T, S: HistoryBufStorage<T> + ?Sized> Deref for HistoryBufInner<T, S> {
584    type Target = [T];
585
586    fn deref(&self) -> &[T] {
587        self.as_slice()
588    }
589}
590
591impl<T, S: HistoryBufStorage<T> + ?Sized> AsRef<[T]> for HistoryBufInner<T, S> {
592    #[inline]
593    fn as_ref(&self) -> &[T] {
594        self
595    }
596}
597
598impl<T, S: HistoryBufStorage<T> + ?Sized> fmt::Debug for HistoryBufInner<T, S>
599where
600    T: fmt::Debug,
601{
602    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
603        <[T] as fmt::Debug>::fmt(self, f)
604    }
605}
606
607impl<T, const N: usize> Default for HistoryBuf<T, N> {
608    fn default() -> Self {
609        Self::new()
610    }
611}
612
613impl<T, S: HistoryBufStorage<T> + ?Sized> PartialEq for HistoryBufInner<T, S>
614where
615    T: PartialEq,
616{
617    fn eq(&self, other: &Self) -> bool {
618        self.oldest_ordered().eq(other.oldest_ordered())
619    }
620}
621
622/// Double ended iterator on the underlying buffer ordered from the oldest data
623/// to the newest.
624pub struct OldestOrdered<'a, T> {
625    inner: core::iter::Chain<core::slice::Iter<'a, T>, core::slice::Iter<'a, T>>,
626}
627
628impl<T> Clone for OldestOrdered<'_, T> {
629    fn clone(&self) -> Self {
630        Self {
631            inner: self.inner.clone(),
632        }
633    }
634}
635
636impl<'a, T> Iterator for OldestOrdered<'a, T> {
637    type Item = &'a T;
638
639    fn next(&mut self) -> Option<&'a T> {
640        self.inner.next()
641    }
642
643    fn size_hint(&self) -> (usize, Option<usize>) {
644        self.inner.size_hint()
645    }
646}
647
648impl<T> DoubleEndedIterator for OldestOrdered<'_, T> {
649    fn next_back(&mut self) -> Option<Self::Item> {
650        self.inner.next_back()
651    }
652}
653
654#[cfg(test)]
655mod tests {
656    use core::{
657        fmt::Debug,
658        sync::atomic::{AtomicUsize, Ordering},
659    };
660
661    use static_assertions::assert_not_impl_any;
662
663    use super::{HistoryBuf, HistoryBufView};
664
665    // Ensure a `HistoryBuf` containing `!Send` values stays `!Send` itself.
666    assert_not_impl_any!(HistoryBuf<*const (), 4>: Send);
667
668    #[test]
669    fn new() {
670        let x: HistoryBuf<u8, 4> = HistoryBuf::new_with(1);
671        assert_eq!(x.len(), 4);
672        assert_eq!(x.as_slice(), [1; 4]);
673        assert_eq!(*x, [1; 4]);
674        assert!(x.is_full());
675
676        let x: HistoryBuf<u8, 4> = HistoryBuf::new();
677        assert_eq!(x.as_slice(), []);
678        assert!(!x.is_full());
679    }
680
681    #[test]
682    fn write() {
683        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new();
684        x.write(1);
685        x.write(4);
686        assert_eq!(x.as_slice(), [1, 4]);
687
688        x.write(5);
689        x.write(6);
690        x.write(10);
691        assert_eq!(x.as_slice(), [10, 4, 5, 6]);
692
693        x.extend([11, 12].iter());
694        assert_eq!(x.as_slice(), [10, 11, 12, 6]);
695    }
696
697    #[test]
698    fn clear() {
699        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new_with(1);
700        x.clear();
701        assert_eq!(x.as_slice(), []);
702
703        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new();
704        x.clear_with(1);
705        assert_eq!(x.as_slice(), [1; 4]);
706    }
707
708    #[test]
709    fn clone() {
710        let mut x: HistoryBuf<u8, 3> = HistoryBuf::new();
711        for i in 0..10 {
712            assert_eq!(x.as_slice(), x.clone().as_slice());
713            x.write(i);
714        }
715
716        // Records number of clones locally and globally.
717        static GLOBAL: AtomicUsize = AtomicUsize::new(0);
718        #[derive(Default, PartialEq, Debug)]
719        struct InstrumentedClone(usize);
720
721        impl Clone for InstrumentedClone {
722            fn clone(&self) -> Self {
723                GLOBAL.fetch_add(1, Ordering::Relaxed);
724                Self(self.0 + 1)
725            }
726        }
727
728        let mut y: HistoryBuf<InstrumentedClone, 2> = HistoryBuf::new();
729        let _ = y.clone();
730        assert_eq!(GLOBAL.load(Ordering::Relaxed), 0);
731        y.write(InstrumentedClone(0));
732        assert_eq!(GLOBAL.load(Ordering::Relaxed), 0);
733        assert_eq!(y.clone().as_slice(), [InstrumentedClone(1)]);
734        assert_eq!(GLOBAL.load(Ordering::Relaxed), 1);
735        y.write(InstrumentedClone(0));
736        assert_eq!(GLOBAL.load(Ordering::Relaxed), 1);
737        assert_eq!(
738            y.clone().as_slice(),
739            [InstrumentedClone(1), InstrumentedClone(1)]
740        );
741        assert_eq!(GLOBAL.load(Ordering::Relaxed), 3);
742        assert_eq!(
743            y.clone().clone().clone().as_slice(),
744            [InstrumentedClone(3), InstrumentedClone(3)]
745        );
746        assert_eq!(GLOBAL.load(Ordering::Relaxed), 9);
747    }
748
749    #[test]
750    fn recent() {
751        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new();
752        assert_eq!(x.recent_index(), None);
753        assert_eq!(x.recent(), None);
754
755        x.write(1);
756        x.write(4);
757        assert_eq!(x.recent_index(), Some(1));
758        assert_eq!(x.recent(), Some(&4));
759
760        x.write(5);
761        x.write(6);
762        x.write(10);
763        assert_eq!(x.recent_index(), Some(0));
764        assert_eq!(x.recent(), Some(&10));
765    }
766
767    #[test]
768    fn oldest() {
769        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new();
770        assert_eq!(x.oldest_index(), None);
771        assert_eq!(x.oldest(), None);
772
773        x.write(1);
774        x.write(4);
775        assert_eq!(x.oldest_index(), Some(0));
776        assert_eq!(x.oldest(), Some(&1));
777
778        x.write(5);
779        x.write(6);
780        x.write(10);
781        assert_eq!(x.oldest_index(), Some(1));
782        assert_eq!(x.oldest(), Some(&4));
783    }
784
785    #[test]
786    fn as_slice() {
787        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new();
788
789        assert_eq!(x.as_slice(), []);
790
791        x.extend([1, 2, 3, 4, 5].iter());
792
793        assert_eq!(x.as_slice(), [5, 2, 3, 4]);
794    }
795
796    /// Test whether `.as_slices()` behaves as expected.
797    #[test]
798    fn as_slices() {
799        let mut buffer: HistoryBuf<u8, 4> = HistoryBuf::new();
800        let mut extend_then_assert = |extend: &[u8], assert: (&[u8], &[u8])| {
801            buffer.extend(extend);
802            assert_eq!(buffer.as_slices(), assert);
803        };
804
805        extend_then_assert(b"a", (b"a", b""));
806        extend_then_assert(b"bcd", (b"abcd", b""));
807        extend_then_assert(b"efg", (b"d", b"efg"));
808        extend_then_assert(b"h", (b"efgh", b""));
809        extend_then_assert(b"123456", (b"34", b"56"));
810    }
811
812    /// Test whether `.as_slices()` and `.oldest_ordered()` produce elements in the same order.
813    #[test]
814    fn as_slices_equals_ordered() {
815        let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
816
817        for n in 0..20 {
818            buffer.write(n);
819            let (head, tail) = buffer.as_slices();
820            assert_eq_iter(
821                [head, tail].iter().copied().flatten(),
822                buffer.oldest_ordered(),
823            );
824        }
825    }
826
827    #[test]
828    fn ordered() {
829        // test on an empty buffer
830        let buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
831        let mut iter = buffer.oldest_ordered();
832        assert_eq!(iter.next(), None);
833        assert_eq!(iter.next(), None);
834        assert_eq!(iter.next_back(), None);
835        assert_eq!(iter.next_back(), None);
836
837        // test on a un-filled buffer
838        let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
839        buffer.extend([1, 2, 3]);
840        assert_eq!(buffer.len(), 3);
841        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3]);
842        assert_eq_iter(buffer.oldest_ordered().rev(), &[3, 2, 1]);
843        let mut iter = buffer.oldest_ordered();
844        assert_eq!(iter.next(), Some(&1));
845        assert_eq!(iter.next_back(), Some(&3));
846        assert_eq!(iter.next_back(), Some(&2));
847        assert_eq!(iter.next_back(), None);
848        assert_eq!(iter.next(), None);
849
850        // test on an exactly filled buffer
851        let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
852        buffer.extend([1, 2, 3, 4, 5, 6]);
853        assert_eq!(buffer.len(), 6);
854        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3, 4, 5, 6]);
855        assert_eq_iter(buffer.oldest_ordered().rev(), &[6, 5, 4, 3, 2, 1]);
856
857        // test on a filled buffer
858        let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
859        buffer.extend([0, 0, 0, 1, 2, 3, 4, 5, 6]);
860        assert_eq!(buffer.len(), 6);
861        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3, 4, 5, 6]);
862        assert_eq_iter(buffer.oldest_ordered().rev(), &[6, 5, 4, 3, 2, 1]);
863
864        // comprehensive test all cases
865        for n in 0..50 {
866            const N: usize = 7;
867            let mut buffer: HistoryBuf<u8, N> = HistoryBuf::new();
868            buffer.extend(0..n);
869            assert_eq_iter(
870                buffer.oldest_ordered().copied(),
871                n.saturating_sub(N as u8)..n,
872            );
873            assert_eq_iter(
874                buffer.oldest_ordered().rev().copied(),
875                (n.saturating_sub(N as u8)..n).rev(),
876            );
877        }
878    }
879
880    /// Compares two iterators item by item, making sure they stop at the same time.
881    fn assert_eq_iter<I: Eq + Debug>(
882        a: impl IntoIterator<Item = I>,
883        b: impl IntoIterator<Item = I>,
884    ) {
885        let mut a = a.into_iter();
886        let mut b = b.into_iter();
887
888        let mut i = 0;
889        loop {
890            let a_item = a.next();
891            let b_item = b.next();
892
893            assert_eq!(a_item, b_item, "{i}");
894
895            i += 1;
896
897            if b_item.is_none() {
898                break;
899            }
900        }
901    }
902
903    #[test]
904    fn partial_eq() {
905        let mut x: HistoryBuf<u8, 3> = HistoryBuf::new();
906        let mut y: HistoryBuf<u8, 3> = HistoryBuf::new();
907        assert_eq!(x, y);
908        x.write(1);
909        assert_ne!(x, y);
910        y.write(1);
911        assert_eq!(x, y);
912        for _ in 0..4 {
913            x.write(2);
914            assert_ne!(x, y);
915            for i in 0..5 {
916                x.write(i);
917                y.write(i);
918            }
919            assert_eq!(
920                x,
921                y,
922                "{:?} {:?}",
923                x.iter().collect::<Vec<_>>(),
924                y.iter().collect::<Vec<_>>()
925            );
926        }
927    }
928
929    #[test]
930    fn clear_drops_values() {
931        static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
932
933        struct DropCheck {}
934
935        impl Drop for DropCheck {
936            fn drop(&mut self) {
937                DROP_COUNT.fetch_add(1, Ordering::SeqCst);
938            }
939        }
940
941        let mut x: HistoryBuf<DropCheck, 3> = HistoryBuf::new();
942        x.write(DropCheck {});
943        x.write(DropCheck {});
944        x.write(DropCheck {});
945
946        assert_eq!(DROP_COUNT.load(Ordering::SeqCst), 0);
947        x.clear();
948        assert_eq!(DROP_COUNT.load(Ordering::SeqCst), 3);
949    }
950
951    #[test]
952    #[cfg(feature = "zeroize")]
953    fn test_history_buf_zeroize() {
954        use zeroize::Zeroize;
955
956        let mut buffer = HistoryBuf::<u8, 8>::new();
957        for i in 0..8 {
958            buffer.write(i);
959        }
960
961        assert_eq!(buffer.len(), 8);
962        assert_eq!(buffer.recent(), Some(&7));
963
964        // Clear to mark formerly used memory as unused, to make sure that it also gets zeroed
965        buffer.clear();
966
967        buffer.write(20);
968        assert_eq!(buffer.len(), 1);
969        assert_eq!(buffer.recent(), Some(&20));
970
971        buffer.zeroize();
972
973        assert_eq!(buffer.len(), 0);
974        assert!(buffer.is_empty());
975
976        // Check that all underlying memory actually got zeroized
977        unsafe {
978            for a in buffer.data.buffer {
979                assert_eq!(a.assume_init(), 0);
980            }
981        }
982    }
983
984    fn _test_variance<'a: 'b, 'b>(x: HistoryBuf<&'a (), 42>) -> HistoryBuf<&'b (), 42> {
985        x
986    }
987    fn _test_variance_view<'a: 'b, 'b, 'c>(
988        x: &'c HistoryBufView<&'a ()>,
989    ) -> &'c HistoryBufView<&'b ()> {
990        x
991    }
992}
heapless/history_buf.rs

heapless/
history_buf.rs
