src/librustc_data_structures/small_vec.rs

   1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! A vector type intended to be used for collecting from iterators onto the stack.
  12 //!
  13 //! Space for up to N elements is provided on the stack.  If more elements are collected, Vec is
  14 //! used to store the values on the heap. SmallVec is similar to AccumulateVec, but adds
  15 //! the ability to push elements.
  16 //!
  17 //! The N above is determined by Array's implementor, by way of an associated constant.
  18
  19 use std::ops::{Deref, DerefMut};
  20 use std::iter::{IntoIterator, FromIterator};
  21 use std::fmt::{self, Debug};
  22 use std::mem;
  23 use std::ptr;
  24
  25 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
  26
  27 use accumulate_vec::{IntoIter, AccumulateVec};
  28 use array_vec::Array;
  29
  30 pub struct SmallVec<A: Array>(AccumulateVec<A>);
  31
  32 impl<A> Clone for SmallVec<A>
  33     where A: Array,
  34           A::Element: Clone {
  35     fn clone(&self) -> Self {
  36         SmallVec(self.0.clone())
  37     }
  38 }
  39
  40 impl<A> Debug for SmallVec<A>
  41     where A: Array + Debug,
  42           A::Element: Debug {
  43     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  44         f.debug_tuple("SmallVec").field(&self.0).finish()
  45     }
  46 }
  47
  48 impl<A: Array> SmallVec<A> {
  49     pub fn new() -> Self {
  50         SmallVec(AccumulateVec::new())
  51     }
  52
  53     pub fn is_array(&self) -> bool {
  54         self.0.is_array()
  55     }
  56
  57     pub fn with_capacity(cap: usize) -> Self {
  58         let mut vec = SmallVec::new();
  59         vec.reserve(cap);
  60         vec
  61     }
  62
  63     pub fn one(el: A::Element) -> Self {
  64         SmallVec(AccumulateVec::one(el))
  65     }
  66
  67     pub fn many<I: IntoIterator<Item=A::Element>>(els: I) -> Self {
  68         SmallVec(AccumulateVec::many(els))
  69     }
  70
  71     pub fn expect_one(self, err: &'static str) -> A::Element {
  72         assert!(self.len() == 1, err);
  73         match self.0 {
  74             AccumulateVec::Array(arr) => arr.into_iter().next().unwrap(),
  75             AccumulateVec::Heap(vec) => vec.into_iter().next().unwrap(),
  76         }
  77     }
  78
  79     /// Will reallocate onto the heap if needed.
  80     pub fn push(&mut self, el: A::Element) {
  81         self.reserve(1);
  82         match self.0 {
  83             AccumulateVec::Array(ref mut array) => array.push(el),
  84             AccumulateVec::Heap(ref mut vec) => vec.push(el),
  85         }
  86     }
  87
  88     pub fn reserve(&mut self, n: usize) {
  89         match self.0 {
  90             AccumulateVec::Array(_) => {
  91                 if self.len() + n > A::LEN {
  92                     let len = self.len();
  93                     let array = mem::replace(&mut self.0,
  94                             AccumulateVec::Heap(Vec::with_capacity(len + n)));
  95                     if let AccumulateVec::Array(array) = array {
  96                         match self.0 {
  97                             AccumulateVec::Heap(ref mut vec) => vec.extend(array),
  98                             _ => unreachable!()
  99                         }
 100                     }
 101                 }
 102             }
 103             AccumulateVec::Heap(ref mut vec) => vec.reserve(n)
 104         }
 105     }
 106
 107     pub unsafe fn set_len(&mut self, len: usize) {
 108         match self.0 {
 109             AccumulateVec::Array(ref mut arr) => arr.set_len(len),
 110             AccumulateVec::Heap(ref mut vec) => vec.set_len(len),
 111         }
 112     }
 113
 114     pub fn insert(&mut self, index: usize, element: A::Element) {
 115         let len = self.len();
 116
 117         // Reserve space for shifting elements to the right
 118         self.reserve(1);
 119
 120         assert!(index <= len);
 121
 122         unsafe {
 123             // infallible
 124             // The spot to put the new value
 125             {
 126                 let p = self.as_mut_ptr().offset(index as isize);
 127                 // Shift everything over to make space. (Duplicating the
 128                 // `index`th element into two consecutive places.)
 129                 ptr::copy(p, p.offset(1), len - index);
 130                 // Write it in, overwriting the first copy of the `index`th
 131                 // element.
 132                 ptr::write(p, element);
 133             }
 134             self.set_len(len + 1);
 135         }
 136     }
 137
 138     pub fn truncate(&mut self, len: usize) {
 139         unsafe {
 140             while len < self.len() {
 141                 // Decrement len before the drop_in_place(), so a panic on Drop
 142                 // doesn't re-drop the just-failed value.
 143                 let newlen = self.len() - 1;
 144                 self.set_len(newlen);
 145                 ::std::ptr::drop_in_place(self.get_unchecked_mut(newlen));
 146             }
 147         }
 148     }
 149 }
 150
 151 impl<A: Array> Deref for SmallVec<A> {
 152     type Target = AccumulateVec<A>;
 153     fn deref(&self) -> &Self::Target {
 154         &self.0
 155     }
 156 }
 157
 158 impl<A: Array> DerefMut for SmallVec<A> {
 159     fn deref_mut(&mut self) -> &mut AccumulateVec<A> {
 160         &mut self.0
 161     }
 162 }
 163
 164 impl<A: Array> FromIterator<A::Element> for SmallVec<A> {
 165     fn from_iter<I>(iter: I) -> Self where I: IntoIterator<Item=A::Element> {
 166         SmallVec(iter.into_iter().collect())
 167     }
 168 }
 169
 170 impl<A: Array> Extend<A::Element> for SmallVec<A> {
 171     fn extend<I: IntoIterator<Item=A::Element>>(&mut self, iter: I) {
 172         let iter = iter.into_iter();
 173         self.reserve(iter.size_hint().0);
 174         match self.0 {
 175             AccumulateVec::Heap(ref mut vec) => vec.extend(iter),
 176             _ => iter.for_each(|el| self.push(el))
 177         }
 178     }
 179 }
 180
 181 impl<A: Array> IntoIterator for SmallVec<A> {
 182     type Item = A::Element;
 183     type IntoIter = IntoIter<A>;
 184     fn into_iter(self) -> Self::IntoIter {
 185         self.0.into_iter()
 186     }
 187 }
 188
 189 impl<A: Array> Default for SmallVec<A> {
 190     fn default() -> SmallVec<A> {
 191         SmallVec::new()
 192     }
 193 }
 194
 195 impl<A> Encodable for SmallVec<A>
 196     where A: Array,
 197           A::Element: Encodable {
 198     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 199         s.emit_seq(self.len(), |s| {
 200             for (i, e) in self.iter().enumerate() {
 201                 s.emit_seq_elt(i, |s| e.encode(s))?;
 202             }
 203             Ok(())
 204         })
 205     }
 206 }
 207
 208 impl<A> Decodable for SmallVec<A>
 209     where A: Array,
 210           A::Element: Decodable {
 211     fn decode<D: Decoder>(d: &mut D) -> Result<SmallVec<A>, D::Error> {
 212         d.read_seq(|d, len| {
 213             (0..len).map(|i| d.read_seq_elt(i, |d| Decodable::decode(d))).collect()
 214         })
 215     }
 216 }
 217
 218 #[cfg(test)]
 219 mod tests {
 220     extern crate test;
 221     use self::test::Bencher;
 222
 223     use super::*;
 224
 225     #[bench]
 226     fn fill_small_vec_1_10_with_cap(b: &mut Bencher) {
 227         b.iter(|| {
 228             let mut sv: SmallVec<[usize; 1]> = SmallVec::with_capacity(10);
 229
 230             sv.extend(0..10);
 231         })
 232     }
 233
 234     #[bench]
 235     fn fill_small_vec_1_10_wo_cap(b: &mut Bencher) {
 236         b.iter(|| {
 237             let mut sv: SmallVec<[usize; 1]> = SmallVec::new();
 238
 239             sv.extend(0..10);
 240         })
 241     }
 242
 243     #[bench]
 244     fn fill_small_vec_8_10_with_cap(b: &mut Bencher) {
 245         b.iter(|| {
 246             let mut sv: SmallVec<[usize; 8]> = SmallVec::with_capacity(10);
 247
 248             sv.extend(0..10);
 249         })
 250     }
 251
 252     #[bench]
 253     fn fill_small_vec_8_10_wo_cap(b: &mut Bencher) {
 254         b.iter(|| {
 255             let mut sv: SmallVec<[usize; 8]> = SmallVec::new();
 256
 257             sv.extend(0..10);
 258         })
 259     }
 260
 261     #[bench]
 262     fn fill_small_vec_32_10_with_cap(b: &mut Bencher) {
 263         b.iter(|| {
 264             let mut sv: SmallVec<[usize; 32]> = SmallVec::with_capacity(10);
 265
 266             sv.extend(0..10);
 267         })
 268     }
 269
 270     #[bench]
 271     fn fill_small_vec_32_10_wo_cap(b: &mut Bencher) {
 272         b.iter(|| {
 273             let mut sv: SmallVec<[usize; 32]> = SmallVec::new();
 274
 275             sv.extend(0..10);
 276         })
 277     }
 278
 279     #[bench]
 280     fn fill_small_vec_1_50_with_cap(b: &mut Bencher) {
 281         b.iter(|| {
 282             let mut sv: SmallVec<[usize; 1]> = SmallVec::with_capacity(50);
 283
 284             sv.extend(0..50);
 285         })
 286     }
 287
 288     #[bench]
 289     fn fill_small_vec_1_50_wo_cap(b: &mut Bencher) {
 290         b.iter(|| {
 291             let mut sv: SmallVec<[usize; 1]> = SmallVec::new();
 292
 293             sv.extend(0..50);
 294         })
 295     }
 296
 297     #[bench]
 298     fn fill_small_vec_8_50_with_cap(b: &mut Bencher) {
 299         b.iter(|| {
 300             let mut sv: SmallVec<[usize; 8]> = SmallVec::with_capacity(50);
 301
 302             sv.extend(0..50);
 303         })
 304     }
 305
 306     #[bench]
 307     fn fill_small_vec_8_50_wo_cap(b: &mut Bencher) {
 308         b.iter(|| {
 309             let mut sv: SmallVec<[usize; 8]> = SmallVec::new();
 310
 311             sv.extend(0..50);
 312         })
 313     }
 314
 315     #[bench]
 316     fn fill_small_vec_32_50_with_cap(b: &mut Bencher) {
 317         b.iter(|| {
 318             let mut sv: SmallVec<[usize; 32]> = SmallVec::with_capacity(50);
 319
 320             sv.extend(0..50);
 321         })
 322     }
 323
 324     #[bench]
 325     fn fill_small_vec_32_50_wo_cap(b: &mut Bencher) {
 326         b.iter(|| {
 327             let mut sv: SmallVec<[usize; 32]> = SmallVec::new();
 328
 329             sv.extend(0..50);
 330         })
 331     }
 332 }