allocator_api2/stable/vec/
splice.rs

1use core::ptr::{self};
2use core::slice::{self};
3
4use crate::stable::alloc::{Allocator, Global};
5
6use super::{Drain, Vec};
7
8/// A splicing iterator for `Vec`.
9///
10/// This struct is created by [`Vec::splice()`].
11/// See its documentation for more.
12///
13/// # Example
14///
15/// ```
16/// let mut v = vec![0, 1, 2];
17/// let new = [7, 8];
18/// let iter: std::vec::Splice<_> = v.splice(1.., new);
19/// ```
20#[derive(Debug)]
21pub struct Splice<'a, I: Iterator + 'a, A: Allocator + 'a = Global> {
22    pub(super) drain: Drain<'a, I::Item, A>,
23    pub(super) replace_with: I,
24}
25
26impl<I: Iterator, A: Allocator> Iterator for Splice<'_, I, A> {
27    type Item = I::Item;
28
29    #[inline(always)]
30    fn next(&mut self) -> Option<Self::Item> {
31        self.drain.next()
32    }
33
34    #[inline(always)]
35    fn size_hint(&self) -> (usize, Option<usize>) {
36        self.drain.size_hint()
37    }
38}
39
40impl<I: Iterator, A: Allocator> DoubleEndedIterator for Splice<'_, I, A> {
41    #[inline(always)]
42    fn next_back(&mut self) -> Option<Self::Item> {
43        self.drain.next_back()
44    }
45}
46
47impl<I: Iterator, A: Allocator> ExactSizeIterator for Splice<'_, I, A> {}
48
49impl<I: Iterator, A: Allocator> Drop for Splice<'_, I, A> {
50    #[inline]
51    fn drop(&mut self) {
52        self.drain.by_ref().for_each(drop);
53
54        unsafe {
55            if self.drain.tail_len == 0 {
56                self.drain.vec.as_mut().extend(self.replace_with.by_ref());
57                return;
58            }
59
60            // First fill the range left by drain().
61            if !self.drain.fill(&mut self.replace_with) {
62                return;
63            }
64
65            // There may be more elements. Use the lower bound as an estimate.
66            // FIXME: Is the upper bound a better guess? Or something else?
67            let (lower_bound, _upper_bound) = self.replace_with.size_hint();
68            if lower_bound > 0 {
69                self.drain.move_tail(lower_bound);
70                if !self.drain.fill(&mut self.replace_with) {
71                    return;
72                }
73            }
74
75            // Collect any remaining elements.
76            // This is a zero-length vector which does not allocate if `lower_bound` was exact.
77            let mut collected = self
78                .replace_with
79                .by_ref()
80                .collect::<Vec<I::Item>>()
81                .into_iter();
82            // Now we have an exact count.
83            if collected.len() > 0 {
84                self.drain.move_tail(collected.len());
85                let filled = self.drain.fill(&mut collected);
86                debug_assert!(filled);
87                debug_assert_eq!(collected.len(), 0);
88            }
89        }
90        // Let `Drain::drop` move the tail back if necessary and restore `vec.len`.
91    }
92}
93
94/// Private helper methods for `Splice::drop`
95impl<T, A: Allocator> Drain<'_, T, A> {
96    /// The range from `self.vec.len` to `self.tail_start` contains elements
97    /// that have been moved out.
98    /// Fill that range as much as possible with new elements from the `replace_with` iterator.
99    /// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.)
100    #[inline(always)]
101    unsafe fn fill<I: Iterator<Item = T>>(&mut self, replace_with: &mut I) -> bool {
102        let vec = unsafe { self.vec.as_mut() };
103        let range_start = vec.len;
104        let range_end = self.tail_start;
105        let range_slice = unsafe {
106            slice::from_raw_parts_mut(vec.as_mut_ptr().add(range_start), range_end - range_start)
107        };
108
109        for place in range_slice {
110            if let Some(new_item) = replace_with.next() {
111                unsafe { ptr::write(place, new_item) };
112                vec.len += 1;
113            } else {
114                return false;
115            }
116        }
117        true
118    }
119
120    /// Makes room for inserting more elements before the tail.
121    #[inline(always)]
122    unsafe fn move_tail(&mut self, additional: usize) {
123        let vec = unsafe { self.vec.as_mut() };
124        let len = self.tail_start + self.tail_len;
125        vec.buf.reserve(len, additional);
126
127        let new_tail_start = self.tail_start + additional;
128        unsafe {
129            let src = vec.as_ptr().add(self.tail_start);
130            let dst = vec.as_mut_ptr().add(new_tail_start);
131            ptr::copy(src, dst, self.tail_len);
132        }
133        self.tail_start = new_tail_start;
134    }
135}
allocator_api2/stable/vec/splice.rs

allocator_api2/stable/vec/
splice.rs
