1 | use crate::alloc::Allocator; |
2 | use crate::vec; |
3 | use core::iter::TrustedLen; |
4 | use core::slice; |
5 | |
6 | use super::VecDeque; |
7 | |
8 | // Specialization trait used for VecDeque::extend |
9 | pub(super) trait SpecExtend<T, I> { |
10 | fn spec_extend(&mut self, iter: I); |
11 | } |
12 | |
13 | impl<T, I, A: Allocator> SpecExtend<T, I> for VecDeque<T, A> |
14 | where |
15 | I: Iterator<Item = T>, |
16 | { |
17 | default fn spec_extend(&mut self, mut iter: I) { |
18 | // This function should be the moral equivalent of: |
19 | // |
20 | // for item in iter { |
21 | // self.push_back(item); |
22 | // } |
23 | |
24 | // May only be called if `deque.len() < deque.capacity()` |
25 | unsafe fn push_unchecked<T, A: Allocator>(deque: &mut VecDeque<T, A>, element: T) { |
26 | // SAFETY: Because of the precondition, it's guaranteed that there is space |
27 | // in the logical array after the last element. |
28 | unsafe { deque.buffer_write(deque.to_physical_idx(deque.len), element) }; |
29 | // This can't overflow because `deque.len() < deque.capacity() <= usize::MAX`. |
30 | deque.len += 1; |
31 | } |
32 | |
33 | while let Some(element) = iter.next() { |
34 | let (lower, _) = iter.size_hint(); |
35 | self.reserve(lower.saturating_add(1)); |
36 | |
37 | // SAFETY: We just reserved space for at least one element. |
38 | unsafe { push_unchecked(self, element) }; |
39 | |
40 | // Inner loop to avoid repeatedly calling `reserve`. |
41 | while self.len < self.capacity() { |
42 | let Some(element) = iter.next() else { |
43 | return; |
44 | }; |
45 | // SAFETY: The loop condition guarantees that `self.len() < self.capacity()`. |
46 | unsafe { push_unchecked(self, element) }; |
47 | } |
48 | } |
49 | } |
50 | } |
51 | |
52 | impl<T, I, A: Allocator> SpecExtend<T, I> for VecDeque<T, A> |
53 | where |
54 | I: TrustedLen<Item = T>, |
55 | { |
56 | default fn spec_extend(&mut self, iter: I) { |
57 | // This is the case for a TrustedLen iterator. |
58 | let (low, high) = iter.size_hint(); |
59 | if let Some(additional) = high { |
60 | debug_assert_eq!( |
61 | low, |
62 | additional, |
63 | "TrustedLen iterator's size hint is not exact: {:?}" , |
64 | (low, high) |
65 | ); |
66 | self.reserve(additional); |
67 | |
68 | let written = unsafe { |
69 | self.write_iter_wrapping(self.to_physical_idx(self.len), iter, additional) |
70 | }; |
71 | |
72 | debug_assert_eq!( |
73 | additional, written, |
74 | "The number of items written to VecDeque doesn't match the TrustedLen size hint" |
75 | ); |
76 | } else { |
77 | // Per TrustedLen contract a `None` upper bound means that the iterator length |
78 | // truly exceeds usize::MAX, which would eventually lead to a capacity overflow anyway. |
79 | // Since the other branch already panics eagerly (via `reserve()`) we do the same here. |
80 | // This avoids additional codegen for a fallback code path which would eventually |
81 | // panic anyway. |
82 | panic!("capacity overflow" ); |
83 | } |
84 | } |
85 | } |
86 | |
87 | impl<T, A: Allocator> SpecExtend<T, vec::IntoIter<T>> for VecDeque<T, A> { |
88 | fn spec_extend(&mut self, mut iterator: vec::IntoIter<T>) { |
89 | let slice: &[T] = iterator.as_slice(); |
90 | self.reserve(additional:slice.len()); |
91 | |
92 | unsafe { |
93 | self.copy_slice(self.to_physical_idx(self.len), src:slice); |
94 | self.len += slice.len(); |
95 | } |
96 | iterator.forget_remaining_elements(); |
97 | } |
98 | } |
99 | |
100 | impl<'a, T: 'a, I, A: Allocator> SpecExtend<&'a T, I> for VecDeque<T, A> |
101 | where |
102 | I: Iterator<Item = &'a T>, |
103 | T: Copy, |
104 | { |
105 | default fn spec_extend(&mut self, iterator: I) { |
106 | self.spec_extend(iter:iterator.copied()) |
107 | } |
108 | } |
109 | |
110 | impl<'a, T: 'a, A: Allocator> SpecExtend<&'a T, slice::Iter<'a, T>> for VecDeque<T, A> |
111 | where |
112 | T: Copy, |
113 | { |
114 | fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) { |
115 | let slice: &[T] = iterator.as_slice(); |
116 | self.reserve(additional:slice.len()); |
117 | |
118 | unsafe { |
119 | self.copy_slice(self.to_physical_idx(self.len), src:slice); |
120 | self.len += slice.len(); |
121 | } |
122 | } |
123 | } |
124 | |