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.
42pub 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
48impl<T, const CAP: usize> Drop for ArrayVec<T, CAP> {
49 fn drop(&mut self) {
50 self.clear();
51
52 // MaybeUninit inhibits array's drop
53 }
54}
55
56macro_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
63impl<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]
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 /// ```
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)]
113 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]
125 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)]
136 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 /// ```
148 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 /// ```
159 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]
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 /// ```
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 /// ```
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 /// ```
248 pub fn truncate(&mut self, new_len: usize) {
249 ArrayVecImpl::truncate(self, new_len)
250 }
251
252 /// Remove all elements in the vector.
253 pub fn clear(&mut self) {
254 ArrayVecImpl::clear(self)
255 }
256
257
258 /// Get pointer to where element at `index` would be
259 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]
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 /// ```
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 /// ```
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 /// ```
371 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 /// ```
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 /// ```
419 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 /// ```
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 /// ```
463 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.
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
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 /// ```
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
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.
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.
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 /// ```
684 pub fn take(&mut self) -> Self {
685 mem::replace(self, Self::new())
686 }
687
688 /// Return a slice containing all elements of the vector.
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.
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.
699 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.
704 pub fn as_mut_ptr(&mut self) -> *mut T {
705 ArrayVecImpl::as_mut_ptr(self)
706 }
707}
708
709impl<T, const CAP: usize> ArrayVecImpl for ArrayVec<T, CAP> {
710 type Item = T;
711 const CAPACITY: usize = CAP;
712
713 fn len(&self) -> usize { self.len() }
714
715 unsafe fn set_len(&mut self, length: usize) {
716 debug_assert!(length <= CAP);
717 self.len = length as LenUint;
718 }
719
720 fn as_ptr(&self) -> *const Self::Item {
721 self.xs.as_ptr() as _
722 }
723
724 fn as_mut_ptr(&mut self) -> *mut Self::Item {
725 self.xs.as_mut_ptr() as _
726 }
727}
728
729impl<T, const CAP: usize> Deref for ArrayVec<T, CAP> {
730 type Target = [T];
731 #[inline]
732 fn deref(&self) -> &Self::Target {
733 self.as_slice()
734 }
735}
736
737impl<T, const CAP: usize> DerefMut for ArrayVec<T, CAP> {
738 #[inline]
739 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/// ```
754impl<T, const CAP: usize> From<[T; CAP]> for ArrayVec<T, CAP> {
755 #[track_caller]
756 fn from(array: [T; CAP]) -> Self {
757 let array: ManuallyDrop<[T; CAP]> = ManuallyDrop::new(array);
758 let mut vec: ArrayVec = <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], count: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/// ```
780impl<T, const CAP: usize> std::convert::TryFrom<&[T]> for ArrayVec<T, CAP>
781 where T: Clone,
782{
783 type Error = CapacityError;
784
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: ArrayVec = 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/// ```
808impl<'a, T: 'a, const CAP: usize> IntoIterator for &'a ArrayVec<T, CAP> {
809 type Item = &'a T;
810 type IntoIter = slice::Iter<'a, T>;
811 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/// ```
825impl<'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>;
828 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/// ```
842impl<T, const CAP: usize> IntoIterator for ArrayVec<T, CAP> {
843 type Item = T;
844 type IntoIter = 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/// ```
866impl<Z: zeroize::Zeroize, const CAP: usize> zeroize::Zeroize for ArrayVec<Z, CAP> {
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`.
878pub struct IntoIter<T, const CAP: usize> {
879 index: usize,
880 v: ArrayVec<T, CAP>,
881}
882
883impl<T, const CAP: usize> Iterator for IntoIter<T, CAP> {
884 type Item = T;
885
886 fn next(&mut self) -> Option<Self::Item> {
887 if self.index == self.v.len() {
888 None
889 } else {
890 unsafe {
891 let index: usize = self.index;
892 self.index = index + 1;
893 Some(ptr::read(self.v.get_unchecked_ptr(index)))
894 }
895 }
896 }
897
898 fn size_hint(&self) -> (usize, Option<usize>) {
899 let len: usize = self.v.len() - self.index;
900 (len, Some(len))
901 }
902}
903
904impl<T, const CAP: usize> DoubleEndedIterator for IntoIter<T, CAP> {
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: usize = self.v.len() - 1;
911 self.v.set_len(length:new_len);
912 Some(ptr::read(self.v.get_unchecked_ptr(index:new_len)))
913 }
914 }
915 }
916}
917
918impl<T, const CAP: usize> ExactSizeIterator for IntoIter<T, CAP> { }
919
920impl<T, const CAP: usize> Drop for IntoIter<T, CAP> {
921 fn drop(&mut self) {
922 // panic safety: Set length to 0 before dropping elements.
923 let index: usize = self.index;
924 let len: usize = self.v.len();
925 unsafe {
926 self.v.set_len(length:0);
927 let elements: &mut [T] = slice::from_raw_parts_mut(
928 self.v.get_unchecked_ptr(index),
929 len:len - index);
930 ptr::drop_in_place(to_drop:elements);
931 }
932 }
933}
934
935impl<T, const CAP: usize> Clone for IntoIter<T, CAP>
936where T: Clone,
937{
938 fn clone(&self) -> IntoIter<T, CAP> {
939 let mut v: ArrayVec = ArrayVec::new();
940 v.extend_from_slice(&self.v[self.index..]);
941 v.into_iter()
942 }
943}
944
945impl<T, const CAP: usize> fmt::Debug for IntoIter<T, CAP>
946where
947 T: fmt::Debug,
948{
949 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
950 f&mut DebugList<'_, '_>.debug_list()
951 .entries(&self.v[self.index..])
952 .finish()
953 }
954}
955
956/// A draining iterator for `ArrayVec`.
957pub 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
967unsafe impl<'a, T: Sync, const CAP: usize> Sync for Drain<'a, T, CAP> {}
968unsafe impl<'a, T: Send, const CAP: usize> Send for Drain<'a, T, CAP> {}
969
970impl<'a, T: 'a, const CAP: usize> Iterator for Drain<'a, T, CAP> {
971 type Item = T;
972
973 fn next(&mut self) -> Option<Self::Item> {
974 self.iter.next().map(|elt: &T|
975 unsafe {
976 ptr::read(src:elt as *const _)
977 }
978 )
979 }
980
981 fn size_hint(&self) -> (usize, Option<usize>) {
982 self.iter.size_hint()
983 }
984}
985
986impl<'a, T: 'a, const CAP: usize> DoubleEndedIterator for Drain<'a, T, CAP>
987{
988 fn next_back(&mut self) -> Option<Self::Item> {
989 self.iter.next_back().map(|elt: &T|
990 unsafe {
991 ptr::read(src:elt as *const _)
992 }
993 )
994 }
995}
996
997impl<'a, T: 'a, const CAP: usize> ExactSizeIterator for Drain<'a, T, CAP> {}
998
999impl<'a, T: 'a, const CAP: usize> Drop for Drain<'a, T, CAP> {
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 ArrayVec = &mut *self.vec;
1009 // memmove back untouched tail, update to new length
1010 let start: usize = source_vec.len();
1011 let tail: usize = self.tail_start;
1012 let ptr: *mut T = source_vec.as_mut_ptr();
1013 ptr::copy(src:ptr.add(tail), dst:ptr.add(start), self.tail_len);
1014 source_vec.set_len(length:start + self.tail_len);
1015 }
1016 }
1017 }
1018}
1019
1020struct ScopeExitGuard<T, Data, F>
1021 where F: FnMut(&Data, &mut T)
1022{
1023 value: T,
1024 data: Data,
1025 f: F,
1026}
1027
1028impl<T, Data, F> Drop for ScopeExitGuard<T, Data, F>
1029 where F: FnMut(&Data, &mut T)
1030{
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.
1041impl<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]
1046 fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) {
1047 unsafe {
1048 self.extend_from_iter::<_, true>(iterable:iter)
1049 }
1050 }
1051}
1052
1053#[inline(never)]
1054#[cold]
1055#[track_caller]
1056fn extend_panic() {
1057 panic!("ArrayVec: capacity exceeded in extend/from_iter");
1058}
1059
1060impl<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]
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.
1102 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
1115unsafe 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(count:offset).cast()
1119 } else {
1120 ptr.add(count: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.
1127impl<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.
1131 fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self {
1132 let mut array: ArrayVec = ArrayVec::new();
1133 array.extend(iter);
1134 array
1135 }
1136}
1137
1138impl<T, const CAP: usize> Clone for ArrayVec<T, CAP>
1139 where T: Clone
1140{
1141 fn clone(&self) -> Self {
1142 self.iter().cloned().collect()
1143 }
1144
1145 fn clone_from(&mut self, rhs: &Self) {
1146 // recursive case for the common prefix
1147 let prefix: usize = cmp::min(self.len(), v2:rhs.len());
1148 self[..prefix].clone_from_slice(&rhs[..prefix]);
1149
1150 if prefix < self.len() {
1151 // rhs was shorter
1152 self.truncate(new_len:prefix);
1153 } else {
1154 let rhs_elems: &[T] = &rhs[self.len()..];
1155 self.extend_from_slice(rhs_elems);
1156 }
1157 }
1158}
1159
1160impl<T, const CAP: usize> Hash for ArrayVec<T, CAP>
1161 where T: Hash
1162{
1163 fn hash<H: Hasher>(&self, state: &mut H) {
1164 Hash::hash(&**self, state)
1165 }
1166}
1167
1168impl<T, const CAP: usize> PartialEq for ArrayVec<T, CAP>
1169 where T: PartialEq
1170{
1171 fn eq(&self, other: &Self) -> bool {
1172 **self == **other
1173 }
1174}
1175
1176impl<T, const CAP: usize> PartialEq<[T]> for ArrayVec<T, CAP>
1177 where T: PartialEq
1178{
1179 fn eq(&self, other: &[T]) -> bool {
1180 **self == *other
1181 }
1182}
1183
1184impl<T, const CAP: usize> Eq for ArrayVec<T, CAP> where T: Eq { }
1185
1186impl<T, const CAP: usize> Borrow<[T]> for ArrayVec<T, CAP> {
1187 fn borrow(&self) -> &[T] { self }
1188}
1189
1190impl<T, const CAP: usize> BorrowMut<[T]> for ArrayVec<T, CAP> {
1191 fn borrow_mut(&mut self) -> &mut [T] { self }
1192}
1193
1194impl<T, const CAP: usize> AsRef<[T]> for ArrayVec<T, CAP> {
1195 fn as_ref(&self) -> &[T] { self }
1196}
1197
1198impl<T, const CAP: usize> AsMut<[T]> for ArrayVec<T, CAP> {
1199 fn as_mut(&mut self) -> &mut [T] { self }
1200}
1201
1202impl<T, const CAP: usize> fmt::Debug for ArrayVec<T, CAP> where T: fmt::Debug {
1203 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { (**self).fmt(f) }
1204}
1205
1206impl<T, const CAP: usize> Default for ArrayVec<T, CAP> {
1207 /// Return an empty array
1208 fn default() -> ArrayVec<T, CAP> {
1209 ArrayVec::new()
1210 }
1211}
1212
1213impl<T, const CAP: usize> PartialOrd for ArrayVec<T, CAP> where T: PartialOrd {
1214 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
1215 (**self).partial_cmp(other)
1216 }
1217
1218 fn lt(&self, other: &Self) -> bool {
1219 (**self).lt(other)
1220 }
1221
1222 fn le(&self, other: &Self) -> bool {
1223 (**self).le(other)
1224 }
1225
1226 fn ge(&self, other: &Self) -> bool {
1227 (**self).ge(other)
1228 }
1229
1230 fn gt(&self, other: &Self) -> bool {
1231 (**self).gt(other)
1232 }
1233}
1234
1235impl<T, const CAP: usize> Ord for ArrayVec<T, CAP> where T: Ord {
1236 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"`.
1245impl<const CAP: usize> io::Write for ArrayVec<u8, CAP> {
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 }
1252 fn flush(&mut self) -> io::Result<()> { Ok(()) }
1253}
1254
1255#[cfg(feature="serde")]
1256/// Requires crate feature `"serde"`
1257impl<T: Serialize, const CAP: usize> Serialize for ArrayVec<T, CAP> {
1258 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"`
1267impl<'de, T: Deserialize<'de>, const CAP: usize> Deserialize<'de> for ArrayVec<T, CAP> {
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