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