use std::{
alloc::{alloc, dealloc, handle_alloc_error, Layout},
fmt,
marker::PhantomData,
mem,
ops::{Index, IndexMut},
ptr::{self, NonNull},
slice,
};
pub(crate) struct Array<T> {
ptr: NonNull<T>,
len: usize,
cap: usize,
_marker: PhantomData<T>,
}
#[allow(dead_code)]
impl<T> Array<T> {
pub fn with_capacity(cap: usize) -> Self {
assert!(cap > 0, "capacity must be greater than zero");
let layout = Layout::array::<T>(cap).expect("Array capacity overflow");
let ptr = if mem::size_of::<T>() == 0 {
NonNull::dangling()
} else {
let raw = unsafe { alloc(layout) };
NonNull::new(raw.cast()).unwrap_or_else(|| handle_alloc_error(layout))
};
Self {
ptr,
len: 0,
cap,
_marker: PhantomData,
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn capacity(&self) -> usize {
self.cap
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn is_full(&self) -> bool {
self.len == self.cap
}
pub fn as_slice(&self) -> &[T] {
unsafe { slice::from_raw_parts(self.ptr.as_ptr(), self.len) }
}
pub fn as_mut_slice(&mut self) -> &mut [T] {
unsafe { slice::from_raw_parts_mut(self.ptr.as_ptr(), self.len) }
}
pub fn first(&self) -> Option<&T> {
self.as_slice().first()
}
pub fn last(&self) -> Option<&T> {
self.as_slice().last()
}
pub fn split_off(&mut self, at: usize) -> Self {
assert!(at <= self.len, "index out of bounds");
let old_len = self.len;
let mut other = Self::with_capacity(self.cap);
unsafe {
let src = self.ptr.as_ptr().add(at);
let dst = other.ptr.as_ptr();
ptr::copy_nonoverlapping(src, dst, old_len - at);
}
other.len = old_len - at;
self.len = at;
other
}
pub fn append_from(&mut self, other: &mut Self) {
let new_len = self
.len
.checked_add(other.len)
.expect("Array length overflow");
assert!(new_len <= self.cap, "Array capacity exceeded");
if other.len == 0 {
return;
}
unsafe {
ptr::copy_nonoverlapping(
other.ptr.as_ptr(),
self.ptr.as_ptr().add(self.len),
other.len,
);
}
self.len = new_len;
other.len = 0;
}
pub fn prepend_from(&mut self, other: &mut Self) {
let prefix_len = other.len;
let new_len = self
.len
.checked_add(prefix_len)
.expect("Array length overflow");
assert!(new_len <= self.cap, "Array capacity exceeded");
if prefix_len == 0 {
return;
}
unsafe {
ptr::copy(
self.ptr.as_ptr(),
self.ptr.as_ptr().add(prefix_len),
self.len,
);
ptr::copy_nonoverlapping(
other.ptr.as_ptr(),
self.ptr.as_ptr(),
prefix_len,
);
}
self.len = new_len;
other.len = 0;
}
pub fn clear(&mut self) {
while self.len != 0 {
self.len -= 1;
unsafe {
ptr::drop_in_place(self.ptr.as_ptr().add(self.len));
}
}
}
pub fn push(&mut self, value: T) {
assert!(self.len < self.cap, "Array capacity exceeded");
unsafe {
let dst = self.ptr.as_ptr().add(self.len);
ptr::write(dst, value);
}
self.len += 1;
}
pub fn insert(&mut self, index: usize, value: T) {
assert!(index <= self.len, "index out of bounds");
assert!(self.len < self.cap, "Array capacity exceeded");
unsafe {
let base = self.ptr.as_ptr();
ptr::copy(base.add(index), base.add(index + 1), self.len - index);
ptr::write(base.add(index), value);
}
self.len += 1;
}
pub fn remove(&mut self, index: usize) -> T {
assert!(index < self.len, "index out of bounds");
unsafe {
let base = self.ptr.as_ptr();
let value = ptr::read(base.add(index));
ptr::copy(base.add(index + 1), base.add(index), self.len - index - 1);
self.len -= 1;
value
}
}
pub fn pop(&mut self) -> Option<T> {
if self.len == 0 {
return None;
}
self.len -= 1;
Some(unsafe { ptr::read(self.ptr.as_ptr().add(self.len)) })
}
pub fn get(&self, index: usize) -> Option<&T> {
if index < self.len {
Some(unsafe { self.get_unchecked(index) })
} else {
None
}
}
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(&self, index: usize) -> &T {
debug_assert!(index < self.len);
unsafe { &*self.ptr.as_ptr().add(index) }
}
pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
debug_assert!(index < self.len);
unsafe { &mut *self.ptr.as_ptr().add(index) }
}
}
impl<T> Index<usize> for Array<T> {
type Output = T;
fn index(&self, index: usize) -> &T {
&self.as_slice()[index]
}
}
impl<T> IndexMut<usize> for Array<T> {
fn index_mut(&mut self, index: usize) -> &mut T {
&mut self.as_mut_slice()[index]
}
}
impl<T: fmt::Debug> fmt::Debug for Array<T> {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
self.as_slice().fmt(formatter)
}
}
impl<T> Drop for Array<T> {
fn drop(&mut self) {
self.clear();
if mem::size_of::<T>() != 0 {
let layout = Layout::array::<T>(self.cap)
.expect("an Array must retain its original valid layout");
unsafe { dealloc(self.ptr.as_ptr().cast(), layout) }
}
}
}
unsafe impl<T: Send> Send for Array<T> {}
unsafe impl<T: Sync> Sync for Array<T> {}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn push_and_get() {
let mut array = Array::with_capacity(4);
array.push(10);
array.push(20);
array.push(30);
assert_eq!(array.len(), 3);
assert_eq!(array.capacity(), 4);
assert_eq!(array.get(0), Some(&10));
assert_eq!(array.get(1), Some(&20));
assert_eq!(array.get(2), Some(&30));
assert_eq!(array.get(3), None);
}
#[test]
fn insert_middle() {
let mut array = Array::with_capacity(8);
array.push(10);
array.push(20);
array.push(40);
array.insert(2, 30);
assert_eq!(array.as_slice(), &[10, 20, 30, 40]);
}
#[test]
fn remove_middle() {
let mut array = Array::with_capacity(8);
array.push(10);
array.push(20);
array.push(30);
array.push(40);
let removed = array.remove(1);
assert_eq!(removed, 20);
assert_eq!(array.as_slice(), &[10, 30, 40]);
}
#[test]
fn pop() {
let mut array = Array::with_capacity(4);
array.push(10);
array.push(20);
assert_eq!(array.pop(), Some(20));
assert_eq!(array.pop(), Some(10));
assert_eq!(array.pop(), None);
}
#[test]
fn drop_values() {
use std::cell::Cell;
use std::rc::Rc;
struct Droppable {
counter: Rc<Cell<usize>>,
}
impl Drop for Droppable {
fn drop(&mut self) {
self.counter.set(self.counter.get() + 1);
}
}
let counter = Rc::new(Cell::new(0));
{
let mut array = Array::with_capacity(8);
array.push(Droppable {
counter: Rc::clone(&counter),
});
array.push(Droppable {
counter: Rc::clone(&counter),
});
let _ = array.remove(0);
assert_eq!(counter.get(), 1);
}
assert_eq!(counter.get(), 2);
}
#[test]
fn clear_remains_valid_when_an_element_destructor_panics() {
use std::{
cell::{Cell, RefCell},
panic::{catch_unwind, AssertUnwindSafe},
rc::Rc,
};
struct DropBomb {
id: usize,
drops: Rc<RefCell<[usize; 3]>>,
armed: Rc<Cell<bool>>,
}
impl Drop for DropBomb {
fn drop(&mut self) {
self.drops.borrow_mut()[self.id] += 1;
if self.id == 1 && self.armed.replace(false) {
panic!("intentional destructor panic");
}
}
}
let drops = Rc::new(RefCell::new([0; 3]));
let armed = Rc::new(Cell::new(true));
let mut array = Array::with_capacity(3);
for id in 0..3 {
array.push(DropBomb {
id,
drops: Rc::clone(&drops),
armed: Rc::clone(&armed),
});
}
let result = catch_unwind(AssertUnwindSafe(|| array.clear()));
assert!(result.is_err());
assert_eq!(array.len(), 1);
assert_eq!(*drops.borrow(), [0, 1, 1]);
array.clear();
assert_eq!(*drops.borrow(), [1, 1, 1]);
}
#[test]
fn split_off_transfers_ownership() {
let mut left = Array::with_capacity(8);
for value in 0..6 {
left.push(value);
}
let mut right = left.split_off(2);
assert_eq!(left.as_slice(), &[0, 1]);
assert_eq!(right.as_slice(), &[2, 3, 4, 5]);
left.append_from(&mut right);
assert_eq!(left.as_slice(), &[0, 1, 2, 3, 4, 5]);
assert!(right.is_empty());
}
#[test]
fn supports_zero_sized_values() {
let mut array = Array::with_capacity(3);
array.push(());
array.insert(0, ());
array.push(());
assert_eq!(array.len(), 3);
assert!(array.is_full());
assert_eq!(array.remove(1), ());
assert_eq!(array.len(), 2);
}
}