library/alloc/src/vec/spec_from_iter_nested.rs

   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 = match iterator.size_hint() {
  54             (_, Some(upper)) => 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(iterator);
  63         vector
  64     }
  65 }