commonlibsse_ng\re\m\MemoryManager/
SimpleArray.rs

1use core::alloc::Layout;
2use core::cmp::Ordering;
3use core::hash::{Hash, Hasher};
4use core::mem::MaybeUninit;
5use core::ptr::{self, NonNull};
6use core::slice;
7use std::alloc::handle_alloc_error;
8
9use crate::re::MemoryManager::TESGlobalAlloc;
10use stdx::alloc::Allocator;
11use stdx::ptr::{ConstNonNull, Unique};
12
13/// Array whose first pointer is only a pointer to the length.
14///
15/// Memory layout:
16/// ```txt
17/// ┌────────────┬────────────┬────────────┬──────┬────────────┐
18/// │ len: usize │ T[0]       │ T[1]       │ ...  │ T[N - 1]   │
19/// └────────────┴────────────┴────────────┴──────┴────────────┘
20///                   ↑
21///   data: Unique<T> ┘
22/// ```
23/// # Example
24/// ```rust
25/// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
26/// let array: SimpleArray<i32> = SimpleArray::new();
27/// assert_eq!(array.len(), 0);
28/// ```
29pub struct SimpleArray<T, A: Allocator = TESGlobalAlloc> {
30    data: Option<Unique<T>>,
31    alloc: A,
32}
33const _: () = assert!(core::mem::size_of::<SimpleArray<i32>>() == core::mem::size_of::<usize>());
34
35impl<T> SimpleArray<T> {
36    /// Creates a new empty `SimpleArray`.
37    ///
38    /// # Example
39    /// ```rust
40    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
41    /// let array: SimpleArray<i32> = SimpleArray::new();
42    /// assert_eq!(array.len(), 0);
43    /// ```
44    #[inline]
45    pub const fn new() -> Self {
46        Self { data: None, alloc: TESGlobalAlloc }
47    }
48
49    /// Creates a new `SimpleArray` with the specified capacity.
50    ///
51    /// Uninitialized memory leads to undefined operation, so 0 is entered.
52    ///
53    /// # Panics
54    /// This function may panic if the allocation fails.
55    ///
56    /// # Example
57    /// ```rust
58    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
59    /// let array: SimpleArray<i32> = SimpleArray::with_capacity(5);
60    /// assert_eq!(array.len(), 5);
61    /// ```
62    #[inline]
63    pub fn with_capacity(count: usize) -> Self {
64        let mut array = Self::new();
65        array.resize(count);
66        array
67    }
68}
69
70impl<T, A> SimpleArray<T, A>
71where
72    A: Allocator,
73{
74    /// Creates a new empty `SimpleArray` with Allocator.
75    ///
76    /// # Example
77    /// ```rust
78    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
79    /// use stdx::alloc::Global; // Since TESAllocator is not available for CI, use Rust's.
80    ///
81    /// let array: SimpleArray<i32, Global> = SimpleArray::new_in(None, Global);
82    /// assert_eq!(array.len(), 0);
83    /// ```
84    #[inline]
85    pub const fn new_in(data: Option<Unique<T>>, alloc: A) -> Self {
86        Self { data, alloc }
87    }
88
89    /// Returns the length of the array (the number of elements currently stored).
90    ///
91    /// Equivalent C++ `size()`
92    ///
93    /// # Example
94    /// ```rust
95    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
96    /// let array: SimpleArray<i32> = SimpleArray::with_capacity(5);
97    /// assert_eq!(array.len(), 5);
98    /// ```
99    #[inline]
100    pub const fn len(&self) -> usize {
101        match self.len_ptr() {
102            Some(ptr) => unsafe { ptr.read() },
103            None => 0,
104        }
105    }
106
107    /// Checks if the array is empty.
108    ///
109    /// # Example
110    /// ```rust
111    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
112    /// let array: SimpleArray<i32> = SimpleArray::new();
113    /// assert!(array.is_empty());
114    /// ```
115    #[inline]
116    pub const fn is_empty(&self) -> bool {
117        self.len() == 0
118    }
119
120    /// Clears the array by deallocating its memory.
121    ///
122    /// # Safety
123    /// This function performs unsafe operations to deallocate the array memory.
124    ///
125    /// # Example
126    /// ```rust
127    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
128    /// let mut array: SimpleArray<i32> = SimpleArray::with_capacity(3);
129    /// array.clear();
130    /// assert!(array.is_empty());
131    /// ```
132    #[inline]
133    pub fn clear(&mut self) {
134        if self.data.is_none() && self.is_empty() {
135            return;
136        }
137
138        if let Some(len_ptr) = self.len_ptr_mut() {
139            unsafe { ptr::drop_in_place(self.as_mut_slice()) };
140            unsafe { self.alloc.deallocate(len_ptr.cast(), Self::layout(self.len())) };
141            self.data = None; // FIXME: Use after free?
142        }
143    }
144
145    /// Resizes the array to the specified count.
146    ///
147    /// # Panics
148    /// This function may panic if the allocation fails.
149    ///
150    /// # Example
151    /// ```rust
152    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
153    /// let mut array = SimpleArray::<u32>::with_capacity(3);
154    /// array.resize(5);
155    /// assert_eq!(array.len(), 5);
156    /// ```
157    pub fn resize(&mut self, count: usize) {
158        if count == 0 {
159            self.clear();
160            return;
161        }
162
163        let old_size = self.len();
164        if old_size == count {
165            return;
166        }
167
168        unsafe {
169            let layout = Self::layout(count);
170            let Ok(new_head) = self.alloc.allocate(layout) else { handle_alloc_error(layout) };
171            let new_head = new_head.cast::<usize>();
172            new_head.write(count); // The first pointer is the length.
173
174            let new_data = new_head.add(1).cast::<T>();
175
176            // clone to new array.
177            if let Some(prev_data) = self.data {
178                let prev_data = prev_data.as_ptr();
179                let new_data = new_data.as_ptr();
180                if count < old_size {
181                    ptr::copy_nonoverlapping(prev_data, new_data, count);
182                } else {
183                    ptr::copy_nonoverlapping(prev_data, new_data, old_size);
184                    for i in old_size..count {
185                        ptr::write(new_data.add(i), MaybeUninit::zeroed().assume_init());
186                    }
187                }
188            } else {
189                ptr::write_bytes(new_data.as_ptr(), MaybeUninit::zeroed().assume_init(), count);
190            }
191
192            self.clear(); // clear prev data array.
193
194            self.data = Some(Unique::from(new_data));
195        }
196    }
197
198    /// Gets a reference to the element at the given index.
199    ///
200    /// Return `None` if the index is out of bounds.
201    ///
202    /// # Example
203    /// ```rust
204    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
205    /// let mut array = SimpleArray::with_capacity(3);
206    /// array[0] = 1;
207    /// assert_eq!(array.get(0), Some(&1));
208    /// assert_eq!(array.get(5), None);
209    /// ```
210    #[inline]
211    pub fn get(&self, index: usize) -> Option<&T> {
212        if index < self.len() { unsafe { Some(self.data()?.add(index).as_ref()) } } else { None }
213    }
214
215    /// Gets a mutable reference to the element at the given index.
216    ///
217    /// Return `None` if the index is out of bounds.
218    ///
219    /// # Example
220    /// ```rust
221    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
222    /// let mut array = SimpleArray::<i32>::with_capacity(3);
223    /// if let Some(value) = array.get_mut(1) {
224    ///     *value = 42;
225    /// };
226    /// assert_eq!(array[1], 42);
227    /// assert_eq!(array.get_mut(5), None);
228    /// ```
229    #[inline]
230    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
231        if index < self.len() { unsafe { Some(self.data()?.add(index).as_mut()) } } else { None }
232    }
233
234    /// Returns a raw pointer to the data.
235    ///
236    /// Equivalent C++ `data()`
237    ///
238    /// # Example
239    /// ```rust
240    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
241    /// let array: SimpleArray<i32> = SimpleArray::new();
242    /// let data = array.as_ptr();
243    /// ```
244    #[inline]
245    pub const fn as_ptr(&self) -> *mut T {
246        match self.data {
247            Some(non_null) => non_null.as_ptr(),
248            None => ptr::null_mut(),
249        }
250    }
251
252    /// Returns a mutable slice of the array.
253    ///
254    /// # Safety
255    /// This function assumes that the array is properly initialized.
256    ///
257    /// # Example
258    /// ```rust
259    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
260    /// let mut array = SimpleArray::with_capacity(4);
261    /// let slice = array.as_mut_slice();
262    /// slice.copy_from_slice(&[1, 2, 3, 4]);
263    /// ```
264    #[inline]
265    pub const fn as_mut_slice(&mut self) -> &mut [T] {
266        let len = self.len();
267        if len == 0 {
268            return &mut [];
269        }
270
271        match self.data {
272            Some(ptr) => unsafe { slice::from_raw_parts_mut(ptr.as_ptr(), len) },
273            None => &mut [],
274        }
275    }
276
277    /// Returns a slice of the array.
278    ///
279    /// # Safety
280    /// This function assumes that the array is properly initialized.
281    ///
282    /// # Example
283    /// ```rust
284    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
285    /// let array = SimpleArray::<i32>::with_capacity(4);
286    /// let slice = array.as_slice();
287    /// assert_eq!(slice, &[0, 0, 0, 0]);
288    /// ```
289    #[inline]
290    pub const fn as_slice(&self) -> &[T] {
291        let len = self.len();
292        if len == 0 {
293            return &[];
294        }
295
296        match self.data {
297            Some(ptr) => unsafe { slice::from_raw_parts(ptr.as_ptr(), len) },
298            None => &[],
299        }
300    }
301
302    /// Return len storage ptr.
303    #[inline]
304    const fn len_ptr(&self) -> Option<ConstNonNull<usize>> {
305        match self.data {
306            Some(data) => unsafe {
307                let ptr = data.as_non_null_ptr().cast::<usize>().sub(1);
308                ConstNonNull::new(ptr.as_ptr())
309            },
310            None => None,
311        }
312    }
313
314    /// Return len storage ptr.(allocated top pointer)
315    #[inline]
316    const fn len_ptr_mut(&mut self) -> Option<NonNull<usize>> {
317        match self.data.as_mut() {
318            Some(data) => unsafe { Some(data.as_non_null_ptr().cast::<usize>().sub(1)) },
319            None => None,
320        }
321    }
322
323    /// Return data ptr.
324    #[inline]
325    const fn data(&self) -> Option<NonNull<T>> {
326        match self.data {
327            Some(data) => Some(data.as_non_null_ptr()),
328            None => None,
329        }
330    }
331
332    /// Size + Element * N
333    ///
334    /// # Error
335    /// If need count(alloc size) > isize::MAX.
336    fn layout(count: usize) -> Layout {
337        let layout = {
338            const LEN_SIZE: usize = core::mem::size_of::<usize>(); // 8
339            const LEN_ALIGN: usize = core::mem::align_of::<usize>(); // x64 => 8
340
341            // Heap head is filled with usize len information
342            let alloc_size = LEN_SIZE + (core::mem::size_of::<T>() * count);
343
344            // IMPORTANT: Avoid undefined behavior.
345            // When T alignment is less than or equal to usize, undefined behavior occurs when storing usize if alignment is made based on T criteria.
346            // Therefore, the alignment must be kept above usize.
347            let alignment = LEN_ALIGN.max(core::mem::align_of::<T>());
348
349            Layout::from_size_align(alloc_size, alignment)
350        };
351
352        match layout {
353            Ok(layout) => layout,
354            Err(err) => panic!("SimpleArray alloc overflow: need size > isize::MAX: {err}"),
355        }
356    }
357
358    /// Creates an iterator that borrows the elements of the `SimpleArray`.
359    ///
360    /// This method returns an iterator over references to the elements of the array. The iterator
361    /// allows you to traverse the array without consuming it, meaning the array remains usable after
362    /// the iteration.
363    ///
364    /// # Example
365    ///
366    /// ```rust
367    /// use commonlibsse_ng::re::MemoryManager::SimpleArray::SimpleArray;
368    /// let mut array = SimpleArray::with_capacity(3);
369    /// let slice = array.as_mut_slice();
370    /// slice[0] = 10;
371    /// slice[1] = 20;
372    /// slice[2] = 30;
373    ///
374    /// let sum: i32 = array.iter().sum();
375    /// assert_eq!(sum, 60);
376    /// ```
377    #[inline]
378    pub const fn iter(&self) -> SimpleArrayIterator<'_, T, A> {
379        SimpleArrayIterator { array: self, index: 0, len: self.len() }
380    }
381}
382
383impl<T, A: Allocator> Drop for SimpleArray<T, A> {
384    fn drop(&mut self) {
385        if self.data.is_none() && self.is_empty() {
386            return;
387        }
388
389        // NOTE: If `self.clear()` is used here, len will be set to 0 before deallocate, and layout inconsistency will occur.
390        //       Therefore, `self.clear()` is not used.
391        if let Some(len_ptr) = self.len_ptr_mut() {
392            unsafe { ptr::drop_in_place(self.as_mut_slice()) };
393            unsafe { self.alloc.deallocate(len_ptr.cast(), Self::layout(self.len())) };
394        }
395    }
396}
397
398impl<T> Default for SimpleArray<T> {
399    #[inline]
400    fn default() -> Self {
401        Self::new()
402    }
403}
404
405impl<T: PartialEq, A: Allocator> PartialEq for SimpleArray<T, A> {
406    fn eq(&self, other: &Self) -> bool {
407        if self.len() != other.len() {
408            return false;
409        }
410        for i in 0..self.len() {
411            if self.get(i) != other.get(i) {
412                return false;
413            }
414        }
415        true
416    }
417}
418
419impl<T: Eq, A: Allocator> Eq for SimpleArray<T, A> {}
420
421impl<T: PartialOrd, A: Allocator> PartialOrd for SimpleArray<T, A> {
422    #[inline]
423    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
424        if self.len() != other.len() {
425            return None;
426        }
427        for i in 0..self.len() {
428            match self[i].partial_cmp(&other[i]) {
429                Some(Ordering::Equal) => {}
430                Some(ordering) => return Some(ordering),
431                None => return None,
432            }
433        }
434        Some(Ordering::Equal)
435    }
436}
437
438impl<T: Ord, A: Allocator> Ord for SimpleArray<T, A> {
439    #[inline]
440    fn cmp(&self, other: &Self) -> Ordering {
441        if self.len() != other.len() {
442            return self.len().cmp(&other.len());
443        }
444        for i in 0..self.len() {
445            match self[i].cmp(&other[i]) {
446                Ordering::Equal => {}
447                ordering => return ordering,
448            }
449        }
450        Ordering::Equal
451    }
452}
453
454impl<T: Hash, A: Allocator> Hash for SimpleArray<T, A> {
455    #[inline]
456    fn hash<H: Hasher>(&self, state: &mut H) {
457        for i in 0..self.len() {
458            self.get(i).hash(state);
459        }
460    }
461}
462
463impl<T, A: Allocator> core::ops::Index<usize> for SimpleArray<T, A> {
464    type Output = T;
465
466    #[inline]
467    fn index(&self, index: usize) -> &Self::Output {
468        assert!(index < self.len(), "Index out of bounds");
469        unsafe { self.data().expect("Accessing empty array").add(index).as_ref() }
470    }
471}
472
473impl<T, A: Allocator> core::ops::IndexMut<usize> for SimpleArray<T, A> {
474    #[inline]
475    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
476        assert!(index < self.len(), "Index out of bounds");
477        unsafe { self.data().expect("Accessing empty array").add(index).as_mut() }
478    }
479}
480
481// Iterator for borrowing `SimpleArray`
482pub struct SimpleArrayIterator<'a, T, A>
483where
484    A: Allocator,
485{
486    array: &'a SimpleArray<T, A>,
487    index: usize,
488    len: usize, // store the length to avoid redundant calculations
489}
490
491impl<'a, T, A: Allocator> Iterator for SimpleArrayIterator<'a, T, A> {
492    type Item = &'a T;
493
494    #[inline]
495    fn next(&mut self) -> Option<Self::Item> {
496        if self.index < self.len {
497            let item = unsafe { self.array.data()?.add(self.index).as_ref() };
498            self.index += 1;
499            Some(item)
500        } else {
501            None
502        }
503    }
504}
505
506// IntoIterator for consuming `SimpleArray`
507pub struct SimpleArrayIntoIterator<T, A: Allocator> {
508    array: SimpleArray<T, A>,
509    index: usize,
510    len: usize, // store the length to avoid redundant calculations
511}
512
513impl<T, A: Allocator> Iterator for SimpleArrayIntoIterator<T, A> {
514    type Item = T;
515
516    #[inline]
517    fn next(&mut self) -> Option<Self::Item> {
518        if self.index < self.len {
519            let item = unsafe { ptr::read(self.array.data()?.add(self.index).as_ptr()) };
520            self.index += 1;
521            Some(item)
522        } else {
523            None
524        }
525    }
526}
527
528impl<T, A: Allocator> IntoIterator for SimpleArray<T, A> {
529    type Item = T;
530    type IntoIter = SimpleArrayIntoIterator<T, A>;
531
532    #[inline]
533    fn into_iter(self) -> Self::IntoIter {
534        let len = self.len();
535        SimpleArrayIntoIterator { array: self, index: 0, len }
536    }
537}
538
539impl<'a, T, A: Allocator> IntoIterator for &'a SimpleArray<T, A> {
540    type Item = &'a T;
541    type IntoIter = SimpleArrayIterator<'a, T, A>;
542
543    #[inline]
544    fn into_iter(self) -> Self::IntoIter {
545        self.iter()
546    }
547}
548
549#[cfg(test)]
550mod tests {
551    use super::*;
552
553    #[test]
554    fn test_new() {
555        let array: SimpleArray<i32> = SimpleArray::new();
556        assert_eq!(array.len(), 0);
557        assert!(array.is_empty());
558    }
559
560    #[test]
561    fn test_with_capacity() {
562        let array: SimpleArray<i32> = SimpleArray::with_capacity(5);
563        assert_eq!(array.len(), 5);
564        assert!(!array.is_empty());
565    }
566
567    #[test]
568    fn test_resize_grow() {
569        let mut array = SimpleArray::<u32>::with_capacity(3);
570        array.resize(5);
571        assert_eq!(array.len(), 5);
572    }
573
574    #[test]
575    fn test_resize_shrink() {
576        let mut array = SimpleArray::<u32>::with_capacity(5);
577        array.resize(2);
578        assert_eq!(array.len(), 2);
579    }
580
581    #[test]
582    fn test_data_access() {
583        let mut array = SimpleArray::with_capacity(3);
584        let slice = array.as_mut_slice();
585        slice[0] = 10;
586        slice[1] = 20;
587        slice[2] = 30;
588
589        let new_slice = array.as_slice();
590        assert_eq!(new_slice, &[10, 20, 30]);
591    }
592
593    #[test]
594    fn test_clear() {
595        // alloc (len: 8 + (u32: 4 * count: 3) = 20bytes)
596        let mut array = SimpleArray::<u32>::with_capacity(3);
597        array.clear();
598        assert_eq!(array.len(), 0);
599        assert!(array.is_empty());
600    }
601
602    #[test]
603    fn test_as_slice() {
604        let mut array = SimpleArray::with_capacity(4);
605        let slice = array.as_mut_slice();
606        slice.copy_from_slice(&[1, 2, 3, 4]);
607
608        let new_slice = array.as_slice();
609        assert_eq!(new_slice, &[1, 2, 3, 4]);
610    }
611
612    #[test]
613    fn test_into_iterator() {
614        let mut array = SimpleArray::with_capacity(5);
615        let slice = array.as_mut_slice();
616        slice[0] = 10;
617        slice[1] = 20;
618        slice[2] = 30;
619        slice[3] = 40;
620        slice[4] = 50;
621
622        let collected: Vec<_> = array.into_iter().collect();
623        assert_eq!(collected, vec![10, 20, 30, 40, 50]);
624    }
625
626    #[test]
627    fn test_iterator() {
628        let mut array = SimpleArray::with_capacity(5);
629        array[0] = 10;
630        array[1] = 20;
631        array[2] = 30;
632        array[3] = 40;
633        array[4] = 50;
634
635        let mut iter = array.iter();
636        assert_eq!(iter.next(), Some(&10));
637        assert_eq!(iter.next(), Some(&20));
638        assert_eq!(iter.next(), Some(&30));
639        assert_eq!(iter.next(), Some(&40));
640        assert_eq!(iter.next(), Some(&50));
641        assert_eq!(iter.next(), None); // No more elements
642    }
643}
commonlibsse_ng\re\m\MemoryManager/SimpleArray.rs

commonlibsse_ng\re\m\MemoryManager/
SimpleArray.rs
