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     /// Note: if `set_len(0)` is called on a non-empty `ThinVec`, it will
  32     /// remain in the `Some` form. This is required for some code sequences
  33     /// (such as the one in `flat_map_in_place`) that call `set_len(0)` before
  34     /// an operation that might panic, and then call `set_len(n)` again
  35     /// afterwards.
  36     pub unsafe fn set_len(&mut self, new_len: usize) {
  37         match *self {
  38             ThinVec(None) => {
  39                 // A prerequisite of `Vec::set_len` is that `new_len` must be
  40                 // less than or equal to capacity(). The same applies here.
  41                 if new_len != 0 {
  42                     panic!("unsafe ThinVec::set_len({})", new_len);
  43                 }
  44             }
  45             ThinVec(Some(ref mut vec)) => vec.set_len(new_len),
  46         }
  47     }
  48
  49     pub fn insert(&mut self, index: usize, value: T) {
  50         match *self {
  51             ThinVec(None) => {
  52                 if index == 0 {
  53                     *self = vec![value].into();
  54                 } else {
  55                     panic!("invalid ThinVec::insert");
  56                 }
  57             }
  58             ThinVec(Some(ref mut vec)) => vec.insert(index, value),
  59         }
  60     }
  61
  62     pub fn remove(&mut self, index: usize) -> T {
  63         match self {
  64             ThinVec(None) => panic!("invalid ThinVec::remove"),
  65             ThinVec(Some(vec)) => vec.remove(index),
  66         }
  67     }
  68
  69     pub fn as_slice(&self) -> &[T] {
  70         match self {
  71             ThinVec(None) => &[],
  72             ThinVec(Some(vec)) => vec.as_slice(),
  73         }
  74     }
  75 }
  76
  77 impl<T> From<Vec<T>> for ThinVec<T> {
  78     fn from(vec: Vec<T>) -> Self {
  79         if vec.is_empty() { ThinVec(None) } else { ThinVec(Some(Box::new(vec))) }
  80     }
  81 }
  82
  83 impl<T> Into<Vec<T>> for ThinVec<T> {
  84     fn into(self) -> Vec<T> {
  85         match self {
  86             ThinVec(None) => Vec::new(),
  87             ThinVec(Some(vec)) => *vec,
  88         }
  89     }
  90 }
  91
  92 impl<T> ::std::ops::Deref for ThinVec<T> {
  93     type Target = [T];
  94     fn deref(&self) -> &[T] {
  95         match *self {
  96             ThinVec(None) => &[],
  97             ThinVec(Some(ref vec)) => vec,
  98         }
  99     }
 100 }
 101
 102 impl<T> ::std::ops::DerefMut for ThinVec<T> {
 103     fn deref_mut(&mut self) -> &mut [T] {
 104         match *self {
 105             ThinVec(None) => &mut [],
 106             ThinVec(Some(ref mut vec)) => vec,
 107         }
 108     }
 109 }
 110
 111 impl<T> FromIterator<T> for ThinVec<T> {
 112     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
 113         // `Vec::from_iter()` should not allocate if the iterator is empty.
 114         let vec: Vec<_> = iter.into_iter().collect();
 115         if vec.is_empty() { ThinVec(None) } else { ThinVec(Some(Box::new(vec))) }
 116     }
 117 }
 118
 119 impl<T> IntoIterator for ThinVec<T> {
 120     type Item = T;
 121     type IntoIter = std::vec::IntoIter<T>;
 122
 123     fn into_iter(self) -> Self::IntoIter {
 124         // This is still performant because `Vec::new()` does not allocate.
 125         self.0.map_or_else(Vec::new, |ptr| *ptr).into_iter()
 126     }
 127 }
 128
 129 impl<'a, T> IntoIterator for &'a ThinVec<T> {
 130     type Item = &'a T;
 131     type IntoIter = std::slice::Iter<'a, T>;
 132
 133     fn into_iter(self) -> Self::IntoIter {
 134         self.as_ref().iter()
 135     }
 136 }
 137
 138 impl<'a, T> IntoIterator for &'a mut ThinVec<T> {
 139     type Item = &'a mut T;
 140     type IntoIter = std::slice::IterMut<'a, T>;
 141
 142     fn into_iter(self) -> Self::IntoIter {
 143         self.as_mut().iter_mut()
 144     }
 145 }
 146
 147 impl<T> Extend<T> for ThinVec<T> {
 148     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
 149         match *self {
 150             ThinVec(Some(ref mut vec)) => vec.extend(iter),
 151             ThinVec(None) => *self = iter.into_iter().collect::<Vec<_>>().into(),
 152         }
 153     }
 154
 155     fn extend_one(&mut self, item: T) {
 156         self.push(item)
 157     }
 158
 159     fn extend_reserve(&mut self, additional: usize) {
 160         match *self {
 161             ThinVec(Some(ref mut vec)) => vec.reserve(additional),
 162             ThinVec(None) => *self = Vec::with_capacity(additional).into(),
 163         }
 164     }
 165 }
 166
 167 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for ThinVec<T> {
 168     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 169         (**self).hash_stable(hcx, hasher)
 170     }
 171 }
 172
 173 impl<T> Default for ThinVec<T> {
 174     fn default() -> Self {
 175         Self(None)
 176     }
 177 }
 178
 179 #[cfg(test)]
 180 mod tests;