osom_tools_runtime/arrays/
dynamic_array.rs

1#![allow(clippy::cast_sign_loss, clippy::cast_possible_truncation, clippy::cast_possible_wrap)]
2
3use core::{alloc::Layout, marker::PhantomData, ops::Deref};
4
5use crate::{
6    Length,
7    allocator::{AllocatedMemory as _, AllocationError, Allocator},
8};
9
10#[cfg(feature = "std_alloc")]
11use crate::allocator::StdAllocator;
12
13/// Represents an error that occurs when constructing new [`DynamicArray`].
14#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
15#[must_use]
16#[repr(u8)]
17pub enum DynamicArrayConstructionError {
18    /// The allocator failed to allocate memory.
19    AllocationError,
20
21    /// The passed array is too long, it exceeds [`MAX_LENGTH`][`DynamicArray::MAX_LENGTH`].
22    ArrayTooLong,
23}
24
25impl From<AllocationError> for DynamicArrayConstructionError {
26    fn from(_: AllocationError) -> Self {
27        DynamicArrayConstructionError::AllocationError
28    }
29}
30
31/// A dynamic array that grows when inserting elements. Similar to
32/// `std::vec::Vec` in its nature.
33///
34/// The main differences are:
35/// * It has slightly different growth rate, new capacity is equal to
36///   3/2 of the old capacity.
37/// * It allows plugging in custom allocators.
38#[must_use]
39pub struct DynamicArray<
40    T,
41    #[cfg(feature = "std_alloc")] TAllocator = StdAllocator,
42    #[cfg(not(feature = "std_alloc"))] TAllocator,
43> where
44    TAllocator: Allocator,
45{
46    ptr: TAllocator::TAllocatedMemory,
47    length: Length,
48    capacity: Length,
49    allocator: TAllocator,
50    phantom: PhantomData<T>,
51}
52
53impl<T, TAllocator: Allocator> DynamicArray<T, TAllocator> {
54    const fn grow_formula(current: i32) -> Length {
55        unsafe { Length::new_unchecked((3 * (current / 2)) + 1) }
56    }
57
58    pub const MAX_LENGTH: usize = Length::MAX;
59
60    /// Creates a new empty [`DynamicArray`] with the default allocator.
61    #[inline(always)]
62    pub fn new() -> Self {
63        Self::with_allocator(TAllocator::default())
64    }
65
66    /// Creates a new empty [`DynamicArray`] with the given allocator.
67    #[inline(always)]
68    pub fn with_allocator(allocator: TAllocator) -> Self {
69        Self {
70            ptr: unsafe { allocator.dangling::<T>() },
71            length: Length::ZERO,
72            capacity: Length::ZERO,
73            allocator: allocator,
74            phantom: PhantomData,
75        }
76    }
77
78    /// Creates a new empty [`DynamicArray`] with the given capacity.
79    ///
80    /// # Errors
81    ///
82    /// For details see [`DynamicArrayConstructionError`].
83    #[inline(always)]
84    pub fn with_capacity(capacity: Length) -> Result<Self, DynamicArrayConstructionError> {
85        Self::with_capacity_and_allocator(capacity, TAllocator::default())
86    }
87
88    /// Creates a new empty [`DynamicArray`] with the given capacity and allocator.
89    ///
90    /// # Errors
91    ///
92    /// For details see [`DynamicArrayConstructionError`].
93    #[inline(always)]
94    pub fn with_capacity_and_allocator(
95        capacity: Length,
96        allocator: TAllocator,
97    ) -> Result<Self, DynamicArrayConstructionError> {
98        if capacity == Length::ZERO {
99            return Ok(Self::with_allocator(allocator));
100        }
101
102        let mut new_array = Self::with_allocator(allocator);
103        new_array.grow(capacity)?;
104        Ok(new_array)
105    }
106
107    /// Returns the length of the [`DynamicArray`].
108    #[inline(always)]
109    pub const fn len(&self) -> Length {
110        self.length
111    }
112
113    /// Returns `true` if the [`DynamicArray`] is empty, `false` otherwise.
114    #[inline(always)]
115    pub const fn is_empty(&self) -> bool {
116        self.length.value() == 0
117    }
118
119    /// Returns the capacity of the [`DynamicArray`].
120    #[inline(always)]
121    pub const fn capacity(&self) -> Length {
122        self.capacity
123    }
124
125    /// Represents the [`DynamicArray`] as a slice.
126    #[inline(always)]
127    pub fn as_slice(&self) -> &[T] {
128        let ptr = self.data_ptr();
129        let len: usize = self.length.into();
130        debug_assert!(ptr.is_aligned(), "Data pointer is not aligned correctly.");
131        debug_assert!(len <= Self::MAX_LENGTH, "Length is too long.");
132        unsafe { core::slice::from_raw_parts(ptr, len) }
133    }
134
135    /// Represents the [`DynamicArray`] as a mutable slice.
136    #[inline(always)]
137    pub fn as_slice_mut(&mut self) -> &mut [T] {
138        let ptr = self.data_ptr();
139        let len: usize = self.length.into();
140        debug_assert!(ptr.is_aligned(), "Data pointer is not aligned correctly.");
141        debug_assert!(len <= Self::MAX_LENGTH, "Length is too long.");
142        unsafe { core::slice::from_raw_parts_mut(ptr, len) }
143    }
144
145    /// Pushes a new element to the end of the [`DynamicArray`].
146    ///
147    /// # Errors
148    ///
149    /// For details see [`DynamicArrayConstructionError`].
150    #[inline(always)]
151    pub fn push(&mut self, value: T) -> Result<(), DynamicArrayConstructionError> {
152        self.extend_from_array([value])
153    }
154
155    /// Extends the [`DynamicArray`] with the given array.
156    ///
157    /// # Errors
158    ///
159    /// For details see [`DynamicArrayConstructionError`].
160    #[inline(always)]
161    pub fn extend_from_array<const N: usize>(&mut self, other: [T; N]) -> Result<(), DynamicArrayConstructionError> {
162        if N == 0 {
163            return Ok(());
164        }
165
166        if N > Self::MAX_LENGTH {
167            return Err(DynamicArrayConstructionError::ArrayTooLong);
168        }
169
170        let len = self.length.value() as usize;
171        let capacity = self.capacity.value() as usize;
172
173        if len + N > capacity {
174            let missing = len + N - capacity;
175            let at_least = (capacity + missing) as i32;
176            let new_capacity = Self::grow_formula(at_least);
177            self.grow(new_capacity)?;
178        }
179
180        let ptr = self.data_ptr();
181        unsafe {
182            let end_ptr = ptr.add(len);
183            end_ptr.copy_from_nonoverlapping(other.as_ptr(), N);
184            core::mem::forget(other);
185        }
186
187        self.length.inc(N as i32);
188        Ok(())
189    }
190
191    /// Pops last element from the [`DynamicArray`],
192    /// decreasing its size.
193    ///
194    /// # Returns
195    ///
196    /// * `Some(T)` if `self.len() > 0`
197    /// * `None` otherwise
198    pub fn pop(&mut self) -> Option<T> {
199        if self.is_empty() {
200            None
201        } else {
202            Some(unsafe { self.pop_unchecked() })
203        }
204    }
205
206    /// Unsafe variant of [`pop`][`Self::pop`].
207    ///
208    /// # Safety
209    ///
210    /// Returns `T` if `self.len() > 0` and decreases the
211    /// [`DynamicArray`] size. The behaviour is undefined if
212    /// `self.len() == 0`.
213    #[inline]
214    pub unsafe fn pop_unchecked(&mut self) -> T {
215        debug_assert!(!self.is_empty(), "Tried pop_unchecked on length 0 DynamicArray.");
216        unsafe {
217            let ptr = self.data_ptr();
218            self.length.dec(1);
219            ptr.add(self.length.into()).read()
220        }
221    }
222
223    #[inline(always)]
224    fn data_ptr(&self) -> *mut T {
225        unsafe { self.ptr.as_ptr().cast::<T>() }
226    }
227
228    #[inline(always)]
229    const fn layout(size: usize) -> Layout {
230        let align = align_of::<T>();
231        let byte_size = size * size_of::<T>();
232        unsafe { Layout::from_size_align_unchecked(byte_size, align) }
233    }
234
235    fn grow(&mut self, new_capacity: Length) -> Result<(), AllocationError> {
236        assert!(
237            new_capacity > self.capacity,
238            "New capacity is less than or equal to the current capacity."
239        );
240        let new_layout = Self::layout(new_capacity.into());
241        let new_ptr = if self.capacity == Length::ZERO {
242            self.allocator.allocate(new_layout)
243        } else {
244            let old_layout = Self::layout(self.capacity.into());
245            self.ptr.clone().resize(old_layout, new_layout)
246        }?;
247
248        let data_ptr = unsafe { new_ptr.as_ptr().cast::<T>() };
249        assert!(
250            data_ptr.is_aligned(),
251            "Newly allocated memory is not aligned correctly."
252        );
253        self.ptr = new_ptr;
254        self.capacity = new_capacity;
255        Ok(())
256    }
257}
258
259impl<T, TAllocator: Allocator> Drop for DynamicArray<T, TAllocator> {
260    fn drop(&mut self) {
261        if self.capacity == Length::ZERO {
262            return;
263        }
264
265        if core::mem::needs_drop::<T>() {
266            unsafe {
267                let mut ptr = self.ptr.as_ptr().cast::<T>();
268                let len = self.length.into();
269                let end = ptr.add(len);
270                while ptr < end {
271                    drop(ptr.read());
272                    ptr = ptr.add(1);
273                }
274            }
275        }
276        let layout = Self::layout(self.capacity.into());
277        self.ptr.clone().deallocate(layout);
278    }
279}
280
281impl<T: Clone, TAllocator: Allocator> DynamicArray<T, TAllocator> {
282    /// Extends the [`DynamicArray`] with the given slice. It copies
283    /// slice's elements one by one.
284    ///
285    /// # Errors
286    ///
287    /// For details see [`DynamicArrayConstructionError`].
288    #[inline(always)]
289    pub fn extend_from_slice(&mut self, slice: &[T]) -> Result<(), DynamicArrayConstructionError> {
290        let slice_len = slice.len();
291        if slice_len == 0 {
292            return Ok(());
293        }
294
295        if slice_len > Self::MAX_LENGTH {
296            return Err(DynamicArrayConstructionError::ArrayTooLong);
297        }
298
299        let len = self.length.value() as usize;
300        let capacity = self.capacity.value() as usize;
301
302        if len + slice_len > capacity {
303            let missing = len + slice_len - capacity;
304            let at_least = (capacity + missing) as i32;
305            let new_capacity = Self::grow_formula(at_least);
306            self.grow(new_capacity)?;
307        }
308
309        let ptr = self.data_ptr();
310        unsafe {
311            let mut end_ptr = ptr.add(len);
312            for value in slice {
313                end_ptr.write(value.clone());
314                end_ptr = end_ptr.add(1);
315            }
316        }
317
318        self.length.inc(slice_len as i32);
319        Ok(())
320    }
321
322    /// Tries to clone the [`DynamicArray`].
323    ///
324    /// # Errors
325    ///
326    /// For details see [`DynamicArrayConstructionError`].
327    #[inline(always)]
328    pub fn try_clone(&self) -> Result<Self, DynamicArrayConstructionError> {
329        let mut new_array = Self::with_capacity_and_allocator(self.capacity, self.allocator.clone())?;
330        new_array.extend_from_slice(self.as_slice())?;
331        Ok(new_array)
332    }
333}
334
335impl<T: Clone, TAllocator: Allocator> Clone for DynamicArray<T, TAllocator> {
336    fn clone(&self) -> Self {
337        self.try_clone().expect("Failed to clone the array")
338    }
339}
340
341impl<T: PartialEq, TAllocator1: Allocator, TAllocator2: Allocator> PartialEq<DynamicArray<T, TAllocator1>>
342    for DynamicArray<T, TAllocator2>
343{
344    fn eq(&self, other: &DynamicArray<T, TAllocator1>) -> bool {
345        self.as_slice() == other.as_slice()
346    }
347}
348
349impl<T: Eq, TAllocator: Allocator> Eq for DynamicArray<T, TAllocator> {}
350
351impl<T: core::hash::Hash, TAllocator: Allocator> core::hash::Hash for DynamicArray<T, TAllocator> {
352    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
353        self.as_slice().hash(state);
354    }
355}
356
357impl<T, TAllocator: Allocator> Deref for DynamicArray<T, TAllocator> {
358    type Target = [T];
359
360    fn deref(&self) -> &Self::Target {
361        self.as_slice()
362    }
363}
364
365impl<T, TAllocator: Allocator> core::ops::DerefMut for DynamicArray<T, TAllocator> {
366    fn deref_mut(&mut self) -> &mut Self::Target {
367        self.as_slice_mut()
368    }
369}
370
371#[allow(clippy::missing_fields_in_debug)]
372impl<T, TAllocator: Allocator> core::fmt::Debug for DynamicArray<T, TAllocator> {
373    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
374        f.debug_struct("DynamicArray")
375            .field("raw_ptr", &self.data_ptr().addr())
376            .field("length", &self.length)
377            .field("capacity", &self.capacity)
378            .finish()
379    }
380}
381
382impl<T, TAllocator: Allocator> Default for DynamicArray<T, TAllocator> {
383    fn default() -> Self {
384        Self::new()
385    }
386}
387
388impl<T, TAllocator: Allocator> AsRef<[T]> for DynamicArray<T, TAllocator> {
389    fn as_ref(&self) -> &[T] {
390        self.as_slice()
391    }
392}
393
394unsafe impl<T: Send, TAllocator: Allocator> Send for DynamicArray<T, TAllocator> {}
395unsafe impl<T: Sync, TAllocator: Allocator> Sync for DynamicArray<T, TAllocator> {}
osom_tools_runtime/arrays/dynamic_array.rs

osom_tools_runtime/arrays/
dynamic_array.rs
