//! Contains the `FixedVec` implementation.
//!
//! [See `FixedVec` for the main information][`FixedVec`].
//!
//! [`FixedVec`]: struct.FixedVec.html
use core::{borrow, cmp, hash, ops, ptr, slice};
use crate::uninit::Uninit;
/// A `Vec`-like structure that does not manage its allocation.
///
/// This vector type will never (re-)allocate but it can also not free underused memory. As opposed
/// to other similar crates, it does require and additional bounds on its type parameter as it
/// truly manages uninitialized memory to store instances.
///
/// # Basic Usage
///
/// It is easy to use a local array or slice of `MaybeUninit` for the storage of a `FixedVec`. Note
/// that, similar to the allocated standard `Vec`, the underlying memory not being stored inline
/// makes moves and splitting much cheaper.
///
/// ```
/// use core::mem::MaybeUninit;
/// use static_alloc::FixedVec;
///
/// let mut memory: [MaybeUninit<usize>; 15] = [MaybeUninit::uninit(); 15];
/// let mut stack = FixedVec::new((&mut memory[..]).into());
///
/// stack.push(1);
/// stack.push(2);
/// stack.push(3);
/// while let Some(top) = stack.pop() {
/// // Prints 3, 2, 1
/// println!("{}", top);
/// }
/// ```
///
/// ## With `Slab`
///
/// One focus of the library is composability. It should not be surprising that `FixedVec`
/// interacts with the [`Slab`] allocator, which implements a specialized interface providing the
/// [`Uninit`] type instead of a raw `*const u8`. Hence, the `FixedVec` can use this instead of its
/// own local stack variables.
///
/// ```
/// use static_alloc::{FixedVec, Slab};
///
/// let alloc: Slab<[u8; 1 << 12]> = Slab::uninit();
/// let some_usize = alloc.leak(0_usize).unwrap();
///
/// // Allocate a vector with capacity `1` from the slab.
/// let mut vec = alloc.fixed_vec(1).unwrap();
///
/// // Push the reference to the other allocation.
/// vec.push(&mut *some_usize);
///
/// // … do something else
///
/// // Ensure lifetimes work out.
/// drop(vec);
///
/// // Hooray, now once again unborrowed.
/// *some_usize = 0;
/// ```
///
/// ## The [`from_unaligned`] constructor
///
/// It is possible to place a `FixedVec` into an uninitialized memory, not only the `Uninit<[T]>`
/// that the [`new`] constructor requires. This will align the underlying memory suitably and
/// substitute a dangling empty slice if that is not possible.
///
/// ```
/// use core::mem::MaybeUninit;
/// use static_alloc::{FixedVec, Uninit};
///
/// struct MyStruct {
/// // ..
/// # _private: [usize; 1],
/// }
///
/// let mut memory: MaybeUninit<[u8; 1024]> = MaybeUninit::uninit();
/// let uninit = Uninit::from(&mut memory);
///
/// // NO guarantees about space lost from required additional aligning.
/// let mut vec: FixedVec<MyStruct> = FixedVec::from_unaligned(uninit);
/// ```
///
/// [`Slab`]: ../slab/struct.Slab.html
/// [`Uninit`]: ../uninit/struct.Uninit.html
/// [`new`]: #method.new
/// [`from_unaligned`]: #method.from_unaligned
pub struct FixedVec<'a, T> {
uninit: Uninit<'a, [T]>,
length: usize,
}
/// An iterator removing a range of elements from a `FixedVec`.
///
/// See [`FixedVec::drain`] for more information.
///
/// [`FixedVec::drain`]: struct.FixedVec.html#method.drain
pub struct Drain<'a, T> {
/// Number of elements drained.
count: usize,
/// The start of the tail (relative to `elements`), inbounds offset for `elements`.
tail: usize,
/// The length of the tail.
tail_len: usize,
/// Pointer to first element to drain (and to write to on `Drop`).
elements: ptr::NonNull<T>,
/// The length field of the underlying `FixedVec`.
len: &'a mut usize,
}
impl<T> FixedVec<'_, T> {
/// Shorten the vector to a maximum length.
///
/// If the length is not larger than `len` this has no effect.
///
/// The tail of the vector is dropped starting from the last element. This order is opposite to
/// `.drain(len..).for_each(drop)`. `truncate` provides the extra guarantee that a `panic`
/// during `Drop` of one element effectively stops the truncation at that point, instead of
/// leaking unspecified other content of the vector. This means that other elements are still
/// dropped when unwinding eventually drops the `FixedVec` itself.
///
/// ## Example
///
/// ```
/// # use core::mem::MaybeUninit;
/// # use static_alloc::{FixedVec, Uninit};
///
/// let mut memory: [MaybeUninit<usize>; 4] = [MaybeUninit::uninit(); 4];
/// let mut vec = FixedVec::new(Uninit::from(&mut memory[..]));
///
/// vec.push(0usize);
/// vec.push(1usize);
/// vec.push(2usize);
///
/// assert_eq!(vec.as_slice(), [0, 1, 2]);
/// vec.truncate(1);
/// assert_eq!(vec.as_slice(), [0]);
/// ```
pub fn truncate(&mut self, len: usize) {
struct SetLenOnDrop<'a> {
len: &'a mut usize,
local_len: usize,
}
impl Drop for SetLenOnDrop<'_> {
fn drop(&mut self) {
*self.len = self.local_len;
}
}
let mut ptr = self.end_mut_ptr();
let current_length = self.length;
let mut set_len = SetLenOnDrop { len: &mut self.length, local_len: current_length };
for _ in len..current_length {
set_len.local_len -= 1;
unsafe {
ptr = ptr.offset(-1);
ptr::drop_in_place(ptr);
}
}
}
/// Extracts a slice containing the entire vector.
pub fn as_slice(&self) -> &[T] {
unsafe {
// SAFETY: length is the number of initialized elements.
slice::from_raw_parts(self.uninit.as_begin_ptr(), self.length)
}
}
/// Extracts the mutable slice containing the entire vector.
pub fn as_mut_slice(&mut self) -> &mut [T] {
unsafe {
// SAFETY:
// * length is the number of initialized elements.
// * unaliased since we take ourselves by `mut` and `uninit` does the rest.
slice::from_raw_parts_mut(self.uninit.as_begin_ptr(), self.length)
}
}
/// Remove all elements.
///
/// This is an alias for [`truncate(0)`][truncate].
///
/// [truncate]: #method.truncate
pub fn clear(&mut self) {
self.truncate(0)
}
/// Returns the number of elements in the vector.
pub fn len(&self) -> usize {
self.length
}
/// Set the raw length.
///
/// ## Safety
/// * `new_len` must be smaller or equal `self.capacity()`
/// * The caller must ensure that all newly referenced elements are properly initialized.
pub unsafe fn set_len(&mut self, new_len: usize) {
self.length = new_len;
}
/// Returns the number of elements the vector can hold.
pub fn capacity(&self) -> usize {
self.uninit.capacity()
}
/// Returns `true` if the vector contains no elements.
pub fn is_empty(&self) -> bool {
self.length == 0
}
/// Appends an element to the back of a collection.
///
/// Return `Err(val)` if it is not possible to append the element.
///
/// ```
/// use static_alloc::{FixedVec, Uninit};
/// use core::mem::MaybeUninit;
///
/// // Only enough storage for one element.
/// let mut allocation: [MaybeUninit<u32>; 1] = [MaybeUninit::uninit()];
/// let mut vec = FixedVec::new(Uninit::from(&mut allocation[..]));
///
/// // First push succeeds.
/// assert_eq!(vec.push(1), Ok(()));
///
/// // The second push fails.
/// assert_eq!(vec.push(2), Err(2));
///
/// ```
pub fn push(&mut self, val: T) -> Result<(), T> {
if self.length == usize::max_value() {
return Err(val);
}
let init = match self.head_tail_mut().1.split_first() {
Some(init) => init,
None => return Err(val),
};
init.init(val);
self.length += 1;
Ok(())
}
/// Removes the last element from a vector and returns it, or `None` if it is empty.
pub fn pop(&mut self) -> Option<T> {
if self.length == 0 {
return None;
}
let last = self.head_tail_mut().0.split_last().unwrap();
let val = unsafe {
// SAFETY: initialized and no reference of any kind exists to it.
ptr::read(last.as_ptr())
};
self.length -= 1;
Some(val)
}
/// Split the capacity into a *borrowed* other vector.
///
/// The other vector borrows the underlying memory resource while it is alive.
///
/// This is a specialized method not found in the standard `Vec` as it relies on `FixedVec` not
/// owning the allocation itself. This avoids splitting the underlying allocation which would
/// require `unsafe` to mend the parts together.
///
/// ## Panics
/// This method panics if `at > self.capacity()`.
///
/// ## Examples
///
/// ```
/// use static_alloc::{FixedVec, Slab};
///
/// let mut memory: Slab<[usize; 8]> = Slab::uninit();
/// let mut vec = memory.fixed_vec::<usize>(8).unwrap();
/// vec.fill(0..7);
///
/// // Can use like a vector:
/// let mut part = vec.split_borrowed(4);
/// assert!(part.push(7).is_ok());
/// assert!((4..8).eq(part.drain(..)));
///
/// // Drop to rescind the borrow on `vec`.
/// drop(part);
///
/// // All split elements are gone
/// assert_eq!(vec.len(), 4);
/// // But retained all capacity
/// assert_eq!(vec.capacity(), 8);
/// ```
#[must_use = "Elements in the split tail will be dropped. Prefer `truncate(at)` or `drain(at..)` if there is no other use."]
pub fn split_borrowed(&mut self, at: usize) -> FixedVec<'_, T> {
assert!(at <= self.capacity(), "`at` out of bounds");
let new_uninit = self.uninit.borrow_mut().split_at(at).unwrap();
let new_len = self.length.saturating_sub(at);
self.length -= new_len;
FixedVec {
uninit: new_uninit,
length: new_len,
}
}
/// Split the capacity of the collection into two at a given index.
///
/// In contrast to `Vec::split_off` calling this method reduces the capacity of `self` to `at`.
///
/// ## Panics
/// This method panics if `at > self.capacity()`.
pub fn split_and_shrink_to(&mut self, at: usize) -> Self {
assert!(at <= self.capacity(), "`at` out of bounds");
// `self.length` is always smaller than `split_at`.
let new_uninit = self.uninit.split_at(at).unwrap();
// The first `at` elements stay in this vec.
let new_len = self.length.saturating_sub(at);
self.length -= new_len;
FixedVec {
uninit: new_uninit,
length: new_len,
}
}
/// Extend the vector with as many elements as fit.
///
/// Returns the iterator with all elements that were not pushed into the vector.
pub fn fill<I: IntoIterator<Item=T>>(&mut self, iter: I)
-> I::IntoIter
{
let unused = self.capacity() - self.len();
let mut iter = iter.into_iter();
for item in iter.by_ref().take(unused) {
unsafe {
*self.end_mut_ptr() = item;
self.set_len(self.length + 1);
}
}
iter
}
/// Creates a draining iterator that yields and removes elements a given range.
///
/// It is unspecified which elements are removed if the `Drain` is never dropped. If you
/// require precise semantics even in this case you might be able to swap the range to the back
/// of the vector and invoke [`split_and_shrink_to`].
///
/// [`split_and_shrink_to`]: #method.split_and_shrink_to
pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>
where R: ops::RangeBounds<usize>
{
let len = self.len();
let start = match range.start_bound() {
ops::Bound::Included(&n) => n,
ops::Bound::Excluded(&n) => n + 1,
ops::Bound::Unbounded => 0,
};
let end = match range.end_bound() {
ops::Bound::Included(&n) => n + 1,
ops::Bound::Excluded(&n) => n,
ops::Bound::Unbounded => len,
};
assert!(start <= end);
assert!(end <= len);
let elements = unsafe {
// SAFETY:
// Within allocation since `start <= len` and len is at most the
// one-past-the-end pointer. Pointer within are also never null.
//
// In particular we can shorten the length. We initially shorten
// the length until all elements are drained. The Drain will
// increase the length by `len - end` elements which will still be
// within the bounds of the allocation as `start <= end`.
self.set_len(start);
ptr::NonNull::new_unchecked(self.as_mut_ptr().add(start))
};
Drain {
// Internal invariant: `count <= tail`.
count: 0,
// Relative to `elements`. inbounds of original `as_mut_ptr()`.
tail: end - start,
tail_len: len - end,
elements,
len: &mut self.length,
}
}
fn head_tail_mut(&mut self) -> (Uninit<'_, [T]>, Uninit<'_, [T]>) {
// Borrow, do not affect the actual allocation by throwing away possible elements.
let mut all = self.uninit.borrow_mut();
// This must always be possible. `self.length` is nevery greater than the capacity.
let tail = all.split_at(self.length).unwrap();
(all, tail)
}
fn end_mut_ptr(&mut self) -> *mut T {
unsafe { self.as_mut_ptr().add(self.length) }
}
}
impl<'a, T> FixedVec<'a, T> {
/// Create a `FixedVec` in a pre-allocated region.
///
/// The capacity will be that of the underlying allocation.
pub fn new(uninit: Uninit<'a, [T]>) -> Self {
FixedVec {
uninit,
length: 0,
}
}
/// Create a `FixedVec` with as large of a capacity as available.
///
/// When no aligned slice can be create within the provided memory then the constructor will
/// fallback to an empty dangling slice.
///
/// This is only a utility function which may be lossy as data before the alignment is
/// discarded. Prefer an explicit [`Uninit::cast_slice`] followed by error handling if this is
/// undesirable.
///
/// [`Uninit::cast_slice`]: ../uninit/struct.Uninit.html#method.cast_slice
pub fn from_unaligned<U: ?Sized>(generic: Uninit<'a, U>) -> Self {
let mut uninit = generic.as_memory();
let slice = uninit.split_slice().unwrap_or_else(Uninit::empty);
Self::new(slice)
}
/// Return trailing bytes that can not be used by the `FixedVec`.
///
/// This operation is idempotent.
pub fn shrink_to_fit(&mut self) -> Uninit<'a, ()> {
self.uninit.shrink_to_fit()
}
}
impl<T> Drain<'_, T> {
/// View the remaining data as a slice.
///
/// Similar to `slice::Iter::as_slice` but you are not allowed to use the iterator as it will
/// invalidate the pointees. This is an extended form of `Peekable::peek`.
pub fn as_slice(&self) -> &[T] {
unsafe {
// SAFETY: all indices up to `tail` are inbounds. Internal invariant guarantees `count`
// is smaller.
slice::from_raw_parts(
self.elements.as_ptr().add(self.count),
self.tail - self.count)
}
}
/// View the remaining data as a mutable slice.
///
/// This is `Peekable::peek` on steroids.
pub fn as_mut_slice(&mut self) -> &mut [T] {
unsafe {
// SAFETY: all indices up to `tail` are inbounds. Internal invariant guarantees `count`
// is smaller. Not aliased as it mutably borrows the `Drain`.
slice::from_raw_parts_mut(
self.elements.as_ptr().add(self.count),
self.tail - self.count)
}
}
}
impl<T> ops::Deref for FixedVec<'_, T> {
type Target = [T];
fn deref(&self) -> &[T] {
self.as_slice()
}
}
impl<T> ops::DerefMut for FixedVec<'_, T> {
fn deref_mut(&mut self) -> &mut [T] {
self.as_mut_slice()
}
}
impl<T> Drop for FixedVec<'_, T> {
fn drop(&mut self) {
unsafe {
ptr::drop_in_place(self.as_mut_slice())
}
}
}
impl<T, I> ops::Index<I> for FixedVec<'_, T>
where I: slice::SliceIndex<[T]>,
{
type Output = I::Output;
fn index(&self, idx: I) -> &I::Output {
ops::Index::index(&**self, idx)
}
}
impl<T, I> ops::IndexMut<I> for FixedVec<'_, T>
where I: slice::SliceIndex<[T]>,
{
fn index_mut(&mut self, idx: I) -> &mut I::Output {
ops::IndexMut::index_mut(&mut**self, idx)
}
}
impl<'a, 'b, T: PartialEq> PartialEq<FixedVec<'b, T>> for FixedVec<'a, T> {
#[inline]
fn eq(&self, other: &FixedVec<T>) -> bool {
PartialEq::eq(&**self, &**other)
}
#[inline]
fn ne(&self, other: &FixedVec<T>) -> bool {
PartialEq::ne(&**self, &**other)
}
}
impl<'a, 'b, T: PartialOrd> PartialOrd<FixedVec<'b, T>> for FixedVec<'a, T> {
#[inline]
fn partial_cmp(&self, other: &FixedVec<T>) -> Option<cmp::Ordering> {
PartialOrd::partial_cmp(&**self, &**other)
}
#[inline]
fn lt(&self, other: &FixedVec<T>) -> bool {
PartialOrd::lt(&**self, &**other)
}
#[inline]
fn le(&self, other: &FixedVec<T>) -> bool {
PartialOrd::le(&**self, &**other)
}
#[inline]
fn ge(&self, other: &FixedVec<T>) -> bool {
PartialOrd::ge(&**self, &**other)
}
#[inline]
fn gt(&self, other: &FixedVec<T>) -> bool {
PartialOrd::gt(&**self, &**other)
}
}
impl<T: Ord> Ord for FixedVec<'_, T> {
#[inline]
fn cmp(&self, other: &FixedVec<T>) -> cmp::Ordering {
Ord::cmp(&**self, &**other)
}
}
impl<T: Eq> Eq for FixedVec<'_, T> { }
impl<T: hash::Hash> hash::Hash for FixedVec<'_, T> {
fn hash<H: hash::Hasher>(&self, state: &mut H) {
hash::Hash::hash(&**self, state)
}
}
impl<T> borrow::Borrow<[T]> for FixedVec<'_, T> {
fn borrow(&self) -> &[T] {
&**self
}
}
impl<T> borrow::BorrowMut<[T]> for FixedVec<'_, T> {
fn borrow_mut(&mut self) -> &mut [T] {
&mut **self
}
}
impl<T> AsRef<[T]> for FixedVec<'_, T> {
fn as_ref(&self) -> &[T] {
&**self
}
}
impl<T> AsMut<[T]> for FixedVec<'_, T> {
fn as_mut(&mut self) -> &mut [T] {
&mut **self
}
}
impl<T> Iterator for Drain<'_, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.count == self.tail {
return None;
}
let t = unsafe {
// SAFETY: `count <= self.tail` and `tail` is always in bounds.
ptr::read(self.elements.as_ptr().add(self.count))
};
self.count += 1;
Some(t)
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.count..self.tail).size_hint()
}
}
impl<T> Drop for Drain<'_, T> {
fn drop(&mut self) {
self.for_each(drop);
if self.tail_len != 0 {
unsafe {
let source = self.elements.as_ptr().add(self.tail);
ptr::copy(source, self.elements.as_ptr(), self.tail_len);
}
// Restore the tail to the vector.
*self.len += self.tail_len;
}
}
}
#[cfg(test)]
mod tests {
use super::FixedVec;
use crate::Uninit;
use core::mem::MaybeUninit;
use core::sync::atomic::{AtomicUsize, Ordering};
#[test]
fn init_and_use() {
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Foo(usize);
const CAPACITY: usize = 30;
let mut allocation: [MaybeUninit<Foo>; 30] = [MaybeUninit::uninit(); 30];
let mut vec = FixedVec::new((&mut allocation[..]).into());
assert_eq!(vec.capacity(), CAPACITY);
assert_eq!(vec.len(), 0);
for i in 0..CAPACITY {
assert_eq!(vec.push(Foo(i)), Ok(()));
}
assert_eq!(vec.capacity(), CAPACITY);
assert_eq!(vec.len(), CAPACITY);
for i in (0..CAPACITY).rev() {
assert_eq!(vec.pop(), Some(Foo(i)));
}
assert_eq!(vec.capacity(), CAPACITY);
assert_eq!(vec.len(), 0);
}
#[test]
fn zst_drop() {
const COUNT: usize = 30;
static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0);
struct HasDrop(usize);
impl Drop for HasDrop {
fn drop(&mut self) {
DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
}
}
let mut allocation: MaybeUninit<[HasDrop; COUNT]> = MaybeUninit::uninit();
let uninit = Uninit::from_maybe_uninit(&mut allocation);
let mut vec = FixedVec::new(uninit.cast_slice().unwrap());
for i in 0..COUNT {
assert!(vec.push(HasDrop(i)).is_ok());
}
drop(vec);
assert_eq!(DROP_COUNTER.load(Ordering::SeqCst), COUNT);
}
#[test]
fn zst() {
struct Zst;
let vec = FixedVec::<Zst>::new(Uninit::empty());
assert_eq!(vec.capacity(), usize::max_value());
}
#[test]
fn split_and_shrink() {
// Zeroed because we want to test the contents.
let mut allocation: MaybeUninit<[u16; 8]> = MaybeUninit::zeroed();
let mut aligned = Uninit::from(&mut allocation).as_memory();
let _ = aligned.split_at_byte(15);
let mut vec = FixedVec::new(aligned.cast_slice().unwrap());
let mut second = vec.split_and_shrink_to(4);
let tail = second.shrink_to_fit();
assert_eq!(vec.capacity(), 4);
assert_eq!(vec.shrink_to_fit().size(), 0);
assert_eq!(second.capacity(), 3);
assert_eq!(second.shrink_to_fit().size(), 0);
assert_eq!(tail.size(), 1);
let _ = tail.cast::<u8>().unwrap().init(0xFF);
(0_u16..4).for_each(|v| assert!(vec.push(v).is_ok()));
(4..7).for_each(|v| assert!(second.push(v).is_ok()));
assert_eq!(vec.len(), 4);
assert_eq!(second.len(), 3);
drop(vec);
drop(second);
assert_eq!(
&unsafe { *allocation.as_ptr() }[..7],
[0, 1, 2, 3, 4, 5, 6]);
}
/// Tests panics during truncation behave as expected.
///
/// Unwinding started in a panic during truncation should not effect `Drop` calls when the
/// `Vec` itself is hit by the unwinding. We test this by voluntarily triggering an unwinding
/// and counting the number of values which have been dropped regularly (that is, during the
/// `Drop` of `Vec` when it is unwound).
///
/// Note that this test is already `should_panic` and the observable failure is thus an abort
/// from a double panic!
#[test]
#[should_panic = "Trigger triggered"]
fn drop_safe_in_truncation() {
use core::cell::Cell;
#[derive(Debug)]
struct Trigger<'a> {
panic_on_drop: bool,
dropped_counter: &'a Cell<usize>,
}
impl Drop for Trigger<'_> {
fn drop(&mut self) {
if self.panic_on_drop { panic!("Trigger triggered") }
// Record this as a normal drop.
self.dropped_counter.set(self.dropped_counter.get() + 1);
}
}
struct AbortMismatchedDropCount<'a> {
counter: &'a Cell<usize>,
expected: usize,
}
impl Drop for AbortMismatchedDropCount<'_> {
fn drop(&mut self) {
struct ForceDupPanic;
impl Drop for ForceDupPanic {
fn drop(&mut self) { panic!() }
}
if self.expected != self.counter.get() {
// For duplicate panic, and thus abort
let _x = ForceDupPanic;
panic!();
}
}
}
let mut allocation: MaybeUninit<[Trigger<'static>; 3]> = MaybeUninit::zeroed();
let drops = Cell::new(0);
// Is `Drop`ed *after* the Vec, and will record the number of usually dropped Triggers.
let _abort_mismatch_raii = AbortMismatchedDropCount {
counter: &drops,
expected: 2,
};
let uninit = Uninit::from(&mut allocation).as_memory();
let mut vec = FixedVec::new(uninit.cast_slice().unwrap());
vec.push(Trigger { panic_on_drop: false, dropped_counter: &drops }).unwrap();
// This one is within the truncated tail but is not dropped until unwind as truncate
// panics. If we were to skip dropping all values of the tail in unwind we'd notice.
vec.push(Trigger { panic_on_drop: false, dropped_counter: &drops }).unwrap();
vec.push(Trigger { panic_on_drop: true, dropped_counter: &drops }).unwrap();
// Trigger!
vec.truncate(1);
}
}