1use super::*;
2use core::convert::{TryFrom, TryInto};
3
4#[cfg(feature = "serde")]
5use core::marker::PhantomData;
6#[cfg(feature = "serde")]
7use serde::de::{
8 Deserialize, Deserializer, Error as DeserializeError, SeqAccess, Visitor,
9};
10#[cfg(feature = "serde")]
11use serde::ser::{Serialize, SerializeSeq, Serializer};
12
13/// Helper to make an `ArrayVec`.
14///
15/// You specify the backing array type, and optionally give all the elements you
16/// want to initially place into the array.
17///
18/// ```rust
19/// use tinyvec::*;
20///
21/// // The backing array type can be specified in the macro call
22/// let empty_av = array_vec!([u8; 16]);
23/// let some_ints = array_vec!([i32; 4] => 1, 2, 3);
24///
25/// // Or left to inference
26/// let empty_av: ArrayVec<[u8; 10]> = array_vec!();
27/// let some_ints: ArrayVec<[u8; 10]> = array_vec!(5, 6, 7, 8);
28/// ```
29#[macro_export]
30macro_rules! array_vec {
31 ($array_type:ty => $($elem:expr),* $(,)?) => {
32 {
33 let mut av: $crate::ArrayVec<$array_type> = Default::default();
34 $( av.push($elem); )*
35 av
36 }
37 };
38 ($array_type:ty) => {
39 $crate::ArrayVec::<$array_type>::default()
40 };
41 ($($elem:expr),*) => {
42 $crate::array_vec!(_ => $($elem),*)
43 };
44 ($elem:expr; $n:expr) => {
45 $crate::ArrayVec::from([$elem; $n])
46 };
47 () => {
48 $crate::array_vec!(_)
49 };
50}
51
52/// An array-backed, vector-like data structure.
53///
54/// * `ArrayVec` has a fixed capacity, equal to the minimum of the array size
55/// and `u16::MAX`. Note that not all capacities are necessarily supported by
56/// default. See comments in [`Array`].
57/// * `ArrayVec` has a variable length, as you add and remove elements. Attempts
58/// to fill the vec beyond its capacity will cause a panic.
59/// * All of the vec's array slots are always initialized in terms of Rust's
60/// memory model. When you remove a element from a location, the old value at
61/// that location is replaced with the type's default value.
62///
63/// The overall API of this type is intended to, as much as possible, emulate
64/// the API of the [`Vec`](https://doc.rust-lang.org/alloc/vec/struct.Vec.html)
65/// type.
66///
67/// ## Construction
68///
69/// You can use the `array_vec!` macro similarly to how you might use the `vec!`
70/// macro. Specify the array type, then optionally give all the initial values
71/// you want to have.
72/// ```rust
73/// # use tinyvec::*;
74/// let some_ints = array_vec!([i32; 4] => 1, 2, 3);
75/// assert_eq!(some_ints.len(), 3);
76/// ```
77///
78/// The [`default`](ArrayVec::new) for an `ArrayVec` is to have a default
79/// array with length 0. The [`new`](ArrayVec::new) method is the same as
80/// calling `default`
81/// ```rust
82/// # use tinyvec::*;
83/// let some_ints = ArrayVec::<[i32; 7]>::default();
84/// assert_eq!(some_ints.len(), 0);
85///
86/// let more_ints = ArrayVec::<[i32; 7]>::new();
87/// assert_eq!(some_ints, more_ints);
88/// ```
89///
90/// If you have an array and want the _whole thing_ so count as being "in" the
91/// new `ArrayVec` you can use one of the `from` implementations. If you want
92/// _part of_ the array then you can use
93/// [`from_array_len`](ArrayVec::from_array_len):
94/// ```rust
95/// # use tinyvec::*;
96/// let some_ints = ArrayVec::from([5, 6, 7, 8]);
97/// assert_eq!(some_ints.len(), 4);
98///
99/// let more_ints = ArrayVec::from_array_len([5, 6, 7, 8], 2);
100/// assert_eq!(more_ints.len(), 2);
101///
102/// let no_ints: ArrayVec<[u8; 5]> = ArrayVec::from_array_empty([1, 2, 3, 4, 5]);
103/// assert_eq!(no_ints.len(), 0);
104/// ```
105#[repr(C)]
106pub struct ArrayVec<A> {
107 len: u16,
108 pub(crate) data: A,
109}
110
111impl<A> Clone for ArrayVec<A>
112where
113 A: Array + Clone,
114 A::Item: Clone,
115{
116 #[inline]
117 fn clone(&self) -> Self {
118 Self { data: self.data.clone(), len: self.len }
119 }
120
121 #[inline]
122 fn clone_from(&mut self, o: &Self) {
123 let iter = self
124 .data
125 .as_slice_mut()
126 .iter_mut()
127 .zip(o.data.as_slice())
128 .take(self.len.max(o.len) as usize);
129 for (dst, src) in iter {
130 dst.clone_from(src)
131 }
132 if let Some(to_drop) =
133 self.data.as_slice_mut().get_mut((o.len as usize)..(self.len as usize))
134 {
135 to_drop.iter_mut().for_each(|x| drop(core::mem::take(x)));
136 }
137 self.len = o.len;
138 }
139}
140
141impl<A> Copy for ArrayVec<A>
142where
143 A: Array + Copy,
144 A::Item: Copy,
145{
146}
147
148impl<A: Array> Default for ArrayVec<A> {
149 #[inline]
150 fn default() -> Self {
151 Self { len: 0, data: A::default() }
152 }
153}
154
155impl<A: Array> Deref for ArrayVec<A> {
156 type Target = [A::Item];
157 #[inline(always)]
158 #[must_use]
159 fn deref(&self) -> &Self::Target {
160 &self.data.as_slice()[..self.len as usize]
161 }
162}
163
164impl<A: Array> DerefMut for ArrayVec<A> {
165 #[inline(always)]
166 #[must_use]
167 fn deref_mut(&mut self) -> &mut Self::Target {
168 &mut self.data.as_slice_mut()[..self.len as usize]
169 }
170}
171
172impl<A: Array, I: SliceIndex<[A::Item]>> Index<I> for ArrayVec<A> {
173 type Output = <I as SliceIndex<[A::Item]>>::Output;
174 #[inline(always)]
175 #[must_use]
176 fn index(&self, index: I) -> &Self::Output {
177 &self.deref()[index]
178 }
179}
180
181impl<A: Array, I: SliceIndex<[A::Item]>> IndexMut<I> for ArrayVec<A> {
182 #[inline(always)]
183 #[must_use]
184 fn index_mut(&mut self, index: I) -> &mut Self::Output {
185 &mut self.deref_mut()[index]
186 }
187}
188
189#[cfg(feature = "serde")]
190#[cfg_attr(docs_rs, doc(cfg(feature = "serde")))]
191impl<A: Array> Serialize for ArrayVec<A>
192where
193 A::Item: Serialize,
194{
195 #[must_use]
196 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
197 where
198 S: Serializer,
199 {
200 let mut seq = serializer.serialize_seq(Some(self.len()))?;
201 for element in self.iter() {
202 seq.serialize_element(element)?;
203 }
204 seq.end()
205 }
206}
207
208#[cfg(feature = "serde")]
209#[cfg_attr(docs_rs, doc(cfg(feature = "serde")))]
210impl<'de, A: Array> Deserialize<'de> for ArrayVec<A>
211where
212 A::Item: Deserialize<'de>,
213{
214 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
215 where
216 D: Deserializer<'de>,
217 {
218 deserializer.deserialize_seq(ArrayVecVisitor(PhantomData))
219 }
220}
221
222#[cfg(feature = "borsh")]
223#[cfg_attr(docs_rs, doc(cfg(feature = "borsh")))]
224impl<A: Array> borsh::BorshSerialize for ArrayVec<A>
225where
226 <A as Array>::Item: borsh::BorshSerialize,
227{
228 fn serialize<W: borsh::io::Write>(
229 &self, writer: &mut W,
230 ) -> borsh::io::Result<()> {
231 <usize as borsh::BorshSerialize>::serialize(&self.len(), writer)?;
232 for elem in self.iter() {
233 <<A as Array>::Item as borsh::BorshSerialize>::serialize(elem, writer)?;
234 }
235 Ok(())
236 }
237}
238
239#[cfg(feature = "borsh")]
240#[cfg_attr(docs_rs, doc(cfg(feature = "borsh")))]
241impl<A: Array> borsh::BorshDeserialize for ArrayVec<A>
242where
243 <A as Array>::Item: borsh::BorshDeserialize,
244{
245 fn deserialize_reader<R: borsh::io::Read>(
246 reader: &mut R,
247 ) -> borsh::io::Result<Self> {
248 let len = <usize as borsh::BorshDeserialize>::deserialize_reader(reader)?;
249 let mut new_arrayvec = Self::default();
250
251 for idx in 0..len {
252 let value =
253 <<A as Array>::Item as borsh::BorshDeserialize>::deserialize_reader(
254 reader,
255 )?;
256 if idx >= new_arrayvec.capacity() {
257 return Err(borsh::io::Error::new(
258 borsh::io::ErrorKind::InvalidData,
259 "invalid ArrayVec length",
260 ));
261 }
262 new_arrayvec.push(value)
263 }
264
265 Ok(new_arrayvec)
266 }
267}
268
269#[cfg(feature = "arbitrary")]
270#[cfg_attr(docs_rs, doc(cfg(feature = "arbitrary")))]
271impl<'a, A> arbitrary::Arbitrary<'a> for ArrayVec<A>
272where
273 A: Array,
274 A::Item: arbitrary::Arbitrary<'a>,
275{
276 fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
277 let max_len = A::CAPACITY.min(u16::MAX as usize) as u16;
278 let len = u.int_in_range::<u16>(0..=max_len)?;
279 let mut self_: Self = Default::default();
280 for _ in 0..len {
281 self_.push(u.arbitrary()?);
282 }
283 Ok(self_)
284 }
285
286 fn size_hint(depth: usize) -> (usize, Option<usize>) {
287 arbitrary::size_hint::recursion_guard(depth, |depth| {
288 let max_len = A::CAPACITY.min(u16::MAX as usize);
289 let inner = A::Item::size_hint(depth).1;
290 (0, inner.map(|inner| 2 + max_len * inner))
291 })
292 }
293}
294
295impl<A: Array> ArrayVec<A> {
296 /// Move all values from `other` into this vec.
297 ///
298 /// ## Panics
299 /// * If the vec overflows its capacity
300 ///
301 /// ## Example
302 /// ```rust
303 /// # use tinyvec::*;
304 /// let mut av = array_vec!([i32; 10] => 1, 2, 3);
305 /// let mut av2 = array_vec!([i32; 10] => 4, 5, 6);
306 /// av.append(&mut av2);
307 /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]);
308 /// assert_eq!(av2, &[][..]);
309 /// ```
310 #[inline]
311 pub fn append(&mut self, other: &mut Self) {
312 assert!(
313 self.try_append(other).is_none(),
314 "ArrayVec::append> total length {} exceeds capacity {}!",
315 self.len() + other.len(),
316 A::CAPACITY
317 );
318 }
319
320 /// Move all values from `other` into this vec.
321 /// If appending would overflow the capacity, Some(other) is returned.
322 /// ## Example
323 /// ```rust
324 /// # use tinyvec::*;
325 /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
326 /// let mut av2 = array_vec!([i32; 7] => 4, 5, 6);
327 /// av.append(&mut av2);
328 /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]);
329 /// assert_eq!(av2, &[][..]);
330 ///
331 /// let mut av3 = array_vec!([i32; 7] => 7, 8, 9);
332 /// assert!(av.try_append(&mut av3).is_some());
333 /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]);
334 /// assert_eq!(av3, &[7, 8, 9][..]);
335 /// ```
336 #[inline]
337 pub fn try_append<'other>(
338 &mut self, other: &'other mut Self,
339 ) -> Option<&'other mut Self> {
340 let new_len = self.len() + other.len();
341 if new_len > A::CAPACITY {
342 return Some(other);
343 }
344
345 let iter = other.iter_mut().map(core::mem::take);
346 for item in iter {
347 self.push(item);
348 }
349
350 other.set_len(0);
351
352 return None;
353 }
354
355 /// A `*mut` pointer to the backing array.
356 ///
357 /// ## Safety
358 ///
359 /// This pointer has provenance over the _entire_ backing array.
360 #[inline(always)]
361 #[must_use]
362 pub fn as_mut_ptr(&mut self) -> *mut A::Item {
363 self.data.as_slice_mut().as_mut_ptr()
364 }
365
366 /// Performs a `deref_mut`, into unique slice form.
367 #[inline(always)]
368 #[must_use]
369 pub fn as_mut_slice(&mut self) -> &mut [A::Item] {
370 self.deref_mut()
371 }
372
373 /// A `*const` pointer to the backing array.
374 ///
375 /// ## Safety
376 ///
377 /// This pointer has provenance over the _entire_ backing array.
378 #[inline(always)]
379 #[must_use]
380 pub fn as_ptr(&self) -> *const A::Item {
381 self.data.as_slice().as_ptr()
382 }
383
384 /// Performs a `deref`, into shared slice form.
385 #[inline(always)]
386 #[must_use]
387 pub fn as_slice(&self) -> &[A::Item] {
388 self.deref()
389 }
390
391 /// The capacity of the `ArrayVec`.
392 ///
393 /// This is fixed based on the array type, but can't yet be made a `const fn`
394 /// on Stable Rust.
395 #[inline(always)]
396 #[must_use]
397 pub fn capacity(&self) -> usize {
398 // Note: This shouldn't use A::CAPACITY, because unsafe code can't rely on
399 // any Array invariants. This ensures that at the very least, the returned
400 // value is a valid length for a subslice of the backing array.
401 self.data.as_slice().len().min(u16::MAX as usize)
402 }
403
404 /// Truncates the `ArrayVec` down to length 0.
405 #[inline(always)]
406 pub fn clear(&mut self) {
407 self.truncate(0)
408 }
409
410 /// Creates a draining iterator that removes the specified range in the vector
411 /// and yields the removed items.
412 ///
413 /// ## Panics
414 /// * If the start is greater than the end
415 /// * If the end is past the edge of the vec.
416 ///
417 /// ## Example
418 /// ```rust
419 /// # use tinyvec::*;
420 /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
421 /// let av2: ArrayVec<[i32; 4]> = av.drain(1..).collect();
422 /// assert_eq!(av.as_slice(), &[1][..]);
423 /// assert_eq!(av2.as_slice(), &[2, 3][..]);
424 ///
425 /// av.drain(..);
426 /// assert_eq!(av.as_slice(), &[]);
427 /// ```
428 #[inline]
429 pub fn drain<R>(&mut self, range: R) -> ArrayVecDrain<'_, A::Item>
430 where
431 R: RangeBounds<usize>,
432 {
433 ArrayVecDrain::new(self, range)
434 }
435
436 /// Returns the inner array of the `ArrayVec`.
437 ///
438 /// This returns the full array, even if the `ArrayVec` length is currently
439 /// less than that.
440 ///
441 /// ## Example
442 ///
443 /// ```rust
444 /// # use tinyvec::{array_vec, ArrayVec};
445 /// let mut favorite_numbers = array_vec!([i32; 5] => 87, 48, 33, 9, 26);
446 /// assert_eq!(favorite_numbers.clone().into_inner(), [87, 48, 33, 9, 26]);
447 ///
448 /// favorite_numbers.pop();
449 /// assert_eq!(favorite_numbers.into_inner(), [87, 48, 33, 9, 0]);
450 /// ```
451 ///
452 /// A use for this function is to build an array from an iterator by first
453 /// collecting it into an `ArrayVec`.
454 ///
455 /// ```rust
456 /// # use tinyvec::ArrayVec;
457 /// let arr_vec: ArrayVec<[i32; 10]> = (1..=3).cycle().take(10).collect();
458 /// let inner = arr_vec.into_inner();
459 /// assert_eq!(inner, [1, 2, 3, 1, 2, 3, 1, 2, 3, 1]);
460 /// ```
461 #[inline]
462 pub fn into_inner(self) -> A {
463 self.data
464 }
465
466 /// Clone each element of the slice into this `ArrayVec`.
467 ///
468 /// ## Panics
469 /// * If the `ArrayVec` would overflow, this will panic.
470 #[inline]
471 pub fn extend_from_slice(&mut self, sli: &[A::Item])
472 where
473 A::Item: Clone,
474 {
475 if sli.is_empty() {
476 return;
477 }
478
479 let new_len = self.len as usize + sli.len();
480 assert!(
481 new_len <= A::CAPACITY,
482 "ArrayVec::extend_from_slice> total length {} exceeds capacity {}!",
483 new_len,
484 A::CAPACITY
485 );
486
487 let target = &mut self.data.as_slice_mut()[self.len as usize..new_len];
488 target.clone_from_slice(sli);
489 self.set_len(new_len);
490 }
491
492 /// Fill the vector until its capacity has been reached.
493 ///
494 /// Successively fills unused space in the spare slice of the vector with
495 /// elements from the iterator. It then returns the remaining iterator
496 /// without exhausting it. This also allows appending the head of an
497 /// infinite iterator.
498 ///
499 /// This is an alternative to `Extend::extend` method for cases where the
500 /// length of the iterator can not be checked. Since this vector can not
501 /// reallocate to increase its capacity, it is unclear what to do with
502 /// remaining elements in the iterator and the iterator itself. The
503 /// interface also provides no way to communicate this to the caller.
504 ///
505 /// ## Panics
506 /// * If the `next` method of the provided iterator panics.
507 ///
508 /// ## Example
509 ///
510 /// ```rust
511 /// # use tinyvec::*;
512 /// let mut av = array_vec!([i32; 4]);
513 /// let mut to_inf = av.fill(0..);
514 /// assert_eq!(&av[..], [0, 1, 2, 3]);
515 /// assert_eq!(to_inf.next(), Some(4));
516 /// ```
517 #[inline]
518 pub fn fill<I: IntoIterator<Item = A::Item>>(
519 &mut self, iter: I,
520 ) -> I::IntoIter {
521 // If this is written as a call to push for each element in iter, the
522 // compiler emits code that updates the length for every element. The
523 // additional complexity from that length update is worth nearly 2x in
524 // the runtime of this function.
525 let mut iter = iter.into_iter();
526 let mut pushed = 0;
527 let to_take = self.capacity() - self.len();
528 let target = &mut self.data.as_slice_mut()[self.len as usize..];
529 for element in iter.by_ref().take(to_take) {
530 target[pushed] = element;
531 pushed += 1;
532 }
533 self.len += pushed as u16;
534 iter
535 }
536
537 /// Wraps up an array and uses the given length as the initial length.
538 ///
539 /// If you want to simply use the full array, use `from` instead.
540 ///
541 /// ## Panics
542 ///
543 /// * The length specified must be less than or equal to the capacity of the
544 /// array.
545 #[inline]
546 #[must_use]
547 #[allow(clippy::match_wild_err_arm)]
548 pub fn from_array_len(data: A, len: usize) -> Self {
549 match Self::try_from_array_len(data, len) {
550 Ok(out) => out,
551 Err(_) => panic!(
552 "ArrayVec::from_array_len> length {} exceeds capacity {}!",
553 len,
554 A::CAPACITY
555 ),
556 }
557 }
558
559 /// Inserts an item at the position given, moving all following elements +1
560 /// index.
561 ///
562 /// ## Panics
563 /// * If `index` > `len`
564 /// * If the capacity is exhausted
565 ///
566 /// ## Example
567 /// ```rust
568 /// use tinyvec::*;
569 /// let mut av = array_vec!([i32; 10] => 1, 2, 3);
570 /// av.insert(1, 4);
571 /// assert_eq!(av.as_slice(), &[1, 4, 2, 3]);
572 /// av.insert(4, 5);
573 /// assert_eq!(av.as_slice(), &[1, 4, 2, 3, 5]);
574 /// ```
575 #[inline]
576 pub fn insert(&mut self, index: usize, item: A::Item) {
577 let x = self.try_insert(index, item);
578 assert!(x.is_none(), "ArrayVec::insert> capacity overflow!");
579 }
580
581 /// Tries to insert an item at the position given, moving all following
582 /// elements +1 index.
583 /// Returns back the element if the capacity is exhausted,
584 /// otherwise returns None.
585 ///
586 /// ## Panics
587 /// * If `index` > `len`
588 ///
589 /// ## Example
590 /// ```rust
591 /// use tinyvec::*;
592 /// let mut av = array_vec!([&'static str; 4] => "one", "two", "three");
593 /// av.insert(1, "four");
594 /// assert_eq!(av.as_slice(), &["one", "four", "two", "three"]);
595 /// assert_eq!(av.try_insert(4, "five"), Some("five"));
596 /// ```
597 #[inline]
598 pub fn try_insert(
599 &mut self, index: usize, mut item: A::Item,
600 ) -> Option<A::Item> {
601 assert!(
602 index <= self.len as usize,
603 "ArrayVec::try_insert> index {} is out of bounds {}",
604 index,
605 self.len
606 );
607
608 // A previous implementation used self.try_push and slice::rotate_right
609 // rotate_right and rotate_left generate a huge amount of code and fail to
610 // inline; calling them here incurs the cost of all the cases they
611 // handle even though we're rotating a usually-small array by a constant
612 // 1 offset. This swap-based implementation benchmarks much better for
613 // small array lengths in particular.
614
615 if (self.len as usize) < A::CAPACITY {
616 self.len += 1;
617 } else {
618 return Some(item);
619 }
620
621 let target = &mut self.as_mut_slice()[index..];
622 #[allow(clippy::needless_range_loop)]
623 for i in 0..target.len() {
624 core::mem::swap(&mut item, &mut target[i]);
625 }
626 return None;
627 }
628
629 /// Checks if the length is 0.
630 #[inline(always)]
631 #[must_use]
632 pub fn is_empty(&self) -> bool {
633 self.len == 0
634 }
635
636 /// The length of the `ArrayVec` (in elements).
637 #[inline(always)]
638 #[must_use]
639 pub fn len(&self) -> usize {
640 self.len as usize
641 }
642
643 /// Makes a new, empty `ArrayVec`.
644 #[inline(always)]
645 #[must_use]
646 pub fn new() -> Self {
647 Self::default()
648 }
649
650 /// Remove and return the last element of the vec, if there is one.
651 ///
652 /// ## Failure
653 /// * If the vec is empty you get `None`.
654 ///
655 /// ## Example
656 /// ```rust
657 /// # use tinyvec::*;
658 /// let mut av = array_vec!([i32; 10] => 1, 2);
659 /// assert_eq!(av.pop(), Some(2));
660 /// assert_eq!(av.pop(), Some(1));
661 /// assert_eq!(av.pop(), None);
662 /// ```
663 #[inline]
664 pub fn pop(&mut self) -> Option<A::Item> {
665 if self.len > 0 {
666 self.len -= 1;
667 let out =
668 core::mem::take(&mut self.data.as_slice_mut()[self.len as usize]);
669 Some(out)
670 } else {
671 None
672 }
673 }
674
675 /// Place an element onto the end of the vec.
676 ///
677 /// ## Panics
678 /// * If the length of the vec would overflow the capacity.
679 ///
680 /// ## Example
681 /// ```rust
682 /// # use tinyvec::*;
683 /// let mut av = array_vec!([i32; 2]);
684 /// assert_eq!(&av[..], []);
685 /// av.push(1);
686 /// assert_eq!(&av[..], [1]);
687 /// av.push(2);
688 /// assert_eq!(&av[..], [1, 2]);
689 /// // av.push(3); this would overflow the ArrayVec and panic!
690 /// ```
691 #[inline(always)]
692 pub fn push(&mut self, val: A::Item) {
693 let x = self.try_push(val);
694 assert!(x.is_none(), "ArrayVec::push> capacity overflow!");
695 }
696
697 /// Tries to place an element onto the end of the vec.\
698 /// Returns back the element if the capacity is exhausted,
699 /// otherwise returns None.
700 /// ```rust
701 /// # use tinyvec::*;
702 /// let mut av = array_vec!([i32; 2]);
703 /// assert_eq!(av.as_slice(), []);
704 /// assert_eq!(av.try_push(1), None);
705 /// assert_eq!(&av[..], [1]);
706 /// assert_eq!(av.try_push(2), None);
707 /// assert_eq!(&av[..], [1, 2]);
708 /// assert_eq!(av.try_push(3), Some(3));
709 /// ```
710 #[inline(always)]
711 pub fn try_push(&mut self, val: A::Item) -> Option<A::Item> {
712 debug_assert!(self.len as usize <= A::CAPACITY);
713
714 let itemref = match self.data.as_slice_mut().get_mut(self.len as usize) {
715 None => return Some(val),
716 Some(x) => x,
717 };
718
719 *itemref = val;
720 self.len += 1;
721 return None;
722 }
723
724 /// Removes the item at `index`, shifting all others down by one index.
725 ///
726 /// Returns the removed element.
727 ///
728 /// ## Panics
729 ///
730 /// * If the index is out of bounds.
731 ///
732 /// ## Example
733 ///
734 /// ```rust
735 /// # use tinyvec::*;
736 /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
737 /// assert_eq!(av.remove(1), 2);
738 /// assert_eq!(&av[..], [1, 3]);
739 /// ```
740 #[inline]
741 pub fn remove(&mut self, index: usize) -> A::Item {
742 let targets: &mut [A::Item] = &mut self.deref_mut()[index..];
743 let item = core::mem::take(&mut targets[0]);
744
745 // A previous implementation used rotate_left
746 // rotate_right and rotate_left generate a huge amount of code and fail to
747 // inline; calling them here incurs the cost of all the cases they
748 // handle even though we're rotating a usually-small array by a constant
749 // 1 offset. This swap-based implementation benchmarks much better for
750 // small array lengths in particular.
751
752 for i in 0..targets.len() - 1 {
753 targets.swap(i, i + 1);
754 }
755 self.len -= 1;
756 item
757 }
758
759 /// As [`resize_with`](ArrayVec::resize_with)
760 /// and it clones the value as the closure.
761 ///
762 /// ## Example
763 ///
764 /// ```rust
765 /// # use tinyvec::*;
766 ///
767 /// let mut av = array_vec!([&str; 10] => "hello");
768 /// av.resize(3, "world");
769 /// assert_eq!(&av[..], ["hello", "world", "world"]);
770 ///
771 /// let mut av = array_vec!([i32; 10] => 1, 2, 3, 4);
772 /// av.resize(2, 0);
773 /// assert_eq!(&av[..], [1, 2]);
774 /// ```
775 #[inline]
776 pub fn resize(&mut self, new_len: usize, new_val: A::Item)
777 where
778 A::Item: Clone,
779 {
780 self.resize_with(new_len, || new_val.clone())
781 }
782
783 /// Resize the vec to the new length.
784 ///
785 /// If it needs to be longer, it's filled with repeated calls to the provided
786 /// function. If it needs to be shorter, it's truncated.
787 ///
788 /// ## Example
789 ///
790 /// ```rust
791 /// # use tinyvec::*;
792 ///
793 /// let mut av = array_vec!([i32; 10] => 1, 2, 3);
794 /// av.resize_with(5, Default::default);
795 /// assert_eq!(&av[..], [1, 2, 3, 0, 0]);
796 ///
797 /// let mut av = array_vec!([i32; 10]);
798 /// let mut p = 1;
799 /// av.resize_with(4, || {
800 /// p *= 2;
801 /// p
802 /// });
803 /// assert_eq!(&av[..], [2, 4, 8, 16]);
804 /// ```
805 #[inline]
806 pub fn resize_with<F: FnMut() -> A::Item>(
807 &mut self, new_len: usize, mut f: F,
808 ) {
809 match new_len.checked_sub(self.len as usize) {
810 None => self.truncate(new_len),
811 Some(new_elements) => {
812 for _ in 0..new_elements {
813 self.push(f());
814 }
815 }
816 }
817 }
818
819 /// Walk the vec and keep only the elements that pass the predicate given.
820 ///
821 /// ## Example
822 ///
823 /// ```rust
824 /// # use tinyvec::*;
825 ///
826 /// let mut av = array_vec!([i32; 10] => 1, 1, 2, 3, 3, 4);
827 /// av.retain(|&x| x % 2 == 0);
828 /// assert_eq!(&av[..], [2, 4]);
829 /// ```
830 #[inline]
831 pub fn retain<F: FnMut(&A::Item) -> bool>(&mut self, mut acceptable: F) {
832 // Drop guard to contain exactly the remaining elements when the test
833 // panics.
834 struct JoinOnDrop<'vec, Item> {
835 items: &'vec mut [Item],
836 done_end: usize,
837 // Start of tail relative to `done_end`.
838 tail_start: usize,
839 }
840
841 impl<Item> Drop for JoinOnDrop<'_, Item> {
842 fn drop(&mut self) {
843 self.items[self.done_end..].rotate_left(self.tail_start);
844 }
845 }
846
847 let mut rest = JoinOnDrop {
848 items: &mut self.data.as_slice_mut()[..self.len as usize],
849 done_end: 0,
850 tail_start: 0,
851 };
852
853 let len = self.len as usize;
854 for idx in 0..len {
855 // Loop start invariant: idx = rest.done_end + rest.tail_start
856 if !acceptable(&rest.items[idx]) {
857 let _ = core::mem::take(&mut rest.items[idx]);
858 self.len -= 1;
859 rest.tail_start += 1;
860 } else {
861 rest.items.swap(rest.done_end, idx);
862 rest.done_end += 1;
863 }
864 }
865 }
866
867 /// Retains only the elements specified by the predicate, passing a mutable
868 /// reference to it.
869 ///
870 /// In other words, remove all elements e such that f(&mut e) returns false.
871 /// This method operates in place, visiting each element exactly once in the
872 /// original order, and preserves the order of the retained elements.
873 ///
874 ///
875 /// ## Example
876 ///
877 /// ```rust
878 /// # use tinyvec::*;
879 ///
880 /// let mut av = array_vec!([i32; 10] => 1, 1, 2, 3, 3, 4);
881 /// av.retain_mut(|x| if *x % 2 == 0 { *x *= 2; true } else { false });
882 /// assert_eq!(&av[..], [4, 8]);
883 /// ```
884 #[inline]
885 pub fn retain_mut<F>(&mut self, mut acceptable: F)
886 where
887 F: FnMut(&mut A::Item) -> bool,
888 {
889 // Drop guard to contain exactly the remaining elements when the test
890 // panics.
891 struct JoinOnDrop<'vec, Item> {
892 items: &'vec mut [Item],
893 done_end: usize,
894 // Start of tail relative to `done_end`.
895 tail_start: usize,
896 }
897
898 impl<Item> Drop for JoinOnDrop<'_, Item> {
899 fn drop(&mut self) {
900 self.items[self.done_end..].rotate_left(self.tail_start);
901 }
902 }
903
904 let mut rest = JoinOnDrop {
905 items: &mut self.data.as_slice_mut()[..self.len as usize],
906 done_end: 0,
907 tail_start: 0,
908 };
909
910 let len = self.len as usize;
911 for idx in 0..len {
912 // Loop start invariant: idx = rest.done_end + rest.tail_start
913 if !acceptable(&mut rest.items[idx]) {
914 let _ = core::mem::take(&mut rest.items[idx]);
915 self.len -= 1;
916 rest.tail_start += 1;
917 } else {
918 rest.items.swap(rest.done_end, idx);
919 rest.done_end += 1;
920 }
921 }
922 }
923
924 /// Forces the length of the vector to `new_len`.
925 ///
926 /// ## Panics
927 /// * If `new_len` is greater than the vec's capacity.
928 ///
929 /// ## Safety
930 /// * This is a fully safe operation! The inactive memory already counts as
931 /// "initialized" by Rust's rules.
932 /// * Other than "the memory is initialized" there are no other guarantees
933 /// regarding what you find in the inactive portion of the vec.
934 #[inline(always)]
935 pub fn set_len(&mut self, new_len: usize) {
936 if new_len > A::CAPACITY {
937 // Note(Lokathor): Technically we don't have to panic here, and we could
938 // just let some other call later on trigger a panic on accident when the
939 // length is wrong. However, it's a lot easier to catch bugs when things
940 // are more "fail-fast".
941 panic!(
942 "ArrayVec::set_len> new length {} exceeds capacity {}",
943 new_len,
944 A::CAPACITY
945 )
946 }
947
948 let new_len: u16 = new_len
949 .try_into()
950 .expect("ArrayVec::set_len> new length is not in range 0..=u16::MAX");
951 self.len = new_len;
952 }
953
954 /// Splits the collection at the point given.
955 ///
956 /// * `[0, at)` stays in this vec
957 /// * `[at, len)` ends up in the new vec.
958 ///
959 /// ## Panics
960 /// * if at > len
961 ///
962 /// ## Example
963 ///
964 /// ```rust
965 /// # use tinyvec::*;
966 /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
967 /// let av2 = av.split_off(1);
968 /// assert_eq!(&av[..], [1]);
969 /// assert_eq!(&av2[..], [2, 3]);
970 /// ```
971 #[inline]
972 pub fn split_off(&mut self, at: usize) -> Self {
973 // FIXME: should this just use drain into the output?
974 if at > self.len() {
975 panic!(
976 "ArrayVec::split_off> at value {} exceeds length of {}",
977 at, self.len
978 );
979 }
980 let mut new = Self::default();
981 let moves = &mut self.as_mut_slice()[at..];
982 let split_len = moves.len();
983 let targets = &mut new.data.as_slice_mut()[..split_len];
984 moves.swap_with_slice(targets);
985
986 /* moves.len() <= u16::MAX, so these are surely in u16 range */
987 new.len = split_len as u16;
988 self.len = at as u16;
989 new
990 }
991
992 /// Creates a splicing iterator that removes the specified range in the
993 /// vector, yields the removed items, and replaces them with elements from
994 /// the provided iterator.
995 ///
996 /// `splice` fuses the provided iterator, so elements after the first `None`
997 /// are ignored.
998 ///
999 /// ## Panics
1000 /// * If the start is greater than the end.
1001 /// * If the end is past the edge of the vec.
1002 /// * If the provided iterator panics.
1003 /// * If the new length would overflow the capacity of the array. Because
1004 /// `ArrayVecSplice` adds elements to this vec in its destructor when
1005 /// necessary, this panic would occur when it is dropped.
1006 ///
1007 /// ## Example
1008 /// ```rust
1009 /// use tinyvec::*;
1010 /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
1011 /// let av2: ArrayVec<[i32; 4]> = av.splice(1.., 4..=6).collect();
1012 /// assert_eq!(av.as_slice(), &[1, 4, 5, 6][..]);
1013 /// assert_eq!(av2.as_slice(), &[2, 3][..]);
1014 ///
1015 /// av.splice(.., None);
1016 /// assert_eq!(av.as_slice(), &[]);
1017 /// ```
1018 #[inline]
1019 pub fn splice<R, I>(
1020 &mut self, range: R, replacement: I,
1021 ) -> ArrayVecSplice<'_, A, core::iter::Fuse<I::IntoIter>>
1022 where
1023 R: RangeBounds<usize>,
1024 I: IntoIterator<Item = A::Item>,
1025 {
1026 use core::ops::Bound;
1027 let start = match range.start_bound() {
1028 Bound::Included(x) => *x,
1029 Bound::Excluded(x) => x.saturating_add(1),
1030 Bound::Unbounded => 0,
1031 };
1032 let end = match range.end_bound() {
1033 Bound::Included(x) => x.saturating_add(1),
1034 Bound::Excluded(x) => *x,
1035 Bound::Unbounded => self.len(),
1036 };
1037 assert!(
1038 start <= end,
1039 "ArrayVec::splice> Illegal range, {} to {}",
1040 start,
1041 end
1042 );
1043 assert!(
1044 end <= self.len(),
1045 "ArrayVec::splice> Range ends at {} but length is only {}!",
1046 end,
1047 self.len()
1048 );
1049
1050 ArrayVecSplice {
1051 removal_start: start,
1052 removal_end: end,
1053 parent: self,
1054 replacement: replacement.into_iter().fuse(),
1055 }
1056 }
1057
1058 /// Remove an element, swapping the end of the vec into its place.
1059 ///
1060 /// ## Panics
1061 /// * If the index is out of bounds.
1062 ///
1063 /// ## Example
1064 /// ```rust
1065 /// # use tinyvec::*;
1066 /// let mut av = array_vec!([&str; 4] => "foo", "bar", "quack", "zap");
1067 ///
1068 /// assert_eq!(av.swap_remove(1), "bar");
1069 /// assert_eq!(&av[..], ["foo", "zap", "quack"]);
1070 ///
1071 /// assert_eq!(av.swap_remove(0), "foo");
1072 /// assert_eq!(&av[..], ["quack", "zap"]);
1073 /// ```
1074 #[inline]
1075 pub fn swap_remove(&mut self, index: usize) -> A::Item {
1076 assert!(
1077 index < self.len(),
1078 "ArrayVec::swap_remove> index {} is out of bounds {}",
1079 index,
1080 self.len
1081 );
1082 if index == self.len() - 1 {
1083 self.pop().unwrap()
1084 } else {
1085 let i = self.pop().unwrap();
1086 replace(&mut self[index], i)
1087 }
1088 }
1089
1090 /// Reduces the vec's length to the given value.
1091 ///
1092 /// If the vec is already shorter than the input, nothing happens.
1093 #[inline]
1094 pub fn truncate(&mut self, new_len: usize) {
1095 if new_len >= self.len as usize {
1096 return;
1097 }
1098
1099 if needs_drop::<A::Item>() {
1100 let len = self.len as usize;
1101 self.data.as_slice_mut()[new_len..len]
1102 .iter_mut()
1103 .map(core::mem::take)
1104 .for_each(drop);
1105 }
1106
1107 /* new_len is less than self.len */
1108 self.len = new_len as u16;
1109 }
1110
1111 /// Wraps an array, using the given length as the starting length.
1112 ///
1113 /// If you want to use the whole length of the array, you can just use the
1114 /// `From` impl.
1115 ///
1116 /// ## Failure
1117 ///
1118 /// If the given length is greater than the capacity of the array this will
1119 /// error, and you'll get the array back in the `Err`.
1120 #[inline]
1121 #[cfg(not(feature = "latest_stable_rust"))]
1122 pub fn try_from_array_len(data: A, len: usize) -> Result<Self, A> {
1123 /* Note(Soveu): Should we allow A::CAPACITY > u16::MAX for now? */
1124 if len <= A::CAPACITY {
1125 Ok(Self { data, len: len as u16 })
1126 } else {
1127 Err(data)
1128 }
1129 }
1130
1131 /// Wraps an array, using the given length as the starting length.
1132 ///
1133 /// If you want to use the whole length of the array, you can just use the
1134 /// `From` impl.
1135 ///
1136 /// ## Failure
1137 ///
1138 /// If the given length is greater than the capacity of the array this will
1139 /// error, and you'll get the array back in the `Err`.
1140 #[inline]
1141 #[cfg(feature = "latest_stable_rust")]
1142 pub const fn try_from_array_len(data: A, len: usize) -> Result<Self, A> {
1143 /* Note(Soveu): Should we allow A::CAPACITY > u16::MAX for now? */
1144 if len <= A::CAPACITY {
1145 Ok(Self { data, len: len as u16 })
1146 } else {
1147 Err(data)
1148 }
1149 }
1150}
1151
1152impl<A> ArrayVec<A> {
1153 /// Wraps up an array as a new empty `ArrayVec`.
1154 ///
1155 /// If you want to simply use the full array, use `from` instead.
1156 ///
1157 /// ## Examples
1158 ///
1159 /// This method in particular allows to create values for statics:
1160 ///
1161 /// ```rust
1162 /// # use tinyvec::ArrayVec;
1163 /// static DATA: ArrayVec<[u8; 5]> = ArrayVec::from_array_empty([0; 5]);
1164 /// assert_eq!(DATA.len(), 0);
1165 /// ```
1166 ///
1167 /// But of course it is just an normal empty `ArrayVec`:
1168 ///
1169 /// ```rust
1170 /// # use tinyvec::ArrayVec;
1171 /// let mut data = ArrayVec::from_array_empty([1, 2, 3, 4]);
1172 /// assert_eq!(&data[..], &[]);
1173 /// data.push(42);
1174 /// assert_eq!(&data[..], &[42]);
1175 /// ```
1176 #[inline]
1177 #[must_use]
1178 pub const fn from_array_empty(data: A) -> Self {
1179 Self { data, len: 0 }
1180 }
1181}
1182
1183#[cfg(feature = "grab_spare_slice")]
1184impl<A: Array> ArrayVec<A> {
1185 /// Obtain the shared slice of the array _after_ the active memory.
1186 ///
1187 /// ## Example
1188 /// ```rust
1189 /// # use tinyvec::*;
1190 /// let mut av = array_vec!([i32; 4]);
1191 /// assert_eq!(av.grab_spare_slice().len(), 4);
1192 /// av.push(10);
1193 /// av.push(11);
1194 /// av.push(12);
1195 /// av.push(13);
1196 /// assert_eq!(av.grab_spare_slice().len(), 0);
1197 /// ```
1198 #[inline(always)]
1199 pub fn grab_spare_slice(&self) -> &[A::Item] {
1200 &self.data.as_slice()[self.len as usize..]
1201 }
1202
1203 /// Obtain the mutable slice of the array _after_ the active memory.
1204 ///
1205 /// ## Example
1206 /// ```rust
1207 /// # use tinyvec::*;
1208 /// let mut av = array_vec!([i32; 4]);
1209 /// assert_eq!(av.grab_spare_slice_mut().len(), 4);
1210 /// av.push(10);
1211 /// av.push(11);
1212 /// assert_eq!(av.grab_spare_slice_mut().len(), 2);
1213 /// ```
1214 #[inline(always)]
1215 pub fn grab_spare_slice_mut(&mut self) -> &mut [A::Item] {
1216 &mut self.data.as_slice_mut()[self.len as usize..]
1217 }
1218}
1219
1220#[cfg(feature = "nightly_slice_partition_dedup")]
1221impl<A: Array> ArrayVec<A> {
1222 /// De-duplicates the vec contents.
1223 #[inline(always)]
1224 pub fn dedup(&mut self)
1225 where
1226 A::Item: PartialEq,
1227 {
1228 self.dedup_by(|a, b| a == b)
1229 }
1230
1231 /// De-duplicates the vec according to the predicate given.
1232 #[inline(always)]
1233 pub fn dedup_by<F>(&mut self, same_bucket: F)
1234 where
1235 F: FnMut(&mut A::Item, &mut A::Item) -> bool,
1236 {
1237 let len = {
1238 let (dedup, _) = self.as_mut_slice().partition_dedup_by(same_bucket);
1239 dedup.len()
1240 };
1241 self.truncate(len);
1242 }
1243
1244 /// De-duplicates the vec according to the key selector given.
1245 #[inline(always)]
1246 pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1247 where
1248 F: FnMut(&mut A::Item) -> K,
1249 K: PartialEq,
1250 {
1251 self.dedup_by(|a, b| key(a) == key(b))
1252 }
1253}
1254
1255impl<A> ArrayVec<A> {
1256 /// Returns the reference to the inner array of the `ArrayVec`.
1257 ///
1258 /// This returns the full array, even if the `ArrayVec` length is currently
1259 /// less than that.
1260 #[inline(always)]
1261 #[must_use]
1262 pub const fn as_inner(&self) -> &A {
1263 &self.data
1264 }
1265}
1266
1267/// Splicing iterator for `ArrayVec`
1268/// See [`ArrayVec::splice`](ArrayVec::<A>::splice)
1269pub struct ArrayVecSplice<'p, A: Array, I: Iterator<Item = A::Item>> {
1270 parent: &'p mut ArrayVec<A>,
1271 removal_start: usize,
1272 removal_end: usize,
1273 replacement: I,
1274}
1275
1276impl<'p, A: Array, I: Iterator<Item = A::Item>> Iterator
1277 for ArrayVecSplice<'p, A, I>
1278{
1279 type Item = A::Item;
1280
1281 #[inline]
1282 fn next(&mut self) -> Option<A::Item> {
1283 if self.removal_start < self.removal_end {
1284 match self.replacement.next() {
1285 Some(replacement) => {
1286 let removed = core::mem::replace(
1287 &mut self.parent[self.removal_start],
1288 replacement,
1289 );
1290 self.removal_start += 1;
1291 Some(removed)
1292 }
1293 None => {
1294 let removed = self.parent.remove(self.removal_start);
1295 self.removal_end -= 1;
1296 Some(removed)
1297 }
1298 }
1299 } else {
1300 None
1301 }
1302 }
1303
1304 #[inline]
1305 fn size_hint(&self) -> (usize, Option<usize>) {
1306 let len = self.len();
1307 (len, Some(len))
1308 }
1309}
1310
1311impl<'p, A, I> ExactSizeIterator for ArrayVecSplice<'p, A, I>
1312where
1313 A: Array,
1314 I: Iterator<Item = A::Item>,
1315{
1316 #[inline]
1317 fn len(&self) -> usize {
1318 self.removal_end - self.removal_start
1319 }
1320}
1321
1322impl<'p, A, I> FusedIterator for ArrayVecSplice<'p, A, I>
1323where
1324 A: Array,
1325 I: Iterator<Item = A::Item>,
1326{
1327}
1328
1329impl<'p, A, I> DoubleEndedIterator for ArrayVecSplice<'p, A, I>
1330where
1331 A: Array,
1332 I: Iterator<Item = A::Item> + DoubleEndedIterator,
1333{
1334 #[inline]
1335 fn next_back(&mut self) -> Option<A::Item> {
1336 if self.removal_start < self.removal_end {
1337 match self.replacement.next_back() {
1338 Some(replacement: ::Item) => {
1339 let removed: ::Item = core::mem::replace(
1340 &mut self.parent[self.removal_end - 1],
1341 src:replacement,
1342 );
1343 self.removal_end -= 1;
1344 Some(removed)
1345 }
1346 None => {
1347 let removed: ::Item = self.parent.remove(self.removal_end - 1);
1348 self.removal_end -= 1;
1349 Some(removed)
1350 }
1351 }
1352 } else {
1353 None
1354 }
1355 }
1356}
1357
1358impl<'p, A: Array, I: Iterator<Item = A::Item>> Drop
1359 for ArrayVecSplice<'p, A, I>
1360{
1361 #[inline]
1362 fn drop(&mut self) {
1363 for _ in self.by_ref() {}
1364
1365 // FIXME: reserve lower bound of size_hint
1366
1367 for replacement: ::Item in self.replacement.by_ref() {
1368 self.parent.insert(self.removal_end, item:replacement);
1369 self.removal_end += 1;
1370 }
1371 }
1372}
1373
1374impl<A: Array> AsMut<[A::Item]> for ArrayVec<A> {
1375 #[inline(always)]
1376 #[must_use]
1377 fn as_mut(&mut self) -> &mut [A::Item] {
1378 &mut *self
1379 }
1380}
1381
1382impl<A: Array> AsRef<[A::Item]> for ArrayVec<A> {
1383 #[inline(always)]
1384 #[must_use]
1385 fn as_ref(&self) -> &[A::Item] {
1386 &*self
1387 }
1388}
1389
1390impl<A: Array> Borrow<[A::Item]> for ArrayVec<A> {
1391 #[inline(always)]
1392 #[must_use]
1393 fn borrow(&self) -> &[A::Item] {
1394 &*self
1395 }
1396}
1397
1398impl<A: Array> BorrowMut<[A::Item]> for ArrayVec<A> {
1399 #[inline(always)]
1400 #[must_use]
1401 fn borrow_mut(&mut self) -> &mut [A::Item] {
1402 &mut *self
1403 }
1404}
1405
1406impl<A: Array> Extend<A::Item> for ArrayVec<A> {
1407 #[inline]
1408 fn extend<T: IntoIterator<Item = A::Item>>(&mut self, iter: T) {
1409 for t: ::Item in iter {
1410 self.push(val:t)
1411 }
1412 }
1413}
1414
1415impl<A: Array> From<A> for ArrayVec<A> {
1416 #[inline(always)]
1417 #[must_use]
1418 /// The output has a length equal to the full array.
1419 ///
1420 /// If you want to select a length, use
1421 /// [`from_array_len`](ArrayVec::from_array_len)
1422 fn from(data: A) -> Self {
1423 let len: u16 = data
1424 .as_slice()
1425 .len()
1426 .try_into()
1427 .expect(msg:"ArrayVec::from> length must be in range 0..=u16::MAX");
1428 Self { len, data }
1429 }
1430}
1431
1432/// The error type returned when a conversion from a slice to an [`ArrayVec`]
1433/// fails.
1434#[derive(Debug, Copy, Clone)]
1435pub struct TryFromSliceError(());
1436
1437impl core::fmt::Display for TryFromSliceError {
1438 #[inline]
1439 fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
1440 f.write_str(data:"could not convert slice to ArrayVec")
1441 }
1442}
1443
1444#[cfg(feature = "std")]
1445impl std::error::Error for TryFromSliceError {}
1446
1447impl<T, A> TryFrom<&'_ [T]> for ArrayVec<A>
1448where
1449 T: Clone + Default,
1450 A: Array<Item = T>,
1451{
1452 type Error = TryFromSliceError;
1453
1454 #[inline]
1455 /// The output has a length equal to that of the slice, with the same capacity
1456 /// as `A`.
1457 fn try_from(slice: &[T]) -> Result<Self, Self::Error> {
1458 if slice.len() > A::CAPACITY {
1459 Err(TryFromSliceError(()))
1460 } else {
1461 let mut arr: ArrayVec = ArrayVec::new();
1462 // We do not use ArrayVec::extend_from_slice, because it looks like LLVM
1463 // fails to deduplicate all the length-checking logic between the
1464 // above if and the contents of that method, thus producing much
1465 // slower code. Unlike many of the other optimizations in this
1466 // crate, this one is worth keeping an eye on. I see no reason, for
1467 // any element type, that these should produce different code. But
1468 // they do. (rustc 1.51.0)
1469 arr.set_len(new_len:slice.len());
1470 arr.as_mut_slice().clone_from_slice(src:slice);
1471 Ok(arr)
1472 }
1473 }
1474}
1475
1476impl<A: Array> FromIterator<A::Item> for ArrayVec<A> {
1477 #[inline]
1478 #[must_use]
1479 fn from_iter<T: IntoIterator<Item = A::Item>>(iter: T) -> Self {
1480 let mut av: ArrayVec = Self::default();
1481 for i: ::Item in iter {
1482 av.push(val:i)
1483 }
1484 av
1485 }
1486}
1487
1488/// Iterator for consuming an `ArrayVec` and returning owned elements.
1489pub struct ArrayVecIterator<A: Array> {
1490 base: u16,
1491 tail: u16,
1492 data: A,
1493}
1494
1495impl<A: Array> ArrayVecIterator<A> {
1496 /// Returns the remaining items of this iterator as a slice.
1497 #[inline]
1498 #[must_use]
1499 pub fn as_slice(&self) -> &[A::Item] {
1500 &self.data.as_slice()[self.base as usize..self.tail as usize]
1501 }
1502}
1503impl<A: Array> FusedIterator for ArrayVecIterator<A> {}
1504impl<A: Array> Iterator for ArrayVecIterator<A> {
1505 type Item = A::Item;
1506 #[inline]
1507 fn next(&mut self) -> Option<Self::Item> {
1508 let slice =
1509 &mut self.data.as_slice_mut()[self.base as usize..self.tail as usize];
1510 let itemref = slice.first_mut()?;
1511 self.base += 1;
1512 return Some(core::mem::take(itemref));
1513 }
1514 #[inline(always)]
1515 #[must_use]
1516 fn size_hint(&self) -> (usize, Option<usize>) {
1517 let s = self.tail - self.base;
1518 let s = s as usize;
1519 (s, Some(s))
1520 }
1521 #[inline(always)]
1522 fn count(self) -> usize {
1523 self.size_hint().0
1524 }
1525 #[inline]
1526 fn last(mut self) -> Option<Self::Item> {
1527 self.next_back()
1528 }
1529 #[inline]
1530 fn nth(&mut self, n: usize) -> Option<A::Item> {
1531 let slice = &mut self.data.as_slice_mut();
1532 let slice = &mut slice[self.base as usize..self.tail as usize];
1533
1534 if let Some(x) = slice.get_mut(n) {
1535 /* n is in range [0 .. self.tail - self.base) so in u16 range */
1536 self.base += n as u16 + 1;
1537 return Some(core::mem::take(x));
1538 }
1539
1540 self.base = self.tail;
1541 return None;
1542 }
1543}
1544
1545impl<A: Array> DoubleEndedIterator for ArrayVecIterator<A> {
1546 #[inline]
1547 fn next_back(&mut self) -> Option<Self::Item> {
1548 let slice =
1549 &mut self.data.as_slice_mut()[self.base as usize..self.tail as usize];
1550 let item = slice.last_mut()?;
1551 self.tail -= 1;
1552 return Some(core::mem::take(item));
1553 }
1554
1555 #[inline]
1556 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1557 let base = self.base as usize;
1558 let tail = self.tail as usize;
1559 let slice = &mut self.data.as_slice_mut()[base..tail];
1560 let n = n.saturating_add(1);
1561
1562 if let Some(n) = slice.len().checked_sub(n) {
1563 let item = &mut slice[n];
1564 /* n is in [0..self.tail - self.base] range, so in u16 range */
1565 self.tail = self.base + n as u16;
1566 return Some(core::mem::take(item));
1567 }
1568
1569 self.tail = self.base;
1570 return None;
1571 }
1572}
1573
1574impl<A: Array> ExactSizeIterator for ArrayVecIterator<A> {
1575 #[inline]
1576 fn len(&self) -> usize {
1577 self.size_hint().0
1578 }
1579}
1580
1581impl<A: Array> Debug for ArrayVecIterator<A>
1582where
1583 A::Item: Debug,
1584{
1585 #[allow(clippy::missing_inline_in_public_items)]
1586 fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
1587 f.debug_tuple(name:"ArrayVecIterator").field(&self.as_slice()).finish()
1588 }
1589}
1590
1591impl<A: Array> IntoIterator for ArrayVec<A> {
1592 type Item = A::Item;
1593 type IntoIter = ArrayVecIterator<A>;
1594 #[inline(always)]
1595 #[must_use]
1596 fn into_iter(self) -> Self::IntoIter {
1597 ArrayVecIterator { base: 0, tail: self.len, data: self.data }
1598 }
1599}
1600
1601impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> {
1602 type Item = &'a mut A::Item;
1603 type IntoIter = core::slice::IterMut<'a, A::Item>;
1604 #[inline(always)]
1605 #[must_use]
1606 fn into_iter(self) -> Self::IntoIter {
1607 self.iter_mut()
1608 }
1609}
1610
1611impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> {
1612 type Item = &'a A::Item;
1613 type IntoIter = core::slice::Iter<'a, A::Item>;
1614 #[inline(always)]
1615 #[must_use]
1616 fn into_iter(self) -> Self::IntoIter {
1617 self.iter()
1618 }
1619}
1620
1621impl<A: Array> PartialEq for ArrayVec<A>
1622where
1623 A::Item: PartialEq,
1624{
1625 #[inline]
1626 #[must_use]
1627 fn eq(&self, other: &Self) -> bool {
1628 self.as_slice().eq(other.as_slice())
1629 }
1630}
1631impl<A: Array> Eq for ArrayVec<A> where A::Item: Eq {}
1632
1633impl<A: Array> PartialOrd for ArrayVec<A>
1634where
1635 A::Item: PartialOrd,
1636{
1637 #[inline]
1638 #[must_use]
1639 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
1640 self.as_slice().partial_cmp(other.as_slice())
1641 }
1642}
1643impl<A: Array> Ord for ArrayVec<A>
1644where
1645 A::Item: Ord,
1646{
1647 #[inline]
1648 #[must_use]
1649 fn cmp(&self, other: &Self) -> core::cmp::Ordering {
1650 self.as_slice().cmp(other.as_slice())
1651 }
1652}
1653
1654impl<A: Array> PartialEq<&A> for ArrayVec<A>
1655where
1656 A::Item: PartialEq,
1657{
1658 #[inline]
1659 #[must_use]
1660 fn eq(&self, other: &&A) -> bool {
1661 self.as_slice().eq(other.as_slice())
1662 }
1663}
1664
1665impl<A: Array> PartialEq<&[A::Item]> for ArrayVec<A>
1666where
1667 A::Item: PartialEq,
1668{
1669 #[inline]
1670 #[must_use]
1671 fn eq(&self, other: &&[A::Item]) -> bool {
1672 self.as_slice().eq(*other)
1673 }
1674}
1675
1676impl<A: Array> Hash for ArrayVec<A>
1677where
1678 A::Item: Hash,
1679{
1680 #[inline]
1681 fn hash<H: Hasher>(&self, state: &mut H) {
1682 self.as_slice().hash(state)
1683 }
1684}
1685
1686#[cfg(feature = "experimental_write_impl")]
1687impl<A: Array<Item = u8>> core::fmt::Write for ArrayVec<A> {
1688 fn write_str(&mut self, s: &str) -> core::fmt::Result {
1689 let my_len = self.len();
1690 let str_len = s.as_bytes().len();
1691 if my_len + str_len <= A::CAPACITY {
1692 let remainder = &mut self.data.as_slice_mut()[my_len..];
1693 let target = &mut remainder[..str_len];
1694 target.copy_from_slice(s.as_bytes());
1695 Ok(())
1696 } else {
1697 Err(core::fmt::Error)
1698 }
1699 }
1700}
1701
1702// // // // // // // //
1703// Formatting impls
1704// // // // // // // //
1705
1706impl<A: Array> Binary for ArrayVec<A>
1707where
1708 A::Item: Binary,
1709{
1710 #[allow(clippy::missing_inline_in_public_items)]
1711 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1712 write!(f, "[")?;
1713 if f.alternate() {
1714 write!(f, "\n ")?;
1715 }
1716 for (i: usize, elem: &impl Binary) in self.iter().enumerate() {
1717 if i > 0 {
1718 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1719 }
1720 Binary::fmt(self:elem, f)?;
1721 }
1722 if f.alternate() {
1723 write!(f, ",\n")?;
1724 }
1725 write!(f, "]")
1726 }
1727}
1728
1729impl<A: Array> Debug for ArrayVec<A>
1730where
1731 A::Item: Debug,
1732{
1733 #[allow(clippy::missing_inline_in_public_items)]
1734 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1735 write!(f, "[")?;
1736 if f.alternate() && !self.is_empty() {
1737 write!(f, "\n ")?;
1738 }
1739 for (i: usize, elem: &impl Debug) in self.iter().enumerate() {
1740 if i > 0 {
1741 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1742 }
1743 Debug::fmt(self:elem, f)?;
1744 }
1745 if f.alternate() && !self.is_empty() {
1746 write!(f, ",\n")?;
1747 }
1748 write!(f, "]")
1749 }
1750}
1751
1752impl<A: Array> Display for ArrayVec<A>
1753where
1754 A::Item: Display,
1755{
1756 #[allow(clippy::missing_inline_in_public_items)]
1757 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1758 write!(f, "[")?;
1759 if f.alternate() {
1760 write!(f, "\n ")?;
1761 }
1762 for (i: usize, elem: &impl Display) in self.iter().enumerate() {
1763 if i > 0 {
1764 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1765 }
1766 Display::fmt(self:elem, f)?;
1767 }
1768 if f.alternate() {
1769 write!(f, ",\n")?;
1770 }
1771 write!(f, "]")
1772 }
1773}
1774
1775impl<A: Array> LowerExp for ArrayVec<A>
1776where
1777 A::Item: LowerExp,
1778{
1779 #[allow(clippy::missing_inline_in_public_items)]
1780 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1781 write!(f, "[")?;
1782 if f.alternate() {
1783 write!(f, "\n ")?;
1784 }
1785 for (i: usize, elem: &impl LowerExp) in self.iter().enumerate() {
1786 if i > 0 {
1787 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1788 }
1789 LowerExp::fmt(self:elem, f)?;
1790 }
1791 if f.alternate() {
1792 write!(f, ",\n")?;
1793 }
1794 write!(f, "]")
1795 }
1796}
1797
1798impl<A: Array> LowerHex for ArrayVec<A>
1799where
1800 A::Item: LowerHex,
1801{
1802 #[allow(clippy::missing_inline_in_public_items)]
1803 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1804 write!(f, "[")?;
1805 if f.alternate() {
1806 write!(f, "\n ")?;
1807 }
1808 for (i: usize, elem: &impl LowerHex) in self.iter().enumerate() {
1809 if i > 0 {
1810 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1811 }
1812 LowerHex::fmt(self:elem, f)?;
1813 }
1814 if f.alternate() {
1815 write!(f, ",\n")?;
1816 }
1817 write!(f, "]")
1818 }
1819}
1820
1821impl<A: Array> Octal for ArrayVec<A>
1822where
1823 A::Item: Octal,
1824{
1825 #[allow(clippy::missing_inline_in_public_items)]
1826 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1827 write!(f, "[")?;
1828 if f.alternate() {
1829 write!(f, "\n ")?;
1830 }
1831 for (i: usize, elem: &impl Octal) in self.iter().enumerate() {
1832 if i > 0 {
1833 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1834 }
1835 Octal::fmt(self:elem, f)?;
1836 }
1837 if f.alternate() {
1838 write!(f, ",\n")?;
1839 }
1840 write!(f, "]")
1841 }
1842}
1843
1844impl<A: Array> Pointer for ArrayVec<A>
1845where
1846 A::Item: Pointer,
1847{
1848 #[allow(clippy::missing_inline_in_public_items)]
1849 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1850 write!(f, "[")?;
1851 if f.alternate() {
1852 write!(f, "\n ")?;
1853 }
1854 for (i: usize, elem: &impl Pointer) in self.iter().enumerate() {
1855 if i > 0 {
1856 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1857 }
1858 Pointer::fmt(self:elem, f)?;
1859 }
1860 if f.alternate() {
1861 write!(f, ",\n")?;
1862 }
1863 write!(f, "]")
1864 }
1865}
1866
1867impl<A: Array> UpperExp for ArrayVec<A>
1868where
1869 A::Item: UpperExp,
1870{
1871 #[allow(clippy::missing_inline_in_public_items)]
1872 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1873 write!(f, "[")?;
1874 if f.alternate() {
1875 write!(f, "\n ")?;
1876 }
1877 for (i: usize, elem: &impl UpperExp) in self.iter().enumerate() {
1878 if i > 0 {
1879 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1880 }
1881 UpperExp::fmt(self:elem, f)?;
1882 }
1883 if f.alternate() {
1884 write!(f, ",\n")?;
1885 }
1886 write!(f, "]")
1887 }
1888}
1889
1890impl<A: Array> UpperHex for ArrayVec<A>
1891where
1892 A::Item: UpperHex,
1893{
1894 #[allow(clippy::missing_inline_in_public_items)]
1895 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1896 write!(f, "[")?;
1897 if f.alternate() {
1898 write!(f, "\n ")?;
1899 }
1900 for (i: usize, elem: &impl UpperHex) in self.iter().enumerate() {
1901 if i > 0 {
1902 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1903 }
1904 UpperHex::fmt(self:elem, f)?;
1905 }
1906 if f.alternate() {
1907 write!(f, ",\n")?;
1908 }
1909 write!(f, "]")
1910 }
1911}
1912
1913#[cfg(feature = "alloc")]
1914use alloc::vec::Vec;
1915
1916#[cfg(all(feature = "alloc", feature = "rustc_1_57"))]
1917use alloc::collections::TryReserveError;
1918
1919#[cfg(feature = "alloc")]
1920impl<A: Array> ArrayVec<A> {
1921 /// Drains all elements to a Vec, but reserves additional space
1922 /// ```
1923 /// # use tinyvec::*;
1924 /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1925 /// let v = av.drain_to_vec_and_reserve(10);
1926 /// assert_eq!(v, &[1, 2, 3]);
1927 /// assert_eq!(v.capacity(), 13);
1928 /// ```
1929 #[inline]
1930 pub fn drain_to_vec_and_reserve(&mut self, n: usize) -> Vec<A::Item> {
1931 let cap = n + self.len();
1932 let mut v = Vec::with_capacity(cap);
1933 let iter = self.iter_mut().map(core::mem::take);
1934 v.extend(iter);
1935 self.set_len(0);
1936 return v;
1937 }
1938
1939 /// Tries to drain all elements to a Vec, but reserves additional space.
1940 ///
1941 /// # Errors
1942 ///
1943 /// If the allocator reports a failure, then an error is returned.
1944 ///
1945 /// ```
1946 /// # use tinyvec::*;
1947 /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1948 /// let v = av.try_drain_to_vec_and_reserve(10);
1949 /// assert!(matches!(v, Ok(_)));
1950 /// let v = v.unwrap();
1951 /// assert_eq!(v, &[1, 2, 3]);
1952 /// assert_eq!(v.capacity(), 13);
1953 /// ```
1954 #[inline]
1955 #[cfg(feature = "rustc_1_57")]
1956 pub fn try_drain_to_vec_and_reserve(
1957 &mut self, n: usize,
1958 ) -> Result<Vec<A::Item>, TryReserveError> {
1959 let cap = n + self.len();
1960 let mut v = Vec::new();
1961 v.try_reserve(cap)?;
1962 let iter = self.iter_mut().map(core::mem::take);
1963 v.extend(iter);
1964 self.set_len(0);
1965 return Ok(v);
1966 }
1967
1968 /// Drains all elements to a Vec
1969 /// ```
1970 /// # use tinyvec::*;
1971 /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1972 /// let v = av.drain_to_vec();
1973 /// assert_eq!(v, &[1, 2, 3]);
1974 /// assert_eq!(v.capacity(), 3);
1975 /// ```
1976 #[inline]
1977 pub fn drain_to_vec(&mut self) -> Vec<A::Item> {
1978 self.drain_to_vec_and_reserve(0)
1979 }
1980
1981 /// Tries to drain all elements to a Vec.
1982 ///
1983 /// # Errors
1984 ///
1985 /// If the allocator reports a failure, then an error is returned.
1986 ///
1987 /// ```
1988 /// # use tinyvec::*;
1989 /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1990 /// let v = av.try_drain_to_vec();
1991 /// assert!(matches!(v, Ok(_)));
1992 /// let v = v.unwrap();
1993 /// assert_eq!(v, &[1, 2, 3]);
1994 /// // Vec may reserve more than necessary in order to prevent more future allocations.
1995 /// assert!(v.capacity() >= 3);
1996 /// ```
1997 #[inline]
1998 #[cfg(feature = "rustc_1_57")]
1999 pub fn try_drain_to_vec(&mut self) -> Result<Vec<A::Item>, TryReserveError> {
2000 self.try_drain_to_vec_and_reserve(0)
2001 }
2002}
2003
2004#[cfg(feature = "serde")]
2005struct ArrayVecVisitor<A: Array>(PhantomData<A>);
2006
2007#[cfg(feature = "serde")]
2008impl<'de, A: Array> Visitor<'de> for ArrayVecVisitor<A>
2009where
2010 A::Item: Deserialize<'de>,
2011{
2012 type Value = ArrayVec<A>;
2013
2014 fn expecting(
2015 &self, formatter: &mut core::fmt::Formatter,
2016 ) -> core::fmt::Result {
2017 formatter.write_str("a sequence")
2018 }
2019
2020 fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
2021 where
2022 S: SeqAccess<'de>,
2023 {
2024 let mut new_arrayvec: ArrayVec<A> = Default::default();
2025
2026 let mut idx = 0usize;
2027 while let Some(value) = seq.next_element()? {
2028 if new_arrayvec.len() >= new_arrayvec.capacity() {
2029 return Err(DeserializeError::invalid_length(idx, &self));
2030 }
2031 new_arrayvec.push(value);
2032 idx = idx + 1;
2033 }
2034
2035 Ok(new_arrayvec)
2036 }
2037}
2038
2039#[cfg(test)]
2040mod test {
2041 use super::*;
2042
2043 #[test]
2044 fn retain_mut_empty_vec() {
2045 let mut av: ArrayVec<[i32; 4]> = ArrayVec::new();
2046 av.retain_mut(|&mut x| x % 2 == 0);
2047 assert_eq!(av.len(), 0);
2048 }
2049
2050 #[test]
2051 fn retain_mut_all_elements() {
2052 let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 2, 4, 6, 8);
2053 av.retain_mut(|&mut x| x % 2 == 0);
2054 assert_eq!(av.len(), 4);
2055 assert_eq!(av.as_slice(), &[2, 4, 6, 8]);
2056 }
2057
2058 #[test]
2059 fn retain_mut_some_elements() {
2060 let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 1, 2, 3, 4);
2061 av.retain_mut(|&mut x| x % 2 == 0);
2062 assert_eq!(av.len(), 2);
2063 assert_eq!(av.as_slice(), &[2, 4]);
2064 }
2065
2066 #[test]
2067 fn retain_mut_no_elements() {
2068 let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 1, 3, 5, 7);
2069 av.retain_mut(|&mut x| x % 2 == 0);
2070 assert_eq!(av.len(), 0);
2071 }
2072
2073 #[test]
2074 fn retain_mut_zero_capacity() {
2075 let mut av: ArrayVec<[i32; 0]> = ArrayVec::new();
2076 av.retain_mut(|&mut x| x % 2 == 0);
2077 assert_eq!(av.len(), 0);
2078 }
2079}
2080