two_sided_vec/
extend.rs

1use std::{mem, iter, slice, vec};
2use super::TwoSidedVec;
3
4
5/// The two-sided counterpart to `Extend`,
6/// which supports extending both the front and back of the
7pub trait TwoSidedExtend<T> {
8    fn extend_back<I: IntoIterator<Item=T>>(&mut self, iter: I);
9    fn extend_front<I: IntoIterator<Item=T>>(&mut self, iter: I);
10}
11
12impl<T> TwoSidedExtend<T> for TwoSidedVec<T> {
13    #[inline]
14    fn extend_back<I: IntoIterator<Item=T>>(&mut self, iter: I) {
15        SpecExtend::<T, I::IntoIter>::extend_back(self, iter.into_iter())
16    }
17    #[inline]
18    fn extend_front<I: IntoIterator<Item=T>>(&mut self, iter: I) {
19        SpecExtend::<T, I::IntoIter>::extend_front(self, iter.into_iter())
20    }
21}
22
23impl<'a, T: Copy + 'a> TwoSidedExtend<&'a T> for TwoSidedVec<T> {
24    #[inline]
25    fn extend_back<I: IntoIterator<Item=&'a T>>(&mut self, iter: I) {
26        SpecExtend::<&'a T, I::IntoIter>::extend_back(self, iter.into_iter())
27    }
28    #[inline]
29    fn extend_front<I: IntoIterator<Item=&'a T>>(&mut self, iter: I) {
30        SpecExtend::<&'a T, I::IntoIter>::extend_front(self, iter.into_iter())
31    }
32}
33
34
35
36/// The internal trait used to specialize `TwoSidedExtend` into more efficient implementations.
37trait SpecExtend<T, I> {
38    fn extend_back(&mut self, iter: I);
39    fn extend_front(&mut self, iter: I);
40}
41
42impl<T, I: Iterator<Item=T>> SpecExtend<T, I> for TwoSidedVec<T> {
43    #[inline]
44    default fn extend_back(&mut self, iter: I) {
45        self.default_extend_back(iter)
46    }
47    #[inline]
48    default fn extend_front(&mut self, iter: I) {
49        self.default_extend_front(iter)
50    }
51}
52/// Specialize for iterators whose length we trust.
53impl<T, I: iter::TrustedLen<Item=T>> SpecExtend<T, I> for TwoSidedVec<T> {
54    default fn extend_back(&mut self, iter: I) {
55        let (low, high) = iter.size_hint();
56        if let Some(additional) = high {
57            debug_assert_eq!(additional, low);
58            self.reserve_back(additional);
59            debug_assert!(additional <= isize::max_value() as usize);
60            let mut ptr = self.start_ptr();
61            for value in iter {
62                unsafe {
63                    ptr = ptr.sub(1);
64                    ptr.write(value);
65                    /*
66                     * Remember we need to be panic safe,
67                     * so we must set this at each step.
68                     * Overflow is impossible,
69                     * since we can never allocate more than `isize::max_value` bytes.
70                     * It appears this actually won't be optimized away by LLVM
71                     * as described in rust-lang/rust#32155
72                     * @bluss found a got workaround but it's kind of overkill for us
73                     * rust-lang/rust#36355
74                     */
75                    self.start_index -= 1;
76                }
77            }
78        } else {
79            self.default_extend_back(iter);
80        }
81    }
82
83    default fn extend_front(&mut self, iter: I) {
84        let (low, high) = iter.size_hint();
85        if let Some(additional) = high {
86            debug_assert_eq!(additional, low);
87            self.reserve_front(additional);
88            debug_assert!(additional <= isize::max_value() as usize);
89            let mut ptr = self.end_ptr();
90            for value in iter {
91                unsafe {
92                    ptr.write(value);
93                    ptr = ptr.add(1);
94                }
95                /*
96                 * Remember we need to be panic safe,
97                 * so we must set this at each step.
98                 * See above for more info on optimization and overflow.
99                 */
100                self.end_index += 1;
101            }
102        } else {
103            self.default_extend_front(iter);
104        }
105    }
106}
107
108impl<T> SpecExtend<T, vec::IntoIter<T>> for TwoSidedVec<T> {
109    #[inline]
110    fn extend_back(&mut self, iter: vec::IntoIter<T>) {
111        // This is specialized to reuse the allocation, so it should be free
112        let elements = iter.collect::<Vec<T>>();
113        unsafe { self.raw_extend_back(elements.as_ptr(), elements.len()); }
114        mem::forget(elements);
115    }
116
117    #[inline]
118    fn extend_front(&mut self, iter: vec::IntoIter<T>) {
119        // This is specialized to reuse the allocation, so it should be free
120        let elements = iter.collect::<Vec<T>>();
121        unsafe { self.raw_extend_front(elements.as_ptr(), elements.len()); }
122        mem::forget(elements);
123    }
124}
125impl<'a, T: Copy + 'a, I: Iterator<Item=&'a T>> SpecExtend<&'a T, I> for TwoSidedVec<T> {
126    #[inline]
127    default fn extend_back(&mut self, iter: I) {
128        TwoSidedExtend::extend_back(self, iter.cloned())
129    }
130
131    #[inline]
132    default fn extend_front(&mut self, iter: I) {
133        TwoSidedExtend::extend_front(self, iter.cloned());
134    }
135}
136/// Specialize `Copy`able slices to directly `memcpy` their bytes.
137impl<'a, T: Copy + 'a> SpecExtend<&'a T, slice::Iter<'a, T>> for TwoSidedVec<T> {
138    #[inline]
139    fn extend_back(&mut self, iter: slice::Iter<'a, T>) {
140        let target = iter.as_slice();
141        unsafe {
142            self.raw_extend_back(target.as_ptr(), target.len());
143        }
144    }
145
146    #[inline]
147    fn extend_front(&mut self, iter: slice::Iter<'a, T>) {
148        let target = iter.as_slice();
149        unsafe {
150            self.raw_extend_front(target.as_ptr(), target.len());
151        }
152    }
153}
154
two_sided_vec/extend.rs

two_sided_vec/
extend.rs
