rune_alloc/vec/
splice.rs

1use core::ptr::{self};
2use core::slice::{self};
3
4use crate::alloc::Allocator;
5use crate::error::Error;
6
7use super::{Drain, Vec};
8
9// NB: This is a larger rewrite than typical, but that's because the `Splice`
10// does a lot of work when it's dropped instead of performing the work in-place
11// like this.
12pub(crate) fn splice<'a, I, A>(
13    drain: &mut Drain<'a, I::Item, A>,
14    replace_with: &mut I,
15) -> Result<(), Error>
16where
17    I: Iterator + 'a,
18    A: Allocator + 'a,
19{
20    for element in drain.by_ref() {
21        drop(element);
22    }
23
24    // At this point draining is done and the only remaining tasks are splicing
25    // and moving things into the final place.
26    // Which means we can replace the slice::Iter with pointers that won't point to deallocated
27    // memory, so that Drain::drop is still allowed to call iter.len(), otherwise it would break
28    // the ptr.sub_ptr contract.
29    drain.iter = [].iter();
30
31    unsafe {
32        if drain.tail_len == 0 {
33            let out = drain.vec.as_mut();
34
35            for element in replace_with.by_ref() {
36                out.try_push(element)?;
37            }
38
39            return Ok(());
40        }
41
42        // First fill the range left by drain().
43        if !drain.fill(replace_with) {
44            return Ok(());
45        }
46
47        // There may be more elements. Use the lower bound as an estimate.
48        // FIXME: Is the upper bound a better guess? Or something else?
49        let (lower_bound, _upper_bound) = replace_with.size_hint();
50
51        if lower_bound > 0 {
52            drain.move_tail(lower_bound)?;
53
54            if !drain.fill(replace_with) {
55                return Ok(());
56            }
57        }
58
59        // Collect any remaining elements.
60        // This is a zero-length vector which does not allocate if `lower_bound` was exact.
61        let mut collected = Vec::new_in(drain.vec.as_ref().allocator());
62
63        for element in replace_with.by_ref() {
64            collected.try_push(element)?;
65        }
66
67        let mut collected = collected.into_iter();
68
69        // Now we have an exact count.
70        if collected.len() > 0 {
71            drain.move_tail(collected.len())?;
72            let filled = drain.fill(&mut collected);
73            debug_assert!(filled);
74            debug_assert_eq!(collected.len(), 0);
75        }
76
77        Ok(())
78    }
79    // Let `Drain::drop` move the tail back if necessary and restore `vec.len`.
80}
81
82/// Private helper methods for `Splice::drop`
83impl<T, A: Allocator> Drain<'_, T, A> {
84    /// The range from `self.vec.len` to `self.tail_start` contains elements
85    /// that have been moved out.
86    /// Fill that range as much as possible with new elements from the `replace_with` iterator.
87    /// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.)
88    unsafe fn fill<I: Iterator<Item = T>>(&mut self, replace_with: &mut I) -> bool {
89        let vec = unsafe { self.vec.as_mut() };
90        let range_start = vec.len;
91        let range_end = self.tail_start;
92        let range_slice = unsafe {
93            slice::from_raw_parts_mut(vec.as_mut_ptr().add(range_start), range_end - range_start)
94        };
95
96        for place in range_slice {
97            if let Some(new_item) = replace_with.next() {
98                unsafe { ptr::write(place, new_item) };
99                vec.len += 1;
100            } else {
101                return false;
102            }
103        }
104        true
105    }
106
107    /// Makes room for inserting more elements before the tail.
108    unsafe fn move_tail(&mut self, additional: usize) -> Result<(), Error> {
109        let vec = unsafe { self.vec.as_mut() };
110        let len = self.tail_start + self.tail_len;
111        vec.buf.try_reserve(len, additional)?;
112
113        let new_tail_start = self.tail_start + additional;
114        unsafe {
115            let src = vec.as_ptr().add(self.tail_start);
116            let dst = vec.as_mut_ptr().add(new_tail_start);
117            ptr::copy(src, dst, self.tail_len);
118        }
119        self.tail_start = new_tail_start;
120        Ok(())
121    }
122}
rune_alloc/vec/splice.rs

rune_alloc/vec/
splice.rs
