1
2 use std::cmp;
3 use std::iter;
4 use std::mem;
5 use std::ops::{Bound, Deref, DerefMut, RangeBounds};
6 use std::ptr;
7 use std::slice;
8
9 // extra traits
10 use std::borrow::{Borrow, BorrowMut};
11 use std::hash::{Hash, Hasher};
12 use std::fmt;
13
14 #[cfg(feature="std")]
15 use std::io;
16
17 use std::mem::ManuallyDrop;
18 use std::mem::MaybeUninit;
19
20 #[cfg(feature="serde")]
21 use serde::{Serialize, Deserialize, Serializer, Deserializer};
22
23 use crate::LenUint;
24 use crate::errors::CapacityError;
25 use crate::arrayvec_impl::ArrayVecImpl;
26 use crate::utils::MakeMaybeUninit;
27
28 /// A vector with a fixed capacity.
29 ///
30 /// The `ArrayVec` is a vector backed by a fixed size array. It keeps track of
31 /// the number of initialized elements. The `ArrayVec<T, CAP>` is parameterized
32 /// by `T` for the element type and `CAP` for the maximum capacity.
33 ///
34 /// `CAP` is of type `usize` but is range limited to `u32::MAX`; attempting to create larger
35 /// arrayvecs with larger capacity will panic.
36 ///
37 /// The vector is a contiguous value (storing the elements inline) that you can store directly on
38 /// the stack if needed.
39 ///
40 /// It offers a simple API but also dereferences to a slice, so that the full slice API is
41 /// available. The ArrayVec can be converted into a by value iterator.
42 pub struct ArrayVec<T, const CAP: usize> {
43 // the `len` first elements of the array are initialized
44 xs: [MaybeUninit<T>; CAP],
45 len: LenUint,
46 }
47
48 impl<T, const CAP: usize> Drop for ArrayVec<T, CAP> {
drop(&mut self)49 fn drop(&mut self) {
50 self.clear();
51
52 // MaybeUninit inhibits array's drop
53 }
54 }
55
56 macro_rules! panic_oob {
57 ($method_name:expr, $index:expr, $len:expr) => {
58 panic!(concat!("ArrayVec::", $method_name, ": index {} is out of bounds in vector of length {}"),
59 $index, $len)
60 }
61 }
62
63 impl<T, const CAP: usize> ArrayVec<T, CAP> {
64 /// Capacity
65 const CAPACITY: usize = CAP;
66
67 /// Create a new empty `ArrayVec`.
68 ///
69 /// The maximum capacity is given by the generic parameter `CAP`.
70 ///
71 /// ```
72 /// use arrayvec::ArrayVec;
73 ///
74 /// let mut array = ArrayVec::<_, 16>::new();
75 /// array.push(1);
76 /// array.push(2);
77 /// assert_eq!(&array[..], &[1, 2]);
78 /// assert_eq!(array.capacity(), 16);
79 /// ```
80 #[inline]
81 #[track_caller]
new() -> ArrayVec<T, CAP>82 pub fn new() -> ArrayVec<T, CAP> {
83 assert_capacity_limit!(CAP);
84 unsafe {
85 ArrayVec { xs: MaybeUninit::uninit().assume_init(), len: 0 }
86 }
87 }
88
89 /// Create a new empty `ArrayVec` (const fn).
90 ///
91 /// The maximum capacity is given by the generic parameter `CAP`.
92 ///
93 /// ```
94 /// use arrayvec::ArrayVec;
95 ///
96 /// static ARRAY: ArrayVec<u8, 1024> = ArrayVec::new_const();
97 /// ```
new_const() -> ArrayVec<T, CAP>98 pub const fn new_const() -> ArrayVec<T, CAP> {
99 assert_capacity_limit_const!(CAP);
100 ArrayVec { xs: MakeMaybeUninit::ARRAY, len: 0 }
101 }
102
103 /// Return the number of elements in the `ArrayVec`.
104 ///
105 /// ```
106 /// use arrayvec::ArrayVec;
107 ///
108 /// let mut array = ArrayVec::from([1, 2, 3]);
109 /// array.pop();
110 /// assert_eq!(array.len(), 2);
111 /// ```
112 #[inline(always)]
len(&self) -> usize113 pub const fn len(&self) -> usize { self.len as usize }
114
115 /// Returns whether the `ArrayVec` is empty.
116 ///
117 /// ```
118 /// use arrayvec::ArrayVec;
119 ///
120 /// let mut array = ArrayVec::from([1]);
121 /// array.pop();
122 /// assert_eq!(array.is_empty(), true);
123 /// ```
124 #[inline]
is_empty(&self) -> bool125 pub const fn is_empty(&self) -> bool { self.len() == 0 }
126
127 /// Return the capacity of the `ArrayVec`.
128 ///
129 /// ```
130 /// use arrayvec::ArrayVec;
131 ///
132 /// let array = ArrayVec::from([1, 2, 3]);
133 /// assert_eq!(array.capacity(), 3);
134 /// ```
135 #[inline(always)]
capacity(&self) -> usize136 pub const fn capacity(&self) -> usize { CAP }
137
138 /// Return true if the `ArrayVec` is completely filled to its capacity, false otherwise.
139 ///
140 /// ```
141 /// use arrayvec::ArrayVec;
142 ///
143 /// let mut array = ArrayVec::<_, 1>::new();
144 /// assert!(!array.is_full());
145 /// array.push(1);
146 /// assert!(array.is_full());
147 /// ```
is_full(&self) -> bool148 pub const fn is_full(&self) -> bool { self.len() == self.capacity() }
149
150 /// Returns the capacity left in the `ArrayVec`.
151 ///
152 /// ```
153 /// use arrayvec::ArrayVec;
154 ///
155 /// let mut array = ArrayVec::from([1, 2, 3]);
156 /// array.pop();
157 /// assert_eq!(array.remaining_capacity(), 1);
158 /// ```
remaining_capacity(&self) -> usize159 pub const fn remaining_capacity(&self) -> usize {
160 self.capacity() - self.len()
161 }
162
163 /// Push `element` to the end of the vector.
164 ///
165 /// ***Panics*** if the vector is already full.
166 ///
167 /// ```
168 /// use arrayvec::ArrayVec;
169 ///
170 /// let mut array = ArrayVec::<_, 2>::new();
171 ///
172 /// array.push(1);
173 /// array.push(2);
174 ///
175 /// assert_eq!(&array[..], &[1, 2]);
176 /// ```
177 #[track_caller]
push(&mut self, element: T)178 pub fn push(&mut self, element: T) {
179 ArrayVecImpl::push(self, element)
180 }
181
182 /// Push `element` to the end of the vector.
183 ///
184 /// Return `Ok` if the push succeeds, or return an error if the vector
185 /// is already full.
186 ///
187 /// ```
188 /// use arrayvec::ArrayVec;
189 ///
190 /// let mut array = ArrayVec::<_, 2>::new();
191 ///
192 /// let push1 = array.try_push(1);
193 /// let push2 = array.try_push(2);
194 ///
195 /// assert!(push1.is_ok());
196 /// assert!(push2.is_ok());
197 ///
198 /// assert_eq!(&array[..], &[1, 2]);
199 ///
200 /// let overflow = array.try_push(3);
201 ///
202 /// assert!(overflow.is_err());
203 /// ```
try_push(&mut self, element: T) -> Result<(), CapacityError<T>>204 pub fn try_push(&mut self, element: T) -> Result<(), CapacityError<T>> {
205 ArrayVecImpl::try_push(self, element)
206 }
207
208 /// Push `element` to the end of the vector without checking the capacity.
209 ///
210 /// It is up to the caller to ensure the capacity of the vector is
211 /// sufficiently large.
212 ///
213 /// This method uses *debug assertions* to check that the arrayvec is not full.
214 ///
215 /// ```
216 /// use arrayvec::ArrayVec;
217 ///
218 /// let mut array = ArrayVec::<_, 2>::new();
219 ///
220 /// if array.len() + 2 <= array.capacity() {
221 /// unsafe {
222 /// array.push_unchecked(1);
223 /// array.push_unchecked(2);
224 /// }
225 /// }
226 ///
227 /// assert_eq!(&array[..], &[1, 2]);
228 /// ```
push_unchecked(&mut self, element: T)229 pub unsafe fn push_unchecked(&mut self, element: T) {
230 ArrayVecImpl::push_unchecked(self, element)
231 }
232
233 /// Shortens the vector, keeping the first `len` elements and dropping
234 /// the rest.
235 ///
236 /// If `len` is greater than the vector’s current length this has no
237 /// effect.
238 ///
239 /// ```
240 /// use arrayvec::ArrayVec;
241 ///
242 /// let mut array = ArrayVec::from([1, 2, 3, 4, 5]);
243 /// array.truncate(3);
244 /// assert_eq!(&array[..], &[1, 2, 3]);
245 /// array.truncate(4);
246 /// assert_eq!(&array[..], &[1, 2, 3]);
247 /// ```
truncate(&mut self, new_len: usize)248 pub fn truncate(&mut self, new_len: usize) {
249 ArrayVecImpl::truncate(self, new_len)
250 }
251
252 /// Remove all elements in the vector.
clear(&mut self)253 pub fn clear(&mut self) {
254 ArrayVecImpl::clear(self)
255 }
256
257
258 /// Get pointer to where element at `index` would be
get_unchecked_ptr(&mut self, index: usize) -> *mut T259 unsafe fn get_unchecked_ptr(&mut self, index: usize) -> *mut T {
260 self.as_mut_ptr().add(index)
261 }
262
263 /// Insert `element` at position `index`.
264 ///
265 /// Shift up all elements after `index`.
266 ///
267 /// It is an error if the index is greater than the length or if the
268 /// arrayvec is full.
269 ///
270 /// ***Panics*** if the array is full or the `index` is out of bounds. See
271 /// `try_insert` for fallible version.
272 ///
273 /// ```
274 /// use arrayvec::ArrayVec;
275 ///
276 /// let mut array = ArrayVec::<_, 2>::new();
277 ///
278 /// array.insert(0, "x");
279 /// array.insert(0, "y");
280 /// assert_eq!(&array[..], &["y", "x"]);
281 ///
282 /// ```
283 #[track_caller]
insert(&mut self, index: usize, element: T)284 pub fn insert(&mut self, index: usize, element: T) {
285 self.try_insert(index, element).unwrap()
286 }
287
288 /// Insert `element` at position `index`.
289 ///
290 /// Shift up all elements after `index`; the `index` must be less than
291 /// or equal to the length.
292 ///
293 /// Returns an error if vector is already at full capacity.
294 ///
295 /// ***Panics*** `index` is out of bounds.
296 ///
297 /// ```
298 /// use arrayvec::ArrayVec;
299 ///
300 /// let mut array = ArrayVec::<_, 2>::new();
301 ///
302 /// assert!(array.try_insert(0, "x").is_ok());
303 /// assert!(array.try_insert(0, "y").is_ok());
304 /// assert!(array.try_insert(0, "z").is_err());
305 /// assert_eq!(&array[..], &["y", "x"]);
306 ///
307 /// ```
try_insert(&mut self, index: usize, element: T) -> Result<(), CapacityError<T>>308 pub fn try_insert(&mut self, index: usize, element: T) -> Result<(), CapacityError<T>> {
309 if index > self.len() {
310 panic_oob!("try_insert", index, self.len())
311 }
312 if self.len() == self.capacity() {
313 return Err(CapacityError::new(element));
314 }
315 let len = self.len();
316
317 // follows is just like Vec<T>
318 unsafe { // infallible
319 // The spot to put the new value
320 {
321 let p: *mut _ = self.get_unchecked_ptr(index);
322 // Shift everything over to make space. (Duplicating the
323 // `index`th element into two consecutive places.)
324 ptr::copy(p, p.offset(1), len - index);
325 // Write it in, overwriting the first copy of the `index`th
326 // element.
327 ptr::write(p, element);
328 }
329 self.set_len(len + 1);
330 }
331 Ok(())
332 }
333
334 /// Remove the last element in the vector and return it.
335 ///
336 /// Return `Some(` *element* `)` if the vector is non-empty, else `None`.
337 ///
338 /// ```
339 /// use arrayvec::ArrayVec;
340 ///
341 /// let mut array = ArrayVec::<_, 2>::new();
342 ///
343 /// array.push(1);
344 ///
345 /// assert_eq!(array.pop(), Some(1));
346 /// assert_eq!(array.pop(), None);
347 /// ```
pop(&mut self) -> Option<T>348 pub fn pop(&mut self) -> Option<T> {
349 ArrayVecImpl::pop(self)
350 }
351
352 /// Remove the element at `index` and swap the last element into its place.
353 ///
354 /// This operation is O(1).
355 ///
356 /// Return the *element* if the index is in bounds, else panic.
357 ///
358 /// ***Panics*** if the `index` is out of bounds.
359 ///
360 /// ```
361 /// use arrayvec::ArrayVec;
362 ///
363 /// let mut array = ArrayVec::from([1, 2, 3]);
364 ///
365 /// assert_eq!(array.swap_remove(0), 1);
366 /// assert_eq!(&array[..], &[3, 2]);
367 ///
368 /// assert_eq!(array.swap_remove(1), 2);
369 /// assert_eq!(&array[..], &[3]);
370 /// ```
swap_remove(&mut self, index: usize) -> T371 pub fn swap_remove(&mut self, index: usize) -> T {
372 self.swap_pop(index)
373 .unwrap_or_else(|| {
374 panic_oob!("swap_remove", index, self.len())
375 })
376 }
377
378 /// Remove the element at `index` and swap the last element into its place.
379 ///
380 /// This is a checked version of `.swap_remove`.
381 /// This operation is O(1).
382 ///
383 /// Return `Some(` *element* `)` if the index is in bounds, else `None`.
384 ///
385 /// ```
386 /// use arrayvec::ArrayVec;
387 ///
388 /// let mut array = ArrayVec::from([1, 2, 3]);
389 ///
390 /// assert_eq!(array.swap_pop(0), Some(1));
391 /// assert_eq!(&array[..], &[3, 2]);
392 ///
393 /// assert_eq!(array.swap_pop(10), None);
394 /// ```
swap_pop(&mut self, index: usize) -> Option<T>395 pub fn swap_pop(&mut self, index: usize) -> Option<T> {
396 let len = self.len();
397 if index >= len {
398 return None;
399 }
400 self.swap(index, len - 1);
401 self.pop()
402 }
403
404 /// Remove the element at `index` and shift down the following elements.
405 ///
406 /// The `index` must be strictly less than the length of the vector.
407 ///
408 /// ***Panics*** if the `index` is out of bounds.
409 ///
410 /// ```
411 /// use arrayvec::ArrayVec;
412 ///
413 /// let mut array = ArrayVec::from([1, 2, 3]);
414 ///
415 /// let removed_elt = array.remove(0);
416 /// assert_eq!(removed_elt, 1);
417 /// assert_eq!(&array[..], &[2, 3]);
418 /// ```
remove(&mut self, index: usize) -> T419 pub fn remove(&mut self, index: usize) -> T {
420 self.pop_at(index)
421 .unwrap_or_else(|| {
422 panic_oob!("remove", index, self.len())
423 })
424 }
425
426 /// Remove the element at `index` and shift down the following elements.
427 ///
428 /// This is a checked version of `.remove(index)`. Returns `None` if there
429 /// is no element at `index`. Otherwise, return the element inside `Some`.
430 ///
431 /// ```
432 /// use arrayvec::ArrayVec;
433 ///
434 /// let mut array = ArrayVec::from([1, 2, 3]);
435 ///
436 /// assert!(array.pop_at(0).is_some());
437 /// assert_eq!(&array[..], &[2, 3]);
438 ///
439 /// assert!(array.pop_at(2).is_none());
440 /// assert!(array.pop_at(10).is_none());
441 /// ```
pop_at(&mut self, index: usize) -> Option<T>442 pub fn pop_at(&mut self, index: usize) -> Option<T> {
443 if index >= self.len() {
444 None
445 } else {
446 self.drain(index..index + 1).next()
447 }
448 }
449
450 /// Retains only the elements specified by the predicate.
451 ///
452 /// In other words, remove all elements `e` such that `f(&mut e)` returns false.
453 /// This method operates in place and preserves the order of the retained
454 /// elements.
455 ///
456 /// ```
457 /// use arrayvec::ArrayVec;
458 ///
459 /// let mut array = ArrayVec::from([1, 2, 3, 4]);
460 /// array.retain(|x| *x & 1 != 0 );
461 /// assert_eq!(&array[..], &[1, 3]);
462 /// ```
retain<F>(&mut self, mut f: F) where F: FnMut(&mut T) -> bool463 pub fn retain<F>(&mut self, mut f: F)
464 where F: FnMut(&mut T) -> bool
465 {
466 // Check the implementation of
467 // https://doc.rust-lang.org/std/vec/struct.Vec.html#method.retain
468 // for safety arguments (especially regarding panics in f and when
469 // dropping elements). Implementation closely mirrored here.
470
471 let original_len = self.len();
472 unsafe { self.set_len(0) };
473
474 struct BackshiftOnDrop<'a, T, const CAP: usize> {
475 v: &'a mut ArrayVec<T, CAP>,
476 processed_len: usize,
477 deleted_cnt: usize,
478 original_len: usize,
479 }
480
481 impl<T, const CAP: usize> Drop for BackshiftOnDrop<'_, T, CAP> {
482 fn drop(&mut self) {
483 if self.deleted_cnt > 0 {
484 unsafe {
485 ptr::copy(
486 self.v.as_ptr().add(self.processed_len),
487 self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt),
488 self.original_len - self.processed_len
489 );
490 }
491 }
492 unsafe {
493 self.v.set_len(self.original_len - self.deleted_cnt);
494 }
495 }
496 }
497
498 let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len };
499
500 #[inline(always)]
501 fn process_one<F: FnMut(&mut T) -> bool, T, const CAP: usize, const DELETED: bool>(
502 f: &mut F,
503 g: &mut BackshiftOnDrop<'_, T, CAP>
504 ) -> bool {
505 let cur = unsafe { g.v.as_mut_ptr().add(g.processed_len) };
506 if !f(unsafe { &mut *cur }) {
507 g.processed_len += 1;
508 g.deleted_cnt += 1;
509 unsafe { ptr::drop_in_place(cur) };
510 return false;
511 }
512 if DELETED {
513 unsafe {
514 let hole_slot = cur.sub(g.deleted_cnt);
515 ptr::copy_nonoverlapping(cur, hole_slot, 1);
516 }
517 }
518 g.processed_len += 1;
519 true
520 }
521
522 // Stage 1: Nothing was deleted.
523 while g.processed_len != original_len {
524 if !process_one::<F, T, CAP, false>(&mut f, &mut g) {
525 break;
526 }
527 }
528
529 // Stage 2: Some elements were deleted.
530 while g.processed_len != original_len {
531 process_one::<F, T, CAP, true>(&mut f, &mut g);
532 }
533
534 drop(g);
535 }
536
537 /// Set the vector’s length without dropping or moving out elements
538 ///
539 /// This method is `unsafe` because it changes the notion of the
540 /// number of “valid” elements in the vector. Use with care.
541 ///
542 /// This method uses *debug assertions* to check that `length` is
543 /// not greater than the capacity.
set_len(&mut self, length: usize)544 pub unsafe fn set_len(&mut self, length: usize) {
545 // type invariant that capacity always fits in LenUint
546 debug_assert!(length <= self.capacity());
547 self.len = length as LenUint;
548 }
549
550 /// Copy all elements from the slice and append to the `ArrayVec`.
551 ///
552 /// ```
553 /// use arrayvec::ArrayVec;
554 ///
555 /// let mut vec: ArrayVec<usize, 10> = ArrayVec::new();
556 /// vec.push(1);
557 /// vec.try_extend_from_slice(&[2, 3]).unwrap();
558 /// assert_eq!(&vec[..], &[1, 2, 3]);
559 /// ```
560 ///
561 /// # Errors
562 ///
563 /// This method will return an error if the capacity left (see
564 /// [`remaining_capacity`]) is smaller then the length of the provided
565 /// slice.
566 ///
567 /// [`remaining_capacity`]: #method.remaining_capacity
try_extend_from_slice(&mut self, other: &[T]) -> Result<(), CapacityError> where T: Copy,568 pub fn try_extend_from_slice(&mut self, other: &[T]) -> Result<(), CapacityError>
569 where T: Copy,
570 {
571 if self.remaining_capacity() < other.len() {
572 return Err(CapacityError::new(()));
573 }
574
575 let self_len = self.len();
576 let other_len = other.len();
577
578 unsafe {
579 let dst = self.get_unchecked_ptr(self_len);
580 ptr::copy_nonoverlapping(other.as_ptr(), dst, other_len);
581 self.set_len(self_len + other_len);
582 }
583 Ok(())
584 }
585
586 /// Create a draining iterator that removes the specified range in the vector
587 /// and yields the removed items from start to end. The element range is
588 /// removed even if the iterator is not consumed until the end.
589 ///
590 /// Note: It is unspecified how many elements are removed from the vector,
591 /// if the `Drain` value is leaked.
592 ///
593 /// **Panics** if the starting point is greater than the end point or if
594 /// the end point is greater than the length of the vector.
595 ///
596 /// ```
597 /// use arrayvec::ArrayVec;
598 ///
599 /// let mut v1 = ArrayVec::from([1, 2, 3]);
600 /// let v2: ArrayVec<_, 3> = v1.drain(0..2).collect();
601 /// assert_eq!(&v1[..], &[3]);
602 /// assert_eq!(&v2[..], &[1, 2]);
603 /// ```
drain<R>(&mut self, range: R) -> Drain<T, CAP> where R: RangeBounds<usize>604 pub fn drain<R>(&mut self, range: R) -> Drain<T, CAP>
605 where R: RangeBounds<usize>
606 {
607 // Memory safety
608 //
609 // When the Drain is first created, it shortens the length of
610 // the source vector to make sure no uninitialized or moved-from elements
611 // are accessible at all if the Drain's destructor never gets to run.
612 //
613 // Drain will ptr::read out the values to remove.
614 // When finished, remaining tail of the vec is copied back to cover
615 // the hole, and the vector length is restored to the new length.
616 //
617 let len = self.len();
618 let start = match range.start_bound() {
619 Bound::Unbounded => 0,
620 Bound::Included(&i) => i,
621 Bound::Excluded(&i) => i.saturating_add(1),
622 };
623 let end = match range.end_bound() {
624 Bound::Excluded(&j) => j,
625 Bound::Included(&j) => j.saturating_add(1),
626 Bound::Unbounded => len,
627 };
628 self.drain_range(start, end)
629 }
630
drain_range(&mut self, start: usize, end: usize) -> Drain<T, CAP>631 fn drain_range(&mut self, start: usize, end: usize) -> Drain<T, CAP>
632 {
633 let len = self.len();
634
635 // bounds check happens here (before length is changed!)
636 let range_slice: *const _ = &self[start..end];
637
638 // Calling `set_len` creates a fresh and thus unique mutable references, making all
639 // older aliases we created invalid. So we cannot call that function.
640 self.len = start as LenUint;
641
642 unsafe {
643 Drain {
644 tail_start: end,
645 tail_len: len - end,
646 iter: (*range_slice).iter(),
647 vec: self as *mut _,
648 }
649 }
650 }
651
652 /// Return the inner fixed size array, if it is full to its capacity.
653 ///
654 /// Return an `Ok` value with the array if length equals capacity,
655 /// return an `Err` with self otherwise.
into_inner(self) -> Result<[T; CAP], Self>656 pub fn into_inner(self) -> Result<[T; CAP], Self> {
657 if self.len() < self.capacity() {
658 Err(self)
659 } else {
660 unsafe { Ok(self.into_inner_unchecked()) }
661 }
662 }
663
664 /// Return the inner fixed size array.
665 ///
666 /// Safety:
667 /// This operation is safe if and only if length equals capacity.
into_inner_unchecked(self) -> [T; CAP]668 pub unsafe fn into_inner_unchecked(self) -> [T; CAP] {
669 debug_assert_eq!(self.len(), self.capacity());
670 let self_ = ManuallyDrop::new(self);
671 let array = ptr::read(self_.as_ptr() as *const [T; CAP]);
672 array
673 }
674
675 /// Returns the ArrayVec, replacing the original with a new empty ArrayVec.
676 ///
677 /// ```
678 /// use arrayvec::ArrayVec;
679 ///
680 /// let mut v = ArrayVec::from([0, 1, 2, 3]);
681 /// assert_eq!([0, 1, 2, 3], v.take().into_inner().unwrap());
682 /// assert!(v.is_empty());
683 /// ```
take(&mut self) -> Self684 pub fn take(&mut self) -> Self {
685 mem::replace(self, Self::new())
686 }
687
688 /// Return a slice containing all elements of the vector.
as_slice(&self) -> &[T]689 pub fn as_slice(&self) -> &[T] {
690 ArrayVecImpl::as_slice(self)
691 }
692
693 /// Return a mutable slice containing all elements of the vector.
as_mut_slice(&mut self) -> &mut [T]694 pub fn as_mut_slice(&mut self) -> &mut [T] {
695 ArrayVecImpl::as_mut_slice(self)
696 }
697
698 /// Return a raw pointer to the vector's buffer.
as_ptr(&self) -> *const T699 pub fn as_ptr(&self) -> *const T {
700 ArrayVecImpl::as_ptr(self)
701 }
702
703 /// Return a raw mutable pointer to the vector's buffer.
as_mut_ptr(&mut self) -> *mut T704 pub fn as_mut_ptr(&mut self) -> *mut T {
705 ArrayVecImpl::as_mut_ptr(self)
706 }
707 }
708
709 impl<T, const CAP: usize> ArrayVecImpl for ArrayVec<T, CAP> {
710 type Item = T;
711 const CAPACITY: usize = CAP;
712
len(&self) -> usize713 fn len(&self) -> usize { self.len() }
714
set_len(&mut self, length: usize)715 unsafe fn set_len(&mut self, length: usize) {
716 debug_assert!(length <= CAP);
717 self.len = length as LenUint;
718 }
719
as_ptr(&self) -> *const Self::Item720 fn as_ptr(&self) -> *const Self::Item {
721 self.xs.as_ptr() as _
722 }
723
as_mut_ptr(&mut self) -> *mut Self::Item724 fn as_mut_ptr(&mut self) -> *mut Self::Item {
725 self.xs.as_mut_ptr() as _
726 }
727 }
728
729 impl<T, const CAP: usize> Deref for ArrayVec<T, CAP> {
730 type Target = [T];
731 #[inline]
deref(&self) -> &Self::Target732 fn deref(&self) -> &Self::Target {
733 self.as_slice()
734 }
735 }
736
737 impl<T, const CAP: usize> DerefMut for ArrayVec<T, CAP> {
738 #[inline]
deref_mut(&mut self) -> &mut Self::Target739 fn deref_mut(&mut self) -> &mut Self::Target {
740 self.as_mut_slice()
741 }
742 }
743
744
745 /// Create an `ArrayVec` from an array.
746 ///
747 /// ```
748 /// use arrayvec::ArrayVec;
749 ///
750 /// let mut array = ArrayVec::from([1, 2, 3]);
751 /// assert_eq!(array.len(), 3);
752 /// assert_eq!(array.capacity(), 3);
753 /// ```
754 impl<T, const CAP: usize> From<[T; CAP]> for ArrayVec<T, CAP> {
755 #[track_caller]
from(array: [T; CAP]) -> Self756 fn from(array: [T; CAP]) -> Self {
757 let array = ManuallyDrop::new(array);
758 let mut vec = <ArrayVec<T, CAP>>::new();
759 unsafe {
760 (&*array as *const [T; CAP] as *const [MaybeUninit<T>; CAP])
761 .copy_to_nonoverlapping(&mut vec.xs as *mut [MaybeUninit<T>; CAP], 1);
762 vec.set_len(CAP);
763 }
764 vec
765 }
766 }
767
768
769 /// Try to create an `ArrayVec` from a slice. This will return an error if the slice was too big to
770 /// fit.
771 ///
772 /// ```
773 /// use arrayvec::ArrayVec;
774 /// use std::convert::TryInto as _;
775 ///
776 /// let array: ArrayVec<_, 4> = (&[1, 2, 3] as &[_]).try_into().unwrap();
777 /// assert_eq!(array.len(), 3);
778 /// assert_eq!(array.capacity(), 4);
779 /// ```
780 impl<T, const CAP: usize> std::convert::TryFrom<&[T]> for ArrayVec<T, CAP>
781 where T: Clone,
782 {
783 type Error = CapacityError;
784
try_from(slice: &[T]) -> Result<Self, Self::Error>785 fn try_from(slice: &[T]) -> Result<Self, Self::Error> {
786 if Self::CAPACITY < slice.len() {
787 Err(CapacityError::new(()))
788 } else {
789 let mut array = Self::new();
790 array.extend_from_slice(slice);
791 Ok(array)
792 }
793 }
794 }
795
796
797 /// Iterate the `ArrayVec` with references to each element.
798 ///
799 /// ```
800 /// use arrayvec::ArrayVec;
801 ///
802 /// let array = ArrayVec::from([1, 2, 3]);
803 ///
804 /// for elt in &array {
805 /// // ...
806 /// }
807 /// ```
808 impl<'a, T: 'a, const CAP: usize> IntoIterator for &'a ArrayVec<T, CAP> {
809 type Item = &'a T;
810 type IntoIter = slice::Iter<'a, T>;
into_iter(self) -> Self::IntoIter811 fn into_iter(self) -> Self::IntoIter { self.iter() }
812 }
813
814 /// Iterate the `ArrayVec` with mutable references to each element.
815 ///
816 /// ```
817 /// use arrayvec::ArrayVec;
818 ///
819 /// let mut array = ArrayVec::from([1, 2, 3]);
820 ///
821 /// for elt in &mut array {
822 /// // ...
823 /// }
824 /// ```
825 impl<'a, T: 'a, const CAP: usize> IntoIterator for &'a mut ArrayVec<T, CAP> {
826 type Item = &'a mut T;
827 type IntoIter = slice::IterMut<'a, T>;
into_iter(self) -> Self::IntoIter828 fn into_iter(self) -> Self::IntoIter { self.iter_mut() }
829 }
830
831 /// Iterate the `ArrayVec` with each element by value.
832 ///
833 /// The vector is consumed by this operation.
834 ///
835 /// ```
836 /// use arrayvec::ArrayVec;
837 ///
838 /// for elt in ArrayVec::from([1, 2, 3]) {
839 /// // ...
840 /// }
841 /// ```
842 impl<T, const CAP: usize> IntoIterator for ArrayVec<T, CAP> {
843 type Item = T;
844 type IntoIter = IntoIter<T, CAP>;
into_iter(self) -> IntoIter<T, CAP>845 fn into_iter(self) -> IntoIter<T, CAP> {
846 IntoIter { index: 0, v: self, }
847 }
848 }
849
850
851 #[cfg(feature = "zeroize")]
852 /// "Best efforts" zeroing of the `ArrayVec`'s buffer when the `zeroize` feature is enabled.
853 ///
854 /// The length is set to 0, and the buffer is dropped and zeroized.
855 /// Cannot ensure that previous moves of the `ArrayVec` did not leave values on the stack.
856 ///
857 /// ```
858 /// use arrayvec::ArrayVec;
859 /// use zeroize::Zeroize;
860 /// let mut array = ArrayVec::from([1, 2, 3]);
861 /// array.zeroize();
862 /// assert_eq!(array.len(), 0);
863 /// let data = unsafe { core::slice::from_raw_parts(array.as_ptr(), array.capacity()) };
864 /// assert_eq!(data, [0, 0, 0]);
865 /// ```
866 impl<Z: zeroize::Zeroize, const CAP: usize> zeroize::Zeroize for ArrayVec<Z, CAP> {
zeroize(&mut self)867 fn zeroize(&mut self) {
868 // Zeroize all the contained elements.
869 self.iter_mut().zeroize();
870 // Drop all the elements and set the length to 0.
871 self.clear();
872 // Zeroize the backing array.
873 self.xs.zeroize();
874 }
875 }
876
877 /// By-value iterator for `ArrayVec`.
878 pub struct IntoIter<T, const CAP: usize> {
879 index: usize,
880 v: ArrayVec<T, CAP>,
881 }
882
883 impl<T, const CAP: usize> Iterator for IntoIter<T, CAP> {
884 type Item = T;
885
next(&mut self) -> Option<Self::Item>886 fn next(&mut self) -> Option<Self::Item> {
887 if self.index == self.v.len() {
888 None
889 } else {
890 unsafe {
891 let index = self.index;
892 self.index = index + 1;
893 Some(ptr::read(self.v.get_unchecked_ptr(index)))
894 }
895 }
896 }
897
size_hint(&self) -> (usize, Option<usize>)898 fn size_hint(&self) -> (usize, Option<usize>) {
899 let len = self.v.len() - self.index;
900 (len, Some(len))
901 }
902 }
903
904 impl<T, const CAP: usize> DoubleEndedIterator for IntoIter<T, CAP> {
next_back(&mut self) -> Option<Self::Item>905 fn next_back(&mut self) -> Option<Self::Item> {
906 if self.index == self.v.len() {
907 None
908 } else {
909 unsafe {
910 let new_len = self.v.len() - 1;
911 self.v.set_len(new_len);
912 Some(ptr::read(self.v.get_unchecked_ptr(new_len)))
913 }
914 }
915 }
916 }
917
918 impl<T, const CAP: usize> ExactSizeIterator for IntoIter<T, CAP> { }
919
920 impl<T, const CAP: usize> Drop for IntoIter<T, CAP> {
drop(&mut self)921 fn drop(&mut self) {
922 // panic safety: Set length to 0 before dropping elements.
923 let index = self.index;
924 let len = self.v.len();
925 unsafe {
926 self.v.set_len(0);
927 let elements = slice::from_raw_parts_mut(
928 self.v.get_unchecked_ptr(index),
929 len - index);
930 ptr::drop_in_place(elements);
931 }
932 }
933 }
934
935 impl<T, const CAP: usize> Clone for IntoIter<T, CAP>
936 where T: Clone,
937 {
clone(&self) -> IntoIter<T, CAP>938 fn clone(&self) -> IntoIter<T, CAP> {
939 let mut v = ArrayVec::new();
940 v.extend_from_slice(&self.v[self.index..]);
941 v.into_iter()
942 }
943 }
944
945 impl<T, const CAP: usize> fmt::Debug for IntoIter<T, CAP>
946 where
947 T: fmt::Debug,
948 {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result949 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
950 f.debug_list()
951 .entries(&self.v[self.index..])
952 .finish()
953 }
954 }
955
956 /// A draining iterator for `ArrayVec`.
957 pub struct Drain<'a, T: 'a, const CAP: usize> {
958 /// Index of tail to preserve
959 tail_start: usize,
960 /// Length of tail
961 tail_len: usize,
962 /// Current remaining range to remove
963 iter: slice::Iter<'a, T>,
964 vec: *mut ArrayVec<T, CAP>,
965 }
966
967 unsafe impl<'a, T: Sync, const CAP: usize> Sync for Drain<'a, T, CAP> {}
968 unsafe impl<'a, T: Send, const CAP: usize> Send for Drain<'a, T, CAP> {}
969
970 impl<'a, T: 'a, const CAP: usize> Iterator for Drain<'a, T, CAP> {
971 type Item = T;
972
next(&mut self) -> Option<Self::Item>973 fn next(&mut self) -> Option<Self::Item> {
974 self.iter.next().map(|elt|
975 unsafe {
976 ptr::read(elt as *const _)
977 }
978 )
979 }
980
size_hint(&self) -> (usize, Option<usize>)981 fn size_hint(&self) -> (usize, Option<usize>) {
982 self.iter.size_hint()
983 }
984 }
985
986 impl<'a, T: 'a, const CAP: usize> DoubleEndedIterator for Drain<'a, T, CAP>
987 {
next_back(&mut self) -> Option<Self::Item>988 fn next_back(&mut self) -> Option<Self::Item> {
989 self.iter.next_back().map(|elt|
990 unsafe {
991 ptr::read(elt as *const _)
992 }
993 )
994 }
995 }
996
997 impl<'a, T: 'a, const CAP: usize> ExactSizeIterator for Drain<'a, T, CAP> {}
998
999 impl<'a, T: 'a, const CAP: usize> Drop for Drain<'a, T, CAP> {
drop(&mut self)1000 fn drop(&mut self) {
1001 // len is currently 0 so panicking while dropping will not cause a double drop.
1002
1003 // exhaust self first
1004 while let Some(_) = self.next() { }
1005
1006 if self.tail_len > 0 {
1007 unsafe {
1008 let source_vec = &mut *self.vec;
1009 // memmove back untouched tail, update to new length
1010 let start = source_vec.len();
1011 let tail = self.tail_start;
1012 let ptr = source_vec.as_mut_ptr();
1013 ptr::copy(ptr.add(tail), ptr.add(start), self.tail_len);
1014 source_vec.set_len(start + self.tail_len);
1015 }
1016 }
1017 }
1018 }
1019
1020 struct ScopeExitGuard<T, Data, F>
1021 where F: FnMut(&Data, &mut T)
1022 {
1023 value: T,
1024 data: Data,
1025 f: F,
1026 }
1027
1028 impl<T, Data, F> Drop for ScopeExitGuard<T, Data, F>
1029 where F: FnMut(&Data, &mut T)
1030 {
drop(&mut self)1031 fn drop(&mut self) {
1032 (self.f)(&self.data, &mut self.value)
1033 }
1034 }
1035
1036
1037
1038 /// Extend the `ArrayVec` with an iterator.
1039 ///
1040 /// ***Panics*** if extending the vector exceeds its capacity.
1041 impl<T, const CAP: usize> Extend<T> for ArrayVec<T, CAP> {
1042 /// Extend the `ArrayVec` with an iterator.
1043 ///
1044 /// ***Panics*** if extending the vector exceeds its capacity.
1045 #[track_caller]
extend<I: IntoIterator<Item=T>>(&mut self, iter: I)1046 fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) {
1047 unsafe {
1048 self.extend_from_iter::<_, true>(iter)
1049 }
1050 }
1051 }
1052
1053 #[inline(never)]
1054 #[cold]
1055 #[track_caller]
extend_panic()1056 fn extend_panic() {
1057 panic!("ArrayVec: capacity exceeded in extend/from_iter");
1058 }
1059
1060 impl<T, const CAP: usize> ArrayVec<T, CAP> {
1061 /// Extend the arrayvec from the iterable.
1062 ///
1063 /// ## Safety
1064 ///
1065 /// Unsafe because if CHECK is false, the length of the input is not checked.
1066 /// The caller must ensure the length of the input fits in the capacity.
1067 #[track_caller]
extend_from_iter<I, const CHECK: bool>(&mut self, iterable: I) where I: IntoIterator<Item = T>1068 pub(crate) unsafe fn extend_from_iter<I, const CHECK: bool>(&mut self, iterable: I)
1069 where I: IntoIterator<Item = T>
1070 {
1071 let take = self.capacity() - self.len();
1072 let len = self.len();
1073 let mut ptr = raw_ptr_add(self.as_mut_ptr(), len);
1074 let end_ptr = raw_ptr_add(ptr, take);
1075 // Keep the length in a separate variable, write it back on scope
1076 // exit. To help the compiler with alias analysis and stuff.
1077 // We update the length to handle panic in the iteration of the
1078 // user's iterator, without dropping any elements on the floor.
1079 let mut guard = ScopeExitGuard {
1080 value: &mut self.len,
1081 data: len,
1082 f: move |&len, self_len| {
1083 **self_len = len as LenUint;
1084 }
1085 };
1086 let mut iter = iterable.into_iter();
1087 loop {
1088 if let Some(elt) = iter.next() {
1089 if ptr == end_ptr && CHECK { extend_panic(); }
1090 debug_assert_ne!(ptr, end_ptr);
1091 ptr.write(elt);
1092 ptr = raw_ptr_add(ptr, 1);
1093 guard.data += 1;
1094 } else {
1095 return; // success
1096 }
1097 }
1098 }
1099
1100 /// Extend the ArrayVec with clones of elements from the slice;
1101 /// the length of the slice must be <= the remaining capacity in the arrayvec.
extend_from_slice(&mut self, slice: &[T]) where T: Clone1102 pub(crate) fn extend_from_slice(&mut self, slice: &[T])
1103 where T: Clone
1104 {
1105 let take = self.capacity() - self.len();
1106 debug_assert!(slice.len() <= take);
1107 unsafe {
1108 let slice = if take < slice.len() { &slice[..take] } else { slice };
1109 self.extend_from_iter::<_, false>(slice.iter().cloned());
1110 }
1111 }
1112 }
1113
1114 /// Rawptr add but uses arithmetic distance for ZST
raw_ptr_add<T>(ptr: *mut T, offset: usize) -> *mut T1115 unsafe fn raw_ptr_add<T>(ptr: *mut T, offset: usize) -> *mut T {
1116 if mem::size_of::<T>() == 0 {
1117 // Special case for ZST
1118 ptr.cast::<u8>().wrapping_add(offset).cast()
1119 } else {
1120 ptr.add(offset)
1121 }
1122 }
1123
1124 /// Create an `ArrayVec` from an iterator.
1125 ///
1126 /// ***Panics*** if the number of elements in the iterator exceeds the arrayvec's capacity.
1127 impl<T, const CAP: usize> iter::FromIterator<T> for ArrayVec<T, CAP> {
1128 /// Create an `ArrayVec` from an iterator.
1129 ///
1130 /// ***Panics*** if the number of elements in the iterator exceeds the arrayvec's capacity.
from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self1131 fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self {
1132 let mut array = ArrayVec::new();
1133 array.extend(iter);
1134 array
1135 }
1136 }
1137
1138 impl<T, const CAP: usize> Clone for ArrayVec<T, CAP>
1139 where T: Clone
1140 {
clone(&self) -> Self1141 fn clone(&self) -> Self {
1142 self.iter().cloned().collect()
1143 }
1144
clone_from(&mut self, rhs: &Self)1145 fn clone_from(&mut self, rhs: &Self) {
1146 // recursive case for the common prefix
1147 let prefix = cmp::min(self.len(), rhs.len());
1148 self[..prefix].clone_from_slice(&rhs[..prefix]);
1149
1150 if prefix < self.len() {
1151 // rhs was shorter
1152 self.truncate(prefix);
1153 } else {
1154 let rhs_elems = &rhs[self.len()..];
1155 self.extend_from_slice(rhs_elems);
1156 }
1157 }
1158 }
1159
1160 impl<T, const CAP: usize> Hash for ArrayVec<T, CAP>
1161 where T: Hash
1162 {
hash<H: Hasher>(&self, state: &mut H)1163 fn hash<H: Hasher>(&self, state: &mut H) {
1164 Hash::hash(&**self, state)
1165 }
1166 }
1167
1168 impl<T, const CAP: usize> PartialEq for ArrayVec<T, CAP>
1169 where T: PartialEq
1170 {
eq(&self, other: &Self) -> bool1171 fn eq(&self, other: &Self) -> bool {
1172 **self == **other
1173 }
1174 }
1175
1176 impl<T, const CAP: usize> PartialEq<[T]> for ArrayVec<T, CAP>
1177 where T: PartialEq
1178 {
eq(&self, other: &[T]) -> bool1179 fn eq(&self, other: &[T]) -> bool {
1180 **self == *other
1181 }
1182 }
1183
1184 impl<T, const CAP: usize> Eq for ArrayVec<T, CAP> where T: Eq { }
1185
1186 impl<T, const CAP: usize> Borrow<[T]> for ArrayVec<T, CAP> {
borrow(&self) -> &[T]1187 fn borrow(&self) -> &[T] { self }
1188 }
1189
1190 impl<T, const CAP: usize> BorrowMut<[T]> for ArrayVec<T, CAP> {
borrow_mut(&mut self) -> &mut [T]1191 fn borrow_mut(&mut self) -> &mut [T] { self }
1192 }
1193
1194 impl<T, const CAP: usize> AsRef<[T]> for ArrayVec<T, CAP> {
as_ref(&self) -> &[T]1195 fn as_ref(&self) -> &[T] { self }
1196 }
1197
1198 impl<T, const CAP: usize> AsMut<[T]> for ArrayVec<T, CAP> {
as_mut(&mut self) -> &mut [T]1199 fn as_mut(&mut self) -> &mut [T] { self }
1200 }
1201
1202 impl<T, const CAP: usize> fmt::Debug for ArrayVec<T, CAP> where T: fmt::Debug {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result1203 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { (**self).fmt(f) }
1204 }
1205
1206 impl<T, const CAP: usize> Default for ArrayVec<T, CAP> {
1207 /// Return an empty array
default() -> ArrayVec<T, CAP>1208 fn default() -> ArrayVec<T, CAP> {
1209 ArrayVec::new()
1210 }
1211 }
1212
1213 impl<T, const CAP: usize> PartialOrd for ArrayVec<T, CAP> where T: PartialOrd {
partial_cmp(&self, other: &Self) -> Option<cmp::Ordering>1214 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
1215 (**self).partial_cmp(other)
1216 }
1217
lt(&self, other: &Self) -> bool1218 fn lt(&self, other: &Self) -> bool {
1219 (**self).lt(other)
1220 }
1221
le(&self, other: &Self) -> bool1222 fn le(&self, other: &Self) -> bool {
1223 (**self).le(other)
1224 }
1225
ge(&self, other: &Self) -> bool1226 fn ge(&self, other: &Self) -> bool {
1227 (**self).ge(other)
1228 }
1229
gt(&self, other: &Self) -> bool1230 fn gt(&self, other: &Self) -> bool {
1231 (**self).gt(other)
1232 }
1233 }
1234
1235 impl<T, const CAP: usize> Ord for ArrayVec<T, CAP> where T: Ord {
cmp(&self, other: &Self) -> cmp::Ordering1236 fn cmp(&self, other: &Self) -> cmp::Ordering {
1237 (**self).cmp(other)
1238 }
1239 }
1240
1241 #[cfg(feature="std")]
1242 /// `Write` appends written data to the end of the vector.
1243 ///
1244 /// Requires `features="std"`.
1245 impl<const CAP: usize> io::Write for ArrayVec<u8, CAP> {
write(&mut self, data: &[u8]) -> io::Result<usize>1246 fn write(&mut self, data: &[u8]) -> io::Result<usize> {
1247 let len = cmp::min(self.remaining_capacity(), data.len());
1248 let _result = self.try_extend_from_slice(&data[..len]);
1249 debug_assert!(_result.is_ok());
1250 Ok(len)
1251 }
flush(&mut self) -> io::Result<()>1252 fn flush(&mut self) -> io::Result<()> { Ok(()) }
1253 }
1254
1255 #[cfg(feature="serde")]
1256 /// Requires crate feature `"serde"`
1257 impl<T: Serialize, const CAP: usize> Serialize for ArrayVec<T, CAP> {
serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer1258 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1259 where S: Serializer
1260 {
1261 serializer.collect_seq(self)
1262 }
1263 }
1264
1265 #[cfg(feature="serde")]
1266 /// Requires crate feature `"serde"`
1267 impl<'de, T: Deserialize<'de>, const CAP: usize> Deserialize<'de> for ArrayVec<T, CAP> {
deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>1268 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1269 where D: Deserializer<'de>
1270 {
1271 use serde::de::{Visitor, SeqAccess, Error};
1272 use std::marker::PhantomData;
1273
1274 struct ArrayVecVisitor<'de, T: Deserialize<'de>, const CAP: usize>(PhantomData<(&'de (), [T; CAP])>);
1275
1276 impl<'de, T: Deserialize<'de>, const CAP: usize> Visitor<'de> for ArrayVecVisitor<'de, T, CAP> {
1277 type Value = ArrayVec<T, CAP>;
1278
1279 fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
1280 write!(formatter, "an array with no more than {} items", CAP)
1281 }
1282
1283 fn visit_seq<SA>(self, mut seq: SA) -> Result<Self::Value, SA::Error>
1284 where SA: SeqAccess<'de>,
1285 {
1286 let mut values = ArrayVec::<T, CAP>::new();
1287
1288 while let Some(value) = seq.next_element()? {
1289 if let Err(_) = values.try_push(value) {
1290 return Err(SA::Error::invalid_length(CAP + 1, &self));
1291 }
1292 }
1293
1294 Ok(values)
1295 }
1296 }
1297
1298 deserializer.deserialize_seq(ArrayVecVisitor::<T, CAP>(PhantomData))
1299 }
1300 }
1301