dst_container/

fixed_vec.rs

use crate::*;
use std::{
    alloc::{handle_alloc_error, AllocError, Allocator, Global, Layout},
    iter::FusedIterator,
    mem::forget,
    ops::{Index, IndexMut, RangeFull},
    ptr::{drop_in_place, NonNull},
    slice::SliceIndex,
};

#[derive(Clone, Copy)]
struct FixedAlloc<T: ?Sized> {
    alloc: Global,
    metadata: <T as Pointee>::Metadata,
}

impl<T: ?Sized> FixedAlloc<T> {
    pub const fn new(metadata: <T as Pointee>::Metadata) -> Self {
        Self {
            alloc: Global,
            metadata,
        }
    }

    #[inline]
    pub const fn metadata(&self) -> <T as Pointee>::Metadata {
        self.metadata
    }

    #[inline]
    pub unsafe fn layout(&self) -> Layout {
        Layout::for_value_raw(std::ptr::from_raw_parts::<T>(
            std::ptr::null::<()>(),
            self.metadata,
        ))
    }

    #[inline]
    pub unsafe fn align_layout(&self, layout: Layout) -> Layout {
        let single_layout = self.layout();
        let layout = Layout::from_size_align_unchecked(
            layout.size(),
            layout.align().max(single_layout.align()),
        );
        layout.pad_to_align()
    }
}

unsafe impl<T: ?Sized> Allocator for FixedAlloc<T> {
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        let layout = unsafe { self.align_layout(layout) };
        self.alloc.allocate(layout)
    }

    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
        let layout = self.align_layout(layout);
        self.alloc.deallocate(ptr, layout)
    }
}

/// A vector designed for DST.
pub struct FixedVec<T: ?Sized>(Vec<u8, FixedAlloc<T>>);

impl<T: ?Sized> FixedVec<T> {
    /// Constructs a new, empty `FixedVec<T>`, with provided metadata.
    ///
    /// The vector will not allocate until elements are pushed onto it.
    ///
    /// # Examples
    ///
    /// ```
    /// # #![allow(unused_mut)]
    /// # use dst_container::*;
    /// let mut vec: FixedVec<UnsizedSlice<u32, u64>> = FixedVec::new(6);
    /// ```
    pub const fn new(metadata: <T as Pointee>::Metadata) -> Self {
        Self(Vec::new_in(FixedAlloc::new(metadata)))
    }

    /// Constructs a new, empty `FixedVec<T>`.
    /// The metadata is obtained from the provided pointer.
    ///
    /// The vector will not allocate until elements are pushed onto it.
    ///
    /// # Examples
    ///
    /// ```
    /// # #![allow(unused_mut)]
    /// # use dst_container::*;
    /// let array = [0u32, 1, 2];
    /// let mut vec: FixedVec<[u32]> = FixedVec::new_like(array.as_slice());
    /// ```
    pub const fn new_like(ptr: *const T) -> Self {
        let (_, metadata) = ptr.to_raw_parts();
        Self::new(metadata)
    }

    /// Constructs a new, empty `FixedVec<T>` with at least the specified capacity.
    pub fn with_capacity(metadata: <T as Pointee>::Metadata, capacity: usize) -> Self {
        let alloc = FixedAlloc::new(metadata);
        let layout = unsafe { alloc.layout() };
        Self(Vec::with_capacity_in(capacity * layout.size(), alloc))
    }

    /// Constructs a new, empty `FixedVec<T>` with at least the specified capacity.
    /// The metadata is obtained from the provided pointer.
    pub fn with_capacity_like(ptr: *const T, capacity: usize) -> Self {
        let (_, metadata) = ptr.to_raw_parts();
        Self::with_capacity(metadata, capacity)
    }

    #[inline]
    fn metadata(&self) -> <T as Pointee>::Metadata {
        self.0.allocator().metadata()
    }

    #[inline]
    unsafe fn layout(&self) -> Layout {
        self.0.allocator().layout()
    }

    #[inline]
    fn item_size(&self) -> usize {
        unsafe { self.layout() }.size()
    }

    #[inline]
    fn start_index(&self, index: usize) -> usize {
        index * self.item_size()
    }

    #[inline]
    unsafe fn raw(&self, index: usize) -> &T {
        let start = self.start_index(index);
        let start_ptr = self.0.as_ptr().add(start);
        &*std::ptr::from_raw_parts(start_ptr as *mut (), self.metadata())
    }

    #[inline]
    unsafe fn raw_mut(&mut self, index: usize) -> &mut T {
        let start = self.start_index(index);
        let start_ptr = self.0.as_mut_ptr().add(start);
        &mut *std::ptr::from_raw_parts_mut(start_ptr as *mut (), self.metadata())
    }

    /// Returns the total number of elements the vector can hold without
    /// reallocating.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dst_container::*;
    /// let mut vec: FixedVec<UnsizedSlice<u32, u32>> = FixedVec::with_capacity(3, 10);
    /// // SAFETY: u32 is trivial.
    /// unsafe{ vec.push_with(|_| {}) };
    /// assert_eq!(vec.capacity(), 10);
    /// ```
    pub fn capacity(&self) -> usize {
        self.0.capacity() / self.item_size()
    }

