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.
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.
11 //! A stack-allocated vector, allowing storage of N elements on the stack.
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};
21 use std::collections::range::RangeArgument;
22 use std::collections::Bound::{Excluded, Included, Unbounded};
24 pub unsafe trait Array {
26 type PartialStorage: Default + Unsize<[ManuallyDrop<Self::Element>]>;
30 unsafe impl<T> Array for [T; 1] {
32 type PartialStorage = [ManuallyDrop<T>; 1];
36 unsafe impl<T> Array for [T; 8] {
38 type PartialStorage = [ManuallyDrop<T>; 8];
42 pub struct ArrayVec<A: Array> {
44 values: A::PartialStorage
47 impl<A> Hash for ArrayVec<A>
50 fn hash<H>(&self, state: &mut H) where H: Hasher {
51 (&self[..]).hash(state);
55 impl<A: Array> PartialEq for ArrayVec<A> {
56 fn eq(&self, other: &Self) -> bool {
61 impl<A: Array> Eq for ArrayVec<A> {}
63 impl<A> Clone for ArrayVec<A>
66 fn clone(&self) -> Self {
67 let mut v = ArrayVec::new();
68 v.extend(self.iter().cloned());
73 impl<A: Array> ArrayVec<A> {
74 pub fn new() -> Self {
77 values: Default::default(),
81 pub fn len(&self) -> usize {
85 pub unsafe fn set_len(&mut self, len: usize) {
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 };
96 pub fn pop(&mut self) -> Option<A::Element> {
98 let arr = &mut self.values as &mut [ManuallyDrop<_>];
101 let value = ptr::read(&arr[self.count]);
109 pub fn drain<R>(&mut self, range: R) -> Drain<A>
110 where R: RangeArgument<usize>
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.
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.
122 let len = self.len();
123 let start = match range.start() {
125 Excluded(&n) => n + 1,
128 let end = match range.end() {
129 Included(&n) => n + 1,
133 assert!(start <= end);
137 // set self.vec length's to start, to be safe in case Drain is leaked
139 // Use the borrow in the IterMut to indicate borrowing behavior of the
140 // whole Drain iterator (like &mut T).
142 let arr = &mut self.values as &mut [ManuallyDrop<_>];
143 slice::from_raw_parts_mut(arr.as_mut_ptr().offset(start as isize),
149 iter: range_slice.iter(),
150 array_vec: Shared::new(self as *mut _),
156 impl<A> Default for ArrayVec<A>
158 fn default() -> Self {
163 impl<A> fmt::Debug for ArrayVec<A>
165 A::Element: fmt::Debug {
166 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
171 impl<A: Array> Deref for ArrayVec<A> {
172 type Target = [A::Element];
173 fn deref(&self) -> &Self::Target {
175 slice::from_raw_parts(&self.values as *const _ as *const A::Element, self.count)
180 impl<A: Array> DerefMut for ArrayVec<A> {
181 fn deref_mut(&mut self) -> &mut [A::Element] {
183 slice::from_raw_parts_mut(&mut self.values as *mut _ as *mut A::Element, self.count)
188 impl<A: Array> Drop for ArrayVec<A> {
191 drop_in_place(&mut self[..])
196 impl<A: Array> Extend<A::Element> for ArrayVec<A> {
197 fn extend<I>(&mut self, iter: I) where I: IntoIterator<Item=A::Element> {
204 pub struct Iter<A: Array> {
205 indices: Range<usize>,
206 store: A::PartialStorage,
209 impl<A: Array> Drop for Iter<A> {
215 impl<A: Array> Iterator for Iter<A> {
216 type Item = A::Element;
218 fn next(&mut self) -> Option<A::Element> {
219 let arr = &self.store as &[ManuallyDrop<_>];
221 self.indices.next().map(|i| ptr::read(&arr[i]).value)
225 fn size_hint(&self) -> (usize, Option<usize>) {
226 self.indices.size_hint()
230 pub struct Drain<'a, A: Array>
235 iter: slice::Iter<'a, ManuallyDrop<A::Element>>,
236 array_vec: Shared<ArrayVec<A>>,
239 impl<'a, A: Array> Iterator for Drain<'a, A> {
240 type Item = A::Element;
243 fn next(&mut self) -> Option<A::Element> {
244 self.iter.next().map(|elt| unsafe { ptr::read(elt as *const ManuallyDrop<_>).value })
247 fn size_hint(&self) -> (usize, Option<usize>) {
248 self.iter.size_hint()
252 impl<'a, A: Array> Drop for Drain<'a, A> {
254 // exhaust self first
255 while let Some(_) = self.next() {}
257 if self.tail_len > 0 {
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;
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);
269 source_array_vec.set_len(start + self.tail_len);
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 {
280 ptr::read(&self.values)
282 let indices = 0..self.count;
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 {
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 {
307 // FIXME: This should use repr(transparent) from rust-lang/rfcs#1758.
308 #[allow(unions_with_drop_fields)]
309 pub union ManuallyDrop<T> {
315 impl<T> ManuallyDrop<T> {
316 fn new() -> ManuallyDrop<T> {
323 impl<T> Default for ManuallyDrop<T> {
324 fn default() -> Self {