alloc/collections/vec_deque/
splice.rs

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

alloc/collections/vec_deque/
splice.rs
