|
|
|
|
Quelle lib.rs
Sprache: unbekannt
|
|
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
//! Small vectors in various sizes. These store a certain number of elements inline, and fall ba ck
//! to the heap for larger allocations. This can be a useful optimization for improving cache
//! locality and reducing allocator traffic for workloads that fit within the inline buffer.
//!
//! ## `no_std` support
//!
//! By default, `smallvec` does not depend on `std`. However, the optional
//! `write` feature implements the `std::io::Write` trait for vectors of `u8`.
//! When this feature is enabled, `smallvec` depends on `std`.
//!
//! ## Optional features
//!
//! ### `serde`
//!
//! When this optional dependency is enabled, `SmallVec` implements the `serde::Serialize` and
//! `serde::Deserialize` traits.
//!
//! ### `write`
//!
//! When this feature is enabled, `SmallVec<[u8; _]>` implements the `std::io::Write` trait.
//! This feature is not compatible with `#![no_std]` programs.
//!
//! ### `union`
//!
//! **This feature requires Rust 1.49.**
//!
//! When the `union` feature is enabled `smallvec` will track its state (inline or spilled)
//! without the use of an enum tag, reducing the size of the `smallvec` by one machine word.
//! This means that there is potentially no space overhead compared to `Vec`.
//! Note that `smallvec` can still be larger than `Vec` if the inline buffer is larger than two
//! machine words.
//!
//! To use this feature add `features = ["union"]` in the `smallvec` section of Cargo.toml.
//! Note that this feature requires Rust 1.49.
//!
//! Tracking issue: [rust-lang/rust#55149](https://github.com/rust-lang/rust/issues/55149)
//!
//! ### `const_generics`
//!
//! **This feature requires Rust 1.51.**
//!
//! When this feature is enabled, `SmallVec` works with any arrays of any size, not just a fixed
//! list of sizes.
//!
//! ### `const_new`
//!
//! **This feature requires Rust 1.51.**
//!
//! 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.
//! For details, see the
//! [Rust Reference](https://doc.rust-lang.org/reference/const_eval.html#const-functions).
//!
//! ### `drain_filter`
//!
//! **This feature is unstable.** It may change to match the unstable `drain_filter` method in libstd.
//!
//! Enables the `drain_filter` method, which produces an iterator that calls a user-provided
//! closure to determine which elements of the vector to remove and yield from the iterator.
//!
//! ### `drain_keep_rest`
//!
//! **This feature is unstable.** It may change to match the unstable `drain_keep_rest` method in libstd.
//!
//! Enables the `DrainFilter::keep_rest` method.
//!
//! ### `specialization`
//!
//! **This feature is unstable and requires a nightly build of the Rust toolchain.**
//!
//! When this feature is enabled, `SmallVec::from(slice)` has improved performance for slices
//! of `Copy` types. (Without this feature, you can use `SmallVec::from_slice` to get optimal
//! performance for `Copy` types.)
//!
//! Tracking issue: [rust-lang/rust#31844](https://github.com/rust-lang/rust/issues/31844)
//!
//! ### `may_dangle`
//!
//! **This feature is unstable and requires a nightly build of the Rust toolchain.**
//!
//! This feature makes the Rust compiler less strict about use of vectors that contain borrowed
//! references. For details, see the
//! [Rustonomicon](https://doc.rust-lang.org/1.42.0/nomicon/dropck.html#an-escape-hatch).
//!
//! Tracking issue: [rust-lang/rust#34761](https://github.com/rust-lang/rust/issues/34761)
#![no_std]
#![cfg_attr(docsrs, feature(doc_cfg))]
#![cfg_attr(feature = "specialization", allow(incomplete_features))]
#![cfg_attr(feature = "specialization", feature(specialization))]
#![cfg_attr(feature = "may_dangle", feature(dropck_eyepatch))]
#![cfg_attr(
feature = "debugger_visualizer",
feature(debugger_visualizer),
debugger_visualizer(natvis_file = "../debug_metadata/smallvec.natvis")
)]
#![deny(missing_docs)]
#[doc(hidden)]
pub extern crate alloc;
#[cfg(any(test, feature = "write"))]
extern crate std;
#[cfg(test)]
mod tests;
#[allow(deprecated)]
use alloc::alloc::{Layout, LayoutErr};
use alloc::boxed::Box;
use alloc::{vec, vec::Vec};
use core::borrow::{Borrow, BorrowMut};
use core::cmp;
use core::fmt;
use core::hash::{Hash, Hasher};
use core::hint::unreachable_unchecked;
use core::iter::{repeat, FromIterator, FusedIterator, IntoIterator};
use core::mem;
use core::mem::MaybeUninit;
use core::ops::{self, Range, RangeBounds};
use core::ptr::{self, NonNull};
use core::slice::{self, SliceIndex};
#[cfg(feature = "serde")]
use serde::{
de::{Deserialize, Deserializer, SeqAccess, Visitor},
ser::{Serialize, SerializeSeq, Serializer},
};
#[cfg(feature = "serde")]
use core::marker::PhantomData;
#[cfg(feature = "write")]
use std::io;
#[cfg(feature = "drain_keep_rest")]
use core::mem::ManuallyDrop;
/// Creates a [`SmallVec`] containing the arguments.
///
/// `smallvec!` allows `SmallVec`s to be defined with the same syntax as array expressions.
/// There are two forms of this macro:
///
/// - Create a [`SmallVec`] containing a given list of elements:
///
/// ```
/// # use smallvec::{smallvec, SmallVec};
/// # fn main() {
/// let v: SmallVec<[_; 128]> = smallvec![1, 2, 3];
/// assert_eq!(v[0], 1);
/// assert_eq!(v[1], 2);
/// assert_eq!(v[2], 3);
/// # }
/// ```
///
/// - Create a [`SmallVec`] from a given element and size:
///
/// ```
/// # use smallvec::{smallvec, SmallVec};
/// # fn main() {
/// let v: SmallVec<[_; 0x8000]> = smallvec![1; 3];
/// assert_eq!(v, SmallVec::from_buf([1, 1, 1]));
/// # }
/// ```
///
/// Note that unlike array expressions this syntax supports all elements
/// which implement [`Clone`] and the number of elements doesn't have to be
/// a constant.
///
/// This will use `clone` to duplicate an expression, so one should be careful
/// using this with types having a nonstandard `Clone` implementation. For
/// example, `smallvec![Rc::new(1); 5]` will create a vector of five references
/// to the same boxed integer value, not five references pointing to independently
/// boxed integers.
#[macro_export]
macro_rules! smallvec {
// count helper: transform any expression into 1
(@one $x:expr) => (1usize);
($elem:expr; $n:expr) => ({
$crate::SmallVec::from_elem($elem, $n)
});
($($x:expr),*$(,)*) => ({
let count = 0usize $(+ $crate::smallvec!(@one $x))*;
#[allow(unused_mut)]
let mut vec = $crate::SmallVec::new();
if count <= vec.inline_size() {
$(vec.push($x);)*
vec
} else {
$crate::SmallVec::from_vec($crate::alloc::vec![$($x,)*])
}
});
}
/// Creates an inline [`SmallVec`] containing the arguments. This macro is enabled by the feature `const_new`.
///
/// `smallvec_inline!` allows `SmallVec`s to be defined with the same syntax as array expressions in `const` contexts.
/// The inline storage `A` will always be an array of the size specified by the arguments.
/// There are two forms of this macro:
///
/// - Create a [`SmallVec`] containing a given list of elements:
///
/// ```
/// # use smallvec::{smallvec_inline, SmallVec};
/// # fn main() {
/// const V: SmallVec<[i32; 3]> = smallvec_inline![1, 2, 3];
/// assert_eq!(V[0], 1);
/// assert_eq!(V[1], 2);
/// assert_eq!(V[2], 3);
/// # }
/// ```
///
/// - Create a [`SmallVec`] from a given element and size:
///
/// ```
/// # use smallvec::{smallvec_inline, SmallVec};
/// # fn main() {
/// const V: SmallVec<[i32; 3]> = smallvec_inline![1; 3];
/// assert_eq!(V, SmallVec::from_buf([1, 1, 1]));
/// # }
/// ```
///
/// Note that the behavior mimics that of array expressions, in contrast to [`smallvec`].
#[cfg(feature = "const_new")]
#[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
#[macro_export]
macro_rules! smallvec_inline {
// count helper: transform any expression into 1
(@one $x:expr) => (1usize);
($elem:expr; $n:expr) => ({
$crate::SmallVec::<[_; $n]>::from_const([$elem; $n])
});
($($x:expr),+ $(,)?) => ({
const N: usize = 0usize $(+ $crate::smallvec_inline!(@one $x))*;
$crate::SmallVec::<[_; N]>::from_const([$($x,)*])
});
}
/// `panic!()` in debug builds, optimization hint in release.
#[cfg(not(feature = "union"))]
macro_rules! debug_unreachable {
() => {
debug_unreachable!("entered unreachable code")
};
($e:expr) => {
if cfg!(debug_assertions) {
panic!($e);
} else {
unreachable_unchecked();
}
};
}
/// Trait to be implemented by a collection that can be extended from a slice
///
/// ## Example
///
/// ```rust
/// use smallvec::{ExtendFromSlice, SmallVec};
///
/// fn initialize<V: ExtendFromSlice<u8>>(v: &mut V) {
/// v.extend_from_slice(b"Test!");
/// }
///
/// let mut vec = Vec::new();
/// initialize(&mut vec);
/// assert_eq!(&vec, b"Test!");
///
/// let mut small_vec = SmallVec::<[u8; 8]>::new();
/// initialize(&mut small_vec);
/// assert_eq!(&small_vec as &[_], b"Test!");
/// ```
#[doc(hidden)]
#[deprecated]
pub trait ExtendFromSlice<T> {
/// Extends a collection from a slice of its element type
fn extend_from_slice(&mut self, other: &[T]);
}
#[allow(deprecated)]
impl<T: Clone> ExtendFromSlice<T> for Vec<T> {
fn extend_from_slice(&mut self, other: &[T]) {
Vec::extend_from_slice(self, other)
}
}
/// Error type for APIs with fallible heap allocation
#[derive(Debug)]
pub enum CollectionAllocErr {
/// Overflow `usize::MAX` or other error during size computation
CapacityOverflow,
/// The allocator return an error
AllocErr {
/// The layout that was passed to the allocator
layout: Layout,
},
}
impl fmt::Display for CollectionAllocErr {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "Allocation error: {:?}", self)
}
}
#[allow(deprecated)]
impl From<LayoutErr> for CollectionAllocErr {
fn from(_: LayoutErr) -> Self {
CollectionAllocErr::CapacityOverflow
}
}
fn infallible<T>(result: Result<T, CollectionAllocErr>) -> T {
match result {
Ok(x) => x,
Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"),
Err(CollectionAllocErr::AllocErr { layout }) => alloc::alloc::handle_alloc_error(layout),
}
}
/// FIXME: use `Layout::array` when we require a Rust version where it’s stable
/// <https://github.com/rust-lang/rust/issues/55724>
fn layout_array<T>(n: usize) -> Result<Layout, CollectionAllocErr> {
let size = mem::size_of::<T>()
.checked_mul(n)
.ok_or(CollectionAllocErr::CapacityOverflow)?;
let align = mem::align_of::<T>();
Layout::from_size_align(size, align).map_err(|_| CollectionAllocErr::CapacityOverflow)
}
unsafe fn deallocate<T>(ptr: NonNull<T>, capacity: usize) {
// This unwrap should succeed since the same did when allocating.
let layout = layout_array::<T>(capacity).unwrap();
alloc::alloc::dealloc(ptr.as_ptr() as *mut u8, layout)
}
/// An iterator that removes the items from a `SmallVec` and yields them by value.
///
/// Returned from [`SmallVec::drain`][1].
///
/// [1]: struct.SmallVec.html#method.drain
pub struct Drain<'a, T: 'a + Array> {
tail_start: usize,
tail_len: usize,
iter: slice::Iter<'a, T::Item>,
vec: NonNull<SmallVec<T>>,
}
impl<'a, T: 'a + Array> fmt::Debug for Drain<'a, T>
where
T::Item: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("Drain").field(&self.iter.as_slice()).finish()
}
}
unsafe impl<'a, T: Sync + Array> Sync for Drain<'a, T> {}
unsafe impl<'a, T: Send + Array> Send for Drain<'a, T> {}
impl<'a, T: 'a + Array> Iterator for Drain<'a, T> {
type Item = T::Item;
#[inline]
fn next(&mut self) -> Option<T::Item> {
self.iter
.next()
.map(|reference| unsafe { ptr::read(reference) })
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, T: 'a + Array> DoubleEndedIterator for Drain<'a, T> {
#[inline]
fn next_back(&mut self) -> Option<T::Item> {
self.iter
.next_back()
.map(|reference| unsafe { ptr::read(reference) })
}
}
impl<'a, T: Array> ExactSizeIterator for Drain<'a, T> {
#[inline]
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, T: Array> FusedIterator for Drain<'a, T> {}
impl<'a, T: 'a + Array> Drop for Drain<'a, T> {
fn drop(&mut self) {
self.for_each(drop);
if self.tail_len > 0 {
unsafe {
let source_vec = self.vec.as_mut();
// memmove back untouched tail, update to new length
let start = source_vec.len();
let tail = self.tail_start;
if tail != start {
// as_mut_ptr creates a &mut, invalidating other pointers.
// This pattern avoids calling it with a pointer already present.
let ptr = source_vec.as_mut_ptr();
let src = ptr.add(tail);
let dst = ptr.add(start);
ptr::copy(src, dst, self.tail_len);
}
source_vec.set_len(start + self.tail_len);
}
}
}
}
#[cfg(feature = "drain_filter")]
/// An iterator which uses a closure to determine if an element should be removed.
///
/// Returned from [`SmallVec::drain_filter`][1].
///
/// [1]: struct.SmallVec.html#method.drain_filter
pub struct DrainFilter<'a, T, F>
where
F: FnMut(&mut T::Item) -> bool,
T: Array,
{
vec: &'a mut SmallVec<T>,
/// The index of the item that will be inspected by the next call to `next`.
idx: usize,
/// The number of items that have been drained (removed) thus far.
del: usize,
/// The original length of `vec` prior to draining.
old_len: usize,
/// The filter test predicate.
pred: F,
/// A flag that indicates a panic has occurred in the filter test predicate.
/// This is used as a hint in the drop implementation to prevent consumption
/// of the remainder of the `DrainFilter`. Any unprocessed items will be
/// backshifted in the `vec`, but no further items will be dropped or
/// tested by the filter predicate.
panic_flag: bool,
}
#[cfg(feature = "drain_filter")]
impl <T, F> fmt::Debug for DrainFilter<'_, T, F>
where
F: FnMut(&mut T::Item) -> bool,
T: Array,
T::Item: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("DrainFilter").field(&self.vec.as_slice()).finish()
}
}
#[cfg(feature = "drain_filter")]
impl <T, F> Iterator for DrainFilter<'_, T, F>
where
F: FnMut(&mut T::Item) -> bool,
T: Array,
{
type Item = T::Item;
fn next(&mut self) -> Option<T::Item>
{
unsafe {
while self.idx < self.old_len {
let i = self.idx;
let v = slice::from_raw_parts_mut(self.vec.as_mut_ptr(), self.old_len);
self.panic_flag = true;
let drained = (self.pred)(&mut v[i]);
self.panic_flag = false;
// Update the index *after* the predicate is called. If the index
// is updated prior and the predicate panics, the element at this
// index would be leaked.
self.idx += 1;
if drained {
self.del += 1;
return Some(ptr::read(&v[i]));
} else if self.del > 0 {
let del = self.del;
let src: *const Self::Item = &v[i];
let dst: *mut Self::Item = &mut v[i - del];
ptr::copy_nonoverlapping(src, dst, 1);
}
}
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(0, Some(self.old_len - self.idx))
}
}
#[cfg(feature = "drain_filter")]
impl <T, F> Drop for DrainFilter<'_, T, F>
where
F: FnMut(&mut T::Item) -> bool,
T: Array,
{
fn drop(&mut self) {
struct BackshiftOnDrop<'a, 'b, T, F>
where
F: FnMut(&mut T::Item) -> bool,
T: Array
{
drain: &'b mut DrainFilter<'a, T, F>,
}
impl<'a, 'b, T, F> Drop for BackshiftOnDrop<'a, 'b, T, F>
where
F: FnMut(&mut T::Item) -> bool,
T: Array
{
fn drop(&mut self) {
unsafe {
if self.drain.idx < self.drain.old_len && self.drain.del > 0 {
// This is a pretty messed up state, and there isn't really an
// obviously right thing to do. We don't want to keep trying
// to execute `pred`, so we just backshift all the unprocessed
// elements and tell the vec that they still exist. The backshift
// is required to prevent a double-drop of the last successfully
// drained item prior to a panic in the predicate.
let ptr = self.drain.vec.as_mut_ptr();
let src = ptr.add(self.drain.idx);
let dst = src.sub(self.drain.del);
let tail_len = self.drain.old_len - self.drain.idx;
src.copy_to(dst, tail_len);
}
self.drain.vec.set_len(self.drain.old_len - self.drain.del);
}
}
}
let backshift = BackshiftOnDrop { drain: self };
// Attempt to consume any remaining elements if the filter predicate
// has not yet panicked. We'll backshift any remaining elements
// whether we've already panicked or if the consumption here panics.
if !backshift.drain.panic_flag {
backshift.drain.for_each(drop);
}
}
}
#[cfg(feature = "drain_keep_rest")]
impl <T, F> DrainFilter<'_, T, F>
where
F: FnMut(&mut T::Item) -> bool,
T: Array
{
/// Keep unyielded elements in the source `Vec`.
///
/// # Examples
///
/// ```
/// # use smallvec::{smallvec, SmallVec};
///
/// let mut vec: SmallVec<[char; 2]> = smallvec!['a', 'b', 'c'];
/// let mut drain = vec.drain_filter(|_| true);
///
/// assert_eq!(drain.next().unwrap(), 'a');
///
/// // This call keeps 'b' and 'c' in the vec.
/// drain.keep_rest();
///
/// // If we wouldn't call `keep_rest()`,
/// // `vec` would be empty.
/// assert_eq!(vec, SmallVec::<[char; 2]>::from_slice(&['b', 'c']));
/// ```
pub fn keep_rest(self)
{
// At this moment layout looks like this:
//
// _____________________/-- old_len
// / \
// [kept] [yielded] [tail]
// \_______/ ^-- idx
// \-- del
//
// Normally `Drop` impl would drop [tail] (via .for_each(drop), ie still calling `pred`)
//
// 1. Move [tail] after [kept]
// 2. Update length of the original vec to `old_len - del`
// a. In case of ZST, this is the only thing we want to do
// 3. Do *not* drop self, as everything is put in a consistent state already, there is nothing to do
let mut this = ManuallyDrop::new(self);
unsafe {
// ZSTs have no identity, so we don't need to move them around.
let needs_move = mem::size_of::<T>() != 0;
if needs_move && this.idx < this.old_len && this.del > 0 {
let ptr = this.vec.as_mut_ptr();
let src = ptr.add(this.idx);
let dst = src.sub(this.del);
let tail_len = this.old_len - this.idx;
src.copy_to(dst, tail_len);
}
let new_len = this.old_len - this.del;
this.vec.set_len(new_len);
}
}
}
#[cfg(feature = "union")]
union SmallVecData<A: Array> {
inline: core::mem::ManuallyDrop<MaybeUninit<A>>,
heap: (NonNull<A::Item>, usize),
}
#[cfg(all(feature = "union", feature = "const_new"))]
impl<T, const N: usize> SmallVecData<[T; N]> {
#[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
#[inline]
const fn from_const(inline: MaybeUninit<[T; N]>) -> Self {
SmallVecData {
inline: core::mem::ManuallyDrop::new(inline),
}
}
}
#[cfg(feature = "union")]
impl<A: Array> SmallVecData<A> {
#[inline]
unsafe fn inline(&self) -> ConstNonNull<A::Item> {
ConstNonNull::new(self.inline.as_ptr() as *const A::Item).unwrap()
}
#[inline]
unsafe fn inline_mut(&mut self) -> NonNull<A::Item> {
NonNull::new(self.inline.as_mut_ptr() as *mut A::Item).unwrap()
}
#[inline]
fn from_inline(inline: MaybeUninit<A>) -> SmallVecData<A> {
SmallVecData {
inline: core::mem::ManuallyDrop::new(inline),
}
}
#[inline]
unsafe fn into_inline(self) -> MaybeUninit<A> {
core::mem::ManuallyDrop::into_inner(self.inline)
}
#[inline]
unsafe fn heap(&self) -> (ConstNonNull<A::Item>, usize) {
(ConstNonNull(self.heap.0), self.heap.1)
}
#[inline]
unsafe fn heap_mut(&mut self) -> (NonNull<A::Item>, &mut usize) {
let h = &mut self.heap;
(h.0, &mut h.1)
}
#[inline]
fn from_heap(ptr: NonNull<A::Item>, len: usize) -> SmallVecData<A> {
SmallVecData { heap: (ptr, len) }
}
}
#[cfg(not(feature = "union"))]
enum SmallVecData<A: Array> {
Inline(MaybeUninit<A>),
// Using NonNull and NonZero here allows to reduce size of `SmallVec`.
Heap {
// Since we never allocate on heap
// unless our capacity is bigger than inline capacity
// heap capacity cannot be less than 1.
// Therefore, pointer cannot be null too.
ptr: NonNull<A::Item>,
len: usize,
},
}
#[cfg(all(not(feature = "union"), feature = "const_new"))]
impl<T, const N: usize> SmallVecData<[T; N]> {
#[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
#[inline]
const fn from_const(inline: MaybeUninit<[T; N]>) -> Self {
SmallVecData::Inline(inline)
}
}
#[cfg(not(feature = "union"))]
impl<A: Array> SmallVecData<A> {
#[inline]
unsafe fn inline(&self) -> ConstNonNull<A::Item> {
match self {
SmallVecData::Inline(a) => ConstNonNull::new(a.as_ptr() as *const A::Item).unwrap(),
_ => debug_unreachable!(),
}
}
#[inline]
unsafe fn inline_mut(&mut self) -> NonNull<A::Item> {
match self {
SmallVecData::Inline(a) => NonNull::new(a.as_mut_ptr() as *mut A::Item).unwrap(),
_ => debug_unreachable!(),
}
}
#[inline]
fn from_inline(inline: MaybeUninit<A>) -> SmallVecData<A> {
SmallVecData::Inline(inline)
}
#[inline]
unsafe fn into_inline(self) -> MaybeUninit<A> {
match self {
SmallVecData::Inline(a) => a,
_ => debug_unreachable!(),
}
}
#[inline]
unsafe fn heap(&self) -> (ConstNonNull<A::Item>, usize) {
match self {
SmallVecData::Heap { ptr, len } => (ConstNonNull(*ptr), *len),
_ => debug_unreachable!(),
}
}
#[inline]
unsafe fn heap_mut(&mut self) -> (NonNull<A::Item>, &mut usize) {
match self {
SmallVecData::Heap { ptr, len } => (*ptr, len),
_ => debug_unreachable!(),
}
}
#[inline]
fn from_heap(ptr: NonNull<A::Item>, len: usize) -> SmallVecData<A> {
SmallVecData::Heap { ptr, len }
}
}
unsafe impl<A: Array + Send> Send for SmallVecData<A> {}
unsafe impl<A: Array + Sync> Sync for SmallVecData<A> {}
/// A `Vec`-like container that can store a small number of elements inline.
///
/// `SmallVec` acts like a vector, but can store a limited amount of data inline within the
/// `SmallVec` struct rather than in a separate allocation. If the data exceeds this limit, the
/// `SmallVec` will "spill" its data onto the heap, allocating a new buffer to hold it.
///
/// The amount of data that a `SmallVec` can store inline depends on its backing store. The backing
/// store can be any type that implements the `Array` trait; usually it is a small fixed-sized
/// array. For example a `SmallVec<[u64; 8]>` can hold up to eight 64-bit integers inline.
///
/// ## Example
///
/// ```rust
/// use smallvec::SmallVec;
/// let mut v = SmallVec::<[u8; 4]>::new(); // initialize an empty vector
///
/// // The vector can hold up to 4 items without spilling onto the heap.
/// v.extend(0..4);
/// assert_eq!(v.len(), 4);
/// assert!(!v.spilled());
///
/// // Pushing another element will force the buffer to spill:
/// v.push(4);
/// assert_eq!(v.len(), 5);
/// assert!(v.spilled());
/// ```
pub struct SmallVec<A: Array> {
// The capacity field is used to determine which of the storage variants is active:
// 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).
// If capacity > Self::inline_capacity() then the heap variant is used and capacity holds the size of the memory allocation.
capacity: usize,
data: SmallVecData<A>,
}
impl<A: Array> SmallVec<A> {
/// Construct an empty vector
#[inline]
pub fn new() -> SmallVec<A> {
// Try to detect invalid custom implementations of `Array`. Hopefully,
// this check should be optimized away entirely for valid ones.
assert!(
mem::size_of::<A>() == A::size() * mem::size_of::<A::Item>()
&& mem::align_of::<A>() >= mem::align_of::<A::Item>()
);
SmallVec {
capacity: 0,
data: SmallVecData::from_inline(MaybeUninit::uninit()),
}
}
/// Construct an empty vector with enough capacity pre-allocated to store at least `n`
/// elements.
///
/// Will create a heap allocation only if `n` is larger than the inline capacity.
///
/// ```
/// # use smallvec::SmallVec;
///
/// let v: SmallVec<[u8; 3]> = SmallVec::with_capacity(100);
///
/// assert!(v.is_empty());
/// assert!(v.capacity() >= 100);
/// ```
#[inline]
pub fn with_capacity(n: usize) -> Self {
let mut v = SmallVec::new();
v.reserve_exact(n);
v
}
/// Construct a new `SmallVec` from a `Vec<A::Item>`.
///
/// Elements will be copied to the inline buffer if `vec.capacity() <= Self::inline_capacity()`.
///
/// ```rust
/// use smallvec::SmallVec;
///
/// let vec = vec![1, 2, 3, 4, 5];
/// let small_vec: SmallVec<[_; 3]> = SmallVec::from_vec(vec);
///
/// assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
/// ```
#[inline]
pub fn from_vec(mut vec: Vec<A::Item>) -> SmallVec<A> {
if vec.capacity() <= Self::inline_capacity() {
// Cannot use Vec with smaller capacity
// because we use value of `Self::capacity` field as indicator.
unsafe {
let mut data = SmallVecData::<A>::from_inline(MaybeUninit::uninit());
let len = vec.len();
vec.set_len(0);
ptr::copy_nonoverlapping(vec.as_ptr(), data.inline_mut().as_ptr(), len);
SmallVec {
capacity: len,
data,
}
}
} else {
let (ptr, cap, len) = (vec.as_mut_ptr(), vec.capacity(), vec.len());
mem::forget(vec);
let ptr = NonNull::new(ptr)
// See docs: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_mut_ptr
.expect("Cannot be null by `Vec` invariant");
SmallVec {
capacity: cap,
data: SmallVecData::from_heap(ptr, len),
}
}
}
/// Constructs a new `SmallVec` on the stack from an `A` without
/// copying elements.
///
/// ```rust
/// use smallvec::SmallVec;
///
/// let buf = [1, 2, 3, 4, 5];
/// let small_vec: SmallVec<_> = SmallVec::from_buf(buf);
///
/// assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
/// ```
#[inline]
pub fn from_buf(buf: A) -> SmallVec<A> {
SmallVec {
capacity: A::size(),
data: SmallVecData::from_inline(MaybeUninit::new(buf)),
}
}
/// Constructs a new `SmallVec` on the stack from an `A` without
/// copying elements. Also sets the length, which must be less or
/// equal to the size of `buf`.
///
/// ```rust
/// use smallvec::SmallVec;
///
/// let buf = [1, 2, 3, 4, 5, 0, 0, 0];
/// let small_vec: SmallVec<_> = SmallVec::from_buf_and_len(buf, 5);
///
/// assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
/// ```
#[inline]
pub fn from_buf_and_len(buf: A, len: usize) -> SmallVec<A> {
assert!(len <= A::size());
unsafe { SmallVec::from_buf_and_len_unchecked(MaybeUninit::new(buf), len) }
}
/// Constructs a new `SmallVec` on the stack from an `A` without
/// copying elements. Also sets the length. The user is responsible
/// for ensuring that `len <= A::size()`.
///
/// ```rust
/// use smallvec::SmallVec;
/// use std::mem::MaybeUninit;
///
/// let buf = [1, 2, 3, 4, 5, 0, 0, 0];
/// let small_vec: SmallVec<_> = unsafe {
/// SmallVec::from_buf_and_len_unchecked(MaybeUninit::new(buf), 5)
/// };
///
/// assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
/// ```
#[inline]
pub unsafe fn from_buf_and_len_unchecked(buf: MaybeUninit<A>, len: usize) -> SmallVec<A> {
SmallVec {
capacity: len,
data: SmallVecData::from_inline(buf),
}
}
/// Sets the length of a vector.
///
/// This will explicitly set the size of the vector, without actually
/// modifying its buffers, so it is up to the caller to ensure that the
/// vector is actually the specified size.
pub unsafe fn set_len(&mut self, new_len: usize) {
let (_, len_ptr, _) = self.triple_mut();
*len_ptr = new_len;
}
/// The maximum number of elements this vector can hold inline
#[inline]
fn inline_capacity() -> usize {
if mem::size_of::<A::Item>() > 0 {
A::size()
} else {
// For zero-size items code like `ptr.add(offset)` always returns the same pointer.
// Therefore all items are at the same address,
// and any array size has capacity for infinitely many items.
// The capacity is limited by the bit width of the length field.
//
// `Vec` also does this:
// https://github.com/rust-lang/rust/blob/1.44.0/src/liballoc/raw_vec.rs#L186
//
// In our case, this also ensures that a smallvec of zero-size items never spills,
// and we never try to allocate zero bytes which `std::alloc::alloc` disallows.
core::usize::MAX
}
}
/// The maximum number of elements this vector can hold inline
#[inline]
pub fn inline_size(&self) -> usize {
Self::inline_capacity()
}
/// The number of elements stored in the vector
#[inline]
pub fn len(&self) -> usize {
self.triple().1
}
/// Returns `true` if the vector is empty
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
/// The number of items the vector can hold without reallocating
#[inline]
pub fn capacity(&self) -> usize {
self.triple().2
}
/// Returns a tuple with (data ptr, len, capacity)
/// Useful to get all `SmallVec` properties with a single check of the current storage variant.
#[inline]
fn triple(&self) -> (ConstNonNull<A::Item>, usize, usize) {
unsafe {
if self.spilled() {
let (ptr, len) = self.data.heap();
(ptr, len, self.capacity)
} else {
(self.data.inline(), self.capacity, Self::inline_capacity())
}
}
}
/// Returns a tuple with (data ptr, len ptr, capacity)
#[inline]
fn triple_mut(&mut self) -> (NonNull<A::Item>, &mut usize, usize) {
unsafe {
if self.spilled() {
let (ptr, len_ptr) = self.data.heap_mut();
(ptr, len_ptr, self.capacity)
} else {
(
self.data.inline_mut(),
&mut self.capacity,
Self::inline_capacity(),
)
}
}
}
/// Returns `true` if the data has spilled into a separate heap-allocated buffer.
#[inline]
pub fn spilled(&self) -> bool {
self.capacity > Self::inline_capacity()
}
/// Creates a draining iterator that removes the specified range in the vector
/// and yields the removed items.
///
/// Note 1: The element range is removed even if the iterator is only
/// partially consumed or not consumed at all.
///
/// Note 2: It is unspecified how many elements are removed from the vector
/// if the `Drain` value is leaked.
///
/// # Panics
///
/// Panics if the starting point is greater than the end point or if
/// the end point is greater than the length of the vector.
pub fn drain<R>(&mut self, range: R) -> Drain<'_, A>
where
R: RangeBounds<usize>,
{
use core::ops::Bound::*;
let len = self.len();
let start = match range.start_bound() {
Included(&n) => n,
Excluded(&n) => n.checked_add(1).expect("Range start out of bounds"),
Unbounded => 0,
};
let end = match range.end_bound() {
Included(&n) => n.checked_add(1).expect("Range end out of bounds"),
Excluded(&n) => n,
Unbounded => len,
};
assert!(start <= end);
assert!(end <= len);
unsafe {
self.set_len(start);
let range_slice = slice::from_raw_parts(self.as_ptr().add(start), end - start);
Drain {
tail_start: end,
tail_len: len - end,
iter: range_slice.iter(),
// Since self is a &mut, passing it to a function would invalidate the slice iterator.
vec: NonNull::new_unchecked(self as *mut _),
}
}
}
#[cfg(feature = "drain_filter")]
/// Creates an iterator which uses a closure to determine if an element should be removed.
///
/// If the closure returns true, the element is removed and yielded. If the closure returns
/// false, the element will remain in the vector and will not be yielded by the iterator.
///
/// Using this method is equivalent to the following code:
/// ```
/// # use smallvec::SmallVec;
/// # let some_predicate = |x: &mut i32| { *x == 2 || *x == 3 || *x == 6 };
/// # let mut vec: SmallVec<[i32; 8]> = SmallVec::from_slice(&[1i32, 2, 3, 4, 5, 6]);
/// let mut i = 0;
/// while i < vec.len() {
/// if some_predicate(&mut vec[i]) {
/// let val = vec.remove(i);
/// // your code here
/// } else {
/// i += 1;
/// }
/// }
///
/// # assert_eq!(vec, SmallVec::<[i32; 8]>::from_slice(&[1i32, 4, 5]));
/// ```
/// ///
/// But `drain_filter` is easier to use. `drain_filter` is also more efficient,
/// because it can backshift the elements of the array in bulk.
///
/// Note that `drain_filter` also lets you mutate every element in the filter closure,
/// regardless of whether you choose to keep or remove it.
///
/// # Examples
///
/// Splitting an array into evens and odds, reusing the original allocation:
///
/// ```
/// # use smallvec::SmallVec;
/// let mut numbers: SmallVec<[i32; 16]> = SmallVec::from_slice(&[1i32, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
///
/// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<SmallVec<[i32; 16]>>();
/// let odds = numbers;
///
/// assert_eq!(evens, SmallVec::<[i32; 16]>::from_slice(&[2i32, 4, 6, 8, 14]));
/// assert_eq!(odds, SmallVec::<[i32; 16]>::from_slice(&[1i32, 3, 5, 9, 11, 13, 15]));
/// ```
pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, A, F,>
where
F: FnMut(&mut A::Item) -> bool,
{
let old_len = self.len();
// Guard against us getting leaked (leak amplification)
unsafe {
self.set_len(0);
}
DrainFilter { vec: self, idx: 0, del: 0, old_len, pred: filter, panic_flag: false }
}
/// Append an item to the vector.
#[inline]
pub fn push(&mut self, value: A::Item) {
unsafe {
let (mut ptr, mut len, cap) = self.triple_mut();
if *len == cap {
self.reserve_one_unchecked();
let (heap_ptr, heap_len) = self.data.heap_mut();
ptr = heap_ptr;
len = heap_len;
}
ptr::write(ptr.as_ptr().add(*len), value);
*len += 1;
}
}
/// Remove an item from the end of the vector and return it, or None if empty.
#[inline]
pub fn pop(&mut self) -> Option<A::Item> {
unsafe {
let (ptr, len_ptr, _) = self.triple_mut();
let ptr: *const _ = ptr.as_ptr();
if *len_ptr == 0 {
return None;
}
let last_index = *len_ptr - 1;
*len_ptr = last_index;
Some(ptr::read(ptr.add(last_index)))
}
}
/// Moves all the elements of `other` into `self`, leaving `other` empty.
///
/// # Example
///
/// ```
/// # use smallvec::{SmallVec, smallvec};
/// let mut v0: SmallVec<[u8; 16]> = smallvec![1, 2, 3];
/// let mut v1: SmallVec<[u8; 32]> = smallvec![4, 5, 6];
/// v0.append(&mut v1);
/// assert_eq!(*v0, [1, 2, 3, 4, 5, 6]);
/// assert_eq!(*v1, []);
/// ```
pub fn append<B>(&mut self, other: &mut SmallVec<B>)
where
B: Array<Item = A::Item>,
{
self.extend(other.drain(..))
}
/// Re-allocate to set the capacity to `max(new_cap, inline_size())`.
///
/// Panics if `new_cap` is less than the vector's length
/// or if the capacity computation overflows `usize`.
pub fn grow(&mut self, new_cap: usize) {
infallible(self.try_grow(new_cap))
}
/// Re-allocate to set the capacity to `max(new_cap, inline_size())`.
///
/// Panics if `new_cap` is less than the vector's length
pub fn try_grow(&mut self, new_cap: usize) -> Result<(), CollectionAllocErr> {
unsafe {
let unspilled = !self.spilled();
let (ptr, &mut len, cap) = self.triple_mut();
assert!(new_cap >= len);
if new_cap <= Self::inline_capacity() {
if unspilled {
return Ok(());
}
self.data = SmallVecData::from_inline(MaybeUninit::uninit());
ptr::copy_nonoverlapping(ptr.as_ptr(), self.data.inline_mut().as_ptr(), len);
self.capacity = len;
deallocate(ptr, cap);
} else if new_cap != cap {
let layout = layout_array::<A::Item>(new_cap)?;
debug_assert!(layout.size() > 0);
let new_alloc;
if unspilled {
new_alloc = NonNull::new(alloc::alloc::alloc(layout))
.ok_or(CollectionAllocErr::AllocErr { layout })?
.cast();
ptr::copy_nonoverlapping(ptr.as_ptr(), new_alloc.as_ptr(), len);
} else {
// This should never fail since the same succeeded
// when previously allocating `ptr`.
let old_layout = layout_array::<A::Item>(cap)?;
let new_ptr =
alloc::alloc::realloc(ptr.as_ptr() as *mut u8, old_layout, layout.size());
new_alloc = NonNull::new(new_ptr)
.ok_or(CollectionAllocErr::AllocErr { layout })?
.cast();
}
self.data = SmallVecData::from_heap(new_alloc, len);
self.capacity = new_cap;
}
Ok(())
}
}
/// Reserve capacity for `additional` more elements to be inserted.
///
/// May reserve more space to avoid frequent reallocations.
///
/// Panics if the capacity computation overflows `usize`.
#[inline]
pub fn reserve(&mut self, additional: usize) {
infallible(self.try_reserve(additional))
}
/// Internal method used to grow in push() and insert(), where we know already we have to grow.
#[cold]
fn reserve_one_unchecked(&mut self) {
debug_assert_eq!(self.len(), self.capacity());
let new_cap = self.len()
.checked_add(1)
.and_then(usize::checked_next_power_of_two)
.expect("capacity overflow");
infallible(self.try_grow(new_cap))
}
/// Reserve capacity for `additional` more elements to be inserted.
///
/// May reserve more space to avoid frequent reallocations.
pub fn try_reserve(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {
// prefer triple_mut() even if triple() would work so that the optimizer removes duplicated
// calls to it from callers.
let (_, &mut len, cap) = self.triple_mut();
if cap - len >= additional {
return Ok(());
}
let new_cap = len
.checked_add(additional)
.and_then(usize::checked_next_power_of_two)
.ok_or(CollectionAllocErr::CapacityOverflow)?;
self.try_grow(new_cap)
}
/// Reserve the minimum capacity for `additional` more elements to be inserted.
///
/// Panics if the new capacity overflows `usize`.
pub fn reserve_exact(&mut self, additional: usize) {
infallible(self.try_reserve_exact(additional))
}
/// Reserve the minimum capacity for `additional` more elements to be inserted.
pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {
let (_, &mut len, cap) = self.triple_mut();
if cap - len >= additional {
return Ok(());
}
let new_cap = len
.checked_add(additional)
.ok_or(CollectionAllocErr::CapacityOverflow)?;
self.try_grow(new_cap)
}
/// Shrink the capacity of the vector as much as possible.
///
/// When possible, this will move data from an external heap buffer to the vector's inline
/// storage.
pub fn shrink_to_fit(&mut self) {
if !self.spilled() {
return;
}
let len = self.len();
if self.inline_size() >= len {
unsafe {
let (ptr, len) = self.data.heap();
self.data = SmallVecData::from_inline(MaybeUninit::uninit());
ptr::copy_nonoverlapping(ptr.as_ptr(), self.data.inline_mut().as_ptr(), len);
deallocate(ptr.0, self.capacity);
self.capacity = len;
}
} else if self.capacity() > len {
self.grow(len);
}
}
/// Shorten the vector, keeping the first `len` elements and dropping the rest.
///
/// If `len` is greater than or equal to the vector's current length, this has no
/// effect.
///
/// This does not re-allocate. If you want the vector's capacity to shrink, call
/// `shrink_to_fit` after truncating.
pub fn truncate(&mut self, len: usize) {
unsafe {
let (ptr, len_ptr, _) = self.triple_mut();
let ptr = ptr.as_ptr();
while len < *len_ptr {
let last_index = *len_ptr - 1;
*len_ptr = last_index;
ptr::drop_in_place(ptr.add(last_index));
}
}
}
/// Extracts a slice containing the entire vector.
///
/// Equivalent to `&s[..]`.
pub fn as_slice(&self) -> &[A::Item] {
self
}
/// Extracts a mutable slice of the entire vector.
///
/// Equivalent to `&mut s[..]`.
pub fn as_mut_slice(&mut self) -> &mut [A::Item] {
self
}
/// Remove the element at position `index`, replacing it with the last element.
///
/// This does not preserve ordering, but is O(1).
///
/// Panics if `index` is out of bounds.
#[inline]
pub fn swap_remove(&mut self, index: usize) -> A::Item {
let len = self.len();
self.swap(len - 1, index);
self.pop()
.unwrap_or_else(|| unsafe { unreachable_unchecked() })
}
/// Remove all elements from the vector.
#[inline]
pub fn clear(&mut self) {
self.truncate(0);
}
/// Remove and return the element at position `index`, shifting all elements after it to the
/// left.
///
/// Panics if `index` is out of bounds.
pub fn remove(&mut self, index: usize) -> A::Item {
unsafe {
let (ptr, len_ptr, _) = self.triple_mut();
let len = *len_ptr;
assert!(index < len);
*len_ptr = len - 1;
let ptr = ptr.as_ptr().add(index);
let item = ptr::read(ptr);
ptr::copy(ptr.add(1), ptr, len - index - 1);
item
}
}
/// Insert an element at position `index`, shifting all elements after it to the right.
///
/// Panics if `index > len`.
pub fn insert(&mut self, index: usize, element: A::Item) {
unsafe {
let (mut ptr, mut len_ptr, cap) = self.triple_mut();
if *len_ptr == cap {
self.reserve_one_unchecked();
let (heap_ptr, heap_len_ptr) = self.data.heap_mut();
ptr = heap_ptr;
len_ptr = heap_len_ptr;
}
let mut ptr = ptr.as_ptr();
let len = *len_ptr;
ptr = ptr.add(index);
if index < len {
ptr::copy(ptr, ptr.add(1), len - index);
} else if index == len {
// No elements need shifting.
} else {
panic!("index exceeds length");
}
*len_ptr = len + 1;
ptr::write(ptr, element);
}
}
/// Insert multiple elements at position `index`, shifting all following elements toward the
/// back.
pub fn insert_many<I: IntoIterator<Item = A::Item>>(&mut self, index: usize, iterable: I) {
let mut iter = iterable.into_iter();
if index == self.len() {
return self.extend(iter);
}
let (lower_size_bound, _) = iter.size_hint();
assert!(lower_size_bound <= core::isize::MAX as usize); // Ensure offset is indexable
assert!(index + lower_size_bound >= index); // Protect against overflow
let mut num_added = 0;
let old_len = self.len();
assert!(index <= old_len);
unsafe {
// Reserve space for `lower_size_bound` elements.
self.reserve(lower_size_bound);
let start = self.as_mut_ptr();
let ptr = start.add(index);
// Move the trailing elements.
ptr::copy(ptr, ptr.add(lower_size_bound), old_len - index);
// In case the iterator panics, don't double-drop the items we just copied above.
self.set_len(0);
let mut guard = DropOnPanic {
start,
skip: index..(index + lower_size_bound),
len: old_len + lower_size_bound,
};
// The set_len above invalidates the previous pointers, so we must re-create them.
let start = self.as_mut_ptr();
let ptr = start.add(index);
while num_added < lower_size_bound {
let element = match iter.next() {
Some(x) => x,
None => break,
};
let cur = ptr.add(num_added);
ptr::write(cur, element);
guard.skip.start += 1;
num_added += 1;
}
if num_added < lower_size_bound {
// Iterator provided fewer elements than the hint. Move the tail backward.
ptr::copy(
ptr.add(lower_size_bound),
ptr.add(num_added),
old_len - index,
);
}
// There are no more duplicate or uninitialized slots, so the guard is not needed.
self.set_len(old_len + num_added);
mem::forget(guard);
}
// Insert any remaining elements one-by-one.
for element in iter {
self.insert(index + num_added, element);
num_added += 1;
}
struct DropOnPanic<T> {
start: *mut T,
skip: Range<usize>, // Space we copied-out-of, but haven't written-to yet.
len: usize,
}
impl<T> Drop for DropOnPanic<T> {
fn drop(&mut self) {
for i in 0..self.len {
if !self.skip.contains(&i) {
unsafe {
ptr::drop_in_place(self.start.add(i));
}
}
}
}
}
}
/// Convert a `SmallVec` to a `Vec`, without reallocating if the `SmallVec` has already spilled onto
/// the heap.
pub fn into_vec(mut self) -> Vec<A::Item> {
if self.spilled() {
unsafe {
let (ptr, &mut len) = self.data.heap_mut();
let v = Vec::from_raw_parts(ptr.as_ptr(), len, self.capacity);
mem::forget(self);
v
}
} else {
self.into_iter().collect()
}
}
/// Converts a `SmallVec` into a `Box<[T]>` without reallocating if the `SmallVec` has already spilled
/// onto the heap.
///
/// Note that this will drop any excess capacity.
pub fn into_boxed_slice(self) -> Box<[A::Item]> {
self.into_vec().into_boxed_slice()
}
/// Convert the `SmallVec` into an `A` if possible. Otherwise return `Err(Self)`.
///
/// This method returns `Err(Self)` if the `SmallVec` is too short (and the `A` contains uninitialized elements),
/// or if the `SmallVec` is too long (and all the elements were spilled to the heap).
pub fn into_inner(self) -> Result<A, Self> {
if self.spilled() || self.len() != A::size() {
// Note: A::size, not Self::inline_capacity
Err(self)
} else {
unsafe {
let data = ptr::read(&self.data);
mem::forget(self);
Ok(data.into_inline().assume_init())
}
}
}
/// Retains only the elements specified by the predicate.
///
/// In other words, remove all elements `e` such that `f(&e)` returns `false`.
/// This method operates in place and preserves the order of the retained
/// elements.
pub fn retain<F: FnMut(&mut A::Item) -> bool>(&mut self, mut f: F) {
let mut del = 0;
let len = self.len();
for i in 0..len {
if !f(&mut self[i]) {
del += 1;
} else if del > 0 {
self.swap(i - del, i);
}
}
self.truncate(len - del);
}
/// Retains only the elements specified by the predicate.
///
/// This method is identical in behaviour to [`retain`]; it is included only
/// to maintain api-compatability with `std::Vec`, where the methods are
/// separate for historical reasons.
pub fn retain_mut<F: FnMut(&mut A::Item) -> bool>(&mut self, f: F) {
self.retain(f)
}
/// Removes consecutive duplicate elements.
pub fn dedup(&mut self)
where
A::Item: PartialEq<A::Item>,
{
self.dedup_by(|a, b| a == b);
}
/// Removes consecutive duplicate elements using the given equality relation.
pub fn dedup_by<F>(&mut self, mut same_bucket: F)
where
F: FnMut(&mut A::Item, &mut A::Item) -> bool,
{
// See the implementation of Vec::dedup_by in the
// standard library for an explanation of this algorithm.
let len = self.len();
if len <= 1 {
return;
}
let ptr = self.as_mut_ptr();
let mut w: usize = 1;
unsafe {
for r in 1..len {
let p_r = ptr.add(r);
let p_wm1 = ptr.add(w - 1);
if !same_bucket(&mut *p_r, &mut *p_wm1) {
if r != w {
let p_w = p_wm1.add(1);
mem::swap(&mut *p_r, &mut *p_w);
}
w += 1;
}
}
}
self.truncate(w);
}
/// Removes consecutive elements that map to the same key.
pub fn dedup_by_key<F, K>(&mut self, mut key: F)
where
F: FnMut(&mut A::Item) -> K,
K: PartialEq<K>,
{
self.dedup_by(|a, b| key(a) == key(b));
}
/// Resizes the `SmallVec` in-place so that `len` is equal to `new_len`.
///
/// If `new_len` is greater than `len`, the `SmallVec` is extended by the difference, with each
/// additional slot filled with the result of calling the closure `f`. The return values from `f`
/// will end up in the `SmallVec` in the order they have been generated.
///
/// If `new_len` is less than `len`, the `SmallVec` is simply truncated.
///
/// This method uses a closure to create new values on every push. If you'd rather `Clone` a given
/// value, use `resize`. If you want to use the `Default` trait to generate values, you can pass
/// `Default::default()` as the second argument.
///
/// Added for `std::vec::Vec` compatibility (added in Rust 1.33.0)
///
/// ```
/// # use smallvec::{smallvec, SmallVec};
/// let mut vec : SmallVec<[_; 4]> = smallvec![1, 2, 3];
/// vec.resize_with(5, Default::default);
/// assert_eq!(&*vec, &[1, 2, 3, 0, 0]);
///
/// let mut vec : SmallVec<[_; 4]> = smallvec![];
/// let mut p = 1;
/// vec.resize_with(4, || { p *= 2; p });
/// assert_eq!(&*vec, &[2, 4, 8, 16]);
/// ```
pub fn resize_with<F>(&mut self, new_len: usize, f: F)
where
F: FnMut() -> A::Item,
{
let old_len = self.len();
if old_len < new_len {
let mut f = f;
let additional = new_len - old_len;
self.reserve(additional);
for _ in 0..additional {
self.push(f());
}
} else if old_len > new_len {
self.truncate(new_len);
}
}
/// Creates a `SmallVec` directly from the raw components of another
/// `SmallVec`.
///
/// # Safety
///
/// This is highly unsafe, due to the number of invariants that aren't
/// checked:
///
/// * `ptr` needs to have been previously allocated via `SmallVec` for its
/// spilled storage (at least, it's highly likely to be incorrect if it
/// wasn't).
/// * `ptr`'s `A::Item` type needs to be the same size and alignment that
/// it was allocated with
/// * `length` needs to be less than or equal to `capacity`.
/// * `capacity` needs to be the capacity that the pointer was allocated
/// with.
///
/// Violating these may cause problems like corrupting the allocator's
/// internal data structures.
///
/// Additionally, `capacity` must be greater than the amount of inline
/// storage `A` has; that is, the new `SmallVec` must need to spill over
/// into heap allocated storage. This condition is asserted against.
///
/// The ownership of `ptr` is effectively transferred to the
/// `SmallVec` which may then deallocate, reallocate or change the
/// contents of memory pointed to by the pointer at will. Ensure
/// that nothing else uses the pointer after calling this
/// function.
///
/// # Examples
///
/// ```
/// # use smallvec::{smallvec, SmallVec};
/// use std::mem;
/// use std::ptr;
///
/// fn main() {
/// let mut v: SmallVec<[_; 1]> = smallvec![1, 2, 3];
///
/// // Pull out the important parts of `v`.
/// let p = v.as_mut_ptr();
/// let len = v.len();
/// let cap = v.capacity();
/// let spilled = v.spilled();
///
/// unsafe {
/// // Forget all about `v`. The heap allocation that stored the
/// // three values won't be deallocated.
/// mem::forget(v);
///
/// // Overwrite memory with [4, 5, 6].
/// //
/// // This is only safe if `spilled` is true! Otherwise, we are
/// // writing into the old `SmallVec`'s inline storage on the
/// // stack.
/// assert!(spilled);
/// for i in 0..len {
/// ptr::write(p.add(i), 4 + i);
/// }
///
/// // Put everything back together into a SmallVec with a different
/// // amount of inline storage, but which is still less than `cap`.
/// let rebuilt = SmallVec::<[_; 2]>::from_raw_parts(p, len, cap);
/// assert_eq!(&*rebuilt, &[4, 5, 6]);
/// }
/// }
#[inline]
pub unsafe fn from_raw_parts(ptr: *mut A::Item, length: usize, capacity: usize) -> SmallVec<A> {
// SAFETY: We require caller to provide same ptr as we alloc
// and we never alloc null pointer.
let ptr = unsafe {
debug_assert!(!ptr.is_null(), "Called `from_raw_parts` with null pointer.");
NonNull::new_unchecked(ptr)
};
assert!(capacity > Self::inline_capacity());
SmallVec {
capacity,
data: SmallVecData::from_heap(ptr, length),
}
}
/// Returns a raw pointer to the vector's buffer.
pub fn as_ptr(&self) -> *const A::Item {
// We shadow the slice method of the same name to avoid going through
// `deref`, which creates an intermediate reference that may place
// additional safety constraints on the contents of the slice.
self.triple().0.as_ptr()
}
/// Returns a raw mutable pointer to the vector's buffer.
pub fn as_mut_ptr(&mut self) -> *mut A::Item {
// We shadow the slice method of the same name to avoid going through
// `deref_mut`, which creates an intermediate reference that may place
// additional safety constraints on the contents of the slice.
self.triple_mut().0.as_ptr()
}
}
impl<A: Array> SmallVec<A>
where
A::Item: Copy,
{
/// Copy the elements from a slice into a new `SmallVec`.
///
/// For slices of `Copy` types, this is more efficient than `SmallVec::from(slice)`.
pub fn from_slice(slice: &[A::Item]) -> Self {
let len = slice.len();
if len <= Self::inline_capacity() {
SmallVec {
capacity: len,
data: SmallVecData::from_inline(unsafe {
let mut data: MaybeUninit<A> = MaybeUninit::uninit();
ptr::copy_nonoverlapping(
slice.as_ptr(),
data.as_mut_ptr() as *mut A::Item,
len,
);
data
}),
}
} else {
let mut b = slice.to_vec();
let cap = b.capacity();
let ptr = NonNull::new(b.as_mut_ptr()).expect("Vec always contain non null pointers.");
mem::forget(b);
SmallVec {
capacity: cap,
data: SmallVecData::from_heap(ptr, len),
}
}
}
/// Copy elements from a slice into the vector at position `index`, shifting any following
/// elements toward the back.
///
/// For slices of `Copy` types, this is more efficient than `insert`.
#[inline]
pub fn insert_from_slice(&mut self, index: usize, slice: &[A::Item]) {
self.reserve(slice.len());
let len = self.len();
assert!(index <= len);
unsafe {
let slice_ptr = slice.as_ptr();
let ptr = self.as_mut_ptr().add(index);
ptr::copy(ptr, ptr.add(slice.len()), len - index);
ptr::copy_nonoverlapping(slice_ptr, ptr, slice.len());
self.set_len(len + slice.len());
}
}
/// Copy elements from a slice and append them to the vector.
///
/// For slices of `Copy` types, this is more efficient than `extend`.
#[inline]
pub fn extend_from_slice(&mut self, slice: &[A::Item]) {
let len = self.len();
self.insert_from_slice(len, slice);
}
}
impl<A: Array> SmallVec<A>
where
A::Item: Clone,
{
/// Resizes the vector so that its length is equal to `len`.
///
/// If `len` is less than the current length, the vector simply truncated.
///
/// If `len` is greater than the current length, `value` is appended to the
/// vector until its length equals `len`.
pub fn resize(&mut self, len: usize, value: A::Item) {
let old_len = self.len();
if len > old_len {
self.extend(repeat(value).take(len - old_len));
} else {
self.truncate(len);
}
}
/// Creates a `SmallVec` with `n` copies of `elem`.
/// ```
/// use smallvec::SmallVec;
///
/// let v = SmallVec::<[char; 128]>::from_elem('d', 2);
/// assert_eq!(v, SmallVec::from_buf(['d', 'd']));
/// ```
pub fn from_elem(elem: A::Item, n: usize) -> Self {
if n > Self::inline_capacity() {
vec![elem; n].into()
} else {
let mut v = SmallVec::<A>::new();
unsafe {
let (ptr, len_ptr, _) = v.triple_mut();
let ptr = ptr.as_ptr();
let mut local_len = SetLenOnDrop::new(len_ptr);
for i in 0..n {
::core::ptr::write(ptr.add(i), elem.clone());
local_len.increment_len(1);
}
}
v
}
}
}
impl<A: Array> ops::Deref for SmallVec<A> {
type Target = [A::Item];
#[inline]
fn deref(&self) -> &[A::Item] {
unsafe {
let (ptr, len, _) = self.triple();
slice::from_raw_parts(ptr.as_ptr(), len)
}
}
}
impl<A: Array> ops::DerefMut for SmallVec<A> {
#[inline]
fn deref_mut(&mut self) -> &mut [A::Item] {
unsafe {
let (ptr, &mut len, _) = self.triple_mut();
slice::from_raw_parts_mut(ptr.as_ptr(), len)
}
}
}
impl<A: Array> AsRef<[A::Item]> for SmallVec<A> {
#[inline]
fn as_ref(&self) -> &[A::Item] {
self
}
}
impl<A: Array> AsMut<[A::Item]> for SmallVec<A> {
#[inline]
fn as_mut(&mut self) -> &mut [A::Item] {
self
}
}
impl<A: Array> Borrow<[A::Item]> for SmallVec<A> {
#[inline]
fn borrow(&self) -> &[A::Item] {
self
}
}
impl<A: Array> BorrowMut<[A::Item]> for SmallVec<A> {
#[inline]
fn borrow_mut(&mut self) -> &mut [A::Item] {
self
}
}
#[cfg(feature = "write")]
#[cfg_attr(docsrs, doc(cfg(feature = "write")))]
impl<A: Array<Item = u8>> io::Write for SmallVec<A> {
#[inline]
fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
self.extend_from_slice(buf);
Ok(buf.len())
}
#[inline]
fn write_all(&mut self, buf: &[u8]) -> io::Result<()> {
self.extend_from_slice(buf);
Ok(())
}
#[inline]
fn flush(&mut self) -> io::Result<()> {
Ok(())
}
}
#[cfg(feature = "serde")]
#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
impl<A: Array> Serialize for SmallVec<A>
where
A::Item: Serialize,
{
fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
let mut state = serializer.serialize_seq(Some(self.len()))?;
for item in self {
state.serialize_element(&item)?;
}
state.end()
}
}
#[cfg(feature = "serde")]
#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
impl<'de, A: Array> Deserialize<'de> for SmallVec<A>
where
A::Item: Deserialize<'de>,
{
fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
deserializer.deserialize_seq(SmallVecVisitor {
phantom: PhantomData,
})
}
}
#[cfg(feature = "serde")]
struct SmallVecVisitor<A> {
--> --------------------
--> maximum size reached
--> --------------------
[ Dauer der Verarbeitung: 0.47 Sekunden
(vorverarbeitet)
]
|
2026-04-02
|
|
|
|
|
