compiler/rustc_data_structures/src/thin_vec.rs

   1 use crate::stable_hasher::{HashStable, StableHasher};
   2
   3 use std::iter::FromIterator;
   4
   5 /// A vector type optimized for cases where this size is usually 0 (cf. `SmallVec`).
   6 /// The `Option<Box<..>>` wrapping allows us to represent a zero sized vector with `None`,
   7 /// which uses only a single (null) pointer.
   8 #[derive(Clone, Encodable, Decodable, Debug, Hash, Eq, PartialEq)]
   9 pub struct ThinVec<T>(Option<Box<Vec<T>>>);
  10
  11 impl<T> ThinVec<T> {
  12     pub fn new() -> Self {
  13         ThinVec(None)
  14     }
  15
  16     pub fn iter(&self) -> std::slice::Iter<'_, T> {
  17         self.into_iter()
  18     }
  19
  20     pub fn iter_mut(&mut self) -> std::slice::IterMut<'_, T> {
  21         self.into_iter()
  22     }
  23
  24     pub fn push(&mut self, item: T) {
  25         match *self {
  26             ThinVec(Some(ref mut vec)) => vec.push(item),
  27             ThinVec(None) => *self = vec![item].into(),
  28         }
  29     }
  30 }
  31
  32 impl<T> From<Vec<T>> for ThinVec<T> {
  33     fn from(vec: Vec<T>) -> Self {
  34         if vec.is_empty() { ThinVec(None) } else { ThinVec(Some(Box::new(vec))) }
  35     }
  36 }
  37
  38 impl<T> Into<Vec<T>> for ThinVec<T> {
  39     fn into(self) -> Vec<T> {
  40         match self {
  41             ThinVec(None) => Vec::new(),
  42             ThinVec(Some(vec)) => *vec,
  43         }
  44     }
  45 }
  46
  47 impl<T> ::std::ops::Deref for ThinVec<T> {
  48     type Target = [T];
  49     fn deref(&self) -> &[T] {
  50         match *self {
  51             ThinVec(None) => &[],
  52             ThinVec(Some(ref vec)) => vec,
  53         }
  54     }
  55 }
  56
  57 impl<T> ::std::ops::DerefMut for ThinVec<T> {
  58     fn deref_mut(&mut self) -> &mut [T] {
  59         match *self {
  60             ThinVec(None) => &mut [],
  61             ThinVec(Some(ref mut vec)) => vec,
  62         }
  63     }
  64 }
  65
  66 impl<T> FromIterator<T> for ThinVec<T> {
  67     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
  68         // `Vec::from_iter()` should not allocate if the iterator is empty.
  69         let vec: Vec<_> = iter.into_iter().collect();
  70         if vec.is_empty() { ThinVec(None) } else { ThinVec(Some(Box::new(vec))) }
  71     }
  72 }
  73
  74 impl<T> IntoIterator for ThinVec<T> {
  75     type Item = T;
  76     type IntoIter = std::vec::IntoIter<T>;
  77
  78     fn into_iter(self) -> Self::IntoIter {
  79         // This is still performant because `Vec::new()` does not allocate.
  80         self.0.map_or_else(Vec::new, |ptr| *ptr).into_iter()
  81     }
  82 }
  83
  84 impl<'a, T> IntoIterator for &'a ThinVec<T> {
  85     type Item = &'a T;
  86     type IntoIter = std::slice::Iter<'a, T>;
  87
  88     fn into_iter(self) -> Self::IntoIter {
  89         self.as_ref().iter()
  90     }
  91 }
  92
  93 impl<'a, T> IntoIterator for &'a mut ThinVec<T> {
  94     type Item = &'a mut T;
  95     type IntoIter = std::slice::IterMut<'a, T>;
  96
  97     fn into_iter(self) -> Self::IntoIter {
  98         self.as_mut().iter_mut()
  99     }
 100 }
 101
 102 impl<T> Extend<T> for ThinVec<T> {
 103     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
 104         match *self {
 105             ThinVec(Some(ref mut vec)) => vec.extend(iter),
 106             ThinVec(None) => *self = iter.into_iter().collect::<Vec<_>>().into(),
 107         }
 108     }
 109
 110     fn extend_one(&mut self, item: T) {
 111         self.push(item)
 112     }
 113
 114     fn extend_reserve(&mut self, additional: usize) {
 115         match *self {
 116             ThinVec(Some(ref mut vec)) => vec.reserve(additional),
 117             ThinVec(None) => *self = Vec::with_capacity(additional).into(),
 118         }
 119     }
 120 }
 121
 122 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for ThinVec<T> {
 123     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 124         (**self).hash_stable(hcx, hasher)
 125     }
 126 }
 127
 128 impl<T> Default for ThinVec<T> {
 129     fn default() -> Self {
 130         Self(None)
 131     }
 132 }
 133
 134 #[cfg(test)]
 135 mod tests;