fixed_collections/
lib.rs

1//! A non growable, dynamically allocated collection
2
3use core::alloc::Layout;
4use core::mem::{MaybeUninit, replace, transmute};
5use core::ops::{Index, IndexMut};
6use core::ptr::{NonNull, slice_from_raw_parts_mut};
7use core::slice::{Iter, IterMut};
8
9extern crate alloc;
10
11#[cfg(not(feature = "std"))]
12use alloc::alloc::{alloc, dealloc, handle_alloc_error};
13
14#[cfg(feature = "std")]
15use std::alloc::{alloc, dealloc, handle_alloc_error};
16
17// use num_traits::Zero;
18
19/// A dynamically allocated array of `T`
20#[derive(Debug)]
21pub struct ArrayPtr<T>(NonNull<[T]>);
22impl<T> Drop for ArrayPtr<T> {
23    fn drop(&mut self) {
24        let layout = Layout::array::<T>(self.as_slice().len()).expect("A sane layout");
25        unsafe { dealloc(self.0.as_ptr().cast(), layout) };
26    }
27}
28impl<T> Index<usize> for ArrayPtr<T> {
29    type Output = T;
30    fn index(&self, index: usize) -> &Self::Output {
31        let s = unsafe { self.0.as_ref() };
32        &s[index]
33    }
34}
35impl<T> IndexMut<usize> for ArrayPtr<T> {
36    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
37        let s = unsafe { self.0.as_mut() };
38        &mut s[index]
39    }
40}
41impl<T> ArrayPtr<T> {
42    /// Allocate a new [`ArrayPtr`]`<T>` without initializing the memory
43    ///
44    /// The number of elements is given by the input parameter `count`
45    pub fn new_uninit(count: usize) -> ArrayPtr<MaybeUninit<T>> {
46        // Since the collection is ungrowable, this is not accepted
47        debug_assert!(
48            count != 0,
49            "Tried to initialize an ArrayPtr with zero elements!"
50        );
51        let layout = Layout::array::<T>(count).expect("A sane layout");
52
53        // SAFETY: We handle the allocation error below, and the layout should be sane
54        let ptr = unsafe { alloc(layout) } as *mut MaybeUninit<T>;
55        if ptr.is_null() {
56            handle_alloc_error(layout);
57        }
58
59        let ptr_slice = slice_from_raw_parts_mut(ptr, count);
60
61        // SAFETY: We validated above the pointer is non-null, and handle allocation errors accordingly
62        let inner = unsafe { NonNull::new_unchecked(ptr_slice) };
63
64        ArrayPtr(inner)
65    }
66    pub fn shift_once(&mut self)
67    where
68        T: Copy,
69    {
70        let fst = self[0];
71        let bound = self.len() - 1;
72        for i in 0..bound {
73            self[i] = self[i + 1]
74        }
75        self[bound] = fst;
76    }
77    /// Create a new [`ArrayPtr`]`<T>` from a pointer an an element-count
78    ///
79    /// # Safety
80    ///
81    /// The caller must ensure that the pointer is non-null,
82    /// and points to the number of elements specified.
83    pub fn from_raw_parts(data: *mut T, len: usize) -> ArrayPtr<T> {
84        // TODO: Make this function unsafe (on next minor version bump)
85
86        let ptr = core::ptr::slice_from_raw_parts_mut(data, len);
87        debug_assert!(
88            !ptr.is_null(),
89            "Tried to make an ArrayPtr from a null pointer!"
90        );
91
92        // SAFETY: We asserted above
93        let inner = unsafe { NonNull::new_unchecked(ptr) };
94        ArrayPtr(inner)
95    }
96}
97impl<T> ArrayPtr<MaybeUninit<T>> {
98    /// # Safety
99    /// Caller must guarantee each member of the
100    /// [`ArrayPtr`] has been written to with a
101    /// valid instance of `T`
102    pub unsafe fn assume_init(self) -> ArrayPtr<T> {
103        debug_assert!(!self.is_empty(), "Calling assume_init on an empty array!");
104        unsafe { transmute(self) }
105    }
106}
107
108#[cfg(feature = "num-traits")]
109impl<T> ArrayPtr<T>
110where
111    T: num_traits::Zero,
112{
113    /// Create a new [`ArrayPtr`]`<T>` by initializing it with `T`'s [`Zero`](num_traits::Zero) implementation.
114    ///
115    /// This function is feature-gated behind the `num-traits` feature.
116    pub fn new_zeroed(count: usize) -> ArrayPtr<T> {
117        let mut arr = ArrayPtr::new_uninit(count);
118        for val in arr.iter_mut() {
119            val.write(T::zero());
120        }
121        unsafe { arr.assume_init() }
122    }
123}
124impl<T> ArrayPtr<T>
125where
126    T: Default,
127{
128    /// Create a new [`ArrayPtr`]`<T>` by initializing it with `T`'s [`Default`] implementation.
129    pub fn new_default(count: usize) -> ArrayPtr<T> {
130        let mut arr = ArrayPtr::new_uninit(count);
131        for val in arr.iter_mut() {
132            val.write(T::default());
133        }
134        unsafe { arr.assume_init() }
135    }
136}
137impl<T> AsRef<[T]> for ArrayPtr<T> {
138    #[inline(always)]
139    fn as_ref(&self) -> &[T] {
140        unsafe { self.0.as_ref() }
141    }
142}
143impl<T> AsMut<[T]> for ArrayPtr<T> {
144    #[inline(always)]
145    fn as_mut(&mut self) -> &mut [T] {
146        unsafe { self.0.as_mut() }
147    }
148}
149impl<T> ArrayPtr<T> {
150    /// Create a new [`ArrayPtr`]`<T>` from a provided closure and element-count
151    ///
152    /// The closure will be invoked as an index-mapping from 0 up to the specified element-count.
153    pub fn from_fn(count: usize, idx_map: impl Fn(usize) -> T) -> ArrayPtr<T> {
154        let mut buf = ArrayPtr::new_uninit(count);
155        for (idx, elt) in buf.iter_mut().enumerate() {
156            elt.write(idx_map(idx));
157        }
158        unsafe { buf.assume_init() }
159    }
160    /// Returns [`true`] if the underlying [`ArrayPtr`]`<T>` is empty
161    ///
162    /// This should never happen.
163    #[inline(always)]
164    pub const fn is_empty(&self) -> bool {
165        self.0.is_empty()
166    }
167    /// Returns the number of elements pointed to the [`ArrayPtr`]`<T>`
168    #[inline(always)]
169    pub const fn len(&self) -> usize {
170        self.0.len()
171    }
172    /// Returns a shared slice-reference to the underlying data
173    #[inline(always)]
174    pub fn as_slice(&self) -> &[T] {
175        self.as_ref()
176    }
177    /// Returns a mutable slice-reference to the underlying data
178    #[inline(always)]
179    pub fn as_mut_slice(&mut self) -> &mut [T] {
180        self.as_mut()
181    }
182    /// Returns an immutable iterator over underlying data
183    #[inline(always)]
184    pub fn iter(&self) -> Iter<'_, T> {
185        self.as_slice().iter()
186    }
187    /// Returns a mutable iterator over underlying data
188    #[inline(always)]
189    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
190        self.as_mut_slice().iter_mut()
191    }
192}
193impl<T> FromIterator<T> for ArrayPtr<T> {
194    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
195        let v: Vec<T> = iter.into_iter().collect();
196
197        let mut arr = ArrayPtr::<T>::new_uninit(v.len());
198        for (idx, val) in v.into_iter().enumerate() {
199            arr[idx].write(val);
200        }
201
202        unsafe { arr.assume_init() }
203    }
204}
205pub struct RingPtr<T> {
206    inner: NonNull<[T]>,
207    head: usize,
208    tail: usize,
209}
210impl<T> Drop for RingPtr<T> {
211    fn drop(&mut self) {
212        let capacity = self.capacity();
213        if capacity == 0 {
214            return;
215        }
216        let layout = Layout::array::<T>(capacity).expect("A sane layout");
217        unsafe { dealloc(self.inner.as_ptr().cast(), layout) };
218    }
219}
220
221impl<T> Index<usize> for RingPtr<T> {
222    type Output = T;
223    fn index(&self, index: usize) -> &Self::Output {
224        &self.as_slice()[index]
225    }
226}
227impl<T> IndexMut<usize> for RingPtr<T> {
228    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
229        &mut self.as_mut_slice()[index]
230    }
231}
232impl<T> RingPtr<T> {
233    pub fn new_uninit(count: usize) -> RingPtr<MaybeUninit<T>> {
234        let layout = Layout::array::<T>(count).expect("A sane layout");
235
236        let ptr = unsafe { alloc(layout) } as *mut MaybeUninit<T>;
237
238        if ptr.is_null() {
239            handle_alloc_error(layout);
240        }
241
242        let ptr_slice = slice_from_raw_parts_mut(ptr, count);
243
244        // SAFETY: We validated above the pointer is non-null, and handle allocation errors accordingly
245        let inner = unsafe { NonNull::new_unchecked(ptr_slice) };
246
247        RingPtr {
248            inner,
249            head: 0,
250            tail: 0,
251        }
252    }
253}
254
255impl<T> RingPtr<MaybeUninit<T>> {
256    /// # Safety
257    /// Caller must guarantee each member of the
258    /// [`RingPtr`] has been written to with a
259    /// valid instance of `T`
260    pub unsafe fn assume_init(self) -> RingPtr<T> {
261        debug_assert!(
262            self.capacity() != 0,
263            "Calling assume_init on an empty array!"
264        );
265        unsafe { transmute(self) }
266    }
267}
268#[cfg(feature = "num-traits")]
269impl<T> RingPtr<T>
270where
271    T: num_traits::Zero,
272{
273    pub fn new_zeroed(count: usize) -> RingPtr<T> {
274        let mut arr = RingPtr::new_uninit(count);
275        for val in arr.iter_mut() {
276            val.write(T::zero());
277        }
278        unsafe { arr.assume_init() }
279    }
280}
281impl<T> RingPtr<T>
282where
283    T: Default,
284{
285    pub fn new_default(count: usize) -> RingPtr<T> {
286        let mut arr = RingPtr::new_uninit(count);
287        for val in arr.iter_mut() {
288            val.write(T::default());
289        }
290        unsafe { arr.assume_init() }
291    }
292}
293
294impl<T> RingPtr<T> {
295    #[inline(always)]
296    fn at(&mut self, offset: usize) -> *mut T {
297        unsafe { self.as_mut_slice().as_mut_ptr().add(offset) }
298    }
299    /// Returns true if the capacity is zero or the current tail is the next head position
300    #[inline(always)]
301    pub const fn is_empty(&self) -> bool {
302        self.inner.is_empty() || self.tail == self.next_head_pos()
303    }
304    /// Returns the 'count' of valid elements in the collection, not the capacity
305    #[inline(always)]
306    pub const fn len(&self) -> usize {
307        if self.head < self.tail {
308            self.head - self.tail
309        } else {
310            let from_head = self.capacity() - self.head;
311            from_head + self.tail
312        }
313    }
314    #[inline]
315    pub const fn capacity(&self) -> usize {
316        self.inner.len()
317    }
318    #[inline(always)]
319    const fn next_head_pos(&self) -> usize {
320        (self.head + 1) % self.capacity()
321    }
322    #[inline(always)]
323    const fn next_tail_pos(&self) -> usize {
324        (self.tail + 1) % self.capacity()
325    }
326
327    pub fn push(&mut self, val: T) {
328        unsafe { self.at(self.tail).write(val) };
329        self.tail = self.next_tail_pos();
330    }
331    pub fn replace(&mut self, src: T) -> T {
332        unsafe { replace(&mut *self.at(self.tail), src) }
333    }
334    pub fn reset(&mut self) {
335        self.head = 0;
336        self.tail = 0;
337    }
338    pub fn pop(&mut self) -> Option<T> {
339        if self.is_empty() {
340            None
341        } else {
342            let val = unsafe { self.at(self.head).read() };
343            self.head = self.next_head_pos();
344            Some(val)
345        }
346    }
347    pub fn peek(&self) -> &T {
348        &self.as_slice()[self.head]
349    }
350    #[inline(always)]
351    pub fn as_slice(&self) -> &[T] {
352        unsafe { self.inner.as_ref() }
353    }
354    #[inline(always)]
355    pub fn as_mut_slice(&mut self) -> &mut [T] {
356        unsafe { self.inner.as_mut() }
357    }
358    #[inline(always)]
359    pub fn iter(&self) -> Iter<'_, T> {
360        self.as_slice().iter()
361    }
362    #[inline(always)]
363    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
364        self.as_mut_slice().iter_mut()
365    }
366}
367pub struct CircularBuffer<T> {
368    buffer: ArrayPtr<T>,
369    cursor: usize,
370}
371impl<T> From<ArrayPtr<T>> for CircularBuffer<T> {
372    fn from(value: ArrayPtr<T>) -> Self {
373        debug_assert!(
374            !value.is_empty(),
375            "Making circular buffer from empty ArrayPtr!"
376        );
377        CircularBuffer {
378            buffer: value,
379            cursor: 0,
380        }
381    }
382}
383#[cfg(feature = "num-traits")]
384impl<T> CircularBuffer<T> {
385    /// Create a new [`CircularBuffer`]`<T>` by initializing it with `T`'s [`Zero`](num_traits::Zero) implementation.
386    ///
387    /// This function is feature-gated behind the `num-traits` feature.
388    pub fn new_zeroed(count: usize) -> CircularBuffer<T>
389    where
390        T: num_traits::Zero,
391    {
392        ArrayPtr::new_zeroed(count).into()
393    }
394}
395impl<T> CircularBuffer<T> {
396    /// Create a new [`CircularBuffer`]`<T>` by initializing it with `T`'s [`Default`] implementation.
397    pub fn new_default(count: usize) -> CircularBuffer<T>
398    where
399        T: Default,
400    {
401        ArrayPtr::new_default(count).into()
402    }
403    /// Returns what the next cursor value would be
404    fn incremented_cursor(&self) -> usize {
405        (self.cursor + 1) % (self.buffer.len())
406    }
407    /// Returns what the previous cursor value would be
408    fn decremented_cursor(&self) -> usize {
409        if self.cursor == 0 {
410            self.buffer.len() - 1
411        } else {
412            (self.cursor - 1) % (self.buffer.len())
413        }
414    }
415    /// Returns a shared reference to the current element
416    fn current_as_ref(&self) -> &T {
417        unsafe { self.buffer.as_slice().get_unchecked(self.cursor) }
418    }
419    /// Returns a mutable reference to the current element
420    fn current_as_mut(&mut self) -> &mut T {
421        unsafe { self.buffer.as_mut_slice().get_unchecked_mut(self.cursor) }
422    }
423    /// Returns the previous value, and increments cursor
424    #[inline(always)]
425    pub fn update_forwards(&mut self, src: T) -> (T, T)
426    where
427        T: Copy,
428    {
429        let prev = *self.current_as_ref();
430        self.cursor = self.incremented_cursor();
431        let curr = replace(self.current_as_mut(), src);
432        (prev, curr)
433    }
434    /// The same as [`CircularBuffer::update_forwards`] but reverses
435    /// through the internal buffer
436    #[inline(always)]
437    pub fn update_backwards(&mut self, src: T) -> (T, T)
438    where
439        T: Copy,
440    {
441        let prev = *self.current_as_ref();
442        self.cursor = self.decremented_cursor();
443        let curr = replace(self.current_as_mut(), src);
444        (prev, curr)
445    }
446    /// Set the [`CircularBuffer`]'s cursor to the specified value
447    #[inline(always)]
448    pub const fn set_cursor(&mut self, val: usize) {
449        self.cursor = val;
450    }
451    /// Set the [`CircularBuffer`]'s cursor to zero
452    #[inline(always)]
453    pub const fn reset_cursor(&mut self) {
454        self.set_cursor(0);
455    }
456    #[inline(always)]
457    pub const fn is_empty(&self) -> bool {
458        self.buffer.is_empty()
459    }
460
461    /// Returns the total element-count in this [`CircularBuffer`]
462    #[inline(always)]
463    pub const fn len(&self) -> usize {
464        self.buffer.len()
465    }
466
467    /// Returns the full data contained in this [`CircularBuffer`]
468    /// as a shared slice-reference
469    #[inline(always)]
470    pub fn as_slice(&self) -> &[T] {
471        self.buffer.as_slice()
472    }
473    /// Returns the full data contained in this [`CircularBuffer`]
474    /// as a mutable slice-reference
475    #[inline(always)]
476    pub fn as_mut_slice(&mut self) -> &mut [T] {
477        self.buffer.as_mut_slice()
478    }
479}
480impl<T> Index<usize> for CircularBuffer<T> {
481    type Output = <ArrayPtr<T> as Index<usize>>::Output;
482    fn index(&self, index: usize) -> &Self::Output {
483        &self.buffer[index]
484    }
485}
486impl<T> IndexMut<usize> for CircularBuffer<T> {
487    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
488        &mut self.buffer[index]
489    }
490}
491
492#[cfg(feature = "circular-buffer-fft")]
493impl<T> CircularBuffer<num_complex::Complex<T>> {
494    #[inline(always)]
495    pub fn inplace_fourier_transform(
496        &mut self,
497        transformer: &dyn rustfft::Fft<T>,
498        scratch: &mut [num_complex::Complex<T>],
499    ) where
500        T: rustfft::FftNum,
501    {
502        transformer.process_with_scratch(self.buffer.as_mut_slice(), scratch);
503    }
504    pub fn inplace_hilbert_transform<'s>(
505        &'s mut self,
506        processor: &dyn rustfft::Fft<T>,
507        reverse_processor: &dyn rustfft::Fft<T>,
508        scratch: &mut [num_complex::Complex<T>],
509    ) -> &'s [num_complex::Complex<T>]
510    where
511        T: rustfft::FftNum + num_traits::NumCast,
512        num_complex::Complex<T>: core::ops::MulAssign + core::ops::DivAssign<T>,
513    {
514        self.inplace_fourier_transform(processor, scratch);
515
516        self.apply_hilbert_filter();
517
518        self.inplace_fourier_transform(reverse_processor, scratch);
519        // Ensure properly scaled values following IFFT
520        self.batch_downscale();
521
522        self.as_slice()
523    }
524    #[inline(always)]
525    pub fn apply_hilbert_filter(&mut self)
526    where
527        T: rustfft::FftNum + num_traits::NumCast + num_traits::Zero,
528        num_complex::Complex<T>: core::ops::MulAssign,
529    {
530        use num_complex::Complex;
531
532        let n = self.buffer.as_slice().len();
533        for (i, elt) in self.buffer.iter_mut().enumerate().take(n) {
534            let multiplier = match i {
535                0 => <num_complex::Complex<T> as num_traits::Zero>::zero(), // Zero DC
536                i if i < n / 2 => Complex::new(T::zero(), -T::one()), // -i for positive frequencies
537                _ => <num_complex::Complex<T> as num_traits::Zero>::zero(), // Zero negative frequencies
538            };
539            *elt *= multiplier;
540        }
541    }
542    #[inline(always)]
543    fn batch_downscale(&mut self)
544    where
545        T: num_traits::Num + num_traits::NumCast + Copy,
546        num_complex::Complex<T>: core::ops::DivAssign<T>,
547    {
548        let n = self.buffer.len();
549        let n_t: T = num_traits::NumCast::from(n).expect("A usize for downscaling");
550        for elt in self.buffer.iter_mut() {
551            *elt /= n_t;
552        }
553    }
554}
555#[cfg(test)]
556mod tests {
557    use super::*;
558
559    mod array_ptr {
560        use super::*;
561
562        #[cfg(feature = "num-traits")]
563        #[test]
564        fn zero_means_zero() {
565            let arr: ArrayPtr<u32> = ArrayPtr::new_zeroed(10);
566            for elt in arr.iter() {
567                assert_eq!(elt, &0);
568            }
569        }
570    }
571}
fixed_collections/lib.rs

fixed_collections/
lib.rs
