1 | use core::cmp; |
2 | use core::iter::TrustedLen; |
3 | use core::ptr; |
4 | |
5 | use crate::raw_vec::RawVec; |
6 | |
7 | use super::{SpecExtend, Vec}; |
8 | |
9 | /// Another specialization trait for Vec::from_iter |
10 | /// necessary to manually prioritize overlapping specializations |
11 | /// see [`SpecFromIter`](super::SpecFromIter) for details. |
12 | pub(super) trait SpecFromIterNested<T, I> { |
13 | fn from_iter(iter: I) -> Self; |
14 | } |
15 | |
16 | impl<T, I> SpecFromIterNested<T, I> for Vec<T> |
17 | where |
18 | I: Iterator<Item = T>, |
19 | { |
20 | default fn from_iter(mut iterator: I) -> Self { |
21 | // Unroll the first iteration, as the vector is going to be |
22 | // expanded on this iteration in every case when the iterable is not |
23 | // empty, but the loop in extend_desugared() is not going to see the |
24 | // vector being full in the few subsequent loop iterations. |
25 | // So we get better branch prediction. |
26 | let mut vector = match iterator.next() { |
27 | None => return Vec::new(), |
28 | Some(element) => { |
29 | let (lower, _) = iterator.size_hint(); |
30 | let initial_capacity = |
31 | cmp::max(RawVec::<T>::MIN_NON_ZERO_CAP, lower.saturating_add(1)); |
32 | let mut vector = Vec::with_capacity(initial_capacity); |
33 | unsafe { |
34 | // SAFETY: We requested capacity at least 1 |
35 | ptr::write(vector.as_mut_ptr(), element); |
36 | vector.set_len(1); |
37 | } |
38 | vector |
39 | } |
40 | }; |
41 | // must delegate to spec_extend() since extend() itself delegates |
42 | // to spec_from for empty Vecs |
43 | <Vec<T> as SpecExtend<T, I>>::spec_extend(&mut vector, iterator); |
44 | vector |
45 | } |
46 | } |
47 | |
48 | impl<T, I> SpecFromIterNested<T, I> for Vec<T> |
49 | where |
50 | I: TrustedLen<Item = T>, |
51 | { |
52 | fn from_iter(iterator: I) -> Self { |
53 | let mut vector: Vec = match iterator.size_hint() { |
54 | (_, Some(upper: usize)) => Vec::with_capacity(upper), |
55 | // TrustedLen contract guarantees that `size_hint() == (_, None)` means that there |
56 | // are more than `usize::MAX` elements. |
57 | // Since the previous branch would eagerly panic if the capacity is too large |
58 | // (via `with_capacity`) we do the same here. |
59 | _ => panic!("capacity overflow" ), |
60 | }; |
61 | // reuse extend specialization for TrustedLen |
62 | vector.spec_extend(iter:iterator); |
63 | vector |
64 | } |
65 | } |
66 | |