    /// Reserves capacity for at least `additional` more elements to be inserted
    /// in the given `FixedVec<T>`. The collection may reserve more space to
    /// speculatively avoid frequent reallocations. After calling `reserve`,
    /// capacity will be greater than or equal to `self.len() + additional`.
    /// Does nothing if capacity is already sufficient.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity exceeds `isize::MAX` bytes.
    pub fn reserve(&mut self, additional: usize) {
        self.0.reserve(additional * self.item_size())
    }

    /// Shrinks the capacity of the vector as much as possible.
    ///
    /// It will drop down as close as possible to the length but the allocator
    /// may still inform the vector that there is space for a few more elements.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dst_container::*;
    /// let mut vec: FixedVec<UnsizedSlice<u32, u32>> = FixedVec::with_capacity(3, 10);
    /// // SAFETY: u32 is trivial.
    /// unsafe{ vec.push_with(|_| {}) };
    /// assert_eq!(vec.capacity(), 10);
    /// vec.shrink_to_fit();
    /// assert!(vec.capacity() >= 1);
    /// ```
    pub fn shrink_to_fit(&mut self) {
        self.0.shrink_to_fit()
    }

    /// Shrinks the capacity of the vector with a lower bound.
    ///
    /// The capacity will remain at least as large as both the length
    /// and the supplied value.
    ///
    /// If the current capacity is less than the lower limit, this is a no-op.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dst_container::*;
    /// let mut vec: FixedVec<UnsizedSlice<u32, u32>> = FixedVec::with_capacity(3, 10);
    /// // SAFETY: u32 is trivial.
    /// unsafe{ vec.push_with(|_| {}) };
    /// assert_eq!(vec.capacity(), 10);
    /// vec.shrink_to(2);
    /// assert!(vec.capacity() >= 2);
    /// vec.shrink_to(0);
    /// assert!(vec.capacity() >= 1);
    /// ```
    pub fn shrink_to(&mut self, min_capacity: usize) {
        self.0.shrink_to(min_capacity * self.item_size())
    }

    /// Shortens the vector, keeping the first `len` elements and dropping
    /// the rest.
    ///
    /// If `len` is greater than the vector's current length, this has no
    /// effect.
    ///
    /// Note that this method has no effect on the allocated capacity
    /// of the vector.
    ///
    /// # Examples
    ///
    /// Truncating a five element vector to two elements:
    ///
    /// ```
    /// # use dst_container::*;
    /// let mut vec: FixedVec<UnsizedSlice<u32, u32>> = FixedVec::with_capacity(3, 10);
    /// // SAFETY: u32 is trivial.
    /// unsafe{ vec.push_with(|slice| { slice.header.write(1); }) };
    /// unsafe{ vec.push_with(|slice| { slice.header.write(2); }) };
    /// unsafe{ vec.push_with(|slice| { slice.header.write(3); }) };
    /// vec.truncate(2);
    /// assert_eq!(vec.len(), 2);
    /// assert_eq!(vec[0].header, 1);
    /// assert_eq!(vec[1].header, 2);
    /// ```
    ///
    /// No truncation occurs when `len` is greater than the vector's current
    /// length:
    ///
    /// ```
    /// # use dst_container::*;
    /// let mut vec: FixedVec<UnsizedSlice<u32, u32>> = FixedVec::with_capacity(3, 10);
    /// // SAFETY: u32 is trivial.
    /// unsafe{ vec.push_with(|slice| { slice.header.write(1); }) };
    /// unsafe{ vec.push_with(|slice| { slice.header.write(2); }) };
    /// unsafe{ vec.push_with(|slice| { slice.header.write(3); }) };
    /// vec.truncate(8);
    /// assert_eq!(vec.len(), 3);
    /// assert_eq!(vec[0].header, 1);
    /// assert_eq!(vec[1].header, 2);
    /// assert_eq!(vec[2].header, 3);
    /// ```
    ///
    /// Truncating when `len == 0` is equivalent to calling the [`clear`]
    /// method.
    ///
    /// ```
    /// # use dst_container::*;
    /// let mut vec: FixedVec<UnsizedSlice<u32, u32>> = FixedVec::with_capacity(3, 10);
    /// // SAFETY: u32 is trivial.
    /// unsafe{ vec.push_with(|slice| { slice.header.write(1); }) };
    /// unsafe{ vec.push_with(|slice| { slice.header.write(2); }) };
    /// unsafe{ vec.push_with(|slice| { slice.header.write(3); }) };
    /// vec.truncate(0);
    /// assert_eq!(vec.len(), 0);
    /// ```
    ///
    /// [`clear`]: FixedVec::clear
    pub fn truncate(&mut self, len: usize) {
        if len < self.len() {
            for i in len..self.len() {
                unsafe {
                    let raw = self.raw_mut(i);
                    drop_in_place(raw)
                }
            }
            self.0.truncate(len * self.item_size())
        }
    }

