trait_stack/
lib.rs

1#![doc = include_str!("../readme.md")]
2// Unstable features
3#![feature(ptr_metadata, unsize)]
4
5pub mod iter;
6
7use core::{
8    fmt::Debug,
9    marker::Unsize,
10    mem,
11    ops::{Index, IndexMut},
12    ptr::{self, DynMetadata, Pointee},
13};
14use iter::{Iter, IterMut};
15use std::alloc;
16use std::{alloc::Layout, ptr::NonNull};
17
18#[repr(align(16))]
19struct DefaultBuffer;
20
21pub struct TraitStack<T: ?Sized + Pointee<Metadata = DynMetadata<T>>> {
22    buf: NonNull<u8>,
23    buf_layout: Layout,
24    buf_occupied: usize,
25
26    table: Vec<(usize, DynMetadata<T>)>,
27}
28
29impl<T: ?Sized + Pointee<Metadata = DynMetadata<T>>> TraitStack<T> {
30    pub const DEFAULT_ALIGN: usize = mem::align_of::<DefaultBuffer>();
31
32    pub const fn new() -> Self {
33        Self {
34            buf: NonNull::<DefaultBuffer>::dangling().cast(),
35            buf_layout: Layout::new::<DefaultBuffer>(),
36            buf_occupied: 0,
37            table: Vec::new(),
38        }
39    }
40
41    pub const fn buf_layout(&self) -> Layout {
42        self.buf_layout
43    }
44
45    #[inline]
46    pub fn table_capacity(&self) -> usize {
47        self.table.capacity()
48    }
49
50    #[inline]
51    pub fn len(&self) -> usize {
52        self.table.len()
53    }
54
55    #[inline]
56    pub fn is_empty(&self) -> bool {
57        self.table.is_empty()
58    }
59
60    #[inline]
61    pub fn buf_ptr(&self) -> *const u8 {
62        self.buf.as_ptr().cast_const()
63    }
64
65    #[inline]
66    pub fn get(&self, index: usize) -> Option<&T> {
67        // SAFETY: Manually constructed reference have valid lifetime
68        unsafe { Some(&*self.get_ptr(index)?) }
69    }
70
71    #[inline]
72    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
73        // SAFETY: Manually constructed reference have valid lifetime
74        unsafe { Some(&mut *(self.get_ptr(index)? as *mut T)) }
75    }
76
77    #[inline]
78    unsafe fn get_ptr(&self, index: usize) -> Option<*const T> {
79        let (offset, metadata) = *self.table.get(index)?;
80
81        Some(self.dyn_ptr_from(offset, metadata))
82    }
83
84    #[inline]
85    unsafe fn dyn_ptr_from(&self, offset: usize, metadata: DynMetadata<T>) -> *const T {
86        ptr::from_raw_parts(self.buf.as_ptr().add(offset) as _, metadata)
87    }
88
89    fn reserve_space_for(&mut self, value_layout: Layout) -> usize {
90        let padding = self.buf_occupied % value_layout.align();
91        let offset = self.buf_occupied + padding;
92
93        let new_buf_layout = Layout::from_size_align(
94            (self.buf_occupied + padding + value_layout.size()).next_power_of_two(),
95            self.buf_layout.align().max(value_layout.align()),
96        )
97        .unwrap();
98
99        if self.buf_layout != new_buf_layout {
100            let new_buf = unsafe {
101                if self.buf_layout.size() == 0 {
102                    alloc::alloc(new_buf_layout)
103                } else if self.buf_layout.align() != new_buf_layout.align() {
104                    alloc::dealloc(self.buf.as_ptr(), self.buf_layout);
105                    alloc::alloc(new_buf_layout)
106                } else {
107                    alloc::realloc(self.buf.as_ptr(), self.buf_layout, new_buf_layout.size())
108                }
109            };
110
111            self.buf = NonNull::new(new_buf).unwrap();
112            self.buf_layout = new_buf_layout;
113        }
114        self.buf_occupied += padding + value_layout.size();
115
116        return offset;
117    }
118
119    pub fn push<I: Unsize<T>>(&mut self, mut item: I) {
120        let (data, metadata) = (&mut item as *mut T).to_raw_parts();
121
122        let item_layout = Layout::new::<I>();
123        let offset = self.reserve_space_for(item_layout);
124
125        // SAFETY: item is moved to data and original is forgotten.
126        unsafe {
127            ptr::copy_nonoverlapping(
128                data as *mut u8,
129                self.buf.as_ptr().add(offset),
130                item_layout.size(),
131            )
132        };
133        mem::forget(item);
134
135        self.table.push((offset, metadata));
136        self.buf_occupied += item_layout.size();
137    }
138
139    pub fn pop(&mut self) -> Option<()> {
140        let (offset, metadata) = self.table.pop()?;
141        let data = unsafe { self.dyn_ptr_from(offset, metadata) };
142
143        // SAFETY: Data get removed after destructor
144        unsafe { ptr::drop_in_place(data as *mut T) };
145        self.buf_occupied = offset;
146
147        Some(())
148    }
149
150    pub fn truncate(&mut self, len: usize) {
151        if len >= self.table.len() {
152            return;
153        }
154
155        let data_start_offset = self.table[len].0;
156
157        for i in len..self.len() {
158            let (offset, metadata) = self.table[i];
159
160            // SAFETY: Data get removed after destructor
161            unsafe {
162                let data = self.dyn_ptr_from(offset, metadata);
163                ptr::drop_in_place(data as *mut T)
164            };
165        }
166
167        self.table.truncate(len);
168        self.buf_occupied = data_start_offset;
169    }
170
171    #[inline]
172    pub fn last(&self) -> Option<&T> {
173        self.get(self.len() - 1)
174    }
175
176    #[inline]
177    pub fn last_mut(&mut self) -> Option<&mut T> {
178        self.get_mut(self.len() - 1)
179    }
180
181    #[inline]
182    pub fn iter(&self) -> Iter<T> {
183        Iter {
184            ptr: self.buf.as_ptr(),
185            table_iter: self.table.iter(),
186        }
187    }
188
189    #[inline]
190    pub fn iter_mut(&mut self) -> IterMut<T> {
191        IterMut {
192            ptr: self.buf.as_ptr(),
193            table_iter: self.table.iter(),
194        }
195    }
196
197    pub fn clear(&mut self) {
198        for (offset, metadata) in &self.table {
199            // SAFETY: Data and table cleared after drop
200            unsafe {
201                ptr::drop_in_place(self.dyn_ptr_from(*offset, *metadata) as *mut T);
202            }
203        }
204
205        self.table.clear();
206        self.buf_occupied = 0;
207    }
208}
209
210impl<T: ?Sized + Pointee<Metadata = DynMetadata<T>>> Drop for TraitStack<T> {
211    fn drop(&mut self) {
212        for (offset, metadata) in &self.table {
213            // SAFETY: Data and table invalid after destructor
214            unsafe {
215                ptr::drop_in_place(self.dyn_ptr_from(*offset, *metadata) as *mut T);
216            }
217        }
218
219        if self.buf_layout.size() > 0 {
220            unsafe {
221                alloc::dealloc(self.buf.as_ptr(), self.buf_layout);
222            }
223        }
224    }
225}
226
227impl<T: ?Sized + Pointee<Metadata = DynMetadata<T>>> Default for TraitStack<T> {
228    fn default() -> Self {
229        Self::new()
230    }
231}
232
233impl<T: ?Sized + Pointee<Metadata = DynMetadata<T>>> Index<usize> for TraitStack<T> {
234    type Output = T;
235
236    fn index(&self, index: usize) -> &Self::Output {
237        self.get(index).unwrap()
238    }
239}
240
241impl<T: ?Sized + Pointee<Metadata = DynMetadata<T>>> IndexMut<usize> for TraitStack<T> {
242    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
243        self.get_mut(index).unwrap()
244    }
245}
246
247// SAFETY: All data stored in [TraitStack] is Send
248unsafe impl<T: ?Sized + Pointee<Metadata = DynMetadata<T>> + Send> Send for TraitStack<T> {}
249
250// SAFETY: All data stored in [TraitStack] is Sync
251unsafe impl<T: ?Sized + Pointee<Metadata = DynMetadata<T>> + Sync> Sync for TraitStack<T> {}
252
253impl<'a, T: ?Sized + Pointee<Metadata = DynMetadata<T>>> IntoIterator for &'a TraitStack<T> {
254    type Item = &'a T;
255
256    type IntoIter = Iter<'a, T>;
257
258    fn into_iter(self) -> Self::IntoIter {
259        self.iter()
260    }
261}
262
263impl<'a, T: ?Sized + Pointee<Metadata = DynMetadata<T>>> IntoIterator for &'a mut TraitStack<T> {
264    type Item = &'a mut T;
265
266    type IntoIter = IterMut<'a, T>;
267
268    fn into_iter(self) -> Self::IntoIter {
269        self.iter_mut()
270    }
271}
272
273impl<T: ?Sized + Pointee<Metadata = DynMetadata<T>> + Debug> Debug for TraitStack<T> {
274    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
275        f.debug_list().entries(self).finish()
276    }
277}
trait_stack/lib.rs

trait_stack/
lib.rs
