matrix_sdk_common/
ring_buffer.rs

1// Copyright 2023 The Matrix.org Foundation C.I.C.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::{
16    collections::{
17        vec_deque::{Drain, Iter, IterMut},
18        VecDeque,
19    },
20    num::NonZeroUsize,
21    ops::RangeBounds,
22};
23
24use serde::{Deserialize, Serialize};
25
26/// A simple fixed-size ring buffer implementation.
27///
28/// A size is provided on creation, and the ring buffer reserves that much
29/// space, and never reallocates.
30#[derive(Clone, Debug, PartialEq, Deserialize, Serialize)]
31#[serde(transparent)]
32pub struct RingBuffer<T> {
33    inner: VecDeque<T>,
34}
35
36impl<T> RingBuffer<T> {
37    /// Create a ring buffer with the supplied capacity, reserving it so we
38    /// never need to reallocate.
39    pub fn new(size: NonZeroUsize) -> Self {
40        Self { inner: VecDeque::with_capacity(size.into()) }
41    }
42
43    /// Returns the number of items that are stored in this ring buffer.
44    ///
45    /// This is the dynamic size indicating how many items are held in the
46    /// buffer, not the fixed capacity.
47    pub fn len(&self) -> usize {
48        self.inner.len()
49    }
50
51    /// Returns true if the ring buffer contains no elements.
52    pub fn is_empty(&self) -> bool {
53        self.inner.is_empty()
54    }
55
56    /// Provides a reference to the element at the given index.
57    ///
58    /// Element at index zero is the "front" i.e. one that will be returned if
59    /// we call pop().
60    pub fn get(&self, index: usize) -> Option<&T> {
61        self.inner.get(index)
62    }
63
64    /// Appends an element to the back of the ring buffer
65    pub fn push(&mut self, value: T) {
66        if self.inner.len() == self.inner.capacity() {
67            self.inner.pop_front();
68        }
69
70        self.inner.push_back(value);
71    }
72
73    /// Removes the first element and returns it, or None if the ring buffer is
74    /// empty.
75    pub fn pop(&mut self) -> Option<T> {
76        self.inner.pop_front()
77    }
78
79    /// Removes and returns one specific element at `index` if it exists,
80    /// otherwise it returns `None`.
81    pub fn remove(&mut self, index: usize) -> Option<T> {
82        self.inner.remove(index)
83    }
84
85    /// Returns an iterator that provides elements in front-to-back order, i.e.
86    /// the same order you would get if you repeatedly called pop().
87    pub fn iter(&self) -> Iter<'_, T> {
88        self.inner.iter()
89    }
90
91    /// Returns a mutable iterator that provides elements in front-to-back
92    /// order, i.e. the same order you would get if you repeatedly called
93    /// pop().
94    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
95        self.inner.iter_mut()
96    }
97
98    /// Returns an iterator that drains its items.
99    pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>
100    where
101        R: RangeBounds<usize>,
102    {
103        self.inner.drain(range)
104    }
105
106    /// Clears the ring buffer, removing all values. This does not affect the
107    /// capacity.
108    pub fn clear(&mut self) {
109        self.inner.clear();
110    }
111
112    /// Returns the total number of elements the `RingBuffer` can hold.
113    pub fn capacity(&self) -> usize {
114        self.inner.capacity()
115    }
116
117    /// Retains only the elements specified by the predicate.
118    pub fn retain<F>(&mut self, predicate: F)
119    where
120        F: FnMut(&T) -> bool,
121    {
122        self.inner.retain(predicate)
123    }
124}
125
126impl<U> Extend<U> for RingBuffer<U> {
127    fn extend<T: IntoIterator<Item = U>>(&mut self, iter: T) {
128        for item in iter.into_iter() {
129            self.push(item);
130        }
131    }
132}
133
134#[cfg(test)]
135mod tests {
136    use std::{num::NonZeroUsize, ops::Not};
137
138    use super::RingBuffer;
139
140    #[test]
141    pub fn test_fixed_size() {
142        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
143
144        assert!(ring_buffer.is_empty());
145
146        ring_buffer.push(1);
147        ring_buffer.push(2);
148        ring_buffer.push(3);
149
150        assert!(ring_buffer.is_empty().not());
151
152        assert_eq!(ring_buffer.get(0), Some(&1));
153        assert_eq!(ring_buffer.get(1), Some(&2));
154        assert_eq!(ring_buffer.get(2), Some(&3));
155
156        ring_buffer.push(4);
157        ring_buffer.push(5);
158
159        assert_eq!(ring_buffer.get(0), Some(&1));
160        assert_eq!(ring_buffer.get(1), Some(&2));
161        assert_eq!(ring_buffer.get(2), Some(&3));
162        assert_eq!(ring_buffer.get(3), Some(&4));
163        assert_eq!(ring_buffer.get(4), Some(&5));
164
165        ring_buffer.push(6);
166
167        assert_eq!(ring_buffer.get(0), Some(&2));
168        assert_eq!(ring_buffer.get(1), Some(&3));
169        assert_eq!(ring_buffer.get(2), Some(&4));
170        assert_eq!(ring_buffer.get(3), Some(&5));
171        assert_eq!(ring_buffer.get(4), Some(&6));
172    }
173
174    #[test]
175    pub fn test_push_and_pop_and_remove_and_length() {
176        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(3).unwrap());
177
178        ring_buffer.push(1);
179        assert_eq!(ring_buffer.len(), 1);
180
181        ring_buffer.push(2);
182        assert_eq!(ring_buffer.len(), 2);
183
184        ring_buffer.push(3);
185        assert_eq!(ring_buffer.len(), 3);
186
187        assert_eq!(ring_buffer.pop(), Some(1));
188        assert_eq!(ring_buffer.len(), 2);
189        assert_eq!(ring_buffer.get(0), Some(&2));
190        assert_eq!(ring_buffer.get(1), Some(&3));
191        assert_eq!(ring_buffer.get(2), None);
192
193        assert_eq!(ring_buffer.pop(), Some(2));
194        assert_eq!(ring_buffer.len(), 1);
195        assert_eq!(ring_buffer.get(0), Some(&3));
196        assert_eq!(ring_buffer.get(1), None);
197        assert_eq!(ring_buffer.get(2), None);
198
199        assert_eq!(ring_buffer.pop(), Some(3));
200        assert_eq!(ring_buffer.len(), 0);
201        assert_eq!(ring_buffer.get(0), None);
202        assert_eq!(ring_buffer.get(1), None);
203        assert_eq!(ring_buffer.get(2), None);
204
205        assert_eq!(ring_buffer.pop(), None);
206
207        ring_buffer.push(1);
208        ring_buffer.push(2);
209        ring_buffer.push(3);
210        assert_eq!(ring_buffer.len(), 3);
211        assert_eq!(ring_buffer.get(0), Some(&1));
212        assert_eq!(ring_buffer.get(1), Some(&2));
213        assert_eq!(ring_buffer.get(2), Some(&3));
214
215        assert_eq!(ring_buffer.remove(1), Some(2));
216        assert_eq!(ring_buffer.len(), 2);
217        assert_eq!(ring_buffer.get(0), Some(&1));
218        assert_eq!(ring_buffer.get(1), Some(&3));
219        assert_eq!(ring_buffer.get(2), None);
220
221        assert_eq!(ring_buffer.remove(0), Some(1));
222        assert_eq!(ring_buffer.len(), 1);
223        assert_eq!(ring_buffer.get(0), Some(&3));
224        assert_eq!(ring_buffer.get(1), None);
225        assert_eq!(ring_buffer.get(2), None);
226
227        assert_eq!(ring_buffer.remove(1), None);
228        assert_eq!(ring_buffer.remove(10), None);
229    }
230
231    #[test]
232    fn test_iter() {
233        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
234
235        ring_buffer.push(1);
236        ring_buffer.push(2);
237        ring_buffer.push(3);
238
239        let as_vec = ring_buffer.iter().copied().collect::<Vec<_>>();
240        assert_eq!(as_vec, [1, 2, 3]);
241
242        let first_entry = ring_buffer.iter_mut().next().unwrap();
243        *first_entry = 42;
244
245        let as_vec = ring_buffer.iter().copied().collect::<Vec<_>>();
246        assert_eq!(as_vec, [42, 2, 3]);
247    }
248
249    #[test]
250    fn test_drain() {
251        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
252
253        ring_buffer.push(1);
254        ring_buffer.push(2);
255        ring_buffer.push(3);
256        ring_buffer.push(4);
257        ring_buffer.push(5);
258
259        let drained = ring_buffer.drain(0..=2).collect::<Vec<_>>();
260        let left = ring_buffer.iter().map(ToOwned::to_owned).collect::<Vec<_>>();
261
262        assert_eq!(drained, &[1, 2, 3]);
263        assert_eq!(left, &[4, 5]);
264
265        ring_buffer.drain(..);
266
267        assert!(ring_buffer.is_empty());
268    }
269
270    #[test]
271    fn test_clear_on_empty_buffer_is_a_noop() {
272        let mut ring_buffer: RingBuffer<u8> = RingBuffer::new(NonZeroUsize::new(3).unwrap());
273        ring_buffer.clear();
274        assert_eq!(ring_buffer.len(), 0);
275    }
276
277    #[test]
278    fn test_clear_removes_all_items() {
279        // Given a RingBuffer that has been used
280        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(3).unwrap());
281        ring_buffer.push(4);
282        ring_buffer.push(5);
283        ring_buffer.push(6);
284        ring_buffer.pop();
285        // Sanity: there are 2 items
286        assert_eq!(ring_buffer.len(), 2);
287
288        // When I clear it
289        ring_buffer.clear();
290
291        // Then it is empty
292        assert_eq!(ring_buffer.len(), 0);
293        assert_eq!(ring_buffer.get(0), None);
294        assert_eq!(ring_buffer.pop(), None);
295    }
296
297    #[test]
298    fn test_clear_does_not_affect_capacity() {
299        // Given a RingBuffer that has been used
300        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(3).unwrap());
301        ring_buffer.push(4);
302        ring_buffer.push(5);
303        ring_buffer.push(6);
304        ring_buffer.pop();
305        // Sanity: capacity is 3
306        assert_eq!(ring_buffer.capacity(), 3);
307
308        // When I clear it
309        ring_buffer.clear();
310
311        // Then its capacity is still 3
312        assert_eq!(ring_buffer.capacity(), 3);
313    }
314
315    #[test]
316    fn test_capacity_is_what_we_passed_to_new() {
317        // Given a RingBuffer
318        let ring_buffer = RingBuffer::<i32>::new(NonZeroUsize::new(13).unwrap());
319        // When I ask for its capacity I get what I provided at the start
320        assert_eq!(ring_buffer.capacity(), 13);
321    }
322
323    #[test]
324    fn test_capacity_is_not_affected_by_overflowing() {
325        // Given a RingBuffer that has been used
326        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(3).unwrap());
327        ring_buffer.push(4);
328        ring_buffer.push(5);
329        ring_buffer.push(6);
330        ring_buffer.push(7);
331        ring_buffer.pop();
332        ring_buffer.push(8);
333        ring_buffer.push(9);
334
335        // When I ask for its capacity, it gives me what I gave it initially
336        assert_eq!(ring_buffer.capacity(), 3);
337
338        // And even if I extend it
339        ring_buffer.extend(vec![10, 11, 12, 13, 14, 15]);
340
341        // Then its capacity is still 3
342        assert_eq!(ring_buffer.capacity(), 3);
343    }
344
345    #[test]
346    fn test_roundtrip_serialization() {
347        // Given a RingBuffer
348        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(3).unwrap());
349        ring_buffer.push("1".to_owned());
350        ring_buffer.push("2".to_owned());
351
352        // When I serialize it
353        let json = serde_json::to_string(&ring_buffer).expect("serialisation failed");
354        // Sanity: the JSON looks as we expect
355        assert_eq!(json, r#"["1","2"]"#);
356
357        // And deserialize it
358        let new_ring_buffer: RingBuffer<String> =
359            serde_json::from_str(&json).expect("deserialisation failed");
360
361        // Then I get back the same as I started with
362        assert_eq!(ring_buffer, new_ring_buffer);
363    }
364
365    #[test]
366    fn test_extending_an_empty_ringbuffer_adds_the_items() {
367        // Given a RingBuffer
368        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
369
370        // When I extend it
371        ring_buffer.extend(vec!["a".to_owned(), "b".to_owned()]);
372
373        // Then the items are added
374        assert_eq!(ring_buffer.iter().map(String::as_str).collect::<Vec<_>>(), vec!["a", "b"]);
375    }
376
377    #[test]
378    fn test_extend_adds_items_to_the_end() {
379        // Given a RingBuffer with something in it
380        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
381        ring_buffer.push("1".to_owned());
382        ring_buffer.push("2".to_owned());
383
384        // When I extend it
385        ring_buffer.extend(vec!["3".to_owned(), "4".to_owned()]);
386
387        // Then the items are added on the end
388        assert_eq!(
389            ring_buffer.iter().map(String::as_str).collect::<Vec<_>>(),
390            vec!["1", "2", "3", "4"]
391        );
392    }
393
394    #[test]
395    fn test_extend_does_not_overflow_max_length() {
396        // Given a RingBuffer with something in it
397        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
398        ring_buffer.push("1".to_owned());
399        ring_buffer.push("2".to_owned());
400
401        // When I extend it with too many items
402        ring_buffer.extend(vec![
403            "3".to_owned(),
404            "4".to_owned(),
405            "5".to_owned(),
406            "6".to_owned(),
407            "7".to_owned(),
408        ]);
409
410        // Then some of previous items are gone, keeping the length to the max
411        assert_eq!(
412            ring_buffer.iter().map(String::as_str).collect::<Vec<_>>(),
413            vec!["3", "4", "5", "6", "7"]
414        );
415    }
416
417    #[test]
418    fn test_extending_a_full_ringbuffer_preserves_max_length() {
419        // Given a full RingBuffer with something in it
420        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(2).unwrap());
421        ring_buffer.push("1".to_owned());
422        ring_buffer.push("2".to_owned());
423
424        // When I extend it with lots of items
425        ring_buffer.extend(vec![
426            "3".to_owned(),
427            "4".to_owned(),
428            "5".to_owned(),
429            "6".to_owned(),
430            "7".to_owned(),
431        ]);
432
433        // Then only the last N items remain
434        assert_eq!(ring_buffer.iter().map(String::as_str).collect::<Vec<_>>(), vec!["6", "7"]);
435    }
436
437    #[test]
438    fn test_retain() {
439        let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(2).unwrap());
440        ring_buffer.push(1);
441        ring_buffer.push(2);
442
443        ring_buffer.retain(|v| v % 2 == 0);
444
445        assert_eq!(ring_buffer.len(), 1);
446        assert_eq!(ring_buffer.get(0).copied().unwrap(), 2);
447    }
448}
matrix_sdk_common/ring_buffer.rs

matrix_sdk_common/
ring_buffer.rs
