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(
147 deque.to_physical_idx(tail_start),
148 deque.to_physical_idx(new_tail_start),
149 self.tail_len,
150 );
151 }
152 self.drain_len += additional;
153 }
154}
155