    /// Returns a raw pointer to the vector's buffer, or a dangling raw pointer
    /// valid for zero sized reads if the vector didn't allocate.
    ///
    /// The caller must ensure that the vector outlives the pointer this
    /// function returns, or else it will end up pointing to garbage.
    /// Modifying the vector may cause its buffer to be reallocated,
    /// which would also make any pointers to it invalid.
    ///
    /// The caller must also ensure that the memory the pointer (non-transitively) points to
    /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
    /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
    ///
    /// [`as_mut_ptr`]: FixedVec::as_mut_ptr
    #[inline]
    pub fn as_ptr(&self) -> *const T {
        unsafe { self.raw(0) }
    }

    /// Returns an unsafe mutable pointer to the vector's buffer, or a dangling
    /// raw pointer valid for zero sized reads if the vector didn't allocate.
    ///
    /// The caller must ensure that the vector outlives the pointer this
    /// function returns, or else it will end up pointing to garbage.
    /// Modifying the vector may cause its buffer to be reallocated,
    /// which would also make any pointers to it invalid.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(ptr_metadata)]
    /// # use dst_container::*;
    ///
    /// // Allocate vector big enough for 1 elements.
    /// let size = 1;
    /// let mut x: FixedVec<UnsizedSlice<u32, u32>> = FixedVec::with_capacity(2, size);
    /// let x_ptr = x.as_mut_ptr();
    ///
    /// // Initialize elements via raw pointer writes, then set length.
    /// unsafe {
    ///     let u32_ptr = x_ptr.to_raw_parts().0 as *mut u32;
    ///     for i in 0..3 {
    ///         *u32_ptr.add(i) = i as u32;
    ///     }
    ///     x.set_len(size);
    /// }
    /// assert_eq!(x[0].header, 0);
    /// assert_eq!(&x[0].slice, &[1, 2]);
    /// ```
    #[inline]
    pub fn as_mut_ptr(&mut self) -> *mut T {
        unsafe { self.raw_mut(0) }
    }

    /// Forces the length of the vector to `new_len`.
    ///
    /// This is a low-level operation that maintains none of the normal
    /// invariants of the type. Normally changing the length of a vector
    /// is done using one of the safe operations instead, such as
    /// [`truncate`], [`extend`], or [`clear`].
    ///
    /// [`truncate`]: FixedVec::truncate
    /// [`extend`]: Extend::extend
    /// [`clear`]: FixedVec::clear
    ///
    /// # Safety
    ///
    /// - `new_len` must be less than or equal to [`capacity()`].
    /// - The elements at `old_len..new_len` must be initialized.
    ///
    /// [`capacity()`]: FixedVec::capacity
    pub unsafe fn set_len(&mut self, new_len: usize) {
        self.0.set_len(new_len * self.item_size())
    }

    unsafe fn copy_to_box(&self, index: usize) -> Box<T> {
        let layout = self.layout();
        if let Ok(ptr) = Global.allocate(layout) {
            let ptr = ptr.as_mut_ptr();
            ptr.copy_from_nonoverlapping(
                self.0.as_ptr().add(index * self.item_size()),
                self.item_size(),
            );
            Box::from_raw(std::ptr::from_raw_parts_mut(
                ptr as *mut (),
                self.metadata(),
            ))
        } else {
            handle_alloc_error(layout)
        }
    }

    /// Removes an element from the vector and returns it.
    ///
    /// The removed element is replaced by the last element of the vector.
    ///
    /// This does not preserve ordering, but is *O*(1).
    /// If you need to preserve the element order, use [`remove`] instead.
    ///
    /// [`remove`]: FixedVec::remove
    ///
    /// # Panics
    ///
    /// Panics if `index` is out of bounds.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dst_container::*;
    /// let mut v = FixedVec::<str>::new(3);
    /// v.push(Box::from("foo"));
    /// v.push(Box::from("bar"));
    /// v.push(Box::from("baz"));
    /// v.push(Box::from("qux"));
    ///
    /// assert_eq!(v.swap_remove(1).as_ref(), "bar");
    /// assert_eq!(&v[1], "qux");
    ///
    /// assert_eq!(v.swap_remove(0).as_ref(), "foo");
    /// assert_eq!(&v[0], "baz");
    /// ```
    pub fn swap_remove(&mut self, index: usize) -> Box<T> {
        let len = self.len();
        if index >= len {
            panic!("swap_remove index (is {index}) should be < len (is {len})");
        }
        let index = index * self.item_size();
        let last_index = (self.len() - 1) * self.item_size();
        unsafe {
            std::ptr::swap_nonoverlapping(
                self.0.as_mut_ptr().add(index),
                self.0.as_mut_ptr().add(last_index),
                self.item_size(),
            );
            self.set_len(self.len() - 1);
            self.copy_to_box(self.len())
        }
    }

