FVec

lib.rs

//! Not tested!

extern crate alloc;

use alloc::{
    alloc::{realloc, Layout},
    collections::TryReserveError,
    ffi::CString,
    vec::{self, Drain},
};
use core::{
    borrow::{Borrow, BorrowMut},
    fmt,
    mem::{forget, replace, size_of, ManuallyDrop, MaybeUninit},
    ops::{Deref, DerefMut, Index, IndexMut, RangeBounds},
    slice::{self, SliceIndex},
};

#[derive(Default, Eq, PartialOrd, Ord, Hash)]
#[repr(transparent)]
pub struct FVec<T>(Vec<T>);

impl<T> FVec<T> {
    pub const fn new() -> Self {
        Self(Vec::new())
    }

    pub fn with_capacity(capacity: usize) -> Result<Self, TryReserveError> {
        let mut v = Self::new();
        v.reserve_exact(capacity)?;
        Ok(v)
    }

    pub fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Result<Self, TryReserveError> {
        let mut v = Self::new();
        v.extend(iter)?;
        Ok(v)
    }

    pub fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) -> Result<(), TryReserveError> {
        let mut iter = iter.into_iter();
        while let Some(e) = iter.next() {
            if self.spare_capacity_mut().is_empty() {
                let (n, _) = iter.size_hint();
                self.reserve(n.saturating_add(1))?;
            }
            unsafe {
                self.spare_capacity_mut().get_unchecked_mut(0).write(e);
                self.set_len(self.len() + 1);
            }
        }
        Ok(())
    }

    pub fn as_slice(&self) -> &[T] {
        &self.0
    }

    pub fn as_mut_slice(&mut self) -> &mut [T] {
        &mut self.0
    }

    pub fn as_ptr(&self) -> *const T {
        self.0.as_ptr()
    }

    pub fn as_mut_ptr(&mut self) -> *mut T {
        self.0.as_mut_ptr()
    }

    pub fn capacity(&self) -> usize {
        self.0.capacity()
    }

    pub fn clear(&mut self) {
        self.0.clear()
    }

    pub fn push(&mut self, value: T) -> Result<(), TryReserveError> {
        self.reserve(1)?;
        unsafe {
            self.spare_capacity_mut().get_unchecked_mut(0).write(value);
            self.set_len(self.len() + 1);
        }
        Ok(())
    }

    pub fn push_within_capacity(&mut self, value: T) -> Result<(), T> {
        match self.spare_capacity_mut() {
            [] => Err(value),
            [dst, ..] => {
                dst.write(value);
                unsafe { self.set_len(self.len() + 1) };
                Ok(())
            }
        }
    }

    pub fn pop(&mut self) -> Option<T> {
        self.0.pop()
    }

    pub fn append(&mut self, other: &mut Self) -> Result<(), TryReserveError> {
        let n = other.len();
        self.reserve(n)?;
        unsafe {
            other
                .as_ptr()
                .copy_to_nonoverlapping(self.spare_capacity_mut().as_mut_ptr() as *mut T, n);
            other.set_len(0);
            self.set_len(self.len() + n);
        }
        Ok(())
    }

    pub fn extend_from_slice(&mut self, slice: &[T]) -> Result<(), TryReserveError>
    where
        T: Copy,
    {
        self.reserve(slice.len())?;
        unsafe {
            slice.as_ptr().copy_to_nonoverlapping(
                self.spare_capacity_mut().as_mut_ptr() as *mut T,
                slice.len(),
            );
            self.set_len(self.len() + slice.len());
        }
        Ok(())
    }

    pub fn extend_from_within<R>(&mut self, range: R) -> Result<(), TryReserveError>
    where
        R: SliceIndex<[T], Output = [T]> + Copy,
        T: Copy,
    {
        let len = self.0[range].len();
        self.reserve(len)?;
        let src = self.0[range].as_ptr();
        let dst = self.spare_capacity_mut().as_mut_ptr().cast();
        unsafe {
            src.copy_to_nonoverlapping(dst, len);
            self.set_len(self.len() + len);
        }
        Ok(())
    }

    pub fn insert(&mut self, index: usize, element: T) -> Result<(), TryReserveError> {
        self.reserve(1)?;
        let p = self[index..].as_mut_ptr();
        unsafe {
            p.copy_to(p.offset(1), self.len() - index);
            p.write(element);
            self.set_len(self.len() + 1);
        }
        Ok(())
    }

    pub fn resize(&mut self, new_len: usize, value: T) -> Result<(), TryReserveError>
    where
        T: Copy,
    {
        let len = self.len();
        if new_len > len {
            self.reserve(new_len - len)?;
            unsafe {
                self.0
                    .spare_capacity_mut()
                    .get_unchecked_mut(..new_len - len)
                    .fill(MaybeUninit::new(value));
                self.set_len(new_len);
            }
        } else {
            self.truncate(new_len);
        }
        Ok(())
    }

    pub fn resize_with<F>(&mut self, new_len: usize, mut f: F) -> Result<(), TryReserveError>
    where
        F: FnMut() -> T,
    {
        let len = self.len();
        if new_len > len {
            self.reserve(new_len - len)?;
            for i in len..new_len {
                unsafe {
                    self.0.spare_capacity_mut().get_unchecked_mut(0).write(f());
                    self.set_len(i);
                }
            }
        } else {
            self.truncate(new_len);
        }
        Ok(())
    }

    pub unsafe fn from_raw_parts(ptr: *mut T, size: usize, capacity: usize) -> Self {
        Self(Vec::from_raw_parts(ptr, size, capacity))
    }

    pub fn into_raw_parts(self) -> (*mut T, usize, usize) {
        let mut v = ManuallyDrop::new(self.0);
        (v.as_mut_ptr(), v.len(), v.capacity())
    }

    pub fn leak<'a>(self) -> &'a mut [T] {
        self.0.leak()
    }

    pub fn retain<F>(&mut self, f: F)
    where
        F: FnMut(&mut T) -> bool,
    {
        self.0.retain_mut(f)
    }

    pub unsafe fn set_len(&mut self, len: usize) {
        self.0.set_len(len)
    }

    pub fn reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
        self.0.try_reserve(additional)
    }

    pub fn reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
        self.0.try_reserve_exact(additional)
    }

    pub fn truncate(&mut self, len: usize) {
        self.0.truncate(len)
    }

    pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
        self.0.spare_capacity_mut()
    }

    pub fn swap_remove(&mut self, index: usize) -> T {
        self.0.swap_remove(index)
    }

    pub fn into_boxed_slice(mut self) -> Result<Box<[T]>, TryShrinkError> {
        self.shrink_to_fit()?;
        let (ptr, len, _) = self.into_raw_parts();
        unsafe { Ok(Box::from_raw(slice::from_raw_parts_mut(ptr, len))) }
    }

    pub fn shrink_to_fit(&mut self) -> Result<(), TryShrinkError> {
        self.shrink_to(self.len())
    }

    pub fn shrink_to(&mut self, min_capacity: usize) -> Result<(), TryShrinkError> {
        if size_of::<T>() == 0 && self.capacity() <= min_capacity {
            return Ok(());
        }
        let new_cap = self.len().max(min_capacity);
        if new_cap == 0 {
            *self = Self::new();
            return Ok(());
        }
        unsafe {
            let new_ptr = realloc(
                self.as_mut_ptr().cast(),
                Layout::array::<T>(self.capacity()).unwrap_unchecked(),
                new_cap,
            );
            if new_ptr.is_null() {
                return Err(TryShrinkError {
                    layout: Layout::array::<T>(new_cap).unwrap_unchecked(),
                });
            }
            forget(replace(
                self,
                Self::from_raw_parts(new_ptr.cast(), self.len(), new_cap),
            ));
        }
        Ok(())
    }

    pub fn drain<R: RangeBounds<usize>>(&mut self, range: R) -> Drain<'_, T> {
        self.0.drain(range)
    }

    pub fn dedup(&mut self)
    where
        T: PartialEq,
    {
        self.0.dedup()
    }

    pub fn dedup_by<F>(&mut self, same_bucket: F)
    where
        F: FnMut(&mut T, &mut T) -> bool,
    {
        self.0.dedup_by(same_bucket)
    }

    pub fn dedup_by_key<F, K>(&mut self, key: F)
    where
        F: FnMut(&mut T) -> K,
        K: PartialEq,
    {
        self.0.dedup_by_key(key)
    }

    pub fn split_off(&mut self, at: usize) -> Result<Self, TryReserveError> {
        let tail = &self.0[at..];
        let mut new = Self::with_capacity(tail.len())?;
        unsafe {
            tail.as_ptr()
                .copy_to_nonoverlapping(new.as_mut_ptr(), tail.len());
            new.set_len(tail.len());
            self.set_len(at);
        }
        Ok(new)
    }
}

