| // 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; | |
| if index > len { | |
| panic!("index exceeds length"); | |
| } | |
| // SAFETY: add is UB if index > len, but we panicked first | |
| ptr = ptr.add(index); | |
| if index < len { | |
| // Shift element to the right of `index`. | |
| ptr::copy(ptr, ptr.add(1), len - index); | |
| } | |
| *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)), | |
| } | |
| } | |
| /// Constructs a new `SmallVec` on the stack from an array without | |
| /// copying elements. Also sets the length. The user is responsible | |
| /// for ensuring that `len <= N`. | |
| /// | |
| /// This is a `const` version of [`SmallVec::from_buf_and_len_unchecked`] that is enabled by the feature `const_new`, with the limitation that it only works for arrays. | |
| #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))] | |
| #[inline] | |
| pub const unsafe fn from_const_with_len_unchecked(items: [T; N], len: usize) -> Self { | |
| SmallVec { | |
| capacity: len, | |
| 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> {} |