    #[allow(clippy::comparison_chain)]
    unsafe fn insert_raw(&mut self, index: usize, f: impl FnOnce(*mut u8)) {
        self.reserve(1);
        let start = self.start_index(index);
        let len = self.len();
        unsafe {
            if index < len {
                std::ptr::copy(
                    self.0.as_ptr().add(start),
                    self.0.as_mut_ptr().add(start + self.item_size()),
                    (len - index) * self.item_size(),
                );
            } else if index == len {
                // Nop.
            } else {
                panic!("insertion index (is {index}) should be <= len (is {len})");
            }
            f(self.0.as_mut_ptr().add(start));
            self.set_len(len + 1);
        }
    }

    /// Inserts an element at position `index` within the vector, shifting all
    /// elements after it to the right.
    ///
    /// # Panics
    ///
    /// Panics if `index > len`.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(maybe_uninit_write_slice)]
    /// # use dst_container::*;
    /// # use std::mem::MaybeUninit;
    ///
    /// let mut vec = FixedVec::<[i32]>::new(2);
    /// unsafe {
    ///     vec.push_with(|slice| { slice.write_copy_of_slice(&[1, 1]); });
    ///     vec.insert(0, Box::<[i32]>::new_zeroed_unsized(2).assume_init());
    /// }
    /// assert_eq!(&vec[0], [0, 0]);
    /// assert_eq!(&vec[1], [1, 1]);
    /// ```
    pub fn insert(&mut self, index: usize, element: Box<T>) {
        let (ptr, metadata) = (element.as_ref() as *const T).to_raw_parts();
        if metadata != self.metadata() {
            panic!("Different metadata.");
        }
        let item_size = self.item_size();
        unsafe {
            self.insert_raw(index, |dest| {
                std::ptr::copy_nonoverlapping(ptr as *const u8, dest, item_size);
            });
        }
        forget(element);
    }

    /// Inserts an element at position `index` within the vector, shifting all
    /// elements after it to the right.
    ///
    /// # Panics
    ///
    /// Panics if `index > len`.
    ///
    /// # Safety
    /// The caller should ensure the new element being initialized.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(maybe_uninit_write_slice)]
    /// # use dst_container::*;
    /// # use std::mem::MaybeUninit;
    ///
    /// let mut vec = FixedVec::<[i32]>::new(2);
    /// unsafe {
    ///     vec.push_with(|slice| { slice.write_copy_of_slice(&[1, 1]); });
    ///     vec.insert_with(0, |slice| { slice.write_copy_of_slice(&[0, 0]); });
    /// }
    /// assert_eq!(&vec[0], [0, 0]);
    /// assert_eq!(&vec[1], [1, 1]);
    /// ```
    pub unsafe fn insert_with(&mut self, index: usize, f: impl FnOnce(&mut T::Target))
    where
        T: MaybeUninitProject,
    {
        let metadata = self.metadata();
        self.insert_raw(index, |dest| {
            let ptr = std::ptr::from_raw_parts_mut::<T::Target>(dest as *mut (), metadata);
            f(&mut *ptr);
        });
    }

    /// Inserts an element at position `index` within the vector, shifting all
    /// elements after it to the right.
    ///
    /// # Panics
    ///
    /// Panics if `index > len`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dst_container::*;
    /// # use std::mem::MaybeUninit;
    ///
    /// let element0: Box<[i32]> = Box::from([0, 0]);
    /// let element1: Box<[i32]> = Box::from([1, 1]);
    ///
    /// let mut vec = FixedVec::<[i32]>::new(2);
    /// vec.push_clone(element1.as_ref());
    /// vec.insert_clone(0, element0.as_ref());
    /// assert_eq!(&vec[0], [0, 0]);
    /// assert_eq!(&vec[1], [1, 1]);
    /// ```
    pub fn insert_clone(&mut self, index: usize, element: &T)
    where
        T: UnsizedClone,
    {
        unsafe {
            self.insert_with(index, |dest| element.clone_to(dest));
        }
    }

    /// Removes and returns the element at position `index` within the vector,
    /// shifting all elements after it to the left.
    ///
    /// # Panics
    ///
    /// Panics if `index` is out of bounds.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(maybe_uninit_write_slice)]
    /// # use dst_container::*;
    /// # use std::mem::MaybeUninit;
    ///
    /// let mut vec = FixedVec::<[i32]>::new(2);
    /// unsafe {
    ///     vec.push_with(|slice| { slice.write_copy_of_slice(&[0, 0]); });
    ///     vec.push_with(|slice| { slice.write_copy_of_slice(&[1, 1]); });
    /// }
    /// assert_eq!(vec.remove(0).as_ref(), &[0, 0]);
    /// assert_eq!(&vec[0], &[1, 1]);
    /// ```
    pub fn remove(&mut self, index: usize) -> Box<T> {
        let len = self.len();
        if index >= len {
            panic!("removal index (is {index}) should be < len (is {len})");
        }
        let start = self.start_index(index);
        unsafe {
            let b;
            {
                b = self.copy_to_box(index);

                std::ptr::copy(
                    self.0.as_ptr().add(start + self.item_size()),
                    self.0.as_mut_ptr().add(start),
                    (len - index - 1) * self.item_size(),
                );
            }
            self.set_len(len - 1);
            b
        }
    }

