devela/data/dst/
stack.rs

Help
1// devela::data::dst::stack
2//
3//! Implementation of the LIFO stack structure.
4//
5// TOC
6// - public API
7// - private API
8// - core_impls
9
10use super::{check_fat_pointer, decompose_pointer, list_push_gen, DstArray, DstBuf};
11use crate::{ConstDefault, MaybeUninit, MemAligned, PhantomData, Ptr};
12
13/* public API */
14
15#[doc = crate::TAG_DATA_STRUCTURE!()]
16/// A statically allocated LIFO stack of
17/// <abbr title="Dynamically sized type">DST</abbr>s with pointer alignment.
18///
19/// # Examples
20/// ```
21/// # use devela::data::DstStackUsize;
22/// let mut stack = DstStackUsize::<[u8], 16>::new();
23/// stack.push_copied(&[1]);
24/// ```
25// WAIT: [lazy_type_alias](https://github.com/rust-lang/rust/issues/112792) ↓DENIED
26pub type DstStackUsize<DST /*: ?Sized*/, const CAP: usize> = DstStack<DST, DstArray<usize, CAP>>;
27
28// Implementation Notes
29// -----
30//
31// The data array is filled from the back, with the metadata stored before
32// (at a lower memory address) the actual data. This so the code can use a
33// single integer to track the position (using size_of_val when popping items,
34// and the known size when pushing).
35
36#[doc = crate::TAG_DATA_STRUCTURE!()]
37/// A statically allocated LIFO stack of <abbr title="Dynamically sized
38/// type">DST</abbr>s.
39///
40/// Note: Each item in the stack takes at least one slot in the buffer
41/// (to store the metadata)
42pub struct DstStack<DST: ?Sized, BUF: DstBuf> {
43    _pd: PhantomData<*const DST>,
44    // Offset from the _back_ of `data` to the next free position.
45    // I.e. data[data.len() - cur_ofs] is the first metadata word
46    next_ofs: usize,
47    data: BUF,
48}
49
50#[doc = crate::TAG_ITERATOR!()]
51/// An iterator over the elements of a [`DstStack`].
52pub struct DstStackIter<'a, DST: 'a + ?Sized, BUF: 'a + DstBuf>(&'a DstStack<DST, BUF>, usize);
53
54#[doc = crate::TAG_ITERATOR!()]
55/// A mutable iterator over the elements of a [`DstStack`].
56pub struct DstStackIterMut<'a, DST: 'a + ?Sized, BUF: 'a + DstBuf>(
57    &'a mut DstStack<DST, BUF>,
58    usize,
59);
60
61impl<DST: ?Sized, BUF: DstBuf> DstStack<DST, BUF> {
62    /// Constructs a new (empty) stack.
63    #[must_use] #[rustfmt::skip]
64    pub fn new() -> Self where BUF: Default { Self::with_buffer(BUF::default()) }
65
66    /// Constructs a new (empty) stack, in compile-time.
67    #[must_use] #[rustfmt::skip]
68    pub const fn new_const() -> Self where BUF: ConstDefault { Self::with_buffer(BUF::DEFAULT) }
69
70    /// Constructs a new (empty) stack using the given `buffer`.
71    #[must_use] #[rustfmt::skip]
72    pub const fn with_buffer(buffer: BUF) -> Self {
73        DstStack { _pd: PhantomData, next_ofs: 0, data: buffer }
74    }
75
76    /// Returns `true` if the stack is empty.
77    #[must_use]
78    pub const fn is_empty(&self) -> bool {
79        self.next_ofs == 0
80    }
81
82    /// Pushes a value at the top of the stack.
83    ///
84    /// ```
85    /// # use devela::data::{DstArray, DstStack};
86    /// let mut stack = DstStack::<[u8], DstArray<u64, 8>>::new();
87    /// stack.push([1, 2,3], |v| v);
88    /// ```
89    pub fn push<VAL, F: FnOnce(&VAL) -> &DST>(&mut self, v: VAL, f: F) -> Result<(), VAL>
90    where
91        (VAL, BUF::Inner): MemAligned,
92    {
93        <(VAL, BUF::Inner) as MemAligned>::assert_compatibility();
94
95        // SAFETY: Destination address is valid.
96        unsafe {
97            match self.push_inner(check_fat_pointer(&v, f)) {
98                Ok(pii) => {
99                    Ptr::write(pii.data.as_mut_ptr() as *mut VAL, v);
100                    Ok(())
101                }
102                Err(()) => Err(v),
103            }
104        }
105    }
106
107    /// Returns a shared reference to the top item on the stack.
108    #[must_use]
109    pub fn top(&self) -> Option<&DST> {
110        self.top_raw().map(|x| unsafe { &*x })
111    }
112
113    /// Returns an exclusive reference to the top item on the stack.
114    #[must_use]
115    pub fn top_mut(&mut self) -> Option<&mut DST> {
116        self.top_raw_mut().map(|x| unsafe { &mut *x })
117    }
118
119    /// Pops the top item off the stack.
120    pub fn pop(&mut self) {
121        if let Some(ptr) = self.top_raw_mut() {
122            assert!(self.next_ofs > 0);
123            // SAFETY: Pointer is valid, and will never be accessed after this point.
124            let words = unsafe {
125                let size = size_of_val(&*ptr);
126                Ptr::drop_in_place(ptr);
127                BUF::round_to_words(size)
128            };
129            self.next_ofs -= words + Self::meta_words();
130        }
131    }
132
133    /// Returns an immutable iterator
134    /// (yields references to items, in the order they would be popped).
135    ///
136    /// # Examples
137    /// ```
138    /// # use devela::data::{DstArray, DstStack};
139    /// let mut list = DstStack::<str, DstArray<usize, 8>>::new();
140    /// list.push_str("Hello");
141    /// list.push_str("world");
142    /// let mut it = list.iter();
143    /// assert_eq!(it.next(), Some("world"));
144    /// assert_eq!(it.next(), Some("Hello"));
145    /// assert_eq!(it.next(), None);
146    /// ```
147    #[must_use]
148    pub const fn iter(&self) -> DstStackIter<DST, BUF> {
149        DstStackIter(self, self.next_ofs)
150    }
151
152    /// Returns a mutable iterator.
153    ///
154    /// # Examples
155    /// ```
156    /// # use devela::data::{DstArray, DstStack};
157    /// let mut list = DstStack::<[u8], DstArray<usize, 8>>::new();
158    /// list.push_copied(&[1,2,3]);
159    /// list.push_copied(&[9]);
160    /// for v in list.iter_mut() {
161    ///     v[0] -= 1;
162    /// }
163    /// let mut it = list.iter();
164    /// assert_eq!(it.next(), Some(&[8][..]));
165    /// assert_eq!(it.next(), Some(&[0,2,3][..]));
166    /// assert_eq!(it.next(), None);
167    /// ```
168    #[must_use]
169    pub fn iter_mut(&mut self) -> DstStackIterMut<DST, BUF> {
170        DstStackIterMut(self, self.next_ofs)
171    }
172}
173
174impl<BUF: DstBuf> DstStack<str, BUF> {
175    /// Pushes the contents of a `string` slice as an item onto the stack.
176    ///
177    /// # Examples
178    /// ```
179    /// # use devela::data::{DstArray, DstStack};
180    /// let mut stack = DstStack::<str, DstArray<u8, 32>>::new();
181    /// stack.push_str("Hello!");
182    /// ```
183    pub fn push_str(&mut self, string: &str) -> Result<(), ()> {
184        unsafe {
185            self.push_inner(string).map(|pii| {
186                Ptr::copy(
187                    string.as_bytes().as_ptr(),
188                    pii.data.as_mut_ptr() as *mut u8,
189                    string.len(),
190                );
191            })
192        }
193    }
194}
195
196impl<BUF: DstBuf, DST: Clone> DstStack<[DST], BUF>
197where
198    (DST, BUF::Inner): MemAligned,
199{
200    /// Pushes a set of items (cloning out of the input `slice`).
201    ///
202    /// # Examples
203    /// ```
204    /// # use devela::data::{DstArray, DstStack};
205    /// let mut stack = DstStack::<[u8], DstArray<u64, 8>>::new();
206    /// stack.push_cloned(&[1, 2, 3]);
207    /// ```
208    pub fn push_cloned(&mut self, slice: &[DST]) -> Result<(), ()> {
209        <(DST, BUF::Inner) as MemAligned>::assert_compatibility();
210        self.push_from_iter(slice.iter().cloned())
211    }
212    /// Pushes a set of items (copying out of the input `slice`).
213    ///
214    /// # Examples
215    /// ```
216    /// # use devela::data::{DstArray, DstStack};
217    /// let mut stack = DstStack::<[u8], DstArray<u64, 8>>::new();
218    /// stack.push_copied(&[1, 2, 3]);
219    /// ```
220    pub fn push_copied(&mut self, slice: &[DST]) -> Result<(), ()>
221    where
222        DST: Copy,
223    {
224        <(DST, BUF::Inner) as MemAligned>::assert_compatibility();
225        // SAFETY: Carefully constructed to maintain consistency.
226        unsafe {
227            self.push_inner(slice).map(|pii| {
228                Ptr::copy(
229                    slice.as_ptr() as *const u8,
230                    pii.data.as_mut_ptr() as *mut u8,
231                    size_of_val(slice),
232                );
233            })
234        }
235    }
236}
237
238impl<BUF: DstBuf, DST> DstStack<[DST], BUF>
239where
240    (DST, BUF::Inner): MemAligned,
241{
242    /// Pushes an item, populated from an exact-sized iterator.
243    ///
244    /// # Examples
245    /// ```
246    /// # use devela::data::{DstArray, DstStack};
247    /// let mut stack = DstStack::<[u8], DstArray<usize, 8>>::new();
248    /// stack.push_from_iter(0..10);
249    /// assert_eq!(stack.top().unwrap(), &[0,1,2,3,4,5,6,7,8,9]);
250    /// ```
251    pub fn push_from_iter(
252        &mut self,
253        mut iter: impl ExactSizeIterator<Item = DST>,
254    ) -> Result<(), ()> {
255        <(DST, BUF::Inner) as MemAligned>::assert_compatibility();
256        // SAFETY: API used correctly.
257        unsafe {
258            let pii = self.push_inner_raw(iter.len() * size_of::<DST>(), &[0])?;
259            list_push_gen(
260                pii.meta,
261                pii.data,
262                iter.len(),
263                |_| iter.next().unwrap(),
264                pii.reset_slot,
265                pii.reset_value,
266            );
267            Ok(())
268        }
269    }
270}
271
272/* private API */
273
274struct PushInnerInfo<'a, DInner> {
275    // Buffer for value data
276    data: &'a mut [MaybeUninit<DInner>],
277
278    // Buffer for metadata (length/vtable)
279    meta: &'a mut [MaybeUninit<DInner>],
280
281    // Memory location for resetting the push
282    reset_slot: &'a mut usize,
283    reset_value: usize,
284}
285
286impl<DST: ?Sized, BUF: DstBuf> DstStack<DST, BUF> {
287    #[must_use]
288    fn meta_words() -> usize {
289        BUF::round_to_words(size_of::<&DST>() - size_of::<usize>())
290    }
291
292    #[must_use]
293    unsafe fn raw_at(&self, ofs: usize) -> *mut DST {
294        let dar = self.data.as_ref();
295        let meta = &dar[dar.len() - ofs..];
296        let mw = Self::meta_words();
297        let (meta, data) = meta.split_at(mw);
298        // SAFETY: caller must ensure safety
299        unsafe { super::make_fat_ptr(data.as_ptr() as *mut (), meta) }
300    }
301    #[must_use]
302    unsafe fn raw_at_mut(&mut self, ofs: usize) -> *mut DST {
303        let dar = self.data.as_mut();
304        let ofs = dar.len() - ofs;
305        let meta = &mut dar[ofs..];
306        let mw = Self::meta_words();
307        let (meta, data) = meta.split_at_mut(mw);
308        // SAFETY: caller must ensure safety
309        unsafe { super::make_fat_ptr(data.as_mut_ptr() as *mut (), meta) }
310    }
311    // Get a raw pointer to the top of the stack.
312    #[must_use]
313    fn top_raw(&self) -> Option<*mut DST> {
314        if self.next_ofs == 0 {
315            None
316        } else {
317            // SAFETY: Internal consistency maintains the metadata validity.
318            Some(unsafe { self.raw_at(self.next_ofs) })
319        }
320    }
321    // Get a raw pointer to the top of the stack
322    #[must_use]
323    fn top_raw_mut(&mut self) -> Option<*mut DST> {
324        if self.next_ofs == 0 {
325            None
326        } else {
327            // SAFETY: Internal consistency maintains the metadata validity.
328            Some(unsafe { self.raw_at_mut(self.next_ofs) })
329        }
330    }
331
332    // See `push_inner_raw`.
333    unsafe fn push_inner(&mut self, fat_ptr: &DST) -> Result<PushInnerInfo<BUF::Inner>, ()> {
334        let bytes = size_of_val(fat_ptr);
335        let (_data_ptr, len, v) = decompose_pointer(fat_ptr);
336        // SAFETY: caller must ensure safety
337        unsafe { self.push_inner_raw(bytes, &v[..len]) }
338    }
339
340    // Returns:
341    // - metadata slot
342    // - data slot
343    // - Total words used
344    unsafe fn push_inner_raw(
345        &mut self,
346        bytes: usize,
347        metadata: &[usize],
348    ) -> Result<PushInnerInfo<BUF::Inner>, ()> {
349        assert!(BUF::round_to_words(size_of_val(metadata)) == Self::meta_words());
350        let words = BUF::round_to_words(bytes) + Self::meta_words();
351
352        let req_space = self.next_ofs + words;
353        // Attempt to resize (if the underlying buffer allows it).
354        if req_space > self.data.as_ref().len() {
355            let old_len = self.data.as_ref().len();
356            if self.data.extend(req_space).is_ok() {
357                let new_len = self.data.as_ref().len();
358                self.data.as_mut().rotate_right(new_len - old_len);
359            }
360        }
361
362        // Check if there is sufficient space for the new item.
363        if req_space <= self.data.as_ref().len() {
364            // Get the base pointer for the new item
365            let prev_next_ofs = self.next_ofs;
366            self.next_ofs += words;
367            let len = self.data.as_ref().len();
368            let slot = &mut self.data.as_mut()[len - self.next_ofs..][..words];
369            let (meta, rv) = slot.split_at_mut(Self::meta_words());
370
371            // Populate the metadata.
372            super::store_metadata(meta, metadata);
373
374            // Increment offset and return.
375            Ok(PushInnerInfo {
376                meta,
377                data: rv,
378                reset_slot: &mut self.next_ofs,
379                reset_value: prev_next_ofs,
380            })
381        } else {
382            Err(())
383        }
384    }
385}
386
387mod core_impls {
388    use super::{DstBuf, DstStack, DstStackIter, DstStackIterMut};
389    use core::{fmt, iter, ops};
390
391    impl<DST: ?Sized, BUF: DstBuf> ops::Drop for DstStack<DST, BUF> {
392        fn drop(&mut self) {
393            while !self.is_empty() {
394                self.pop();
395            }
396        }
397    }
398    impl<DST: ?Sized, BUF: DstBuf + Default> Default for DstStack<DST, BUF> {
399        #[must_use]
400        fn default() -> Self {
401            DstStack::new()
402        }
403    }
404
405    macro_rules! impl_trait {
406        ( $t:path; $($body:tt)* ) => {
407            impl<BUF: DstBuf, DST: ?Sized> $t for DstStack<DST, BUF> where DST: $t { $( $body )* }
408        }
409    }
410    impl_trait! { fmt::Debug;
411        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
412            f.write_str("[")?;
413            for v in self.iter() {
414                v.fmt(f)?;
415                f.write_str(",")?;
416            }
417            f.write_str("]")?;
418            Ok( () )
419        }
420    }
421
422    /* iter */
423
424    impl<'a, DST: 'a + ?Sized, BUF: 'a + DstBuf> iter::Iterator for DstStackIter<'a, DST, BUF> {
425        type Item = &'a DST;
426        #[must_use]
427        fn next(&mut self) -> Option<&'a DST> {
428            if self.1 == 0 {
429                None
430            } else {
431                // SAFETY: Bounds checked, aliasing enforced by API.
432                let rv = unsafe { &*self.0.raw_at(self.1) };
433                self.1 -= DstStack::<DST, BUF>::meta_words() + BUF::round_to_words(size_of_val(rv));
434                Some(rv)
435            }
436        }
437    }
438
439    impl<'a, DST: 'a + ?Sized, BUF: 'a + DstBuf> iter::Iterator for DstStackIterMut<'a, DST, BUF> {
440        type Item = &'a mut DST;
441        #[must_use]
442        fn next(&mut self) -> Option<&'a mut DST> {
443            if self.1 == 0 {
444                None
445            } else {
446                // SAFETY: Bounds checked, aliasing enforced by API.
447                let rv = unsafe { &mut *self.0.raw_at_mut(self.1) };
448                self.1 -= DstStack::<DST, BUF>::meta_words() + BUF::round_to_words(size_of_val(rv));
449                Some(rv)
450            }
451        }
452    }
453}
devela/data/dst/stack.rs

devela/data/dst/
stack.rs
