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