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

osom_lib_arrays/
dynamic_array.rs
