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};
  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
  22 pub unsafe trait Array {
  23     type Element;
  24     type PartialStorage: Default + Unsize<[ManuallyDrop<Self::Element>]>;
  25     const LEN: usize;
  26 }
  27
  28 unsafe impl<T> Array for [T; 1] {
  29     type Element = T;
  30     type PartialStorage = [ManuallyDrop<T>; 1];
  31     const LEN: usize = 1;
  32 }
  33
  34 unsafe impl<T> Array for [T; 8] {
  35     type Element = T;
  36     type PartialStorage = [ManuallyDrop<T>; 8];
  37     const LEN: usize = 8;
  38 }
  39
  40 pub struct ArrayVec<A: Array> {
  41     count: usize,
  42     values: A::PartialStorage
  43 }
  44
  45 impl<A> Hash for ArrayVec<A>
  46     where A: Array,
  47           A::Element: Hash {
  48     fn hash<H>(&self, state: &mut H) where H: Hasher {
  49         (&self[..]).hash(state);
  50     }
  51 }
  52
  53 impl<A: Array> PartialEq for ArrayVec<A> {
  54     fn eq(&self, other: &Self) -> bool {
  55         self == other
  56     }
  57 }
  58
  59 impl<A: Array> Eq for ArrayVec<A> {}
  60
  61 impl<A> Clone for ArrayVec<A>
  62     where A: Array,
  63           A::Element: Clone {
  64     fn clone(&self) -> Self {
  65         let mut v = ArrayVec::new();
  66         v.extend(self.iter().cloned());
  67         v
  68     }
  69 }
  70
  71 impl<A: Array> ArrayVec<A> {
  72     pub fn new() -> Self {
  73         ArrayVec {
  74             count: 0,
  75             values: Default::default(),
  76         }
  77     }
  78
  79     pub fn len(&self) -> usize {
  80         self.count
  81     }
  82
  83     pub unsafe fn set_len(&mut self, len: usize) {
  84         self.count = len;
  85     }
  86
  87     /// Panics when the stack vector is full.
  88     pub fn push(&mut self, el: A::Element) {
  89         let arr = &mut self.values as &mut [ManuallyDrop<_>];
  90         arr[self.count] = ManuallyDrop { value: el };
  91         self.count += 1;
  92     }
  93
  94     pub fn pop(&mut self) -> Option<A::Element> {
  95         if self.count > 0 {
  96             let arr = &mut self.values as &mut [ManuallyDrop<_>];
  97             self.count -= 1;
  98             unsafe {
  99                 let value = ptr::read(&arr[self.count]);
 100                 Some(value.value)
 101             }
 102         } else {
 103             None
 104         }
 105     }
 106 }
 107
 108 impl<A> Default for ArrayVec<A>
 109     where A: Array {
 110     fn default() -> Self {
 111         ArrayVec::new()
 112     }
 113 }
 114
 115 impl<A> fmt::Debug for ArrayVec<A>
 116     where A: Array,
 117           A::Element: fmt::Debug {
 118     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 119         self[..].fmt(f)
 120     }
 121 }
 122
 123 impl<A: Array> Deref for ArrayVec<A> {
 124     type Target = [A::Element];
 125     fn deref(&self) -> &Self::Target {
 126         unsafe {
 127             slice::from_raw_parts(&self.values as *const _ as *const A::Element, self.count)
 128         }
 129     }
 130 }
 131
 132 impl<A: Array> DerefMut for ArrayVec<A> {
 133     fn deref_mut(&mut self) -> &mut [A::Element] {
 134         unsafe {
 135             slice::from_raw_parts_mut(&mut self.values as *mut _ as *mut A::Element, self.count)
 136         }
 137     }
 138 }
 139
 140 impl<A: Array> Drop for ArrayVec<A> {
 141     fn drop(&mut self) {
 142         unsafe {
 143             drop_in_place(&mut self[..])
 144         }
 145     }
 146 }
 147
 148 impl<A: Array> Extend<A::Element> for ArrayVec<A> {
 149     fn extend<I>(&mut self, iter: I) where I: IntoIterator<Item=A::Element> {
 150         for el in iter {
 151             self.push(el);
 152         }
 153     }
 154 }
 155
 156 pub struct Iter<A: Array> {
 157     indices: Range<usize>,
 158     store: A::PartialStorage,
 159 }
 160
 161 impl<A: Array> Drop for Iter<A> {
 162     fn drop(&mut self) {
 163         for _ in self {}
 164     }
 165 }
 166
 167 impl<A: Array> Iterator for Iter<A> {
 168     type Item = A::Element;
 169
 170     fn next(&mut self) -> Option<A::Element> {
 171         let arr = &self.store as &[ManuallyDrop<_>];
 172         unsafe {
 173             self.indices.next().map(|i| ptr::read(&arr[i]).value)
 174         }
 175     }
 176
 177     fn size_hint(&self) -> (usize, Option<usize>) {
 178         self.indices.size_hint()
 179     }
 180 }
 181
 182 impl<A: Array> IntoIterator for ArrayVec<A> {
 183     type Item = A::Element;
 184     type IntoIter = Iter<A>;
 185     fn into_iter(self) -> Self::IntoIter {
 186         let store = unsafe {
 187             ptr::read(&self.values)
 188         };
 189         let indices = 0..self.count;
 190         mem::forget(self);
 191         Iter {
 192             indices: indices,
 193             store: store,
 194         }
 195     }
 196 }
 197
 198 impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> {
 199     type Item = &'a A::Element;
 200     type IntoIter = slice::Iter<'a, A::Element>;
 201     fn into_iter(self) -> Self::IntoIter {
 202         self.iter()
 203     }
 204 }
 205
 206 impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> {
 207     type Item = &'a mut A::Element;
 208     type IntoIter = slice::IterMut<'a, A::Element>;
 209     fn into_iter(self) -> Self::IntoIter {
 210         self.iter_mut()
 211     }
 212 }
 213
 214 // FIXME: This should use repr(transparent) from rust-lang/rfcs#1758.
 215 #[allow(unions_with_drop_fields)]
 216 pub union ManuallyDrop<T> {
 217     value: T,
 218     #[allow(dead_code)]
 219     empty: (),
 220 }
 221
 222 impl<T> ManuallyDrop<T> {
 223     fn new() -> ManuallyDrop<T> {
 224         ManuallyDrop {
 225             empty: ()
 226         }
 227     }
 228 }
 229
 230 impl<T> Default for ManuallyDrop<T> {
 231     fn default() -> Self {
 232         ManuallyDrop::new()
 233     }
 234 }
 235