osom_lib_arrays/
inline_dynamic_array.rs

1#![allow(
2    clippy::needless_borrow,
3    clippy::uninit_assumed_init,
4    clippy::cast_possible_truncation,
5    clippy::cast_possible_wrap,
6    clippy::cast_sign_loss
7)]
8
9use core::alloc::Layout;
10use core::mem::ManuallyDrop;
11use core::ops::Deref;
12
13use osom_lib_alloc::{AllocatedMemory, AllocationError, Allocator};
14use osom_lib_primitives::{DoesNotHaveToBeUsed, Length};
15
16#[cfg(feature = "std_alloc")]
17use osom_lib_alloc::StdAllocator;
18
19use crate::errors::ArrayConstructionError;
20
21union InlineDynamicArrayUnion<T, const N: usize> {
22    stack_data: ManuallyDrop<[T; N]>,
23    heap_data: *mut T,
24}
25
26/// A struct similar to [`DynamicArray`][`super::DynamicArray`],
27/// but holds `N` items inlined. Meaning it won't allocate memory
28/// until it exceeds `N` elements.
29///
30/// Note that this struct can only grow, and will never shrink.
31#[must_use]
32pub struct InlineDynamicArray<
33    const N: usize,
34    T,
35    #[cfg(feature = "std_alloc")] TAllocator = StdAllocator,
36    #[cfg(not(feature = "std_alloc"))] TAllocator,
37> where
38    TAllocator: Allocator,
39{
40    data: InlineDynamicArrayUnion<T, N>,
41    length: Length,
42    capacity: Length,
43    allocator: TAllocator,
44}
45
46impl<const N: usize, T, TAllocator: Allocator> InlineDynamicArray<N, T, TAllocator> {
47    pub const MAX_SIZE: usize = Length::MAX;
48
49    const fn validate() {
50        assert!(
51            N > 0,
52            "N in InlineVec must be greater than 0. InlineVec with N == 0 is just Vec. Use Vec instead."
53        );
54
55        // Note: 2147482623 is (i32::MAX - 1024). This is definitely way too much,
56        // but we reserve some space, just in case.
57        assert!(
58            N < Self::MAX_SIZE,
59            "N in InlineVec must be at most 2147482623. Which likely already is waaaay too much."
60        );
61    }
62
63    #[inline(always)]
64    const fn layout(size: usize) -> Layout {
65        let real_size = size * size_of::<T>();
66        let alignment = align_of::<T>();
67        unsafe { Layout::from_size_align_unchecked(real_size, alignment) }
68    }
69
70    #[inline(always)]
71    fn allocate_memory(&self, size: usize) -> Result<*mut T, AllocationError> {
72        let new_memory = self.allocator.allocate(Self::layout(size))?;
73        let result: *mut T = unsafe { new_memory.as_ptr() };
74        assert!(result.is_aligned(), "Newly allocated memory is not aligned correctly.");
75        Ok(result)
76    }
77
78    #[inline(always)]
79    const fn is_inlined(&self) -> bool {
80        self.capacity.value() == N as i32
81    }
82
83    #[inline(always)]
84    fn data_ptr(&self) -> *mut T {
85        unsafe {
86            if self.is_inlined() {
87                (&self.data.stack_data).as_ptr().cast_mut()
88            } else {
89                self.data.heap_data
90            }
91        }
92    }
93
94    fn try_grow(&mut self, new_capacity: usize) -> Result<(), ArrayConstructionError> {
95        if new_capacity > Self::MAX_SIZE {
96            return Err(ArrayConstructionError::ArrayTooLong);
97        }
98
99        debug_assert!(
100            new_capacity > self.capacity.into(),
101            "Tried to grow to a smaller capacity."
102        );
103
104        unsafe {
105            if self.is_inlined() {
106                if new_capacity <= N {
107                    return Ok(());
108                }
109                let new_memory = self.allocate_memory(new_capacity)?;
110                let stack_data = (&self.data.stack_data).as_ptr();
111                new_memory.copy_from_nonoverlapping(stack_data, self.length.into());
112                self.data = InlineDynamicArrayUnion { heap_data: new_memory };
113            } else {
114                let old_layout = Self::layout(self.capacity.into());
115                let new_layout = Self::layout(new_capacity);
116                let old_memory = self.allocator.convert_raw_ptr(self.data.heap_data);
117                let new_memory = old_memory.resize(old_layout, new_layout)?;
118                self.data.heap_data = new_memory.as_ptr();
119            }
120            self.capacity = Length::new_unchecked(new_capacity as i32);
121        }
122        Ok(())
123    }
124
125    /// Pushes a value to the end of the [`InlineDynamicArray`].
126    ///
127    /// Note that the [`InlineDynamicArray`] data will be moved to the heap
128    /// only when length exceeds `N`. It won't come back from the
129    /// heap though.
130    ///
131    /// Also note that the [`InlineDynamicArray`] will never shrink, it will
132    /// only keep growing.
133    ///
134    /// # Errors
135    ///
136    /// For details see [`ArrayConstructionError`].
137    pub fn push(&mut self, value: T) -> Result<(), ArrayConstructionError> {
138        let capacity: usize = self.capacity.into();
139        unsafe {
140            if self.is_inlined() && self.length.value() < N as i32 {
141                let data = &mut self.data.stack_data;
142                data.as_mut_ptr().add(self.length.into()).write(value);
143                self.length += 1;
144                return Ok(());
145            }
146
147            if self.length == self.capacity {
148                self.try_grow(capacity * 2)?;
149            }
150
151            self.data.heap_data.add(self.length.into()).write(value);
152            self.length += 1;
153        }
154        Ok(())
155    }
156
157    /// Pops last element from the [`InlineDynamicArray`],
158    /// decreasing its size.
159    ///
160    /// # Returns
161    ///
162    /// * `Some(T)` if `self.len() > 0`
163    /// * `None` otherwise
164    pub fn pop(&mut self) -> Option<T> {
165        if self.is_empty() {
166            None
167        } else {
168            Some(unsafe { self.pop_unchecked() })
169        }
170    }
171
172    /// Unsafe variant of [`pop`][`Self::pop`].
173    ///
174    /// # Safety
175    ///
176    /// Returns `T` if `self.len() > 0` and decrease the
177    /// [`InlineDynamicArray`] size. The behaviour is undefined if
178    /// `self.len() == 0`.
179    #[inline]
180    pub unsafe fn pop_unchecked(&mut self) -> T {
181        debug_assert!(!self.is_empty(), "Tried pop_unchecked on length 0 InlineDynamicArray.");
182        unsafe {
183            let ptr = self.data_ptr();
184            self.length -= 1;
185            ptr.add(self.length.into()).read()
186        }
187    }
188
189    /// Creates a new empty [`InlineDynamicArray`].
190    #[inline(always)]
191    pub fn new() -> Self {
192        Self::with_allocator(TAllocator::default())
193    }
194
195    /// Creates a new empty [`InlineDynamicArray`] with the given allocator.
196    #[inline]
197    pub fn with_allocator(allocator: TAllocator) -> Self {
198        const { Self::validate() };
199
200        Self {
201            data: InlineDynamicArrayUnion {
202                heap_data: unsafe { allocator.dangling::<T>().as_ptr() },
203            },
204            length: Length::ZERO,
205            capacity: unsafe { Length::new_unchecked(N as i32) },
206            allocator: allocator,
207        }
208    }
209
210    /// Creates a new empty [`InlineDynamicArray`] with the given capacity.
211    ///
212    /// # Errors
213    ///
214    /// For details see [`ArrayConstructionError`].
215    #[inline(always)]
216    pub fn with_capacity(capacity: Length) -> Result<Self, ArrayConstructionError> {
217        Self::with_capacity_and_allocator(capacity, TAllocator::default())
218    }
219
220    /// Creates a new empty [`InlineDynamicArray`] with the given capacity and allocator.
221    ///
222    /// # Errors
223    ///
224    /// For details see [`ArrayConstructionError`].
225    #[inline(always)]
226    pub fn with_capacity_and_allocator(
227        capacity: Length,
228        allocator: TAllocator,
229    ) -> Result<Self, ArrayConstructionError> {
230        let mut array = Self::with_allocator(allocator);
231        array.try_grow(capacity.into())?;
232        Ok(array)
233    }
234
235    /// Returns the number of elements in the [`InlineDynamicArray`].
236    #[inline(always)]
237    pub const fn len(&self) -> Length {
238        self.length
239    }
240
241    /// Returns `true` if the [`InlineDynamicArray`] is empty,
242    /// otherwise `false`.
243    #[inline(always)]
244    #[must_use]
245    pub const fn is_empty(&self) -> bool {
246        self.length.value() == 0
247    }
248
249    /// Returns the capacity of the [`InlineDynamicArray`]. Note that
250    /// this is always at least `N`.
251    #[inline(always)]
252    pub const fn capacity(&self) -> Length {
253        self.capacity
254    }
255
256    /// Returns a reference to the allocator of the [`InlineDynamicArray`].
257    #[inline(always)]
258    pub const fn allocator(&self) -> &TAllocator {
259        &self.allocator
260    }
261
262    /// Represents current [`InlineDynamicArray`] as a slice.
263    #[inline]
264    pub fn as_slice(&self) -> &[T] {
265        unsafe {
266            let ptr = self.data_ptr();
267            core::slice::from_raw_parts(ptr, self.len().into())
268        }
269    }
270
271    /// Represents current [`InlineDynamicArray`] as a mutable slice.
272    #[inline]
273    pub fn as_slice_mut(&mut self) -> &mut [T] {
274        unsafe {
275            let ptr = self.data_ptr();
276            core::slice::from_raw_parts_mut(ptr, self.len().into())
277        }
278    }
279
280    /// Fills the [`InlineDynamicArray`] up to its capacity, by invoking
281    /// `constructor` for each missing element.
282    ///
283    /// # Notes
284    ///
285    /// This method does not reallocate the underlying memory.
286    pub fn fill<F: FnMut() -> T>(&mut self, mut constructor: F) -> DoesNotHaveToBeUsed<Length> {
287        let capacity: usize = self.capacity.into();
288        let len: usize = self.len().into();
289        let diff = capacity - len;
290        if diff == 0 {
291            return Length::ZERO.into();
292        }
293
294        unsafe {
295            let mut ptr = self.data_ptr().add(len);
296            for _ in 0..diff {
297                ptr.write(constructor());
298                ptr = ptr.add(1);
299            }
300            self.length = Length::new_unchecked(capacity as i32);
301            Length::new_unchecked(diff as i32).into()
302        }
303    }
304}
305
306impl<const N: usize, T: Clone, TAllocator: Allocator> InlineDynamicArray<N, T, TAllocator> {
307    /// Tries to clone the [`InlineDynamicArray`].
308    ///
309    /// # Errors
310    ///
311    /// For details see [`ArrayConstructionError`].
312    pub fn try_clone(&self) -> Result<Self, ArrayConstructionError> {
313        let mut new = Self::with_allocator(self.allocator.clone());
314        let slice = self.as_slice();
315        for item in slice {
316            new.push(item.clone())?;
317        }
318        Ok(new)
319    }
320}
321
322impl<const N: usize, T, TAllocator: Allocator> Drop for InlineDynamicArray<N, T, TAllocator> {
323    fn drop(&mut self) {
324        unsafe {
325            if core::mem::needs_drop::<T>() {
326                let mut ptr = self.data_ptr();
327                let mut idx = 0;
328                while idx < self.len().into() {
329                    core::ptr::drop_in_place(ptr);
330                    ptr = ptr.add(1);
331                    idx += 1;
332                }
333            }
334
335            if !self.is_inlined() {
336                let layout = Self::layout(self.capacity.into());
337                let memory = self.allocator.convert_raw_ptr(self.data.heap_data);
338                memory.deallocate(layout);
339            }
340        }
341    }
342}
343
344impl<const N: usize, T, TAllocator: Allocator> Default for InlineDynamicArray<N, T, TAllocator> {
345    fn default() -> Self {
346        Self::new()
347    }
348}
349
350impl<const N: usize, T: Clone, TAllocator: Allocator> Clone for InlineDynamicArray<N, T, TAllocator> {
351    fn clone(&self) -> Self {
352        self.try_clone().expect("Failed to clone the inline dynamic array")
353    }
354}
355
356impl<const N: usize, T, TAllocator: Allocator> core::fmt::Debug for InlineDynamicArray<N, T, TAllocator> {
357    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
358        f.debug_struct("InlineDynamicArray")
359            .field("N", &N)
360            .field("len", &self.len())
361            .field("capacity", &self.capacity())
362            .field("is_inlined", &self.is_inlined())
363            .field("raw_ptr", &self.data_ptr().addr())
364            .finish()
365    }
366}
367
368impl<const N1: usize, const N2: usize, T: PartialEq, TAllocator1: Allocator, TAllocator2: Allocator>
369    PartialEq<InlineDynamicArray<N1, T, TAllocator1>> for InlineDynamicArray<N2, T, TAllocator2>
370{
371    fn eq(&self, other: &InlineDynamicArray<N1, T, TAllocator1>) -> bool {
372        self.as_slice() == other.as_slice()
373    }
374}
375
376impl<const N: usize, T: Eq, TAllocator: Allocator> Eq for InlineDynamicArray<N, T, TAllocator> {}
377
378impl<const N: usize, T, TAllocator: Allocator> Deref for InlineDynamicArray<N, T, TAllocator> {
379    type Target = [T];
380
381    fn deref(&self) -> &Self::Target {
382        self.as_slice()
383    }
384}
385
386impl<const N: usize, T, TAllocator: Allocator> AsRef<[T]> for InlineDynamicArray<N, T, TAllocator> {
387    fn as_ref(&self) -> &[T] {
388        self.as_slice()
389    }
390}
391
392unsafe impl<const N: usize, T: Send, TAllocator: Allocator> Send for InlineDynamicArray<N, T, TAllocator> {}
393unsafe impl<const N: usize, T: Sync, TAllocator: Allocator> Sync for InlineDynamicArray<N, T, TAllocator> {}
osom_lib_arrays/inline_dynamic_array.rs

osom_lib_arrays/
inline_dynamic_array.rs
