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