src/librustc_data_structures/array_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 stack-allocated vector, allowing storage of N elements on the stack.
  12
  13 use std::marker::Unsize;
  14 use std::iter::Extend;
  15 use std::ptr::{self, drop_in_place, Shared};
  16 use std::ops::{Deref, DerefMut, Range};
  17 use std::hash::{Hash, Hasher};
  18 use std::slice;
  19 use std::fmt;
  20 use std::mem;
  21 use std::collections::range::RangeArgument;
  22
  23 pub unsafe trait Array {
  24     type Element;
  25     type PartialStorage: Default + Unsize<[ManuallyDrop<Self::Element>]>;
  26     const LEN: usize;
  27 }
  28
  29 unsafe impl<T> Array for [T; 1] {
  30     type Element = T;
  31     type PartialStorage = [ManuallyDrop<T>; 1];
  32     const LEN: usize = 1;
  33 }
  34
  35 unsafe impl<T> Array for [T; 8] {
  36     type Element = T;
  37     type PartialStorage = [ManuallyDrop<T>; 8];
  38     const LEN: usize = 8;
  39 }
  40
  41 pub struct ArrayVec<A: Array> {
  42     count: usize,
  43     values: A::PartialStorage
  44 }
  45
  46 impl<A> Hash for ArrayVec<A>
  47     where A: Array,
  48           A::Element: Hash {
  49     fn hash<H>(&self, state: &mut H) where H: Hasher {
  50         (&self[..]).hash(state);
  51     }
  52 }
  53
  54 impl<A: Array> PartialEq for ArrayVec<A> {
  55     fn eq(&self, other: &Self) -> bool {
  56         self == other
  57     }
  58 }
  59
  60 impl<A: Array> Eq for ArrayVec<A> {}
  61
  62 impl<A> Clone for ArrayVec<A>
  63     where A: Array,
  64           A::Element: Clone {
  65     fn clone(&self) -> Self {
  66         let mut v = ArrayVec::new();
  67         v.extend(self.iter().cloned());
  68         v
  69     }
  70 }
  71
  72 impl<A: Array> ArrayVec<A> {
  73     pub fn new() -> Self {
  74         ArrayVec {
  75             count: 0,
  76             values: Default::default(),
  77         }
  78     }
  79
  80     pub fn len(&self) -> usize {
  81         self.count
  82     }
  83
  84     pub unsafe fn set_len(&mut self, len: usize) {
  85         self.count = len;
  86     }
  87
  88     /// Panics when the stack vector is full.
  89     pub fn push(&mut self, el: A::Element) {
  90         let arr = &mut self.values as &mut [ManuallyDrop<_>];
  91         arr[self.count] = ManuallyDrop { value: el };
  92         self.count += 1;
  93     }
  94
  95     pub fn pop(&mut self) -> Option<A::Element> {
  96         if self.count > 0 {
  97             let arr = &mut self.values as &mut [ManuallyDrop<_>];
  98             self.count -= 1;
  99             unsafe {
 100                 let value = ptr::read(&arr[self.count]);
 101                 Some(value.value)
 102             }
 103         } else {
 104             None
 105         }
 106     }
 107
 108     pub fn drain<R>(&mut self, range: R) -> Drain<A>
 109         where R: RangeArgument<usize>
 110     {
 111         // Memory safety
 112         //
 113         // When the Drain is first created, it shortens the length of
 114         // the source vector to make sure no uninitalized or moved-from elements
 115         // are accessible at all if the Drain's destructor never gets to run.
 116         //
 117         // Drain will ptr::read out the values to remove.
 118         // When finished, remaining tail of the vec is copied back to cover
 119         // the hole, and the vector length is restored to the new length.
 120         //
 121         let len = self.len();
 122         let start = *range.start().unwrap_or(&0);
 123         let end = *range.end().unwrap_or(&len);
 124         assert!(start <= end);
 125         assert!(end <= len);
 126
 127         unsafe {
 128             // set self.vec length's to start, to be safe in case Drain is leaked
 129             self.set_len(start);
 130             // Use the borrow in the IterMut to indicate borrowing behavior of the
 131             // whole Drain iterator (like &mut T).
 132             let range_slice = {
 133                 let arr = &mut self.values as &mut [ManuallyDrop<_>];
 134                 slice::from_raw_parts_mut(arr.as_mut_ptr().offset(start as isize),
 135                                           end - start)
 136             };
 137             Drain {
 138                 tail_start: end,
 139                 tail_len: len - end,
 140                 iter: range_slice.iter(),
 141                 array_vec: Shared::new(self as *mut _),
 142             }
 143         }
 144     }
 145 }
 146
 147 impl<A> Default for ArrayVec<A>
 148     where A: Array {
 149     fn default() -> Self {
 150         ArrayVec::new()
 151     }
 152 }
 153
 154 impl<A> fmt::Debug for ArrayVec<A>
 155     where A: Array,
 156           A::Element: fmt::Debug {
 157     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 158         self[..].fmt(f)
 159     }
 160 }
 161
 162 impl<A: Array> Deref for ArrayVec<A> {
 163     type Target = [A::Element];
 164     fn deref(&self) -> &Self::Target {
 165         unsafe {
 166             slice::from_raw_parts(&self.values as *const _ as *const A::Element, self.count)
 167         }
 168     }
 169 }
 170
 171 impl<A: Array> DerefMut for ArrayVec<A> {
 172     fn deref_mut(&mut self) -> &mut [A::Element] {
 173         unsafe {
 174             slice::from_raw_parts_mut(&mut self.values as *mut _ as *mut A::Element, self.count)
 175         }
 176     }
 177 }
 178
 179 impl<A: Array> Drop for ArrayVec<A> {
 180     fn drop(&mut self) {
 181         unsafe {
 182             drop_in_place(&mut self[..])
 183         }
 184     }
 185 }
 186
 187 impl<A: Array> Extend<A::Element> for ArrayVec<A> {
 188     fn extend<I>(&mut self, iter: I) where I: IntoIterator<Item=A::Element> {
 189         for el in iter {
 190             self.push(el);
 191         }
 192     }
 193 }
 194
 195 pub struct Iter<A: Array> {
 196     indices: Range<usize>,
 197     store: A::PartialStorage,
 198 }
 199
 200 impl<A: Array> Drop for Iter<A> {
 201     fn drop(&mut self) {
 202         for _ in self {}
 203     }
 204 }
 205
 206 impl<A: Array> Iterator for Iter<A> {
 207     type Item = A::Element;
 208
 209     fn next(&mut self) -> Option<A::Element> {
 210         let arr = &self.store as &[ManuallyDrop<_>];
 211         unsafe {
 212             self.indices.next().map(|i| ptr::read(&arr[i]).value)
 213         }
 214     }
 215
 216     fn size_hint(&self) -> (usize, Option<usize>) {
 217         self.indices.size_hint()
 218     }
 219 }
 220
 221 pub struct Drain<'a, A: Array>
 222         where A::Element: 'a
 223 {
 224     tail_start: usize,
 225     tail_len: usize,
 226     iter: slice::Iter<'a, ManuallyDrop<A::Element>>,
 227     array_vec: Shared<ArrayVec<A>>,
 228 }
 229
 230 impl<'a, A: Array> Iterator for Drain<'a, A> {
 231     type Item = A::Element;
 232
 233     #[inline]
 234     fn next(&mut self) -> Option<A::Element> {
 235         self.iter.next().map(|elt| unsafe { ptr::read(elt as *const ManuallyDrop<_>).value })
 236     }
 237
 238     fn size_hint(&self) -> (usize, Option<usize>) {
 239         self.iter.size_hint()
 240     }
 241 }
 242
 243 impl<'a, A: Array> Drop for Drain<'a, A> {
 244     fn drop(&mut self) {
 245         // exhaust self first
 246         while let Some(_) = self.next() {}
 247
 248         if self.tail_len > 0 {
 249             unsafe {
 250                 let source_array_vec = &mut **self.array_vec;
 251                 // memmove back untouched tail, update to new length
 252                 let start = source_array_vec.len();
 253                 let tail = self.tail_start;
 254                 {
 255                     let mut arr = &mut source_array_vec.values as &mut [ManuallyDrop<_>];
 256                     let src = arr.as_ptr().offset(tail as isize);
 257                     let dst = arr.as_mut_ptr().offset(start as isize);
 258                     ptr::copy(src, dst, self.tail_len);
 259                 };
 260                 source_array_vec.set_len(start + self.tail_len);
 261             }
 262         }
 263     }
 264 }
 265
 266 impl<A: Array> IntoIterator for ArrayVec<A> {
 267     type Item = A::Element;
 268     type IntoIter = Iter<A>;
 269     fn into_iter(self) -> Self::IntoIter {
 270         let store = unsafe {
 271             ptr::read(&self.values)
 272         };
 273         let indices = 0..self.count;
 274         mem::forget(self);
 275         Iter {
 276             indices: indices,
 277             store: store,
 278         }
 279     }
 280 }
 281
 282 impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> {
 283     type Item = &'a A::Element;
 284     type IntoIter = slice::Iter<'a, A::Element>;
 285     fn into_iter(self) -> Self::IntoIter {
 286         self.iter()
 287     }
 288 }
 289
 290 impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> {
 291     type Item = &'a mut A::Element;
 292     type IntoIter = slice::IterMut<'a, A::Element>;
 293     fn into_iter(self) -> Self::IntoIter {
 294         self.iter_mut()
 295     }
 296 }
 297
 298 // FIXME: This should use repr(transparent) from rust-lang/rfcs#1758.
 299 #[allow(unions_with_drop_fields)]
 300 pub union ManuallyDrop<T> {
 301     value: T,
 302     #[allow(dead_code)]
 303     empty: (),
 304 }
 305
 306 impl<T> ManuallyDrop<T> {
 307     fn new() -> ManuallyDrop<T> {
 308         ManuallyDrop {
 309             empty: ()
 310         }
 311     }
 312 }
 313
 314 impl<T> Default for ManuallyDrop<T> {
 315     fn default() -> Self {
 316         ManuallyDrop::new()
 317     }
 318 }
 319