eta_algorithms/data_structs/array/
mod.rs

1use std::alloc::{realloc, Layout};
2use std::cmp::min;
3use std::marker::PhantomData;
4use std::ops::{Index, IndexMut};
5use std::ptr;
6use std::ptr::{addr_of_mut, copy_nonoverlapping};
7
8pub mod iterator;
9
10pub struct Array<T>
11where
12    T: Copy + Sized,
13{
14    phantom_data: PhantomData<()>, // For compile time borrow checking correctness
15    layout: Layout,
16    data: *mut T,
17    capacity: usize,
18}
19
20impl<T> Clone for Array<T>
21where
22    T: Copy + Sized,
23{
24    fn clone(&self) -> Self {
25        let array = Self::new(self.capacity);
26        unsafe { copy_nonoverlapping(self.data, array.data, self.capacity) }
27        array
28    }
29}
30
31impl<T> Array<T>
32where
33    T: Copy + Sized,
34{
35    #[inline(always)]
36    pub fn capacity(&self) -> usize {
37        self.capacity
38    }
39    pub fn resize(&mut self, new_capacity: usize) {
40        let new_layout = Layout::array::<T>(new_capacity).expect("Failed to create layout");
41        let new_ptr = unsafe { realloc(self.data as *mut u8, new_layout, new_layout.size()) };
42        if new_ptr.is_null() {
43            panic!("Failed to allocate memory");
44        }
45        self.data = new_ptr as *mut T;
46        self.capacity = new_capacity;
47        self.layout = new_layout;
48    }
49    #[inline(always)]
50    pub fn resize_by(&mut self, additional_capacity: usize) {
51        self.resize(self.capacity + additional_capacity);
52    }
53
54    pub fn as_ptr(&self) -> *const T {
55        self.data
56    }
57
58    pub fn as_mut_ptr(&mut self) -> *mut T {
59        self.data
60    }
61
62    pub fn new(capacity: usize) -> Self {
63        let layout = Layout::array::<T>(capacity).expect("Failed to create layout");
64        let data = unsafe { std::alloc::alloc(layout) as *mut T };
65        if data.is_null() {
66            panic!("Failed to allocate memory");
67        }
68        Array {
69            phantom_data: PhantomData,
70            layout,
71            data,
72            capacity,
73        }
74    }
75
76    #[inline(always)]
77    pub fn new_default_bytes(capacity: usize, default: u8) -> Self {
78        let arr = Self::new(capacity);
79        unsafe { ptr::write_bytes(arr.data, default, capacity) };
80        arr
81    }
82    #[inline(always)]
83    pub fn new_with_default(capacity: usize, default: T) -> Self
84    where
85        T: Copy,
86    {
87        let mut arr = Self::new(capacity);
88        arr.fill(default);
89        arr
90    }
91
92    pub fn fill(&mut self, value: T)
93    where
94        T: Copy,
95    {
96        for i in self.iter_mut() {
97            *i = value;
98        }
99    }
100    #[inline(always)]
101    pub fn iter(&self) -> iterator::ArrayIterator<T> {
102        iterator::ArrayIterator {
103            phantom_data: &self.phantom_data,
104            data: self.data,
105            end: unsafe { self.data.add(self.capacity) },
106        }
107    }
108
109    #[inline(always)]
110    pub fn iter_mut(&mut self) -> iterator::ArrayIteratorMut<T> {
111        iterator::ArrayIteratorMut {
112            phantom_data: &mut self.phantom_data,
113            data: self.data,
114            end: unsafe { self.data.add(self.capacity) },
115        }
116    }
117
118    #[inline(always)]
119    pub fn iter_range(&self, start: usize, end: usize) -> iterator::ArrayIterator<T> {
120        iterator::ArrayIterator {
121            phantom_data: &self.phantom_data,
122            data: unsafe { self.data.add(start) },
123            end: unsafe { min(self.data.add(end), self.data.add(self.capacity)) },
124        }
125    }
126
127    #[inline(always)]
128    pub fn iter_range_mut(&mut self, start: usize, end: usize) -> iterator::ArrayIteratorMut<T> {
129        iterator::ArrayIteratorMut {
130            phantom_data: &mut self.phantom_data,
131            data: unsafe { self.data.add(start) },
132            end: unsafe { min(self.data.add(end), self.data.add(self.capacity)) },
133        }
134    }
135
136    /// Extremely unsafe as it bypasses lifetime checks. Use if you know what you are doing.
137    /// This is good for cases where you need dynamically retrieve multiple mutable iterators to chunks of non-overlapping data.
138    #[inline(always)]
139    pub unsafe fn iter_range_mut_unchecked(&mut self, start: usize, end: usize) -> iterator::ArrayIteratorMut<'static, T> {
140        static mut PHANTOM: PhantomData<()> = PhantomData;
141        iterator::ArrayIteratorMut {
142            phantom_data: &mut *addr_of_mut!(PHANTOM),
143            data: unsafe { self.data.add(start) },
144            end: unsafe { min(self.data.add(end), self.data.add(self.capacity)) },
145        }
146    }
147
148    /// Copies the contents of the vector into the array.
149    pub fn from_vec(vec: Vec<T>) -> Self {
150        let arr = Self::new(vec.len());
151        unsafe {
152            copy_nonoverlapping(vec.as_ptr(), arr.data, arr.capacity);
153            arr
154        }
155    }
156    /// Copies the contents of the slice into the array.
157    pub fn from_slice(slice: &[T]) -> Self {
158        let arr = Self::new(slice.len());
159        unsafe {
160            copy_nonoverlapping(slice.as_ptr(), arr.data, arr.capacity);
161            arr
162        }
163    }
164
165    pub fn as_slice(&self) -> &[T] {
166        unsafe { std::slice::from_raw_parts(self.data, self.capacity) }
167    }
168
169    pub fn as_mut_slice(&mut self) -> &mut [T] {
170        unsafe { std::slice::from_raw_parts_mut(self.data, self.capacity) }
171    }
172
173    pub fn split_at(&mut self, index: usize) -> (&[T], &[T]) {
174        if index >= self.capacity {
175            panic!("Index out of bounds");
176        }
177        let new_data = unsafe { self.data.add(index) };
178        let left = unsafe { std::slice::from_raw_parts(self.data, index) };
179        let right = unsafe { std::slice::from_raw_parts(new_data, self.capacity - index) };
180        (left, right)
181    }
182
183    pub fn split_at_mut(&mut self, index: usize) -> (&mut [T], &mut [T]) {
184        if index >= self.capacity {
185            panic!("Index out of bounds");
186        }
187        let new_data = unsafe { self.data.add(index) };
188        let left = unsafe { std::slice::from_raw_parts_mut(self.data, index) };
189        let right = unsafe { std::slice::from_raw_parts_mut(new_data, self.capacity - index) };
190        (left, right)
191    }
192
193    pub fn split_into_parts(&self, parts: usize) -> Array<&[T]> {
194        if parts > self.capacity {
195            panic!("Parts must be less than or equal to the capacity of the array");
196        }
197
198        if parts == 0 {
199            panic!("Parts cannot be 0");
200        }
201
202        let chunk_size = self.capacity / parts;
203        let remainder = self.capacity % parts;
204
205        let mut arr = Array::<&[T]>::new(parts);
206        let mut ptr = self.data as *const T;
207        for i in 0..parts - 1 {
208            arr[i] = unsafe { std::slice::from_raw_parts(ptr, chunk_size) };
209            ptr = unsafe { ptr.add(chunk_size) };
210        }
211
212        arr[parts - 1] = unsafe { std::slice::from_raw_parts(ptr, chunk_size + remainder) };
213
214        arr
215    }
216    pub fn split_into_parts_mut(&mut self, parts: usize) -> Vec<&mut [T]> {
217        if parts >= self.capacity {
218            panic!("Parts must be less than or equal to the capacity of the array");
219        }
220
221        if parts == 0 {
222            panic!("Parts cannot be 0");
223        }
224
225        let chunk_size = self.capacity / parts;
226        let remainder = self.capacity % parts;
227
228        let mut arr = Vec::<&mut [T]>::with_capacity(parts);
229        let mut ptr = self.data;
230        for _ in 0..parts - 1 {
231            arr.push(unsafe { std::slice::from_raw_parts_mut(ptr, chunk_size) });
232            ptr = unsafe { ptr.add(chunk_size) };
233        }
234
235        arr.push(unsafe { std::slice::from_raw_parts_mut(ptr, chunk_size + remainder) });
236        arr
237    }
238    #[inline(always)]
239    pub unsafe fn index_unchecked(&self, index: usize) -> &T {
240        self.data.add(index).as_ref().unwrap()
241    }
242
243    #[inline(always)]
244    pub unsafe fn index_unchecked_mut(&mut self, index: usize) -> &mut T {
245        self.data.add(index).as_mut().unwrap()
246    }
247}
248
249impl<T> Drop for Array<T>
250where
251    T: Copy + Sized,
252{
253    fn drop(&mut self) {
254        unsafe {
255            std::alloc::dealloc(self.data as *mut u8, self.layout);
256        }
257    }
258}
259
260impl<T> Index<usize> for Array<T>
261where
262    T: Copy + Sized,
263{
264    type Output = T;
265
266    #[inline(always)]
267    fn index(&self, index: usize) -> &Self::Output {
268        if index >= self.capacity {
269            panic!("Index out of bounds");
270        }
271
272        unsafe { &*self.data.add(index) }
273    }
274}
275
276impl<T> IndexMut<usize> for Array<T>
277where
278    T: Copy + Sized,
279{
280    #[inline(always)]
281    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
282        if index >= self.capacity {
283            panic!("Index out of bounds");
284        }
285        unsafe { &mut *self.data.add(index) }
286    }
287}
eta_algorithms/data_structs/array/mod.rs

eta_algorithms/data_structs/array/
mod.rs
