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