    /// Appends an element to the back of a collection.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity exceeds `isize::MAX` bytes.
    #[inline]
    pub fn push(&mut self, value: Box<T>) {
        self.insert(self.len(), value);
    }

    /// Appends an element to the back of a collection.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity exceeds `isize::MAX` bytes.
    ///
    /// # Safety
    ///
    /// The same as [`insert_with`].
    ///
    /// [`insert_with`]: FixedVec::insert_with
    #[inline]
    pub unsafe fn push_with(&mut self, f: impl FnOnce(&mut T::Target))
    where
        T: MaybeUninitProject,
    {
        self.insert_with(self.len(), f);
    }

    /// Appends an element to the back of a collection.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity exceeds `isize::MAX` bytes.
    #[inline]
    pub fn push_clone(&mut self, value: &T)
    where
        T: UnsizedClone,
    {
        self.insert_clone(self.len(), value);
    }

    /// Removes the last element from a vector and returns it, or [`None`] if it
    /// is empty.
    pub fn pop(&mut self) -> Option<Box<T>> {
        if self.is_empty() {
            None
        } else {
            Some(self.remove(self.len() - 1))
        }
    }

    /// Clears the vector, removing all values.
    ///
    /// Note that this method has no effect on the allocated capacity
    /// of the vector.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dst_container::*;
    /// let mut vec = FixedVec::<[i32]>::new(2);
    /// unsafe {
    ///     vec.push_with(|slice| {});
    ///     vec.push_with(|slice| {});
    /// }
    /// vec.clear();
    /// assert!(vec.is_empty());
    /// ```
    #[inline]
    pub fn clear(&mut self) {
        self.truncate(0)
    }

    /// Returns the number of elements in the vector, also referred to
    /// as its 'length'.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dst_container::*;
    /// let mut vec = FixedVec::<[i32]>::new(2);
    /// unsafe {
    ///     vec.push_with(|slice| {});
    ///     vec.push_with(|slice| {});
    /// }
    /// assert_eq!(vec.len(), 2);
    /// ```
    #[inline]
    pub fn len(&self) -> usize {
        self.0.len() / self.item_size()
    }

    /// Returns `true` if the vector contains no elements.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dst_container::*;
    /// let mut vec = FixedVec::<[i32]>::new(2);
    /// assert!(vec.is_empty());
    /// unsafe {
    ///     vec.push_with(|slice| {});
    ///     vec.push_with(|slice| {});
    /// }
    /// assert!(!vec.is_empty());
    /// ```
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.0.len() == 0
    }

    /// Returns an iterator over the vector.
    ///
    /// The iterator yields all items from start to end.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(maybe_uninit_write_slice)]
    /// # use dst_container::*;
    /// # use std::mem::MaybeUninit;
    ///
    /// let mut vec = FixedVec::<[i32]>::new(2);
    /// unsafe {
    ///     vec.push_with(|slice| { slice.write_copy_of_slice(&[0, 0]); });
    ///     vec.push_with(|slice| { slice.write_copy_of_slice(&[1, 1]); });
    ///     vec.push_with(|slice| { slice.write_copy_of_slice(&[2, 2]); });
    /// }
    ///
    /// let mut iterator = vec.iter();
    ///
    /// assert_eq!(iterator.next(), Some(&[0, 0][..]));
    /// assert_eq!(iterator.next(), Some(&[1, 1][..]));
    /// assert_eq!(iterator.next(), Some(&[2, 2][..]));
    /// assert_eq!(iterator.next(), None);
    /// ```
    #[inline]
    pub fn iter(&self) -> FixedVecIter<'_, T> {
        FixedVecIter::new(self)
    }

    /// Returns an iterator that allows modifying each value.
    ///
    /// The iterator yields all items from start to end.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(maybe_uninit_write_slice)]
    /// # use dst_container::*;
    /// # use std::mem::MaybeUninit;
    ///
    /// let mut vec = FixedVec::<[i32]>::new(2);
    /// unsafe {
    ///     vec.push_with(|slice| { slice.write_copy_of_slice(&[0, 0]); });
    ///     vec.push_with(|slice| { slice.write_copy_of_slice(&[1, 1]); });
    ///     vec.push_with(|slice| { slice.write_copy_of_slice(&[2, 2]); });
    /// }
    ///
    /// for elem in vec.iter_mut() {
    ///     elem[0] += 2;
    ///     elem[1] *= 2;
    /// }
    ///
    /// let mut iterator = vec.iter();
    ///
    /// assert_eq!(iterator.next(), Some(&[2, 0][..]));
    /// assert_eq!(iterator.next(), Some(&[3, 2][..]));
    /// assert_eq!(iterator.next(), Some(&[4, 4][..]));
    /// assert_eq!(iterator.next(), None);
    /// ```
    #[inline]
    pub fn iter_mut(&mut self) -> FixedVecIterMut<'_, T> {
        FixedVecIterMut::new(self)
    }

    /// Returns a reference to an element or subslice depending on the type of
    /// index.
    ///
    /// - If given a position, returns a reference to the element at that
    ///   position or `None` if out of bounds.
    /// - If given a range, returns the subslice corresponding to that range,
    ///   or `None` if out of bounds.
    #[inline]
    pub fn get<I: SliceIndex<Self>>(&self, index: I) -> Option<&I::Output> {
        index.get(self)
    }

    /// Returns a mutable reference to an element or subslice depending on the
    /// type of index (see [`get`]) or `None` if the index is out of bounds.
    ///
    /// [`get`]: FixedVec::get
    #[inline]
    pub fn get_mut<I: SliceIndex<Self>>(&mut self, index: I) -> Option<&mut I::Output> {
        index.get_mut(self)
    }

    /// Returns a reference to an element or subslice, without doing bounds
    /// checking.
    ///
    /// For a safe alternative see [`get`].
    ///
    /// # Safety
    ///
    /// Calling this method with an out-of-bounds index is *[undefined behavior]*
    /// even if the resulting reference is not used.
    ///
    /// [`get`]: FixedVec::get
    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
    #[inline]
    pub unsafe fn get_unchecked<I: SliceIndex<Self>>(&self, index: I) -> &I::Output {
        &*index.get_unchecked(self)
    }

    /// Returns a mutable reference to an element or subslice, without doing
    /// bounds checking.
    ///
    /// For a safe alternative see [`get_mut`].
    ///
    /// # Safety
    ///
    /// Calling this method with an out-of-bounds index is *[undefined behavior]*
    /// even if the resulting reference is not used.
    ///
    /// [`get_mut`]: FixedVec::get_mut
    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
    #[inline]
    pub unsafe fn get_unchecked_mut<I: SliceIndex<Self>>(&mut self, index: I) -> &mut I::Output {
        &mut *index.get_unchecked_mut(self)
    }
}

