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}