Skip to main content

smallvec/
lib.rs

1// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
2// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
3// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
4// option. This file may not be copied, modified, or distributed
5// except according to those terms.
6
7//! Small vectors in various sizes. These store a certain number of elements
8//! inline, and fall back to the heap for larger allocations.  This can be a
9//! useful optimization for improving cache locality and reducing allocator
10//! traffic for workloads that fit within the inline buffer.
11//!
12//! ## `no_std` support
13//!
14//! By default, `smallvec` does not depend on `std`.  However, the optional
15//! `write` feature implements the `std::io::Write` trait for vectors of `u8`.
16//! When this feature is enabled, `smallvec` depends on `std`.
17//!
18//! ## Optional features
19//!
20//! ### `serde`
21//!
22//! When this optional dependency is enabled, `SmallVec` implements the
23//! `serde::Serialize` and `serde::Deserialize` traits.
24//!
25//! ### `write`
26//!
27//! When this feature is enabled, `SmallVec<[u8; _]>` implements the
28//! `std::io::Write` trait. This feature is not compatible with `#![no_std]`
29//! programs.
30//!
31//! ### `union`
32//!
33//! **This feature requires Rust 1.49.**
34//!
35//! When the `union` feature is enabled `smallvec` will track its state (inline
36//! or spilled) without the use of an enum tag, reducing the size of the
37//! `smallvec` by one machine word. This means that there is potentially no
38//! space overhead compared to `Vec`. Note that `smallvec` can still be larger
39//! than `Vec` if the inline buffer is larger than two machine words.
40//!
41//! To use this feature add `features = ["union"]` in the `smallvec` section of
42//! Cargo.toml. Note that this feature requires Rust 1.49.
43//!
44//! Tracking issue: [rust-lang/rust#55149](https://github.com/rust-lang/rust/issues/55149)
45//!
46//! ### `const_generics`
47//!
48//! **This feature requires Rust 1.51.**
49//!
50//! When this feature is enabled, `SmallVec` works with any arrays of any size,
51//! not just a fixed list of sizes.
52//!
53//! ### `const_new`
54//!
55//! **This feature requires Rust 1.51.**
56//!
57//! This feature exposes the functions [`SmallVec::new_const`],
58//! [`SmallVec::from_const`], and [`smallvec_inline`] which enables the
59//! `SmallVec` to be initialized from a const context. For details, see the
60//! [Rust Reference](https://doc.rust-lang.org/reference/const_eval.html#const-functions).
61//!
62//! ### `drain_filter`
63//!
64//! **This feature is unstable.** It may change to match the unstable
65//! `drain_filter` method in libstd.
66//!
67//! Enables the `drain_filter` method, which produces an iterator that calls a
68//! user-provided closure to determine which elements of the vector to remove
69//! and yield from the iterator.
70//!
71//! ### `drain_keep_rest`
72//!
73//! **This feature is unstable.** It may change to match the unstable
74//! `drain_keep_rest` method in libstd.
75//!
76//! Enables the `DrainFilter::keep_rest` method.
77//!
78//! ### `specialization`
79//!
80//! **This feature is unstable and requires a nightly build of the Rust
81//! toolchain.**
82//!
83//! When this feature is enabled, `SmallVec::from(slice)` has improved
84//! performance for slices of `Copy` types.  (Without this feature, you can use
85//! `SmallVec::from_slice` to get optimal performance for `Copy` types.)
86//!
87//! Tracking issue: [rust-lang/rust#31844](https://github.com/rust-lang/rust/issues/31844)
88//!
89//! ### `may_dangle`
90//!
91//! **This feature is unstable and requires a nightly build of the Rust
92//! toolchain.**
93//!
94//! This feature makes the Rust compiler less strict about use of vectors that
95//! contain borrowed references. For details, see the
96//! [Rustonomicon](https://doc.rust-lang.org/1.42.0/nomicon/dropck.html#an-escape-hatch).
97//!
98//! Tracking issue: [rust-lang/rust#34761](https://github.com/rust-lang/rust/issues/34761)
99
100#![no_std]
101#![cfg_attr(docsrs, feature(doc_cfg))]
102#![cfg_attr(feature = "specialization", allow(incomplete_features))]
103#![cfg_attr(feature = "specialization", feature(specialization))]
104#![cfg_attr(feature = "may_dangle", feature(dropck_eyepatch))]
105#![deny(missing_docs)]
106
107#[doc(hidden)]
108pub extern crate alloc;
109
110#[cfg(any(test, feature = "write"))]
111extern crate std;
112
113#[cfg(test)]
114mod tests;
115
116#[cfg(feature = "drain_keep_rest")]
117use core::mem::ManuallyDrop;
118#[cfg(feature = "malloc_size_of")]
119use malloc_size_of::{
120    MallocShallowSizeOf,
121    MallocSizeOf,
122    MallocSizeOfOps
123};
124#[cfg(feature = "serde")]
125use serde::{
126    de::{
127        Deserialize,
128        Deserializer,
129        SeqAccess,
130        Visitor
131    },
132    ser::{
133        Serialize,
134        SerializeSeq,
135        Serializer
136    }
137};
138#[cfg(feature = "write")]
139use std::io;
140#[allow(deprecated)]
141use {
142    alloc::{
143        alloc::{
144            Layout,
145            LayoutErr
146        },
147        boxed::Box,
148        vec,
149        vec::Vec
150    },
151    core::{
152        borrow::{
153            Borrow,
154            BorrowMut
155        },
156        cmp,
157        fmt,
158        hash::{
159            Hash,
160            Hasher
161        },
162        hint::unreachable_unchecked,
163        iter::{
164            FromIterator,
165            FusedIterator,
166            IntoIterator,
167            repeat
168        },
169        marker::PhantomData,
170        mem::{
171            self,
172            MaybeUninit
173        },
174        ops::{
175            self,
176            Range,
177            RangeBounds
178        },
179        ptr::{
180            self,
181            NonNull
182        },
183        slice::{
184            self,
185            SliceIndex
186        }
187    }
188};
189
190/// Creates a [`SmallVec`] containing the arguments.
191///
192/// `smallvec!` allows `SmallVec`s to be defined with the same syntax as array
193/// expressions. There are two forms of this macro:
194///
195/// - Create a [`SmallVec`] containing a given list of elements:
196///
197/// ```
198/// # use smallvec::{smallvec, SmallVec};
199/// # fn main() {
200/// let v: SmallVec<[_; 128]> = smallvec![1, 2, 3];
201/// assert_eq!(v[0], 1);
202/// assert_eq!(v[1], 2);
203/// assert_eq!(v[2], 3);
204/// # }
205/// ```
206///
207/// - Create a [`SmallVec`] from a given element and size:
208///
209/// ```
210/// # use smallvec::{smallvec, SmallVec};
211/// # fn main() {
212/// let v: SmallVec<[_; 10]> = smallvec![1; 3];
213/// assert_eq!(v, SmallVec::from_buf([1, 1, 1]));
214/// # }
215/// ```
216///
217/// Note that unlike array expressions this syntax supports all elements
218/// which implement [`Clone`] and the number of elements doesn't have to be
219/// a constant.
220///
221/// This will use `clone` to duplicate an expression, so one should be careful
222/// using this with types having a nonstandard `Clone` implementation. For
223/// example, `smallvec![Rc::new(1); 5]` will create a vector of five references
224/// to the same boxed integer value, not five references pointing to
225/// independently boxed integers.
226#[macro_export]
227macro_rules! smallvec {
228    // count helper: transform any expression into 1
229    (@one $x:expr) => (1usize);
230    () => (
231        $crate::SmallVec::new()
232    );
233    ($elem:expr; $n:expr) => ({
234        $crate::SmallVec::from_elem($elem, $n)
235    });
236    ($($x:expr),+$(,)?) => ({
237        let count = 0usize $(+ $crate::smallvec!(@one $x))+;
238        let mut vec = $crate::SmallVec::new();
239        if count <= vec.inline_size() {
240            $(vec.push($x);)*
241            vec
242        } else {
243            $crate::SmallVec::from_vec($crate::alloc::vec![$($x,)+])
244        }
245    });
246}
247
248/// Creates an inline [`SmallVec`] containing the arguments. This macro is
249/// enabled by the feature `const_new`.
250///
251/// `smallvec_inline!` allows `SmallVec`s to be defined with the same syntax as
252/// array expressions in `const` contexts. The inline storage `A` will always be
253/// an array of the size specified by the arguments. There are two forms of this
254/// macro:
255///
256/// - Create a [`SmallVec`] containing a given list of elements:
257///
258/// ```
259/// # use smallvec::{smallvec_inline, SmallVec};
260/// # fn main() {
261/// const V: SmallVec<[i32; 3]> = smallvec_inline![1, 2, 3];
262/// assert_eq!(V[0], 1);
263/// assert_eq!(V[1], 2);
264/// assert_eq!(V[2], 3);
265/// # }
266/// ```
267///
268/// - Create a [`SmallVec`] from a given element and size:
269///
270/// ```
271/// # use smallvec::{smallvec_inline, SmallVec};
272/// # fn main() {
273/// const V: SmallVec<[i32; 3]> = smallvec_inline![1; 3];
274/// assert_eq!(V, SmallVec::from_buf([1, 1, 1]));
275/// # }
276/// ```
277///
278/// Note that the behavior mimics that of array expressions, in contrast to
279/// [`smallvec`].
280#[cfg(feature = "const_new")]
281#[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
282#[macro_export]
283macro_rules! smallvec_inline {
284    // count helper: transform any expression into 1
285    (@one $x:expr) => (1usize);
286    ($elem:expr; $n:expr) => ({
287        $crate::SmallVec::<[_; $n]>::from_const([$elem; $n])
288    });
289    ($($x:expr),+ $(,)?) => ({
290        const N: usize = 0usize $(+ $crate::smallvec_inline!(@one $x))*;
291        $crate::SmallVec::<[_; N]>::from_const([$($x,)*])
292    });
293}
294
295/// `panic!()` in debug builds, optimization hint in release.
296#[cfg(not(feature = "union"))]
297macro_rules! debug_unreachable {
298    () => {
299        debug_unreachable!("entered unreachable code")
300    };
301    ($e:expr) => {
302        if cfg!(debug_assertions) {
303            panic!($e);
304        } else {
305            unreachable_unchecked();
306        }
307    };
308}
309
310/// Trait to be implemented by a collection that can be extended from a slice
311///
312/// ## Example
313///
314/// ```rust
315/// use smallvec::{
316///     ExtendFromSlice,
317///     SmallVec
318/// };
319///
320/// fn initialize<V: ExtendFromSlice<u8>>(v: &mut V) { v.extend_from_slice(b"Test!"); }
321///
322/// let mut vec = Vec::new();
323/// initialize(&mut vec);
324/// assert_eq!(&vec, b"Test!");
325///
326/// let mut small_vec = SmallVec::<[u8; 8]>::new();
327/// initialize(&mut small_vec);
328/// assert_eq!(&small_vec as &[_], b"Test!");
329/// ```
330#[doc(hidden)]
331#[deprecated]
332pub trait ExtendFromSlice<T> {
333    /// Extends a collection from a slice of its element type
334    fn extend_from_slice(&mut self, other: &[T]);
335}
336
337#[allow(deprecated)]
338impl<T: Clone> ExtendFromSlice<T> for Vec<T> {
339    fn extend_from_slice(&mut self, other: &[T]) { Vec::extend_from_slice(self, other) }
340}
341
342/// Error type for APIs with fallible heap allocation
343#[derive(Debug)]
344pub enum CollectionAllocErr {
345    /// Overflow `usize::MAX` or other error during size computation
346    CapacityOverflow,
347    /// The allocator return an error
348    AllocErr {
349        /// The layout that was passed to the allocator
350        layout: Layout
351    }
352}
353
354impl fmt::Display for CollectionAllocErr {
355    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
356        write!(f, "Allocation error: {:?}", self)
357    }
358}
359
360#[allow(deprecated)]
361impl From<LayoutErr> for CollectionAllocErr {
362    fn from(_: LayoutErr) -> Self { CollectionAllocErr::CapacityOverflow }
363}
364
365fn infallible<T>(result: Result<T, CollectionAllocErr>) -> T {
366    match result {
367        Ok(x) => x,
368        Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"),
369        Err(CollectionAllocErr::AllocErr {
370            layout
371        }) => alloc::alloc::handle_alloc_error(layout)
372    }
373}
374
375/// FIXME: use `Layout::array` when we require a Rust version where it’s stable
376/// <https://github.com/rust-lang/rust/issues/55724>
377fn layout_array<T>(n: usize) -> Result<Layout, CollectionAllocErr> {
378    let size = mem::size_of::<T>()
379        .checked_mul(n)
380        .ok_or(CollectionAllocErr::CapacityOverflow)?;
381    let align = mem::align_of::<T>();
382    Layout::from_size_align(size, align).map_err(|_| CollectionAllocErr::CapacityOverflow)
383}
384
385unsafe fn deallocate<T>(ptr: NonNull<T>, capacity: usize) {
386    // This unwrap should succeed since the same did when allocating.
387    let layout = layout_array::<T>(capacity).unwrap();
388    alloc::alloc::dealloc(ptr.as_ptr() as *mut u8, layout)
389}
390
391/// An iterator that removes the items from a `SmallVec` and yields them by
392/// value.
393///
394/// Returned from [`SmallVec::drain`][1].
395///
396/// [1]: struct.SmallVec.html#method.drain
397pub struct Drain<'a, T: 'a + Array> {
398    tail_start: usize,
399    tail_len: usize,
400    iter: slice::Iter<'a, T::Item>,
401    vec: NonNull<SmallVec<T>>
402}
403
404impl<'a, T: 'a + Array> fmt::Debug for Drain<'a, T>
405where T::Item: fmt::Debug
406{
407    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
408        f.debug_tuple("Drain").field(&self.iter.as_slice()).finish()
409    }
410}
411
412unsafe impl<'a, T: Sync + Array> Sync for Drain<'a, T> {}
413unsafe impl<'a, T: Send + Array> Send for Drain<'a, T> {}
414
415impl<'a, T: 'a + Array> Iterator for Drain<'a, T> {
416    type Item = T::Item;
417
418    #[inline]
419    fn next(&mut self) -> Option<T::Item> {
420        self.iter
421            .next()
422            .map(|reference| unsafe { ptr::read(reference) })
423    }
424
425    #[inline]
426    fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
427}
428
429impl<'a, T: 'a + Array> DoubleEndedIterator for Drain<'a, T> {
430    #[inline]
431    fn next_back(&mut self) -> Option<T::Item> {
432        self.iter
433            .next_back()
434            .map(|reference| unsafe { ptr::read(reference) })
435    }
436}
437
438impl<'a, T: Array> ExactSizeIterator for Drain<'a, T> {
439    #[inline]
440    fn len(&self) -> usize { self.iter.len() }
441}
442
443impl<'a, T: Array> FusedIterator for Drain<'a, T> {}
444
445impl<'a, T: 'a + Array> Drop for Drain<'a, T> {
446    fn drop(&mut self) {
447        self.for_each(drop);
448
449        if self.tail_len > 0 {
450            unsafe {
451                let source_vec = self.vec.as_mut();
452
453                // memmove back untouched tail, update to new length
454                let start = source_vec.len();
455                let tail = self.tail_start;
456                if tail != start {
457                    // as_mut_ptr creates a &mut, invalidating other pointers.
458                    // This pattern avoids calling it with a pointer already
459                    // present.
460                    let ptr = source_vec.as_mut_ptr();
461                    let src = ptr.add(tail);
462                    let dst = ptr.add(start);
463                    ptr::copy(src, dst, self.tail_len);
464                }
465                source_vec.set_len(start + self.tail_len);
466            }
467        }
468    }
469}
470
471#[cfg(feature = "drain_filter")]
472/// An iterator which uses a closure to determine if an element should be
473/// removed.
474///
475/// Returned from [`SmallVec::drain_filter`][1].
476///
477/// [1]: struct.SmallVec.html#method.drain_filter
478pub struct DrainFilter<'a, T, F>
479where
480    F: FnMut(&mut T::Item) -> bool,
481    T: Array
482{
483    vec: &'a mut SmallVec<T>,
484    /// The index of the item that will be inspected by the next call to `next`.
485    idx: usize,
486    /// The number of items that have been drained (removed) thus far.
487    del: usize,
488    /// The original length of `vec` prior to draining.
489    old_len: usize,
490    /// The filter test predicate.
491    pred: F,
492    /// A flag that indicates a panic has occurred in the filter test predicate.
493    /// This is used as a hint in the drop implementation to prevent consumption
494    /// of the remainder of the `DrainFilter`. Any unprocessed items will be
495    /// backshifted in the `vec`, but no further items will be dropped or
496    /// tested by the filter predicate.
497    panic_flag: bool
498}
499
500#[cfg(feature = "drain_filter")]
501impl<T, F> fmt::Debug for DrainFilter<'_, T, F>
502where
503    F: FnMut(&mut T::Item) -> bool,
504    T: Array,
505    T::Item: fmt::Debug
506{
507    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
508        f.debug_tuple("DrainFilter")
509            .field(&self.vec.as_slice())
510            .finish()
511    }
512}
513
514#[cfg(feature = "drain_filter")]
515impl<T, F> Iterator for DrainFilter<'_, T, F>
516where
517    F: FnMut(&mut T::Item) -> bool,
518    T: Array
519{
520    type Item = T::Item;
521
522    fn next(&mut self) -> Option<T::Item> {
523        unsafe {
524            while self.idx < self.old_len {
525                let i = self.idx;
526                let v = slice::from_raw_parts_mut(self.vec.as_mut_ptr(), self.old_len);
527                self.panic_flag = true;
528                let drained = (self.pred)(&mut v[i]);
529                self.panic_flag = false;
530                // Update the index *after* the predicate is called. If the
531                // index is updated prior and the predicate
532                // panics, the element at this index would be
533                // leaked.
534                self.idx += 1;
535                if drained {
536                    self.del += 1;
537                    return Some(ptr::read(&v[i]));
538                } else if self.del > 0 {
539                    let del = self.del;
540                    let src: *const Self::Item = &v[i];
541                    let dst: *mut Self::Item = &mut v[i - del];
542                    ptr::copy_nonoverlapping(src, dst, 1);
543                }
544            }
545            None
546        }
547    }
548
549    fn size_hint(&self) -> (usize, Option<usize>) { (0, Some(self.old_len - self.idx)) }
550}
551
552#[cfg(feature = "drain_filter")]
553impl<T, F> Drop for DrainFilter<'_, T, F>
554where
555    F: FnMut(&mut T::Item) -> bool,
556    T: Array
557{
558    fn drop(&mut self) {
559        struct BackshiftOnDrop<'a, 'b, T, F>
560        where
561            F: FnMut(&mut T::Item) -> bool,
562            T: Array
563        {
564            drain: &'b mut DrainFilter<'a, T, F>
565        }
566
567        impl<'a, 'b, T, F> Drop for BackshiftOnDrop<'a, 'b, T, F>
568        where
569            F: FnMut(&mut T::Item) -> bool,
570            T: Array
571        {
572            fn drop(&mut self) {
573                unsafe {
574                    if self.drain.idx < self.drain.old_len && self.drain.del > 0 {
575                        // This is a pretty messed up state, and there isn't
576                        // really an obviously right
577                        // thing to do. We don't want to keep trying
578                        // to execute `pred`, so we just backshift all the
579                        // unprocessed elements and tell
580                        // the vec that they still exist. The backshift
581                        // is required to prevent a double-drop of the last
582                        // successfully drained item
583                        // prior to a panic in the predicate.
584                        let ptr = self.drain.vec.as_mut_ptr();
585                        let src = ptr.add(self.drain.idx);
586                        let dst = src.sub(self.drain.del);
587                        let tail_len = self.drain.old_len - self.drain.idx;
588                        src.copy_to(dst, tail_len);
589                    }
590                    self.drain.vec.set_len(self.drain.old_len - self.drain.del);
591                }
592            }
593        }
594
595        let backshift = BackshiftOnDrop {
596            drain: self
597        };
598
599        // Attempt to consume any remaining elements if the filter predicate
600        // has not yet panicked. We'll backshift any remaining elements
601        // whether we've already panicked or if the consumption here panics.
602        if !backshift.drain.panic_flag {
603            backshift.drain.for_each(drop);
604        }
605    }
606}
607
608#[cfg(feature = "drain_keep_rest")]
609impl<T, F> DrainFilter<'_, T, F>
610where
611    F: FnMut(&mut T::Item) -> bool,
612    T: Array
613{
614    /// Keep unyielded elements in the source `Vec`.
615    ///
616    /// # Examples
617    ///
618    /// ```
619    /// # use smallvec::{smallvec, SmallVec};
620    ///
621    /// let mut vec: SmallVec<[char; 2]> = smallvec!['a', 'b', 'c'];
622    /// let mut drain = vec.drain_filter(|_| true);
623    ///
624    /// assert_eq!(drain.next().unwrap(), 'a');
625    ///
626    /// // This call keeps 'b' and 'c' in the vec.
627    /// drain.keep_rest();
628    ///
629    /// // If we wouldn't call `keep_rest()`,
630    /// // `vec` would be empty.
631    /// assert_eq!(vec, SmallVec::<[char; 2]>::from_slice(&['b', 'c']));
632    /// ```
633    pub fn keep_rest(self) {
634        // At this moment layout looks like this:
635        //
636        //  _____________________/-- old_len
637        // /                     \
638        // [kept] [yielded] [tail]
639        //        \_______/ ^-- idx
640        //                \-- del
641        //
642        // Normally `Drop` impl would drop [tail] (via .for_each(drop), ie still
643        // calling `pred`)
644        //
645        // 1. Move [tail] after [kept]
646        // 2. Update length of the original vec to `old_len - del` a. In case of
647        //    ZST, this is the only thing we want to do
648        // 3. Do *not* drop self, as everything is put in a consistent state
649        //    already, there is nothing to do
650        let mut this = ManuallyDrop::new(self);
651
652        unsafe {
653            // ZSTs have no identity, so we don't need to move them around.
654            let needs_move = mem::size_of::<T::Item>() != 0;
655
656            if needs_move && this.idx < this.old_len && this.del > 0 {
657                let ptr = this.vec.as_mut_ptr();
658                let src = ptr.add(this.idx);
659                let dst = src.sub(this.del);
660                let tail_len = this.old_len - this.idx;
661                src.copy_to(dst, tail_len);
662            }
663
664            let new_len = this.old_len - this.del;
665            this.vec.set_len(new_len);
666        }
667    }
668}
669
670#[cfg(feature = "union")]
671union SmallVecData<A: Array> {
672    inline: core::mem::ManuallyDrop<MaybeUninit<A>>,
673    heap: (NonNull<A::Item>, usize)
674}
675
676#[cfg(all(feature = "union", feature = "const_new"))]
677impl<T, const N: usize> SmallVecData<[T; N]> {
678    #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
679    #[inline]
680    const fn from_const(inline: MaybeUninit<[T; N]>) -> Self {
681        SmallVecData {
682            inline: core::mem::ManuallyDrop::new(inline)
683        }
684    }
685}
686
687#[cfg(feature = "union")]
688impl<A: Array> SmallVecData<A> {
689    #[inline]
690    unsafe fn inline(&self) -> ConstNonNull<A::Item> {
691        ConstNonNull::new(self.inline.as_ptr() as *const A::Item).unwrap()
692    }
693
694    #[inline]
695    unsafe fn inline_mut(&mut self) -> NonNull<A::Item> {
696        NonNull::new(self.inline.as_mut_ptr() as *mut A::Item).unwrap()
697    }
698
699    #[inline]
700    fn from_inline(inline: MaybeUninit<A>) -> SmallVecData<A> {
701        SmallVecData {
702            inline: core::mem::ManuallyDrop::new(inline)
703        }
704    }
705
706    // Workaround for https://github.com/rust-lang/rust/issues/157743: when from_inline is
707    // called with MaybeUninit::uninit(), rustc 1.93+ GVN propagates const
708    // <uninit> into the ManuallyDrop::new() aggregate, causing LLVM to
709    // materialize a global constant that MemCpyOpt then collapses into a
710    // memset over the whole struct. Using assume_init() of a doubly-wrapped
711    // MaybeUninit produces Immediate::Uninit instead of const <uninit>,
712    // which codegen handles as undef without emitting any global. This
713    // function also avoids introducing an intermediate local that would
714    // inflate stack frames in debug builds.
715    #[inline]
716    fn empty() -> SmallVecData<A> {
717        // SAFETY: ManuallyDrop<MaybeUninit<A>> is valid for any bit pattern
718        // including uninitialized bytes, so assume_init() on a
719        // MaybeUninit of that type is sound.
720        SmallVecData {
721            inline: unsafe { MaybeUninit::uninit().assume_init() }
722        }
723    }
724
725    #[inline]
726    unsafe fn into_inline(self) -> MaybeUninit<A> {
727        core::mem::ManuallyDrop::into_inner(self.inline)
728    }
729
730    #[inline]
731    unsafe fn heap(&self) -> (ConstNonNull<A::Item>, usize) {
732        (ConstNonNull(self.heap.0), self.heap.1)
733    }
734
735    #[inline]
736    unsafe fn heap_mut(&mut self) -> (NonNull<A::Item>, &mut usize) {
737        let h = &mut self.heap;
738        (h.0, &mut h.1)
739    }
740
741    #[inline]
742    fn from_heap(ptr: NonNull<A::Item>, len: usize) -> SmallVecData<A> {
743        SmallVecData {
744            heap: (ptr, len)
745        }
746    }
747}
748
749#[cfg(not(feature = "union"))]
750enum SmallVecData<A: Array> {
751    Inline(MaybeUninit<A>),
752    // Using NonNull and NonZero here allows to reduce size of `SmallVec`.
753    Heap {
754        // Since we never allocate on heap
755        // unless our capacity is bigger than inline capacity
756        // heap capacity cannot be less than 1.
757        // Therefore, pointer cannot be null too.
758        ptr: NonNull<A::Item>,
759        len: usize
760    }
761}
762
763#[cfg(all(not(feature = "union"), feature = "const_new"))]
764impl<T, const N: usize> SmallVecData<[T; N]> {
765    #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
766    #[inline]
767    const fn from_const(inline: MaybeUninit<[T; N]>) -> Self { SmallVecData::Inline(inline) }
768}
769
770#[cfg(not(feature = "union"))]
771impl<A: Array> SmallVecData<A> {
772    #[inline]
773    unsafe fn inline(&self) -> ConstNonNull<A::Item> {
774        match self {
775            SmallVecData::Inline(a) => ConstNonNull::new(a.as_ptr() as *const A::Item).unwrap(),
776            _ => debug_unreachable!()
777        }
778    }
779
780    #[inline]
781    unsafe fn inline_mut(&mut self) -> NonNull<A::Item> {
782        match self {
783            SmallVecData::Inline(a) => NonNull::new(a.as_mut_ptr() as *mut A::Item).unwrap(),
784            _ => debug_unreachable!()
785        }
786    }
787
788    #[inline]
789    fn from_inline(inline: MaybeUninit<A>) -> SmallVecData<A> { SmallVecData::Inline(inline) }
790
791    // See the comment on the union variant's empty() for why this exists.
792    #[inline]
793    fn empty() -> SmallVecData<A> {
794        // SAFETY: MaybeUninit<A> is valid for any bit pattern including
795        // uninitialized bytes, so assume_init() on a MaybeUninit of
796        // that type is sound.
797        SmallVecData::Inline(unsafe { MaybeUninit::uninit().assume_init() })
798    }
799
800    #[inline]
801    unsafe fn into_inline(self) -> MaybeUninit<A> {
802        match self {
803            SmallVecData::Inline(a) => a,
804            _ => debug_unreachable!()
805        }
806    }
807
808    #[inline]
809    unsafe fn heap(&self) -> (ConstNonNull<A::Item>, usize) {
810        match self {
811            SmallVecData::Heap {
812                ptr,
813                len
814            } => (ConstNonNull(*ptr), *len),
815            _ => debug_unreachable!()
816        }
817    }
818
819    #[inline]
820    unsafe fn heap_mut(&mut self) -> (NonNull<A::Item>, &mut usize) {
821        match self {
822            SmallVecData::Heap {
823                ptr,
824                len
825            } => (*ptr, len),
826            _ => debug_unreachable!()
827        }
828    }
829
830    #[inline]
831    fn from_heap(ptr: NonNull<A::Item>, len: usize) -> SmallVecData<A> {
832        SmallVecData::Heap {
833            ptr,
834            len
835        }
836    }
837}
838
839unsafe impl<A: Array + Send> Send for SmallVecData<A> {}
840unsafe impl<A: Array + Sync> Sync for SmallVecData<A> {}
841
842/// A `Vec`-like container that can store a small number of elements inline.
843///
844/// `SmallVec` acts like a vector, but can store a limited amount of data inline
845/// within the `SmallVec` struct rather than in a separate allocation.  If the
846/// data exceeds this limit, the `SmallVec` will "spill" its data onto the heap,
847/// allocating a new buffer to hold it.
848///
849/// The amount of data that a `SmallVec` can store inline depends on its backing
850/// store. The backing store can be any type that implements the `Array` trait;
851/// usually it is a small fixed-sized array.  For example a `SmallVec<[u64; 8]>`
852/// can hold up to eight 64-bit integers inline.
853///
854/// ## Example
855///
856/// ```rust
857/// use smallvec::SmallVec;
858/// let mut v = SmallVec::<[u8; 4]>::new(); // initialize an empty vector
859///
860/// // The vector can hold up to 4 items without spilling onto the heap.
861/// v.extend(0..4);
862/// assert_eq!(v.len(), 4);
863/// assert!(!v.spilled());
864///
865/// // Pushing another element will force the buffer to spill:
866/// v.push(4);
867/// assert_eq!(v.len(), 5);
868/// assert!(v.spilled());
869/// ```
870///
871/// References used by an element's destructor must outlive the vector, even
872/// with the `may_dangle` feature and no inline storage:
873///
874/// ```compile_fail,E0597
875/// use smallvec::SmallVec;
876///
877/// struct PrintOnDrop<'a>(&'a str);
878/// impl Drop for PrintOnDrop<'_> {
879///     fn drop(&mut self) {
880///         println!("{}", self.0);
881///     }
882/// }
883///
884/// let mut v = SmallVec::<[PrintOnDrop<'_>; 0]>::new();
885/// let text = String::from("borrowed");
886/// v.push(PrintOnDrop(&text));
887/// // `text` is dropped before `v`, whose elements still need it.
888/// ```
889pub struct SmallVec<A: Array> {
890    // The capacity field is used to determine which of the storage variants is
891    // active: If capacity <= Self::inline_capacity() then the inline variant is
892    // used and capacity holds the current length of the vector (number of
893    // elements actually in use). If capacity > Self::inline_capacity() then the
894    // heap variant is used and capacity holds the size of the
895    // memory allocation.
896    capacity: usize,
897    data: SmallVecData<A>,
898    // Own A::Item, including when A has length zero and all items are on the
899    // heap. This is required for sound drop checking with #[may_dangle].
900    _marker: PhantomData<A::Item>
901}
902
903impl<A: Array> SmallVec<A> {
904    /// Construct an empty vector
905    #[inline]
906    pub fn new() -> SmallVec<A> {
907        // Try to detect invalid custom implementations of `Array`. Hopefully,
908        // this check should be optimized away entirely for valid ones.
909        assert!(
910            mem::size_of::<A>() == A::size() * mem::size_of::<A::Item>()
911                && mem::align_of::<A>() >= mem::align_of::<A::Item>()
912        );
913        SmallVec {
914            capacity: 0,
915            data: SmallVecData::empty(),
916            _marker: PhantomData
917        }
918    }
919
920    /// Construct an empty vector with enough capacity pre-allocated to store at
921    /// least `n` elements.
922    ///
923    /// Will create a heap allocation only if `n` is larger than the inline
924    /// capacity.
925    ///
926    /// ```
927    /// # use smallvec::SmallVec;
928    ///
929    /// let v: SmallVec<[u8; 3]> = SmallVec::with_capacity(100);
930    ///
931    /// assert!(v.is_empty());
932    /// assert!(v.capacity() >= 100);
933    /// ```
934    #[inline]
935    pub fn with_capacity(n: usize) -> Self {
936        let mut v = SmallVec::new();
937        v.reserve_exact(n);
938        v
939    }
940
941    /// Construct a new `SmallVec` from a `Vec<A::Item>`.
942    ///
943    /// Elements will be copied to the inline buffer if `vec.capacity() <=
944    /// Self::inline_capacity()`.
945    ///
946    /// ```rust
947    /// use smallvec::SmallVec;
948    ///
949    /// let vec = vec![1, 2, 3, 4, 5];
950    /// let small_vec: SmallVec<[_; 3]> = SmallVec::from_vec(vec);
951    ///
952    /// assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
953    /// ```
954    #[inline]
955    pub fn from_vec(mut vec: Vec<A::Item>) -> SmallVec<A> {
956        if vec.capacity() <= Self::inline_capacity() {
957            // Cannot use Vec with smaller capacity
958            // because we use value of `Self::capacity` field as indicator.
959            unsafe {
960                let mut data = SmallVecData::<A>::empty();
961                let len = vec.len();
962                vec.set_len(0);
963                ptr::copy_nonoverlapping(vec.as_ptr(), data.inline_mut().as_ptr(), len);
964
965                SmallVec {
966                    capacity: len,
967                    data,
968                    _marker: PhantomData
969                }
970            }
971        } else {
972            let (ptr, cap, len) = (vec.as_mut_ptr(), vec.capacity(), vec.len());
973            mem::forget(vec);
974            let ptr = NonNull::new(ptr)
975                // See docs: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_mut_ptr
976                .expect("Cannot be null by `Vec` invariant");
977
978            SmallVec {
979                capacity: cap,
980                data: SmallVecData::from_heap(ptr, len),
981                _marker: PhantomData
982            }
983        }
984    }
985
986    /// Constructs a new `SmallVec` on the stack from an `A` without
987    /// copying elements.
988    ///
989    /// ```rust
990    /// use smallvec::SmallVec;
991    ///
992    /// let buf = [1, 2, 3, 4, 5];
993    /// let small_vec: SmallVec<_> = SmallVec::from_buf(buf);
994    ///
995    /// assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
996    /// ```
997    #[inline]
998    pub fn from_buf(buf: A) -> SmallVec<A> {
999        SmallVec {
1000            capacity: A::size(),
1001            data: SmallVecData::from_inline(MaybeUninit::new(buf)),
1002            _marker: PhantomData
1003        }
1004    }
1005
1006    /// Constructs a new `SmallVec` on the stack from an `A` without
1007    /// copying elements. Also sets the length, which must be less or
1008    /// equal to the size of `buf`.
1009    ///
1010    /// ```rust
1011    /// use smallvec::SmallVec;
1012    ///
1013    /// let buf = [1, 2, 3, 4, 5, 0, 0, 0];
1014    /// let small_vec: SmallVec<_> = SmallVec::from_buf_and_len(buf, 5);
1015    ///
1016    /// assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
1017    /// ```
1018    #[inline]
1019    pub fn from_buf_and_len(buf: A, len: usize) -> SmallVec<A> {
1020        assert!(len <= A::size());
1021        unsafe { SmallVec::from_buf_and_len_unchecked(MaybeUninit::new(buf), len) }
1022    }
1023
1024    /// Constructs a new `SmallVec` on the stack from an `A` without
1025    /// copying elements. Also sets the length. The user is responsible
1026    /// for ensuring that `len <= A::size()`.
1027    ///
1028    /// ```rust
1029    /// use {
1030    ///     smallvec::SmallVec,
1031    ///     std::mem::MaybeUninit
1032    /// };
1033    ///
1034    /// let buf = [1, 2, 3, 4, 5, 0, 0, 0];
1035    /// let small_vec: SmallVec<_> =
1036    ///     unsafe { SmallVec::from_buf_and_len_unchecked(MaybeUninit::new(buf), 5) };
1037    ///
1038    /// assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
1039    /// ```
1040    #[inline]
1041    pub unsafe fn from_buf_and_len_unchecked(buf: MaybeUninit<A>, len: usize) -> SmallVec<A> {
1042        SmallVec {
1043            capacity: len,
1044            data: SmallVecData::from_inline(buf),
1045            _marker: PhantomData
1046        }
1047    }
1048
1049    /// Sets the length of a vector.
1050    ///
1051    /// This will explicitly set the size of the vector, without actually
1052    /// modifying its buffers, so it is up to the caller to ensure that the
1053    /// vector is actually the specified size.
1054    pub unsafe fn set_len(&mut self, new_len: usize) {
1055        let (_, len_ptr, _) = self.triple_mut();
1056        *len_ptr = new_len;
1057    }
1058
1059    /// The maximum number of elements this vector can hold inline
1060    #[inline]
1061    fn inline_capacity() -> usize {
1062        if mem::size_of::<A::Item>() > 0 {
1063            A::size()
1064        } else {
1065            // For zero-size items code like `ptr.add(offset)` always returns
1066            // the same pointer. Therefore all items are at the same
1067            // address, and any array size has capacity for
1068            // infinitely many items. The capacity is limited by the
1069            // bit width of the length field.
1070            //
1071            // `Vec` also does this:
1072            // https://github.com/rust-lang/rust/blob/1.44.0/src/liballoc/raw_vec.rs#L186
1073            //
1074            // In our case, this also ensures that a smallvec of zero-size items
1075            // never spills, and we never try to allocate zero bytes
1076            // which `std::alloc::alloc` disallows.
1077            #[allow(deprecated)]
1078            core::usize::MAX
1079        }
1080    }
1081
1082    /// The maximum number of elements this vector can hold inline
1083    #[inline]
1084    pub fn inline_size(&self) -> usize { Self::inline_capacity() }
1085
1086    /// The number of elements stored in the vector
1087    #[inline]
1088    pub fn len(&self) -> usize { self.triple().1 }
1089
1090    /// Returns `true` if the vector is empty
1091    #[inline]
1092    pub fn is_empty(&self) -> bool { self.len() == 0 }
1093
1094    /// The number of items the vector can hold without reallocating
1095    #[inline]
1096    pub fn capacity(&self) -> usize { self.triple().2 }
1097
1098    /// Returns a tuple with (data ptr, len, capacity)
1099    /// Useful to get all `SmallVec` properties with a single check of the
1100    /// current storage variant.
1101    #[inline]
1102    fn triple(&self) -> (ConstNonNull<A::Item>, usize, usize) {
1103        unsafe {
1104            if self.spilled() {
1105                let (ptr, len) = self.data.heap();
1106                (ptr, len, self.capacity)
1107            } else {
1108                (self.data.inline(), self.capacity, Self::inline_capacity())
1109            }
1110        }
1111    }
1112
1113    /// Returns a tuple with (data ptr, len ptr, capacity)
1114    #[inline]
1115    fn triple_mut(&mut self) -> (NonNull<A::Item>, &mut usize, usize) {
1116        unsafe {
1117            if self.spilled() {
1118                let (ptr, len_ptr) = self.data.heap_mut();
1119                (ptr, len_ptr, self.capacity)
1120            } else {
1121                (
1122                    self.data.inline_mut(),
1123                    &mut self.capacity,
1124                    Self::inline_capacity()
1125                )
1126            }
1127        }
1128    }
1129
1130    /// Returns `true` if the data has spilled into a separate heap-allocated
1131    /// buffer.
1132    #[inline]
1133    pub fn spilled(&self) -> bool { self.capacity > Self::inline_capacity() }
1134
1135    /// Creates a draining iterator that removes the specified range in the
1136    /// vector and yields the removed items.
1137    ///
1138    /// Note 1: The element range is removed even if the iterator is only
1139    /// partially consumed or not consumed at all.
1140    ///
1141    /// Note 2: It is unspecified how many elements are removed from the vector
1142    /// if the `Drain` value is leaked.
1143    ///
1144    /// # Panics
1145    ///
1146    /// Panics if the starting point is greater than the end point or if
1147    /// the end point is greater than the length of the vector.
1148    pub fn drain<R>(&mut self, range: R) -> Drain<'_, A>
1149    where R: RangeBounds<usize> {
1150        use core::ops::Bound::*;
1151
1152        let len = self.len();
1153        let start = match range.start_bound() {
1154            Included(&n) => n,
1155            Excluded(&n) => n.checked_add(1).expect("Range start out of bounds"),
1156            Unbounded => 0
1157        };
1158        let end = match range.end_bound() {
1159            Included(&n) => n.checked_add(1).expect("Range end out of bounds"),
1160            Excluded(&n) => n,
1161            Unbounded => len
1162        };
1163
1164        assert!(start <= end);
1165        assert!(end <= len);
1166
1167        unsafe {
1168            self.set_len(start);
1169
1170            let range_slice = slice::from_raw_parts(self.as_ptr().add(start), end - start);
1171
1172            Drain {
1173                tail_start: end,
1174                tail_len: len - end,
1175                iter: range_slice.iter(),
1176                // Since self is a &mut, passing it to a function would
1177                // invalidate the slice iterator.
1178                vec: NonNull::new_unchecked(self as *mut _)
1179            }
1180        }
1181    }
1182
1183    #[cfg(feature = "drain_filter")]
1184    /// Creates an iterator which uses a closure to determine if an element
1185    /// should be removed.
1186    ///
1187    /// If the closure returns true, the element is removed and yielded. If the
1188    /// closure returns false, the element will remain in the vector and
1189    /// will not be yielded by the iterator.
1190    ///
1191    /// Using this method is equivalent to the following code:
1192    /// ```
1193    /// # use smallvec::SmallVec;
1194    /// # let some_predicate = |x: &mut i32| { *x == 2 || *x == 3 || *x == 6 };
1195    /// # let mut vec: SmallVec<[i32; 8]> = SmallVec::from_slice(&[1i32, 2, 3, 4, 5, 6]);
1196    /// let mut i = 0;
1197    /// while i < vec.len() {
1198    ///     if some_predicate(&mut vec[i]) {
1199    ///         let val = vec.remove(i);
1200    ///         // your code here
1201    ///     } else {
1202    ///         i += 1;
1203    ///     }
1204    /// }
1205    ///
1206    /// # assert_eq!(vec, SmallVec::<[i32; 8]>::from_slice(&[1i32, 4, 5]));
1207    /// ```
1208    /// ///
1209    /// But `drain_filter` is easier to use. `drain_filter` is also more
1210    /// efficient, because it can backshift the elements of the array in
1211    /// bulk.
1212    ///
1213    /// Note that `drain_filter` also lets you mutate every element in the
1214    /// filter closure, regardless of whether you choose to keep or remove
1215    /// it.
1216    ///
1217    /// # Examples
1218    ///
1219    /// Splitting an array into evens and odds, reusing the original allocation:
1220    ///
1221    /// ```
1222    /// # use smallvec::SmallVec;
1223    /// let mut numbers: SmallVec<[i32; 16]> =
1224    ///     SmallVec::from_slice(&[1i32, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
1225    ///
1226    /// let evens = numbers
1227    ///     .drain_filter(|x| *x % 2 == 0)
1228    ///     .collect::<SmallVec<[i32; 16]>>();
1229    /// let odds = numbers;
1230    ///
1231    /// assert_eq!(
1232    ///     evens,
1233    ///     SmallVec::<[i32; 16]>::from_slice(&[2i32, 4, 6, 8, 14])
1234    /// );
1235    /// assert_eq!(
1236    ///     odds,
1237    ///     SmallVec::<[i32; 16]>::from_slice(&[1i32, 3, 5, 9, 11, 13, 15])
1238    /// );
1239    /// ```
1240    pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, A, F>
1241    where F: FnMut(&mut A::Item) -> bool {
1242        let old_len = self.len();
1243
1244        // Guard against us getting leaked (leak amplification)
1245        unsafe {
1246            self.set_len(0);
1247        }
1248
1249        DrainFilter {
1250            vec: self,
1251            idx: 0,
1252            del: 0,
1253            old_len,
1254            pred: filter,
1255            panic_flag: false
1256        }
1257    }
1258
1259    /// Append an item to the vector.
1260    #[inline]
1261    pub fn push(&mut self, value: A::Item) {
1262        unsafe {
1263            if self.spilled() {
1264                let (mut ptr, mut len_ptr) = self.data.heap_mut();
1265                if *len_ptr == self.capacity {
1266                    self.reserve_one_unchecked();
1267                    let (heap_ptr, heap_len) = self.data.heap_mut();
1268                    ptr = heap_ptr;
1269                    len_ptr = heap_len;
1270                }
1271                ptr::write(ptr.as_ptr().add(*len_ptr), value);
1272                *len_ptr += 1;
1273            } else {
1274                let mut ptr = self.data.inline_mut();
1275                let mut len_ptr = &mut self.capacity;
1276                if *len_ptr == Self::inline_capacity() {
1277                    self.reserve_one_unchecked();
1278                    let (heap_ptr, heap_len) = self.data.heap_mut();
1279                    ptr = heap_ptr;
1280                    len_ptr = heap_len;
1281                }
1282                ptr::write(ptr.as_ptr().add(*len_ptr), value);
1283                *len_ptr += 1;
1284            };
1285        }
1286    }
1287
1288    /// Remove an item from the end of the vector and return it, or None if
1289    /// empty.
1290    #[inline]
1291    pub fn pop(&mut self) -> Option<A::Item> {
1292        unsafe {
1293            let (ptr, len_ptr, _) = self.triple_mut();
1294            let ptr: *const _ = ptr.as_ptr();
1295            if *len_ptr == 0 {
1296                return None;
1297            }
1298            let last_index = *len_ptr - 1;
1299            *len_ptr = last_index;
1300            Some(ptr::read(ptr.add(last_index)))
1301        }
1302    }
1303
1304    /// Moves all the elements of `other` into `self`, leaving `other` empty.
1305    ///
1306    /// # Example
1307    ///
1308    /// ```
1309    /// # use smallvec::{SmallVec, smallvec};
1310    /// let mut v0: SmallVec<[u8; 16]> = smallvec![1, 2, 3];
1311    /// let mut v1: SmallVec<[u8; 32]> = smallvec![4, 5, 6];
1312    /// v0.append(&mut v1);
1313    /// assert_eq!(*v0, [1, 2, 3, 4, 5, 6]);
1314    /// assert_eq!(*v1, []);
1315    /// ```
1316    pub fn append<B>(&mut self, other: &mut SmallVec<B>)
1317    where B: Array<Item = A::Item> {
1318        self.extend(other.drain(..))
1319    }
1320
1321    /// Re-allocate to set the capacity to `max(new_cap, inline_size())`.
1322    ///
1323    /// If `new_cap` is less than the vector's length, this is a no-op.
1324    /// Panics if the capacity computation overflows `usize`.
1325    pub fn grow(&mut self, new_cap: usize) { infallible(self.try_grow(new_cap)) }
1326
1327    /// Re-allocate to set the capacity to `max(new_cap, inline_size())`.
1328    ///
1329    /// If `new_cap` is less than the vector's length, this is a no-op.
1330    pub fn try_grow(&mut self, new_cap: usize) -> Result<(), CollectionAllocErr> {
1331        unsafe {
1332            let unspilled = !self.spilled();
1333            let (ptr, &mut len, cap) = self.triple_mut();
1334            if new_cap < len {
1335                return Ok(());
1336            }
1337            if new_cap <= Self::inline_capacity() {
1338                if unspilled {
1339                    return Ok(());
1340                }
1341                self.data = SmallVecData::empty();
1342                ptr::copy_nonoverlapping(ptr.as_ptr(), self.data.inline_mut().as_ptr(), len);
1343                self.capacity = len;
1344                deallocate(ptr, cap);
1345            } else if new_cap != cap {
1346                let layout = layout_array::<A::Item>(new_cap)?;
1347                debug_assert!(layout.size() > 0);
1348                let new_alloc;
1349                if unspilled {
1350                    new_alloc = NonNull::new(alloc::alloc::alloc(layout))
1351                        .ok_or(CollectionAllocErr::AllocErr {
1352                            layout
1353                        })?
1354                        .cast();
1355                    ptr::copy_nonoverlapping(ptr.as_ptr(), new_alloc.as_ptr(), len);
1356                } else {
1357                    // This should never fail since the same succeeded
1358                    // when previously allocating `ptr`.
1359                    let old_layout = layout_array::<A::Item>(cap)?;
1360
1361                    let new_ptr =
1362                        alloc::alloc::realloc(ptr.as_ptr() as *mut u8, old_layout, layout.size());
1363                    new_alloc = NonNull::new(new_ptr)
1364                        .ok_or(CollectionAllocErr::AllocErr {
1365                            layout
1366                        })?
1367                        .cast();
1368                }
1369                self.data = SmallVecData::from_heap(new_alloc, len);
1370                self.capacity = new_cap;
1371            }
1372            Ok(())
1373        }
1374    }
1375
1376    /// Reserve capacity for `additional` more elements to be inserted.
1377    ///
1378    /// May reserve more space to avoid frequent reallocations.
1379    ///
1380    /// Panics if the capacity computation overflows `usize`.
1381    #[inline]
1382    pub fn reserve(&mut self, additional: usize) { infallible(self.try_reserve(additional)) }
1383
1384    /// Internal method used to grow in push() and insert(), where we know
1385    /// already we have to grow.
1386    #[cold]
1387    fn reserve_one_unchecked(&mut self) {
1388        debug_assert_eq!(self.len(), self.capacity());
1389        let new_cap = self
1390            .len()
1391            .checked_add(1)
1392            .and_then(usize::checked_next_power_of_two)
1393            .expect("capacity overflow");
1394        infallible(self.try_grow(new_cap))
1395    }
1396
1397    /// Reserve capacity for `additional` more elements to be inserted.
1398    ///
1399    /// May reserve more space to avoid frequent reallocations.
1400    pub fn try_reserve(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {
1401        // prefer triple_mut() even if triple() would work so that the optimizer
1402        // removes duplicated calls to it from callers.
1403        let (_, &mut len, cap) = self.triple_mut();
1404        if cap - len >= additional {
1405            return Ok(());
1406        }
1407        let new_cap = len
1408            .checked_add(additional)
1409            .and_then(usize::checked_next_power_of_two)
1410            .ok_or(CollectionAllocErr::CapacityOverflow)?;
1411        self.try_grow(new_cap)
1412    }
1413
1414    /// Reserve the minimum capacity for `additional` more elements to be
1415    /// inserted.
1416    ///
1417    /// Panics if the new capacity overflows `usize`.
1418    pub fn reserve_exact(&mut self, additional: usize) {
1419        infallible(self.try_reserve_exact(additional))
1420    }
1421
1422    /// Reserve the minimum capacity for `additional` more elements to be
1423    /// inserted.
1424    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {
1425        let (_, &mut len, cap) = self.triple_mut();
1426        if cap - len >= additional {
1427            return Ok(());
1428        }
1429        let new_cap = len
1430            .checked_add(additional)
1431            .ok_or(CollectionAllocErr::CapacityOverflow)?;
1432        self.try_grow(new_cap)
1433    }
1434
1435    /// Shrink the capacity of the vector as much as possible.
1436    ///
1437    /// When possible, this will move data from an external heap buffer to the
1438    /// vector's inline storage.
1439    pub fn shrink_to_fit(&mut self) {
1440        if !self.spilled() {
1441            return;
1442        }
1443        let len = self.len();
1444        if self.inline_size() >= len {
1445            unsafe {
1446                let (ptr, len) = self.data.heap();
1447                self.data = SmallVecData::empty();
1448                ptr::copy_nonoverlapping(ptr.as_ptr(), self.data.inline_mut().as_ptr(), len);
1449                deallocate(ptr.0, self.capacity);
1450                self.capacity = len;
1451            }
1452        } else if self.capacity() > len {
1453            self.grow(len);
1454        }
1455    }
1456
1457    /// Shorten the vector, keeping the first `len` elements and dropping the
1458    /// rest.
1459    ///
1460    /// If `len` is greater than or equal to the vector's current length, this
1461    /// has no effect.
1462    ///
1463    /// This does not re-allocate.  If you want the vector's capacity to shrink,
1464    /// call `shrink_to_fit` after truncating.
1465    pub fn truncate(&mut self, len: usize) {
1466        unsafe {
1467            let (ptr, len_ptr, _) = self.triple_mut();
1468            let ptr = ptr.as_ptr();
1469            while len < *len_ptr {
1470                let last_index = *len_ptr - 1;
1471                *len_ptr = last_index;
1472                ptr::drop_in_place(ptr.add(last_index));
1473            }
1474        }
1475    }
1476
1477    /// Extracts a slice containing the entire vector.
1478    ///
1479    /// Equivalent to `&s[..]`.
1480    pub fn as_slice(&self) -> &[A::Item] { self }
1481
1482    /// Extracts a mutable slice of the entire vector.
1483    ///
1484    /// Equivalent to `&mut s[..]`.
1485    pub fn as_mut_slice(&mut self) -> &mut [A::Item] { self }
1486
1487    /// Remove the element at position `index`, replacing it with the last
1488    /// element.
1489    ///
1490    /// This does not preserve ordering, but is O(1).
1491    ///
1492    /// Panics if `index` is out of bounds.
1493    #[inline]
1494    pub fn swap_remove(&mut self, index: usize) -> A::Item {
1495        let len = self.len();
1496        self.swap(len - 1, index);
1497        self.pop()
1498            .unwrap_or_else(|| unsafe { unreachable_unchecked() })
1499    }
1500
1501    /// Remove all elements from the vector.
1502    #[inline]
1503    pub fn clear(&mut self) { self.truncate(0); }
1504
1505    /// Remove and return the element at position `index`, shifting all elements
1506    /// after it to the left.
1507    ///
1508    /// Panics if `index` is out of bounds.
1509    pub fn remove(&mut self, index: usize) -> A::Item {
1510        unsafe {
1511            let (ptr, len_ptr, _) = self.triple_mut();
1512            let len = *len_ptr;
1513            assert!(index < len);
1514            *len_ptr = len - 1;
1515            let ptr = ptr.as_ptr().add(index);
1516            let item = ptr::read(ptr);
1517            ptr::copy(ptr.add(1), ptr, len - index - 1);
1518            item
1519        }
1520    }
1521
1522    /// Insert an element at position `index`, shifting all elements after it to
1523    /// the right.
1524    ///
1525    /// Panics if `index > len`.
1526    pub fn insert(&mut self, index: usize, element: A::Item) {
1527        unsafe {
1528            let (mut ptr, mut len_ptr, cap) = self.triple_mut();
1529            if *len_ptr == cap {
1530                self.reserve_one_unchecked();
1531                let (heap_ptr, heap_len_ptr) = self.data.heap_mut();
1532                ptr = heap_ptr;
1533                len_ptr = heap_len_ptr;
1534            }
1535            let mut ptr = ptr.as_ptr();
1536            let len = *len_ptr;
1537            if index > len {
1538                panic!("index exceeds length");
1539            }
1540            // SAFETY: add is UB if index > len, but we panicked first
1541            ptr = ptr.add(index);
1542            if index < len {
1543                // Shift element to the right of `index`.
1544                ptr::copy(ptr, ptr.add(1), len - index);
1545            }
1546            *len_ptr = len + 1;
1547            ptr::write(ptr, element);
1548        }
1549    }
1550
1551    /// Insert multiple elements at position `index`, shifting all following
1552    /// elements toward the back.
1553    pub fn insert_many<I: IntoIterator<Item = A::Item>>(&mut self, index: usize, iterable: I) {
1554        let mut iter = iterable.into_iter();
1555        if index == self.len() {
1556            return self.extend(iter);
1557        }
1558
1559        let (lower_size_bound, _) = iter.size_hint();
1560        #[allow(deprecated)]
1561        {
1562            assert!(lower_size_bound <= core::isize::MAX as usize)
1563        } // Ensure offset is indexable
1564        assert!(index + lower_size_bound >= index); // Protect against overflow
1565
1566        let mut num_added = 0;
1567        let old_len = self.len();
1568        assert!(index <= old_len);
1569
1570        unsafe {
1571            // Reserve space for `lower_size_bound` elements.
1572            self.reserve(lower_size_bound);
1573            let start = self.as_mut_ptr();
1574            let ptr = start.add(index);
1575
1576            // Move the trailing elements.
1577            ptr::copy(ptr, ptr.add(lower_size_bound), old_len - index);
1578
1579            // In case the iterator panics, don't double-drop the items we just
1580            // copied above.
1581            self.set_len(0);
1582            let mut guard = DropOnPanic {
1583                start,
1584                skip: index..(index + lower_size_bound),
1585                len: old_len + lower_size_bound
1586            };
1587
1588            // The set_len above invalidates the previous pointers, so we must
1589            // re-create them.
1590            let start = self.as_mut_ptr();
1591            let ptr = start.add(index);
1592
1593            while num_added < lower_size_bound {
1594                let element = match iter.next() {
1595                    Some(x) => x,
1596                    None => break
1597                };
1598                let cur = ptr.add(num_added);
1599                ptr::write(cur, element);
1600                guard.skip.start += 1;
1601                num_added += 1;
1602            }
1603
1604            if num_added < lower_size_bound {
1605                // Iterator provided fewer elements than the hint. Move the tail
1606                // backward.
1607                ptr::copy(
1608                    ptr.add(lower_size_bound),
1609                    ptr.add(num_added),
1610                    old_len - index
1611                );
1612            }
1613            // There are no more duplicate or uninitialized slots, so the guard
1614            // is not needed.
1615            self.set_len(old_len + num_added);
1616            mem::forget(guard);
1617        }
1618
1619        // Insert any remaining elements one-by-one.
1620        for element in iter {
1621            self.insert(index + num_added, element);
1622            num_added += 1;
1623        }
1624
1625        struct DropOnPanic<T> {
1626            start: *mut T,
1627            skip: Range<usize>, // Space we copied-out-of, but haven't written-to yet.
1628            len: usize
1629        }
1630
1631        impl<T> Drop for DropOnPanic<T> {
1632            fn drop(&mut self) {
1633                for i in 0..self.len {
1634                    if !self.skip.contains(&i) {
1635                        unsafe {
1636                            ptr::drop_in_place(self.start.add(i));
1637                        }
1638                    }
1639                }
1640            }
1641        }
1642    }
1643
1644    /// Convert a `SmallVec` to a `Vec`, without reallocating if the `SmallVec`
1645    /// has already spilled onto the heap.
1646    pub fn into_vec(mut self) -> Vec<A::Item> {
1647        if self.spilled() {
1648            unsafe {
1649                let (ptr, &mut len) = self.data.heap_mut();
1650                let v = Vec::from_raw_parts(ptr.as_ptr(), len, self.capacity);
1651                mem::forget(self);
1652                v
1653            }
1654        } else {
1655            self.into_iter().collect()
1656        }
1657    }
1658
1659    /// Converts a `SmallVec` into a `Box<[T]>` without reallocating if the
1660    /// `SmallVec` has already spilled onto the heap.
1661    ///
1662    /// Note that this will drop any excess capacity.
1663    pub fn into_boxed_slice(self) -> Box<[A::Item]> { self.into_vec().into_boxed_slice() }
1664
1665    /// Convert the `SmallVec` into an `A` if possible. Otherwise return
1666    /// `Err(Self)`.
1667    ///
1668    /// This method returns `Err(Self)` if the `SmallVec` is too short (and the
1669    /// `A` contains uninitialized elements), or if the `SmallVec` is too
1670    /// long (and all the elements were spilled to the heap).
1671    pub fn into_inner(self) -> Result<A, Self> {
1672        if self.spilled() || self.len() != A::size() {
1673            // Note: A::size, not Self::inline_capacity
1674            Err(self)
1675        } else {
1676            unsafe {
1677                let data = ptr::read(&self.data);
1678                mem::forget(self);
1679                Ok(data.into_inline().assume_init())
1680            }
1681        }
1682    }
1683
1684    /// Retains only the elements specified by the predicate.
1685    ///
1686    /// In other words, remove all elements `e` such that `f(&e)` returns
1687    /// `false`. This method operates in place and preserves the order of
1688    /// the retained elements.
1689    pub fn retain<F: FnMut(&mut A::Item) -> bool>(&mut self, mut f: F) {
1690        let original_len = self.len();
1691
1692        if original_len == 0 {
1693            // Empty case: explicit return allows better optimization, vs
1694            // letting compiler infer it
1695            return;
1696        }
1697
1698        // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked]
1699        //      |            ^- write                ^- read             |
1700        //      |<-              original_len                          ->|
1701        // Kept: Elements which predicate returns true on.
1702        // Hole: Moved or dropped element slot.
1703        // Unchecked: Unchecked valid elements.
1704        //
1705        // This drop guard will be invoked when predicate or `drop` of element
1706        // panicked. It shifts unchecked elements to cover holes and
1707        // `set_len` to the correct length. In cases when predicate and
1708        // `drop` never panic, it will be optimized out.
1709        struct PanicGuard<'a, A: Array> {
1710            v: &'a mut SmallVec<A>,
1711            read: usize,
1712            write: usize,
1713            original_len: usize
1714        }
1715
1716        impl<A: Array> Drop for PanicGuard<'_, A> {
1717            #[cold]
1718            fn drop(&mut self) {
1719                let remaining = self.original_len - self.read;
1720                // SAFETY: Trailing unchecked items must be valid since we never
1721                // touch them.
1722                unsafe {
1723                    let ptr = self.v.as_mut_ptr();
1724                    ptr::copy(ptr.add(self.read), ptr.add(self.write), remaining);
1725                }
1726                // SAFETY: After filling holes, all items are in contiguous
1727                // memory.
1728                unsafe {
1729                    self.v.set_len(self.write + remaining);
1730                }
1731            }
1732        }
1733
1734        let mut read = 0;
1735        loop {
1736            // SAFETY: read < original_len
1737            let cur = unsafe { self.get_unchecked_mut(read) };
1738            if !f(cur) {
1739                break;
1740            }
1741            read += 1;
1742            if read == original_len {
1743                // All elements are kept, return early.
1744                return;
1745            }
1746        }
1747
1748        // Critical section starts here and at least one element is going to be
1749        // removed. Advance `g.read` early to avoid double drop if
1750        // `drop_in_place` panicked.
1751        let mut g = PanicGuard {
1752            v: self,
1753            read: read + 1,
1754            write: read,
1755            original_len
1756        };
1757        // SAFETY: previous `read` is always less than original_len.
1758        unsafe { ptr::drop_in_place(g.v.as_mut_ptr().add(read)) }
1759
1760        let ptr = g.v.as_mut_ptr();
1761        while g.read < g.original_len {
1762            // SAFETY: `read` is always less than original_len.
1763            let cur = unsafe { &mut *ptr.add(g.read) };
1764            if !f(cur) {
1765                // Advance `read` early to avoid double drop if `drop_in_place`
1766                // panicked.
1767                g.read += 1;
1768                // SAFETY: We never touch this element again after dropped.
1769                unsafe { ptr::drop_in_place(cur) };
1770            } else {
1771                // SAFETY: `read` > `write`, so the slots don't overlap.
1772                // We use copy for move, and never touch the source element
1773                // again.
1774                unsafe {
1775                    let hole = ptr.add(g.write);
1776                    ptr::copy_nonoverlapping(cur, hole, 1);
1777                }
1778                g.write += 1;
1779                g.read += 1;
1780            }
1781        }
1782
1783        // We are leaving the critical section and no panic happened,
1784        // Commit the length change and forget the guard.
1785        // SAFETY: `write` is always less than or equal to original_len.
1786        unsafe { g.v.set_len(g.write) };
1787        core::mem::forget(g);
1788    }
1789
1790    /// Retains only the elements specified by the predicate.
1791    ///
1792    /// This method is identical in behaviour to [`SmallVec::retain`]; it is
1793    /// included only to maintain api-compatibility with `std::Vec`, where
1794    /// the methods are separate for historical reasons.
1795    pub fn retain_mut<F: FnMut(&mut A::Item) -> bool>(&mut self, f: F) { self.retain(f) }
1796
1797    /// Removes consecutive duplicate elements.
1798    pub fn dedup(&mut self)
1799    where A::Item: PartialEq<A::Item> {
1800        self.dedup_by(|a, b| a == b);
1801    }
1802
1803    /// Removes consecutive duplicate elements using the given equality
1804    /// relation.
1805    pub fn dedup_by<F>(&mut self, mut same_bucket: F)
1806    where F: FnMut(&mut A::Item, &mut A::Item) -> bool {
1807        // See the implementation of Vec::dedup_by in the
1808        // standard library for an explanation of this algorithm.
1809        let len = self.len();
1810        if len <= 1 {
1811            return;
1812        }
1813
1814        let ptr = self.as_mut_ptr();
1815        let mut w: usize = 1;
1816
1817        unsafe {
1818            for r in 1..len {
1819                let p_r = ptr.add(r);
1820                let p_wm1 = ptr.add(w - 1);
1821                if !same_bucket(&mut *p_r, &mut *p_wm1) {
1822                    if r != w {
1823                        let p_w = p_wm1.add(1);
1824                        mem::swap(&mut *p_r, &mut *p_w);
1825                    }
1826                    w += 1;
1827                }
1828            }
1829        }
1830
1831        self.truncate(w);
1832    }
1833
1834    /// Removes consecutive elements that map to the same key.
1835    pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1836    where
1837        F: FnMut(&mut A::Item) -> K,
1838        K: PartialEq<K>
1839    {
1840        self.dedup_by(|a, b| key(a) == key(b));
1841    }
1842
1843    /// Resizes the `SmallVec` in-place so that `len` is equal to `new_len`.
1844    ///
1845    /// If `new_len` is greater than `len`, the `SmallVec` is extended by the
1846    /// difference, with each additional slot filled with the result of
1847    /// calling the closure `f`. The return values from `f` will end up in
1848    /// the `SmallVec` in the order they have been generated.
1849    ///
1850    /// If `new_len` is less than `len`, the `SmallVec` is simply truncated.
1851    ///
1852    /// This method uses a closure to create new values on every push. If you'd
1853    /// rather `Clone` a given value, use `resize`. If you want to use the
1854    /// `Default` trait to generate values, you can pass
1855    /// `Default::default()` as the second argument.
1856    ///
1857    /// Added for `std::vec::Vec` compatibility (added in Rust 1.33.0)
1858    ///
1859    /// ```
1860    /// # use smallvec::{smallvec, SmallVec};
1861    /// let mut vec: SmallVec<[_; 4]> = smallvec![1, 2, 3];
1862    /// vec.resize_with(5, Default::default);
1863    /// assert_eq!(&*vec, &[1, 2, 3, 0, 0]);
1864    ///
1865    /// let mut vec: SmallVec<[_; 4]> = smallvec![];
1866    /// let mut p = 1;
1867    /// vec.resize_with(4, || {
1868    ///     p *= 2;
1869    ///     p
1870    /// });
1871    /// assert_eq!(&*vec, &[2, 4, 8, 16]);
1872    /// ```
1873    pub fn resize_with<F>(&mut self, new_len: usize, f: F)
1874    where F: FnMut() -> A::Item {
1875        let old_len = self.len();
1876        if old_len < new_len {
1877            let mut f = f;
1878            let additional = new_len - old_len;
1879            self.reserve(additional);
1880            for _ in 0..additional {
1881                self.push(f());
1882            }
1883        } else if old_len > new_len {
1884            self.truncate(new_len);
1885        }
1886    }
1887
1888    /// Creates a `SmallVec` directly from the raw components of another
1889    /// `SmallVec`.
1890    ///
1891    /// # Safety
1892    ///
1893    /// This is highly unsafe, due to the number of invariants that aren't
1894    /// checked:
1895    ///
1896    /// * `ptr` needs to have been previously allocated via `SmallVec` for its
1897    ///   spilled storage (at least, it's highly likely to be incorrect if it
1898    ///   wasn't).
1899    /// * `ptr`'s `A::Item` type needs to be the same size and alignment that it
1900    ///   was allocated with
1901    /// * `length` needs to be less than or equal to `capacity`.
1902    /// * `capacity` needs to be the capacity that the pointer was allocated
1903    ///   with.
1904    ///
1905    /// Violating these may cause problems like corrupting the allocator's
1906    /// internal data structures.
1907    ///
1908    /// Additionally, `capacity` must be greater than the amount of inline
1909    /// storage `A` has; that is, the new `SmallVec` must need to spill over
1910    /// into heap allocated storage. This condition is asserted against.
1911    ///
1912    /// The ownership of `ptr` is effectively transferred to the
1913    /// `SmallVec` which may then deallocate, reallocate or change the
1914    /// contents of memory pointed to by the pointer at will. Ensure
1915    /// that nothing else uses the pointer after calling this
1916    /// function.
1917    ///
1918    /// # Examples
1919    ///
1920    /// ```
1921    /// # use smallvec::{smallvec, SmallVec};
1922    /// use std::mem;
1923    /// use std::ptr;
1924    ///
1925    /// fn main() {
1926    ///     let mut v: SmallVec<[_; 1]> = smallvec![1, 2, 3];
1927    ///
1928    ///     // Pull out the important parts of `v`.
1929    ///     let p = v.as_mut_ptr();
1930    ///     let len = v.len();
1931    ///     let cap = v.capacity();
1932    ///     let spilled = v.spilled();
1933    ///
1934    ///     unsafe {
1935    ///         // Forget all about `v`. The heap allocation that stored the
1936    ///         // three values won't be deallocated.
1937    ///         mem::forget(v);
1938    ///
1939    ///         // Overwrite memory with [4, 5, 6].
1940    ///         //
1941    ///         // This is only safe if `spilled` is true! Otherwise, we are
1942    ///         // writing into the old `SmallVec`'s inline storage on the
1943    ///         // stack.
1944    ///         assert!(spilled);
1945    ///         for i in 0..len {
1946    ///             ptr::write(p.add(i), 4 + i);
1947    ///         }
1948    ///
1949    ///         // Put everything back together into a SmallVec with a different
1950    ///         // amount of inline storage, but which is still less than `cap`.
1951    ///         let rebuilt = SmallVec::<[_; 2]>::from_raw_parts(p, len, cap);
1952    ///         assert_eq!(&*rebuilt, &[4, 5, 6]);
1953    ///     }
1954    /// }
1955    #[inline]
1956    pub unsafe fn from_raw_parts(ptr: *mut A::Item, length: usize, capacity: usize) -> SmallVec<A> {
1957        // SAFETY: We require caller to provide same ptr as we alloc
1958        // and we never alloc null pointer.
1959        let ptr = unsafe {
1960            debug_assert!(!ptr.is_null(), "Called `from_raw_parts` with null pointer.");
1961            NonNull::new_unchecked(ptr)
1962        };
1963        assert!(capacity > Self::inline_capacity());
1964        SmallVec {
1965            capacity,
1966            data: SmallVecData::from_heap(ptr, length),
1967            _marker: PhantomData
1968        }
1969    }
1970
1971    /// Returns a raw pointer to the vector's buffer.
1972    pub fn as_ptr(&self) -> *const A::Item {
1973        // We shadow the slice method of the same name to avoid going through
1974        // `deref`, which creates an intermediate reference that may place
1975        // additional safety constraints on the contents of the slice.
1976        self.triple().0.as_ptr()
1977    }
1978
1979    /// Returns a raw mutable pointer to the vector's buffer.
1980    pub fn as_mut_ptr(&mut self) -> *mut A::Item {
1981        // We shadow the slice method of the same name to avoid going through
1982        // `deref_mut`, which creates an intermediate reference that may place
1983        // additional safety constraints on the contents of the slice.
1984        self.triple_mut().0.as_ptr()
1985    }
1986}
1987
1988impl<A: Array> SmallVec<A>
1989where A::Item: Copy
1990{
1991    /// Copy the elements from a slice into a new `SmallVec`.
1992    ///
1993    /// For slices of `Copy` types, this is more efficient than
1994    /// `SmallVec::from(slice)`.
1995    pub fn from_slice(slice: &[A::Item]) -> Self {
1996        let len = slice.len();
1997        if len <= Self::inline_capacity() {
1998            SmallVec {
1999                capacity: len,
2000                data: SmallVecData::from_inline(unsafe {
2001                    let mut data: MaybeUninit<A> = MaybeUninit::uninit();
2002                    ptr::copy_nonoverlapping(
2003                        slice.as_ptr(),
2004                        data.as_mut_ptr() as *mut A::Item,
2005                        len
2006                    );
2007                    data
2008                }),
2009                _marker: PhantomData
2010            }
2011        } else {
2012            let mut b = slice.to_vec();
2013            let cap = b.capacity();
2014            let ptr = NonNull::new(b.as_mut_ptr()).expect("Vec always contain non null pointers.");
2015            mem::forget(b);
2016            SmallVec {
2017                capacity: cap,
2018                data: SmallVecData::from_heap(ptr, len),
2019                _marker: PhantomData
2020            }
2021        }
2022    }
2023
2024    /// Copy elements from a slice into the vector at position `index`, shifting
2025    /// any following elements toward the back.
2026    ///
2027    /// For slices of `Copy` types, this is more efficient than `insert`.
2028    #[inline]
2029    pub fn insert_from_slice(&mut self, index: usize, slice: &[A::Item]) {
2030        self.reserve(slice.len());
2031
2032        let len = self.len();
2033        assert!(index <= len);
2034
2035        unsafe {
2036            let slice_ptr = slice.as_ptr();
2037            let ptr = self.as_mut_ptr().add(index);
2038            ptr::copy(ptr, ptr.add(slice.len()), len - index);
2039            ptr::copy_nonoverlapping(slice_ptr, ptr, slice.len());
2040            self.set_len(len + slice.len());
2041        }
2042    }
2043
2044    /// Copy elements from a slice and append them to the vector.
2045    ///
2046    /// For slices of `Copy` types, this is more efficient than `extend`.
2047    #[inline]
2048    pub fn extend_from_slice(&mut self, slice: &[A::Item]) {
2049        let len = self.len();
2050        self.insert_from_slice(len, slice);
2051    }
2052}
2053
2054impl<A: Array> SmallVec<A>
2055where A::Item: Clone
2056{
2057    /// Resizes the vector so that its length is equal to `len`.
2058    ///
2059    /// If `len` is less than the current length, the vector simply truncated.
2060    ///
2061    /// If `len` is greater than the current length, `value` is appended to the
2062    /// vector until its length equals `len`.
2063    pub fn resize(&mut self, len: usize, value: A::Item) {
2064        let old_len = self.len();
2065
2066        if len > old_len {
2067            self.extend(repeat(value).take(len - old_len));
2068        } else {
2069            self.truncate(len);
2070        }
2071    }
2072
2073    /// Creates a `SmallVec` with `n` copies of `elem`.
2074    /// ```
2075    /// use smallvec::SmallVec;
2076    ///
2077    /// let v = SmallVec::<[char; 128]>::from_elem('d', 2);
2078    /// assert_eq!(v, SmallVec::from_buf(['d', 'd']));
2079    /// ```
2080    pub fn from_elem(elem: A::Item, n: usize) -> Self {
2081        if n > Self::inline_capacity() {
2082            vec![elem; n].into()
2083        } else {
2084            let mut v = SmallVec::<A>::new();
2085            unsafe {
2086                let (ptr, len_ptr, _) = v.triple_mut();
2087                let ptr = ptr.as_ptr();
2088                let mut local_len = SetLenOnDrop::new(len_ptr);
2089
2090                for i in 0..n {
2091                    ::core::ptr::write(ptr.add(i), elem.clone());
2092                    local_len.increment_len(1);
2093                }
2094            }
2095            v
2096        }
2097    }
2098}
2099
2100impl<A: Array> ops::Deref for SmallVec<A> {
2101    type Target = [A::Item];
2102
2103    #[inline]
2104    fn deref(&self) -> &[A::Item] {
2105        unsafe {
2106            let (ptr, len, _) = self.triple();
2107            slice::from_raw_parts(ptr.as_ptr(), len)
2108        }
2109    }
2110}
2111
2112impl<A: Array> ops::DerefMut for SmallVec<A> {
2113    #[inline]
2114    fn deref_mut(&mut self) -> &mut [A::Item] {
2115        unsafe {
2116            let (ptr, &mut len, _) = self.triple_mut();
2117            slice::from_raw_parts_mut(ptr.as_ptr(), len)
2118        }
2119    }
2120}
2121
2122impl<A: Array> AsRef<[A::Item]> for SmallVec<A> {
2123    #[inline]
2124    fn as_ref(&self) -> &[A::Item] { self }
2125}
2126
2127impl<A: Array> AsMut<[A::Item]> for SmallVec<A> {
2128    #[inline]
2129    fn as_mut(&mut self) -> &mut [A::Item] { self }
2130}
2131
2132impl<A: Array> Borrow<[A::Item]> for SmallVec<A> {
2133    #[inline]
2134    fn borrow(&self) -> &[A::Item] { self }
2135}
2136
2137impl<A: Array> BorrowMut<[A::Item]> for SmallVec<A> {
2138    #[inline]
2139    fn borrow_mut(&mut self) -> &mut [A::Item] { self }
2140}
2141
2142#[cfg(feature = "write")]
2143#[cfg_attr(docsrs, doc(cfg(feature = "write")))]
2144impl<A: Array<Item = u8>> io::Write for SmallVec<A> {
2145    #[inline]
2146    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
2147        self.extend_from_slice(buf);
2148        Ok(buf.len())
2149    }
2150
2151    #[inline]
2152    fn write_all(&mut self, buf: &[u8]) -> io::Result<()> {
2153        self.extend_from_slice(buf);
2154        Ok(())
2155    }
2156
2157    #[inline]
2158    fn flush(&mut self) -> io::Result<()> { Ok(()) }
2159}
2160
2161#[cfg(feature = "serde")]
2162#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
2163impl<A: Array> Serialize for SmallVec<A>
2164where A::Item: Serialize
2165{
2166    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
2167        let mut state = serializer.serialize_seq(Some(self.len()))?;
2168        for item in self {
2169            state.serialize_element(&item)?;
2170        }
2171        state.end()
2172    }
2173}
2174
2175#[cfg(feature = "serde")]
2176#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
2177impl<'de, A: Array> Deserialize<'de> for SmallVec<A>
2178where A::Item: Deserialize<'de>
2179{
2180    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
2181        deserializer.deserialize_seq(SmallVecVisitor {
2182            phantom: PhantomData
2183        })
2184    }
2185}
2186
2187#[cfg(feature = "serde")]
2188struct SmallVecVisitor<A> {
2189    phantom: PhantomData<A>
2190}
2191
2192#[cfg(feature = "serde")]
2193impl<'de, A: Array> Visitor<'de> for SmallVecVisitor<A>
2194where A::Item: Deserialize<'de>
2195{
2196    type Value = SmallVec<A>;
2197
2198    fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
2199        formatter.write_str("a sequence")
2200    }
2201
2202    fn visit_seq<B>(self, mut seq: B) -> Result<Self::Value, B::Error>
2203    where B: SeqAccess<'de> {
2204        use serde::de::Error;
2205        let len = seq.size_hint().unwrap_or(0);
2206        let mut values = SmallVec::new();
2207        values.try_reserve(len).map_err(B::Error::custom)?;
2208
2209        while let Some(value) = seq.next_element()? {
2210            values.push(value);
2211        }
2212
2213        Ok(values)
2214    }
2215}
2216
2217#[cfg(feature = "malloc_size_of")]
2218impl<A: Array> MallocShallowSizeOf for SmallVec<A> {
2219    fn shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
2220        if self.spilled() {
2221            unsafe { ops.malloc_size_of(self.as_ptr()) }
2222        } else {
2223            0
2224        }
2225    }
2226}
2227
2228#[cfg(feature = "malloc_size_of")]
2229impl<A> MallocSizeOf for SmallVec<A>
2230where
2231    A: Array,
2232    A::Item: MallocSizeOf
2233{
2234    fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
2235        let mut n = self.shallow_size_of(ops);
2236        for elem in self.iter() {
2237            n += elem.size_of(ops);
2238        }
2239        n
2240    }
2241}
2242
2243#[cfg(feature = "specialization")]
2244trait SpecFrom<A: Array, S> {
2245    fn spec_from(slice: S) -> SmallVec<A>;
2246}
2247
2248#[cfg(feature = "specialization")]
2249mod specialization;
2250
2251#[cfg(feature = "arbitrary")]
2252mod arbitrary;
2253
2254#[cfg(feature = "specialization")]
2255impl<'a, A: Array> SpecFrom<A, &'a [A::Item]> for SmallVec<A>
2256where A::Item: Copy
2257{
2258    #[inline]
2259    fn spec_from(slice: &'a [A::Item]) -> SmallVec<A> { SmallVec::from_slice(slice) }
2260}
2261
2262impl<'a, A: Array> From<&'a [A::Item]> for SmallVec<A>
2263where A::Item: Clone
2264{
2265    #[cfg(not(feature = "specialization"))]
2266    #[inline]
2267    fn from(slice: &'a [A::Item]) -> SmallVec<A> { slice.iter().cloned().collect() }
2268
2269    #[cfg(feature = "specialization")]
2270    #[inline]
2271    fn from(slice: &'a [A::Item]) -> SmallVec<A> { SmallVec::spec_from(slice) }
2272}
2273
2274impl<A: Array> From<Vec<A::Item>> for SmallVec<A> {
2275    #[inline]
2276    fn from(vec: Vec<A::Item>) -> SmallVec<A> { SmallVec::from_vec(vec) }
2277}
2278
2279impl<A: Array> From<A> for SmallVec<A> {
2280    #[inline]
2281    fn from(array: A) -> SmallVec<A> { SmallVec::from_buf(array) }
2282}
2283
2284impl<A: Array, I: SliceIndex<[A::Item]>> ops::Index<I> for SmallVec<A> {
2285    type Output = I::Output;
2286
2287    fn index(&self, index: I) -> &I::Output { &(**self)[index] }
2288}
2289
2290impl<A: Array, I: SliceIndex<[A::Item]>> ops::IndexMut<I> for SmallVec<A> {
2291    fn index_mut(&mut self, index: I) -> &mut I::Output { &mut (&mut **self)[index] }
2292}
2293
2294#[allow(deprecated)]
2295impl<A: Array> ExtendFromSlice<A::Item> for SmallVec<A>
2296where A::Item: Copy
2297{
2298    fn extend_from_slice(&mut self, other: &[A::Item]) { SmallVec::extend_from_slice(self, other) }
2299}
2300
2301impl<A: Array> FromIterator<A::Item> for SmallVec<A> {
2302    #[inline]
2303    fn from_iter<I: IntoIterator<Item = A::Item>>(iterable: I) -> SmallVec<A> {
2304        let mut v = SmallVec::new();
2305        v.extend(iterable);
2306        v
2307    }
2308}
2309
2310impl<A: Array> Extend<A::Item> for SmallVec<A> {
2311    fn extend<I: IntoIterator<Item = A::Item>>(&mut self, iterable: I) {
2312        let mut iter = iterable.into_iter();
2313        let (lower_size_bound, _) = iter.size_hint();
2314        self.reserve(lower_size_bound);
2315
2316        unsafe {
2317            let (ptr, len_ptr, cap) = self.triple_mut();
2318            let ptr = ptr.as_ptr();
2319            let mut len = SetLenOnDrop::new(len_ptr);
2320            while len.get() < cap {
2321                if let Some(out) = iter.next() {
2322                    ptr::write(ptr.add(len.get()), out);
2323                    len.increment_len(1);
2324                } else {
2325                    return;
2326                }
2327            }
2328        }
2329
2330        for elem in iter {
2331            self.push(elem);
2332        }
2333    }
2334}
2335
2336impl<A: Array> fmt::Debug for SmallVec<A>
2337where A::Item: fmt::Debug
2338{
2339    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2340        f.debug_list().entries(self.iter()).finish()
2341    }
2342}
2343
2344impl<A: Array> Default for SmallVec<A> {
2345    #[inline]
2346    fn default() -> SmallVec<A> { SmallVec::new() }
2347}
2348
2349#[cfg(feature = "may_dangle")]
2350unsafe impl<#[may_dangle] A: Array> Drop for SmallVec<A> {
2351    fn drop(&mut self) {
2352        unsafe {
2353            if self.spilled() {
2354                let (ptr, &mut len) = self.data.heap_mut();
2355                Vec::from_raw_parts(ptr.as_ptr(), len, self.capacity);
2356            } else {
2357                ptr::drop_in_place(&mut self[..]);
2358            }
2359        }
2360    }
2361}
2362
2363#[cfg(not(feature = "may_dangle"))]
2364impl<A: Array> Drop for SmallVec<A> {
2365    fn drop(&mut self) {
2366        unsafe {
2367            if self.spilled() {
2368                let (ptr, &mut len) = self.data.heap_mut();
2369                drop(Vec::from_raw_parts(ptr.as_ptr(), len, self.capacity));
2370            } else {
2371                ptr::drop_in_place(&mut self[..]);
2372            }
2373        }
2374    }
2375}
2376
2377impl<A: Array> Clone for SmallVec<A>
2378where A::Item: Clone
2379{
2380    #[inline]
2381    fn clone(&self) -> SmallVec<A> { SmallVec::from(self.as_slice()) }
2382
2383    fn clone_from(&mut self, source: &Self) {
2384        // Inspired from `impl Clone for Vec`.
2385
2386        // drop anything that will not be overwritten
2387        self.truncate(source.len());
2388
2389        // self.len <= other.len due to the truncate above, so the
2390        // slices here are always in-bounds.
2391        let (init, tail) = source.split_at(self.len());
2392
2393        // reuse the contained values' allocations/resources.
2394        self.clone_from_slice(init);
2395        self.extend(tail.iter().cloned());
2396    }
2397}
2398
2399impl<A: Array, B: Array> PartialEq<SmallVec<B>> for SmallVec<A>
2400where A::Item: PartialEq<B::Item>
2401{
2402    #[inline]
2403    fn eq(&self, other: &SmallVec<B>) -> bool { self[..] == other[..] }
2404}
2405
2406impl<A: Array> Eq for SmallVec<A> where A::Item: Eq {}
2407
2408impl<A: Array> PartialOrd for SmallVec<A>
2409where A::Item: PartialOrd
2410{
2411    #[inline]
2412    fn partial_cmp(&self, other: &SmallVec<A>) -> Option<cmp::Ordering> {
2413        PartialOrd::partial_cmp(&**self, &**other)
2414    }
2415}
2416
2417impl<A: Array> Ord for SmallVec<A>
2418where A::Item: Ord
2419{
2420    #[inline]
2421    fn cmp(&self, other: &SmallVec<A>) -> cmp::Ordering { Ord::cmp(&**self, &**other) }
2422}
2423
2424impl<A: Array> Hash for SmallVec<A>
2425where A::Item: Hash
2426{
2427    fn hash<H: Hasher>(&self, state: &mut H) { (**self).hash(state) }
2428}
2429
2430unsafe impl<A: Array> Send for SmallVec<A> where A::Item: Send {}
2431
2432/// An iterator that consumes a `SmallVec` and yields its items by value.
2433///
2434/// Returned from [`SmallVec::into_iter`][1].
2435///
2436/// [1]: struct.SmallVec.html#method.into_iter
2437pub struct IntoIter<A: Array> {
2438    data: SmallVec<A>,
2439    current: usize,
2440    end: usize
2441}
2442
2443impl<A: Array> fmt::Debug for IntoIter<A>
2444where A::Item: fmt::Debug
2445{
2446    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2447        f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
2448    }
2449}
2450
2451impl<A: Array + Clone> Clone for IntoIter<A>
2452where A::Item: Clone
2453{
2454    fn clone(&self) -> IntoIter<A> { SmallVec::from(self.as_slice()).into_iter() }
2455}
2456
2457impl<A: Array> Drop for IntoIter<A> {
2458    fn drop(&mut self) { for _ in self {} }
2459}
2460
2461impl<A: Array> Iterator for IntoIter<A> {
2462    type Item = A::Item;
2463
2464    #[inline]
2465    fn next(&mut self) -> Option<A::Item> {
2466        if self.current == self.end {
2467            None
2468        } else {
2469            unsafe {
2470                let current = self.current;
2471                self.current += 1;
2472                Some(ptr::read(self.data.as_ptr().add(current)))
2473            }
2474        }
2475    }
2476
2477    #[inline]
2478    fn size_hint(&self) -> (usize, Option<usize>) {
2479        let size = self.end - self.current;
2480        (size, Some(size))
2481    }
2482}
2483
2484impl<A: Array> DoubleEndedIterator for IntoIter<A> {
2485    #[inline]
2486    fn next_back(&mut self) -> Option<A::Item> {
2487        if self.current == self.end {
2488            None
2489        } else {
2490            unsafe {
2491                self.end -= 1;
2492                Some(ptr::read(self.data.as_ptr().add(self.end)))
2493            }
2494        }
2495    }
2496}
2497
2498impl<A: Array> ExactSizeIterator for IntoIter<A> {}
2499impl<A: Array> FusedIterator for IntoIter<A> {}
2500
2501impl<A: Array> IntoIter<A> {
2502    /// Returns the remaining items of this iterator as a slice.
2503    pub fn as_slice(&self) -> &[A::Item] {
2504        let len = self.end - self.current;
2505        unsafe { core::slice::from_raw_parts(self.data.as_ptr().add(self.current), len) }
2506    }
2507
2508    /// Returns the remaining items of this iterator as a mutable slice.
2509    pub fn as_mut_slice(&mut self) -> &mut [A::Item] {
2510        let len = self.end - self.current;
2511        unsafe { core::slice::from_raw_parts_mut(self.data.as_mut_ptr().add(self.current), len) }
2512    }
2513}
2514
2515impl<A: Array> IntoIterator for SmallVec<A> {
2516    type IntoIter = IntoIter<A>;
2517    type Item = A::Item;
2518
2519    fn into_iter(mut self) -> Self::IntoIter {
2520        unsafe {
2521            // Set SmallVec len to zero as `IntoIter` drop handles dropping of
2522            // the elements
2523            let len = self.len();
2524            self.set_len(0);
2525            IntoIter {
2526                data: self,
2527                current: 0,
2528                end: len
2529            }
2530        }
2531    }
2532}
2533
2534impl<'a, A: Array> IntoIterator for &'a SmallVec<A> {
2535    type IntoIter = slice::Iter<'a, A::Item>;
2536    type Item = &'a A::Item;
2537
2538    fn into_iter(self) -> Self::IntoIter { self.iter() }
2539}
2540
2541impl<'a, A: Array> IntoIterator for &'a mut SmallVec<A> {
2542    type IntoIter = slice::IterMut<'a, A::Item>;
2543    type Item = &'a mut A::Item;
2544
2545    fn into_iter(self) -> Self::IntoIter { self.iter_mut() }
2546}
2547
2548/// Types that can be used as the backing store for a [`SmallVec`].
2549pub unsafe trait Array {
2550    /// The type of the array's elements.
2551    type Item;
2552    /// Returns the number of items the array can hold.
2553    fn size() -> usize;
2554}
2555
2556/// Set the length of the vec when the `SetLenOnDrop` value goes out of scope.
2557///
2558/// Copied from <https://github.com/rust-lang/rust/pull/36355>
2559struct SetLenOnDrop<'a> {
2560    len: &'a mut usize,
2561    local_len: usize
2562}
2563
2564impl<'a> SetLenOnDrop<'a> {
2565    #[inline]
2566    fn new(len: &'a mut usize) -> Self {
2567        SetLenOnDrop {
2568            local_len: *len,
2569            len
2570        }
2571    }
2572
2573    #[inline]
2574    fn get(&self) -> usize { self.local_len }
2575
2576    #[inline]
2577    fn increment_len(&mut self, increment: usize) { self.local_len += increment; }
2578}
2579
2580impl<'a> Drop for SetLenOnDrop<'a> {
2581    #[inline]
2582    fn drop(&mut self) { *self.len = self.local_len; }
2583}
2584
2585#[cfg(feature = "const_new")]
2586impl<T, const N: usize> SmallVec<[T; N]> {
2587    /// Construct an empty vector.
2588    ///
2589    /// This is a `const` version of [`SmallVec::new`] that is enabled by the
2590    /// feature `const_new`, with the limitation that it only works for arrays.
2591    #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
2592    #[inline]
2593    pub const fn new_const() -> Self {
2594        SmallVec {
2595            capacity: 0,
2596            data: SmallVecData::from_const(MaybeUninit::uninit()),
2597            _marker: PhantomData
2598        }
2599    }
2600
2601    /// The array passed as an argument is moved to be an inline version of
2602    /// `SmallVec`.
2603    ///
2604    /// This is a `const` version of [`SmallVec::from_buf`] that is enabled by
2605    /// the feature `const_new`, with the limitation that it only works for
2606    /// arrays.
2607    #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
2608    #[inline]
2609    pub const fn from_const(items: [T; N]) -> Self {
2610        SmallVec {
2611            capacity: N,
2612            data: SmallVecData::from_const(MaybeUninit::new(items)),
2613            _marker: PhantomData
2614        }
2615    }
2616
2617    /// Constructs a new `SmallVec` on the stack from an array without
2618    /// copying elements. Also sets the length. The user is responsible
2619    /// for ensuring that `len <= N`.
2620    ///
2621    /// This is a `const` version of [`SmallVec::from_buf_and_len_unchecked`]
2622    /// that is enabled by the feature `const_new`, with the limitation that it
2623    /// only works for arrays.
2624    #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
2625    #[inline]
2626    pub const unsafe fn from_const_with_len_unchecked(items: [T; N], len: usize) -> Self {
2627        SmallVec {
2628            capacity: len,
2629            data: SmallVecData::from_const(MaybeUninit::new(items)),
2630            _marker: PhantomData
2631        }
2632    }
2633}
2634
2635#[cfg(feature = "const_generics")]
2636#[cfg_attr(docsrs, doc(cfg(feature = "const_generics")))]
2637unsafe impl<T, const N: usize> Array for [T; N] {
2638    type Item = T;
2639
2640    #[inline]
2641    fn size() -> usize { N }
2642}
2643
2644#[cfg(not(feature = "const_generics"))]
2645macro_rules! impl_array(
2646    ($($size:expr),+) => {
2647        $(
2648            unsafe impl<T> Array for [T; $size] {
2649                type Item = T;
2650                #[inline]
2651                fn size() -> usize { $size }
2652            }
2653        )+
2654    }
2655);
2656
2657#[cfg(not(feature = "const_generics"))]
2658impl_array!(
2659    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
2660    26, 27, 28, 29, 30, 31, 32, 36, 0x40, 0x60, 0x80, 0x100, 0x200, 0x400, 0x600, 0x800, 0x1000,
2661    0x2000, 0x4000, 0x6000, 0x8000, 0x10000, 0x20000, 0x40000, 0x60000, 0x80000, 0x10_0000
2662);
2663
2664/// Convenience trait for constructing a `SmallVec`
2665pub trait ToSmallVec<A: Array> {
2666    /// Construct a new `SmallVec` from a slice.
2667    fn to_smallvec(&self) -> SmallVec<A>;
2668}
2669
2670impl<A: Array> ToSmallVec<A> for [A::Item]
2671where A::Item: Copy
2672{
2673    #[inline]
2674    fn to_smallvec(&self) -> SmallVec<A> { SmallVec::from_slice(self) }
2675}
2676
2677// Immutable counterpart for `NonNull<T>`.
2678#[repr(transparent)]
2679struct ConstNonNull<T>(NonNull<T>);
2680
2681impl<T> ConstNonNull<T> {
2682    #[inline]
2683    fn new(ptr: *const T) -> Option<Self> { NonNull::new(ptr as *mut T).map(Self) }
2684
2685    #[inline]
2686    fn as_ptr(self) -> *const T { self.0.as_ptr() }
2687}
2688
2689impl<T> Clone for ConstNonNull<T> {
2690    #[inline]
2691    fn clone(&self) -> Self { *self }
2692}
2693
2694impl<T> Copy for ConstNonNull<T> {}
2695
2696#[cfg(feature = "impl_bincode")]
2697use bincode::{
2698    BorrowDecode,
2699    de::{
2700        BorrowDecoder,
2701        Decode,
2702        Decoder,
2703        read::Reader
2704    },
2705    enc::{
2706        Encode,
2707        Encoder,
2708        write::Writer
2709    },
2710    error::{
2711        DecodeError,
2712        EncodeError
2713    }
2714};
2715
2716#[cfg(feature = "impl_bincode")]
2717impl<A, Context> Decode<Context> for SmallVec<A>
2718where
2719    A: Array,
2720    A::Item: Decode<Context>
2721{
2722    fn decode<D: Decoder<Context = Context>>(decoder: &mut D) -> Result<Self, DecodeError> {
2723        use core::convert::TryInto;
2724        let len = u64::decode(decoder)?;
2725        let len = len
2726            .try_into()
2727            .map_err(|_| DecodeError::OutsideUsizeRange(len))?;
2728        decoder.claim_container_read::<A::Item>(len)?;
2729
2730        let mut vec = SmallVec::with_capacity(len);
2731        if unty::type_equal::<A::Item, u8>() {
2732            // Initialize the smallvec's buffer.  Note that we need to do this
2733            // through the raw pointer as we cannot name the type
2734            // [u8; N] even though A::Item is u8.
2735            let ptr = vec.as_mut_ptr();
2736            // SAFETY: A::Item is u8 and the smallvec has been allocated with
2737            // enough capacity
2738            unsafe {
2739                core::ptr::write_bytes(ptr, 0, len);
2740                vec.set_len(len);
2741            }
2742            // Read the data into the smallvec's buffer.
2743            let slice = vec.as_mut_slice();
2744            // SAFETY: A::Item is u8
2745            let slice = unsafe { core::mem::transmute::<&mut [A::Item], &mut [u8]>(slice) };
2746            decoder.reader().read(slice)?;
2747        } else {
2748            for _ in 0..len {
2749                decoder.unclaim_bytes_read(core::mem::size_of::<A::Item>());
2750                vec.push(A::Item::decode(decoder)?);
2751            }
2752        }
2753        Ok(vec)
2754    }
2755}
2756
2757#[cfg(feature = "impl_bincode")]
2758impl<'de, A, Context> BorrowDecode<'de, Context> for SmallVec<A>
2759where
2760    A: Array,
2761    A::Item: BorrowDecode<'de, Context>
2762{
2763    fn borrow_decode<D: BorrowDecoder<'de, Context = Context>>(
2764        decoder: &mut D
2765    ) -> Result<Self, DecodeError> {
2766        use core::convert::TryInto;
2767        let len = u64::decode(decoder)?;
2768        let len = len
2769            .try_into()
2770            .map_err(|_| DecodeError::OutsideUsizeRange(len))?;
2771        decoder.claim_container_read::<A::Item>(len)?;
2772
2773        let mut vec = SmallVec::with_capacity(len);
2774        if unty::type_equal::<A::Item, u8>() {
2775            // Initialize the smallvec's buffer.  Note that we need to do this
2776            // through the raw pointer as we cannot name the type
2777            // [u8; N] even though A::Item is u8.
2778            let ptr = vec.as_mut_ptr();
2779            // SAFETY: A::Item is u8 and the smallvec has been allocated with
2780            // enough capacity
2781            unsafe {
2782                core::ptr::write_bytes(ptr, 0, len);
2783                vec.set_len(len);
2784            }
2785            // Read the data into the smallvec's buffer.
2786            let slice = vec.as_mut_slice();
2787            // SAFETY: A::Item is u8
2788            let slice = unsafe { core::mem::transmute::<&mut [A::Item], &mut [u8]>(slice) };
2789            decoder.reader().read(slice)?;
2790        } else {
2791            for _ in 0..len {
2792                decoder.unclaim_bytes_read(core::mem::size_of::<A::Item>());
2793                vec.push(A::Item::borrow_decode(decoder)?);
2794            }
2795        }
2796        Ok(vec)
2797    }
2798}
2799
2800#[cfg(feature = "impl_bincode")]
2801impl<A> Encode for SmallVec<A>
2802where
2803    A: Array,
2804    A::Item: Encode
2805{
2806    fn encode<E: Encoder>(&self, encoder: &mut E) -> Result<(), EncodeError> {
2807        (self.len() as u64).encode(encoder)?;
2808        if unty::type_equal::<A::Item, u8>() {
2809            // Safety: A::Item is u8
2810            let slice: &[u8] = unsafe { core::mem::transmute(self.as_slice()) };
2811            encoder.writer().write(slice)?;
2812        } else {
2813            for item in self.iter() {
2814                item.encode(encoder)?;
2815            }
2816        }
2817        Ok(())
2818    }
2819}