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> Drain<'_, T, A>
84where
85    A: Allocator,
86{
87    /// The range from `self.vec.len` to `self.tail_start` contains elements
88    /// that have been moved out.
89    /// Fill that range as much as possible with new elements from the `replace_with` iterator.
90    /// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.)
91    unsafe fn fill<I: Iterator<Item = T>>(&mut self, replace_with: &mut I) -> bool {
92        let vec = unsafe { self.vec.as_mut() };
93        let range_start = vec.len;
94        let range_end = self.tail_start;
95        let range_slice = unsafe {
96            slice::from_raw_parts_mut(vec.as_mut_ptr().add(range_start), range_end - range_start)
97        };
98
99        for place in range_slice {
100            if let Some(new_item) = replace_with.next() {
101                unsafe { ptr::write(place, new_item) };
102                vec.len += 1;
103            } else {
104                return false;
105            }
106        }
107        true
108    }
109
110    /// Makes room for inserting more elements before the tail.
111    unsafe fn move_tail(&mut self, additional: usize) -> Result<(), Error> {
112        let vec = unsafe { self.vec.as_mut() };
113        let len = self.tail_start + self.tail_len;
114        vec.buf.try_reserve(len, additional)?;
115
116        let new_tail_start = self.tail_start + additional;
117        unsafe {
118            let src = vec.as_ptr().add(self.tail_start);
119            let dst = vec.as_mut_ptr().add(new_tail_start);
120            ptr::copy(src, dst, self.tail_len);
121        }
122        self.tail_start = new_tail_start;
123        Ok(())
124    }
125}
rune_alloc/vec/splice.rs

rune_alloc/vec/
splice.rs
