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