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