stack_dst/
fifo.rs

1// See parent for docs
2use core::{iter, marker, mem, ops, ptr};
3
4mod impls;
5
6// Implementation Notes
7// -----
8//
9/// A First-In-First-Out queue of DSTs
10///
11/// ```
12/// let mut queue = ::stack_dst::Fifo::<str, ::stack_dst::buffers::Ptr8>::new();
13/// queue.push_back_str("Hello");
14/// queue.push_back_str("World");
15/// assert_eq!(queue.pop_front().as_ref().map(|v| &v[..]), Some("Hello"));
16/// ```
17pub struct Fifo<T: ?Sized, D: ::DataBuf> {
18    _pd: marker::PhantomData<*const T>,
19    read_pos: usize,
20    write_pos: usize,
21    data: D,
22}
23impl<T: ?Sized, D: ::DataBuf> Fifo<T, D> {
24    /// Construct a new (empty) list
25    pub fn new() -> Self
26    where
27        D: Default,
28    {
29        Self::with_buffer(D::default())
30    }
31    /// Construct a new (empty) list using the provided buffer
32    pub fn with_buffer(data: D) -> Self {
33        Fifo {
34            _pd: marker::PhantomData,
35            read_pos: 0,
36            write_pos: 0,
37            data,
38        }
39    }
40
41    fn meta_words() -> usize {
42        D::round_to_words(mem::size_of::<&T>() - mem::size_of::<usize>())
43    }
44    fn space_words(&self) -> usize {
45        self.data.as_ref().len() - self.write_pos
46    }
47
48    /// Push a value at the top of the stack
49    #[cfg(feature = "unsize")]
50    pub fn push_back<U: marker::Unsize<T>>(&mut self, v: U) -> Result<(), U>
51    where
52        (U, D::Inner): crate::AlignmentValid,
53    {
54        self.push_back_stable(v, |p| p)
55    }
56
57    /// Push a value to the end of the list (without using `Unsize`)
58    pub fn push_back_stable<U, F: FnOnce(&U) -> &T>(&mut self, v: U, f: F) -> Result<(), U>
59    where
60        (U, D::Inner): crate::AlignmentValid,
61    {
62        <(U, D::Inner) as crate::AlignmentValid>::check();
63
64        // SAFE: Destination address is valid
65        unsafe {
66            match self.push_inner(crate::check_fat_pointer(&v, f)) {
67                Ok(pii) => {
68                    ptr::write(pii.data.as_mut_ptr() as *mut U, v);
69                    Ok(())
70                }
71                Err(_) => Err(v),
72            }
73        }
74    }
75
76    /// Compact the list (moving the read position to zero)
77    pub fn compact(&mut self) {
78        if self.read_pos != 0 {
79            self.data.as_mut().rotate_left(self.read_pos);
80            self.write_pos -= self.read_pos;
81            self.read_pos = 0;
82        }
83    }
84
85    /// Checks if the queue is currently empty
86    pub fn empty(&self) -> bool {
87        self.read_pos == self.write_pos
88    }
89
90    /// Remove an item from the front of the list
91    pub fn pop_front(&mut self) -> Option<PopHandle<T, D>> {
92        if self.read_pos == self.write_pos {
93            None
94        } else {
95            Some(PopHandle { parent: self })
96        }
97    }
98    /// Peek the front of the queue
99    pub fn front_mut(&mut self) -> Option<&mut T> {
100        if self.read_pos == self.write_pos {
101            None
102        } else {
103            Some(unsafe { &mut *self.front_raw_mut() })
104        }
105    }
106    /// Peek the front of the queue
107    pub fn front(&self) -> Option<&T> {
108        if self.read_pos == self.write_pos {
109            None
110        } else {
111            Some(unsafe { &*self.front_raw() })
112        }
113    }
114
115    /// Obtain an immutable iterator (yields references to items, in insertion order)
116    /// ```
117    /// let mut list = ::stack_dst::Fifo::<str, ::stack_dst::buffers::Ptr8>::new();
118    /// list.push_back_str("Hello");
119    /// list.push_back_str("world");
120    /// let mut it = list.iter();
121    /// assert_eq!(it.next(), Some("Hello"));
122    /// assert_eq!(it.next(), Some("world"));
123    /// assert_eq!(it.next(), None);
124    /// ```
125    pub fn iter(&self) -> Iter<T, D> {
126        Iter(self, self.read_pos)
127    }
128    /// Obtain a mutable iterator
129    /// ```
130    /// let mut list = ::stack_dst::Fifo::<[u8], ::stack_dst::buffers::Ptr8>::new();
131    /// list.push_copied(&[1,2,3]);
132    /// list.push_copied(&[9]);
133    /// for v in list.iter_mut() {
134    ///     v[0] -= 1;
135    /// }
136    /// let mut it = list.iter();
137    /// assert_eq!(it.next(), Some(&[0,2,3][..]));
138    /// assert_eq!(it.next(), Some(&[8][..]));
139    /// assert_eq!(it.next(), None);
140    /// ```
141    pub fn iter_mut(&mut self) -> IterMut<T, D> {
142        IterMut(self, self.read_pos)
143    }
144    // Note: No into_iter, not possible due to unsized types
145    // Could make a `drain` that returns read handles (pops as it goes)
146
147    fn front_raw(&self) -> *mut T {
148        assert!(self.read_pos < self.write_pos);
149
150        // SAFE: Internal consistency maintains the metadata validity
151        unsafe { self.raw_at(self.read_pos) }
152    }
153    // UNSAFE: Caller must ensure that `pos` is the start of an object
154    unsafe fn raw_at(&self, pos: usize) -> *mut T {
155        assert!(pos >= self.read_pos);
156        assert!(pos < self.write_pos);
157        let meta = &self.data.as_ref()[pos..];
158        let mw = Self::meta_words();
159        let (meta, data) = meta.split_at(mw);
160        super::make_fat_ptr(data.as_ptr() as *mut (), meta)
161    }
162    fn front_raw_mut(&mut self) -> *mut T {
163        assert!(self.read_pos < self.write_pos);
164
165        // SAFE: Internal consistency maintains the metadata validity
166        unsafe { self.raw_at_mut(self.read_pos) }
167    }
168    // UNSAFE: Caller must ensure that `pos` is the start of an object
169    unsafe fn raw_at_mut(&mut self, pos: usize) -> *mut T {
170        assert!(pos >= self.read_pos);
171        assert!(pos < self.write_pos);
172        let meta = &mut self.data.as_mut()[pos..];
173        let mw = Self::meta_words();
174        let (meta, data) = meta.split_at_mut(mw);
175        super::make_fat_ptr(data.as_mut_ptr() as *mut (), meta)
176    }
177    fn pop_front_inner(&mut self) {
178        // SAFE: `front_raw_mut` asserts that there's an item, rest is correct
179        unsafe {
180            let ptr = &mut *self.front_raw_mut();
181            let len = mem::size_of_val(ptr);
182            ptr::drop_in_place(ptr);
183            let words = D::round_to_words(len);
184            self.read_pos += Self::meta_words() + words;
185        }
186    }
187
188
189    /// Remove any items that don't meet a predicate
190    ///
191    /// ```
192    /// # extern crate core;
193    /// use stack_dst::Fifo;
194    /// use core::any::Any;
195    /// use core::fmt::Debug;
196    /// trait DebugAny: 'static + Any + Debug { fn as_any(&self) -> &dyn Any; }
197    /// impl<T: Debug + Any + 'static> DebugAny for T { fn as_any(&self) -> &dyn Any { self } }
198    /// let mut list = {
199    ///     let mut list: Fifo<dyn DebugAny, ::stack_dst::buffers::Ptr8> = Fifo::new();
200    ///     list.push_back_stable(1234, |v| v);
201    ///     list.push_back_stable(234.5f32, |v| v);
202    ///     list.push_back_stable(5678, |v| v);
203    ///     list.push_back_stable(0.5f32, |v| v);
204    ///     list
205    ///     };
206    /// list.retain(|v| (*v).as_any().downcast_ref::<f32>().is_some());
207    /// let mut it = list.iter().map(|v| format!("{:?}", v));
208    /// assert_eq!(it.next(), Some("234.5".to_owned()));
209    /// assert_eq!(it.next(), Some("0.5".to_owned()));
210    /// assert_eq!(it.next(), None);
211    /// ```
212    pub fn retain<Cb>(&mut self, mut cb: Cb)
213    where
214        Cb: FnMut(&mut T)->bool
215    {
216        let orig_write_pos = self.write_pos;
217        self.write_pos = self.read_pos;
218        let mut ofs = self.read_pos;
219        let mut writeback_pos = ofs;
220        while ofs < orig_write_pos
221        {
222            let v: &mut T = unsafe {
223                let meta = &mut self.data.as_mut()[ofs..];
224                let mw = Self::meta_words();
225                let (meta, data) = meta.split_at_mut(mw);
226                &mut *super::make_fat_ptr(data.as_mut_ptr() as *mut (), meta)
227                };
228            let words = Self::meta_words() + D::round_to_words(mem::size_of_val(v));
229            if cb(v) {
230                if writeback_pos != ofs {
231                    let d = self.data.as_mut();
232                    // writeback is always before `ofs`, so this ordering is correct
233                    for i in 0..words {
234                        let (a,b) = d.split_at_mut(ofs+i);
235                        a[writeback_pos+i] = b[0];
236                    }
237                }
238                writeback_pos += words;
239            }
240            else {
241                // Don't update `writeback_pos`
242                // SAFE: Valid pointer, won't be accessed again
243                unsafe {
244                    ptr::drop_in_place(v);
245                }
246            }
247            ofs += words;
248        }
249        assert!(ofs == orig_write_pos);
250        self.write_pos = writeback_pos;
251    }
252}
253
254struct PushInnerInfo<'a, DInner> {
255    /// Buffer for value data
256    data: &'a mut crate::BufSlice<DInner>,
257    /// Buffer for metadata (length/vtable)
258    meta: &'a mut crate::BufSlice<DInner>,
259    /// Memory location for resetting the push
260    reset_slot: &'a mut usize,
261    reset_value: usize,
262}
263
264impl<T: ?Sized, D: ::DataBuf> Fifo<T, D>
265{
266    /// Push an item to the list (setting metadata based on `fat_ptr`)
267    /// UNSAFE: Caller must fill the buffer before any potential panic
268    unsafe fn push_inner(&mut self, fat_ptr: &T) -> Result<PushInnerInfo<D::Inner>, ()> {
269        let bytes = mem::size_of_val(fat_ptr);
270        let (_data_ptr, len, v) = crate::decompose_pointer(fat_ptr);
271        self.push_inner_raw(bytes, &v[..len])
272    }
273    unsafe fn push_inner_raw(&mut self, bytes: usize, metadata: &[usize]) -> Result<PushInnerInfo<D::Inner>, ()> {
274        let words = D::round_to_words(bytes) + Self::meta_words();
275
276        // 1. Check if there's space for the item
277        if self.space_words() < words {
278            // 2. If not, check if compaction would help
279            if self.space_words() + self.read_pos >= words {
280                self.compact();
281            }
282            // 3. Then, try expanding
283            if self.space_words() < words {
284                if let Err(_) = self.data.extend(self.write_pos + words) {
285                    // if expansion fails, return error
286                    return Err(());
287                }
288            }
289        }
290        assert!(self.space_words() >= words);
291
292        // Get the base pointer for the new item
293        let slot = &mut self.data.as_mut()[self.write_pos..][..words];
294        let prev_write_pos = self.write_pos;
295        self.write_pos += words;
296        let (meta, rv) = slot.split_at_mut(Self::meta_words());
297
298        // Populate the metadata
299        super::store_metadata(meta, metadata);
300
301        // Increment offset and return
302        Ok(PushInnerInfo {
303            meta: meta,
304            data: rv,
305            reset_slot: &mut self.write_pos,
306            reset_value: prev_write_pos,
307            })
308    }
309}
310
311impl<D: ::DataBuf> Fifo<str, D> {
312    /// Push the contents of a string slice as an item onto the stack
313    pub fn push_back_str(&mut self, v: &str) -> Result<(), ()> {
314        unsafe {
315            self.push_inner(v)
316                .map(|pii| ptr::copy(v.as_bytes().as_ptr(), pii.data.as_mut_ptr() as *mut u8, v.len()))
317        }
318    }
319}
320
321impl<D: ::DataBuf, T: Clone> Fifo<[T], D>
322where
323    (T, D::Inner): crate::AlignmentValid,
324{
325    /// Pushes a set of items (cloning out of the input slice)
326    ///
327    /// ```
328    /// # use ::stack_dst::Fifo;
329    /// let mut queue = Fifo::<[String], ::stack_dst::buffers::Ptr8>::new();
330    /// queue.push_cloned(&["1".to_owned()]);
331    /// ```
332    pub fn push_cloned(&mut self, v: &[T]) -> Result<(), ()> {
333        <(T, D::Inner) as crate::AlignmentValid>::check();
334        self.push_from_iter(v.iter().cloned())
335    }
336    /// Pushes a set of items (copying out of the input slice)
337    ///
338    /// ```
339    /// # use ::stack_dst::Fifo;
340    /// let mut queue = Fifo::<[usize], ::stack_dst::buffers::Ptr8>::new();
341    /// queue.push_copied(&[1]);
342    /// ```
343    pub fn push_copied(&mut self, v: &[T]) -> Result<(), ()>
344    where
345        T: Copy,
346    {
347        <(T, D::Inner) as crate::AlignmentValid>::check();
348        // SAFE: Carefully constructed to maintain consistency
349        unsafe {
350            self.push_inner(v).map(|pii| {
351                ptr::copy(
352                    v.as_ptr() as *const u8,
353                    pii.data.as_mut_ptr() as *mut u8,
354                    mem::size_of_val(v),
355                )
356            })
357        }
358    }
359}
360impl<D: crate::DataBuf, T> Fifo<[T], D>
361where
362    (T, D::Inner): crate::AlignmentValid,
363{
364    /// Push an item, populated from an exact-sized iterator
365    /// 
366    /// ```
367    /// # extern crate core;
368    /// # use stack_dst::Fifo;
369    /// # use core::fmt::Display;
370    /// 
371    /// let mut stack = Fifo::<[u8], ::stack_dst::buffers::Ptr8>::new();
372    /// stack.push_from_iter(0..10);
373    /// assert_eq!(stack.front().unwrap(), &[0,1,2,3,4,5,6,7,8,9]);
374    /// ```
375    pub fn push_from_iter(&mut self, mut iter: impl ExactSizeIterator<Item=T>)->Result<(),()> {
376        <(T, D::Inner) as crate::AlignmentValid>::check();
377        // SAFE: API used correctly
378        unsafe {
379            let pii = self.push_inner_raw(iter.len() * mem::size_of::<T>(), &[0])?;
380            crate::list_push_gen(pii.meta, pii.data, iter.len(), |_| iter.next().unwrap(), pii.reset_slot, pii.reset_value);
381            Ok( () )
382        }
383    }
384}
385
386impl<T: ?Sized, D: crate::DataBuf> ops::Drop for Fifo<T, D> {
387    fn drop(&mut self) {
388        while let Some(_) = self.pop_front() {}
389    }
390}
391impl<T: ?Sized, D: ::DataBuf + Default> Default for Fifo<T, D> {
392    fn default() -> Self {
393        Fifo::new()
394    }
395}
396
397/// Handle returned by `Fifo::pop` (does the actual pop on drop)
398pub struct PopHandle<'a, T: 'a + ?Sized, D: 'a + crate::DataBuf> {
399    parent: &'a mut Fifo<T, D>,
400}
401impl<'a, T: ?Sized, D: crate::DataBuf> ops::Deref for PopHandle<'a, T, D> {
402    type Target = T;
403    fn deref(&self) -> &T {
404        unsafe { &*self.parent.front_raw() }
405    }
406}
407impl<'a, T: ?Sized, D: crate::DataBuf> ops::DerefMut for PopHandle<'a, T, D> {
408    fn deref_mut(&mut self) -> &mut T {
409        unsafe { &mut *self.parent.front_raw_mut() }
410    }
411}
412impl<'a, T: ?Sized, D: crate::DataBuf> ops::Drop for PopHandle<'a, T, D> {
413    fn drop(&mut self) {
414        self.parent.pop_front_inner();
415    }
416}
417
418/// DST FIFO iterator (immutable)
419pub struct Iter<'a, T: 'a + ?Sized, D: 'a + crate::DataBuf>(&'a Fifo<T, D>, usize);
420impl<'a, T: 'a + ?Sized, D: 'a + crate::DataBuf> iter::Iterator for Iter<'a, T, D> {
421    type Item = &'a T;
422    fn next(&mut self) -> Option<&'a T> {
423        if self.1 == self.0.write_pos {
424            None
425        } else {
426            // SAFE: Bounds checked, aliasing enforced by API
427            let rv = unsafe { &*self.0.raw_at(self.1) };
428            self.1 += Fifo::<T, D>::meta_words() + D::round_to_words(mem::size_of_val(rv));
429            Some(rv)
430        }
431    }
432}
433/// DST FIFO iterator (mutable)
434pub struct IterMut<'a, T: 'a + ?Sized, D: 'a + crate::DataBuf>(&'a mut Fifo<T, D>, usize);
435impl<'a, T: 'a + ?Sized, D: 'a + crate::DataBuf> iter::Iterator for IterMut<'a, T, D> {
436    type Item = &'a mut T;
437    fn next(&mut self) -> Option<&'a mut T> {
438        if self.1 == self.0.write_pos {
439            None
440        } else {
441            // SAFE: Bounds checked, aliasing enforced by API
442            let rv = unsafe { &mut *self.0.raw_at_mut(self.1) };
443            self.1 += Fifo::<T, D>::meta_words() + D::round_to_words(mem::size_of_val(rv));
444            Some(rv)
445        }
446    }
447}
stack_dst/fifo.rs

stack_dst/
fifo.rs
