tinyvec/
tinyvec.rs

1use super::*;
2
3use alloc::vec::{self, Vec};
4use core::convert::TryFrom;
5use tinyvec_macros::impl_mirrored;
6
7#[cfg(feature = "rustc_1_57")]
8use alloc::collections::TryReserveError;
9
10#[cfg(feature = "serde")]
11use core::marker::PhantomData;
12#[cfg(feature = "serde")]
13use serde::de::{Deserialize, Deserializer, SeqAccess, Visitor};
14#[cfg(feature = "serde")]
15use serde::ser::{Serialize, SerializeSeq, Serializer};
16
17/// Helper to make a `TinyVec`.
18///
19/// You specify the backing array type, and optionally give all the elements you
20/// want to initially place into the array.
21///
22/// ```rust
23/// use tinyvec::*;
24///
25/// // The backing array type can be specified in the macro call
26/// let empty_tv = tiny_vec!([u8; 16]);
27/// let some_ints = tiny_vec!([i32; 4] => 1, 2, 3);
28/// let many_ints = tiny_vec!([i32; 4] => 1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
29///
30/// // Or left to inference
31/// let empty_tv: TinyVec<[u8; 16]> = tiny_vec!();
32/// let some_ints: TinyVec<[i32; 4]> = tiny_vec!(1, 2, 3);
33/// let many_ints: TinyVec<[i32; 4]> = tiny_vec!(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
34/// ```
35#[macro_export]
36#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
37macro_rules! tiny_vec {
38  ($array_type:ty => $($elem:expr),* $(,)?) => {
39    {
40      // https://github.com/rust-lang/lang-team/issues/28
41      const INVOKED_ELEM_COUNT: usize = 0 $( + { let _ = stringify!($elem); 1 })*;
42      // If we have more `$elem` than the `CAPACITY` we will simply go directly
43      // to constructing on the heap.
44      match $crate::TinyVec::constructor_for_capacity(INVOKED_ELEM_COUNT) {
45        $crate::TinyVecConstructor::Inline(f) => {
46          f($crate::array_vec!($array_type => $($elem),*))
47        }
48        $crate::TinyVecConstructor::Heap(f) => {
49          f(vec!($($elem),*))
50        }
51      }
52    }
53  };
54  ($array_type:ty) => {
55    $crate::TinyVec::<$array_type>::default()
56  };
57  ($($elem:expr),*) => {
58    $crate::tiny_vec!(_ => $($elem),*)
59  };
60  ($elem:expr; $n:expr) => {
61    $crate::TinyVec::from([$elem; $n])
62  };
63  () => {
64    $crate::tiny_vec!(_)
65  };
66}
67
68#[doc(hidden)] // Internal implementation details of `tiny_vec!`
69pub enum TinyVecConstructor<A: Array> {
70  Inline(fn(ArrayVec<A>) -> TinyVec<A>),
71  Heap(fn(Vec<A::Item>) -> TinyVec<A>),
72}
73
74/// A vector that starts inline, but can automatically move to the heap.
75///
76/// * Requires the `alloc` feature
77///
78/// A `TinyVec` is either an Inline([`ArrayVec`](crate::ArrayVec::<A>)) or
79/// Heap([`Vec`](https://doc.rust-lang.org/alloc/vec/struct.Vec.html)). The
80/// interface for the type as a whole is a bunch of methods that just match on
81/// the enum variant and then call the same method on the inner vec.
82///
83/// ## Construction
84///
85/// Because it's an enum, you can construct a `TinyVec` simply by making an
86/// `ArrayVec` or `Vec` and then putting it into the enum.
87///
88/// There is also a macro
89///
90/// ```rust
91/// # use tinyvec::*;
92/// let empty_tv = tiny_vec!([u8; 16]);
93/// let some_ints = tiny_vec!([i32; 4] => 1, 2, 3);
94/// ```
95#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
96pub enum TinyVec<A: Array> {
97  #[allow(missing_docs)]
98  Inline(ArrayVec<A>),
99  #[allow(missing_docs)]
100  Heap(Vec<A::Item>),
101}
102
103impl<A> Clone for TinyVec<A>
104where
105  A: Array + Clone,
106  A::Item: Clone,
107{
108  #[inline]
109  fn clone(&self) -> Self {
110    match self {
111      TinyVec::Heap(v) => TinyVec::Heap(v.clone()),
112      TinyVec::Inline(v) => TinyVec::Inline(v.clone()),
113    }
114  }
115
116  #[inline]
117  fn clone_from(&mut self, o: &Self) {
118    if o.len() > self.len() {
119      self.reserve(o.len() - self.len());
120    } else {
121      self.truncate(o.len());
122    }
123    let (start, end) = o.split_at(self.len());
124    for (dst, src) in self.iter_mut().zip(start) {
125      dst.clone_from(src);
126    }
127    self.extend_from_slice(end);
128  }
129}
130
131impl<A: Array> Default for TinyVec<A> {
132  #[inline]
133  fn default() -> Self {
134    TinyVec::Inline(ArrayVec::default())
135  }
136}
137
138impl<A: Array> Deref for TinyVec<A> {
139  type Target = [A::Item];
140
141  impl_mirrored! {
142    type Mirror = TinyVec;
143    #[inline(always)]
144    #[must_use]
145    fn deref(self: &Self) -> &Self::Target;
146  }
147}
148
149impl<A: Array> DerefMut for TinyVec<A> {
150  impl_mirrored! {
151    type Mirror = TinyVec;
152    #[inline(always)]
153    #[must_use]
154    fn deref_mut(self: &mut Self) -> &mut Self::Target;
155  }
156}
157
158impl<A: Array, I: SliceIndex<[A::Item]>> Index<I> for TinyVec<A> {
159  type Output = <I as SliceIndex<[A::Item]>>::Output;
160  #[inline(always)]
161  fn index(&self, index: I) -> &Self::Output {
162    &self.deref()[index]
163  }
164}
165
166impl<A: Array, I: SliceIndex<[A::Item]>> IndexMut<I> for TinyVec<A> {
167  #[inline(always)]
168  fn index_mut(&mut self, index: I) -> &mut Self::Output {
169    &mut self.deref_mut()[index]
170  }
171}
172
173#[cfg(feature = "std")]
174#[cfg_attr(docs_rs, doc(cfg(feature = "std")))]
175impl<A: Array<Item = u8>> std::io::Write for TinyVec<A> {
176  #[inline(always)]
177  fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
178    self.extend_from_slice(buf);
179    Ok(buf.len())
180  }
181
182  #[inline(always)]
183  fn flush(&mut self) -> std::io::Result<()> {
184    Ok(())
185  }
186}
187
188#[cfg(feature = "serde")]
189#[cfg_attr(docs_rs, doc(cfg(feature = "serde")))]
190impl<A: Array> Serialize for TinyVec<A>
191where
192  A::Item: Serialize,
193{
194  fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
195  where
196    S: Serializer,
197  {
198    let mut seq = serializer.serialize_seq(Some(self.len()))?;
199    for element in self.iter() {
200      seq.serialize_element(element)?;
201    }
202    seq.end()
203  }
204}
205
206#[cfg(feature = "serde")]
207#[cfg_attr(docs_rs, doc(cfg(feature = "serde")))]
208impl<'de, A: Array> Deserialize<'de> for TinyVec<A>
209where
210  A::Item: Deserialize<'de>,
211{
212  fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
213  where
214    D: Deserializer<'de>,
215  {
216    deserializer.deserialize_seq(TinyVecVisitor(PhantomData))
217  }
218}
219
220#[cfg(feature = "borsh")]
221#[cfg_attr(docs_rs, doc(cfg(feature = "borsh")))]
222impl<A: Array> borsh::BorshSerialize for TinyVec<A>
223where
224  <A as Array>::Item: borsh::BorshSerialize,
225{
226  fn serialize<W: borsh::io::Write>(
227    &self, writer: &mut W,
228  ) -> borsh::io::Result<()> {
229    <usize as borsh::BorshSerialize>::serialize(&self.len(), writer)?;
230    for elem in self.iter() {
231      <<A as Array>::Item as borsh::BorshSerialize>::serialize(elem, writer)?;
232    }
233    Ok(())
234  }
235}
236
237#[cfg(feature = "borsh")]
238#[cfg_attr(docs_rs, doc(cfg(feature = "borsh")))]
239impl<A: Array> borsh::BorshDeserialize for TinyVec<A>
240where
241  <A as Array>::Item: borsh::BorshDeserialize,
242{
243  fn deserialize_reader<R: borsh::io::Read>(
244    reader: &mut R,
245  ) -> borsh::io::Result<Self> {
246    let len = <usize as borsh::BorshDeserialize>::deserialize_reader(reader)?;
247    let mut new_tinyvec = Self::with_capacity(len);
248
249    for _ in 0..len {
250      new_tinyvec.push(
251        <<A as Array>::Item as borsh::BorshDeserialize>::deserialize_reader(
252          reader,
253        )?,
254      )
255    }
256
257    Ok(new_tinyvec)
258  }
259}
260
261#[cfg(feature = "arbitrary")]
262#[cfg_attr(docs_rs, doc(cfg(feature = "arbitrary")))]
263impl<'a, A> arbitrary::Arbitrary<'a> for TinyVec<A>
264where
265  A: Array,
266  A::Item: arbitrary::Arbitrary<'a>,
267{
268  fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
269    let v = Vec::arbitrary(u)?;
270    let mut tv = TinyVec::Heap(v);
271    tv.shrink_to_fit();
272    Ok(tv)
273  }
274}
275
276impl<A: Array> TinyVec<A> {
277  /// Returns whether elements are on heap
278  #[inline(always)]
279  #[must_use]
280  pub fn is_heap(&self) -> bool {
281    match self {
282      TinyVec::Heap(_) => true,
283      TinyVec::Inline(_) => false,
284    }
285  }
286  /// Returns whether elements are on stack
287  #[inline(always)]
288  #[must_use]
289  pub fn is_inline(&self) -> bool {
290    !self.is_heap()
291  }
292
293  /// Shrinks the capacity of the vector as much as possible.\
294  /// It is inlined if length is less than `A::CAPACITY`.
295  /// ```rust
296  /// use tinyvec::*;
297  /// let mut tv = tiny_vec!([i32; 2] => 1, 2, 3);
298  /// assert!(tv.is_heap());
299  /// let _ = tv.pop();
300  /// assert!(tv.is_heap());
301  /// tv.shrink_to_fit();
302  /// assert!(tv.is_inline());
303  /// ```
304  #[inline]
305  pub fn shrink_to_fit(&mut self) {
306    let vec = match self {
307      TinyVec::Inline(_) => return,
308      TinyVec::Heap(h) => h,
309    };
310
311    if vec.len() > A::CAPACITY {
312      return vec.shrink_to_fit();
313    }
314
315    let moved_vec = core::mem::take(vec);
316
317    let mut av = ArrayVec::default();
318    let mut rest = av.fill(moved_vec);
319    debug_assert!(rest.next().is_none());
320    *self = TinyVec::Inline(av);
321  }
322
323  /// Moves the content of the TinyVec to the heap, if it's inline.
324  /// ```rust
325  /// use tinyvec::*;
326  /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3);
327  /// assert!(tv.is_inline());
328  /// tv.move_to_the_heap();
329  /// assert!(tv.is_heap());
330  /// ```
331  #[allow(clippy::missing_inline_in_public_items)]
332  pub fn move_to_the_heap(&mut self) {
333    let arr = match self {
334      TinyVec::Heap(_) => return,
335      TinyVec::Inline(a) => a,
336    };
337
338    let v = arr.drain_to_vec();
339    *self = TinyVec::Heap(v);
340  }
341
342  /// Tries to move the content of the TinyVec to the heap, if it's inline.
343  ///
344  /// # Errors
345  ///
346  /// If the allocator reports a failure, then an error is returned and the
347  /// content is kept on the stack.
348  ///
349  /// ```rust
350  /// use tinyvec::*;
351  /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3);
352  /// assert!(tv.is_inline());
353  /// assert_eq!(Ok(()), tv.try_move_to_the_heap());
354  /// assert!(tv.is_heap());
355  /// ```
356  #[inline]
357  #[cfg(feature = "rustc_1_57")]
358  pub fn try_move_to_the_heap(&mut self) -> Result<(), TryReserveError> {
359    let arr = match self {
360      TinyVec::Heap(_) => return Ok(()),
361      TinyVec::Inline(a) => a,
362    };
363
364    let v = arr.try_drain_to_vec()?;
365    *self = TinyVec::Heap(v);
366    return Ok(());
367  }
368
369  /// If TinyVec is inline, moves the content of it to the heap.
370  /// Also reserves additional space.
371  /// ```rust
372  /// use tinyvec::*;
373  /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3);
374  /// assert!(tv.is_inline());
375  /// tv.move_to_the_heap_and_reserve(32);
376  /// assert!(tv.is_heap());
377  /// assert!(tv.capacity() >= 35);
378  /// ```
379  #[inline]
380  pub fn move_to_the_heap_and_reserve(&mut self, n: usize) {
381    let arr = match self {
382      TinyVec::Heap(h) => return h.reserve(n),
383      TinyVec::Inline(a) => a,
384    };
385
386    let v = arr.drain_to_vec_and_reserve(n);
387    *self = TinyVec::Heap(v);
388  }
389
390  /// If TinyVec is inline, try to move the content of it to the heap.
391  /// Also reserves additional space.
392  ///
393  /// # Errors
394  ///
395  /// If the allocator reports a failure, then an error is returned.
396  ///
397  /// ```rust
398  /// use tinyvec::*;
399  /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3);
400  /// assert!(tv.is_inline());
401  /// assert_eq!(Ok(()), tv.try_move_to_the_heap_and_reserve(32));
402  /// assert!(tv.is_heap());
403  /// assert!(tv.capacity() >= 35);
404  /// ```
405  #[inline]
406  #[cfg(feature = "rustc_1_57")]
407  pub fn try_move_to_the_heap_and_reserve(
408    &mut self, n: usize,
409  ) -> Result<(), TryReserveError> {
410    let arr = match self {
411      TinyVec::Heap(h) => return h.try_reserve(n),
412      TinyVec::Inline(a) => a,
413    };
414
415    let v = arr.try_drain_to_vec_and_reserve(n)?;
416    *self = TinyVec::Heap(v);
417    return Ok(());
418  }
419
420  /// Reserves additional space.
421  /// Moves to the heap if array can't hold `n` more items
422  /// ```rust
423  /// use tinyvec::*;
424  /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3, 4);
425  /// assert!(tv.is_inline());
426  /// tv.reserve(1);
427  /// assert!(tv.is_heap());
428  /// assert!(tv.capacity() >= 5);
429  /// ```
430  #[inline]
431  pub fn reserve(&mut self, n: usize) {
432    let arr = match self {
433      TinyVec::Heap(h) => return h.reserve(n),
434      TinyVec::Inline(a) => a,
435    };
436
437    if n > arr.capacity() - arr.len() {
438      let v = arr.drain_to_vec_and_reserve(n);
439      *self = TinyVec::Heap(v);
440    }
441
442    /* In this place array has enough place, so no work is needed more */
443    return;
444  }
445
446  /// Tries to reserve additional space.
447  /// Moves to the heap if array can't hold `n` more items.
448  ///
449  /// # Errors
450  ///
451  /// If the allocator reports a failure, then an error is returned.
452  ///
453  /// ```rust
454  /// use tinyvec::*;
455  /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3, 4);
456  /// assert!(tv.is_inline());
457  /// assert_eq!(Ok(()), tv.try_reserve(1));
458  /// assert!(tv.is_heap());
459  /// assert!(tv.capacity() >= 5);
460  /// ```
461  #[inline]
462  #[cfg(feature = "rustc_1_57")]
463  pub fn try_reserve(&mut self, n: usize) -> Result<(), TryReserveError> {
464    let arr = match self {
465      TinyVec::Heap(h) => return h.try_reserve(n),
466      TinyVec::Inline(a) => a,
467    };
468
469    if n > arr.capacity() - arr.len() {
470      let v = arr.try_drain_to_vec_and_reserve(n)?;
471      *self = TinyVec::Heap(v);
472    }
473
474    /* In this place array has enough place, so no work is needed more */
475    return Ok(());
476  }
477
478  /// Reserves additional space.
479  /// Moves to the heap if array can't hold `n` more items
480  ///
481  /// From [Vec::reserve_exact](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.reserve_exact)
482  /// ```text
483  /// Note that the allocator may give the collection more space than it requests.
484  /// Therefore, capacity can not be relied upon to be precisely minimal.
485  /// Prefer `reserve` if future insertions are expected.
486  /// ```
487  /// ```rust
488  /// use tinyvec::*;
489  /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3, 4);
490  /// assert!(tv.is_inline());
491  /// tv.reserve_exact(1);
492  /// assert!(tv.is_heap());
493  /// assert!(tv.capacity() >= 5);
494  /// ```
495  #[inline]
496  pub fn reserve_exact(&mut self, n: usize) {
497    let arr = match self {
498      TinyVec::Heap(h) => return h.reserve_exact(n),
499      TinyVec::Inline(a) => a,
500    };
501
502    if n > arr.capacity() - arr.len() {
503      let v = arr.drain_to_vec_and_reserve(n);
504      *self = TinyVec::Heap(v);
505    }
506
507    /* In this place array has enough place, so no work is needed more */
508    return;
509  }
510
511  /// Tries to reserve additional space.
512  /// Moves to the heap if array can't hold `n` more items
513  ///
514  /// # Errors
515  ///
516  /// If the allocator reports a failure, then an error is returned.
517  ///
518  /// From [Vec::try_reserve_exact](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.try_reserve_exact)
519  /// ```text
520  /// Note that the allocator may give the collection more space than it requests.
521  /// Therefore, capacity can not be relied upon to be precisely minimal.
522  /// Prefer `reserve` if future insertions are expected.
523  /// ```
524  /// ```rust
525  /// use tinyvec::*;
526  /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3, 4);
527  /// assert!(tv.is_inline());
528  /// assert_eq!(Ok(()), tv.try_reserve_exact(1));
529  /// assert!(tv.is_heap());
530  /// assert!(tv.capacity() >= 5);
531  /// ```
532  #[inline]
533  #[cfg(feature = "rustc_1_57")]
534  pub fn try_reserve_exact(&mut self, n: usize) -> Result<(), TryReserveError> {
535    let arr = match self {
536      TinyVec::Heap(h) => return h.try_reserve_exact(n),
537      TinyVec::Inline(a) => a,
538    };
539
540    if n > arr.capacity() - arr.len() {
541      let v = arr.try_drain_to_vec_and_reserve(n)?;
542      *self = TinyVec::Heap(v);
543    }
544
545    /* In this place array has enough place, so no work is needed more */
546    return Ok(());
547  }
548
549  /// Makes a new TinyVec with _at least_ the given capacity.
550  ///
551  /// If the requested capacity is less than or equal to the array capacity you
552  /// get an inline vec. If it's greater than you get a heap vec.
553  /// ```
554  /// # use tinyvec::*;
555  /// let t = TinyVec::<[u8; 10]>::with_capacity(5);
556  /// assert!(t.is_inline());
557  /// assert!(t.capacity() >= 5);
558  ///
559  /// let t = TinyVec::<[u8; 10]>::with_capacity(20);
560  /// assert!(t.is_heap());
561  /// assert!(t.capacity() >= 20);
562  /// ```
563  #[inline]
564  #[must_use]
565  pub fn with_capacity(cap: usize) -> Self {
566    if cap <= A::CAPACITY {
567      TinyVec::Inline(ArrayVec::default())
568    } else {
569      TinyVec::Heap(Vec::with_capacity(cap))
570    }
571  }
572
573  /// Converts a `TinyVec<[T; N]>` into a `Box<[T]>`.
574  ///
575  /// - For `TinyVec::Heap(Vec<T>)`, it takes the `Vec<T>` and converts it into
576  ///   a `Box<[T]>` without heap reallocation.
577  /// - For `TinyVec::Inline(inner_data)`, it first converts the `inner_data` to
578  ///   `Vec<T>`, then into a `Box<[T]>`. Requiring only a single heap
579  ///   allocation.
580  ///
581  /// ## Example
582  ///
583  /// ```
584  /// use core::mem::size_of_val as mem_size_of;
585  /// use tinyvec::TinyVec;
586  ///
587  /// // Initialize TinyVec with 256 elements (exceeding inline capacity)
588  /// let v: TinyVec<[_; 128]> = (0u8..=255).collect();
589  ///
590  /// assert!(v.is_heap());
591  /// assert_eq!(mem_size_of(&v), 136); // mem size of TinyVec<[u8; N]>: N+8
592  /// assert_eq!(v.len(), 256);
593  ///
594  /// let boxed = v.into_boxed_slice();
595  /// assert_eq!(mem_size_of(&boxed), 16); // mem size of Box<[u8]>: 16 bytes (fat pointer)
596  /// assert_eq!(boxed.len(), 256);
597  /// ```
598  #[inline]
599  #[must_use]
600  pub fn into_boxed_slice(self) -> alloc::boxed::Box<[A::Item]> {
601    self.into_vec().into_boxed_slice()
602  }
603
604  /// Converts a `TinyVec<[T; N]>` into a `Vec<T>`.
605  ///
606  /// `v.into_vec()` is equivalent to `Into::<Vec<_>>::into(v)`.
607  ///
608  /// - For `TinyVec::Inline(_)`, `.into_vec()` **does not** offer a performance
609  ///   advantage over `.to_vec()`.
610  /// - For `TinyVec::Heap(vec_data)`, `.into_vec()` will take `vec_data`
611  ///   without heap reallocation.
612  ///
613  /// ## Example
614  ///
615  /// ```
616  /// use tinyvec::TinyVec;
617  ///
618  /// let v = TinyVec::from([0u8; 8]);
619  /// let v2 = v.clone();
620  ///
621  /// let vec = v.into_vec();
622  /// let vec2: Vec<_> = v2.into();
623  ///
624  /// assert_eq!(vec, vec2);
625  /// ```
626  #[inline]
627  #[must_use]
628  pub fn into_vec(self) -> Vec<A::Item> {
629    self.into()
630  }
631}
632
633impl<A: Array> TinyVec<A> {
634  /// Move all values from `other` into this vec.
635  #[inline]
636  pub fn append(&mut self, other: &mut Self) {
637    self.reserve(other.len());
638
639    /* Doing append should be faster, because it is effectively a memcpy */
640    match (self, other) {
641      (TinyVec::Heap(sh), TinyVec::Heap(oh)) => sh.append(oh),
642      (TinyVec::Inline(a), TinyVec::Heap(h)) => a.extend(h.drain(..)),
643      (ref mut this, TinyVec::Inline(arr)) => this.extend(arr.drain(..)),
644    }
645  }
646
647  impl_mirrored! {
648    type Mirror = TinyVec;
649
650    /// Remove an element, swapping the end of the vec into its place.
651    ///
652    /// ## Panics
653    /// * If the index is out of bounds.
654    ///
655    /// ## Example
656    /// ```rust
657    /// use tinyvec::*;
658    /// let mut tv = tiny_vec!([&str; 4] => "foo", "bar", "quack", "zap");
659    ///
660    /// assert_eq!(tv.swap_remove(1), "bar");
661    /// assert_eq!(tv.as_slice(), &["foo", "zap", "quack"][..]);
662    ///
663    /// assert_eq!(tv.swap_remove(0), "foo");
664    /// assert_eq!(tv.as_slice(), &["quack", "zap"][..]);
665    /// ```
666    #[inline]
667    pub fn swap_remove(self: &mut Self, index: usize) -> A::Item;
668
669    /// Remove and return the last element of the vec, if there is one.
670    ///
671    /// ## Failure
672    /// * If the vec is empty you get `None`.
673    #[inline]
674    pub fn pop(self: &mut Self) -> Option<A::Item>;
675
676    /// Removes the item at `index`, shifting all others down by one index.
677    ///
678    /// Returns the removed element.
679    ///
680    /// ## Panics
681    ///
682    /// If the index is out of bounds.
683    ///
684    /// ## Example
685    ///
686    /// ```rust
687    /// use tinyvec::*;
688    /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3);
689    /// assert_eq!(tv.remove(1), 2);
690    /// assert_eq!(tv.as_slice(), &[1, 3][..]);
691    /// ```
692    #[inline]
693    pub fn remove(self: &mut Self, index: usize) -> A::Item;
694
695    /// The length of the vec (in elements).
696    #[inline(always)]
697    #[must_use]
698    pub fn len(self: &Self) -> usize;
699
700    /// The capacity of the `TinyVec`.
701    ///
702    /// When not heap allocated this is fixed based on the array type.
703    /// Otherwise its the result of the underlying Vec::capacity.
704    #[inline(always)]
705    #[must_use]
706    pub fn capacity(self: &Self) -> usize;
707
708    /// Reduces the vec's length to the given value.
709    ///
710    /// If the vec is already shorter than the input, nothing happens.
711    #[inline]
712    pub fn truncate(self: &mut Self, new_len: usize);
713
714    /// A mutable pointer to the backing array.
715    ///
716    /// ## Safety
717    ///
718    /// This pointer has provenance over the _entire_ backing array/buffer.
719    #[inline(always)]
720    #[must_use]
721    pub fn as_mut_ptr(self: &mut Self) -> *mut A::Item;
722
723    /// A const pointer to the backing array.
724    ///
725    /// ## Safety
726    ///
727    /// This pointer has provenance over the _entire_ backing array/buffer.
728    #[inline(always)]
729    #[must_use]
730    pub fn as_ptr(self: &Self) -> *const A::Item;
731  }
732
733  /// Walk the vec and keep only the elements that pass the predicate given.
734  ///
735  /// ## Example
736  ///
737  /// ```rust
738  /// use tinyvec::*;
739  ///
740  /// let mut tv = tiny_vec!([i32; 10] => 1, 2, 3, 4);
741  /// tv.retain(|&x| x % 2 == 0);
742  /// assert_eq!(tv.as_slice(), &[2, 4][..]);
743  /// ```
744  #[inline]
745  pub fn retain<F: FnMut(&A::Item) -> bool>(&mut self, acceptable: F) {
746    match self {
747      TinyVec::Inline(i) => i.retain(acceptable),
748      TinyVec::Heap(h) => h.retain(acceptable),
749    }
750  }
751
752  /// Walk the vec and keep only the elements that pass the predicate given,
753  /// having the opportunity to modify the elements at the same time.
754  ///
755  /// ## Example
756  ///
757  /// ```rust
758  /// use tinyvec::*;
759  ///
760  /// let mut tv = tiny_vec!([i32; 10] => 1, 2, 3, 4);
761  /// tv.retain_mut(|x| if *x % 2 == 0 { *x *= 2; true } else { false });
762  /// assert_eq!(tv.as_slice(), &[4, 8][..]);
763  /// ```
764  #[inline]
765  #[cfg(feature = "rustc_1_61")]
766  pub fn retain_mut<F: FnMut(&mut A::Item) -> bool>(&mut self, acceptable: F) {
767    match self {
768      TinyVec::Inline(i) => i.retain_mut(acceptable),
769      TinyVec::Heap(h) => h.retain_mut(acceptable),
770    }
771  }
772
773  /// Helper for getting the mut slice.
774  #[inline(always)]
775  #[must_use]
776  pub fn as_mut_slice(&mut self) -> &mut [A::Item] {
777    self.deref_mut()
778  }
779
780  /// Helper for getting the shared slice.
781  #[inline(always)]
782  #[must_use]
783  pub fn as_slice(&self) -> &[A::Item] {
784    self.deref()
785  }
786
787  /// Removes all elements from the vec.
788  #[inline(always)]
789  pub fn clear(&mut self) {
790    self.truncate(0)
791  }
792
793  /// De-duplicates the vec.
794  #[cfg(feature = "nightly_slice_partition_dedup")]
795  #[inline(always)]
796  pub fn dedup(&mut self)
797  where
798    A::Item: PartialEq,
799  {
800    self.dedup_by(|a, b| a == b)
801  }
802
803  /// De-duplicates the vec according to the predicate given.
804  #[cfg(feature = "nightly_slice_partition_dedup")]
805  #[inline(always)]
806  pub fn dedup_by<F>(&mut self, same_bucket: F)
807  where
808    F: FnMut(&mut A::Item, &mut A::Item) -> bool,
809  {
810    let len = {
811      let (dedup, _) = self.as_mut_slice().partition_dedup_by(same_bucket);
812      dedup.len()
813    };
814    self.truncate(len);
815  }
816
817  /// De-duplicates the vec according to the key selector given.
818  #[cfg(feature = "nightly_slice_partition_dedup")]
819  #[inline(always)]
820  pub fn dedup_by_key<F, K>(&mut self, mut key: F)
821  where
822    F: FnMut(&mut A::Item) -> K,
823    K: PartialEq,
824  {
825    self.dedup_by(|a, b| key(a) == key(b))
826  }
827
828  /// Creates a draining iterator that removes the specified range in the vector
829  /// and yields the removed items.
830  ///
831  /// **Note: This method has significant performance issues compared to
832  /// matching on the TinyVec and then calling drain on the Inline or Heap value
833  /// inside. The draining iterator has to branch on every single access. It is
834  /// provided for simplicity and compatibility only.**
835  ///
836  /// ## Panics
837  /// * If the start is greater than the end
838  /// * If the end is past the edge of the vec.
839  ///
840  /// ## Example
841  /// ```rust
842  /// use tinyvec::*;
843  /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3);
844  /// let tv2: TinyVec<[i32; 4]> = tv.drain(1..).collect();
845  /// assert_eq!(tv.as_slice(), &[1][..]);
846  /// assert_eq!(tv2.as_slice(), &[2, 3][..]);
847  ///
848  /// tv.drain(..);
849  /// assert_eq!(tv.as_slice(), &[]);
850  /// ```
851  #[inline]
852  pub fn drain<R: RangeBounds<usize>>(
853    &mut self, range: R,
854  ) -> TinyVecDrain<'_, A> {
855    match self {
856      TinyVec::Inline(i) => TinyVecDrain::Inline(i.drain(range)),
857      TinyVec::Heap(h) => TinyVecDrain::Heap(h.drain(range)),
858    }
859  }
860
861  /// Clone each element of the slice into this vec.
862  /// ```rust
863  /// use tinyvec::*;
864  /// let mut tv = tiny_vec!([i32; 4] => 1, 2);
865  /// tv.extend_from_slice(&[3, 4]);
866  /// assert_eq!(tv.as_slice(), [1, 2, 3, 4]);
867  /// ```
868  #[inline]
869  pub fn extend_from_slice(&mut self, sli: &[A::Item])
870  where
871    A::Item: Clone,
872  {
873    self.reserve(sli.len());
874    match self {
875      TinyVec::Inline(a) => a.extend_from_slice(sli),
876      TinyVec::Heap(h) => h.extend_from_slice(sli),
877    }
878  }
879
880  /// Wraps up an array and uses the given length as the initial length.
881  ///
882  /// Note that the `From` impl for arrays assumes the full length is used.
883  ///
884  /// ## Panics
885  ///
886  /// The length must be less than or equal to the capacity of the array.
887  #[inline]
888  #[must_use]
889  #[allow(clippy::match_wild_err_arm)]
890  pub fn from_array_len(data: A, len: usize) -> Self {
891    match Self::try_from_array_len(data, len) {
892      Ok(out) => out,
893      Err(_) => {
894        panic!("TinyVec: length {} exceeds capacity {}!", len, A::CAPACITY)
895      }
896    }
897  }
898
899  /// This is an internal implementation detail of the `tiny_vec!` macro, and
900  /// using it other than from that macro is not supported by this crate's
901  /// SemVer guarantee.
902  #[inline(always)]
903  #[doc(hidden)]
904  pub fn constructor_for_capacity(cap: usize) -> TinyVecConstructor<A> {
905    if cap <= A::CAPACITY {
906      TinyVecConstructor::Inline(TinyVec::Inline)
907    } else {
908      TinyVecConstructor::Heap(TinyVec::Heap)
909    }
910  }
911
912  /// Inserts an item at the position given, moving all following elements +1
913  /// index.
914  ///
915  /// ## Panics
916  /// * If `index` > `len`
917  ///
918  /// ## Example
919  /// ```rust
920  /// use tinyvec::*;
921  /// let mut tv = tiny_vec!([i32; 10] => 1, 2, 3);
922  /// tv.insert(1, 4);
923  /// assert_eq!(tv.as_slice(), &[1, 4, 2, 3]);
924  /// tv.insert(4, 5);
925  /// assert_eq!(tv.as_slice(), &[1, 4, 2, 3, 5]);
926  /// ```
927  #[inline]
928  pub fn insert(&mut self, index: usize, item: A::Item) {
929    assert!(
930      index <= self.len(),
931      "insertion index (is {}) should be <= len (is {})",
932      index,
933      self.len()
934    );
935
936    let arr = match self {
937      TinyVec::Heap(v) => return v.insert(index, item),
938      TinyVec::Inline(a) => a,
939    };
940
941    if let Some(x) = arr.try_insert(index, item) {
942      let mut v = Vec::with_capacity(arr.len() * 2);
943      let mut it = arr.iter_mut().map(core::mem::take);
944      v.extend(it.by_ref().take(index));
945      v.push(x);
946      v.extend(it);
947      *self = TinyVec::Heap(v);
948    }
949  }
950
951  /// If the vec is empty.
952  #[inline(always)]
953  #[must_use]
954  pub fn is_empty(&self) -> bool {
955    self.len() == 0
956  }
957
958  /// Makes a new, empty vec.
959  #[inline(always)]
960  #[must_use]
961  pub fn new() -> Self {
962    Self::default()
963  }
964
965  /// Place an element onto the end of the vec.
966  #[inline]
967  pub fn push(&mut self, val: A::Item) {
968    // The code path for moving the inline contents to the heap produces a lot
969    // of instructions, but we have a strong guarantee that this is a cold
970    // path. LLVM doesn't know this, inlines it, and this tends to cause a
971    // cascade of other bad inlining decisions because the body of push looks
972    // huge even though nearly every call executes the same few instructions.
973    //
974    // Moving the logic out of line with #[cold] causes the hot code to  be
975    // inlined together, and we take the extra cost of a function call only
976    // in rare cases.
977    #[cold]
978    fn drain_to_heap_and_push<A: Array>(
979      arr: &mut ArrayVec<A>, val: A::Item,
980    ) -> TinyVec<A> {
981      /* Make the Vec twice the size to amortize the cost of draining */
982      let mut v = arr.drain_to_vec_and_reserve(arr.len());
983      v.push(val);
984      TinyVec::Heap(v)
985    }
986
987    match self {
988      TinyVec::Heap(v) => v.push(val),
989      TinyVec::Inline(arr) => {
990        if let Some(x) = arr.try_push(val) {
991          *self = drain_to_heap_and_push(arr, x);
992        }
993      }
994    }
995  }
996
997  /// Resize the vec to the new length.
998  ///
999  /// If it needs to be longer, it's filled with clones of the provided value.
1000  /// If it needs to be shorter, it's truncated.
1001  ///
1002  /// ## Example
1003  ///
1004  /// ```rust
1005  /// use tinyvec::*;
1006  ///
1007  /// let mut tv = tiny_vec!([&str; 10] => "hello");
1008  /// tv.resize(3, "world");
1009  /// assert_eq!(tv.as_slice(), &["hello", "world", "world"][..]);
1010  ///
1011  /// let mut tv = tiny_vec!([i32; 10] => 1, 2, 3, 4);
1012  /// tv.resize(2, 0);
1013  /// assert_eq!(tv.as_slice(), &[1, 2][..]);
1014  /// ```
1015  #[inline]
1016  pub fn resize(&mut self, new_len: usize, new_val: A::Item)
1017  where
1018    A::Item: Clone,
1019  {
1020    self.resize_with(new_len, || new_val.clone());
1021  }
1022
1023  /// Resize the vec to the new length.
1024  ///
1025  /// If it needs to be longer, it's filled with repeated calls to the provided
1026  /// function. If it needs to be shorter, it's truncated.
1027  ///
1028  /// ## Example
1029  ///
1030  /// ```rust
1031  /// use tinyvec::*;
1032  ///
1033  /// let mut tv = tiny_vec!([i32; 3] => 1, 2, 3);
1034  /// tv.resize_with(5, Default::default);
1035  /// assert_eq!(tv.as_slice(), &[1, 2, 3, 0, 0][..]);
1036  ///
1037  /// let mut tv = tiny_vec!([i32; 2]);
1038  /// let mut p = 1;
1039  /// tv.resize_with(4, || {
1040  ///   p *= 2;
1041  ///   p
1042  /// });
1043  /// assert_eq!(tv.as_slice(), &[2, 4, 8, 16][..]);
1044  /// ```
1045  #[inline]
1046  pub fn resize_with<F: FnMut() -> A::Item>(&mut self, new_len: usize, f: F) {
1047    match new_len.checked_sub(self.len()) {
1048      None => return self.truncate(new_len),
1049      Some(n) => self.reserve(n),
1050    }
1051
1052    match self {
1053      TinyVec::Inline(a) => a.resize_with(new_len, f),
1054      TinyVec::Heap(v) => v.resize_with(new_len, f),
1055    }
1056  }
1057
1058  /// Splits the collection at the point given.
1059  ///
1060  /// * `[0, at)` stays in this vec
1061  /// * `[at, len)` ends up in the new vec.
1062  ///
1063  /// ## Panics
1064  /// * if at > len
1065  ///
1066  /// ## Example
1067  ///
1068  /// ```rust
1069  /// use tinyvec::*;
1070  /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3);
1071  /// let tv2 = tv.split_off(1);
1072  /// assert_eq!(tv.as_slice(), &[1][..]);
1073  /// assert_eq!(tv2.as_slice(), &[2, 3][..]);
1074  /// ```
1075  #[inline]
1076  pub fn split_off(&mut self, at: usize) -> Self {
1077    match self {
1078      TinyVec::Inline(a) => TinyVec::Inline(a.split_off(at)),
1079      TinyVec::Heap(v) => TinyVec::Heap(v.split_off(at)),
1080    }
1081  }
1082
1083  /// Creates a splicing iterator that removes the specified range in the
1084  /// vector, yields the removed items, and replaces them with elements from
1085  /// the provided iterator.
1086  ///
1087  /// `splice` fuses the provided iterator, so elements after the first `None`
1088  /// are ignored.
1089  ///
1090  /// ## Panics
1091  /// * If the start is greater than the end.
1092  /// * If the end is past the edge of the vec.
1093  /// * If the provided iterator panics.
1094  ///
1095  /// ## Example
1096  /// ```rust
1097  /// use tinyvec::*;
1098  /// let mut tv = tiny_vec!([i32; 4] => 1, 2, 3);
1099  /// let tv2: TinyVec<[i32; 4]> = tv.splice(1.., 4..=6).collect();
1100  /// assert_eq!(tv.as_slice(), &[1, 4, 5, 6][..]);
1101  /// assert_eq!(tv2.as_slice(), &[2, 3][..]);
1102  ///
1103  /// tv.splice(.., None);
1104  /// assert_eq!(tv.as_slice(), &[]);
1105  /// ```
1106  #[inline]
1107  pub fn splice<R, I>(
1108    &mut self, range: R, replacement: I,
1109  ) -> TinyVecSplice<'_, A, core::iter::Fuse<I::IntoIter>>
1110  where
1111    R: RangeBounds<usize>,
1112    I: IntoIterator<Item = A::Item>,
1113  {
1114    use core::ops::Bound;
1115    let start = match range.start_bound() {
1116      Bound::Included(x) => *x,
1117      Bound::Excluded(x) => x.saturating_add(1),
1118      Bound::Unbounded => 0,
1119    };
1120    let end = match range.end_bound() {
1121      Bound::Included(x) => x.saturating_add(1),
1122      Bound::Excluded(x) => *x,
1123      Bound::Unbounded => self.len(),
1124    };
1125    assert!(
1126      start <= end,
1127      "TinyVec::splice> Illegal range, {} to {}",
1128      start,
1129      end
1130    );
1131    assert!(
1132      end <= self.len(),
1133      "TinyVec::splice> Range ends at {} but length is only {}!",
1134      end,
1135      self.len()
1136    );
1137
1138    TinyVecSplice {
1139      removal_start: start,
1140      removal_end: end,
1141      parent: self,
1142      replacement: replacement.into_iter().fuse(),
1143    }
1144  }
1145
1146  /// Wraps an array, using the given length as the starting length.
1147  ///
1148  /// If you want to use the whole length of the array, you can just use the
1149  /// `From` impl.
1150  ///
1151  /// ## Failure
1152  ///
1153  /// If the given length is greater than the capacity of the array this will
1154  /// error, and you'll get the array back in the `Err`.
1155  #[inline]
1156  pub fn try_from_array_len(data: A, len: usize) -> Result<Self, A> {
1157    let arr = ArrayVec::try_from_array_len(data, len)?;
1158    Ok(TinyVec::Inline(arr))
1159  }
1160}
1161
1162/// Draining iterator for `TinyVecDrain`
1163///
1164/// See [`TinyVecDrain::drain`](TinyVecDrain::<A>::drain)
1165#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
1166pub enum TinyVecDrain<'p, A: Array> {
1167  #[allow(missing_docs)]
1168  Inline(ArrayVecDrain<'p, A::Item>),
1169  #[allow(missing_docs)]
1170  Heap(vec::Drain<'p, A::Item>),
1171}
1172
1173impl<'p, A: Array> Iterator for TinyVecDrain<'p, A> {
1174  type Item = A::Item;
1175
1176  impl_mirrored! {
1177    type Mirror = TinyVecDrain;
1178
1179    #[inline]
1180    fn next(self: &mut Self) -> Option<Self::Item>;
1181    #[inline]
1182    fn nth(self: &mut Self, n: usize) -> Option<Self::Item>;
1183    #[inline]
1184    fn size_hint(self: &Self) -> (usize, Option<usize>);
1185    #[inline]
1186    fn last(self: Self) -> Option<Self::Item>;
1187    #[inline]
1188    fn count(self: Self) -> usize;
1189  }
1190
1191  #[inline]
1192  fn for_each<F: FnMut(Self::Item)>(self, f: F) {
1193    match self {
1194      TinyVecDrain::Inline(i) => i.for_each(f),
1195      TinyVecDrain::Heap(h) => h.for_each(f),
1196    }
1197  }
1198}
1199
1200impl<'p, A: Array> DoubleEndedIterator for TinyVecDrain<'p, A> {
1201  impl_mirrored! {
1202    type Mirror = TinyVecDrain;
1203
1204    #[inline]
1205    fn next_back(self: &mut Self) -> Option<Self::Item>;
1206
1207    #[inline]
1208    fn nth_back(self: &mut Self, n: usize) -> Option<Self::Item>;
1209  }
1210}
1211
1212/// Splicing iterator for `TinyVec`
1213/// See [`TinyVec::splice`](TinyVec::<A>::splice)
1214#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
1215pub struct TinyVecSplice<'p, A: Array, I: Iterator<Item = A::Item>> {
1216  parent: &'p mut TinyVec<A>,
1217  removal_start: usize,
1218  removal_end: usize,
1219  replacement: I,
1220}
1221
1222impl<'p, A, I> Iterator for TinyVecSplice<'p, A, I>
1223where
1224  A: Array,
1225  I: Iterator<Item = A::Item>,
1226{
1227  type Item = A::Item;
1228
1229  #[inline]
1230  fn next(&mut self) -> Option<A::Item> {
1231    if self.removal_start < self.removal_end {
1232      match self.replacement.next() {
1233        Some(replacement) => {
1234          let removed = core::mem::replace(
1235            &mut self.parent[self.removal_start],
1236            replacement,
1237          );
1238          self.removal_start += 1;
1239          Some(removed)
1240        }
1241        None => {
1242          let removed = self.parent.remove(self.removal_start);
1243          self.removal_end -= 1;
1244          Some(removed)
1245        }
1246      }
1247    } else {
1248      None
1249    }
1250  }
1251
1252  #[inline]
1253  fn size_hint(&self) -> (usize, Option<usize>) {
1254    let len = self.len();
1255    (len, Some(len))
1256  }
1257}
1258
1259impl<'p, A, I> ExactSizeIterator for TinyVecSplice<'p, A, I>
1260where
1261  A: Array,
1262  I: Iterator<Item = A::Item>,
1263{
1264  #[inline]
1265  fn len(&self) -> usize {
1266    self.removal_end - self.removal_start
1267  }
1268}
1269
1270impl<'p, A, I> FusedIterator for TinyVecSplice<'p, A, I>
1271where
1272  A: Array,
1273  I: Iterator<Item = A::Item>,
1274{
1275}
1276
1277impl<'p, A, I> DoubleEndedIterator for TinyVecSplice<'p, A, I>
1278where
1279  A: Array,
1280  I: Iterator<Item = A::Item> + DoubleEndedIterator,
1281{
1282  #[inline]
1283  fn next_back(&mut self) -> Option<A::Item> {
1284    if self.removal_start < self.removal_end {
1285      match self.replacement.next_back() {
1286        Some(replacement) => {
1287          let removed = core::mem::replace(
1288            &mut self.parent[self.removal_end - 1],
1289            replacement,
1290          );
1291          self.removal_end -= 1;
1292          Some(removed)
1293        }
1294        None => {
1295          let removed = self.parent.remove(self.removal_end - 1);
1296          self.removal_end -= 1;
1297          Some(removed)
1298        }
1299      }
1300    } else {
1301      None
1302    }
1303  }
1304}
1305
1306impl<'p, A: Array, I: Iterator<Item = A::Item>> Drop
1307  for TinyVecSplice<'p, A, I>
1308{
1309  #[inline]
1310  fn drop(&mut self) {
1311    for _ in self.by_ref() {}
1312
1313    let (lower_bound, _) = self.replacement.size_hint();
1314    self.parent.reserve(lower_bound);
1315
1316    for replacement in self.replacement.by_ref() {
1317      self.parent.insert(self.removal_end, replacement);
1318      self.removal_end += 1;
1319    }
1320  }
1321}
1322
1323impl<A: Array> AsMut<[A::Item]> for TinyVec<A> {
1324  #[inline(always)]
1325  fn as_mut(&mut self) -> &mut [A::Item] {
1326    &mut *self
1327  }
1328}
1329
1330impl<A: Array> AsRef<[A::Item]> for TinyVec<A> {
1331  #[inline(always)]
1332  fn as_ref(&self) -> &[A::Item] {
1333    &*self
1334  }
1335}
1336
1337impl<A: Array> Borrow<[A::Item]> for TinyVec<A> {
1338  #[inline(always)]
1339  fn borrow(&self) -> &[A::Item] {
1340    &*self
1341  }
1342}
1343
1344impl<A: Array> BorrowMut<[A::Item]> for TinyVec<A> {
1345  #[inline(always)]
1346  fn borrow_mut(&mut self) -> &mut [A::Item] {
1347    &mut *self
1348  }
1349}
1350
1351impl<A: Array> Extend<A::Item> for TinyVec<A> {
1352  #[inline]
1353  fn extend<T: IntoIterator<Item = A::Item>>(&mut self, iter: T) {
1354    let iter = iter.into_iter();
1355    let (lower_bound, _) = iter.size_hint();
1356    self.reserve(lower_bound);
1357
1358    let a = match self {
1359      TinyVec::Heap(h) => return h.extend(iter),
1360      TinyVec::Inline(a) => a,
1361    };
1362
1363    let mut iter = a.fill(iter);
1364    let maybe = iter.next();
1365
1366    let surely = match maybe {
1367      Some(x) => x,
1368      None => return,
1369    };
1370
1371    let mut v = a.drain_to_vec_and_reserve(a.len());
1372    v.push(surely);
1373    v.extend(iter);
1374    *self = TinyVec::Heap(v);
1375  }
1376}
1377
1378impl<A: Array> From<ArrayVec<A>> for TinyVec<A> {
1379  #[inline(always)]
1380  fn from(arr: ArrayVec<A>) -> Self {
1381    TinyVec::Inline(arr)
1382  }
1383}
1384
1385impl<A: Array> From<A> for TinyVec<A> {
1386  #[inline]
1387  fn from(array: A) -> Self {
1388    TinyVec::Inline(ArrayVec::from(array))
1389  }
1390}
1391
1392impl<T, A> From<&'_ [T]> for TinyVec<A>
1393where
1394  T: Clone + Default,
1395  A: Array<Item = T>,
1396{
1397  #[inline]
1398  fn from(slice: &[T]) -> Self {
1399    if let Ok(arr) = ArrayVec::try_from(slice) {
1400      TinyVec::Inline(arr)
1401    } else {
1402      TinyVec::Heap(slice.into())
1403    }
1404  }
1405}
1406
1407impl<T, A> From<&'_ mut [T]> for TinyVec<A>
1408where
1409  T: Clone + Default,
1410  A: Array<Item = T>,
1411{
1412  #[inline]
1413  fn from(slice: &mut [T]) -> Self {
1414    Self::from(&*slice)
1415  }
1416}
1417
1418impl<A: Array> FromIterator<A::Item> for TinyVec<A> {
1419  #[inline]
1420  fn from_iter<T: IntoIterator<Item = A::Item>>(iter: T) -> Self {
1421    let mut av = Self::default();
1422    av.extend(iter);
1423    av
1424  }
1425}
1426
1427impl<A: Array> Into<Vec<A::Item>> for TinyVec<A> {
1428  /// Converts a `TinyVec` into a `Vec`.
1429  ///
1430  /// ## Examples
1431  ///
1432  /// ### Inline to Vec
1433  ///
1434  /// For `TinyVec::Inline(_)`,
1435  ///   `.into()` **does not** offer a performance advantage over `.to_vec()`.
1436  ///
1437  /// ```
1438  /// use core::mem::size_of_val as mem_size_of;
1439  /// use tinyvec::TinyVec;
1440  ///
1441  /// let v = TinyVec::from([0u8; 128]);
1442  /// assert_eq!(mem_size_of(&v), 136);
1443  ///
1444  /// let vec: Vec<_> = v.into();
1445  /// assert_eq!(mem_size_of(&vec), 24);
1446  /// ```
1447  ///
1448  /// ### Heap into Vec
1449  ///
1450  /// For `TinyVec::Heap(vec_data)`,
1451  ///   `.into()` will take `vec_data` without heap reallocation.
1452  ///
1453  /// ```
1454  /// use core::{
1455  ///   any::type_name_of_val as type_of, mem::size_of_val as mem_size_of,
1456  /// };
1457  /// use tinyvec::TinyVec;
1458  ///
1459  /// const fn from_heap<T: Default>(owned: Vec<T>) -> TinyVec<[T; 1]> {
1460  ///   TinyVec::Heap(owned)
1461  /// }
1462  ///
1463  /// let v = from_heap(vec![0u8; 128]);
1464  /// assert_eq!(v.len(), 128);
1465  /// assert_eq!(mem_size_of(&v), 24);
1466  /// assert!(type_of(&v).ends_with("TinyVec<[u8; 1]>"));
1467  ///
1468  /// let vec: Vec<_> = v.into();
1469  /// assert_eq!(mem_size_of(&vec), 24);
1470  /// assert!(type_of(&vec).ends_with("Vec<u8>"));
1471  /// ```
1472  #[inline]
1473  fn into(self) -> Vec<A::Item> {
1474    match self {
1475      Self::Heap(inner) => inner,
1476      Self::Inline(mut inner) => inner.drain_to_vec(),
1477    }
1478  }
1479}
1480
1481/// Iterator for consuming an `TinyVec` and returning owned elements.
1482#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
1483pub enum TinyVecIterator<A: Array> {
1484  #[allow(missing_docs)]
1485  Inline(ArrayVecIterator<A>),
1486  #[allow(missing_docs)]
1487  Heap(alloc::vec::IntoIter<A::Item>),
1488}
1489
1490impl<A: Array> TinyVecIterator<A> {
1491  impl_mirrored! {
1492    type Mirror = TinyVecIterator;
1493    /// Returns the remaining items of this iterator as a slice.
1494    #[inline]
1495    #[must_use]
1496    pub fn as_slice(self: &Self) -> &[A::Item];
1497  }
1498}
1499
1500impl<A: Array> FusedIterator for TinyVecIterator<A> {}
1501
1502impl<A: Array> Iterator for TinyVecIterator<A> {
1503  type Item = A::Item;
1504
1505  impl_mirrored! {
1506    type Mirror = TinyVecIterator;
1507
1508    #[inline]
1509    fn next(self: &mut Self) -> Option<Self::Item>;
1510
1511    #[inline(always)]
1512    #[must_use]
1513    fn size_hint(self: &Self) -> (usize, Option<usize>);
1514
1515    #[inline(always)]
1516    fn count(self: Self) -> usize;
1517
1518    #[inline]
1519    fn last(self: Self) -> Option<Self::Item>;
1520
1521    #[inline]
1522    fn nth(self: &mut Self, n: usize) -> Option<A::Item>;
1523  }
1524}
1525
1526impl<A: Array> DoubleEndedIterator for TinyVecIterator<A> {
1527  impl_mirrored! {
1528    type Mirror = TinyVecIterator;
1529
1530    #[inline]
1531    fn next_back(self: &mut Self) -> Option<Self::Item>;
1532
1533    #[inline]
1534    fn nth_back(self: &mut Self, n: usize) -> Option<Self::Item>;
1535  }
1536}
1537
1538impl<A: Array> ExactSizeIterator for TinyVecIterator<A> {
1539  impl_mirrored! {
1540    type Mirror = TinyVecIterator;
1541    #[inline]
1542    fn len(self: &Self) -> usize;
1543  }
1544}
1545
1546impl<A: Array> Debug for TinyVecIterator<A>
1547where
1548  A::Item: Debug,
1549{
1550  #[allow(clippy::missing_inline_in_public_items)]
1551  fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
1552    f.debug_tuple("TinyVecIterator").field(&self.as_slice()).finish()
1553  }
1554}
1555
1556impl<A: Array> IntoIterator for TinyVec<A> {
1557  type Item = A::Item;
1558  type IntoIter = TinyVecIterator<A>;
1559  #[inline(always)]
1560  fn into_iter(self) -> Self::IntoIter {
1561    match self {
1562      TinyVec::Inline(a) => TinyVecIterator::Inline(a.into_iter()),
1563      TinyVec::Heap(v) => TinyVecIterator::Heap(v.into_iter()),
1564    }
1565  }
1566}
1567
1568impl<'a, A: Array> IntoIterator for &'a mut TinyVec<A> {
1569  type Item = &'a mut A::Item;
1570  type IntoIter = core::slice::IterMut<'a, A::Item>;
1571  #[inline(always)]
1572  fn into_iter(self) -> Self::IntoIter {
1573    self.iter_mut()
1574  }
1575}
1576
1577impl<'a, A: Array> IntoIterator for &'a TinyVec<A> {
1578  type Item = &'a A::Item;
1579  type IntoIter = core::slice::Iter<'a, A::Item>;
1580  #[inline(always)]
1581  fn into_iter(self) -> Self::IntoIter {
1582    self.iter()
1583  }
1584}
1585
1586impl<A: Array> PartialEq for TinyVec<A>
1587where
1588  A::Item: PartialEq,
1589{
1590  #[inline]
1591  fn eq(&self, other: &Self) -> bool {
1592    self.as_slice().eq(other.as_slice())
1593  }
1594}
1595impl<A: Array> Eq for TinyVec<A> where A::Item: Eq {}
1596
1597impl<A: Array> PartialOrd for TinyVec<A>
1598where
1599  A::Item: PartialOrd,
1600{
1601  #[inline]
1602  fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
1603    self.as_slice().partial_cmp(other.as_slice())
1604  }
1605}
1606impl<A: Array> Ord for TinyVec<A>
1607where
1608  A::Item: Ord,
1609{
1610  #[inline]
1611  fn cmp(&self, other: &Self) -> core::cmp::Ordering {
1612    self.as_slice().cmp(other.as_slice())
1613  }
1614}
1615
1616impl<A: Array> PartialEq<&A> for TinyVec<A>
1617where
1618  A::Item: PartialEq,
1619{
1620  #[inline]
1621  fn eq(&self, other: &&A) -> bool {
1622    self.as_slice().eq(other.as_slice())
1623  }
1624}
1625
1626impl<A: Array> PartialEq<&[A::Item]> for TinyVec<A>
1627where
1628  A::Item: PartialEq,
1629{
1630  #[inline]
1631  fn eq(&self, other: &&[A::Item]) -> bool {
1632    self.as_slice().eq(*other)
1633  }
1634}
1635
1636impl<A: Array> Hash for TinyVec<A>
1637where
1638  A::Item: Hash,
1639{
1640  #[inline]
1641  fn hash<H: Hasher>(&self, state: &mut H) {
1642    self.as_slice().hash(state)
1643  }
1644}
1645
1646// // // // // // // //
1647// Formatting impls
1648// // // // // // // //
1649
1650impl<A: Array> Binary for TinyVec<A>
1651where
1652  A::Item: Binary,
1653{
1654  #[allow(clippy::missing_inline_in_public_items)]
1655  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1656    write!(f, "[")?;
1657    if f.alternate() {
1658      write!(f, "\n    ")?;
1659    }
1660    for (i, elem) in self.iter().enumerate() {
1661      if i > 0 {
1662        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1663      }
1664      Binary::fmt(elem, f)?;
1665    }
1666    if f.alternate() {
1667      write!(f, ",\n")?;
1668    }
1669    write!(f, "]")
1670  }
1671}
1672
1673impl<A: Array> Debug for TinyVec<A>
1674where
1675  A::Item: Debug,
1676{
1677  #[allow(clippy::missing_inline_in_public_items)]
1678  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1679    write!(f, "[")?;
1680    if f.alternate() && !self.is_empty() {
1681      write!(f, "\n    ")?;
1682    }
1683    for (i, elem) in self.iter().enumerate() {
1684      if i > 0 {
1685        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1686      }
1687      Debug::fmt(elem, f)?;
1688    }
1689    if f.alternate() && !self.is_empty() {
1690      write!(f, ",\n")?;
1691    }
1692    write!(f, "]")
1693  }
1694}
1695
1696impl<A: Array> Display for TinyVec<A>
1697where
1698  A::Item: Display,
1699{
1700  #[allow(clippy::missing_inline_in_public_items)]
1701  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1702    write!(f, "[")?;
1703    if f.alternate() {
1704      write!(f, "\n    ")?;
1705    }
1706    for (i, elem) in self.iter().enumerate() {
1707      if i > 0 {
1708        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1709      }
1710      Display::fmt(elem, f)?;
1711    }
1712    if f.alternate() {
1713      write!(f, ",\n")?;
1714    }
1715    write!(f, "]")
1716  }
1717}
1718
1719impl<A: Array> LowerExp for TinyVec<A>
1720where
1721  A::Item: LowerExp,
1722{
1723  #[allow(clippy::missing_inline_in_public_items)]
1724  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1725    write!(f, "[")?;
1726    if f.alternate() {
1727      write!(f, "\n    ")?;
1728    }
1729    for (i, elem) in self.iter().enumerate() {
1730      if i > 0 {
1731        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1732      }
1733      LowerExp::fmt(elem, f)?;
1734    }
1735    if f.alternate() {
1736      write!(f, ",\n")?;
1737    }
1738    write!(f, "]")
1739  }
1740}
1741
1742impl<A: Array> LowerHex for TinyVec<A>
1743where
1744  A::Item: LowerHex,
1745{
1746  #[allow(clippy::missing_inline_in_public_items)]
1747  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1748    write!(f, "[")?;
1749    if f.alternate() {
1750      write!(f, "\n    ")?;
1751    }
1752    for (i, elem) in self.iter().enumerate() {
1753      if i > 0 {
1754        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1755      }
1756      LowerHex::fmt(elem, f)?;
1757    }
1758    if f.alternate() {
1759      write!(f, ",\n")?;
1760    }
1761    write!(f, "]")
1762  }
1763}
1764
1765impl<A: Array> Octal for TinyVec<A>
1766where
1767  A::Item: Octal,
1768{
1769  #[allow(clippy::missing_inline_in_public_items)]
1770  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1771    write!(f, "[")?;
1772    if f.alternate() {
1773      write!(f, "\n    ")?;
1774    }
1775    for (i, elem) in self.iter().enumerate() {
1776      if i > 0 {
1777        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1778      }
1779      Octal::fmt(elem, f)?;
1780    }
1781    if f.alternate() {
1782      write!(f, ",\n")?;
1783    }
1784    write!(f, "]")
1785  }
1786}
1787
1788impl<A: Array> Pointer for TinyVec<A>
1789where
1790  A::Item: Pointer,
1791{
1792  #[allow(clippy::missing_inline_in_public_items)]
1793  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1794    write!(f, "[")?;
1795    if f.alternate() {
1796      write!(f, "\n    ")?;
1797    }
1798    for (i, elem) in self.iter().enumerate() {
1799      if i > 0 {
1800        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1801      }
1802      Pointer::fmt(elem, f)?;
1803    }
1804    if f.alternate() {
1805      write!(f, ",\n")?;
1806    }
1807    write!(f, "]")
1808  }
1809}
1810
1811impl<A: Array> UpperExp for TinyVec<A>
1812where
1813  A::Item: UpperExp,
1814{
1815  #[allow(clippy::missing_inline_in_public_items)]
1816  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1817    write!(f, "[")?;
1818    if f.alternate() {
1819      write!(f, "\n    ")?;
1820    }
1821    for (i, elem) in self.iter().enumerate() {
1822      if i > 0 {
1823        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1824      }
1825      UpperExp::fmt(elem, f)?;
1826    }
1827    if f.alternate() {
1828      write!(f, ",\n")?;
1829    }
1830    write!(f, "]")
1831  }
1832}
1833
1834impl<A: Array> UpperHex for TinyVec<A>
1835where
1836  A::Item: UpperHex,
1837{
1838  #[allow(clippy::missing_inline_in_public_items)]
1839  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1840    write!(f, "[")?;
1841    if f.alternate() {
1842      write!(f, "\n    ")?;
1843    }
1844    for (i, elem) in self.iter().enumerate() {
1845      if i > 0 {
1846        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1847      }
1848      UpperHex::fmt(elem, f)?;
1849    }
1850    if f.alternate() {
1851      write!(f, ",\n")?;
1852    }
1853    write!(f, "]")
1854  }
1855}
1856
1857#[cfg(feature = "serde")]
1858#[cfg_attr(docs_rs, doc(cfg(feature = "alloc")))]
1859struct TinyVecVisitor<A: Array>(PhantomData<A>);
1860
1861#[cfg(feature = "serde")]
1862impl<'de, A: Array> Visitor<'de> for TinyVecVisitor<A>
1863where
1864  A::Item: Deserialize<'de>,
1865{
1866  type Value = TinyVec<A>;
1867
1868  fn expecting(
1869    &self, formatter: &mut core::fmt::Formatter,
1870  ) -> core::fmt::Result {
1871    formatter.write_str("a sequence")
1872  }
1873
1874  fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
1875  where
1876    S: SeqAccess<'de>,
1877  {
1878    let mut new_tinyvec = match seq.size_hint() {
1879      Some(expected_size) => TinyVec::with_capacity(expected_size),
1880      None => Default::default(),
1881    };
1882
1883    while let Some(value) = seq.next_element()? {
1884      new_tinyvec.push(value);
1885    }
1886
1887    Ok(new_tinyvec)
1888  }
1889}