impl<T: ?Sized> Drop for FixedVec<T> {
    fn drop(&mut self) {
        self.clear()
    }
}

impl<T: ?Sized, I: SliceIndex<FixedVec<T>>> Index<I> for FixedVec<T> {
    type Output = I::Output;

    fn index(&self, index: I) -> &Self::Output {
        index.index(self)
    }
}

impl<T: ?Sized, I: SliceIndex<FixedVec<T>>> IndexMut<I> for FixedVec<T> {
    fn index_mut(&mut self, index: I) -> &mut Self::Output {
        index.index_mut(self)
    }
}

unsafe impl<T: ?Sized> SliceIndex<FixedVec<T>> for usize {
    type Output = T;

    fn get(self, slice: &FixedVec<T>) -> Option<&Self::Output> {
        if self < slice.len() {
            Some(unsafe { slice.raw(self) })
        } else {
            None
        }
    }

    fn get_mut(self, slice: &mut FixedVec<T>) -> Option<&mut Self::Output> {
        if self < slice.len() {
            Some(unsafe { slice.raw_mut(self) })
        } else {
            None
        }
    }

    unsafe fn get_unchecked(self, slice: *const FixedVec<T>) -> *const Self::Output {
        (*slice).raw(self)
    }

    unsafe fn get_unchecked_mut(self, slice: *mut FixedVec<T>) -> *mut Self::Output {
        (*slice).raw_mut(self)
    }

    fn index(self, slice: &FixedVec<T>) -> &Self::Output {
        self.get(slice).expect("Index out of bound.")
    }

    fn index_mut(self, slice: &mut FixedVec<T>) -> &mut Self::Output {
        self.get_mut(slice).expect("Index out of bound.")
    }
}

unsafe impl<T: ?Sized> SliceIndex<FixedVec<T>> for RangeFull {
    type Output = FixedVec<T>;

    fn get(self, slice: &FixedVec<T>) -> Option<&Self::Output> {
        Some(slice)
    }

    fn get_mut(self, slice: &mut FixedVec<T>) -> Option<&mut Self::Output> {
        Some(slice)
    }

    unsafe fn get_unchecked(self, slice: *const FixedVec<T>) -> *const Self::Output {
        slice
    }

    unsafe fn get_unchecked_mut(self, slice: *mut FixedVec<T>) -> *mut Self::Output {
        slice
    }

    fn index(self, slice: &FixedVec<T>) -> &Self::Output {
        slice
    }

    fn index_mut(self, slice: &mut FixedVec<T>) -> &mut Self::Output {
        slice
    }
}

pub struct FixedVecIter<'a, T: ?Sized> {
    vec: &'a FixedVec<T>,
    index: usize,
}

impl<'a, T: ?Sized> FixedVecIter<'a, T> {
    pub(crate) fn new(vec: &'a FixedVec<T>) -> Self {
        Self { vec, index: 0 }
    }
}

