ring_vec/
lib.rs

1#![no_std]
2extern crate alloc;
3use alloc::vec::Vec;
4
5use core::cmp::min;
6use core::fmt::Debug;
7
8// It's basically a queue with a maximum capacity that wraps around in
9// the internal storage.
10#[derive(Debug)]
11pub struct RingVec<T: Debug> {
12    inner: Vec<Option<T>>,
13    capacity: usize, // in case we haven't allocated it all
14    start: usize,
15    len: usize, // number of items present
16}
17
18impl<T: Debug> RingVec<T> {
19
20    /// Creates an empty RingVec
21    pub fn new(capacity: usize) -> RingVec<T> {
22        if capacity > 0 {
23            RingVec { inner: Vec::new(), capacity, start: 0, len: 0 }
24        } else {
25            panic!("RingVec requires a nonzero capacity");
26        }
27    }
28
29    /// Creates an empty RingVec with preallocated storage
30    pub fn new_preallocated(capacity: usize) -> RingVec<T> {
31        let inner = Vec::with_capacity(capacity);
32        RingVec { inner, capacity, start: 0, len: 0 }
33    }
34
35    /// True if there is no spare capacity
36    pub fn is_full(&self) -> bool { self.len == self.capacity }
37
38    /// Returns the number of items in the RingVec
39    pub fn len(&self) -> usize { self.inner.len() - self.start }
40
41    /// Returns the maximum possible number of items.
42    pub fn capacity(&self) -> usize { self.capacity }
43
44    /// Returns a ref to the head of the queue, if any.
45    pub fn peek(&self) -> Option<&T> {
46        if self.len > 0 { self.inner[self.start].as_ref() }
47        else { None }
48    }
49
50    /// Returns the next item in the queue, if any.
51    pub fn pop(&mut self) -> Option<T> {
52        if self.len > 0 {
53            let start = self.start;
54            self.start = (self.start + 1) % self.capacity;
55            self.len -= 1;
56            let ret = self.inner[start].take();
57            ret
58        } else { None }
59    }
60
61    /// Appends an item if there is space.
62    pub fn push(&mut self, item: T) -> Result<(), T> {
63        if self.len < self.capacity {
64            let end = self.start + self.len;
65            if end >= self.inner.capacity() {
66                self.inner.push(Some(item));
67            } else {
68                self.inner[end % self.capacity] = Some(item);
69            }
70            self.len += 1;
71            Ok(())
72        } else {
73            Err(item)
74        }
75    }
76
77    /// Empties the RingVec, optionally shrinking the storage.
78    pub fn empty(&mut self) {
79        self.inner.clear();
80        self.start = 0;
81        self.len = 0;
82    }
83
84    /// Attempts to reduce memory usage.
85    pub fn shrink_to_fit(&mut self) {
86        if self.len == self.capacity { return; }
87        let mut new = Vec::with_capacity(self.len());
88        let end = self.start + self.len;
89        for i in self.start..min(end, self.capacity) {
90            new.push(self.inner[i].take());
91        }
92        if end > self.capacity {
93            for i in 0..(end - self.capacity) {
94                new.push(self.inner[i].take());
95            }
96        }
97        self.inner = new;
98    }
99
100}
101
102#[cfg(test)]
103mod tests {
104
105    use crate::RingVec;
106
107    #[test]
108    fn works() {
109        let mut q: RingVec<usize> = RingVec::new(1);
110        assert_eq!(q.peek(), None);
111        assert_eq!(q.pop(), None);
112        assert_eq!(q.push(1), Ok(()));
113        assert_eq!(q.peek(), Some(&1));
114        assert_eq!(q.pop(), Some(1));
115        assert_eq!(q.peek(), None);
116        assert_eq!(q.pop(), None);
117        assert_eq!(q.push(2), Ok(()));
118        assert_eq!(q.peek(), Some(&2));
119        assert_eq!(q.push(3), Err(3));
120        assert_eq!(q.pop(), Some(2));
121        assert_eq!(q.push(4), Ok(()));
122        assert_eq!(q.peek(), Some(&4));
123        assert_eq!(q.pop(), Some(4));
124        assert_eq!(q.peek(), None);
125        assert_eq!(q.pop(), None);
126        assert_eq!(q.peek(), None);
127    }
128
129}
ring_vec/lib.rs

ring_vec/
lib.rs
