ringbuffer/with_alloc/
alloc_ringbuffer.rs

1use core::ops::{Index, IndexMut};
2
3use crate::ringbuffer_trait::{
4    RingBuffer, RingBufferIntoIterator, RingBufferIterator, RingBufferMutIterator,
5};
6
7extern crate alloc;
8
9// We need boxes, so depend on alloc
10use crate::{mask_and, GrowableAllocRingBuffer};
11use core::ptr;
12
13/// The `AllocRingBuffer` is a `RingBuffer` which is based on a Vec. This means it allocates at runtime
14/// on the heap, and therefore needs the [`alloc`] crate. This struct and therefore the dependency on
15/// alloc can be disabled by disabling the `alloc` (default) feature.
16///
17/// # Example
18/// ```
19/// use ringbuffer::{AllocRingBuffer, RingBuffer};
20///
21/// let mut buffer = AllocRingBuffer::new(2);
22///
23/// // First entry of the buffer is now 5.
24/// buffer.push(5);
25///
26/// // The last item we pushed is 5
27/// assert_eq!(buffer.back(), Some(&5));
28///
29/// // Second entry is now 42.
30/// buffer.push(42);
31///
32/// assert_eq!(buffer.peek(), Some(&5));
33/// assert!(buffer.is_full());
34///
35/// // Because capacity is reached the next push will be the first item of the buffer.
36/// buffer.push(1);
37/// assert_eq!(buffer.to_vec(), vec![42, 1]);
38/// ```
39#[derive(Debug)]
40pub struct AllocRingBuffer<T> {
41    buf: *mut T,
42
43    // the size of the allocation. Next power of 2 up from the capacity
44    size: usize,
45    // maximum number of elements actually allowed in the ringbuffer.
46    // Always less than or equal than the size
47    capacity: usize,
48
49    readptr: usize,
50    writeptr: usize,
51}
52
53// SAFETY: all methods that require mutable access take &mut,
54// being send and sync was the old behavior but broke when we switched to *mut T.
55unsafe impl<T: Sync> Sync for AllocRingBuffer<T> {}
56unsafe impl<T: Send> Send for AllocRingBuffer<T> {}
57
58impl<T, const N: usize> From<[T; N]> for AllocRingBuffer<T> {
59    fn from(value: [T; N]) -> Self {
60        let mut rb = Self::new(value.len());
61        rb.extend(value);
62        rb
63    }
64}
65
66impl<T: Clone, const N: usize> From<&[T; N]> for AllocRingBuffer<T> {
67    // the cast here is actually not trivial
68    #[allow(trivial_casts)]
69    fn from(value: &[T; N]) -> Self {
70        Self::from(value as &[T])
71    }
72}
73
74impl<T: Clone> From<&[T]> for AllocRingBuffer<T> {
75    fn from(value: &[T]) -> Self {
76        let mut rb = Self::new(value.len());
77        rb.extend(value.iter().cloned());
78        rb
79    }
80}
81
82impl<T> From<GrowableAllocRingBuffer<T>> for AllocRingBuffer<T> {
83    fn from(mut v: GrowableAllocRingBuffer<T>) -> AllocRingBuffer<T> {
84        let mut rb = AllocRingBuffer::new(v.len());
85        rb.extend(v.drain());
86        rb
87    }
88}
89
90impl<T: Clone> From<&mut [T]> for AllocRingBuffer<T> {
91    fn from(value: &mut [T]) -> Self {
92        Self::from(&*value)
93    }
94}
95
96impl<T: Clone, const CAP: usize> From<&mut [T; CAP]> for AllocRingBuffer<T> {
97    fn from(value: &mut [T; CAP]) -> Self {
98        Self::from(value.clone())
99    }
100}
101
102impl<T> From<alloc::vec::Vec<T>> for AllocRingBuffer<T> {
103    fn from(value: alloc::vec::Vec<T>) -> Self {
104        let mut res = AllocRingBuffer::new(value.len());
105        res.extend(value);
106        res
107    }
108}
109
110impl<T> From<alloc::collections::VecDeque<T>> for AllocRingBuffer<T> {
111    fn from(value: alloc::collections::VecDeque<T>) -> Self {
112        let mut res = AllocRingBuffer::new(value.len());
113        res.extend(value);
114        res
115    }
116}
117
118impl<T> From<alloc::collections::LinkedList<T>> for AllocRingBuffer<T> {
119    fn from(value: alloc::collections::LinkedList<T>) -> Self {
120        let mut res = AllocRingBuffer::new(value.len());
121        res.extend(value);
122        res
123    }
124}
125
126impl From<alloc::string::String> for AllocRingBuffer<char> {
127    fn from(value: alloc::string::String) -> Self {
128        let mut res = AllocRingBuffer::new(value.len());
129        res.extend(value.chars());
130        res
131    }
132}
133
134impl From<&str> for AllocRingBuffer<char> {
135    fn from(value: &str) -> Self {
136        let mut res = AllocRingBuffer::new(value.len());
137        res.extend(value.chars());
138        res
139    }
140}
141
142impl<T, const CAP: usize> From<crate::ConstGenericRingBuffer<T, CAP>> for AllocRingBuffer<T> {
143    fn from(mut value: crate::ConstGenericRingBuffer<T, CAP>) -> Self {
144        let mut res = AllocRingBuffer::new(value.len());
145        res.extend(value.drain());
146        res
147    }
148}
149
150impl<T> Drop for AllocRingBuffer<T> {
151    fn drop(&mut self) {
152        self.drain().for_each(drop);
153
154        let layout = alloc::alloc::Layout::array::<T>(self.size).unwrap();
155        unsafe {
156            alloc::alloc::dealloc(self.buf as *mut u8, layout);
157        }
158    }
159}
160
161impl<T: Clone> Clone for AllocRingBuffer<T> {
162    fn clone(&self) -> Self {
163        debug_assert_ne!(self.capacity, 0);
164
165        let mut new = Self::new(self.capacity);
166        self.iter().cloned().for_each(|i| new.push(i));
167        new
168    }
169}
170
171impl<T: PartialEq> PartialEq for AllocRingBuffer<T> {
172    fn eq(&self, other: &Self) -> bool {
173        self.capacity == other.capacity
174            && self.len() == other.len()
175            && self.iter().zip(other.iter()).all(|(a, b)| a == b)
176    }
177}
178
179impl<T: Eq + PartialEq> Eq for AllocRingBuffer<T> {}
180
181impl<T> IntoIterator for AllocRingBuffer<T> {
182    type Item = T;
183    type IntoIter = RingBufferIntoIterator<T, Self>;
184
185    fn into_iter(self) -> Self::IntoIter {
186        RingBufferIntoIterator::new(self)
187    }
188}
189
190impl<'a, T> IntoIterator for &'a AllocRingBuffer<T> {
191    type Item = &'a T;
192    type IntoIter = RingBufferIterator<'a, T, AllocRingBuffer<T>>;
193
194    fn into_iter(self) -> Self::IntoIter {
195        self.iter()
196    }
197}
198
199impl<'a, T> IntoIterator for &'a mut AllocRingBuffer<T> {
200    type Item = &'a mut T;
201    type IntoIter = RingBufferMutIterator<'a, T, AllocRingBuffer<T>>;
202
203    fn into_iter(self) -> Self::IntoIter {
204        self.iter_mut()
205    }
206}
207
208impl<T> Extend<T> for AllocRingBuffer<T> {
209    fn extend<A: IntoIterator<Item = T>>(&mut self, iter: A) {
210        let iter = iter.into_iter();
211
212        for i in iter {
213            self.push(i);
214        }
215    }
216}
217
218unsafe impl<T> RingBuffer<T> for AllocRingBuffer<T> {
219    #[inline]
220    unsafe fn ptr_capacity(rb: *const Self) -> usize {
221        (*rb).capacity
222    }
223
224    #[inline]
225    unsafe fn ptr_buffer_size(rb: *const Self) -> usize {
226        (*rb).size
227    }
228
229    impl_ringbuffer!(readptr, writeptr);
230
231    #[inline]
232    fn push(&mut self, value: T) {
233        if self.is_full() {
234            // mask with and is allowed here because size is always a power of two
235            let previous_value =
236                unsafe { ptr::read(get_unchecked_mut(self, mask_and(self.size, self.readptr))) };
237
238            // make sure we drop whatever is being overwritten
239            // SAFETY: the buffer is full, so this must be initialized
240            //       : also, index has been masked
241            // make sure we drop because it won't happen automatically
242            unsafe {
243                drop(previous_value);
244            }
245
246            self.readptr += 1;
247        }
248
249        // mask with and is allowed here because size is always a power of two
250        let index = mask_and(self.size, self.writeptr);
251
252        unsafe {
253            ptr::write(get_unchecked_mut(self, index), value);
254        }
255
256        self.writeptr += 1;
257    }
258
259    fn dequeue(&mut self) -> Option<T> {
260        if self.is_empty() {
261            None
262        } else {
263            // mask with and is allowed here because size is always a power of two
264            let index = mask_and(self.size, self.readptr);
265            let res = unsafe { get_unchecked_mut(self, index) };
266            self.readptr += 1;
267
268            // Safety: the fact that we got this maybeuninit from the buffer (with mask) means that
269            // it's initialized. If it wasn't the is_empty call would have caught it. Values
270            // are always initialized when inserted so this is safe.
271            unsafe { Some(ptr::read(res)) }
272        }
273    }
274
275    impl_ringbuffer_ext!(
276        get_unchecked,
277        get_unchecked_mut,
278        readptr,
279        writeptr,
280        mask_and
281    );
282
283    #[inline]
284    fn fill_with<F: FnMut() -> T>(&mut self, mut f: F) {
285        self.clear();
286
287        self.readptr = 0;
288        self.writeptr = self.capacity;
289
290        for i in 0..self.capacity {
291            unsafe { ptr::write(get_unchecked_mut(self, i), f()) };
292        }
293    }
294}
295
296impl<T> AllocRingBuffer<T> {
297    /// Creates a `AllocRingBuffer` with a certain capacity. The actual capacity is the input to the
298    /// function raised to the power of two (effectively the input is the log2 of the actual capacity)
299    #[inline]
300    #[must_use]
301    pub fn with_capacity_power_of_2(cap_power_of_two: usize) -> Self {
302        Self::new(1 << cap_power_of_two)
303    }
304
305    #[inline]
306    /// Alias of [`with_capacity`](AllocRingBuffer::new).
307    #[must_use]
308    #[deprecated = "alias of new"]
309    pub fn with_capacity(cap: usize) -> Self {
310        Self::new(cap)
311    }
312
313    /// Creates a `AllocRingBuffer` with a certain capacity. The capacity must not be zero.
314    ///
315    /// # Panics
316    /// Panics when capacity is zero
317    #[inline]
318    #[must_use]
319    pub fn new(capacity: usize) -> Self {
320        assert_ne!(capacity, 0, "Capacity must be greater than 0");
321        let size = capacity.next_power_of_two();
322        let layout = alloc::alloc::Layout::array::<T>(size).unwrap();
323        let buf = unsafe { alloc::alloc::alloc(layout) as *mut T };
324        Self {
325            buf,
326            size,
327            capacity,
328            readptr: 0,
329            writeptr: 0,
330        }
331    }
332}
333
334/// Get a reference from the buffer without checking it is initialized.
335///
336/// Caller must be sure the index is in bounds, or this will panic.
337#[inline]
338unsafe fn get_unchecked<'a, T>(rb: *const AllocRingBuffer<T>, index: usize) -> &'a T {
339    let p = (*rb).buf.add(index);
340    // Safety: caller makes sure the index is in bounds for the ringbuffer.
341    // All in bounds values in the ringbuffer are initialized
342    &*p
343}
344
345/// Get a mut reference from the buffer without checking it is initialized.
346///
347/// Caller must be sure the index is in bounds, or this will panic.
348#[inline]
349unsafe fn get_unchecked_mut<T>(rb: *mut AllocRingBuffer<T>, index: usize) -> *mut T {
350    let p = (*rb).buf.add(index);
351
352    // Safety: caller makes sure the index is in bounds for the ringbuffer.
353    // All in bounds values in the ringbuffer are initialized
354    p.cast()
355}
356
357impl<T> Index<usize> for AllocRingBuffer<T> {
358    type Output = T;
359
360    fn index(&self, index: usize) -> &Self::Output {
361        self.get(index).expect("index out of bounds")
362    }
363}
364
365impl<T> IndexMut<usize> for AllocRingBuffer<T> {
366    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
367        self.get_mut(index).expect("index out of bounds")
368    }
369}
370
371#[cfg(test)]
372mod tests {
373    use crate::{AllocRingBuffer, RingBuffer};
374
375    // just test that this compiles
376    #[test]
377    fn test_generic_clone() {
378        fn helper(a: &AllocRingBuffer<i32>) -> AllocRingBuffer<i32> {
379            a.clone()
380        }
381
382        _ = helper(&AllocRingBuffer::new(2));
383        _ = helper(&AllocRingBuffer::new(5));
384    }
385
386    #[test]
387    fn test_not_power_of_two() {
388        let mut rb = AllocRingBuffer::new(10);
389        const NUM_VALS: usize = 1000;
390
391        // recycle the ringbuffer a bunch of time to see if noneof the logic
392        // messes up
393        for _ in 0..100 {
394            for i in 0..NUM_VALS {
395                rb.enqueue(i);
396            }
397            assert!(rb.is_full());
398
399            for i in 0..10 {
400                assert_eq!(Some(i + NUM_VALS - rb.capacity()), rb.dequeue())
401            }
402
403            assert!(rb.is_empty())
404        }
405    }
406
407    #[test]
408    fn test_with_capacity_power_of_two() {
409        let b = AllocRingBuffer::<i32>::with_capacity_power_of_2(2);
410        assert_eq!(b.capacity, 4);
411    }
412
413    #[test]
414    #[should_panic]
415    fn test_index_zero_length() {
416        let b = AllocRingBuffer::<i32>::new(2);
417        let _ = b[2];
418    }
419
420    #[test]
421    fn test_extend() {
422        let mut buf = AllocRingBuffer::<u8>::new(4);
423        (0..4).for_each(|_| buf.push(0));
424
425        let new_data = [0, 1, 2];
426        buf.extend(new_data);
427
428        let expected = [0, 0, 1, 2];
429
430        for i in 0..4 {
431            let actual = buf[i];
432            let expected = expected[i];
433            assert_eq!(actual, expected);
434        }
435    }
436
437    #[test]
438    fn test_extend_with_overflow() {
439        let mut buf = AllocRingBuffer::<u8>::new(8);
440        (0..8).for_each(|_| buf.push(0));
441
442        let new_data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
443        buf.extend(new_data);
444
445        let expected = [2, 3, 4, 5, 6, 7, 8, 9];
446
447        for i in 0..8 {
448            let actual = buf[i];
449            let expected = expected[i];
450            assert_eq!(actual, expected);
451        }
452    }
453
454    #[test]
455    fn test_conversions() {
456        // from &[T]
457        let data: &[i32] = &[1, 2, 3, 4];
458        let buf = AllocRingBuffer::from(data);
459        assert_eq!(buf.capacity, 4);
460        assert_eq!(buf.to_vec(), alloc::vec![1, 2, 3, 4]);
461
462        // from &[T; N]
463        let buf = AllocRingBuffer::from(&[1, 2, 3, 4]);
464        assert_eq!(buf.capacity, 4);
465        assert_eq!(buf.to_vec(), alloc::vec![1, 2, 3, 4]);
466
467        // from [T; N]
468        let buf = AllocRingBuffer::from([1, 2, 3, 4]);
469        assert_eq!(buf.capacity, 4);
470        assert_eq!(buf.to_vec(), alloc::vec![1, 2, 3, 4]);
471    }
472}