0
\$\begingroup\$

I implemented a vector with small inline storage to avoid allocation when the size is small.

I am still new to Rust, so I have no idea how good this is. I tried to match Vec's API for functions of the same name, but I didn't implement all methods and traits of Vec.

#![feature(generic_const_exprs)]
#![feature(maybe_uninit_uninit_array)]
#![feature(allocator_api)]

use std::{
  alloc::{Allocator, Global, Layout},
  borrow::{Borrow, BorrowMut},
  cmp::min,
  mem::{ManuallyDrop, MaybeUninit},
  ptr::{drop_in_place, NonNull},
};

const fn num_elems_from_size<T>(BYTE_SIZE: usize) -> usize {
  (BYTE_SIZE - 2 * std::mem::size_of::<usize>()) / std::mem::size_of::<T>()
}

union BufferOrPtr<T, const BYTE_SIZE: usize = 64>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  data: NonNull<MaybeUninit<T>>,
  buffer: ManuallyDrop<[MaybeUninit<T>; num_elems_from_size::<T>(BYTE_SIZE)]>,
}

/// BYTE_SIZE is only a hint and is not guaranteed to be the exact final size of the struct
struct SVec<T, const BYTE_SIZE: usize = 64>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  size: usize,
  capacity: usize,
  buffer_or_ptr: BufferOrPtr<T, BYTE_SIZE>,
}

impl<T, const BYTE_SIZE: usize> SVec<T, BYTE_SIZE>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  fn internal_capacity() -> usize {
    num_elems_from_size::<T>(BYTE_SIZE)
  }
  pub fn new() -> Self {
    SVec {
      size: 0,
      capacity: Self::internal_capacity(),
      buffer_or_ptr: BufferOrPtr::<T, BYTE_SIZE> {
        buffer: ManuallyDrop::new(MaybeUninit::uninit_array()),
      },
    }
  }
  pub fn with_capacity(capacity: usize) -> Self {
    let mut v = Self::new();
    v.grow_if_needed(capacity);
    v
  }
  fn is_small(&self) -> bool {
    self.capacity <= Self::internal_capacity()
  }
  fn get_ptr_mut(&mut self) -> *mut MaybeUninit<T> {
    unsafe {
      if self.is_small() {
        self.buffer_or_ptr.borrow_mut().buffer.as_mut_ptr()
      } else {
        self.buffer_or_ptr.borrow_mut().data.as_ptr()
      }
    }
  }
  fn get_ptr(&self) -> *const MaybeUninit<T> {
    unsafe {
      if self.is_small() {
        self.buffer_or_ptr.borrow().buffer.as_ptr()
      } else {
        self.buffer_or_ptr.borrow().data.as_ptr()
      }
    }
  }
  pub fn as_mut_ptr(&mut self) -> *mut T {
    self.get_ptr_mut() as *mut T
  }
  pub fn as_ptr(&self) -> *const T {
    self.get_ptr() as *const T
  }
  pub fn as_slice(&self) -> &[T] {
    unsafe { std::slice::from_raw_parts(self.as_ptr(), self.size) }
  }
  pub fn as_mut_slice(&mut self) -> &mut [T] {
    unsafe { std::slice::from_raw_parts_mut(self.as_mut_ptr(), self.size) }
  }
  fn grow_if_needed(&mut self, extra_elems: usize) {
    if self.size + extra_elems <= self.capacity {
      return;
    }
    if self.is_small() {
      self.capacity = min(32, self.capacity.next_power_of_two() * 2);
      let addr = Global
        .allocate(Layout::array::<MaybeUninit<T>>(self.capacity).unwrap())
        .unwrap();
      unsafe {
        std::ptr::copy_nonoverlapping(
          self.buffer_or_ptr.borrow().buffer.as_ptr(),
          addr.as_ptr() as *mut MaybeUninit<T>,
          self.size,
        );
        self.buffer_or_ptr.borrow_mut().data =
          NonNull::new_unchecked(addr.as_ptr() as *mut MaybeUninit<T>);
      }
      return;
    } else {
      unsafe {
        self.buffer_or_ptr.borrow_mut().data = Global
          .grow(
            self.buffer_or_ptr.borrow().data.cast::<u8>(),
            Layout::array::<MaybeUninit<T>>(self.capacity).unwrap(),
            Layout::array::<MaybeUninit<T>>(self.capacity * 2).unwrap(),
          )
          .expect("alloc failed")
          .cast::<MaybeUninit<T>>();
        self.capacity = self.capacity * 2;
      }
    }
  }
  pub fn len(&self) -> usize {
    self.size
  }
  pub fn capacity(&self) -> usize {
    self.capacity
  }
  pub fn clear(&mut self) {
    while self.size > 0 {
      self.pop();
    }
  }
  pub fn is_empty(&self) -> bool {
    self.size == 0
  }
  fn push_raw(&mut self, value: T) {
    assert!(self.size < self.capacity);
    let ptr = self.get_ptr_mut();
    unsafe {
      std::ptr::write(ptr.add(self.size) as *mut T, value);
    }
    self.size += 1;
  }
  pub fn push(&mut self, value: T) {
    self.grow_if_needed(1);
    self.push_raw(value);
  }
  pub fn pop(&mut self) -> Option<T> {
    if self.size == 0 {
      return None;
    }
    unsafe {
      let ptr = self.get_ptr_mut().add(self.size - 1);
      let elem: &mut MaybeUninit<T> = &mut *ptr;
      let old = std::mem::replace(elem, MaybeUninit::<T>::uninit());
      self.size -= 1;
      Some(old.assume_init())
    }
  }
  pub fn append<const other_byte_size: usize>(&mut self, other: &mut SVec<T, other_byte_size>)
  where
    [(); num_elems_from_size::<T>(other_byte_size)]:,
  {
    self.grow_if_needed(other.size);
    unsafe {
      std::ptr::copy_nonoverlapping(
        other.get_ptr_mut(),
        self.get_ptr_mut().add(self.size),
        other.size,
      );
    }
    self.size += other.size;
    other.size = 0;
  }
  pub fn insert(&mut self, index: usize, element: T) {
    assert!(index <= self.size);
    self.grow_if_needed(1);
    unsafe {
      let ptr = self.as_mut_ptr().add(index);
      std::ptr::copy(ptr, ptr.add(1), self.size - index);
      std::ptr::write(ptr, element);
    }
    self.size += 1;
  }
}

