| 1 |
//! # Ring buffer tools. |
| 2 |
use core::fmt; |
| 3 |
use core::ops::Index; |
| 4 |
|
| 5 |
/// A ring buffer trait. |
| 6 |
#[allow(dead_code)] |
| 7 |
pub trait RingBuffer: Default + Index<usize, Output=u8> { |
| 8 |
/// The size of the buffer in bytes. |
| 9 |
const BUFFER_SIZE: usize; |
| 10 |
/// The current value of the internal cursor. |
| 11 |
fn cursor(&self) -> usize; |
| 12 |
/// Allows to set the current value of the internal cursor. |
| 13 |
fn set_cursor(&mut self, pos: isize); |
| 14 |
/// Pushes the new byte value to the buffer, overwriting the oldest one. |
| 15 |
fn push(&mut self, byte: u8); |
| 16 |
/// Returns an iterator which will yield consecutive bytes from the buffer starting at `-offset` |
| 17 |
/// from the last element. |
| 18 |
/// |
| 19 |
/// `offset` = 0 indicates the last element written to the buffer. |
| 20 |
/// |
| 21 |
/// At each iteration the yielded value is also being pushed to the ring buffer. |
| 22 |
fn iter_from_offset(&mut self, offset: usize) -> HistoryIter<'_, Self>; |
| 23 |
/// Returns an iterator which will yield consecutive bytes from the buffer starting at `pos`. |
| 24 |
/// |
| 25 |
/// At each iteration the yielded value is also being pushed to the ring buffer. |
| 26 |
fn iter_from_pos(&mut self, pos: usize) -> HistoryIter<'_, Self>; |
| 27 |
} |
| 28 |
|
| 29 |
/// A generic ring buffer implementation using arrays of the size of the power of two as internal buffers. |
| 30 |
/// |
| 31 |
/// `N` must be a power of 2. |
| 32 |
#[derive(Clone)] |
| 33 |
pub struct RingArrayBuf<const N: usize> { |
| 34 |
buffer: [u8; N], |
| 35 |
cursor: usize |
| 36 |
} |
| 37 |
|
| 38 |
impl<const N: usize> fmt::Debug for RingArrayBuf<N> { |
| 39 |
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| 40 |
f.debug_struct("RingArrayBuf") |
| 41 |
.field("buffer", &N) |
| 42 |
.field("cursor", &self.cursor) |
| 43 |
.finish() |
| 44 |
} |
| 45 |
} |
| 46 |
|
| 47 |
/// The ring buffer history iterator. |
| 48 |
pub struct HistoryIter<'a, T> { |
| 49 |
index: usize, |
| 50 |
ringbuf: &'a mut T |
| 51 |
} |
| 52 |
|
| 53 |
impl<'a, T: RingBuffer> Iterator for HistoryIter<'a, T> { |
| 54 |
type Item = u8; |
| 55 |
|
| 56 |
#[inline] |
| 57 |
fn next(&mut self) -> Option<Self::Item> { |
| 58 |
let index = self.index; |
| 59 |
let res = self.ringbuf[index]; |
| 60 |
self.index = index.wrapping_add(1); |
| 61 |
self.ringbuf.push(res); |
| 62 |
Some(res) |
| 63 |
} |
| 64 |
} |
| 65 |
|
| 66 |
macro_rules! index_mask { |
| 67 |
($size:expr) => { ($size - 1) }; |
| 68 |
} |
| 69 |
|
| 70 |
impl<const N: usize> Default for RingArrayBuf<N> { |
| 71 |
fn default() -> Self { |
| 72 |
assert!(N.is_power_of_two(), "invalid RingArrayBuf size: should be a power of two!"); |
| 73 |
let buffer = [b' '; N]; |
| 74 |
RingArrayBuf { buffer, cursor: 0 } |
| 75 |
} |
| 76 |
} |
| 77 |
|
| 78 |
impl<const N: usize> Index<usize> for RingArrayBuf<N> { |
| 79 |
type Output = u8; |
| 80 |
|
| 81 |
#[inline(always)] |
| 82 |
fn index(&self, index: usize) -> &Self::Output { |
| 83 |
self.buffer.index(index & index_mask!(N)) |
| 84 |
} |
| 85 |
} |
| 86 |
|
| 87 |
impl<const N: usize> RingBuffer for RingArrayBuf<N> { |
| 88 |
const BUFFER_SIZE: usize = N; |
| 89 |
|
| 90 |
#[inline(always)] |
| 91 |
fn cursor(&self) -> usize { |
| 92 |
self.cursor |
| 93 |
} |
| 94 |
|
| 95 |
fn set_cursor(&mut self, pos: isize) { |
| 96 |
self.cursor = pos as usize & index_mask!(N); |
| 97 |
} |
| 98 |
|
| 99 |
fn push(&mut self, byte: u8) { |
| 100 |
let index = self.cursor; |
| 101 |
self.buffer[index & index_mask!(N)] = byte; |
| 102 |
self.cursor = (index + 1) & index_mask!(N); |
| 103 |
} |
| 104 |
|
| 105 |
fn iter_from_offset(&mut self, offset: usize) -> HistoryIter<'_, Self> { |
| 106 |
let offset = (offset & index_mask!(N)) + 1; |
| 107 |
let index = self.cursor + N - offset; |
| 108 |
HistoryIter { index, ringbuf: self } |
| 109 |
} |
| 110 |
|
| 111 |
fn iter_from_pos(&mut self, pos: usize) -> HistoryIter<'_, Self> { |
| 112 |
let index = pos & index_mask!(N); |
| 113 |
HistoryIter { index, ringbuf: self } |
| 114 |
} |
| 115 |
} |
| 116 |
|
| 117 |
#[cfg(feature = "std")] |
| 118 |
#[cfg(test)] |
| 119 |
mod tests { |
| 120 |
use super::*; |
| 121 |
|
| 122 |
type TestRingBuffer = RingArrayBuf<32>; |
| 123 |
|
| 124 |
#[test] |
| 125 |
fn ringbuf_works() { |
| 126 |
let mut buffer = TestRingBuffer::default(); |
| 127 |
assert_eq!(buffer.cursor(), 0); |
| 128 |
for i in 0..32 { |
| 129 |
assert_eq!(buffer[i], b' '); |
| 130 |
} |
| 131 |
buffer.push(b'!'); |
| 132 |
assert_eq!(buffer.cursor(), 1); |
| 133 |
assert_eq!(buffer[0], b'!'); |
| 134 |
assert_eq!(buffer[1], b' '); |
| 135 |
for i in 0..32 { |
| 136 |
buffer.push(i as u8); |
| 137 |
assert_eq!(buffer.cursor(), (i + 2) % 32); |
| 138 |
assert_eq!(buffer[(i + 1) % 32], i as u8); |
| 139 |
} |
| 140 |
for i in 0..32 { |
| 141 |
let mut buffer = TestRingBuffer::default(); |
| 142 |
for _ in 0..i { |
| 143 |
buffer.push(b'.'); |
| 144 |
} |
| 145 |
assert_eq!(buffer.cursor(), i); |
| 146 |
for n in 0..32 { |
| 147 |
buffer.push(n); |
| 148 |
} |
| 149 |
assert_eq!(buffer.cursor(), i); |
| 150 |
for _ in 0..2 { |
| 151 |
let vec: Vec<_> = buffer.iter_from_offset(31).take(32).collect(); |
| 152 |
assert_eq!(buffer.cursor(), i); |
| 153 |
assert_eq!(vec, (0..32).collect::<Vec<u8>>()); |
| 154 |
} |
| 155 |
let mut hist = buffer.iter_from_offset(15); |
| 156 |
let mut vec = Vec::new(); |
| 157 |
vec.extend(hist.by_ref().take(5)); |
| 158 |
assert_eq!(vec, (16..16+5).collect::<Vec<u8>>()); |
| 159 |
let mut hist = buffer.iter_from_offset(15).take(11); |
| 160 |
vec.extend(hist.by_ref()); |
| 161 |
assert_eq!(vec, (16..32).collect::<Vec<u8>>()); |
| 162 |
} |
| 163 |
} |
| 164 |
} |