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. `SmallVector`).
   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)]
   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
  25 impl<T> From<Vec<T>> for ThinVec<T> {
  26     fn from(vec: Vec<T>) -> Self {
  27         if vec.is_empty() { ThinVec(None) } else { ThinVec(Some(Box::new(vec))) }
  28     }
  29 }
  30
  31 impl<T> Into<Vec<T>> for ThinVec<T> {
  32     fn into(self) -> Vec<T> {
  33         match self {
  34             ThinVec(None) => Vec::new(),
  35             ThinVec(Some(vec)) => *vec,
  36         }
  37     }
  38 }
  39
  40 impl<T> ::std::ops::Deref for ThinVec<T> {
  41     type Target = [T];
  42     fn deref(&self) -> &[T] {
  43         match *self {
  44             ThinVec(None) => &[],
  45             ThinVec(Some(ref vec)) => vec,
  46         }
  47     }
  48 }
  49
  50 impl<T> ::std::ops::DerefMut for ThinVec<T> {
  51     fn deref_mut(&mut self) -> &mut [T] {
  52         match *self {
  53             ThinVec(None) => &mut [],
  54             ThinVec(Some(ref mut vec)) => vec,
  55         }
  56     }
  57 }
  58
  59 impl<T> FromIterator<T> for ThinVec<T> {
  60     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
  61         // `Vec::from_iter()` should not allocate if the iterator is empty.
  62         let vec: Vec<_> = iter.into_iter().collect();
  63         if vec.is_empty() { ThinVec(None) } else { ThinVec(Some(Box::new(vec))) }
  64     }
  65 }
  66
  67 impl<T> IntoIterator for ThinVec<T> {
  68     type Item = T;
  69     type IntoIter = std::vec::IntoIter<T>;
  70
  71     fn into_iter(self) -> Self::IntoIter {
  72         // This is still performant because `Vec::new()` does not allocate.
  73         self.0.map_or_else(Vec::new, |ptr| *ptr).into_iter()
  74     }
  75 }
  76
  77 impl<'a, T> IntoIterator for &'a ThinVec<T> {
  78     type Item = &'a T;
  79     type IntoIter = std::slice::Iter<'a, T>;
  80
  81     fn into_iter(self) -> Self::IntoIter {
  82         self.as_ref().iter()
  83     }
  84 }
  85
  86 impl<'a, T> IntoIterator for &'a mut ThinVec<T> {
  87     type Item = &'a mut T;
  88     type IntoIter = std::slice::IterMut<'a, T>;
  89
  90     fn into_iter(self) -> Self::IntoIter {
  91         self.as_mut().iter_mut()
  92     }
  93 }
  94
  95 impl<T> Extend<T> for ThinVec<T> {
  96     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
  97         match *self {
  98             ThinVec(Some(ref mut vec)) => vec.extend(iter),
  99             ThinVec(None) => *self = iter.into_iter().collect::<Vec<_>>().into(),
 100         }
 101     }
 102
 103     fn extend_one(&mut self, item: T) {
 104         match *self {
 105             ThinVec(Some(ref mut vec)) => vec.push(item),
 106             ThinVec(None) => *self = vec![item].into(),
 107         }
 108     }
 109
 110     fn extend_reserve(&mut self, additional: usize) {
 111         match *self {
 112             ThinVec(Some(ref mut vec)) => vec.reserve(additional),
 113             ThinVec(None) => *self = Vec::with_capacity(additional).into(),
 114         }
 115     }
 116 }
 117
 118 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for ThinVec<T> {
 119     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 120         (**self).hash_stable(hcx, hasher)
 121     }
 122 }
 123
 124 impl<T> Default for ThinVec<T> {
 125     fn default() -> Self {
 126         Self(None)
 127     }
 128 }
 129
 130 #[cfg(test)]
 131 mod tests;