impl<T: Clone, const BYTE_SIZE: usize> SVec<T, BYTE_SIZE>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  pub fn extend_from_slice(&mut self, other: &[T]) {
    self.grow_if_needed(other.len());
    other.iter().for_each(|elem| self.push_raw(elem.clone()));
  }
  pub fn from_elem(elem: T, n: usize) -> Self {
    let mut v = SVec::<T, BYTE_SIZE>::with_capacity(n);
    for _ in 0..n {
      v.push(elem.clone());
    }
    v
  }
}

impl<T, const BYTE_SIZE: usize> Drop for SVec<T, BYTE_SIZE>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  fn drop(&mut self) {
    unsafe {
      drop_in_place(self.as_mut_slice());
      if !self.is_small() {
        Global.deallocate(
          self.buffer_or_ptr.borrow().data.cast::<u8>(),
          Layout::array::<MaybeUninit<T>>(self.capacity).unwrap(),
        );
      }
    }
  }
}

impl<T, const BYTE_SIZE: usize> AsMut<[T]> for SVec<T, BYTE_SIZE>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  fn as_mut(&mut self) -> &mut [T] {
    self.as_mut_slice()
  }
}

impl<T, const BYTE_SIZE: usize> AsRef<[T]> for SVec<T, BYTE_SIZE>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  fn as_ref(&self) -> &[T] {
    self.as_slice()
  }
}

impl<T, const BYTE_SIZE: usize> Borrow<[T]> for SVec<T, BYTE_SIZE>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  fn borrow(&self) -> &[T] {
    self.as_slice()
  }
}

impl<T, const BYTE_SIZE: usize> BorrowMut<[T]> for SVec<T, BYTE_SIZE>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  fn borrow_mut(&mut self) -> &mut [T] {
    self.as_mut_slice()
  }
}

impl<T: Clone, const BYTE_SIZE: usize> Clone for SVec<T, BYTE_SIZE>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  fn clone(&self) -> SVec<T, BYTE_SIZE> {
    let mut new = SVec::<T, BYTE_SIZE>::new();
    new.extend_from_slice(self.as_slice());
    new
  }
}

impl<T, const BYTE_SIZE: usize> Default for SVec<T, BYTE_SIZE>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  fn default() -> Self {
    Self::new()
  }
}

impl<T: Clone, const BYTE_SIZE: usize, A: Allocator> From<Vec<T, A>> for SVec<T, BYTE_SIZE>
where
  [(); num_elems_from_size::<T>(BYTE_SIZE)]:,
{
  fn from(vec: Vec<T, A>) -> Self {
    let mut new = SVec::<T, BYTE_SIZE>::new();
    new.extend_from_slice(vec.as_slice());
    new
  }
}

#[macro_export]
macro_rules! svec {
  ($t:ty) => (
      SVec::<$t>::new()
  );
  ($t:ty; $elem:expr; $n:expr) => (
      SVec::<$t>::from_elem($elem, $n)
  );
  ($t:ty; $( $x:expr ),* ) => {
    {
      let mut vec = SVec::<$t>::new();
      $(
        vec.push($x);
      )*
      vec
    }
  };
}

The code is already long so I didn't include the tests.

Are there any visible bugs? What can I improve?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ What's that? There's tests? Oh, yes please, post them! Put them in a (separately scrolling) code section and folks can ignore them if they choose. \$\endgroup\$
    – J_H
    Feb 25 at 18:29

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.