1 //! **arrayvec** provides the types `ArrayVec` and `ArrayString`:
2 //! array-backed vector and string types, which store their contents inline.
3 //!
4 //! The arrayvec package has the following cargo features:
5 //!
6 //! - `std`
7 //! - Optional, enabled by default
8 //! - Use libstd; disable to use `no_std` instead.
9 //!
10 //! - `serde`
11 //! - Optional
12 //! - Enable serialization for ArrayVec and ArrayString using serde 1.x
13 //! - `array-sizes-33-128`, `array-sizes-129-255`
14 //! - Optional
15 //! - Enable more array sizes (see [Array] for more information)
16 //!
17 //! ## Rust Version
18 //!
19 //! This version of arrayvec requires Rust 1.36 or later.
20 //!
21 #![doc(html_root_url="https://docs.rs/arrayvec/0.4/")]
22 #![cfg_attr(not(feature="std"), no_std)]
23
24 #[cfg(feature="serde")]
25 extern crate serde;
26
27 #[cfg(not(feature="std"))]
28 extern crate core as std;
29
30 use std::cmp;
31 use std::iter;
32 use std::mem;
33 use std::ops::{Bound, Deref, DerefMut, RangeBounds};
34 use std::ptr;
35 use std::slice;
36
37 // extra traits
38 use std::borrow::{Borrow, BorrowMut};
39 use std::hash::{Hash, Hasher};
40 use std::fmt;
41
42 #[cfg(feature="std")]
43 use std::io;
44
45
46 mod maybe_uninit;
47 use crate::maybe_uninit::MaybeUninit;
48
49 #[cfg(feature="serde")]
50 use serde::{Serialize, Deserialize, Serializer, Deserializer};
51
52 mod array;
53 mod array_string;
54 mod char;
55 mod errors;
56
57 pub use crate::array::Array;
58 use crate::array::Index;
59 pub use crate::array_string::ArrayString;
60 pub use crate::errors::CapacityError;
61
62
63 /// A vector with a fixed capacity.
64 ///
65 /// The `ArrayVec` is a vector backed by a fixed size array. It keeps track of
66 /// the number of initialized elements.
67 ///
68 /// The vector is a contiguous value that you can store directly on the stack
69 /// if needed.
70 ///
71 /// It offers a simple API but also dereferences to a slice, so
72 /// that the full slice API is available.
73 ///
74 /// ArrayVec can be converted into a by value iterator.
75 pub struct ArrayVec<A: Array> {
76 xs: MaybeUninit<A>,
77 len: A::Index,
78 }
79
80 impl<A: Array> Drop for ArrayVec<A> {
drop(&mut self)81 fn drop(&mut self) {
82 self.clear();
83
84 // NoDrop inhibits array's drop
85 // panic safety: NoDrop::drop will trigger on panic, so the inner
86 // array will not drop even after panic.
87 }
88 }
89
90 macro_rules! panic_oob {
91 ($method_name:expr, $index:expr, $len:expr) => {
92 panic!(concat!("ArrayVec::", $method_name, ": index {} is out of bounds in vector of length {}"),
93 $index, $len)
94 }
95 }
96
97 impl<A: Array> ArrayVec<A> {
98 /// Create a new empty `ArrayVec`.
99 ///
100 /// Capacity is inferred from the type parameter.
101 ///
102 /// ```
103 /// use arrayvec::ArrayVec;
104 ///
105 /// let mut array = ArrayVec::<[_; 16]>::new();
106 /// array.push(1);
107 /// array.push(2);
108 /// assert_eq!(&array[..], &[1, 2]);
109 /// assert_eq!(array.capacity(), 16);
110 /// ```
new() -> ArrayVec<A>111 pub fn new() -> ArrayVec<A> {
112 unsafe {
113 ArrayVec { xs: MaybeUninit::uninitialized(), len: Index::from(0) }
114 }
115 }
116
117 /// Return the number of elements in the `ArrayVec`.
118 ///
119 /// ```
120 /// use arrayvec::ArrayVec;
121 ///
122 /// let mut array = ArrayVec::from([1, 2, 3]);
123 /// array.pop();
124 /// assert_eq!(array.len(), 2);
125 /// ```
126 #[inline]
len(&self) -> usize127 pub fn len(&self) -> usize { self.len.to_usize() }
128
129 /// Return the capacity of the `ArrayVec`.
130 ///
131 /// ```
132 /// use arrayvec::ArrayVec;
133 ///
134 /// let array = ArrayVec::from([1, 2, 3]);
135 /// assert_eq!(array.capacity(), 3);
136 /// ```
137 #[inline(always)]
capacity(&self) -> usize138 pub fn capacity(&self) -> usize { A::CAPACITY }
139
140 /// Return if the `ArrayVec` is completely filled.
141 ///
142 /// ```
143 /// use arrayvec::ArrayVec;
144 ///
145 /// let mut array = ArrayVec::<[_; 1]>::new();
146 /// assert!(!array.is_full());
147 /// array.push(1);
148 /// assert!(array.is_full());
149 /// ```
is_full(&self) -> bool150 pub fn is_full(&self) -> bool { self.len() == self.capacity() }
151
152 /// Returns the capacity left in the `ArrayVec`.
153 ///
154 /// ```
155 /// use arrayvec::ArrayVec;
156 ///
157 /// let mut array = ArrayVec::from([1, 2, 3]);
158 /// array.pop();
159 /// assert_eq!(array.remaining_capacity(), 1);
160 /// ```
remaining_capacity(&self) -> usize161 pub fn remaining_capacity(&self) -> usize {
162 self.capacity() - self.len()
163 }
164
165 /// Push `element` to the end of the vector.
166 ///
167 /// ***Panics*** if the vector is already full.
168 ///
169 /// ```
170 /// use arrayvec::ArrayVec;
171 ///
172 /// let mut array = ArrayVec::<[_; 2]>::new();
173 ///
174 /// array.push(1);
175 /// array.push(2);
176 ///
177 /// assert_eq!(&array[..], &[1, 2]);
178 /// ```
push(&mut self, element: A::Item)179 pub fn push(&mut self, element: A::Item) {
180 self.try_push(element).unwrap()
181 }
182
183 /// Push `element` to the end of the vector.
184 ///
185 /// Return `Ok` if the push succeeds, or return an error if the vector
186 /// is already full.
187 ///
188 /// ```
189 /// use arrayvec::ArrayVec;
190 ///
191 /// let mut array = ArrayVec::<[_; 2]>::new();
192 ///
193 /// let push1 = array.try_push(1);
194 /// let push2 = array.try_push(2);
195 ///
196 /// assert!(push1.is_ok());
197 /// assert!(push2.is_ok());
198 ///
199 /// assert_eq!(&array[..], &[1, 2]);
200 ///
201 /// let overflow = array.try_push(3);
202 ///
203 /// assert!(overflow.is_err());
204 /// ```
try_push(&mut self, element: A::Item) -> Result<(), CapacityError<A::Item>>205 pub fn try_push(&mut self, element: A::Item) -> Result<(), CapacityError<A::Item>> {
206 if self.len() < A::CAPACITY {
207 unsafe {
208 self.push_unchecked(element);
209 }
210 Ok(())
211 } else {
212 Err(CapacityError::new(element))
213 }
214 }
215
216
217 /// Push `element` to the end of the vector without checking the capacity.
218 ///
219 /// It is up to the caller to ensure the capacity of the vector is
220 /// sufficiently large.
221 ///
222 /// This method uses *debug assertions* to check that the arrayvec is not full.
223 ///
224 /// ```
225 /// use arrayvec::ArrayVec;
226 ///
227 /// let mut array = ArrayVec::<[_; 2]>::new();
228 ///
229 /// if array.len() + 2 <= array.capacity() {
230 /// unsafe {
231 /// array.push_unchecked(1);
232 /// array.push_unchecked(2);
233 /// }
234 /// }
235 ///
236 /// assert_eq!(&array[..], &[1, 2]);
237 /// ```
push_unchecked(&mut self, element: A::Item)238 pub unsafe fn push_unchecked(&mut self, element: A::Item) {
239 let len = self.len();
240 debug_assert!(len < A::CAPACITY);
241 ptr::write(self.get_unchecked_ptr(len), element);
242 self.set_len(len + 1);
243 }
244
245 /// Get pointer to where element at `index` would be
get_unchecked_ptr(&mut self, index: usize) -> *mut A::Item246 unsafe fn get_unchecked_ptr(&mut self, index: usize) -> *mut A::Item {
247 self.xs.ptr_mut().add(index)
248 }
249
250 /// Insert `element` at position `index`.
251 ///
252 /// Shift up all elements after `index`.
253 ///
254 /// It is an error if the index is greater than the length or if the
255 /// arrayvec is full.
256 ///
257 /// ***Panics*** if the array is full or the `index` is out of bounds. See
258 /// `try_insert` for fallible version.
259 ///
260 /// ```
261 /// use arrayvec::ArrayVec;
262 ///
263 /// let mut array = ArrayVec::<[_; 2]>::new();
264 ///
265 /// array.insert(0, "x");
266 /// array.insert(0, "y");
267 /// assert_eq!(&array[..], &["y", "x"]);
268 ///
269 /// ```
insert(&mut self, index: usize, element: A::Item)270 pub fn insert(&mut self, index: usize, element: A::Item) {
271 self.try_insert(index, element).unwrap()
272 }
273
274 /// Insert `element` at position `index`.
275 ///
276 /// Shift up all elements after `index`; the `index` must be less than
277 /// or equal to the length.
278 ///
279 /// Returns an error if vector is already at full capacity.
280 ///
281 /// ***Panics*** `index` is out of bounds.
282 ///
283 /// ```
284 /// use arrayvec::ArrayVec;
285 ///
286 /// let mut array = ArrayVec::<[_; 2]>::new();
287 ///
288 /// assert!(array.try_insert(0, "x").is_ok());
289 /// assert!(array.try_insert(0, "y").is_ok());
290 /// assert!(array.try_insert(0, "z").is_err());
291 /// assert_eq!(&array[..], &["y", "x"]);
292 ///
293 /// ```
try_insert(&mut self, index: usize, element: A::Item) -> Result<(), CapacityError<A::Item>>294 pub fn try_insert(&mut self, index: usize, element: A::Item) -> Result<(), CapacityError<A::Item>> {
295 if index > self.len() {
296 panic_oob!("try_insert", index, self.len())
297 }
298 if self.len() == self.capacity() {
299 return Err(CapacityError::new(element));
300 }
301 let len = self.len();
302
303 // follows is just like Vec<T>
304 unsafe { // infallible
305 // The spot to put the new value
306 {
307 let p: *mut _ = self.get_unchecked_ptr(index);
308 // Shift everything over to make space. (Duplicating the
309 // `index`th element into two consecutive places.)
310 ptr::copy(p, p.offset(1), len - index);
311 // Write it in, overwriting the first copy of the `index`th
312 // element.
313 ptr::write(p, element);
314 }
315 self.set_len(len + 1);
316 }
317 Ok(())
318 }
319
320 /// Remove the last element in the vector and return it.
321 ///
322 /// Return `Some(` *element* `)` if the vector is non-empty, else `None`.
323 ///
324 /// ```
325 /// use arrayvec::ArrayVec;
326 ///
327 /// let mut array = ArrayVec::<[_; 2]>::new();
328 ///
329 /// array.push(1);
330 ///
331 /// assert_eq!(array.pop(), Some(1));
332 /// assert_eq!(array.pop(), None);
333 /// ```
pop(&mut self) -> Option<A::Item>334 pub fn pop(&mut self) -> Option<A::Item> {
335 if self.len() == 0 {
336 return None;
337 }
338 unsafe {
339 let new_len = self.len() - 1;
340 self.set_len(new_len);
341 Some(ptr::read(self.get_unchecked_ptr(new_len)))
342 }
343 }
344
345 /// Remove the element at `index` and swap the last element into its place.
346 ///
347 /// This operation is O(1).
348 ///
349 /// Return the *element* if the index is in bounds, else panic.
350 ///
351 /// ***Panics*** if the `index` is out of bounds.
352 ///
353 /// ```
354 /// use arrayvec::ArrayVec;
355 ///
356 /// let mut array = ArrayVec::from([1, 2, 3]);
357 ///
358 /// assert_eq!(array.swap_remove(0), 1);
359 /// assert_eq!(&array[..], &[3, 2]);
360 ///
361 /// assert_eq!(array.swap_remove(1), 2);
362 /// assert_eq!(&array[..], &[3]);
363 /// ```
swap_remove(&mut self, index: usize) -> A::Item364 pub fn swap_remove(&mut self, index: usize) -> A::Item {
365 self.swap_pop(index)
366 .unwrap_or_else(|| {
367 panic_oob!("swap_remove", index, self.len())
368 })
369 }
370
371 /// Remove the element at `index` and swap the last element into its place.
372 ///
373 /// This is a checked version of `.swap_remove`.
374 /// This operation is O(1).
375 ///
376 /// Return `Some(` *element* `)` if the index is in bounds, else `None`.
377 ///
378 /// ```
379 /// use arrayvec::ArrayVec;
380 ///
381 /// let mut array = ArrayVec::from([1, 2, 3]);
382 ///
383 /// assert_eq!(array.swap_pop(0), Some(1));
384 /// assert_eq!(&array[..], &[3, 2]);
385 ///
386 /// assert_eq!(array.swap_pop(10), None);
387 /// ```
swap_pop(&mut self, index: usize) -> Option<A::Item>388 pub fn swap_pop(&mut self, index: usize) -> Option<A::Item> {
389 let len = self.len();
390 if index >= len {
391 return None;
392 }
393 self.swap(index, len - 1);
394 self.pop()
395 }
396
397 /// Remove the element at `index` and shift down the following elements.
398 ///
399 /// The `index` must be strictly less than the length of the vector.
400 ///
401 /// ***Panics*** if the `index` is out of bounds.
402 ///
403 /// ```
404 /// use arrayvec::ArrayVec;
405 ///
406 /// let mut array = ArrayVec::from([1, 2, 3]);
407 ///
408 /// let removed_elt = array.remove(0);
409 /// assert_eq!(removed_elt, 1);
410 /// assert_eq!(&array[..], &[2, 3]);
411 /// ```
remove(&mut self, index: usize) -> A::Item412 pub fn remove(&mut self, index: usize) -> A::Item {
413 self.pop_at(index)
414 .unwrap_or_else(|| {
415 panic_oob!("remove", index, self.len())
416 })
417 }
418
419 /// Remove the element at `index` and shift down the following elements.
420 ///
421 /// This is a checked version of `.remove(index)`. Returns `None` if there
422 /// is no element at `index`. Otherwise, return the element inside `Some`.
423 ///
424 /// ```
425 /// use arrayvec::ArrayVec;
426 ///
427 /// let mut array = ArrayVec::from([1, 2, 3]);
428 ///
429 /// assert!(array.pop_at(0).is_some());
430 /// assert_eq!(&array[..], &[2, 3]);
431 ///
432 /// assert!(array.pop_at(2).is_none());
433 /// assert!(array.pop_at(10).is_none());
434 /// ```
pop_at(&mut self, index: usize) -> Option<A::Item>435 pub fn pop_at(&mut self, index: usize) -> Option<A::Item> {
436 if index >= self.len() {
437 None
438 } else {
439 self.drain(index..index + 1).next()
440 }
441 }
442
443 /// Shortens the vector, keeping the first `len` elements and dropping
444 /// the rest.
445 ///
446 /// If `len` is greater than the vector’s current length this has no
447 /// effect.
448 ///
449 /// ```
450 /// use arrayvec::ArrayVec;
451 ///
452 /// let mut array = ArrayVec::from([1, 2, 3, 4, 5]);
453 /// array.truncate(3);
454 /// assert_eq!(&array[..], &[1, 2, 3]);
455 /// array.truncate(4);
456 /// assert_eq!(&array[..], &[1, 2, 3]);
457 /// ```
truncate(&mut self, new_len: usize)458 pub fn truncate(&mut self, new_len: usize) {
459 unsafe {
460 if new_len < self.len() {
461 let tail: *mut [_] = &mut self[new_len..];
462 self.len = Index::from(new_len);
463 ptr::drop_in_place(tail);
464 }
465 }
466 }
467
468 /// Remove all elements in the vector.
clear(&mut self)469 pub fn clear(&mut self) {
470 self.truncate(0)
471 }
472
473 /// Retains only the elements specified by the predicate.
474 ///
475 /// In other words, remove all elements `e` such that `f(&mut e)` returns false.
476 /// This method operates in place and preserves the order of the retained
477 /// elements.
478 ///
479 /// ```
480 /// use arrayvec::ArrayVec;
481 ///
482 /// let mut array = ArrayVec::from([1, 2, 3, 4]);
483 /// array.retain(|x| *x & 1 != 0 );
484 /// assert_eq!(&array[..], &[1, 3]);
485 /// ```
retain<F>(&mut self, mut f: F) where F: FnMut(&mut A::Item) -> bool486 pub fn retain<F>(&mut self, mut f: F)
487 where F: FnMut(&mut A::Item) -> bool
488 {
489 let len = self.len();
490 let mut del = 0;
491 {
492 let v = &mut **self;
493
494 for i in 0..len {
495 if !f(&mut v[i]) {
496 del += 1;
497 } else if del > 0 {
498 v.swap(i - del, i);
499 }
500 }
501 }
502 if del > 0 {
503 self.drain(len - del..);
504 }
505 }
506
507 /// Set the vector’s length without dropping or moving out elements
508 ///
509 /// This method is `unsafe` because it changes the notion of the
510 /// number of “valid” elements in the vector. Use with care.
511 ///
512 /// This method uses *debug assertions* to check that `length` is
513 /// not greater than the capacity.
set_len(&mut self, length: usize)514 pub unsafe fn set_len(&mut self, length: usize) {
515 debug_assert!(length <= self.capacity());
516 self.len = Index::from(length);
517 }
518
519 /// Copy and appends all elements in a slice to the `ArrayVec`.
520 ///
521 /// ```
522 /// use arrayvec::ArrayVec;
523 ///
524 /// let mut vec: ArrayVec<[usize; 10]> = ArrayVec::new();
525 /// vec.push(1);
526 /// vec.try_extend_from_slice(&[2, 3]).unwrap();
527 /// assert_eq!(&vec[..], &[1, 2, 3]);
528 /// ```
529 ///
530 /// # Errors
531 ///
532 /// This method will return an error if the capacity left (see
533 /// [`remaining_capacity`]) is smaller then the length of the provided
534 /// slice.
535 ///
536 /// [`remaining_capacity`]: #method.remaining_capacity
try_extend_from_slice(&mut self, other: &[A::Item]) -> Result<(), CapacityError> where A::Item: Copy,537 pub fn try_extend_from_slice(&mut self, other: &[A::Item]) -> Result<(), CapacityError>
538 where A::Item: Copy,
539 {
540 if self.remaining_capacity() < other.len() {
541 return Err(CapacityError::new(()));
542 }
543
544 let self_len = self.len();
545 let other_len = other.len();
546
547 unsafe {
548 let dst = self.xs.ptr_mut().offset(self_len as isize);
549 ptr::copy_nonoverlapping(other.as_ptr(), dst, other_len);
550 self.set_len(self_len + other_len);
551 }
552 Ok(())
553 }
554
555 /// Create a draining iterator that removes the specified range in the vector
556 /// and yields the removed items from start to end. The element range is
557 /// removed even if the iterator is not consumed until the end.
558 ///
559 /// Note: It is unspecified how many elements are removed from the vector,
560 /// if the `Drain` value is leaked.
561 ///
562 /// **Panics** if the starting point is greater than the end point or if
563 /// the end point is greater than the length of the vector.
564 ///
565 /// ```
566 /// use arrayvec::ArrayVec;
567 ///
568 /// let mut v = ArrayVec::from([1, 2, 3]);
569 /// let u: ArrayVec<[_; 3]> = v.drain(0..2).collect();
570 /// assert_eq!(&v[..], &[3]);
571 /// assert_eq!(&u[..], &[1, 2]);
572 /// ```
drain<R>(&mut self, range: R) -> Drain<A> where R: RangeBounds<usize>573 pub fn drain<R>(&mut self, range: R) -> Drain<A>
574 where R: RangeBounds<usize>
575 {
576 // Memory safety
577 //
578 // When the Drain is first created, it shortens the length of
579 // the source vector to make sure no uninitialized or moved-from elements
580 // are accessible at all if the Drain's destructor never gets to run.
581 //
582 // Drain will ptr::read out the values to remove.
583 // When finished, remaining tail of the vec is copied back to cover
584 // the hole, and the vector length is restored to the new length.
585 //
586 let len = self.len();
587 let start = match range.start_bound() {
588 Bound::Unbounded => 0,
589 Bound::Included(&i) => i,
590 Bound::Excluded(&i) => i.saturating_add(1),
591 };
592 let end = match range.end_bound() {
593 Bound::Excluded(&j) => j,
594 Bound::Included(&j) => j.saturating_add(1),
595 Bound::Unbounded => len,
596 };
597 self.drain_range(start, end)
598 }
599
drain_range(&mut self, start: usize, end: usize) -> Drain<A>600 fn drain_range(&mut self, start: usize, end: usize) -> Drain<A>
601 {
602 let len = self.len();
603 // bounds check happens here
604 let range_slice: *const _ = &self[start..end];
605
606 unsafe {
607 // set self.vec length's to start, to be safe in case Drain is leaked
608 self.set_len(start);
609 Drain {
610 tail_start: end,
611 tail_len: len - end,
612 iter: (*range_slice).iter(),
613 vec: self as *mut _,
614 }
615 }
616 }
617
618 /// Return the inner fixed size array, if it is full to its capacity.
619 ///
620 /// Return an `Ok` value with the array if length equals capacity,
621 /// return an `Err` with self otherwise.
into_inner(self) -> Result<A, Self>622 pub fn into_inner(self) -> Result<A, Self> {
623 if self.len() < self.capacity() {
624 Err(self)
625 } else {
626 unsafe {
627 let array = ptr::read(self.xs.ptr() as *const A);
628 mem::forget(self);
629 Ok(array)
630 }
631 }
632 }
633
634 /// Dispose of `self` (same as drop)
635 #[deprecated="Use std::mem::drop instead, if at all needed."]
dispose(mut self)636 pub fn dispose(mut self) {
637 self.clear();
638 mem::forget(self);
639 }
640
641 /// Return a slice containing all elements of the vector.
as_slice(&self) -> &[A::Item]642 pub fn as_slice(&self) -> &[A::Item] {
643 self
644 }
645
646 /// Return a mutable slice containing all elements of the vector.
as_mut_slice(&mut self) -> &mut [A::Item]647 pub fn as_mut_slice(&mut self) -> &mut [A::Item] {
648 self
649 }
650
651 /// Return a raw pointer to the vector's buffer.
as_ptr(&self) -> *const A::Item652 pub fn as_ptr(&self) -> *const A::Item {
653 self.xs.ptr()
654 }
655
656 /// Return a raw mutable pointer to the vector's buffer.
as_mut_ptr(&mut self) -> *mut A::Item657 pub fn as_mut_ptr(&mut self) -> *mut A::Item {
658 self.xs.ptr_mut()
659 }
660 }
661
662 impl<A: Array> Deref for ArrayVec<A> {
663 type Target = [A::Item];
664 #[inline]
deref(&self) -> &[A::Item]665 fn deref(&self) -> &[A::Item] {
666 unsafe {
667 slice::from_raw_parts(self.xs.ptr(), self.len())
668 }
669 }
670 }
671
672 impl<A: Array> DerefMut for ArrayVec<A> {
673 #[inline]
deref_mut(&mut self) -> &mut [A::Item]674 fn deref_mut(&mut self) -> &mut [A::Item] {
675 let len = self.len();
676 unsafe {
677 slice::from_raw_parts_mut(self.xs.ptr_mut(), len)
678 }
679 }
680 }
681
682 /// Create an `ArrayVec` from an array.
683 ///
684 /// ```
685 /// use arrayvec::ArrayVec;
686 ///
687 /// let mut array = ArrayVec::from([1, 2, 3]);
688 /// assert_eq!(array.len(), 3);
689 /// assert_eq!(array.capacity(), 3);
690 /// ```
691 impl<A: Array> From<A> for ArrayVec<A> {
from(array: A) -> Self692 fn from(array: A) -> Self {
693 ArrayVec { xs: MaybeUninit::from(array), len: Index::from(A::CAPACITY) }
694 }
695 }
696
697
698 /// Iterate the `ArrayVec` with references to each element.
699 ///
700 /// ```
701 /// use arrayvec::ArrayVec;
702 ///
703 /// let array = ArrayVec::from([1, 2, 3]);
704 ///
705 /// for elt in &array {
706 /// // ...
707 /// }
708 /// ```
709 impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> {
710 type Item = &'a A::Item;
711 type IntoIter = slice::Iter<'a, A::Item>;
into_iter(self) -> Self::IntoIter712 fn into_iter(self) -> Self::IntoIter { self.iter() }
713 }
714
715 /// Iterate the `ArrayVec` with mutable references to each element.
716 ///
717 /// ```
718 /// use arrayvec::ArrayVec;
719 ///
720 /// let mut array = ArrayVec::from([1, 2, 3]);
721 ///
722 /// for elt in &mut array {
723 /// // ...
724 /// }
725 /// ```
726 impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> {
727 type Item = &'a mut A::Item;
728 type IntoIter = slice::IterMut<'a, A::Item>;
into_iter(self) -> Self::IntoIter729 fn into_iter(self) -> Self::IntoIter { self.iter_mut() }
730 }
731
732 /// Iterate the `ArrayVec` with each element by value.
733 ///
734 /// The vector is consumed by this operation.
735 ///
736 /// ```
737 /// use arrayvec::ArrayVec;
738 ///
739 /// for elt in ArrayVec::from([1, 2, 3]) {
740 /// // ...
741 /// }
742 /// ```
743 impl<A: Array> IntoIterator for ArrayVec<A> {
744 type Item = A::Item;
745 type IntoIter = IntoIter<A>;
into_iter(self) -> IntoIter<A>746 fn into_iter(self) -> IntoIter<A> {
747 IntoIter { index: Index::from(0), v: self, }
748 }
749 }
750
751
752 /// By-value iterator for `ArrayVec`.
753 pub struct IntoIter<A: Array> {
754 index: A::Index,
755 v: ArrayVec<A>,
756 }
757
758 impl<A: Array> Iterator for IntoIter<A> {
759 type Item = A::Item;
760
next(&mut self) -> Option<A::Item>761 fn next(&mut self) -> Option<A::Item> {
762 if self.index == self.v.len {
763 None
764 } else {
765 unsafe {
766 let index = self.index.to_usize();
767 self.index = Index::from(index + 1);
768 Some(ptr::read(self.v.get_unchecked_ptr(index)))
769 }
770 }
771 }
772
size_hint(&self) -> (usize, Option<usize>)773 fn size_hint(&self) -> (usize, Option<usize>) {
774 let len = self.v.len() - self.index.to_usize();
775 (len, Some(len))
776 }
777 }
778
779 impl<A: Array> DoubleEndedIterator for IntoIter<A> {
next_back(&mut self) -> Option<A::Item>780 fn next_back(&mut self) -> Option<A::Item> {
781 if self.index == self.v.len {
782 None
783 } else {
784 unsafe {
785 let new_len = self.v.len() - 1;
786 self.v.set_len(new_len);
787 Some(ptr::read(self.v.get_unchecked_ptr(new_len)))
788 }
789 }
790 }
791 }
792
793 impl<A: Array> ExactSizeIterator for IntoIter<A> { }
794
795 impl<A: Array> Drop for IntoIter<A> {
drop(&mut self)796 fn drop(&mut self) {
797 // panic safety: Set length to 0 before dropping elements.
798 let index = self.index.to_usize();
799 let len = self.v.len();
800 unsafe {
801 self.v.set_len(0);
802 let elements = slice::from_raw_parts_mut(
803 self.v.get_unchecked_ptr(index),
804 len - index);
805 ptr::drop_in_place(elements);
806 }
807 }
808 }
809
810 impl<A: Array> Clone for IntoIter<A>
811 where
812 A::Item: Clone,
813 {
clone(&self) -> IntoIter<A>814 fn clone(&self) -> IntoIter<A> {
815 self.v[self.index.to_usize()..]
816 .iter()
817 .cloned()
818 .collect::<ArrayVec<A>>()
819 .into_iter()
820 }
821 }
822
823 impl<A: Array> fmt::Debug for IntoIter<A>
824 where
825 A::Item: fmt::Debug,
826 {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result827 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
828 f.debug_list()
829 .entries(&self.v[self.index.to_usize()..])
830 .finish()
831 }
832 }
833
834 /// A draining iterator for `ArrayVec`.
835 pub struct Drain<'a, A>
836 where A: Array,
837 A::Item: 'a,
838 {
839 /// Index of tail to preserve
840 tail_start: usize,
841 /// Length of tail
842 tail_len: usize,
843 /// Current remaining range to remove
844 iter: slice::Iter<'a, A::Item>,
845 vec: *mut ArrayVec<A>,
846 }
847
848 unsafe impl<'a, A: Array + Sync> Sync for Drain<'a, A> {}
849 unsafe impl<'a, A: Array + Send> Send for Drain<'a, A> {}
850
851 impl<'a, A: Array> Iterator for Drain<'a, A>
852 where A::Item: 'a,
853 {
854 type Item = A::Item;
855
next(&mut self) -> Option<Self::Item>856 fn next(&mut self) -> Option<Self::Item> {
857 self.iter.next().map(|elt|
858 unsafe {
859 ptr::read(elt as *const _)
860 }
861 )
862 }
863
size_hint(&self) -> (usize, Option<usize>)864 fn size_hint(&self) -> (usize, Option<usize>) {
865 self.iter.size_hint()
866 }
867 }
868
869 impl<'a, A: Array> DoubleEndedIterator for Drain<'a, A>
870 where A::Item: 'a,
871 {
next_back(&mut self) -> Option<Self::Item>872 fn next_back(&mut self) -> Option<Self::Item> {
873 self.iter.next_back().map(|elt|
874 unsafe {
875 ptr::read(elt as *const _)
876 }
877 )
878 }
879 }
880
881 impl<'a, A: Array> ExactSizeIterator for Drain<'a, A> where A::Item: 'a {}
882
883 impl<'a, A: Array> Drop for Drain<'a, A>
884 where A::Item: 'a
885 {
drop(&mut self)886 fn drop(&mut self) {
887 // len is currently 0 so panicking while dropping will not cause a double drop.
888
889 // exhaust self first
890 while let Some(_) = self.next() { }
891
892 if self.tail_len > 0 {
893 unsafe {
894 let source_vec = &mut *self.vec;
895 // memmove back untouched tail, update to new length
896 let start = source_vec.len();
897 let tail = self.tail_start;
898 let src = source_vec.as_ptr().offset(tail as isize);
899 let dst = source_vec.as_mut_ptr().offset(start as isize);
900 ptr::copy(src, dst, self.tail_len);
901 source_vec.set_len(start + self.tail_len);
902 }
903 }
904 }
905 }
906
907 struct ScopeExitGuard<T, Data, F>
908 where F: FnMut(&Data, &mut T)
909 {
910 value: T,
911 data: Data,
912 f: F,
913 }
914
915 impl<T, Data, F> Drop for ScopeExitGuard<T, Data, F>
916 where F: FnMut(&Data, &mut T)
917 {
drop(&mut self)918 fn drop(&mut self) {
919 (self.f)(&self.data, &mut self.value)
920 }
921 }
922
923
924
925 /// Extend the `ArrayVec` with an iterator.
926 ///
927 /// Does not extract more items than there is space for. No error
928 /// occurs if there are more iterator elements.
929 impl<A: Array> Extend<A::Item> for ArrayVec<A> {
extend<T: IntoIterator<Item=A::Item>>(&mut self, iter: T)930 fn extend<T: IntoIterator<Item=A::Item>>(&mut self, iter: T) {
931 let take = self.capacity() - self.len();
932 unsafe {
933 let len = self.len();
934 let mut ptr = raw_ptr_add(self.as_mut_ptr(), len);
935 let end_ptr = raw_ptr_add(ptr, take);
936 // Keep the length in a separate variable, write it back on scope
937 // exit. To help the compiler with alias analysis and stuff.
938 // We update the length to handle panic in the iteration of the
939 // user's iterator, without dropping any elements on the floor.
940 let mut guard = ScopeExitGuard {
941 value: &mut self.len,
942 data: len,
943 f: move |&len, self_len| {
944 **self_len = Index::from(len);
945 }
946 };
947 let mut iter = iter.into_iter();
948 loop {
949 if ptr == end_ptr { break; }
950 if let Some(elt) = iter.next() {
951 raw_ptr_write(ptr, elt);
952 ptr = raw_ptr_add(ptr, 1);
953 guard.data += 1;
954 } else {
955 break;
956 }
957 }
958 }
959 }
960 }
961
962 /// Rawptr add but uses arithmetic distance for ZST
raw_ptr_add<T>(ptr: *mut T, offset: usize) -> *mut T963 unsafe fn raw_ptr_add<T>(ptr: *mut T, offset: usize) -> *mut T {
964 if mem::size_of::<T>() == 0 {
965 // Special case for ZST
966 (ptr as usize).wrapping_add(offset) as _
967 } else {
968 ptr.offset(offset as isize)
969 }
970 }
971
raw_ptr_write<T>(ptr: *mut T, value: T)972 unsafe fn raw_ptr_write<T>(ptr: *mut T, value: T) {
973 if mem::size_of::<T>() == 0 {
974 /* nothing */
975 } else {
976 ptr::write(ptr, value)
977 }
978 }
979
980 /// Create an `ArrayVec` from an iterator.
981 ///
982 /// Does not extract more items than there is space for. No error
983 /// occurs if there are more iterator elements.
984 impl<A: Array> iter::FromIterator<A::Item> for ArrayVec<A> {
from_iter<T: IntoIterator<Item=A::Item>>(iter: T) -> Self985 fn from_iter<T: IntoIterator<Item=A::Item>>(iter: T) -> Self {
986 let mut array = ArrayVec::new();
987 array.extend(iter);
988 array
989 }
990 }
991
992 impl<A: Array> Clone for ArrayVec<A>
993 where A::Item: Clone
994 {
clone(&self) -> Self995 fn clone(&self) -> Self {
996 self.iter().cloned().collect()
997 }
998
clone_from(&mut self, rhs: &Self)999 fn clone_from(&mut self, rhs: &Self) {
1000 // recursive case for the common prefix
1001 let prefix = cmp::min(self.len(), rhs.len());
1002 self[..prefix].clone_from_slice(&rhs[..prefix]);
1003
1004 if prefix < self.len() {
1005 // rhs was shorter
1006 for _ in 0..self.len() - prefix {
1007 self.pop();
1008 }
1009 } else {
1010 let rhs_elems = rhs[self.len()..].iter().cloned();
1011 self.extend(rhs_elems);
1012 }
1013 }
1014 }
1015
1016 impl<A: Array> Hash for ArrayVec<A>
1017 where A::Item: Hash
1018 {
hash<H: Hasher>(&self, state: &mut H)1019 fn hash<H: Hasher>(&self, state: &mut H) {
1020 Hash::hash(&**self, state)
1021 }
1022 }
1023
1024 impl<A: Array> PartialEq for ArrayVec<A>
1025 where A::Item: PartialEq
1026 {
eq(&self, other: &Self) -> bool1027 fn eq(&self, other: &Self) -> bool {
1028 **self == **other
1029 }
1030 }
1031
1032 impl<A: Array> PartialEq<[A::Item]> for ArrayVec<A>
1033 where A::Item: PartialEq
1034 {
eq(&self, other: &[A::Item]) -> bool1035 fn eq(&self, other: &[A::Item]) -> bool {
1036 **self == *other
1037 }
1038 }
1039
1040 impl<A: Array> Eq for ArrayVec<A> where A::Item: Eq { }
1041
1042 impl<A: Array> Borrow<[A::Item]> for ArrayVec<A> {
borrow(&self) -> &[A::Item]1043 fn borrow(&self) -> &[A::Item] { self }
1044 }
1045
1046 impl<A: Array> BorrowMut<[A::Item]> for ArrayVec<A> {
borrow_mut(&mut self) -> &mut [A::Item]1047 fn borrow_mut(&mut self) -> &mut [A::Item] { self }
1048 }
1049
1050 impl<A: Array> AsRef<[A::Item]> for ArrayVec<A> {
as_ref(&self) -> &[A::Item]1051 fn as_ref(&self) -> &[A::Item] { self }
1052 }
1053
1054 impl<A: Array> AsMut<[A::Item]> for ArrayVec<A> {
as_mut(&mut self) -> &mut [A::Item]1055 fn as_mut(&mut self) -> &mut [A::Item] { self }
1056 }
1057
1058 impl<A: Array> fmt::Debug for ArrayVec<A> where A::Item: fmt::Debug {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result1059 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { (**self).fmt(f) }
1060 }
1061
1062 impl<A: Array> Default for ArrayVec<A> {
1063 /// Return an empty array
default() -> ArrayVec<A>1064 fn default() -> ArrayVec<A> {
1065 ArrayVec::new()
1066 }
1067 }
1068
1069 impl<A: Array> PartialOrd for ArrayVec<A> where A::Item: PartialOrd {
partial_cmp(&self, other: &ArrayVec<A>) -> Option<cmp::Ordering>1070 fn partial_cmp(&self, other: &ArrayVec<A>) -> Option<cmp::Ordering> {
1071 (**self).partial_cmp(other)
1072 }
1073
lt(&self, other: &Self) -> bool1074 fn lt(&self, other: &Self) -> bool {
1075 (**self).lt(other)
1076 }
1077
le(&self, other: &Self) -> bool1078 fn le(&self, other: &Self) -> bool {
1079 (**self).le(other)
1080 }
1081
ge(&self, other: &Self) -> bool1082 fn ge(&self, other: &Self) -> bool {
1083 (**self).ge(other)
1084 }
1085
gt(&self, other: &Self) -> bool1086 fn gt(&self, other: &Self) -> bool {
1087 (**self).gt(other)
1088 }
1089 }
1090
1091 impl<A: Array> Ord for ArrayVec<A> where A::Item: Ord {
cmp(&self, other: &ArrayVec<A>) -> cmp::Ordering1092 fn cmp(&self, other: &ArrayVec<A>) -> cmp::Ordering {
1093 (**self).cmp(other)
1094 }
1095 }
1096
1097 #[cfg(feature="std")]
1098 /// `Write` appends written data to the end of the vector.
1099 ///
1100 /// Requires `features="std"`.
1101 impl<A: Array<Item=u8>> io::Write for ArrayVec<A> {
write(&mut self, data: &[u8]) -> io::Result<usize>1102 fn write(&mut self, data: &[u8]) -> io::Result<usize> {
1103 let len = cmp::min(self.remaining_capacity(), data.len());
1104 let _result = self.try_extend_from_slice(&data[..len]);
1105 debug_assert!(_result.is_ok());
1106 Ok(len)
1107 }
flush(&mut self) -> io::Result<()>1108 fn flush(&mut self) -> io::Result<()> { Ok(()) }
1109 }
1110
1111 #[cfg(feature="serde")]
1112 /// Requires crate feature `"serde"`
1113 impl<T: Serialize, A: Array<Item=T>> Serialize for ArrayVec<A> {
serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer1114 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1115 where S: Serializer
1116 {
1117 serializer.collect_seq(self)
1118 }
1119 }
1120
1121 #[cfg(feature="serde")]
1122 /// Requires crate feature `"serde"`
1123 impl<'de, T: Deserialize<'de>, A: Array<Item=T>> Deserialize<'de> for ArrayVec<A> {
deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>1124 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1125 where D: Deserializer<'de>
1126 {
1127 use serde::de::{Visitor, SeqAccess, Error};
1128 use std::marker::PhantomData;
1129
1130 struct ArrayVecVisitor<'de, T: Deserialize<'de>, A: Array<Item=T>>(PhantomData<(&'de (), T, A)>);
1131
1132 impl<'de, T: Deserialize<'de>, A: Array<Item=T>> Visitor<'de> for ArrayVecVisitor<'de, T, A> {
1133 type Value = ArrayVec<A>;
1134
1135 fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
1136 write!(formatter, "an array with no more than {} items", A::CAPACITY)
1137 }
1138
1139 fn visit_seq<SA>(self, mut seq: SA) -> Result<Self::Value, SA::Error>
1140 where SA: SeqAccess<'de>,
1141 {
1142 let mut values = ArrayVec::<A>::new();
1143
1144 while let Some(value) = seq.next_element()? {
1145 if let Err(_) = values.try_push(value) {
1146 return Err(SA::Error::invalid_length(A::CAPACITY + 1, &self));
1147 }
1148 }
1149
1150 Ok(values)
1151 }
1152 }
1153
1154 deserializer.deserialize_seq(ArrayVecVisitor::<T, A>(PhantomData))
1155 }
1156 }
1157