impl<T> AsRef<[T]> for FVec<T> {
    fn as_ref(&self) -> &[T] {
        &self.0
    }
}

impl<T> AsRef<Vec<T>> for FVec<T> {
    fn as_ref(&self) -> &Vec<T> {
        &self.0
    }
}

impl<T> AsMut<[T]> for FVec<T> {
    fn as_mut(&mut self) -> &mut [T] {
        &mut self.0
    }
}

impl<T> AsMut<Vec<T>> for FVec<T> {
    fn as_mut(&mut self) -> &mut Vec<T> {
        &mut self.0
    }
}

impl<T> Borrow<[T]> for FVec<T> {
    fn borrow(&self) -> &[T] {
        &self.0
    }
}

impl<T> BorrowMut<[T]> for FVec<T> {
    fn borrow_mut(&mut self) -> &mut [T] {
        &mut self.0
    }
}

impl<T> Deref for FVec<T> {
    type Target = [T];

    fn deref(&self) -> &[T] {
        &self.0
    }
}

impl<T> DerefMut for FVec<T> {
    fn deref_mut(&mut self) -> &mut [T] {
        &mut self.0
    }
}

impl<T: fmt::Debug> fmt::Debug for FVec<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.0.fmt(f)
    }
}

impl<T, I: SliceIndex<[T]>> Index<I> for FVec<T> {
    type Output = I::Output;

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

impl<T, I: SliceIndex<[T]>> IndexMut<I> for FVec<T> {
    fn index_mut(&mut self, index: I) -> &mut I::Output {
        self.0.index_mut(index)
    }
}

impl<T> IntoIterator for FVec<T> {
    type Item = T;

