#![cfg_attr(
feature = "unstable",
feature(coerce_unsized),
feature(set_ptr_value),
feature(pointer_byte_offsets)
)]
#![cfg_attr(doc, feature(doc_cfg))]
#![warn(missing_docs)]
#![warn(clippy::pedantic)]
#![warn(clippy::nursery)]
#![allow(clippy::must_use_candidate)]
#![allow(unstable_name_collisions)]
#![cfg_attr(test, feature(test))]
#[cfg(test)]
mod bench;
#[cfg(test)]
mod test;
mod impls;
mod iter;
mod ptr_ext;
use ptr_ext::{ConstPtrExt, MutPtrExt, PtrExt};
pub use iter::*;
use core::panic;
use std::{
alloc::{alloc, dealloc, handle_alloc_error, Layout},
any::Any,
marker::PhantomData,
mem::{self, align_of, align_of_val, size_of, size_of_val, ManuallyDrop},
ops::{Index, IndexMut},
ptr::{drop_in_place, NonNull},
slice,
};
#[cfg(any(doc, feature = "unstable"))]
use std::ops::CoerceUnsized;
type Coercer<T, U> = for<'a> fn(&'a T) -> &'a U;
pub struct DynVec<T: ?Sized> {
ptr: NonNull<u8>,
len: usize,
capacity: usize,
end_ptr: NonNull<u8>,
_phantom: PhantomData<T>,
}
type Extra<T> = *const T;
impl<T: ?Sized> DynVec<T> {
pub const fn new() -> Self {
let ptr = NonNull::dangling();
Self {
ptr,
len: 0,
capacity: 0,
end_ptr: ptr,
_phantom: PhantomData,
}
}
pub fn from_elem(v: T, len: usize) -> Self
where
T: Sized + Clone,
{
let mut vec = Self::with_capacity(len);
for _ in 0..len {
vec.push(v.clone());
}
vec
}
pub fn with_capacity(cap: usize) -> Self
where
T: Sized,
{
Self::with_capacity_for::<T>(cap)
}
pub fn with_capacity_bytes(cap: usize) -> Self {
let mut vec = Self::new();
unsafe {
vec.realloc(cap);
}
vec
}
pub fn with_capacity_for<U>(cap: usize) -> Self {
Self::with_capacity_bytes(cap * (size_of::<U>() + size_of::<Extra<U>>()))
}
pub fn into_raw_parts(self) -> (*mut u8, usize, usize, usize) {
let mut this = ManuallyDrop::new(self);
(
this.as_mut_ptr(),
this.len(),
this.capacity(),
this.data_size(),
)
}
pub const unsafe fn from_raw_parts(
ptr: *mut u8,
len: usize,
capacity: usize,
data_size: usize,
) -> Self {
Self {
ptr: NonNull::new_unchecked(ptr),
len,
capacity,
end_ptr: NonNull::new_unchecked(ptr.add(data_size)),
_phantom: PhantomData,
}
}
pub fn push(&mut self, v: T)
where
T: Sized,
{
unsafe { self.push_raw(&*ManuallyDrop::new(v)) }
}
pub fn push_box(&mut self, v: Box<T>) {
let ptr = Box::into_raw(v);
unsafe {
let layout = Layout::for_value(&*ptr); self.push_raw(ptr);
dealloc(ptr.cast(), layout);
}
}
#[cfg(any(doc, feature = "unstable"))]
#[cfg_attr(doc, doc(cfg(feature = "unstable")))]
pub fn push_unsize<U>(&mut self, v: U)
where
for<'a> &'a U: CoerceUnsized<&'a T>,
{
self.push_unsize_stable(v, |v| v as _);
}
pub fn push_unsize_stable<U>(&mut self, v: U, coercer: Coercer<U, T>) {
let v_unsized: &T = coercer(&v);
unsafe { self.push_raw(v_unsized) };
mem::forget(v);
}
unsafe fn push_raw(&mut self, v: *const T) {
if !self.will_fit(&*v) {
let new_alloc_size = self.capacity * 2 + size_of_val(&*v) * 2 + size_of::<Extra<T>>();
self.realloc(new_alloc_size);
}
self.push_raw_unchecked(v);
}
fn get_next_elem_ptr(&self, v: &T) -> *mut u8 {
self.end_ptr.as_ptr().align_up(align_of_val(v))
}
pub fn will_fit(&self, v: &T) -> bool {
let remaining_space = self.get_ptr_to_extra(self.len).addr() - self.end_ptr.as_ptr().addr();
let needed_space = size_of_val(v) + size_of::<Extra<T>>();
remaining_space >= needed_space
}
unsafe fn push_raw_unchecked(&mut self, v: *const T) {
let dest = self.get_next_elem_ptr(&*v).with_meta_from(v);
v.copy_val_to(dest);
self.set_extra_from_ptr(self.len, dest);
self.end_ptr = NonNull::new_unchecked(dest.get_end().cast());
self.len += 1;
}
pub fn pop(&mut self) -> Option<Box<T>> {
unsafe {
self.len = self.len.checked_sub(1)?;
let el = self.get_ptr(self.len);
Some(el.read_to_box())
}
}
unsafe fn realloc(&mut self, size: usize) {
let layout = Layout::from_size_align_unchecked(size, align_of::<Extra<T>>()).pad_to_align();
let new_alloc = NonNull::new(alloc(layout)).unwrap_or_else(|| handle_alloc_error(layout));
if self.capacity == 0 {
self.ptr = new_alloc;
self.end_ptr = self.ptr;
} else {
let mut ptr = new_alloc.as_ptr();
for i in 0..self.len {
let v = self.get_ptr(i);
ptr = ptr.align_up(align_of_val(&*v));
v.copy_val_to(ptr);
self.set_extra_from_ptr(i, ptr.with_meta_from(v));
ptr = ptr.wrapping_add(size_of_val(&*v));
}
self.end_ptr = NonNull::new_unchecked(ptr);
let extra_src = self.get_ptr_to_extra(self.len);
let extra_dst = {
let current_alloc_end = self.ptr.as_ptr().wrapping_add(self.capacity);
let new_alloc_end = new_alloc.as_ptr().wrapping_add(layout.size());
let extra_len = current_alloc_end.addr() - extra_src.addr();
new_alloc_end.wrapping_sub(extra_len)
};
extra_src.copy_to(extra_dst.cast(), self.len);
dealloc(
self.ptr.as_ptr(),
Layout::from_size_align_unchecked(self.capacity, 8),
);
self.ptr = new_alloc;
}
self.capacity = layout.size();
}
fn get_ptr_to_extra(&self, index: usize) -> *mut Extra<T> {
self.ptr
.as_ptr()
.add_bytes(self.capacity)
.cast::<Extra<T>>()
.wrapping_sub(index)
}
unsafe fn set_extra_from_ptr(&self, index: usize, ptr: *const T) {
self.get_ptr_to_extra(index + 1).write(ptr);
}
unsafe fn get_ptr(&self, index: usize) -> *const T {
*self.get_ptr_to_extra(index + 1)
}
unsafe fn get_ptr_before_pad(&self, index: usize) -> *const T {
self.get_ptr(index).with_addr_from(if index > 0 {
self.get_ptr(index - 1).get_end().cast()
} else {
self.ptr.as_ptr()
})
}
pub fn get(&self, index: usize) -> Option<&T> {
if index < self.len {
Some(unsafe { self.get_unchecked(index) })
} else {
None
}
}
pub unsafe fn get_unchecked(&self, index: usize) -> &T {
&*self.get_ptr(index)
}
pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
if index < self.len {
Some(unsafe { self.get_unchecked_mut(index) })
} else {
None
}
}
pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
&mut *(self.get_ptr(index) as *mut _)
}
pub const fn len(&self) -> usize {
self.len
}
pub const fn is_empty(&self) -> bool {
self.len == 0
}
pub const fn capacity(&self) -> usize {
self.capacity
}
pub const fn as_ptr(&self) -> *const u8 {
self.ptr.as_ptr()
}
pub fn as_mut_ptr(&mut self) -> *mut u8 {
self.ptr.as_ptr()
}
pub const fn as_end_ptr(&self) -> *const u8 {
self.end_ptr.as_ptr()
}
pub fn as_end_ptr_mut(&mut self) -> *mut u8 {
self.end_ptr.as_ptr()
}
pub fn data_size(&self) -> usize {
self.as_end_ptr() as usize - self.as_ptr() as usize
}
#[cfg(any(doc, feature = "unstable"))]
#[cfg_attr(doc, doc(cfg(feature = "unstable")))]
pub fn unsize<U: ?Sized>(self) -> DynVec<U>
where
for<'a> &'a T: CoerceUnsized<&'a U>,
{
self.unsize_stable(|v| v as _)
}
pub fn unsize_stable<U: ?Sized>(mut self, coercer: Coercer<T, U>) -> DynVec<U> {
if size_of::<Extra<U>>() > size_of::<Extra<T>>() {
let elem_size = self.end_ptr.as_ptr().addr() - self.ptr.as_ptr().addr();
let extra_size = self.len * size_of::<Extra<U>>();
let needed_size = elem_size + extra_size;
if needed_size > self.capacity {
unsafe {
self.realloc(needed_size);
}
}
}
let new_vec = DynVec::<U> {
ptr: self.ptr,
len: self.len,
capacity: self.capacity,
end_ptr: self.end_ptr,
_phantom: PhantomData,
};
if size_of::<Extra<U>>() > size_of::<Extra<T>>() {
for i in (0..self.len).rev() {
let current = unsafe { &*self.get_ptr(i) };
unsafe { new_vec.set_extra_from_ptr(i, coercer(current)) }
}
} else {
for i in 0..self.len {
let current = unsafe { &*self.get_ptr(i) };
unsafe { new_vec.set_extra_from_ptr(i, coercer(current)) }
}
}
mem::forget(self);
new_vec
}
unsafe fn dealloc(&self) {
if self.capacity != 0 {
dealloc(
self.ptr.as_ptr(),
Layout::from_size_align_unchecked(self.capacity, align_of::<Extra<T>>()),
);
}
}
#[cfg(any(doc, feature = "unstable"))]
#[cfg_attr(doc, doc(cfg(feature = "unstable")))]
pub fn extend_unsize<U, I: IntoIterator<Item = U>>(&mut self, iter: I)
where
for<'a> &'a U: CoerceUnsized<&'a T>,
{
self.extend_unsize_stable(iter, |v| v as _);
}
pub fn extend_unsize_stable<U, I: IntoIterator<Item = U>>(
&mut self,
iter: I,
coercer: Coercer<U, T>,
) {
for item in iter {
self.push_unsize_stable(item, coercer);
}
}
pub fn remove(&mut self, index: usize) -> Option<Box<T>> {
if index >= self.len {
return None;
}
if index == self.len - 1 {
return self.pop();
}
unsafe {
let res = Some(self.get_ptr(index).read_to_box());
for index in index..self.len - 1 {
let mut new_ptr = self.get_ptr_before_pad(index);
let next_ptr = self.get_ptr(index + 1);
new_ptr = new_ptr.align_up(align_of_val(&*next_ptr));
if new_ptr == next_ptr {
break;
}
next_ptr.copy_val_to(new_ptr as *mut T);
self.set_extra_from_ptr(index, new_ptr.with_meta_from(next_ptr));
}
self.len -= 1;
res
}
}
}
impl<T> DynVec<[T]> {
pub fn as_slice_flatten(&self) -> &[T] {
if self.len == 0 {
return unsafe { slice::from_raw_parts(NonNull::dangling().as_ptr(), 0) };
}
unsafe {
slice::from_raw_parts(self.get_ptr(0).data_ptr().cast(), {
let start = self.get_ptr(0).addr();
let end = self.end_ptr.as_ptr().addr();
debug_assert_eq!((end - start) % size_of::<T>(), 0);
(end - start) / size_of::<T>() })
}
}
pub fn as_mut_slice_flatten(&mut self) -> &mut [T] {
if self.len == 0 {
return unsafe { slice::from_raw_parts_mut(NonNull::dangling().as_ptr(), 0) };
}
unsafe {
slice::from_raw_parts_mut(self.get_ptr(0).data_ptr() as _, {
let start = self.get_ptr(0).addr();
let end = self.end_ptr.as_ptr().addr();
debug_assert_eq!((end - start) % size_of::<T>(), 0);
(end - start) / size_of::<T>() })
}
}
}
impl DynVec<dyn Any> {
pub fn downcast_get<T: Any>(&self, index: usize) -> Option<&T> {
self.get(index)?.downcast_ref()
}
pub fn downcast_get_mut<T: Any>(&mut self, index: usize) -> Option<&mut T> {
self.get_mut(index)?.downcast_mut()
}
pub fn downcast_pop<T: Any>(&mut self) -> Option<T> {
unsafe {
let el = self.get_unchecked_mut(self.len.checked_sub(1)?);
let v = Some((el.downcast_mut()? as *mut T).read());
self.len -= 1;
v
}
}
}
impl<T: ?Sized> Drop for DynVec<T> {
fn drop(&mut self) {
unsafe {
for el in self.iter_mut() {
drop_in_place(el);
}
self.dealloc();
}
}
}
impl<T: ?Sized> Index<usize> for DynVec<T> {
type Output = T;
#[track_caller]
fn index(&self, index: usize) -> &Self::Output {
self.get(index).unwrap_or_else(|| {
panic!(
"index out of bounds: the len is {} but the index is {}",
self.len, index
)
})
}
}
impl<T: ?Sized> IndexMut<usize> for DynVec<T> {
#[track_caller]
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
let len = self.len;
self.get_mut(index).unwrap_or_else(|| {
panic!(
"index out of bounds: the len is {} but the index is {}",
len, index
)
})
}
}
#[macro_export]
macro_rules! dyn_vec {
() => {
$crate::DynVec::new();
};
(box: $($elem:expr),+ $(,)?) => {{
let mut vec = $crate::DynVec::new();
$(vec.push_box($elem);)+
vec
}};
(unsized: $($elem:expr),+ $(,)?) => {{
let mut vec = $crate::DynVec::new();
$(vec.push_unsize_stable($elem, |v| v as _);)+
vec
}};
($elem:expr; $n:expr) => {
$crate::DynVec::from_elem($elem, $n)
};
($($elem:expr),+ $(,)?) => {{
let mut vec = $crate::DynVec::new();
$(vec.push($elem);)+
vec
}};
}