uucore/features/
ringbuffer.rs

1// This file is part of the uutils coreutils package.
2//
3// For the full copyright and license information, please view the LICENSE
4// file that was distributed with this source code.
5//! A fixed-size ring buffer.
6use std::collections::VecDeque;
7
8/// A fixed-size ring buffer backed by a `VecDeque`.
9///
10/// If the ring buffer is not full, then calling the [`push_back`]
11/// method appends elements, as in a [`VecDeque`]. If the ring buffer
12/// is full, then calling [`push_back`] removes the element at the
13/// front of the buffer (in a first-in, first-out manner) before
14/// appending the new element to the back of the buffer.
15///
16/// Use [`from_iter`] to take the last `size` elements from an
17/// iterator.
18///
19/// # Examples
20///
21/// After exceeding the size limit, the oldest elements are dropped in
22/// favor of the newest element:
23///
24/// ```rust,ignore
25/// let mut buffer: RingBuffer<u8> = RingBuffer::new(2);
26/// buffer.push_back(0);
27/// buffer.push_back(1);
28/// buffer.push_back(2);
29/// assert_eq!(vec![1, 2], buffer.data);
30/// ```
31///
32/// Take the last `n` elements from an iterator:
33///
34/// ```rust,ignore
35/// let iter = [0, 1, 2].iter();
36/// let actual = RingBuffer::from_iter(iter, 2).data;
37/// let expected = VecDeque::from_iter([1, 2].iter());
38/// assert_eq!(expected, actual);
39/// ```
40///
41/// [`push_back`]: struct.RingBuffer.html#method.push_back
42/// [`from_iter`]: struct.RingBuffer.html#method.from_iter
43pub struct RingBuffer<T> {
44    /// The data stored in the ring buffer.
45    pub data: VecDeque<T>,
46
47    /// The maximum number of elements that the ring buffer can hold.
48    size: usize,
49}
50
51impl<T> RingBuffer<T> {
52    /// Create a new ring buffer with a maximum size of `size`.
53    pub fn new(size: usize) -> Self {
54        Self {
55            data: VecDeque::new(),
56            size,
57        }
58    }
59
60    /// Create a new ring buffer from an iterator.
61    pub fn from_iter(iter: impl Iterator<Item = T>, size: usize) -> Self {
62        let mut ring_buffer = Self::new(size);
63        for value in iter {
64            ring_buffer.push_back(value);
65        }
66        ring_buffer
67    }
68
69    /// Append a value to the end of the ring buffer.
70    ///
71    /// If the ring buffer is not full, this method return [`None`]. If
72    /// the ring buffer is full, appending a new element will cause the
73    /// oldest element to be evicted. In that case this method returns
74    /// that element, or `None`.
75    ///
76    /// In the special case where the size limit is zero, each call to
77    /// this method with input `value` returns `Some(value)`, because
78    /// the input is immediately evicted.
79    ///
80    /// # Examples
81    ///
82    /// Appending an element when the buffer is full returns the oldest
83    /// element:
84    ///
85    /// ```rust,ignore
86    /// let mut buf = RingBuffer::new(3);
87    /// assert_eq!(None, buf.push_back(0));
88    /// assert_eq!(None, buf.push_back(1));
89    /// assert_eq!(None, buf.push_back(2));
90    /// assert_eq!(Some(0), buf.push_back(3));
91    /// ```
92    ///
93    /// If the size limit is zero, then this method always returns the
94    /// input value:
95    ///
96    /// ```rust,ignore
97    /// let mut buf = RingBuffer::new(0);
98    /// assert_eq!(Some(0), buf.push_back(0));
99    /// assert_eq!(Some(1), buf.push_back(1));
100    /// assert_eq!(Some(2), buf.push_back(2));
101    /// ```
102    pub fn push_back(&mut self, value: T) -> Option<T> {
103        if self.size == 0 {
104            return Some(value);
105        }
106        let result = if self.size <= self.data.len() {
107            self.data.pop_front()
108        } else {
109            None
110        };
111        self.data.push_back(value);
112        result
113    }
114}
115
116#[cfg(test)]
117mod tests {
118
119    use crate::ringbuffer::RingBuffer;
120    use std::collections::VecDeque;
121
122    #[test]
123    fn test_size_limit_zero() {
124        let mut buf = RingBuffer::new(0);
125        assert_eq!(Some(0), buf.push_back(0));
126        assert_eq!(Some(1), buf.push_back(1));
127        assert_eq!(Some(2), buf.push_back(2));
128    }
129
130    #[test]
131    fn test_evict_oldest() {
132        let mut buf = RingBuffer::new(2);
133        assert_eq!(None, buf.push_back(0));
134        assert_eq!(None, buf.push_back(1));
135        assert_eq!(Some(0), buf.push_back(2));
136    }
137
138    #[test]
139    fn test_from_iter() {
140        let iter = [0, 1, 2].iter();
141        let actual = RingBuffer::from_iter(iter, 2).data;
142        let expected: VecDeque<&i32> = [1, 2].iter().collect();
143        assert_eq!(expected, actual);
144    }
145}
uucore/features/ringbuffer.rs

uucore/features/
ringbuffer.rs
