1use core::fmt;
2use core::mem::MaybeUninit;
3use core::ops::Deref;
4use core::ptr;
5use core::slice;
6
7/// A "history buffer", similar to a write-only ring buffer of fixed length.
8///
9/// This buffer keeps a fixed number of elements. On write, the oldest element
10/// is overwritten. Thus, the buffer is useful to keep a history of values with
11/// some desired depth, and for example calculate a rolling average.
12///
13/// # Examples
14/// ```
15/// use heapless::HistoryBuffer;
16///
17/// // Initialize a new buffer with 8 elements.
18/// let mut buf = HistoryBuffer::<_, 8>::new();
19///
20/// // Starts with no data
21/// assert_eq!(buf.recent(), None);
22///
23/// buf.write(3);
24/// buf.write(5);
25/// buf.extend(&[4, 4]);
26///
27/// // The most recent written element is a four.
28/// assert_eq!(buf.recent(), Some(&4));
29///
30/// // To access all elements in an unspecified order, use `as_slice()`.
31/// for el in buf.as_slice() { println!("{:?}", el); }
32///
33/// // Now we can prepare an average of all values, which comes out to 4.
34/// let avg = buf.as_slice().iter().sum::<usize>() / buf.len();
35/// assert_eq!(avg, 4);
36/// ```
37pub struct HistoryBuffer<T, const N: usize> {
38 data: [MaybeUninit<T>; N],
39 write_at: usize,
40 filled: bool,
41}
42
43impl<T, const N: usize> HistoryBuffer<T, N> {
44 const INIT: MaybeUninit<T> = MaybeUninit::uninit();
45
46 /// Constructs a new history buffer.
47 ///
48 /// The construction of a `HistoryBuffer` works in `const` contexts.
49 ///
50 /// # Examples
51 ///
52 /// ```
53 /// use heapless::HistoryBuffer;
54 ///
55 /// // Allocate a 16-element buffer on the stack
56 /// let x: HistoryBuffer<u8, 16> = HistoryBuffer::new();
57 /// assert_eq!(x.len(), 0);
58 /// ```
59 #[inline]
60 pub const fn new() -> Self {
61 // Const assert
62 crate::sealed::greater_than_0::<N>();
63
64 Self {
65 data: [Self::INIT; N],
66 write_at: 0,
67 filled: false,
68 }
69 }
70
71 /// Clears the buffer, replacing every element with the default value of
72 /// type `T`.
73 pub fn clear(&mut self) {
74 *self = Self::new();
75 }
76}
77
78impl<T, const N: usize> HistoryBuffer<T, N>
79where
80 T: Copy + Clone,
81{
82 /// Constructs a new history buffer, where every element is the given value.
83 ///
84 /// # Examples
85 ///
86 /// ```
87 /// use heapless::HistoryBuffer;
88 ///
89 /// // Allocate a 16-element buffer on the stack
90 /// let mut x: HistoryBuffer<u8, 16> = HistoryBuffer::new_with(4);
91 /// // All elements are four
92 /// assert_eq!(x.as_slice(), [4; 16]);
93 /// ```
94 #[inline]
95 pub fn new_with(t: T) -> Self {
96 Self {
97 data: [MaybeUninit::new(t); N],
98 write_at: 0,
99 filled: true,
100 }
101 }
102
103 /// Clears the buffer, replacing every element with the given value.
104 pub fn clear_with(&mut self, t: T) {
105 *self = Self::new_with(t);
106 }
107}
108
109impl<T, const N: usize> HistoryBuffer<T, N> {
110 /// Returns the current fill level of the buffer.
111 #[inline]
112 pub fn len(&self) -> usize {
113 if self.filled {
114 N
115 } else {
116 self.write_at
117 }
118 }
119
120 /// Returns the capacity of the buffer, which is the length of the
121 /// underlying backing array.
122 #[inline]
123 pub fn capacity(&self) -> usize {
124 N
125 }
126
127 /// Writes an element to the buffer, overwriting the oldest value.
128 pub fn write(&mut self, t: T) {
129 if self.filled {
130 // Drop the old before we overwrite it.
131 unsafe { ptr::drop_in_place(self.data[self.write_at].as_mut_ptr()) }
132 }
133 self.data[self.write_at] = MaybeUninit::new(t);
134
135 self.write_at += 1;
136 if self.write_at == self.capacity() {
137 self.write_at = 0;
138 self.filled = true;
139 }
140 }
141
142 /// Clones and writes all elements in a slice to the buffer.
143 ///
144 /// If the slice is longer than the buffer, only the last `self.len()`
145 /// elements will actually be stored.
146 pub fn extend_from_slice(&mut self, other: &[T])
147 where
148 T: Clone,
149 {
150 for item in other {
151 self.write(item.clone());
152 }
153 }
154
155 /// Returns a reference to the most recently written value.
156 ///
157 /// # Examples
158 ///
159 /// ```
160 /// use heapless::HistoryBuffer;
161 ///
162 /// let mut x: HistoryBuffer<u8, 16> = HistoryBuffer::new();
163 /// x.write(4);
164 /// x.write(10);
165 /// assert_eq!(x.recent(), Some(&10));
166 /// ```
167 pub fn recent(&self) -> Option<&T> {
168 if self.write_at == 0 {
169 if self.filled {
170 Some(unsafe { &*self.data[self.capacity() - 1].as_ptr() })
171 } else {
172 None
173 }
174 } else {
175 Some(unsafe { &*self.data[self.write_at - 1].as_ptr() })
176 }
177 }
178
179 /// Returns the array slice backing the buffer, without keeping track
180 /// of the write position. Therefore, the element order is unspecified.
181 pub fn as_slice(&self) -> &[T] {
182 unsafe { slice::from_raw_parts(self.data.as_ptr() as *const _, self.len()) }
183 }
184
185 /// Returns a pair of slices which contain, in order, the contents of the buffer.
186 ///
187 /// # Examples
188 ///
189 /// ```
190 /// use heapless::HistoryBuffer;
191 ///
192 /// let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
193 /// buffer.extend([0, 0, 0]);
194 /// buffer.extend([1, 2, 3, 4, 5, 6]);
195 /// assert_eq!(buffer.as_slices(), (&[1, 2, 3][..], &[4, 5, 6][..]));
196 /// ```
197 pub fn as_slices(&self) -> (&[T], &[T]) {
198 let buffer = self.as_slice();
199
200 if !self.filled {
201 (buffer, &[])
202 } else {
203 (&buffer[self.write_at..], &buffer[..self.write_at])
204 }
205 }
206
207 /// Returns an iterator for iterating over the buffer from oldest to newest.
208 ///
209 /// # Examples
210 ///
211 /// ```
212 /// use heapless::HistoryBuffer;
213 ///
214 /// let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
215 /// buffer.extend([0, 0, 0, 1, 2, 3, 4, 5, 6]);
216 /// let expected = [1, 2, 3, 4, 5, 6];
217 /// for (x, y) in buffer.oldest_ordered().zip(expected.iter()) {
218 /// assert_eq!(x, y)
219 /// }
220 ///
221 /// ```
222 pub fn oldest_ordered<'a>(&'a self) -> OldestOrdered<'a, T, N> {
223 if self.filled {
224 OldestOrdered {
225 buf: self,
226 cur: self.write_at,
227 wrapped: false,
228 }
229 } else {
230 // special case: act like we wrapped already to handle empty buffer.
231 OldestOrdered {
232 buf: self,
233 cur: 0,
234 wrapped: true,
235 }
236 }
237 }
238}
239
240impl<T, const N: usize> Extend<T> for HistoryBuffer<T, N> {
241 fn extend<I>(&mut self, iter: I)
242 where
243 I: IntoIterator<Item = T>,
244 {
245 for item: T in iter.into_iter() {
246 self.write(item);
247 }
248 }
249}
250
251impl<'a, T, const N: usize> Extend<&'a T> for HistoryBuffer<T, N>
252where
253 T: 'a + Clone,
254{
255 fn extend<I>(&mut self, iter: I)
256 where
257 I: IntoIterator<Item = &'a T>,
258 {
259 self.extend(iter.into_iter().cloned())
260 }
261}
262
263impl<T, const N: usize> Clone for HistoryBuffer<T, N>
264where
265 T: Clone,
266{
267 fn clone(&self) -> Self {
268 let mut ret: HistoryBuffer = Self::new();
269 for (new: &mut MaybeUninit, old: &T) in ret.data.iter_mut().zip(self.as_slice()) {
270 new.write(val:old.clone());
271 }
272 ret.filled = self.filled;
273 ret.write_at = self.write_at;
274 ret
275 }
276}
277
278impl<T, const N: usize> Drop for HistoryBuffer<T, N> {
279 fn drop(&mut self) {
280 unsafe {
281 ptr::drop_in_place(to_drop:ptr::slice_from_raw_parts_mut(
282 self.data.as_mut_ptr() as *mut T,
283 self.len(),
284 ))
285 }
286 }
287}
288
289impl<T, const N: usize> Deref for HistoryBuffer<T, N> {
290 type Target = [T];
291
292 fn deref(&self) -> &[T] {
293 self.as_slice()
294 }
295}
296
297impl<T, const N: usize> AsRef<[T]> for HistoryBuffer<T, N> {
298 #[inline]
299 fn as_ref(&self) -> &[T] {
300 self
301 }
302}
303
304impl<T, const N: usize> fmt::Debug for HistoryBuffer<T, N>
305where
306 T: fmt::Debug,
307{
308 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
309 <[T] as fmt::Debug>::fmt(self, f)
310 }
311}
312
313impl<T, const N: usize> Default for HistoryBuffer<T, N> {
314 fn default() -> Self {
315 Self::new()
316 }
317}
318
319impl<T, const N: usize> PartialEq for HistoryBuffer<T, N>
320where
321 T: PartialEq,
322{
323 fn eq(&self, other: &Self) -> bool {
324 self.oldest_ordered().eq(other.oldest_ordered())
325 }
326}
327
328/// An iterator on the underlying buffer ordered from oldest data to newest
329#[derive(Clone)]
330pub struct OldestOrdered<'a, T, const N: usize> {
331 buf: &'a HistoryBuffer<T, N>,
332 cur: usize,
333 wrapped: bool,
334}
335
336impl<'a, T, const N: usize> Iterator for OldestOrdered<'a, T, N> {
337 type Item = &'a T;
338
339 fn next(&mut self) -> Option<&'a T> {
340 if self.cur == self.buf.len() && self.buf.filled {
341 // roll-over
342 self.cur = 0;
343 self.wrapped = true;
344 }
345
346 if self.cur == self.buf.write_at && self.wrapped {
347 return None;
348 }
349
350 let item: &T = &self.buf[self.cur];
351 self.cur += 1;
352 Some(item)
353 }
354}
355
356#[cfg(test)]
357mod tests {
358 use crate::HistoryBuffer;
359 use core::fmt::Debug;
360 use core::sync::atomic::{AtomicUsize, Ordering};
361
362 #[test]
363 fn new() {
364 let x: HistoryBuffer<u8, 4> = HistoryBuffer::new_with(1);
365 assert_eq!(x.len(), 4);
366 assert_eq!(x.as_slice(), [1; 4]);
367 assert_eq!(*x, [1; 4]);
368
369 let x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
370 assert_eq!(x.as_slice(), []);
371 }
372
373 #[test]
374 fn write() {
375 let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
376 x.write(1);
377 x.write(4);
378 assert_eq!(x.as_slice(), [1, 4]);
379
380 x.write(5);
381 x.write(6);
382 x.write(10);
383 assert_eq!(x.as_slice(), [10, 4, 5, 6]);
384
385 x.extend([11, 12].iter());
386 assert_eq!(x.as_slice(), [10, 11, 12, 6]);
387 }
388
389 #[test]
390 fn clear() {
391 let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new_with(1);
392 x.clear();
393 assert_eq!(x.as_slice(), []);
394
395 let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
396 x.clear_with(1);
397 assert_eq!(x.as_slice(), [1; 4]);
398 }
399
400 #[test]
401 fn clone() {
402 let mut x: HistoryBuffer<u8, 3> = HistoryBuffer::new();
403 for i in 0..10 {
404 assert_eq!(x.as_slice(), x.clone().as_slice());
405 x.write(i);
406 }
407
408 // Records number of clones locally and globally.
409 static GLOBAL: AtomicUsize = AtomicUsize::new(0);
410 #[derive(Default, PartialEq, Debug)]
411 struct InstrumentedClone(usize);
412
413 impl Clone for InstrumentedClone {
414 fn clone(&self) -> Self {
415 GLOBAL.fetch_add(1, Ordering::Relaxed);
416 Self(self.0 + 1)
417 }
418 }
419
420 let mut y: HistoryBuffer<InstrumentedClone, 2> = HistoryBuffer::new();
421 let _ = y.clone();
422 assert_eq!(GLOBAL.load(Ordering::Relaxed), 0);
423 y.write(InstrumentedClone(0));
424 assert_eq!(GLOBAL.load(Ordering::Relaxed), 0);
425 assert_eq!(y.clone().as_slice(), [InstrumentedClone(1)]);
426 assert_eq!(GLOBAL.load(Ordering::Relaxed), 1);
427 y.write(InstrumentedClone(0));
428 assert_eq!(GLOBAL.load(Ordering::Relaxed), 1);
429 assert_eq!(
430 y.clone().as_slice(),
431 [InstrumentedClone(1), InstrumentedClone(1)]
432 );
433 assert_eq!(GLOBAL.load(Ordering::Relaxed), 3);
434 assert_eq!(
435 y.clone().clone().clone().as_slice(),
436 [InstrumentedClone(3), InstrumentedClone(3)]
437 );
438 assert_eq!(GLOBAL.load(Ordering::Relaxed), 9);
439 }
440
441 #[test]
442 fn recent() {
443 let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
444 assert_eq!(x.recent(), None);
445
446 x.write(1);
447 x.write(4);
448 assert_eq!(x.recent(), Some(&4));
449
450 x.write(5);
451 x.write(6);
452 x.write(10);
453 assert_eq!(x.recent(), Some(&10));
454 }
455
456 #[test]
457 fn as_slice() {
458 let mut x: HistoryBuffer<u8, 4> = HistoryBuffer::new();
459
460 assert_eq!(x.as_slice(), []);
461
462 x.extend([1, 2, 3, 4, 5].iter());
463
464 assert_eq!(x.as_slice(), [5, 2, 3, 4]);
465 }
466
467 /// Test whether .as_slices() behaves as expected.
468 #[test]
469 fn as_slices() {
470 let mut buffer: HistoryBuffer<u8, 4> = HistoryBuffer::new();
471 let mut extend_then_assert = |extend: &[u8], assert: (&[u8], &[u8])| {
472 buffer.extend(extend);
473 assert_eq!(buffer.as_slices(), assert);
474 };
475
476 extend_then_assert(b"a", (b"a", b""));
477 extend_then_assert(b"bcd", (b"abcd", b""));
478 extend_then_assert(b"efg", (b"d", b"efg"));
479 extend_then_assert(b"h", (b"efgh", b""));
480 extend_then_assert(b"123456", (b"34", b"56"));
481 }
482
483 /// Test whether .as_slices() and .oldest_ordered() produce elements in the same order.
484 #[test]
485 fn as_slices_equals_ordered() {
486 let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
487
488 for n in 0..20 {
489 buffer.write(n);
490 let (head, tail) = buffer.as_slices();
491 assert_eq_iter(
492 [head, tail].iter().copied().flatten(),
493 buffer.oldest_ordered(),
494 )
495 }
496 }
497
498 #[test]
499 fn ordered() {
500 // test on an empty buffer
501 let buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
502 let mut iter = buffer.oldest_ordered();
503 assert_eq!(iter.next(), None);
504 assert_eq!(iter.next(), None);
505
506 // test on a un-filled buffer
507 let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
508 buffer.extend([1, 2, 3]);
509 assert_eq!(buffer.len(), 3);
510 assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3]);
511
512 // test on a filled buffer
513 let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
514 buffer.extend([0, 0, 0, 1, 2, 3, 4, 5, 6]);
515 assert_eq!(buffer.len(), 6);
516 assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3, 4, 5, 6]);
517
518 // comprehensive test all cases
519 for n in 0..50 {
520 const N: usize = 7;
521 let mut buffer: HistoryBuffer<u8, N> = HistoryBuffer::new();
522 buffer.extend(0..n);
523 assert_eq_iter(
524 buffer.oldest_ordered().copied(),
525 n.saturating_sub(N as u8)..n,
526 );
527 }
528 }
529
530 /// Compares two iterators item by item, making sure they stop at the same time.
531 fn assert_eq_iter<I: Eq + Debug>(
532 a: impl IntoIterator<Item = I>,
533 b: impl IntoIterator<Item = I>,
534 ) {
535 let mut a = a.into_iter();
536 let mut b = b.into_iter();
537
538 let mut i = 0;
539 loop {
540 let a_item = a.next();
541 let b_item = b.next();
542
543 assert_eq!(a_item, b_item, "{}", i);
544
545 i += 1;
546
547 if b_item.is_none() {
548 break;
549 }
550 }
551 }
552
553 #[test]
554 fn partial_eq() {
555 let mut x: HistoryBuffer<u8, 3> = HistoryBuffer::new();
556 let mut y: HistoryBuffer<u8, 3> = HistoryBuffer::new();
557 assert_eq!(x, y);
558 x.write(1);
559 assert_ne!(x, y);
560 y.write(1);
561 assert_eq!(x, y);
562 for _ in 0..4 {
563 x.write(2);
564 assert_ne!(x, y);
565 for i in 0..5 {
566 x.write(i);
567 y.write(i);
568 }
569 assert_eq!(
570 x,
571 y,
572 "{:?} {:?}",
573 x.iter().collect::<Vec<_>>(),
574 y.iter().collect::<Vec<_>>()
575 );
576 }
577 }
578}
579