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?