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

heapless/
history_buf.rs
