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: &'a ::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: &'a ::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(name:"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 if index > len {
1376 panic!("index exceeds length");
1377 }
1378 // SAFETY: add is UB if index > len, but we panicked first
1379 ptr = ptr.add(index);
1380 if index < len {
1381 // Shift element to the right of `index`.
1382 ptr::copy(ptr, ptr.add(1), len - index);
1383 }
1384 *len_ptr = len + 1;
1385 ptr::write(ptr, element);
1386 }
1387 }
1388
1389 /// Insert multiple elements at position `index`, shifting all following elements toward the
1390 /// back.
1391 pub fn insert_many<I: IntoIterator<Item = A::Item>>(&mut self, index: usize, iterable: I) {
1392 let mut iter = iterable.into_iter();
1393 if index == self.len() {
1394 return self.extend(iter);
1395 }
1396
1397 let (lower_size_bound, _) = iter.size_hint();
1398 assert!(lower_size_bound <= core::isize::MAX as usize); // Ensure offset is indexable
1399 assert!(index + lower_size_bound >= index); // Protect against overflow
1400
1401 let mut num_added = 0;
1402 let old_len = self.len();
1403 assert!(index <= old_len);
1404
1405 unsafe {
1406 // Reserve space for `lower_size_bound` elements.
1407 self.reserve(lower_size_bound);
1408 let start = self.as_mut_ptr();
1409 let ptr = start.add(index);
1410
1411 // Move the trailing elements.
1412 ptr::copy(ptr, ptr.add(lower_size_bound), old_len - index);
1413
1414 // In case the iterator panics, don't double-drop the items we just copied above.
1415 self.set_len(0);
1416 let mut guard = DropOnPanic {
1417 start,
1418 skip: index..(index + lower_size_bound),
1419 len: old_len + lower_size_bound,
1420 };
1421
1422 // The set_len above invalidates the previous pointers, so we must re-create them.
1423 let start = self.as_mut_ptr();
1424 let ptr = start.add(index);
1425
1426 while num_added < lower_size_bound {
1427 let element = match iter.next() {
1428 Some(x) => x,
1429 None => break,
1430 };
1431 let cur = ptr.add(num_added);
1432 ptr::write(cur, element);
1433 guard.skip.start += 1;
1434 num_added += 1;
1435 }
1436
1437 if num_added < lower_size_bound {
1438 // Iterator provided fewer elements than the hint. Move the tail backward.
1439 ptr::copy(
1440 ptr.add(lower_size_bound),
1441 ptr.add(num_added),
1442 old_len - index,
1443 );
1444 }
1445 // There are no more duplicate or uninitialized slots, so the guard is not needed.
1446 self.set_len(old_len + num_added);
1447 mem::forget(guard);
1448 }
1449
1450 // Insert any remaining elements one-by-one.
1451 for element in iter {
1452 self.insert(index + num_added, element);
1453 num_added += 1;
1454 }
1455
1456 struct DropOnPanic<T> {
1457 start: *mut T,
1458 skip: Range<usize>, // Space we copied-out-of, but haven't written-to yet.
1459 len: usize,
1460 }
1461
1462 impl<T> Drop for DropOnPanic<T> {
1463 fn drop(&mut self) {
1464 for i in 0..self.len {
1465 if !self.skip.contains(&i) {
1466 unsafe {
1467 ptr::drop_in_place(self.start.add(i));
1468 }
1469 }
1470 }
1471 }
1472 }
1473 }
1474
1475 /// Convert a `SmallVec` to a `Vec`, without reallocating if the `SmallVec` has already spilled onto
1476 /// the heap.
1477 pub fn into_vec(mut self) -> Vec<A::Item> {
1478 if self.spilled() {
1479 unsafe {
1480 let (ptr, &mut len) = self.data.heap_mut();
1481 let v = Vec::from_raw_parts(ptr.as_ptr(), len, self.capacity);
1482 mem::forget(self);
1483 v
1484 }
1485 } else {
1486 self.into_iter().collect()
1487 }
1488 }
1489
1490 /// Converts a `SmallVec` into a `Box<[T]>` without reallocating if the `SmallVec` has already spilled
1491 /// onto the heap.
1492 ///
1493 /// Note that this will drop any excess capacity.
1494 pub fn into_boxed_slice(self) -> Box<[A::Item]> {
1495 self.into_vec().into_boxed_slice()
1496 }
1497
1498 /// Convert the `SmallVec` into an `A` if possible. Otherwise return `Err(Self)`.
1499 ///
1500 /// This method returns `Err(Self)` if the `SmallVec` is too short (and the `A` contains uninitialized elements),
1501 /// or if the `SmallVec` is too long (and all the elements were spilled to the heap).
1502 pub fn into_inner(self) -> Result<A, Self> {
1503 if self.spilled() || self.len() != A::size() {
1504 // Note: A::size, not Self::inline_capacity
1505 Err(self)
1506 } else {
1507 unsafe {
1508 let data = ptr::read(&self.data);
1509 mem::forget(self);
1510 Ok(data.into_inline().assume_init())
1511 }
1512 }
1513 }
1514
1515 /// Retains only the elements specified by the predicate.
1516 ///
1517 /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
1518 /// This method operates in place and preserves the order of the retained
1519 /// elements.
1520 pub fn retain<F: FnMut(&mut A::Item) -> bool>(&mut self, mut f: F) {
1521 let mut del = 0;
1522 let len = self.len();
1523 for i in 0..len {
1524 if !f(&mut self[i]) {
1525 del += 1;
1526 } else if del > 0 {
1527 self.swap(i - del, i);
1528 }
1529 }
1530 self.truncate(len - del);
1531 }
1532
1533 /// Retains only the elements specified by the predicate.
1534 ///
1535 /// This method is identical in behaviour to [`retain`]; it is included only
1536 /// to maintain api-compatability with `std::Vec`, where the methods are
1537 /// separate for historical reasons.
1538 pub fn retain_mut<F: FnMut(&mut A::Item) -> bool>(&mut self, f: F) {
1539 self.retain(f)
1540 }
1541
1542 /// Removes consecutive duplicate elements.
1543 pub fn dedup(&mut self)
1544 where
1545 A::Item: PartialEq<A::Item>,
1546 {
1547 self.dedup_by(|a, b| a == b);
1548 }
1549
1550 /// Removes consecutive duplicate elements using the given equality relation.
1551 pub fn dedup_by<F>(&mut self, mut same_bucket: F)
1552 where
1553 F: FnMut(&mut A::Item, &mut A::Item) -> bool,
1554 {
1555 // See the implementation of Vec::dedup_by in the
1556 // standard library for an explanation of this algorithm.
1557 let len = self.len();
1558 if len <= 1 {
1559 return;
1560 }
1561
1562 let ptr = self.as_mut_ptr();
1563 let mut w: usize = 1;
1564
1565 unsafe {
1566 for r in 1..len {
1567 let p_r = ptr.add(r);
1568 let p_wm1 = ptr.add(w - 1);
1569 if !same_bucket(&mut *p_r, &mut *p_wm1) {
1570 if r != w {
1571 let p_w = p_wm1.add(1);
1572 mem::swap(&mut *p_r, &mut *p_w);
1573 }
1574 w += 1;
1575 }
1576 }
1577 }
1578
1579 self.truncate(w);
1580 }
1581
1582 /// Removes consecutive elements that map to the same key.
1583 pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1584 where
1585 F: FnMut(&mut A::Item) -> K,
1586 K: PartialEq<K>,
1587 {
1588 self.dedup_by(|a, b| key(a) == key(b));
1589 }
1590
1591 /// Resizes the `SmallVec` in-place so that `len` is equal to `new_len`.
1592 ///
1593 /// If `new_len` is greater than `len`, the `SmallVec` is extended by the difference, with each
1594 /// additional slot filled with the result of calling the closure `f`. The return values from `f`
1595 /// will end up in the `SmallVec` in the order they have been generated.
1596 ///
1597 /// If `new_len` is less than `len`, the `SmallVec` is simply truncated.
1598 ///
1599 /// This method uses a closure to create new values on every push. If you'd rather `Clone` a given
1600 /// value, use `resize`. If you want to use the `Default` trait to generate values, you can pass
1601 /// `Default::default()` as the second argument.
1602 ///
1603 /// Added for `std::vec::Vec` compatibility (added in Rust 1.33.0)
1604 ///
1605 /// ```
1606 /// # use smallvec::{smallvec, SmallVec};
1607 /// let mut vec : SmallVec<[_; 4]> = smallvec![1, 2, 3];
1608 /// vec.resize_with(5, Default::default);
1609 /// assert_eq!(&*vec, &[1, 2, 3, 0, 0]);
1610 ///
1611 /// let mut vec : SmallVec<[_; 4]> = smallvec![];
1612 /// let mut p = 1;
1613 /// vec.resize_with(4, || { p *= 2; p });
1614 /// assert_eq!(&*vec, &[2, 4, 8, 16]);
1615 /// ```
1616 pub fn resize_with<F>(&mut self, new_len: usize, f: F)
1617 where
1618 F: FnMut() -> A::Item,
1619 {
1620 let old_len = self.len();
1621 if old_len < new_len {
1622 let mut f = f;
1623 let additional = new_len - old_len;
1624 self.reserve(additional);
1625 for _ in 0..additional {
1626 self.push(f());
1627 }
1628 } else if old_len > new_len {
1629 self.truncate(new_len);
1630 }
1631 }
1632
1633 /// Creates a `SmallVec` directly from the raw components of another
1634 /// `SmallVec`.
1635 ///
1636 /// # Safety
1637 ///
1638 /// This is highly unsafe, due to the number of invariants that aren't
1639 /// checked:
1640 ///
1641 /// * `ptr` needs to have been previously allocated via `SmallVec` for its
1642 /// spilled storage (at least, it's highly likely to be incorrect if it
1643 /// wasn't).
1644 /// * `ptr`'s `A::Item` type needs to be the same size and alignment that
1645 /// it was allocated with
1646 /// * `length` needs to be less than or equal to `capacity`.
1647 /// * `capacity` needs to be the capacity that the pointer was allocated
1648 /// with.
1649 ///
1650 /// Violating these may cause problems like corrupting the allocator's
1651 /// internal data structures.
1652 ///
1653 /// Additionally, `capacity` must be greater than the amount of inline
1654 /// storage `A` has; that is, the new `SmallVec` must need to spill over
1655 /// into heap allocated storage. This condition is asserted against.
1656 ///
1657 /// The ownership of `ptr` is effectively transferred to the
1658 /// `SmallVec` which may then deallocate, reallocate or change the
1659 /// contents of memory pointed to by the pointer at will. Ensure
1660 /// that nothing else uses the pointer after calling this
1661 /// function.
1662 ///
1663 /// # Examples
1664 ///
1665 /// ```
1666 /// # use smallvec::{smallvec, SmallVec};
1667 /// use std::mem;
1668 /// use std::ptr;
1669 ///
1670 /// fn main() {
1671 /// let mut v: SmallVec<[_; 1]> = smallvec![1, 2, 3];
1672 ///
1673 /// // Pull out the important parts of `v`.
1674 /// let p = v.as_mut_ptr();
1675 /// let len = v.len();
1676 /// let cap = v.capacity();
1677 /// let spilled = v.spilled();
1678 ///
1679 /// unsafe {
1680 /// // Forget all about `v`. The heap allocation that stored the
1681 /// // three values won't be deallocated.
1682 /// mem::forget(v);
1683 ///
1684 /// // Overwrite memory with [4, 5, 6].
1685 /// //
1686 /// // This is only safe if `spilled` is true! Otherwise, we are
1687 /// // writing into the old `SmallVec`'s inline storage on the
1688 /// // stack.
1689 /// assert!(spilled);
1690 /// for i in 0..len {
1691 /// ptr::write(p.add(i), 4 + i);
1692 /// }
1693 ///
1694 /// // Put everything back together into a SmallVec with a different
1695 /// // amount of inline storage, but which is still less than `cap`.
1696 /// let rebuilt = SmallVec::<[_; 2]>::from_raw_parts(p, len, cap);
1697 /// assert_eq!(&*rebuilt, &[4, 5, 6]);
1698 /// }
1699 /// }
1700 #[inline]
1701 pub unsafe fn from_raw_parts(ptr: *mut A::Item, length: usize, capacity: usize) -> SmallVec<A> {
1702 // SAFETY: We require caller to provide same ptr as we alloc
1703 // and we never alloc null pointer.
1704 let ptr = unsafe {
1705 debug_assert!(!ptr.is_null(), "Called `from_raw_parts` with null pointer.");
1706 NonNull::new_unchecked(ptr)
1707 };
1708 assert!(capacity > Self::inline_capacity());
1709 SmallVec {
1710 capacity,
1711 data: SmallVecData::from_heap(ptr, length),
1712 }
1713 }
1714
1715 /// Returns a raw pointer to the vector's buffer.
1716 pub fn as_ptr(&self) -> *const A::Item {
1717 // We shadow the slice method of the same name to avoid going through
1718 // `deref`, which creates an intermediate reference that may place
1719 // additional safety constraints on the contents of the slice.
1720 self.triple().0.as_ptr()
1721 }
1722
1723 /// Returns a raw mutable pointer to the vector's buffer.
1724 pub fn as_mut_ptr(&mut self) -> *mut A::Item {
1725 // We shadow the slice method of the same name to avoid going through
1726 // `deref_mut`, which creates an intermediate reference that may place
1727 // additional safety constraints on the contents of the slice.
1728 self.triple_mut().0.as_ptr()
1729 }
1730}
1731
1732impl<A: Array> SmallVec<A>
1733where
1734 A::Item: Copy,
1735{
1736 /// Copy the elements from a slice into a new `SmallVec`.
1737 ///
1738 /// For slices of `Copy` types, this is more efficient than `SmallVec::from(slice)`.
1739 pub fn from_slice(slice: &[A::Item]) -> Self {
1740 let len = slice.len();
1741 if len <= Self::inline_capacity() {
1742 SmallVec {
1743 capacity: len,
1744 data: SmallVecData::from_inline(unsafe {
1745 let mut data: MaybeUninit<A> = MaybeUninit::uninit();
1746 ptr::copy_nonoverlapping(
1747 slice.as_ptr(),
1748 data.as_mut_ptr() as *mut A::Item,
1749 len,
1750 );
1751 data
1752 }),
1753 }
1754 } else {
1755 let mut b = slice.to_vec();
1756 let cap = b.capacity();
1757 let ptr = NonNull::new(b.as_mut_ptr()).expect("Vec always contain non null pointers.");
1758 mem::forget(b);
1759 SmallVec {
1760 capacity: cap,
1761 data: SmallVecData::from_heap(ptr, len),
1762 }
1763 }
1764 }
1765
1766 /// Copy elements from a slice into the vector at position `index`, shifting any following
1767 /// elements toward the back.
1768 ///
1769 /// For slices of `Copy` types, this is more efficient than `insert`.
1770 #[inline]
1771 pub fn insert_from_slice(&mut self, index: usize, slice: &[A::Item]) {
1772 self.reserve(slice.len());
1773
1774 let len = self.len();
1775 assert!(index <= len);
1776
1777 unsafe {
1778 let slice_ptr = slice.as_ptr();
1779 let ptr = self.as_mut_ptr().add(index);
1780 ptr::copy(ptr, ptr.add(slice.len()), len - index);
1781 ptr::copy_nonoverlapping(slice_ptr, ptr, slice.len());
1782 self.set_len(len + slice.len());
1783 }
1784 }
1785
1786 /// Copy elements from a slice and append them to the vector.
1787 ///
1788 /// For slices of `Copy` types, this is more efficient than `extend`.
1789 #[inline]
1790 pub fn extend_from_slice(&mut self, slice: &[A::Item]) {
1791 let len = self.len();
1792 self.insert_from_slice(len, slice);
1793 }
1794}
1795
1796impl<A: Array> SmallVec<A>
1797where
1798 A::Item: Clone,
1799{
1800 /// Resizes the vector so that its length is equal to `len`.
1801 ///
1802 /// If `len` is less than the current length, the vector simply truncated.
1803 ///
1804 /// If `len` is greater than the current length, `value` is appended to the
1805 /// vector until its length equals `len`.
1806 pub fn resize(&mut self, len: usize, value: A::Item) {
1807 let old_len = self.len();
1808
1809 if len > old_len {
1810 self.extend(repeat(value).take(len - old_len));
1811 } else {
1812 self.truncate(len);
1813 }
1814 }
1815
1816 /// Creates a `SmallVec` with `n` copies of `elem`.
1817 /// ```
1818 /// use smallvec::SmallVec;
1819 ///
1820 /// let v = SmallVec::<[char; 128]>::from_elem('d', 2);
1821 /// assert_eq!(v, SmallVec::from_buf(['d', 'd']));
1822 /// ```
1823 pub fn from_elem(elem: A::Item, n: usize) -> Self {
1824 if n > Self::inline_capacity() {
1825 vec![elem; n].into()
1826 } else {
1827 let mut v = SmallVec::<A>::new();
1828 unsafe {
1829 let (ptr, len_ptr, _) = v.triple_mut();
1830 let ptr = ptr.as_ptr();
1831 let mut local_len = SetLenOnDrop::new(len_ptr);
1832
1833 for i in 0..n {
1834 ::core::ptr::write(ptr.add(i), elem.clone());
1835 local_len.increment_len(1);
1836 }
1837 }
1838 v
1839 }
1840 }
1841}
1842
1843impl<A: Array> ops::Deref for SmallVec<A> {
1844 type Target = [A::Item];
1845 #[inline]
1846 fn deref(&self) -> &[A::Item] {
1847 unsafe {
1848 let (ptr: ConstNonNull<::Item>, len: usize, _) = self.triple();
1849 slice::from_raw_parts(data:ptr.as_ptr(), len)
1850 }
1851 }
1852}
1853
1854impl<A: Array> ops::DerefMut for SmallVec<A> {
1855 #[inline]
1856 fn deref_mut(&mut self) -> &mut [A::Item] {
1857 unsafe {
1858 let (ptr: NonNull<::Item>, &mut len: usize, _) = self.triple_mut();
1859 slice::from_raw_parts_mut(data:ptr.as_ptr(), len)
1860 }
1861 }
1862}
1863
1864impl<A: Array> AsRef<[A::Item]> for SmallVec<A> {
1865 #[inline]
1866 fn as_ref(&self) -> &[A::Item] {
1867 self
1868 }
1869}
1870
1871impl<A: Array> AsMut<[A::Item]> for SmallVec<A> {
1872 #[inline]
1873 fn as_mut(&mut self) -> &mut [A::Item] {
1874 self
1875 }
1876}
1877
1878impl<A: Array> Borrow<[A::Item]> for SmallVec<A> {
1879 #[inline]
1880 fn borrow(&self) -> &[A::Item] {
1881 self
1882 }
1883}
1884
1885impl<A: Array> BorrowMut<[A::Item]> for SmallVec<A> {
1886 #[inline]
1887 fn borrow_mut(&mut self) -> &mut [A::Item] {
1888 self
1889 }
1890}
1891
1892#[cfg(feature = "write")]
1893#[cfg_attr(docsrs, doc(cfg(feature = "write")))]
1894impl<A: Array<Item = u8>> io::Write for SmallVec<A> {
1895 #[inline]
1896 fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
1897 self.extend_from_slice(buf);
1898 Ok(buf.len())
1899 }
1900
1901 #[inline]
1902 fn write_all(&mut self, buf: &[u8]) -> io::Result<()> {
1903 self.extend_from_slice(buf);
1904 Ok(())
1905 }
1906
1907 #[inline]
1908 fn flush(&mut self) -> io::Result<()> {
1909 Ok(())
1910 }
1911}
1912
1913#[cfg(feature = "serde")]
1914#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1915impl<A: Array> Serialize for SmallVec<A>
1916where
1917 A::Item: Serialize,
1918{
1919 fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
1920 let mut state = serializer.serialize_seq(Some(self.len()))?;
1921 for item in self {
1922 state.serialize_element(&item)?;
1923 }
1924 state.end()
1925 }
1926}
1927
1928#[cfg(feature = "serde")]
1929#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1930impl<'de, A: Array> Deserialize<'de> for SmallVec<A>
1931where
1932 A::Item: Deserialize<'de>,
1933{
1934 fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
1935 deserializer.deserialize_seq(SmallVecVisitor {
1936 phantom: PhantomData,
1937 })
1938 }
1939}
1940
1941#[cfg(feature = "serde")]
1942struct SmallVecVisitor<A> {
1943 phantom: PhantomData<A>,
1944}
1945
1946#[cfg(feature = "serde")]
1947impl<'de, A: Array> Visitor<'de> for SmallVecVisitor<A>
1948where
1949 A::Item: Deserialize<'de>,
1950{
1951 type Value = SmallVec<A>;
1952
1953 fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
1954 formatter.write_str("a sequence")
1955 }
1956
1957 fn visit_seq<B>(self, mut seq: B) -> Result<Self::Value, B::Error>
1958 where
1959 B: SeqAccess<'de>,
1960 {
1961 use serde::de::Error;
1962 let len = seq.size_hint().unwrap_or(0);
1963 let mut values = SmallVec::new();
1964 values.try_reserve(len).map_err(B::Error::custom)?;
1965
1966 while let Some(value) = seq.next_element()? {
1967 values.push(value);
1968 }
1969
1970 Ok(values)
1971 }
1972}
1973
1974#[cfg(feature = "specialization")]
1975trait SpecFrom<A: Array, S> {
1976 fn spec_from(slice: S) -> SmallVec<A>;
1977}
1978
1979#[cfg(feature = "specialization")]
1980mod specialization;
1981
1982#[cfg(feature = "arbitrary")]
1983mod arbitrary;
1984
1985#[cfg(feature = "specialization")]
1986impl<'a, A: Array> SpecFrom<A, &'a [A::Item]> for SmallVec<A>
1987where
1988 A::Item: Copy,
1989{
1990 #[inline]
1991 fn spec_from(slice: &'a [A::Item]) -> SmallVec<A> {
1992 SmallVec::from_slice(slice)
1993 }
1994}
1995
1996impl<'a, A: Array> From<&'a [A::Item]> for SmallVec<A>
1997where
1998 A::Item: Clone,
1999{
2000 #[cfg(not(feature = "specialization"))]
2001 #[inline]
2002 fn from(slice: &'a [A::Item]) -> SmallVec<A> {
2003 slice.iter().cloned().collect()
2004 }
2005
2006 #[cfg(feature = "specialization")]
2007 #[inline]
2008 fn from(slice: &'a [A::Item]) -> SmallVec<A> {
2009 SmallVec::spec_from(slice)
2010 }
2011}
2012
2013impl<A: Array> From<Vec<A::Item>> for SmallVec<A> {
2014 #[inline]
2015 fn from(vec: Vec<A::Item>) -> SmallVec<A> {
2016 SmallVec::from_vec(vec)
2017 }
2018}
2019
2020impl<A: Array> From<A> for SmallVec<A> {
2021 #[inline]
2022 fn from(array: A) -> SmallVec<A> {
2023 SmallVec::from_buf(array)
2024 }
2025}
2026
2027impl<A: Array, I: SliceIndex<[A::Item]>> ops::Index<I> for SmallVec<A> {
2028 type Output = I::Output;
2029
2030 fn index(&self, index: I) -> &I::Output {
2031 &(**self)[index]
2032 }
2033}
2034
2035impl<A: Array, I: SliceIndex<[A::Item]>> ops::IndexMut<I> for SmallVec<A> {
2036 fn index_mut(&mut self, index: I) -> &mut I::Output {
2037 &mut (&mut **self)[index]
2038 }
2039}
2040
2041#[allow(deprecated)]
2042impl<A: Array> ExtendFromSlice<A::Item> for SmallVec<A>
2043where
2044 A::Item: Copy,
2045{
2046 fn extend_from_slice(&mut self, other: &[A::Item]) {
2047 SmallVec::extend_from_slice(self, slice:other)
2048 }
2049}
2050
2051impl<A: Array> FromIterator<A::Item> for SmallVec<A> {
2052 #[inline]
2053 fn from_iter<I: IntoIterator<Item = A::Item>>(iterable: I) -> SmallVec<A> {
2054 let mut v: SmallVec = SmallVec::new();
2055 v.extend(iter:iterable);
2056 v
2057 }
2058}
2059
2060impl<A: Array> Extend<A::Item> for SmallVec<A> {
2061 fn extend<I: IntoIterator<Item = A::Item>>(&mut self, iterable: I) {
2062 let mut iter = iterable.into_iter();
2063 let (lower_size_bound, _) = iter.size_hint();
2064 self.reserve(lower_size_bound);
2065
2066 unsafe {
2067 let (ptr, len_ptr, cap) = self.triple_mut();
2068 let ptr = ptr.as_ptr();
2069 let mut len = SetLenOnDrop::new(len_ptr);
2070 while len.get() < cap {
2071 if let Some(out) = iter.next() {
2072 ptr::write(ptr.add(len.get()), out);
2073 len.increment_len(1);
2074 } else {
2075 return;
2076 }
2077 }
2078 }
2079
2080 for elem in iter {
2081 self.push(elem);
2082 }
2083 }
2084}
2085
2086impl<A: Array> fmt::Debug for SmallVec<A>
2087where
2088 A::Item: fmt::Debug,
2089{
2090 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2091 f.debug_list().entries(self.iter()).finish()
2092 }
2093}
2094
2095impl<A: Array> Default for SmallVec<A> {
2096 #[inline]
2097 fn default() -> SmallVec<A> {
2098 SmallVec::new()
2099 }
2100}
2101
2102#[cfg(feature = "may_dangle")]
2103unsafe impl<#[may_dangle] A: Array> Drop for SmallVec<A> {
2104 fn drop(&mut self) {
2105 unsafe {
2106 if self.spilled() {
2107 let (ptr: NonNull<::Item>, &mut len: usize) = self.data.heap_mut();
2108 Vec::from_raw_parts(ptr.as_ptr(), length:len, self.capacity);
2109 } else {
2110 ptr::drop_in_place(&mut self[..]);
2111 }
2112 }
2113 }
2114}
2115
2116#[cfg(not(feature = "may_dangle"))]
2117impl<A: Array> Drop for SmallVec<A> {
2118 fn drop(&mut self) {
2119 unsafe {
2120 if self.spilled() {
2121 let (ptr, &mut len) = self.data.heap_mut();
2122 drop(Vec::from_raw_parts(ptr.as_ptr(), len, self.capacity));
2123 } else {
2124 ptr::drop_in_place(&mut self[..]);
2125 }
2126 }
2127 }
2128}
2129
2130impl<A: Array> Clone for SmallVec<A>
2131where
2132 A::Item: Clone,
2133{
2134 #[inline]
2135 fn clone(&self) -> SmallVec<A> {
2136 SmallVec::from(self.as_slice())
2137 }
2138
2139 fn clone_from(&mut self, source: &Self) {
2140 // Inspired from `impl Clone for Vec`.
2141
2142 // drop anything that will not be overwritten
2143 self.truncate(source.len());
2144
2145 // self.len <= other.len due to the truncate above, so the
2146 // slices here are always in-bounds.
2147 let (init: &[impl Clone], tail: &[impl Clone]) = source.split_at(self.len());
2148
2149 // reuse the contained values' allocations/resources.
2150 self.clone_from_slice(src:init);
2151 self.extend(iter:tail.iter().cloned());
2152 }
2153}
2154
2155impl<A: Array, B: Array> PartialEq<SmallVec<B>> for SmallVec<A>
2156where
2157 A::Item: PartialEq<B::Item>,
2158{
2159 #[inline]
2160 fn eq(&self, other: &SmallVec<B>) -> bool {
2161 self[..] == other[..]
2162 }
2163}
2164
2165impl<A: Array> Eq for SmallVec<A> where A::Item: Eq {}
2166
2167impl<A: Array> PartialOrd for SmallVec<A>
2168where
2169 A::Item: PartialOrd,
2170{
2171 #[inline]
2172 fn partial_cmp(&self, other: &SmallVec<A>) -> Option<cmp::Ordering> {
2173 PartialOrd::partial_cmp(&**self, &**other)
2174 }
2175}
2176
2177impl<A: Array> Ord for SmallVec<A>
2178where
2179 A::Item: Ord,
2180{
2181 #[inline]
2182 fn cmp(&self, other: &SmallVec<A>) -> cmp::Ordering {
2183 Ord::cmp(&**self, &**other)
2184 }
2185}
2186
2187impl<A: Array> Hash for SmallVec<A>
2188where
2189 A::Item: Hash,
2190{
2191 fn hash<H: Hasher>(&self, state: &mut H) {
2192 (**self).hash(state)
2193 }
2194}
2195
2196unsafe impl<A: Array> Send for SmallVec<A> where A::Item: Send {}
2197
2198/// An iterator that consumes a `SmallVec` and yields its items by value.
2199///
2200/// Returned from [`SmallVec::into_iter`][1].
2201///
2202/// [1]: struct.SmallVec.html#method.into_iter
2203pub struct IntoIter<A: Array> {
2204 data: SmallVec<A>,
2205 current: usize,
2206 end: usize,
2207}
2208
2209impl<A: Array> fmt::Debug for IntoIter<A>
2210where
2211 A::Item: fmt::Debug,
2212{
2213 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2214 f.debug_tuple(name:"IntoIter").field(&self.as_slice()).finish()
2215 }
2216}
2217
2218impl<A: Array + Clone> Clone for IntoIter<A>
2219where
2220 A::Item: Clone,
2221{
2222 fn clone(&self) -> IntoIter<A> {
2223 SmallVec::from(self.as_slice()).into_iter()
2224 }
2225}
2226
2227impl<A: Array> Drop for IntoIter<A> {
2228 fn drop(&mut self) {
2229 for _ in self {}
2230 }
2231}
2232
2233impl<A: Array> Iterator for IntoIter<A> {
2234 type Item = A::Item;
2235
2236 #[inline]
2237 fn next(&mut self) -> Option<A::Item> {
2238 if self.current == self.end {
2239 None
2240 } else {
2241 unsafe {
2242 let current: usize = self.current;
2243 self.current += 1;
2244 Some(ptr::read(self.data.as_ptr().add(count:current)))
2245 }
2246 }
2247 }
2248
2249 #[inline]
2250 fn size_hint(&self) -> (usize, Option<usize>) {
2251 let size: usize = self.end - self.current;
2252 (size, Some(size))
2253 }
2254}
2255
2256impl<A: Array> DoubleEndedIterator for IntoIter<A> {
2257 #[inline]
2258 fn next_back(&mut self) -> Option<A::Item> {
2259 if self.current == self.end {
2260 None
2261 } else {
2262 unsafe {
2263 self.end -= 1;
2264 Some(ptr::read(self.data.as_ptr().add(self.end)))
2265 }
2266 }
2267 }
2268}
2269
2270impl<A: Array> ExactSizeIterator for IntoIter<A> {}
2271impl<A: Array> FusedIterator for IntoIter<A> {}
2272
2273impl<A: Array> IntoIter<A> {
2274 /// Returns the remaining items of this iterator as a slice.
2275 pub fn as_slice(&self) -> &[A::Item] {
2276 let len: usize = self.end - self.current;
2277 unsafe { core::slice::from_raw_parts(self.data.as_ptr().add(self.current), len) }
2278 }
2279
2280 /// Returns the remaining items of this iterator as a mutable slice.
2281 pub fn as_mut_slice(&mut self) -> &mut [A::Item] {
2282 let len: usize = self.end - self.current;
2283 unsafe { core::slice::from_raw_parts_mut(self.data.as_mut_ptr().add(self.current), len) }
2284 }
2285}
2286
2287impl<A: Array> IntoIterator for SmallVec<A> {
2288 type IntoIter = IntoIter<A>;
2289 type Item = A::Item;
2290 fn into_iter(mut self) -> Self::IntoIter {
2291 unsafe {
2292 // Set SmallVec len to zero as `IntoIter` drop handles dropping of the elements
2293 let len: usize = self.len();
2294 self.set_len(new_len:0);
2295 IntoIter {
2296 data: self,
2297 current: 0,
2298 end: len,
2299 }
2300 }
2301 }
2302}
2303
2304impl<'a, A: Array> IntoIterator for &'a SmallVec<A> {
2305 type IntoIter = slice::Iter<'a, A::Item>;
2306 type Item = &'a A::Item;
2307 fn into_iter(self) -> Self::IntoIter {
2308 self.iter()
2309 }
2310}
2311
2312impl<'a, A: Array> IntoIterator for &'a mut SmallVec<A> {
2313 type IntoIter = slice::IterMut<'a, A::Item>;
2314 type Item = &'a mut A::Item;
2315 fn into_iter(self) -> Self::IntoIter {
2316 self.iter_mut()
2317 }
2318}
2319
2320/// Types that can be used as the backing store for a [`SmallVec`].
2321pub unsafe trait Array {
2322 /// The type of the array's elements.
2323 type Item;
2324 /// Returns the number of items the array can hold.
2325 fn size() -> usize;
2326}
2327
2328/// Set the length of the vec when the `SetLenOnDrop` value goes out of scope.
2329///
2330/// Copied from <https://github.com/rust-lang/rust/pull/36355>
2331struct SetLenOnDrop<'a> {
2332 len: &'a mut usize,
2333 local_len: usize,
2334}
2335
2336impl<'a> SetLenOnDrop<'a> {
2337 #[inline]
2338 fn new(len: &'a mut usize) -> Self {
2339 SetLenOnDrop {
2340 local_len: *len,
2341 len,
2342 }
2343 }
2344
2345 #[inline]
2346 fn get(&self) -> usize {
2347 self.local_len
2348 }
2349
2350 #[inline]
2351 fn increment_len(&mut self, increment: usize) {
2352 self.local_len += increment;
2353 }
2354}
2355
2356impl<'a> Drop for SetLenOnDrop<'a> {
2357 #[inline]
2358 fn drop(&mut self) {
2359 *self.len = self.local_len;
2360 }
2361}
2362
2363#[cfg(feature = "const_new")]
2364impl<T, const N: usize> SmallVec<[T; N]> {
2365 /// Construct an empty vector.
2366 ///
2367 /// 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.
2368 #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
2369 #[inline]
2370 pub const fn new_const() -> Self {
2371 SmallVec {
2372 capacity: 0,
2373 data: SmallVecData::from_const(MaybeUninit::uninit()),
2374 }
2375 }
2376
2377 /// The array passed as an argument is moved to be an inline version of `SmallVec`.
2378 ///
2379 /// 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.
2380 #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
2381 #[inline]
2382 pub const fn from_const(items: [T; N]) -> Self {
2383 SmallVec {
2384 capacity: N,
2385 data: SmallVecData::from_const(MaybeUninit::new(items)),
2386 }
2387 }
2388
2389 /// Constructs a new `SmallVec` on the stack from an array without
2390 /// copying elements. Also sets the length. The user is responsible
2391 /// for ensuring that `len <= N`.
2392 ///
2393 /// 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.
2394 #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))]
2395 #[inline]
2396 pub const unsafe fn from_const_with_len_unchecked(items: [T; N], len: usize) -> Self {
2397 SmallVec {
2398 capacity: len,
2399 data: SmallVecData::from_const(MaybeUninit::new(items)),
2400 }
2401 }
2402}
2403
2404#[cfg(feature = "const_generics")]
2405#[cfg_attr(docsrs, doc(cfg(feature = "const_generics")))]
2406unsafe impl<T, const N: usize> Array for [T; N] {
2407 type Item = T;
2408 #[inline]
2409 fn size() -> usize {
2410 N
2411 }
2412}
2413
2414#[cfg(not(feature = "const_generics"))]
2415macro_rules! impl_array(
2416 ($($size:expr),+) => {
2417 $(
2418 unsafe impl<T> Array for [T; $size] {
2419 type Item = T;
2420 #[inline]
2421 fn size() -> usize { $size }
2422 }
2423 )+
2424 }
2425);
2426
2427#[cfg(not(feature = "const_generics"))]
2428impl_array!(
2429 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,
2430 26, 27, 28, 29, 30, 31, 32, 36, 0x40, 0x60, 0x80, 0x100, 0x200, 0x400, 0x600, 0x800, 0x1000,
2431 0x2000, 0x4000, 0x6000, 0x8000, 0x10000, 0x20000, 0x40000, 0x60000, 0x80000, 0x10_0000
2432);
2433
2434/// Convenience trait for constructing a `SmallVec`
2435pub trait ToSmallVec<A: Array> {
2436 /// Construct a new `SmallVec` from a slice.
2437 fn to_smallvec(&self) -> SmallVec<A>;
2438}
2439
2440impl<A: Array> ToSmallVec<A> for [A::Item]
2441where
2442 A::Item: Copy,
2443{
2444 #[inline]
2445 fn to_smallvec(&self) -> SmallVec<A> {
2446 SmallVec::from_slice(self)
2447 }
2448}
2449
2450// Immutable counterpart for `NonNull<T>`.
2451#[repr(transparent)]
2452struct ConstNonNull<T>(NonNull<T>);
2453
2454impl<T> ConstNonNull<T> {
2455 #[inline]
2456 fn new(ptr: *const T) -> Option<Self> {
2457 NonNull::new(ptr as *mut T).map(Self)
2458 }
2459 #[inline]
2460 fn as_ptr(self) -> *const T {
2461 self.0.as_ptr()
2462 }
2463}
2464
2465impl<T> Clone for ConstNonNull<T> {
2466 #[inline]
2467 fn clone(&self) -> Self {
2468 *self
2469 }
2470}
2471
2472impl<T> Copy for ConstNonNull<T> {}
2473