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        self.clear();
312
313        for d in self.data.borrow_mut() {
314            *d = MaybeUninit::new(t);
315        }
316        self.write_at = 0;
317        self.filled = true;
318    }
319}
320
321impl<T, S: HistoryBufStorage<T> + ?Sized> HistoryBufInner<T, S> {
322    /// Clears the buffer
323    pub fn clear(&mut self) {
324        struct Guard<'a, T, S: HistoryBufStorage<T> + ?Sized>(&'a mut HistoryBufInner<T, S>);
325        impl<'a, T, S: HistoryBufStorage<T> + ?Sized> Drop for Guard<'a, T, S> {
326            fn drop(&mut self) {
327                self.0.write_at = 0;
328                self.0.filled = false;
329            }
330        }
331        let this = Guard(self);
332        // SAFETY: Guard will be dropped and lead to a consistent empty state even in the case of a
333        // panic leading to unwinding during the dropping of an item
334        unsafe { this.0.drop_contents() };
335    }
336}
337
338impl<T, S: HistoryBufStorage<T> + ?Sized> HistoryBufInner<T, S> {
339    unsafe fn drop_contents(&mut self) {
340        unsafe {
341            ptr::drop_in_place(ptr::slice_from_raw_parts_mut(
342                self.data.borrow_mut().as_mut_ptr().cast::<T>(),
343                self.len(),
344            ));
345        }
346    }
347
348    /// Returns the current fill level of the buffer.
349    #[inline]
350    pub fn len(&self) -> usize {
351        if self.filled {
352            self.capacity()
353        } else {
354            self.write_at
355        }
356    }
357
358    /// Returns true if the buffer is empty.
359    ///
360    /// # Examples
361    ///
362    /// ```
363    /// use heapless::HistoryBuf;
364    ///
365    /// let x: HistoryBuf<u8, 16> = HistoryBuf::new();
366    /// assert!(x.is_empty());
367    /// ```
368    #[inline]
369    pub fn is_empty(&self) -> bool {
370        self.len() == 0
371    }
372
373    /// Returns the capacity of the buffer, which is the length of the
374    /// underlying backing array.
375    #[inline]
376    pub fn capacity(&self) -> usize {
377        self.data.borrow().len()
378    }
379
380    /// Returns whether the buffer is full
381    #[inline]
382    pub fn is_full(&self) -> bool {
383        self.filled
384    }
385
386    /// Writes an element to the buffer, overwriting the oldest value.
387    pub fn write(&mut self, t: T) {
388        if self.filled {
389            // Drop the old before we overwrite it.
390            unsafe { ptr::drop_in_place(self.data.borrow_mut()[self.write_at].as_mut_ptr()) }
391        }
392        self.data.borrow_mut()[self.write_at] = MaybeUninit::new(t);
393
394        self.write_at += 1;
395        if self.write_at == self.capacity() {
396            self.write_at = 0;
397            self.filled = true;
398        }
399    }
400
401    /// Clones and writes all elements in a slice to the buffer.
402    ///
403    /// If the slice is longer than the buffer, only the last `self.len()`
404    /// elements will actually be stored.
405    pub fn extend_from_slice(&mut self, other: &[T])
406    where
407        T: Clone,
408    {
409        for item in other {
410            self.write(item.clone());
411        }
412    }
413
414    /// Returns a reference to the most recently written value.
415    ///
416    /// # Examples
417    ///
418    /// ```
419    /// use heapless::HistoryBuf;
420    ///
421    /// let mut x: HistoryBuf<u8, 16> = HistoryBuf::new();
422    /// x.write(4);
423    /// x.write(10);
424    /// assert_eq!(x.recent(), Some(&10));
425    /// ```
426    pub fn recent(&self) -> Option<&T> {
427        self.recent_index()
428            .map(|i| unsafe { &*self.data.borrow()[i].as_ptr() })
429    }
430
431    /// Returns index of the most recently written value in the underlying slice.
432    ///
433    /// # Examples
434    ///
435    /// ```
436    /// use heapless::HistoryBuf;
437    ///
438    /// let mut x: HistoryBuf<u8, 16> = HistoryBuf::new();
439    /// x.write(4);
440    /// x.write(10);
441    /// assert_eq!(x.recent_index(), Some(1));
442    /// ```
443    pub fn recent_index(&self) -> Option<usize> {
444        if self.write_at == 0 {
445            if self.filled {
446                Some(self.capacity() - 1)
447            } else {
448                None
449            }
450        } else {
451            Some(self.write_at - 1)
452        }
453    }
454
455    /// Returns a reference to the oldest value in the buffer.
456    ///
457    /// # Examples
458    ///
459    /// ```
460    /// use heapless::HistoryBuf;
461    ///
462    /// let mut x: HistoryBuf<u8, 16> = HistoryBuf::new();
463    /// x.write(4);
464    /// x.write(10);
465    /// assert_eq!(x.oldest(), Some(&4));
466    /// ```
467    pub fn oldest(&self) -> Option<&T> {
468        self.oldest_index()
469            .map(|i| unsafe { &*self.data.borrow()[i].as_ptr() })
470    }
471
472    /// Returns index of the oldest value in the underlying slice.
473    ///
474    /// # Examples
475    ///
476    /// ```
477    /// use heapless::HistoryBuf;
478    ///
479    /// let mut x: HistoryBuf<u8, 16> = HistoryBuf::new();
480    /// x.write(4);
481    /// x.write(10);
482    /// assert_eq!(x.oldest_index(), Some(0));
483    /// ```
484    pub fn oldest_index(&self) -> Option<usize> {
485        if self.filled {
486            Some(self.write_at)
487        } else if self.write_at == 0 {
488            None
489        } else {
490            Some(0)
491        }
492    }
493
494    /// Returns the array slice backing the buffer, without keeping track
495    /// of the write position. Therefore, the element order is unspecified.
496    pub fn as_slice(&self) -> &[T] {
497        unsafe { slice::from_raw_parts(self.data.borrow().as_ptr().cast(), self.len()) }
498    }
499
500    /// Returns a pair of slices which contain, in order, the contents of the buffer.
501    ///
502    /// # Examples
503    ///
504    /// ```
505    /// use heapless::HistoryBuf;
506    ///
507    /// let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
508    /// buffer.extend([0, 0, 0]);
509    /// buffer.extend([1, 2, 3, 4, 5, 6]);
510    /// assert_eq!(buffer.as_slices(), (&[1, 2, 3][..], &[4, 5, 6][..]));
511    /// ```
512    pub fn as_slices(&self) -> (&[T], &[T]) {
513        let buffer = self.as_slice();
514
515        if self.filled {
516            (&buffer[self.write_at..], &buffer[..self.write_at])
517        } else {
518            (buffer, &[])
519        }
520    }
521
522    /// Returns double ended iterator for iterating over the buffer from
523    /// the oldest to the newest and back.
524    ///
525    /// # Examples
526    ///
527    /// ```
528    /// use heapless::HistoryBuf;
529    ///
530    /// let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
531    /// buffer.extend([0, 0, 0, 1, 2, 3, 4, 5, 6]);
532    /// let expected = [1, 2, 3, 4, 5, 6];
533    /// for (x, y) in buffer.oldest_ordered().zip(expected.iter()) {
534    ///     assert_eq!(x, y)
535    /// }
536    /// ```
537    pub fn oldest_ordered(&self) -> OldestOrdered<'_, T> {
538        let (old, new) = self.as_slices();
539        OldestOrdered {
540            inner: old.iter().chain(new),
541        }
542    }
543}
544
545impl<T, S: HistoryBufStorage<T> + ?Sized> Extend<T> for HistoryBufInner<T, S> {
546    fn extend<I>(&mut self, iter: I)
547    where
548        I: IntoIterator<Item = T>,
549    {
550        for item in iter.into_iter() {
551            self.write(item);
552        }
553    }
554}
555
556impl<'a, T, S: HistoryBufStorage<T> + ?Sized> Extend<&'a T> for HistoryBufInner<T, S>
557where
558    T: 'a + Clone,
559{
560    fn extend<I>(&mut self, iter: I)
561    where
562        I: IntoIterator<Item = &'a T>,
563    {
564        self.extend(iter.into_iter().cloned());
565    }
566}
567
568impl<T, const N: usize> Clone for HistoryBuf<T, N>
569where
570    T: Clone,
571{
572    fn clone(&self) -> Self {
573        let mut ret = Self::new();
574        for (new, old) in ret.data.borrow_mut().iter_mut().zip(self.as_slice()) {
575            new.write(old.clone());
576        }
577        ret.filled = self.filled;
578        ret.write_at = self.write_at;
579        ret
580    }
581}
582
583impl<T, S: HistoryBufStorage<T> + ?Sized> Drop for HistoryBufInner<T, S> {
584    fn drop(&mut self) {
585        unsafe { self.drop_contents() }
586    }
587}
588
589impl<T, S: HistoryBufStorage<T> + ?Sized> Deref for HistoryBufInner<T, S> {
590    type Target = [T];
591
592    fn deref(&self) -> &[T] {
593        self.as_slice()
594    }
595}
596
597impl<T, S: HistoryBufStorage<T> + ?Sized> AsRef<[T]> for HistoryBufInner<T, S> {
598    #[inline]
599    fn as_ref(&self) -> &[T] {
600        self
601    }
602}
603
604impl<T, S: HistoryBufStorage<T> + ?Sized> fmt::Debug for HistoryBufInner<T, S>
605where
606    T: fmt::Debug,
607{
608    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
609        <[T] as fmt::Debug>::fmt(self, f)
610    }
611}
612
613impl<T, const N: usize> Default for HistoryBuf<T, N> {
614    fn default() -> Self {
615        Self::new()
616    }
617}
618
619impl<T, S1, S2> PartialEq<HistoryBufInner<T, S2>> for HistoryBufInner<T, S1>
620where
621    T: PartialEq,
622    S1: HistoryBufStorage<T> + ?Sized,
623    S2: HistoryBufStorage<T> + ?Sized,
624{
625    fn eq(&self, other: &HistoryBufInner<T, S2>) -> bool {
626        self.oldest_ordered().eq(other.oldest_ordered())
627    }
628}
629
630/// Double ended iterator on the underlying buffer ordered from the oldest data
631/// to the newest.
632pub struct OldestOrdered<'a, T> {
633    inner: core::iter::Chain<core::slice::Iter<'a, T>, core::slice::Iter<'a, T>>,
634}
635
636impl<T> Clone for OldestOrdered<'_, T> {
637    fn clone(&self) -> Self {
638        Self {
639            inner: self.inner.clone(),
640        }
641    }
642}
643
644impl<'a, T> Iterator for OldestOrdered<'a, T> {
645    type Item = &'a T;
646
647    fn next(&mut self) -> Option<&'a T> {
648        self.inner.next()
649    }
650
651    fn size_hint(&self) -> (usize, Option<usize>) {
652        self.inner.size_hint()
653    }
654}
655
656impl<T> DoubleEndedIterator for OldestOrdered<'_, T> {
657    fn next_back(&mut self) -> Option<Self::Item> {
658        self.inner.next_back()
659    }
660}
661
662#[cfg(test)]
663mod tests {
664    use core::{
665        fmt::Debug,
666        sync::atomic::{AtomicUsize, Ordering},
667    };
668    use std::{
669        mem::ManuallyDrop,
670        panic::{catch_unwind, AssertUnwindSafe},
671        sync::atomic::AtomicI32,
672    };
673
674    use static_assertions::assert_not_impl_any;
675
676    use super::{HistoryBuf, HistoryBufView};
677
678    // Ensure a `HistoryBuf` containing `!Send` values stays `!Send` itself.
679    assert_not_impl_any!(HistoryBuf<*const (), 4>: Send);
680
681    #[test]
682    fn new() {
683        let x: HistoryBuf<u8, 4> = HistoryBuf::new_with(1);
684        assert_eq!(x.len(), 4);
685        assert_eq!(x.as_slice(), [1; 4]);
686        assert_eq!(*x, [1; 4]);
687        assert!(x.is_full());
688
689        let x: HistoryBuf<u8, 4> = HistoryBuf::new();
690        assert_eq!(x.as_slice(), []);
691        assert!(!x.is_full());
692    }
693
694    #[test]
695    fn write() {
696        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new();
697        x.write(1);
698        x.write(4);
699        assert_eq!(x.as_slice(), [1, 4]);
700
701        x.write(5);
702        x.write(6);
703        x.write(10);
704        assert_eq!(x.as_slice(), [10, 4, 5, 6]);
705
706        x.extend([11, 12].iter());
707        assert_eq!(x.as_slice(), [10, 11, 12, 6]);
708    }
709
710    #[test]
711    fn clear() {
712        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new_with(1);
713        x.clear();
714        assert_eq!(x.as_slice(), []);
715
716        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new();
717        x.clear_with(1);
718        assert_eq!(x.as_slice(), [1; 4]);
719    }
720
721    #[test]
722    fn clone() {
723        let mut x: HistoryBuf<u8, 3> = HistoryBuf::new();
724        for i in 0..10 {
725            assert_eq!(x.as_slice(), x.clone().as_slice());
726            x.write(i);
727        }
728
729        // Records number of clones locally and globally.
730        static GLOBAL: AtomicUsize = AtomicUsize::new(0);
731        #[derive(Default, PartialEq, Debug)]
732        struct InstrumentedClone(usize);
733
734        impl Clone for InstrumentedClone {
735            fn clone(&self) -> Self {
736                GLOBAL.fetch_add(1, Ordering::Relaxed);
737                Self(self.0 + 1)
738            }
739        }
740
741        let mut y: HistoryBuf<InstrumentedClone, 2> = HistoryBuf::new();
742        let _ = y.clone();
743        assert_eq!(GLOBAL.load(Ordering::Relaxed), 0);
744        y.write(InstrumentedClone(0));
745        assert_eq!(GLOBAL.load(Ordering::Relaxed), 0);
746        assert_eq!(y.clone().as_slice(), [InstrumentedClone(1)]);
747        assert_eq!(GLOBAL.load(Ordering::Relaxed), 1);
748        y.write(InstrumentedClone(0));
749        assert_eq!(GLOBAL.load(Ordering::Relaxed), 1);
750        assert_eq!(
751            y.clone().as_slice(),
752            [InstrumentedClone(1), InstrumentedClone(1)]
753        );
754        assert_eq!(GLOBAL.load(Ordering::Relaxed), 3);
755        assert_eq!(
756            y.clone().clone().clone().as_slice(),
757            [InstrumentedClone(3), InstrumentedClone(3)]
758        );
759        assert_eq!(GLOBAL.load(Ordering::Relaxed), 9);
760    }
761
762    #[test]
763    fn recent() {
764        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new();
765        assert_eq!(x.recent_index(), None);
766        assert_eq!(x.recent(), None);
767
768        x.write(1);
769        x.write(4);
770        assert_eq!(x.recent_index(), Some(1));
771        assert_eq!(x.recent(), Some(&4));
772
773        x.write(5);
774        x.write(6);
775        x.write(10);
776        assert_eq!(x.recent_index(), Some(0));
777        assert_eq!(x.recent(), Some(&10));
778    }
779
780    #[test]
781    fn oldest() {
782        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new();
783        assert_eq!(x.oldest_index(), None);
784        assert_eq!(x.oldest(), None);
785
786        x.write(1);
787        x.write(4);
788        assert_eq!(x.oldest_index(), Some(0));
789        assert_eq!(x.oldest(), Some(&1));
790
791        x.write(5);
792        x.write(6);
793        x.write(10);
794        assert_eq!(x.oldest_index(), Some(1));
795        assert_eq!(x.oldest(), Some(&4));
796    }
797
798    #[test]
799    fn as_slice() {
800        let mut x: HistoryBuf<u8, 4> = HistoryBuf::new();
801
802        assert_eq!(x.as_slice(), []);
803
804        x.extend([1, 2, 3, 4, 5].iter());
805
806        assert_eq!(x.as_slice(), [5, 2, 3, 4]);
807    }
808
809    /// Test whether `.as_slices()` behaves as expected.
810    #[test]
811    fn as_slices() {
812        let mut buffer: HistoryBuf<u8, 4> = HistoryBuf::new();
813        let mut extend_then_assert = |extend: &[u8], assert: (&[u8], &[u8])| {
814            buffer.extend(extend);
815            assert_eq!(buffer.as_slices(), assert);
816        };
817
818        extend_then_assert(b"a", (b"a", b""));
819        extend_then_assert(b"bcd", (b"abcd", b""));
820        extend_then_assert(b"efg", (b"d", b"efg"));
821        extend_then_assert(b"h", (b"efgh", b""));
822        extend_then_assert(b"123456", (b"34", b"56"));
823    }
824
825    /// Test whether `.as_slices()` and `.oldest_ordered()` produce elements in the same order.
826    #[test]
827    fn as_slices_equals_ordered() {
828        let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
829
830        for n in 0..20 {
831            buffer.write(n);
832            let (head, tail) = buffer.as_slices();
833            assert_eq_iter(
834                [head, tail].iter().copied().flatten(),
835                buffer.oldest_ordered(),
836            );
837        }
838    }
839
840    #[test]
841    fn ordered() {
842        // test on an empty buffer
843        let buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
844        let mut iter = buffer.oldest_ordered();
845        assert_eq!(iter.next(), None);
846        assert_eq!(iter.next(), None);
847        assert_eq!(iter.next_back(), None);
848        assert_eq!(iter.next_back(), None);
849
850        // test on a un-filled buffer
851        let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
852        buffer.extend([1, 2, 3]);
853        assert_eq!(buffer.len(), 3);
854        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3]);
855        assert_eq_iter(buffer.oldest_ordered().rev(), &[3, 2, 1]);
856        let mut iter = buffer.oldest_ordered();
857        assert_eq!(iter.next(), Some(&1));
858        assert_eq!(iter.next_back(), Some(&3));
859        assert_eq!(iter.next_back(), Some(&2));
860        assert_eq!(iter.next_back(), None);
861        assert_eq!(iter.next(), None);
862
863        // test on an exactly filled buffer
864        let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
865        buffer.extend([1, 2, 3, 4, 5, 6]);
866        assert_eq!(buffer.len(), 6);
867        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3, 4, 5, 6]);
868        assert_eq_iter(buffer.oldest_ordered().rev(), &[6, 5, 4, 3, 2, 1]);
869
870        // test on a filled buffer
871        let mut buffer: HistoryBuf<u8, 6> = HistoryBuf::new();
872        buffer.extend([0, 0, 0, 1, 2, 3, 4, 5, 6]);
873        assert_eq!(buffer.len(), 6);
874        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3, 4, 5, 6]);
875        assert_eq_iter(buffer.oldest_ordered().rev(), &[6, 5, 4, 3, 2, 1]);
876
877        // comprehensive test all cases
878        for n in 0..50 {
879            const N: usize = 7;
880            let mut buffer: HistoryBuf<u8, N> = HistoryBuf::new();
881            buffer.extend(0..n);
882            assert_eq_iter(
883                buffer.oldest_ordered().copied(),
884                n.saturating_sub(N as u8)..n,
885            );
886            assert_eq_iter(
887                buffer.oldest_ordered().rev().copied(),
888                (n.saturating_sub(N as u8)..n).rev(),
889            );
890        }
891    }
892
893    /// Compares two iterators item by item, making sure they stop at the same time.
894    fn assert_eq_iter<I: Eq + Debug>(
895        a: impl IntoIterator<Item = I>,
896        b: impl IntoIterator<Item = I>,
897    ) {
898        let mut a = a.into_iter();
899        let mut b = b.into_iter();
900
901        let mut i = 0;
902        loop {
903            let a_item = a.next();
904            let b_item = b.next();
905
906            assert_eq!(a_item, b_item, "{i}");
907
908            i += 1;
909
910            if b_item.is_none() {
911                break;
912            }
913        }
914    }
915
916    #[test]
917    fn partial_eq() {
918        let mut x: HistoryBuf<u8, 3> = HistoryBuf::new();
919        let mut y: HistoryBuf<u8, 3> = HistoryBuf::new();
920        assert_eq!(x, y);
921        x.write(1);
922        assert_ne!(x, y);
923        y.write(1);
924        assert_eq!(x, y);
925        for _ in 0..4 {
926            x.write(2);
927            assert_ne!(x, y);
928            for i in 0..5 {
929                x.write(i);
930                y.write(i);
931            }
932            assert_eq!(
933                x,
934                y,
935                "{:?} {:?}",
936                x.iter().collect::<Vec<_>>(),
937                y.iter().collect::<Vec<_>>()
938            );
939        }
940    }
941
942    #[test]
943    fn clear_drops_values() {
944        static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
945
946        struct DropCheck {}
947
948        impl Drop for DropCheck {
949            fn drop(&mut self) {
950                DROP_COUNT.fetch_add(1, Ordering::SeqCst);
951            }
952        }
953
954        let mut x: HistoryBuf<DropCheck, 3> = HistoryBuf::new();
955        x.write(DropCheck {});
956        x.write(DropCheck {});
957        x.write(DropCheck {});
958
959        assert_eq!(DROP_COUNT.load(Ordering::SeqCst), 0);
960        x.clear();
961        assert_eq!(DROP_COUNT.load(Ordering::SeqCst), 3);
962    }
963
964    #[test]
965    #[cfg(feature = "zeroize")]
966    fn test_history_buf_zeroize() {
967        use zeroize::Zeroize;
968
969        let mut buffer = HistoryBuf::<u8, 8>::new();
970        for i in 0..8 {
971            buffer.write(i);
972        }
973
974        assert_eq!(buffer.len(), 8);
975        assert_eq!(buffer.recent(), Some(&7));
976
977        // Clear to mark formerly used memory as unused, to make sure that it also gets zeroed
978        buffer.clear();
979
980        buffer.write(20);
981        assert_eq!(buffer.len(), 1);
982        assert_eq!(buffer.recent(), Some(&20));
983
984        buffer.zeroize();
985
986        assert_eq!(buffer.len(), 0);
987        assert!(buffer.is_empty());
988
989        // Check that all underlying memory actually got zeroized
990        unsafe {
991            for a in buffer.data.buffer {
992                assert_eq!(a.assume_init(), 0);
993            }
994        }
995    }
996
997    #[test]
998    fn test_use_after_free_clear() {
999        // See https://github.com/rust-embedded/heapless/issues/646
1000
1001        static COUNT: AtomicI32 = AtomicI32::new(0);
1002
1003        #[derive(Debug)]
1004        #[allow(unused)]
1005        struct Dropper();
1006
1007        impl Dropper {
1008            fn new() -> Self {
1009                COUNT.fetch_add(1, Ordering::Relaxed);
1010                Self()
1011            }
1012            fn count() -> i32 {
1013                COUNT.load(Ordering::Relaxed)
1014            }
1015        }
1016        impl Drop for Dropper {
1017            fn drop(&mut self) {
1018                COUNT.fetch_sub(1, Ordering::Relaxed);
1019                panic!("Testing  panicking");
1020            }
1021        }
1022
1023        let mut history_buf = HistoryBuf::<Dropper, 5>::new();
1024        history_buf.write(Dropper::new());
1025        // Don't panic on dropping of the history_buf
1026        let mut history_buf = ManuallyDrop::new(history_buf);
1027        let mut unwind_safe_history_buf = AssertUnwindSafe(&mut history_buf);
1028
1029        catch_unwind(move || unwind_safe_history_buf.clear()).unwrap_err();
1030        assert_eq!(history_buf.len(), 0);
1031        history_buf.clear();
1032        assert_eq!(Dropper::count(), 0);
1033    }
1034
1035    fn _test_variance<'a: 'b, 'b>(x: HistoryBuf<&'a (), 42>) -> HistoryBuf<&'b (), 42> {
1036        x
1037    }
1038    fn _test_variance_view<'a: 'b, 'b, 'c>(
1039        x: &'c HistoryBufView<&'a ()>,
1040    ) -> &'c HistoryBufView<&'b ()> {
1041        x
1042    }
1043}
heapless/history_buf.rs

heapless/
history_buf.rs
