luaur_common/records/
vec_deque.rs

1use core::alloc::Layout;
2use core::cmp;
3use core::marker::PhantomData;
4use core::ptr::{self, NonNull};
5
6#[allow(non_snake_case)]
7pub struct VecDeque<T> {
8    pub(crate) buffer: Option<NonNull<T>>,
9    pub(crate) buffer_capacity: usize,
10    pub(crate) head: usize,
11    pub(crate) queue_size: usize,
12    pub(crate) _marker: PhantomData<T>,
13}
14
15impl<T> VecDeque<T> {
16    /// `VecDeque(std::initializer_list<T>)` — construct from a list, reserving
17    /// exactly the element count so the buffer is contiguous with
18    /// `capacity == size` (no growth), matching the C++ initializer-list ctor.
19    pub fn from_init_list(items: Vec<T>) -> Self {
20        let mut q = Self::new();
21        if !items.is_empty() {
22            q.reserve(items.len());
23        }
24        for item in items {
25            q.push_back(item);
26        }
27        q
28    }
29
30    pub(crate) fn allocate(&self, capacity: usize) -> NonNull<T> {
31        if capacity == 0 {
32            panic!("Zero capacity allocation");
33        }
34        let layout = Layout::array::<T>(capacity).unwrap();
35        unsafe {
36            let ptr = std::alloc::alloc(layout);
37            NonNull::new(ptr as *mut T).expect("Allocation failed")
38        }
39    }
40
41    pub(crate) fn deallocate(&self, ptr: Option<NonNull<T>>, capacity: usize) {
42        if let Some(p) = ptr {
43            if capacity > 0 {
44                let layout = Layout::array::<T>(capacity).unwrap();
45                unsafe {
46                    std::alloc::dealloc(p.as_ptr() as *mut u8, layout);
47                }
48            }
49        }
50    }
51
52    pub(crate) fn grow(&mut self) {
53        let old_capacity = self.capacity();
54        let new_capacity = if old_capacity > 0 {
55            old_capacity * 3 / 2 + 1
56        } else {
57            4
58        };
59
60        if new_capacity > self.max_size() {
61            panic!("bad_array_new_length");
62        }
63
64        let new_buffer = self.allocate(new_capacity);
65        let head_size = cmp::min(self.queue_size, old_capacity - self.head);
66        let tail_size = self.queue_size - head_size;
67
68        unsafe {
69            if let Some(old_buf) = self.buffer {
70                if head_size != 0 {
71                    ptr::copy_nonoverlapping(
72                        old_buf.as_ptr().add(self.head),
73                        new_buffer.as_ptr(),
74                        head_size,
75                    );
76                }
77                if tail_size != 0 {
78                    ptr::copy_nonoverlapping(
79                        old_buf.as_ptr(),
80                        new_buffer.as_ptr().add(head_size),
81                        tail_size,
82                    );
83                }
84            }
85        }
86
87        self.deallocate(self.buffer, old_capacity);
88
89        self.buffer = Some(new_buffer);
90        self.buffer_capacity = new_capacity;
91        self.head = 0;
92    }
93
94    pub fn push_back(&mut self, value: T) {
95        if self.is_full() {
96            self.grow();
97        }
98        let next_back = self.logicalToPhysical(self.queue_size);
99        unsafe {
100            ptr::write(self.buffer.unwrap().as_ptr().add(next_back), value);
101        }
102        self.queue_size += 1;
103    }
104
105    pub fn pop_back(&mut self) {
106        assert!(!self.empty());
107        self.queue_size -= 1;
108        let next_back = self.logicalToPhysical(self.queue_size);
109        unsafe {
110            ptr::drop_in_place(self.buffer.unwrap().as_ptr().add(next_back));
111        }
112    }
113
114    pub fn push_front(&mut self, value: T) {
115        if self.is_full() {
116            self.grow();
117        }
118        self.head = if self.head == 0 {
119            self.capacity() - 1
120        } else {
121            self.head - 1
122        };
123        unsafe {
124            ptr::write(self.buffer.unwrap().as_ptr().add(self.head), value);
125        }
126        self.queue_size += 1;
127    }
128
129    pub fn pop_front(&mut self) {
130        assert!(!self.empty());
131        unsafe {
132            ptr::drop_in_place(self.buffer.unwrap().as_ptr().add(self.head));
133        }
134        self.head += 1;
135        self.queue_size -= 1;
136        if self.head == self.capacity() {
137            self.head = 0;
138        }
139    }
140
141    pub fn clear(&mut self) {
142        self.destroyElements();
143        self.head = 0;
144        self.queue_size = 0;
145    }
146
147    pub fn reserve(&mut self, new_capacity: usize) {
148        if new_capacity > self.max_size() {
149            panic!("too large");
150        }
151        let old_capacity = self.capacity();
152        if new_capacity <= old_capacity {
153            return;
154        }
155
156        let head_size = cmp::min(self.queue_size, old_capacity - self.head);
157        let tail_size = self.queue_size - head_size;
158        let new_buffer = self.allocate(new_capacity);
159
160        unsafe {
161            if let Some(old_buf) = self.buffer {
162                if head_size != 0 {
163                    ptr::copy_nonoverlapping(
164                        old_buf.as_ptr().add(self.head),
165                        new_buffer.as_ptr(),
166                        head_size,
167                    );
168                }
169                if tail_size != 0 {
170                    ptr::copy_nonoverlapping(
171                        old_buf.as_ptr(),
172                        new_buffer.as_ptr().add(head_size),
173                        tail_size,
174                    );
175                }
176            }
177        }
178
179        self.deallocate(self.buffer, old_capacity);
180        self.buffer = Some(new_buffer);
181        self.buffer_capacity = new_capacity;
182        self.head = 0;
183    }
184
185    pub fn shrink_to_fit(&mut self) {
186        let old_capacity = self.capacity();
187        let new_capacity = self.queue_size;
188        if old_capacity == new_capacity {
189            return;
190        }
191        if new_capacity == 0 {
192            self.destroyElements();
193            self.deallocate(self.buffer, old_capacity);
194            self.buffer = None;
195            self.buffer_capacity = 0;
196            self.head = 0;
197            return;
198        }
199
200        let head_size = cmp::min(self.queue_size, old_capacity - self.head);
201        let tail_size = self.queue_size - head_size;
202        let new_buffer = self.allocate(new_capacity);
203
204        unsafe {
205            if let Some(old_buf) = self.buffer {
206                if head_size != 0 {
207                    ptr::copy_nonoverlapping(
208                        old_buf.as_ptr().add(self.head),
209                        new_buffer.as_ptr(),
210                        head_size,
211                    );
212                }
213                if tail_size != 0 {
214                    ptr::copy_nonoverlapping(
215                        old_buf.as_ptr(),
216                        new_buffer.as_ptr().add(head_size),
217                        tail_size,
218                    );
219                }
220            }
221        }
222
223        self.deallocate(self.buffer, old_capacity);
224        self.buffer = Some(new_buffer);
225        self.buffer_capacity = new_capacity;
226        self.head = 0;
227    }
228
229    pub fn at(&self, pos: usize) -> &T {
230        if pos >= self.queue_size {
231            panic!("VecDeque out of range");
232        }
233        unsafe {
234            &*self
235                .buffer
236                .unwrap()
237                .as_ptr()
238                .add(self.logicalToPhysical(pos))
239        }
240    }
241
242    pub fn at_mut(&mut self, pos: usize) -> &mut T {
243        if pos >= self.queue_size {
244            panic!("VecDeque out of range");
245        }
246        unsafe {
247            &mut *self
248                .buffer
249                .unwrap()
250                .as_ptr()
251                .add(self.logicalToPhysical(pos))
252        }
253    }
254
255    pub fn front(&self) -> &T {
256        assert!(!self.empty());
257        unsafe { &*self.buffer.unwrap().as_ptr().add(self.head) }
258    }
259
260    pub fn front_mut(&mut self) -> &mut T {
261        assert!(!self.empty());
262        unsafe { &mut *self.buffer.unwrap().as_ptr().add(self.head) }
263    }
264
265    pub fn back(&self) -> &T {
266        assert!(!self.empty());
267        let back_idx = self.logicalToPhysical(self.queue_size - 1);
268        unsafe { &*self.buffer.unwrap().as_ptr().add(back_idx) }
269    }
270
271    pub fn back_mut(&mut self) -> &mut T {
272        assert!(!self.empty());
273        let back_idx = self.logicalToPhysical(self.queue_size - 1);
274        unsafe { &mut *self.buffer.unwrap().as_ptr().add(back_idx) }
275    }
276}
277
278impl<T> Drop for VecDeque<T> {
279    fn drop(&mut self) {
280        self.destroyElements();
281        self.deallocate(self.buffer, self.buffer_capacity);
282    }
283}
284
285impl<T: core::fmt::Debug> core::fmt::Debug for VecDeque<T> {
286    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
287        write!(f, "VecDeque[")?;
288        let mut first = true;
289        for i in 0..self.queue_size {
290            if !first {
291                write!(f, ", ")?;
292            }
293            first = false;
294            if let Some(buf) = self.buffer {
295                let idx = (self.head + i) % self.buffer_capacity;
296                unsafe { write!(f, "{:?}", &*buf.as_ptr().add(idx))? };
297            }
298        }
299        write!(f, "]")
300    }
301}
302
303impl<T: Clone> Clone for VecDeque<T> {
304    fn clone(&self) -> Self {
305        let mut new_deque = VecDeque::<T>::new();
306        if self.buffer_capacity > 0 {
307            let new_buffer = new_deque.allocate(self.buffer_capacity);
308            new_deque.buffer = Some(new_buffer);
309            new_deque.buffer_capacity = self.buffer_capacity;
310            new_deque.head = self.head;
311            new_deque.queue_size = self.queue_size;
312
313            let head_size = cmp::min(self.queue_size, self.buffer_capacity - self.head);
314            let tail_size = self.queue_size - head_size;
315
316            unsafe {
317                if let Some(old_buf) = self.buffer {
318                    for i in 0..head_size {
319                        let val = (&*old_buf.as_ptr().add(self.head + i)).clone();
320                        ptr::write(new_buffer.as_ptr().add(self.head + i), val);
321                    }
322                    for i in 0..tail_size {
323                        let val = (&*old_buf.as_ptr().add(i)).clone();
324                        ptr::write(new_buffer.as_ptr().add(i), val);
325                    }
326                }
327            }
328        }
329        new_deque
330    }
331}
luaur_common/records/vec_deque.rs

luaur_common/records/
vec_deque.rs
