Debian Codegraph @

.cargo/vendor/delharc/src/ringbuf.rs

raw
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 }