| #[cfg(feature = "read")] |
| use alloc::boxed::Box; |
| #[cfg(feature = "read")] |
| use alloc::vec::Vec; |
| use core::fmt; |
| use core::mem::MaybeUninit; |
| use core::ops; |
| use core::ptr; |
| use core::slice; |
| |
| mod sealed { |
| // SAFETY: Implementer must not modify the content in storage. |
| pub unsafe trait Sealed { |
| type Storage; |
| |
| fn new_storage() -> Self::Storage; |
| |
| fn grow(_storage: &mut Self::Storage, _additional: usize) -> Result<(), CapacityFull> { |
| Err(CapacityFull) |
| } |
| } |
| |
| #[derive(Clone, Copy, Debug)] |
| pub struct CapacityFull; |
| } |
| |
| use sealed::*; |
| |
| /// Marker trait for types that can be used as backing storage when a growable array type is needed. |
| /// |
| /// This trait is sealed and cannot be implemented for types outside this crate. |
| pub trait ArrayLike: Sealed { |
| /// Type of the elements being stored. |
| type Item; |
| |
| #[doc(hidden)] |
| fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<Self::Item>]; |
| |
| #[doc(hidden)] |
| fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<Self::Item>]; |
| } |
| |
| // Use macro since const generics can't be used due to MSRV. |
| macro_rules! impl_array { |
| () => {}; |
| ($n:literal $($rest:tt)*) => { |
| // SAFETY: does not modify the content in storage. |
| unsafe impl<T> Sealed for [T; $n] { |
| type Storage = [MaybeUninit<T>; $n]; |
| |
| fn new_storage() -> Self::Storage { |
| // SAFETY: An uninitialized `[MaybeUninit<_>; _]` is valid. |
| unsafe { MaybeUninit::uninit().assume_init() } |
| } |
| } |
| |
| impl<T> ArrayLike for [T; $n] { |
| type Item = T; |
| |
| fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] { |
| storage |
| } |
| |
| fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] { |
| storage |
| } |
| } |
| |
| impl_array!($($rest)*); |
| } |
| } |
| |
| impl_array!(0 1 2 3 4 8 16 32 64 128 192); |
| |
| #[cfg(feature = "read")] |
| unsafe impl<T> Sealed for Vec<T> { |
| type Storage = Box<[MaybeUninit<T>]>; |
| |
| fn new_storage() -> Self::Storage { |
| Box::new([]) |
| } |
| |
| fn grow(storage: &mut Self::Storage, additional: usize) -> Result<(), CapacityFull> { |
| let mut vec: Vec<_> = core::mem::replace(storage, Box::new([])).into(); |
| vec.reserve(additional); |
| // SAFETY: This is a `Vec` of `MaybeUninit`. |
| unsafe { vec.set_len(vec.capacity()) }; |
| *storage = vec.into_boxed_slice(); |
| Ok(()) |
| } |
| } |
| |
| #[cfg(feature = "read")] |
| impl<T> ArrayLike for Vec<T> { |
| type Item = T; |
| |
| fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] { |
| storage |
| } |
| |
| fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] { |
| storage |
| } |
| } |
| |
| pub(crate) struct ArrayVec<A: ArrayLike> { |
| storage: A::Storage, |
| len: usize, |
| } |
| |
| impl<A: ArrayLike> ArrayVec<A> { |
| pub fn new() -> Self { |
| Self { |
| storage: A::new_storage(), |
| len: 0, |
| } |
| } |
| |
| pub fn clear(&mut self) { |
| let ptr: *mut [A::Item] = &mut **self; |
| // Set length first so the type invariant is upheld even if `drop_in_place` panicks. |
| self.len = 0; |
| // SAFETY: `ptr` contains valid elements only and we "forget" them by setting the length. |
| unsafe { ptr::drop_in_place(ptr) }; |
| } |
| |
| pub fn try_push(&mut self, value: A::Item) -> Result<(), CapacityFull> { |
| let mut storage = A::as_mut_slice(&mut self.storage); |
| if self.len >= storage.len() { |
| A::grow(&mut self.storage, 1)?; |
| storage = A::as_mut_slice(&mut self.storage); |
| } |
| |
| storage[self.len] = MaybeUninit::new(value); |
| self.len += 1; |
| Ok(()) |
| } |
| |
| pub fn try_insert(&mut self, index: usize, element: A::Item) -> Result<(), CapacityFull> { |
| assert!(index <= self.len); |
| |
| let mut storage = A::as_mut_slice(&mut self.storage); |
| if self.len >= storage.len() { |
| A::grow(&mut self.storage, 1)?; |
| storage = A::as_mut_slice(&mut self.storage); |
| } |
| |
| // SAFETY: storage[index] is filled later. |
| unsafe { |
| let p = storage.as_mut_ptr().add(index); |
| core::ptr::copy(p as *const _, p.add(1), self.len - index); |
| } |
| storage[index] = MaybeUninit::new(element); |
| self.len += 1; |
| Ok(()) |
| } |
| |
| pub fn pop(&mut self) -> Option<A::Item> { |
| if self.len == 0 { |
| None |
| } else { |
| self.len -= 1; |
| // SAFETY: this element is valid and we "forget" it by setting the length. |
| Some(unsafe { A::as_slice(&mut self.storage)[self.len].as_ptr().read() }) |
| } |
| } |
| |
| pub fn swap_remove(&mut self, index: usize) -> A::Item { |
| assert!(self.len > 0); |
| A::as_mut_slice(&mut self.storage).swap(index, self.len - 1); |
| self.pop().unwrap() |
| } |
| } |
| |
| #[cfg(feature = "read")] |
| impl<T> ArrayVec<Vec<T>> { |
| pub fn into_vec(mut self) -> Vec<T> { |
| let len = core::mem::replace(&mut self.len, 0); |
| let storage = core::mem::replace(&mut self.storage, Box::new([])); |
| let slice = Box::leak(storage); |
| debug_assert!(len <= slice.len()); |
| // SAFETY: valid elements. |
| unsafe { Vec::from_raw_parts(slice.as_mut_ptr() as *mut T, len, slice.len()) } |
| } |
| } |
| |
| impl<A: ArrayLike> Drop for ArrayVec<A> { |
| fn drop(&mut self) { |
| self.clear(); |
| } |
| } |
| |
| impl<A: ArrayLike> Default for ArrayVec<A> { |
| fn default() -> Self { |
| Self::new() |
| } |
| } |
| |
| impl<A: ArrayLike> ops::Deref for ArrayVec<A> { |
| type Target = [A::Item]; |
| |
| fn deref(&self) -> &[A::Item] { |
| let slice = &A::as_slice(&self.storage); |
| debug_assert!(self.len <= slice.len()); |
| // SAFETY: valid elements. |
| unsafe { slice::from_raw_parts(slice.as_ptr() as _, self.len) } |
| } |
| } |
| |
| impl<A: ArrayLike> ops::DerefMut for ArrayVec<A> { |
| fn deref_mut(&mut self) -> &mut [A::Item] { |
| let slice = &mut A::as_mut_slice(&mut self.storage); |
| debug_assert!(self.len <= slice.len()); |
| // SAFETY: valid elements. |
| unsafe { slice::from_raw_parts_mut(slice.as_mut_ptr() as _, self.len) } |
| } |
| } |
| |
| impl<A: ArrayLike> Clone for ArrayVec<A> |
| where |
| A::Item: Clone, |
| { |
| fn clone(&self) -> Self { |
| let mut new = Self::default(); |
| for value in &**self { |
| new.try_push(value.clone()).unwrap(); |
| } |
| new |
| } |
| } |
| |
| impl<A: ArrayLike> PartialEq for ArrayVec<A> |
| where |
| A::Item: PartialEq, |
| { |
| fn eq(&self, other: &Self) -> bool { |
| **self == **other |
| } |
| } |
| |
| impl<A: ArrayLike> Eq for ArrayVec<A> where A::Item: Eq {} |
| |
| impl<A: ArrayLike> fmt::Debug for ArrayVec<A> |
| where |
| A::Item: fmt::Debug, |
| { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| fmt::Debug::fmt(&**self, f) |
| } |
| } |