impl<'a, T: ?Sized> Iterator for FixedVecIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.vec.len() {
            let res = Some(unsafe { self.vec.get_unchecked(self.index) });
            self.index += 1;
            res
        } else {
            None
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.vec.len();
        (len, Some(len))
    }

    fn count(self) -> usize {
        self.vec.len()
    }

    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        self.vec.get(n)
    }
}

impl<T: ?Sized> ExactSizeIterator for FixedVecIter<'_, T> {}

impl<'a, T: ?Sized> DoubleEndedIterator for FixedVecIter<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.index > 0 {
            self.index -= 1;
            Some(unsafe { self.vec.get_unchecked(self.index) })
        } else {
            None
        }
    }

    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
        if n >= self.vec.len() {
            None
        } else {
            Some(unsafe { self.vec.get_unchecked(self.vec.len() - n - 1) })
        }
    }
}

impl<T: ?Sized> FusedIterator for FixedVecIter<'_, T> {}

impl<'a, T: ?Sized> IntoIterator for &'a FixedVec<T> {
    type Item = &'a T;

    type IntoIter = FixedVecIter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

pub struct FixedVecIterMut<'a, T: ?Sized> {
    vec: &'a mut FixedVec<T>,
    index: usize,
}

impl<'a, T: ?Sized> FixedVecIterMut<'a, T> {
    pub(crate) fn new(vec: &'a mut FixedVec<T>) -> Self {
        Self { vec, index: 0 }
    }
}

impl<'a, T: ?Sized> Iterator for FixedVecIterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.vec.len() {
            let res = Some(unsafe { self.vec.get_unchecked_mut(self.index) });
            self.index += 1;
            res.map(|p| unsafe { &mut *(p as *mut T) })
        } else {
            None
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.vec.len();
        (len, Some(len))
    }

    fn count(self) -> usize {
        self.vec.len()
    }

    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        self.vec.get_mut(n).map(|p| unsafe { &mut *(p as *mut T) })
    }
}

impl<T: ?Sized> ExactSizeIterator for FixedVecIterMut<'_, T> {}

impl<'a, T: ?Sized> DoubleEndedIterator for FixedVecIterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.index > 0 {
            self.index -= 1;
            Some(unsafe { &mut *(self.vec.get_unchecked_mut(self.index) as *mut T) })
        } else {
            None
        }
    }

    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
        if n >= self.vec.len() {
            None
        } else {
            Some(unsafe { &mut *(self.vec.get_unchecked_mut(self.vec.len() - n - 1) as *mut T) })
        }
    }
}

impl<T: ?Sized> FusedIterator for FixedVecIterMut<'_, T> {}

impl<'a, T: ?Sized> IntoIterator for &'a mut FixedVec<T> {
    type Item = &'a mut T;

    type IntoIter = FixedVecIterMut<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<T: ?Sized> Extend<Box<T>> for FixedVec<T> {
    fn extend<I: IntoIterator<Item = Box<T>>>(&mut self, iter: I) {
        for item in iter {
            self.push(item);
        }
    }
}

impl<T: ?Sized + UnsizedClone> Clone for FixedVec<T> {
    fn clone(&self) -> Self {
        let mut vec = FixedVec::<T>::with_capacity(self.metadata(), self.len());
        for item in self {
            unsafe {
                vec.push_with(|dest| item.clone_to(dest));
            }
        }
        vec
    }
}

#[cfg(test)]
mod test {
    use crate::*;
    use std::sync::Arc;

    #[test]
    fn basic() {
        let mut vec: FixedVec<UnsizedSlice<u32, u64>> = FixedVec::new(6);
        assert_eq!(vec.len(), 0);
        vec.push(unsafe {
            Box::<UnsizedSlice<u32, u64>>::new_unsized_with(6, |slice| {
                slice.header.write(114514);
                slice.slice.write_copy_of_slice(&[1, 1, 4, 5, 1, 4]);
            })
        });
        assert_eq!(vec.len(), 1);
        assert_eq!(&vec[0].header, &114514);
        assert_eq!(&vec[0].slice, &[1, 1, 4, 5, 1, 4]);
    }

    #[test]
    fn in_place() {
        let mut vec: FixedVec<UnsizedSlice<u32, u64>> = FixedVec::new(6);
        assert_eq!(vec.len(), 0);
        unsafe {
            vec.push_with(|slice| {
                slice.header.write(114514);
                slice.slice.write_copy_of_slice(&[1, 1, 4, 5, 1, 4]);
            })
        };
        assert_eq!(vec.len(), 1);
        assert_eq!(&vec[0].header, &114514);
        assert_eq!(&vec[0].slice, &[1, 1, 4, 5, 1, 4]);
    }