    type IntoIter = vec::IntoIter<T>;

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

impl<'a, T> IntoIterator for &'a FVec<T> {
    type Item = &'a T;

    type IntoIter = slice::Iter<'a, T>;

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

impl<'a, T> IntoIterator for &'a mut FVec<T> {
    type Item = &'a mut T;

    type IntoIter = slice::IterMut<'a, T>;

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

impl<T> From<Vec<T>> for FVec<T> {
    fn from(vec: Vec<T>) -> Self {
        Self(vec)
    }
}

impl<T> From<FVec<T>> for Vec<T> {
    fn from(vec: FVec<T>) -> Self {
        vec.0
    }
}

impl<T> From<Box<[T]>> for FVec<T> {
    fn from(b: Box<[T]>) -> Self {
        Self(b.into())
    }
}

impl From<String> for FVec<u8> {
    fn from(s: String) -> Self {
        Self(s.into_bytes())
    }
}

impl From<CString> for FVec<u8> {
    fn from(s: CString) -> Self {
        Self(s.into_bytes())
    }
}

impl<T, U> PartialEq<FVec<U>> for FVec<T>
where
    T: PartialEq<U>,
{
    fn eq(&self, other: &FVec<U>) -> bool {
        self.0[..] == other.0[..]
    }
}

impl<T, U> PartialEq<[U]> for FVec<T>
where
    T: PartialEq<U>,
{
    fn eq(&self, other: &[U]) -> bool {
        self.0[..] == other[..]
    }
}

impl<T, U> PartialEq<&[U]> for FVec<T>
where
    T: PartialEq<U>,
{
    fn eq(&self, other: &&[U]) -> bool {
        self.0[..] == other[..]
    }
}

impl<T, U, const N: usize> PartialEq<[U; N]> for FVec<T>
where
    T: PartialEq<U>,
{
    fn eq(&self, other: &[U; N]) -> bool {
        self.0[..] == other[..]
    }
}

impl<T, U, const N: usize> PartialEq<&[U; N]> for FVec<T>
where
    T: PartialEq<U>,
{
    fn eq(&self, other: &&[U; N]) -> bool {
        self.0[..] == other[..]
    }
}

impl<T, U> PartialEq<FVec<U>> for [T]
where
    T: PartialEq<U>,
{
    fn eq(&self, other: &FVec<U>) -> bool {
        self[..] == other.0[..]
    }
}

impl<T, U> PartialEq<FVec<U>> for &[T]
where
    T: PartialEq<U>,
{
    fn eq(&self, other: &FVec<U>) -> bool {
        self[..] == other.0[..]
    }
}

impl<T, U, const N: usize> PartialEq<FVec<U>> for [T; N]
where
    T: PartialEq<U>,
{
    fn eq(&self, other: &FVec<U>) -> bool {
        self[..] == other.0[..]
    }
}

impl<T, U, const N: usize> PartialEq<FVec<U>> for &[T; N]
where
    T: PartialEq<U>,
{
    fn eq(&self, other: &FVec<U>) -> bool {
        self[..] == other.0[..]
    }
}

#[derive(Clone, PartialEq, Eq, Debug)]
pub struct TryShrinkError {
    layout: Layout,
}

impl fmt::Display for TryShrinkError {
    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt.write_str("memory reallocation failed because the memory allocator returned a error")
    }
}