aboutsummaryrefslogtreecommitdiff
path: root/vendor/smallvec/src
diff options
context:
space:
mode:
authorValentin Popov <valentin@popov.link>2024-07-19 15:37:58 +0300
committerValentin Popov <valentin@popov.link>2024-07-19 15:37:58 +0300
commita990de90fe41456a23e58bd087d2f107d321f3a1 (patch)
tree15afc392522a9e85dc3332235e311b7d39352ea9 /vendor/smallvec/src
parent3d48cd3f81164bbfc1a755dc1d4a9a02f98c8ddd (diff)
downloadfparkan-a990de90fe41456a23e58bd087d2f107d321f3a1.tar.xz
fparkan-a990de90fe41456a23e58bd087d2f107d321f3a1.zip
Deleted vendor folder
Diffstat (limited to 'vendor/smallvec/src')
-rw-r--r--vendor/smallvec/src/arbitrary.rs19
-rw-r--r--vendor/smallvec/src/lib.rs2457
-rw-r--r--vendor/smallvec/src/specialization.rs19
-rw-r--r--vendor/smallvec/src/tests.rs1013
4 files changed, 0 insertions, 3508 deletions
diff --git a/vendor/smallvec/src/arbitrary.rs b/vendor/smallvec/src/arbitrary.rs
deleted file mode 100644
index cbdfcb0..0000000
--- a/vendor/smallvec/src/arbitrary.rs
+++ /dev/null
@@ -1,19 +0,0 @@
-use crate::{Array, SmallVec};
-use arbitrary::{Arbitrary, Unstructured};
-
-impl<'a, A: Array> Arbitrary<'a> for SmallVec<A>
-where
- <A as Array>::Item: Arbitrary<'a>,
-{
- fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
- u.arbitrary_iter()?.collect()
- }
-
- fn arbitrary_take_rest(u: Unstructured<'a>) -> arbitrary::Result<Self> {
- u.arbitrary_take_rest_iter()?.collect()
- }
-
- fn size_hint(depth: usize) -> (usize, Option<usize>) {
- arbitrary::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
- }
-}
diff --git a/vendor/smallvec/src/lib.rs b/vendor/smallvec/src/lib.rs
deleted file mode 100644
index f9a6c8a..0000000
--- a/vendor/smallvec/src/lib.rs
+++ /dev/null
@@ -1,2457 +0,0 @@
-// 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 back
-//! 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> {
- phantom: PhantomData<A>,
-}
-
-#[cfg(feature = "serde")]
-impl<'de, A: Array> Visitor<'de> for SmallVecVisitor<A>
-where
- A::Item: Deserialize<'de>,
-{
- type Value = SmallVec<A>;
-
- fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
- formatter.write_str("a sequence")
- }
-
- fn visit_seq<B>(self, mut seq: B) -> Result<Self::Value, B::Error>
- where
- B: SeqAccess<'de>,
- {
- use serde::de::Error;
- let len = seq.size_hint().unwrap_or(0);
- let mut values = SmallVec::new();
- values.try_reserve(len).map_err(B::Error::custom)?;
-
- while let Some(value) = seq.next_element()? {
- values.push(value);
- }
-
- Ok(values)
- }
-}
-
-#[cfg(feature = "specialization")]
-trait SpecFrom<A: Array, S> {
- fn spec_from(slice: S) -> SmallVec<A>;
-}
-
-#[cfg(feature = "specialization")]
-mod specialization;
-
-#[cfg(feature = "arbitrary")]
-mod arbitrary;
-
-#[cfg(feature = "specialization")]
-impl<'a, A: Array> SpecFrom<A, &'a [A::Item]> for SmallVec<A>
-where
- A::Item: Copy,
-{
- #[inline]
- fn spec_from(slice: &'a [A::Item]) -> SmallVec<A> {
- SmallVec::from_slice(slice)
- }
-}
-
-impl<'a, A: Array> From<&'a [A::Item]> for SmallVec<A>
-where
- A::Item: Clone,
-{
- #[cfg(not(feature = "specialization"))]
- #[inline]
- fn from(slice: &'a [A::Item]) -> SmallVec<A> {
- slice.iter().cloned().collect()
- }
-
- #[cfg(feature = "specialization")]
- #[inline]
- fn from(slice: &'a [A::Item]) -> SmallVec<A> {
- SmallVec::spec_from(slice)
- }
-}
-
-impl<A: Array> From<Vec<A::Item>> for SmallVec<A> {
- #[inline]
- fn from(vec: Vec<A::Item>) -> SmallVec<A> {
- SmallVec::from_vec(vec)
- }
-}
-
-impl<A: Array> From<A> for SmallVec<A> {
- #[inline]
- fn from(array: A) -> SmallVec<A> {
- SmallVec::from_buf(array)
- }
-}
-
-impl<A: Array, I: SliceIndex<[A::Item]>> ops::Index<I> for SmallVec<A> {
- type Output = I::Output;
-
- fn index(&self, index: I) -> &I::Output {
- &(**self)[index]
- }
-}
-
-impl<A: Array, I: SliceIndex<[A::Item]>> ops::IndexMut<I> for SmallVec<A> {
- fn index_mut(&mut self, index: I) -> &mut I::Output {
- &mut (&mut **self)[index]
- }
-}
-
-#[allow(deprecated)]
-impl<A: Array> ExtendFromSlice<A::Item> for SmallVec<A>
-where
- A::Item: Copy,
-{
- fn extend_from_slice(&mut self, other: &[A::Item]) {
- SmallVec::extend_from_slice(self, other)
- }
-}
-
-impl<A: Array> FromIterator<A::Item> for SmallVec<A> {
- #[inline]
- fn from_iter<I: IntoIterator<Item = A::Item>>(iterable: I) -> SmallVec<A> {
- let mut v = SmallVec::new();
- v.extend(iterable);
- v
- }
-}
-
-impl<A: Array> Extend<A::Item> for SmallVec<A> {
- fn extend<I: IntoIterator<Item = A::Item>>(&mut self, iterable: I) {
- let mut iter = iterable.into_iter();
- let (lower_size_bound, _) = iter.size_hint();
- self.reserve(lower_size_bound);
-
- unsafe {
- let (ptr, len_ptr, cap) = self.triple_mut();
- let ptr = ptr.as_ptr();
- let mut len = SetLenOnDrop::new(len_ptr);
- while len.get() < cap {
- if let Some(out) = iter.next() {
- ptr::write(ptr.add(len.get()), out);
- len.increment_len(1);
- } else {
- return;
- }
- }
- }
-
- for elem in iter {
- self.push(elem);
- }
- }
-}
-
-impl<A: Array> fmt::Debug for SmallVec<A>
-where
- A::Item: fmt::Debug,
-{
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- f.debug_list().entries(self.iter()).finish()
- }
-}
-
-impl<A: Array> Default for SmallVec<A> {
- #[inline]
- fn default() -> SmallVec<A> {
- SmallVec::new()
- }
-}
-
-#[cfg(feature = "may_dangle")]
-unsafe impl<#[may_dangle] A: Array> Drop for SmallVec<A> {
- fn drop(&mut self) {
- unsafe {
- if self.spilled() {
- let (ptr, &mut len) = self.data.heap_mut();
- Vec::from_raw_parts(ptr.as_ptr(), len, self.capacity);
- } else {
- ptr::drop_in_place(&mut self[..]);
- }
- }
- }
-}
-
-#[cfg(not(feature = "may_dangle"))]
-impl<A: Array> Drop for SmallVec<A> {
- fn drop(&mut self) {
- unsafe {
- if self.spilled() {
- let (ptr, &mut len) = self.data.heap_mut();
- drop(Vec::from_raw_parts(ptr.as_ptr(), len, self.capacity));
- } else {
- ptr::drop_in_place(&mut self[..]);
- }
- }
- }
-}
-
-impl<A: Array> Clone for SmallVec<A>
-where
- A::Item: Clone,
-{
- #[inline]
- fn clone(&self) -> SmallVec<A> {
- SmallVec::from(self.as_slice())
- }
-
- fn clone_from(&mut self, source: &Self) {
- // Inspired from `impl Clone for Vec`.
-
- // drop anything that will not be overwritten
- self.truncate(source.len());
-
- // self.len <= other.len due to the truncate above, so the
- // slices here are always in-bounds.
- let (init, tail) = source.split_at(self.len());
-
- // reuse the contained values' allocations/resources.
- self.clone_from_slice(init);
- self.extend(tail.iter().cloned());
- }
-}
-
-impl<A: Array, B: Array> PartialEq<SmallVec<B>> for SmallVec<A>
-where
- A::Item: PartialEq<B::Item>,
-{
- #[inline]
- fn eq(&self, other: &SmallVec<B>) -> bool {
- self[..] == other[..]
- }
-}
-
-impl<A: Array> Eq for SmallVec<A> where A::Item: Eq {}
-
-impl<A: Array> PartialOrd for SmallVec<A>
-where
- A::Item: PartialOrd,
-{
- #[inline]
- fn partial_cmp(&self, other: &SmallVec<A>) -> Option<cmp::Ordering> {
- PartialOrd::partial_cmp(&**self, &**other)
- }
-}
-
-impl<A: Array> Ord for SmallVec<A>
-where
- A::Item: Ord,
-{
- #[inline]
- fn cmp(&self, other: &SmallVec<A>) -> cmp::Ordering {
- Ord::cmp(&**self, &**other)
- }
-}
-
-impl<A: Array> Hash for SmallVec<A>
-where
- A::Item: Hash,
-{
- fn hash<H: Hasher>(&self, state: &mut H) {
- (**self).hash(state)
- }
-}
-
-unsafe impl<A: Array> Send for SmallVec<A> where A::Item: Send {}
-
-/// An iterator that consumes a `SmallVec` and yields its items by value.
-///
-/// Returned from [`SmallVec::into_iter`][1].
-///
-/// [1]: struct.SmallVec.html#method.into_iter
-pub struct IntoIter<A: Array> {
- data: SmallVec<A>,
- current: usize,
- end: usize,
-}
-
-impl<A: Array> fmt::Debug for IntoIter<A>
-where
- A::Item: fmt::Debug,
-{
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
- }
-}
-
-impl<A: Array + Clone> Clone for IntoIter<A>
-where
- A::Item: Clone,
-{
- fn clone(&self) -> IntoIter<A> {
- SmallVec::from(self.as_slice()).into_iter()
- }
-}
-
-impl<A: Array> Drop for IntoIter<A> {
- fn drop(&mut self) {
- for _ in self {}
- }
-}
-
-impl<A: Array> Iterator for IntoIter<A> {
- type Item = A::Item;
-
- #[inline]
- fn next(&mut self) -> Option<A::Item> {
- if self.current == self.end {
- None
- } else {
- unsafe {
- let current = self.current;
- self.current += 1;
- Some(ptr::read(self.data.as_ptr().add(current)))
- }
- }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let size = self.end - self.current;
- (size, Some(size))
- }
-}
-
-impl<A: Array> DoubleEndedIterator for IntoIter<A> {
- #[inline]
- fn next_back(&mut self) -> Option<A::Item> {
- if self.current == self.end {
- None
- } else {
- unsafe {
- self.end -= 1;
- Some(ptr::read(self.data.as_ptr().add(self.end)))
- }
- }
- }
-}
-
-impl<A: Array> ExactSizeIterator for IntoIter<A> {}
-impl<A: Array> FusedIterator for IntoIter<A> {}
-
-impl<A: Array> IntoIter<A> {
- /// Returns the remaining items of this iterator as a slice.
- pub fn as_slice(&self) -> &[A::Item] {
- let len = self.end - self.current;
- unsafe { core::slice::from_raw_parts(self.data.as_ptr().add(self.current), len) }
- }
-
- /// Returns the remaining items of this iterator as a mutable slice.
- pub fn as_mut_slice(&mut self) -> &mut [A::Item] {
- let len = self.end - self.current;
- unsafe { core::slice::from_raw_parts_mut(self.data.as_mut_ptr().add(self.current), len) }
- }
-}
-
-impl<A: Array> IntoIterator for SmallVec<A> {
- type IntoIter = IntoIter<A>;
- type Item = A::Item;
- fn into_iter(mut self) -> Self::IntoIter {
- unsafe {
- // Set SmallVec len to zero as `IntoIter` drop handles dropping of the elements
- let len = self.len();
- self.set_len(0);
- IntoIter {
- data: self,
- current: 0,
- end: len,
- }
- }
- }
-}
-
-impl<'a, A: Array> IntoIterator for &'a SmallVec<A> {
- type IntoIter = slice::Iter<'a, A::Item>;
- type Item = &'a A::Item;
- fn into_iter(self) -> Self::IntoIter {
- self.iter()
- }
-}
-
-impl<'a, A: Array> IntoIterator for &'a mut SmallVec<A> {
- type IntoIter = slice::IterMut<'a, A::Item>;
- type Item = &'a mut A::Item;
- fn into_iter(self) -> Self::IntoIter {
- self.iter_mut()
- }
-}
-
-/// Types that can be used as the backing store for a [`SmallVec`].
-pub unsafe trait Array {
- /// The type of the array's elements.
- type Item;
- /// Returns the number of items the array can hold.
- fn size() -> usize;
-}
-
-/// Set the length of the vec when the `SetLenOnDrop` value goes out of scope.
-///
-/// Copied from <https://github.com/rust-lang/rust/pull/36355>
-struct SetLenOnDrop<'a> {
- len: &'a mut usize,
- local_len: usize,
-}
-
-impl<'a> SetLenOnDrop<'a> {
- #[inline]
- fn new(len: &'a mut usize) -> Self {
- SetLenOnDrop {
- local_len: *len,
- len,
- }
- }
-
- #[inline]
- fn get(&self) -> usize {
- self.local_len
- }
-
- #[inline]
- fn increment_len(&mut self, increment: usize) {
- self.local_len += increment;
- }
-}
-
-impl<'a> Drop for SetLenOnDrop<'a> {
- #[inline]
- fn drop(&mut self) {
- *self.len = self.local_len;
- }
-}
-
-#[cfg(feature = "const_new")]
-impl<T, const N: usize> SmallVec<[T; N]> {
- /// Construct an empty vector.
- ///
- /// 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.
- #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
- #[inline]
- pub const fn new_const() -> Self {
- SmallVec {
- capacity: 0,
- data: SmallVecData::from_const(MaybeUninit::uninit()),
- }
- }
-
- /// The array passed as an argument is moved to be an inline version of `SmallVec`.
- ///
- /// 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.
- #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
- #[inline]
- pub const fn from_const(items: [T; N]) -> Self {
- SmallVec {
- capacity: N,
- data: SmallVecData::from_const(MaybeUninit::new(items)),
- }
- }
-}
-
-#[cfg(feature = "const_generics")]
-#[cfg_attr(docsrs, doc(cfg(feature = "const_generics")))]
-unsafe impl<T, const N: usize> Array for [T; N] {
- type Item = T;
- #[inline]
- fn size() -> usize {
- N
- }
-}
-
-#[cfg(not(feature = "const_generics"))]
-macro_rules! impl_array(
- ($($size:expr),+) => {
- $(
- unsafe impl<T> Array for [T; $size] {
- type Item = T;
- #[inline]
- fn size() -> usize { $size }
- }
- )+
- }
-);
-
-#[cfg(not(feature = "const_generics"))]
-impl_array!(
- 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,
- 26, 27, 28, 29, 30, 31, 32, 36, 0x40, 0x60, 0x80, 0x100, 0x200, 0x400, 0x600, 0x800, 0x1000,
- 0x2000, 0x4000, 0x6000, 0x8000, 0x10000, 0x20000, 0x40000, 0x60000, 0x80000, 0x10_0000
-);
-
-/// Convenience trait for constructing a `SmallVec`
-pub trait ToSmallVec<A: Array> {
- /// Construct a new `SmallVec` from a slice.
- fn to_smallvec(&self) -> SmallVec<A>;
-}
-
-impl<A: Array> ToSmallVec<A> for [A::Item]
-where
- A::Item: Copy,
-{
- #[inline]
- fn to_smallvec(&self) -> SmallVec<A> {
- SmallVec::from_slice(self)
- }
-}
-
-// Immutable counterpart for `NonNull<T>`.
-#[repr(transparent)]
-struct ConstNonNull<T>(NonNull<T>);
-
-impl<T> ConstNonNull<T> {
- #[inline]
- fn new(ptr: *const T) -> Option<Self> {
- NonNull::new(ptr as *mut T).map(Self)
- }
- #[inline]
- fn as_ptr(self) -> *const T {
- self.0.as_ptr()
- }
-}
-
-impl<T> Clone for ConstNonNull<T> {
- #[inline]
- fn clone(&self) -> Self {
- *self
- }
-}
-
-impl<T> Copy for ConstNonNull<T> {}
diff --git a/vendor/smallvec/src/specialization.rs b/vendor/smallvec/src/specialization.rs
deleted file mode 100644
index 658fa77..0000000
--- a/vendor/smallvec/src/specialization.rs
+++ /dev/null
@@ -1,19 +0,0 @@
-// 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.
-
-//! Implementations that require `default fn`.
-
-use super::{Array, SmallVec, SpecFrom};
-
-impl<'a, A: Array> SpecFrom<A, &'a [A::Item]> for SmallVec<A>
-where
- A::Item: Clone,
-{
- #[inline]
- default fn spec_from(slice: &'a [A::Item]) -> SmallVec<A> {
- slice.into_iter().cloned().collect()
- }
-}
diff --git a/vendor/smallvec/src/tests.rs b/vendor/smallvec/src/tests.rs
deleted file mode 100644
index 936ad6f..0000000
--- a/vendor/smallvec/src/tests.rs
+++ /dev/null
@@ -1,1013 +0,0 @@
-use crate::{smallvec, SmallVec};
-
-use std::iter::FromIterator;
-
-use alloc::borrow::ToOwned;
-use alloc::boxed::Box;
-use alloc::rc::Rc;
-use alloc::{vec, vec::Vec};
-
-#[test]
-pub fn test_zero() {
- let mut v = SmallVec::<[_; 0]>::new();
- assert!(!v.spilled());
- v.push(0usize);
- assert!(v.spilled());
- assert_eq!(&*v, &[0]);
-}
-
-// We heap allocate all these strings so that double frees will show up under valgrind.
-
-#[test]
-pub fn test_inline() {
- let mut v = SmallVec::<[_; 16]>::new();
- v.push("hello".to_owned());
- v.push("there".to_owned());
- assert_eq!(&*v, &["hello".to_owned(), "there".to_owned(),][..]);
-}
-
-#[test]
-pub fn test_spill() {
- let mut v = SmallVec::<[_; 2]>::new();
- v.push("hello".to_owned());
- assert_eq!(v[0], "hello");
- v.push("there".to_owned());
- v.push("burma".to_owned());
- assert_eq!(v[0], "hello");
- v.push("shave".to_owned());
- assert_eq!(
- &*v,
- &[
- "hello".to_owned(),
- "there".to_owned(),
- "burma".to_owned(),
- "shave".to_owned(),
- ][..]
- );
-}
-
-#[test]
-pub fn test_double_spill() {
- let mut v = SmallVec::<[_; 2]>::new();
- v.push("hello".to_owned());
- v.push("there".to_owned());
- v.push("burma".to_owned());
- v.push("shave".to_owned());
- v.push("hello".to_owned());
- v.push("there".to_owned());
- v.push("burma".to_owned());
- v.push("shave".to_owned());
- assert_eq!(
- &*v,
- &[
- "hello".to_owned(),
- "there".to_owned(),
- "burma".to_owned(),
- "shave".to_owned(),
- "hello".to_owned(),
- "there".to_owned(),
- "burma".to_owned(),
- "shave".to_owned(),
- ][..]
- );
-}
-
-// https://github.com/servo/rust-smallvec/issues/4
-#[test]
-fn issue_4() {
- SmallVec::<[Box<u32>; 2]>::new();
-}
-
-// https://github.com/servo/rust-smallvec/issues/5
-#[test]
-fn issue_5() {
- assert!(Some(SmallVec::<[&u32; 2]>::new()).is_some());
-}
-
-#[test]
-fn test_with_capacity() {
- let v: SmallVec<[u8; 3]> = SmallVec::with_capacity(1);
- assert!(v.is_empty());
- assert!(!v.spilled());
- assert_eq!(v.capacity(), 3);
-
- let v: SmallVec<[u8; 3]> = SmallVec::with_capacity(10);
- assert!(v.is_empty());
- assert!(v.spilled());
- assert_eq!(v.capacity(), 10);
-}
-
-#[test]
-fn drain() {
- let mut v: SmallVec<[u8; 2]> = SmallVec::new();
- v.push(3);
- assert_eq!(v.drain(..).collect::<Vec<_>>(), &[3]);
-
- // spilling the vec
- v.push(3);
- v.push(4);
- v.push(5);
- let old_capacity = v.capacity();
- assert_eq!(v.drain(1..).collect::<Vec<_>>(), &[4, 5]);
- // drain should not change the capacity
- assert_eq!(v.capacity(), old_capacity);
-
- // Exercise the tail-shifting code when in the inline state
- // This has the potential to produce UB due to aliasing
- let mut v: SmallVec<[u8; 2]> = SmallVec::new();
- v.push(1);
- v.push(2);
- assert_eq!(v.drain(..1).collect::<Vec<_>>(), &[1]);
-}
-
-#[test]
-fn drain_rev() {
- let mut v: SmallVec<[u8; 2]> = SmallVec::new();
- v.push(3);
- assert_eq!(v.drain(..).rev().collect::<Vec<_>>(), &[3]);
-
- // spilling the vec
- v.push(3);
- v.push(4);
- v.push(5);
- assert_eq!(v.drain(..).rev().collect::<Vec<_>>(), &[5, 4, 3]);
-}
-
-#[test]
-fn drain_forget() {
- let mut v: SmallVec<[u8; 1]> = smallvec![0, 1, 2, 3, 4, 5, 6, 7];
- std::mem::forget(v.drain(2..5));
- assert_eq!(v.len(), 2);
-}
-
-#[test]
-fn into_iter() {
- let mut v: SmallVec<[u8; 2]> = SmallVec::new();
- v.push(3);
- assert_eq!(v.into_iter().collect::<Vec<_>>(), &[3]);
-
- // spilling the vec
- let mut v: SmallVec<[u8; 2]> = SmallVec::new();
- v.push(3);
- v.push(4);
- v.push(5);
- assert_eq!(v.into_iter().collect::<Vec<_>>(), &[3, 4, 5]);
-}
-
-#[test]
-fn into_iter_rev() {
- let mut v: SmallVec<[u8; 2]> = SmallVec::new();
- v.push(3);
- assert_eq!(v.into_iter().rev().collect::<Vec<_>>(), &[3]);
-
- // spilling the vec
- let mut v: SmallVec<[u8; 2]> = SmallVec::new();
- v.push(3);
- v.push(4);
- v.push(5);
- assert_eq!(v.into_iter().rev().collect::<Vec<_>>(), &[5, 4, 3]);
-}
-
-#[test]
-fn into_iter_drop() {
- use std::cell::Cell;
-
- struct DropCounter<'a>(&'a Cell<i32>);
-
- impl<'a> Drop for DropCounter<'a> {
- fn drop(&mut self) {
- self.0.set(self.0.get() + 1);
- }
- }
-
- {
- let cell = Cell::new(0);
- let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
- v.push(DropCounter(&cell));
- v.into_iter();
- assert_eq!(cell.get(), 1);
- }
-
- {
- let cell = Cell::new(0);
- let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
- v.push(DropCounter(&cell));
- v.push(DropCounter(&cell));
- assert!(v.into_iter().next().is_some());
- assert_eq!(cell.get(), 2);
- }
-
- {
- let cell = Cell::new(0);
- let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
- v.push(DropCounter(&cell));
- v.push(DropCounter(&cell));
- v.push(DropCounter(&cell));
- assert!(v.into_iter().next().is_some());
- assert_eq!(cell.get(), 3);
- }
- {
- let cell = Cell::new(0);
- let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
- v.push(DropCounter(&cell));
- v.push(DropCounter(&cell));
- v.push(DropCounter(&cell));
- {
- let mut it = v.into_iter();
- assert!(it.next().is_some());
- assert!(it.next_back().is_some());
- }
- assert_eq!(cell.get(), 3);
- }
-}
-
-#[test]
-fn test_capacity() {
- let mut v: SmallVec<[u8; 2]> = SmallVec::new();
- v.reserve(1);
- assert_eq!(v.capacity(), 2);
- assert!(!v.spilled());
-
- v.reserve_exact(0x100);
- assert!(v.capacity() >= 0x100);
-
- v.push(0);
- v.push(1);
- v.push(2);
- v.push(3);
-
- v.shrink_to_fit();
- assert!(v.capacity() < 0x100);
-}
-
-#[test]
-fn test_truncate() {
- let mut v: SmallVec<[Box<u8>; 8]> = SmallVec::new();
-
- for x in 0..8 {
- v.push(Box::new(x));
- }
- v.truncate(4);
-
- assert_eq!(v.len(), 4);
- assert!(!v.spilled());
-
- assert_eq!(*v.swap_remove(1), 1);
- assert_eq!(*v.remove(1), 3);
- v.insert(1, Box::new(3));
-
- assert_eq!(&v.iter().map(|v| **v).collect::<Vec<_>>(), &[0, 3, 2]);
-}
-
-#[test]
-fn test_insert_many() {
- let mut v: SmallVec<[u8; 8]> = SmallVec::new();
- for x in 0..4 {
- v.push(x);
- }
- assert_eq!(v.len(), 4);
- v.insert_many(1, [5, 6].iter().cloned());
- assert_eq!(
- &v.iter().map(|v| *v).collect::<Vec<_>>(),
- &[0, 5, 6, 1, 2, 3]
- );
-}
-
-struct MockHintIter<T: Iterator> {
- x: T,
- hint: usize,
-}
-impl<T: Iterator> Iterator for MockHintIter<T> {
- type Item = T::Item;
- fn next(&mut self) -> Option<Self::Item> {
- self.x.next()
- }
- fn size_hint(&self) -> (usize, Option<usize>) {
- (self.hint, None)
- }
-}
-
-#[test]
-fn test_insert_many_short_hint() {
- let mut v: SmallVec<[u8; 8]> = SmallVec::new();
- for x in 0..4 {
- v.push(x);
- }
- assert_eq!(v.len(), 4);
- v.insert_many(
- 1,
- MockHintIter {
- x: [5, 6].iter().cloned(),
- hint: 5,
- },
- );
- assert_eq!(
- &v.iter().map(|v| *v).collect::<Vec<_>>(),
- &[0, 5, 6, 1, 2, 3]
- );
-}
-
-#[test]
-fn test_insert_many_long_hint() {
- let mut v: SmallVec<[u8; 8]> = SmallVec::new();
- for x in 0..4 {
- v.push(x);
- }
- assert_eq!(v.len(), 4);
- v.insert_many(
- 1,
- MockHintIter {
- x: [5, 6].iter().cloned(),
- hint: 1,
- },
- );
- assert_eq!(
- &v.iter().map(|v| *v).collect::<Vec<_>>(),
- &[0, 5, 6, 1, 2, 3]
- );
-}
-
-// https://github.com/servo/rust-smallvec/issues/96
-mod insert_many_panic {
- use crate::{smallvec, SmallVec};
- use alloc::boxed::Box;
-
- struct PanicOnDoubleDrop {
- dropped: Box<bool>,
- }
-
- impl PanicOnDoubleDrop {
- fn new() -> Self {
- Self {
- dropped: Box::new(false),
- }
- }
- }
-
- impl Drop for PanicOnDoubleDrop {
- fn drop(&mut self) {
- assert!(!*self.dropped, "already dropped");
- *self.dropped = true;
- }
- }
-
- /// Claims to yield `hint` items, but actually yields `count`, then panics.
- struct BadIter {
- hint: usize,
- count: usize,
- }
-
- impl Iterator for BadIter {
- type Item = PanicOnDoubleDrop;
- fn size_hint(&self) -> (usize, Option<usize>) {
- (self.hint, None)
- }
- fn next(&mut self) -> Option<Self::Item> {
- if self.count == 0 {
- panic!()
- }
- self.count -= 1;
- Some(PanicOnDoubleDrop::new())
- }
- }
-
- #[test]
- fn panic_early_at_start() {
- let mut vec: SmallVec<[PanicOnDoubleDrop; 0]> =
- smallvec![PanicOnDoubleDrop::new(), PanicOnDoubleDrop::new(),];
- let result = ::std::panic::catch_unwind(move || {
- vec.insert_many(0, BadIter { hint: 1, count: 0 });
- });
- assert!(result.is_err());
- }
-
- #[test]
- fn panic_early_in_middle() {
- let mut vec: SmallVec<[PanicOnDoubleDrop; 0]> =
- smallvec![PanicOnDoubleDrop::new(), PanicOnDoubleDrop::new(),];
- let result = ::std::panic::catch_unwind(move || {
- vec.insert_many(1, BadIter { hint: 4, count: 2 });
- });
- assert!(result.is_err());
- }
-
- #[test]
- fn panic_early_at_end() {
- let mut vec: SmallVec<[PanicOnDoubleDrop; 0]> =
- smallvec![PanicOnDoubleDrop::new(), PanicOnDoubleDrop::new(),];
- let result = ::std::panic::catch_unwind(move || {
- vec.insert_many(2, BadIter { hint: 3, count: 1 });
- });
- assert!(result.is_err());
- }
-
- #[test]
- fn panic_late_at_start() {
- let mut vec: SmallVec<[PanicOnDoubleDrop; 0]> =
- smallvec![PanicOnDoubleDrop::new(), PanicOnDoubleDrop::new(),];
- let result = ::std::panic::catch_unwind(move || {
- vec.insert_many(0, BadIter { hint: 3, count: 5 });
- });
- assert!(result.is_err());
- }
-
- #[test]
- fn panic_late_at_end() {
- let mut vec: SmallVec<[PanicOnDoubleDrop; 0]> =
- smallvec![PanicOnDoubleDrop::new(), PanicOnDoubleDrop::new(),];
- let result = ::std::panic::catch_unwind(move || {
- vec.insert_many(2, BadIter { hint: 3, count: 5 });
- });
- assert!(result.is_err());
- }
-}
-
-#[test]
-#[should_panic]
-fn test_invalid_grow() {
- let mut v: SmallVec<[u8; 8]> = SmallVec::new();
- v.extend(0..8);
- v.grow(5);
-}
-
-#[test]
-#[should_panic]
-fn drain_overflow() {
- let mut v: SmallVec<[u8; 8]> = smallvec![0];
- v.drain(..=std::usize::MAX);
-}
-
-#[test]
-fn test_insert_from_slice() {
- let mut v: SmallVec<[u8; 8]> = SmallVec::new();
- for x in 0..4 {
- v.push(x);
- }
- assert_eq!(v.len(), 4);
- v.insert_from_slice(1, &[5, 6]);
- assert_eq!(
- &v.iter().map(|v| *v).collect::<Vec<_>>(),
- &[0, 5, 6, 1, 2, 3]
- );
-}
-
-#[test]
-fn test_extend_from_slice() {
- let mut v: SmallVec<[u8; 8]> = SmallVec::new();
- for x in 0..4 {
- v.push(x);
- }
- assert_eq!(v.len(), 4);
- v.extend_from_slice(&[5, 6]);
- assert_eq!(
- &v.iter().map(|v| *v).collect::<Vec<_>>(),
- &[0, 1, 2, 3, 5, 6]
- );
-}
-
-#[test]
-#[should_panic]
-fn test_drop_panic_smallvec() {
- // This test should only panic once, and not double panic,
- // which would mean a double drop
- struct DropPanic;
-
- impl Drop for DropPanic {
- fn drop(&mut self) {
- panic!("drop");
- }
- }
-
- let mut v = SmallVec::<[_; 1]>::new();
- v.push(DropPanic);
-}
-
-#[test]
-fn test_eq() {
- let mut a: SmallVec<[u32; 2]> = SmallVec::new();
- let mut b: SmallVec<[u32; 2]> = SmallVec::new();
- let mut c: SmallVec<[u32; 2]> = SmallVec::new();
- // a = [1, 2]
- a.push(1);
- a.push(2);
- // b = [1, 2]
- b.push(1);
- b.push(2);
- // c = [3, 4]
- c.push(3);
- c.push(4);
-
- assert!(a == b);
- assert!(a != c);
-}
-
-#[test]
-fn test_ord() {
- let mut a: SmallVec<[u32; 2]> = SmallVec::new();
- let mut b: SmallVec<[u32; 2]> = SmallVec::new();
- let mut c: SmallVec<[u32; 2]> = SmallVec::new();
- // a = [1]
- a.push(1);
- // b = [1, 1]
- b.push(1);
- b.push(1);
- // c = [1, 2]
- c.push(1);
- c.push(2);
-
- assert!(a < b);
- assert!(b > a);
- assert!(b < c);
- assert!(c > b);
-}
-
-#[test]
-fn test_hash() {
- use std::collections::hash_map::DefaultHasher;
- use std::hash::Hash;
-
- {
- let mut a: SmallVec<[u32; 2]> = SmallVec::new();
- let b = [1, 2];
- a.extend(b.iter().cloned());
- let mut hasher = DefaultHasher::new();
- assert_eq!(a.hash(&mut hasher), b.hash(&mut hasher));
- }
- {
- let mut a: SmallVec<[u32; 2]> = SmallVec::new();
- let b = [1, 2, 11, 12];
- a.extend(b.iter().cloned());
- let mut hasher = DefaultHasher::new();
- assert_eq!(a.hash(&mut hasher), b.hash(&mut hasher));
- }
-}
-
-#[test]
-fn test_as_ref() {
- let mut a: SmallVec<[u32; 2]> = SmallVec::new();
- a.push(1);
- assert_eq!(a.as_ref(), [1]);
- a.push(2);
- assert_eq!(a.as_ref(), [1, 2]);
- a.push(3);
- assert_eq!(a.as_ref(), [1, 2, 3]);
-}
-
-#[test]
-fn test_as_mut() {
- let mut a: SmallVec<[u32; 2]> = SmallVec::new();
- a.push(1);
- assert_eq!(a.as_mut(), [1]);
- a.push(2);
- assert_eq!(a.as_mut(), [1, 2]);
- a.push(3);
- assert_eq!(a.as_mut(), [1, 2, 3]);
- a.as_mut()[1] = 4;
- assert_eq!(a.as_mut(), [1, 4, 3]);
-}
-
-#[test]
-fn test_borrow() {
- use std::borrow::Borrow;
-
- let mut a: SmallVec<[u32; 2]> = SmallVec::new();
- a.push(1);
- assert_eq!(a.borrow(), [1]);
- a.push(2);
- assert_eq!(a.borrow(), [1, 2]);
- a.push(3);
- assert_eq!(a.borrow(), [1, 2, 3]);
-}
-
-#[test]
-fn test_borrow_mut() {
- use std::borrow::BorrowMut;
-
- let mut a: SmallVec<[u32; 2]> = SmallVec::new();
- a.push(1);
- assert_eq!(a.borrow_mut(), [1]);
- a.push(2);
- assert_eq!(a.borrow_mut(), [1, 2]);
- a.push(3);
- assert_eq!(a.borrow_mut(), [1, 2, 3]);
- BorrowMut::<[u32]>::borrow_mut(&mut a)[1] = 4;
- assert_eq!(a.borrow_mut(), [1, 4, 3]);
-}
-
-#[test]
-fn test_from() {
- assert_eq!(&SmallVec::<[u32; 2]>::from(&[1][..])[..], [1]);
- assert_eq!(&SmallVec::<[u32; 2]>::from(&[1, 2, 3][..])[..], [1, 2, 3]);
-
- let vec = vec![];
- let small_vec: SmallVec<[u8; 3]> = SmallVec::from(vec);
- assert_eq!(&*small_vec, &[]);
- drop(small_vec);
-
- let vec = vec![1, 2, 3, 4, 5];
- let small_vec: SmallVec<[u8; 3]> = SmallVec::from(vec);
- assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
- drop(small_vec);
-
- let vec = vec![1, 2, 3, 4, 5];
- let small_vec: SmallVec<[u8; 1]> = SmallVec::from(vec);
- assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
- drop(small_vec);
-
- let array = [1];
- let small_vec: SmallVec<[u8; 1]> = SmallVec::from(array);
- assert_eq!(&*small_vec, &[1]);
- drop(small_vec);
-
- let array = [99; 128];
- let small_vec: SmallVec<[u8; 128]> = SmallVec::from(array);
- assert_eq!(&*small_vec, vec![99u8; 128].as_slice());
- drop(small_vec);
-}
-
-#[test]
-fn test_from_slice() {
- assert_eq!(&SmallVec::<[u32; 2]>::from_slice(&[1][..])[..], [1]);
- assert_eq!(
- &SmallVec::<[u32; 2]>::from_slice(&[1, 2, 3][..])[..],
- [1, 2, 3]
- );
-}
-
-#[test]
-fn test_exact_size_iterator() {
- let mut vec = SmallVec::<[u32; 2]>::from(&[1, 2, 3][..]);
- assert_eq!(vec.clone().into_iter().len(), 3);
- assert_eq!(vec.drain(..2).len(), 2);
- assert_eq!(vec.into_iter().len(), 1);
-}
-
-#[test]
-fn test_into_iter_as_slice() {
- let vec = SmallVec::<[u32; 2]>::from(&[1, 2, 3][..]);
- let mut iter = vec.clone().into_iter();
- assert_eq!(iter.as_slice(), &[1, 2, 3]);
- assert_eq!(iter.as_mut_slice(), &[1, 2, 3]);
- iter.next();
- assert_eq!(iter.as_slice(), &[2, 3]);
- assert_eq!(iter.as_mut_slice(), &[2, 3]);
- iter.next_back();
- assert_eq!(iter.as_slice(), &[2]);
- assert_eq!(iter.as_mut_slice(), &[2]);
-}
-
-#[test]
-fn test_into_iter_clone() {
- // Test that the cloned iterator yields identical elements and that it owns its own copy
- // (i.e. no use after move errors).
- let mut iter = SmallVec::<[u8; 2]>::from_iter(0..3).into_iter();
- let mut clone_iter = iter.clone();
- while let Some(x) = iter.next() {
- assert_eq!(x, clone_iter.next().unwrap());
- }
- assert_eq!(clone_iter.next(), None);
-}
-
-#[test]
-fn test_into_iter_clone_partially_consumed_iterator() {
- // Test that the cloned iterator only contains the remaining elements of the original iterator.
- let mut iter = SmallVec::<[u8; 2]>::from_iter(0..3).into_iter().skip(1);
- let mut clone_iter = iter.clone();
- while let Some(x) = iter.next() {
- assert_eq!(x, clone_iter.next().unwrap());
- }
- assert_eq!(clone_iter.next(), None);
-}
-
-#[test]
-fn test_into_iter_clone_empty_smallvec() {
- let mut iter = SmallVec::<[u8; 2]>::new().into_iter();
- let mut clone_iter = iter.clone();
- assert_eq!(iter.next(), None);
- assert_eq!(clone_iter.next(), None);
-}
-
-#[test]
-fn shrink_to_fit_unspill() {
- let mut vec = SmallVec::<[u8; 2]>::from_iter(0..3);
- vec.pop();
- assert!(vec.spilled());
- vec.shrink_to_fit();
- assert!(!vec.spilled(), "shrink_to_fit will un-spill if possible");
-}
-
-#[test]
-fn test_into_vec() {
- let vec = SmallVec::<[u8; 2]>::from_iter(0..2);
- assert_eq!(vec.into_vec(), vec![0, 1]);
-
- let vec = SmallVec::<[u8; 2]>::from_iter(0..3);
- assert_eq!(vec.into_vec(), vec![0, 1, 2]);
-}
-
-#[test]
-fn test_into_inner() {
- let vec = SmallVec::<[u8; 2]>::from_iter(0..2);
- assert_eq!(vec.into_inner(), Ok([0, 1]));
-
- let vec = SmallVec::<[u8; 2]>::from_iter(0..1);
- assert_eq!(vec.clone().into_inner(), Err(vec));
-
- let vec = SmallVec::<[u8; 2]>::from_iter(0..3);
- assert_eq!(vec.clone().into_inner(), Err(vec));
-}
-
-#[test]
-fn test_from_vec() {
- let vec = vec![];
- let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
- assert_eq!(&*small_vec, &[]);
- drop(small_vec);
-
- let vec = vec![];
- let small_vec: SmallVec<[u8; 1]> = SmallVec::from_vec(vec);
- assert_eq!(&*small_vec, &[]);
- drop(small_vec);
-
- let vec = vec![1];
- let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
- assert_eq!(&*small_vec, &[1]);
- drop(small_vec);
-
- let vec = vec![1, 2, 3];
- let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
- assert_eq!(&*small_vec, &[1, 2, 3]);
- drop(small_vec);
-
- let vec = vec![1, 2, 3, 4, 5];
- let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
- assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
- drop(small_vec);
-
- let vec = vec![1, 2, 3, 4, 5];
- let small_vec: SmallVec<[u8; 1]> = SmallVec::from_vec(vec);
- assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
- drop(small_vec);
-}
-
-#[test]
-fn test_retain() {
- // Test inline data storate
- let mut sv: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 2, 3, 3, 4]);
- sv.retain(|&mut i| i != 3);
- assert_eq!(sv.pop(), Some(4));
- assert_eq!(sv.pop(), Some(2));
- assert_eq!(sv.pop(), Some(1));
- assert_eq!(sv.pop(), None);
-
- // Test spilled data storage
- let mut sv: SmallVec<[i32; 3]> = SmallVec::from_slice(&[1, 2, 3, 3, 4]);
- sv.retain(|&mut i| i != 3);
- assert_eq!(sv.pop(), Some(4));
- assert_eq!(sv.pop(), Some(2));
- assert_eq!(sv.pop(), Some(1));
- assert_eq!(sv.pop(), None);
-
- // Test that drop implementations are called for inline.
- let one = Rc::new(1);
- let mut sv: SmallVec<[Rc<i32>; 3]> = SmallVec::new();
- sv.push(Rc::clone(&one));
- assert_eq!(Rc::strong_count(&one), 2);
- sv.retain(|_| false);
- assert_eq!(Rc::strong_count(&one), 1);
-
- // Test that drop implementations are called for spilled data.
- let mut sv: SmallVec<[Rc<i32>; 1]> = SmallVec::new();
- sv.push(Rc::clone(&one));
- sv.push(Rc::new(2));
- assert_eq!(Rc::strong_count(&one), 2);
- sv.retain(|_| false);
- assert_eq!(Rc::strong_count(&one), 1);
-}
-
-#[test]
-fn test_dedup() {
- let mut dupes: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 1, 2, 3, 3]);
- dupes.dedup();
- assert_eq!(&*dupes, &[1, 2, 3]);
-
- let mut empty: SmallVec<[i32; 5]> = SmallVec::new();
- empty.dedup();
- assert!(empty.is_empty());
-
- let mut all_ones: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 1, 1, 1, 1]);
- all_ones.dedup();
- assert_eq!(all_ones.len(), 1);
-
- let mut no_dupes: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 2, 3, 4, 5]);
- no_dupes.dedup();
- assert_eq!(no_dupes.len(), 5);
-}
-
-#[test]
-fn test_resize() {
- let mut v: SmallVec<[i32; 8]> = SmallVec::new();
- v.push(1);
- v.resize(5, 0);
- assert_eq!(v[..], [1, 0, 0, 0, 0][..]);
-
- v.resize(2, -1);
- assert_eq!(v[..], [1, 0][..]);
-}
-
-#[cfg(feature = "write")]
-#[test]
-fn test_write() {
- use std::io::Write;
-
- let data = [1, 2, 3, 4, 5];
-
- let mut small_vec: SmallVec<[u8; 2]> = SmallVec::new();
- let len = small_vec.write(&data[..]).unwrap();
- assert_eq!(len, 5);
- assert_eq!(small_vec.as_ref(), data.as_ref());
-
- let mut small_vec: SmallVec<[u8; 2]> = SmallVec::new();
- small_vec.write_all(&data[..]).unwrap();
- assert_eq!(small_vec.as_ref(), data.as_ref());
-}
-
-#[cfg(feature = "serde")]
-#[test]
-fn test_serde() {
- use bincode::{config, deserialize};
- let mut small_vec: SmallVec<[i32; 2]> = SmallVec::new();
- small_vec.push(1);
- let encoded = config().limit(100).serialize(&small_vec).unwrap();
- let decoded: SmallVec<[i32; 2]> = deserialize(&encoded).unwrap();
- assert_eq!(small_vec, decoded);
- small_vec.push(2);
- // Spill the vec
- small_vec.push(3);
- small_vec.push(4);
- // Check again after spilling.
- let encoded = config().limit(100).serialize(&small_vec).unwrap();
- let decoded: SmallVec<[i32; 2]> = deserialize(&encoded).unwrap();
- assert_eq!(small_vec, decoded);
-}
-
-#[test]
-fn grow_to_shrink() {
- let mut v: SmallVec<[u8; 2]> = SmallVec::new();
- v.push(1);
- v.push(2);
- v.push(3);
- assert!(v.spilled());
- v.clear();
- // Shrink to inline.
- v.grow(2);
- assert!(!v.spilled());
- assert_eq!(v.capacity(), 2);
- assert_eq!(v.len(), 0);
- v.push(4);
- assert_eq!(v[..], [4]);
-}
-
-#[test]
-fn resumable_extend() {
- let s = "a b c";
- // This iterator yields: (Some('a'), None, Some('b'), None, Some('c')), None
- let it = s
- .chars()
- .scan(0, |_, ch| if ch.is_whitespace() { None } else { Some(ch) });
- let mut v: SmallVec<[char; 4]> = SmallVec::new();
- v.extend(it);
- assert_eq!(v[..], ['a']);
-}
-
-// #139
-#[test]
-fn uninhabited() {
- enum Void {}
- let _sv = SmallVec::<[Void; 8]>::new();
-}
-
-#[test]
-fn grow_spilled_same_size() {
- let mut v: SmallVec<[u8; 2]> = SmallVec::new();
- v.push(0);
- v.push(1);
- v.push(2);
- assert!(v.spilled());
- assert_eq!(v.capacity(), 4);
- // grow with the same capacity
- v.grow(4);
- assert_eq!(v.capacity(), 4);
- assert_eq!(v[..], [0, 1, 2]);
-}
-
-#[cfg(feature = "const_generics")]
-#[test]
-fn const_generics() {
- let _v = SmallVec::<[i32; 987]>::default();
-}
-
-#[cfg(feature = "const_new")]
-#[test]
-fn const_new() {
- let v = const_new_inner();
- assert_eq!(v.capacity(), 4);
- assert_eq!(v.len(), 0);
- let v = const_new_inline_sized();
- assert_eq!(v.capacity(), 4);
- assert_eq!(v.len(), 4);
- assert_eq!(v[0], 1);
- let v = const_new_inline_args();
- assert_eq!(v.capacity(), 2);
- assert_eq!(v.len(), 2);
- assert_eq!(v[0], 1);
- assert_eq!(v[1], 4);
-}
-#[cfg(feature = "const_new")]
-const fn const_new_inner() -> SmallVec<[i32; 4]> {
- SmallVec::<[i32; 4]>::new_const()
-}
-#[cfg(feature = "const_new")]
-const fn const_new_inline_sized() -> SmallVec<[i32; 4]> {
- crate::smallvec_inline![1; 4]
-}
-#[cfg(feature = "const_new")]
-const fn const_new_inline_args() -> SmallVec<[i32; 2]> {
- crate::smallvec_inline![1, 4]
-}
-
-#[test]
-fn empty_macro() {
- let _v: SmallVec<[u8; 1]> = smallvec![];
-}
-
-#[test]
-fn zero_size_items() {
- SmallVec::<[(); 0]>::new().push(());
-}
-
-#[test]
-fn test_insert_many_overflow() {
- let mut v: SmallVec<[u8; 1]> = SmallVec::new();
- v.push(123);
-
- // Prepare an iterator with small lower bound
- let iter = (0u8..5).filter(|n| n % 2 == 0);
- assert_eq!(iter.size_hint().0, 0);
-
- v.insert_many(0, iter);
- assert_eq!(&*v, &[0, 2, 4, 123]);
-}
-
-#[test]
-fn test_clone_from() {
- let mut a: SmallVec<[u8; 2]> = SmallVec::new();
- a.push(1);
- a.push(2);
- a.push(3);
-
- let mut b: SmallVec<[u8; 2]> = SmallVec::new();
- b.push(10);
-
- let mut c: SmallVec<[u8; 2]> = SmallVec::new();
- c.push(20);
- c.push(21);
- c.push(22);
-
- a.clone_from(&b);
- assert_eq!(&*a, &[10]);
-
- b.clone_from(&c);
- assert_eq!(&*b, &[20, 21, 22]);
-}
-
-#[test]
-fn test_size() {
- use core::mem::size_of;
- assert_eq!(24, size_of::<SmallVec<[u8; 8]>>());
-}
-
-#[cfg(feature = "drain_filter")]
-#[test]
-fn drain_filter() {
- let mut a: SmallVec<[u8; 2]> = smallvec![1u8, 2, 3, 4, 5, 6, 7, 8];
-
- let b: SmallVec<[u8; 2]> = a.drain_filter(|x| *x % 3 == 0).collect();
-
- assert_eq!(a, SmallVec::<[u8; 2]>::from_slice(&[1u8, 2, 4, 5, 7, 8]));
- assert_eq!(b, SmallVec::<[u8; 2]>::from_slice(&[3u8, 6]));
-}
-
-#[cfg(feature = "drain_keep_rest")]
-#[test]
-fn drain_keep_rest() {
- let mut a: SmallVec<[i32; 3]> = smallvec![1i32, 2, 3, 4, 5, 6, 7, 8];
- let mut df = a.drain_filter(|x| *x % 2 == 0);
-
- assert_eq!(df.next().unwrap(), 2);
- assert_eq!(df.next().unwrap(), 4);
-
- df.keep_rest();
-
- assert_eq!(a, SmallVec::<[i32; 3]>::from_slice(&[1i32, 3, 5, 6, 7, 8]));
-}