    #[test]
    fn untrivial_drop() {
        let data = Arc::new(());
        assert_eq!(Arc::strong_count(&data), 1);

        let b = unsafe {
            Box::<UnsizedSlice<Arc<()>, Arc<()>>>::new_unsized_with(2, |slice| {
                slice.header.write(data.clone());
                slice
                    .slice
                    .write_clone_of_slice(&[data.clone(), data.clone()]);
            })
        };
        assert_eq!(Arc::strong_count(&data), 4);

        let mut vec: FixedVec<UnsizedSlice<Arc<()>, Arc<()>>> = FixedVec::new(2);
        vec.push_clone(&b);
        assert_eq!(Arc::strong_count(&data), 7);
        vec.push_clone(&b);
        assert_eq!(Arc::strong_count(&data), 10);

        drop(vec);
        assert_eq!(Arc::strong_count(&data), 4);
        drop(b);
        assert_eq!(Arc::strong_count(&data), 1);
    }

    #[test]
    fn clone() {
        let mut vec = FixedVec::<[i32]>::new(2);
        vec.push(Box::from([1, 1]));
        vec.push(Box::from([2, 2]));
        vec.push(Box::from([3, 3]));
        assert_eq!(&vec[0], &[1, 1]);
        assert_eq!(&vec[1], &[2, 2]);
        assert_eq!(&vec[2], &[3, 3]);

        let vec2 = vec.clone();
        assert_eq!(&vec2[0], &[1, 1]);
        assert_eq!(&vec2[1], &[2, 2]);
        assert_eq!(&vec2[2], &[3, 3]);
    }

    #[test]
    #[should_panic]
    fn different_meta() {
        let mut vec: FixedVec<UnsizedSlice<u32, u64>> = FixedVec::new(6);
        vec.push(unsafe {
            Box::<UnsizedSlice<u32, u64>>::new_unsized_with(3, |slice| {
                slice.header.write(114514);
                slice.slice.write_copy_of_slice(&[1, 1, 4]);
            })
        });
    }
}

#[cfg(test)]
mod bench {
    use crate::*;
    use test::{black_box, Bencher};

    const SLICE_LEN: usize = 1000;

    #[bench]
    fn fixed_vec(b: &mut Bencher) {
        b.iter(|| unsafe {
            let mut vec = FixedVec::<[u32]>::with_capacity(SLICE_LEN, SLICE_LEN);
            for _i in 0..SLICE_LEN {
                vec.push_with(|_| {});
            }
            black_box(vec)
        })
    }

    #[bench]
    fn fixed_vec_zeroed(b: &mut Bencher) {
        b.iter(|| unsafe {
            let mut vec = FixedVec::<[u32]>::with_capacity(SLICE_LEN, SLICE_LEN);
            for _i in 0..SLICE_LEN {
                vec.push_with(|slice| {
                    slice.write_copy_of_slice(&[0; SLICE_LEN]);
                });
            }
            black_box(vec)
        })
    }

    #[bench]
    fn flatten_vec(b: &mut Bencher) {
        b.iter(|| {
            let mut vec = Vec::with_capacity(SLICE_LEN * SLICE_LEN);
            for _i in 0..(SLICE_LEN * SLICE_LEN) {
                vec.push(0u32);
            }
            black_box(vec)
        })
    }

    #[bench]
    fn vec_box(b: &mut Bencher) {
        b.iter(|| unsafe {
            let mut vec: Vec<Box<[u32]>> = Vec::with_capacity(SLICE_LEN);
            for _i in 0..SLICE_LEN {
                vec.push(Box::new_uninit_slice(SLICE_LEN).assume_init());
            }
            black_box(vec)
        })
    }

    #[bench]
    fn vec_box_zeroed(b: &mut Bencher) {
        b.iter(|| unsafe {
            let mut vec: Vec<Box<[u32]>> = Vec::with_capacity(SLICE_LEN);
            for _i in 0..SLICE_LEN {
                vec.push(Box::new_zeroed_slice(SLICE_LEN).assume_init());
            }
            black_box(vec)
        })
    }
}

#[cfg(test)]
mod bench_clone {
    use crate::*;
    use test::{black_box, Bencher};

    const SLICE_LEN: usize = 1000;

    #[bench]
    fn fixed_vec(b: &mut Bencher) {
        let mut vec = FixedVec::<[u32]>::with_capacity(SLICE_LEN, SLICE_LEN);
        for _i in 0..SLICE_LEN {
            unsafe {
                vec.push_with(|_| {});
            }
        }
        b.iter(|| black_box(vec.clone()))
    }

    #[bench]
    fn vec(b: &mut Bencher) {
        let mut vec = Vec::with_capacity(SLICE_LEN * SLICE_LEN);
        for _i in 0..(SLICE_LEN * SLICE_LEN) {
            vec.push(0u32);
        }
        b.iter(|| black_box(vec.clone()))
    }

    #[bench]
    fn vec_box(b: &mut Bencher) {
        let mut vec: Vec<Box<[u32]>> = Vec::with_capacity(SLICE_LEN);
        for _i in 0..SLICE_LEN {
            vec.push(unsafe { Box::new_uninit_slice(SLICE_LEN).assume_init() });
        }
        b.iter(|| black_box(vec.clone()))
    }
}