use std::alloc::{alloc, dealloc, realloc, Layout, LayoutErr};
use std::borrow::{Borrow, BorrowMut};
use std::cmp::{self, Ordering};
use std::fmt::{self, Debug, Formatter};
use std::hash::Hash;
use std::iter::FromIterator;
use std::mem::{self, MaybeUninit};
use std::ops::{Deref, DerefMut, Index, IndexMut};
use std::slice::SliceIndex;
use super::value::{IValue, TypeTag};
#[repr(C)]
#[repr(align(4))]
struct Header {
len: usize,
cap: usize,
}
impl Header {
fn as_ptr(&self) -> *const IValue {
unsafe { (self as *const Header).add(1) as *const IValue }
}
fn as_slice(&self) -> &[IValue] {
unsafe { std::slice::from_raw_parts(self.as_ptr(), self.len) }
}
fn as_mut_slice(&mut self) -> &mut [IValue] {
unsafe { std::slice::from_raw_parts_mut(self.as_ptr() as *mut _, self.len) }
}
fn as_mut_uninit_slice(&mut self) -> &mut [MaybeUninit<IValue>] {
unsafe { std::slice::from_raw_parts_mut(self.as_ptr() as *mut _, self.cap) }
}
unsafe fn push(&mut self, item: IValue) {
let index = self.len;
self.as_mut_uninit_slice()
.get_unchecked_mut(index)
.as_mut_ptr()
.write(item);
self.len += 1;
}
fn pop(&mut self) -> Option<IValue> {
if self.len == 0 {
None
} else {
self.len -= 1;
let index = self.len;
unsafe {
Some(
self.as_mut_uninit_slice()
.get_unchecked_mut(index)
.as_mut_ptr()
.read(),
)
}
}
}
}
pub struct IntoIter {
header: *mut Header,
index: usize,
}
impl Iterator for IntoIter {
type Item = IValue;
fn next(&mut self) -> Option<Self::Item> {
if self.header.is_null() {
None
} else {
unsafe {
let len = (*self.header).len;
let res = (*self.header)
.as_mut_uninit_slice()
.get_unchecked_mut(self.index)
.as_ptr()
.read();
self.index += 1;
if self.index >= len {
IArray::dealloc(self.header as *mut u8);
self.header = std::ptr::null_mut();
}
Some(res)
}
}
}
}
impl ExactSizeIterator for IntoIter {
fn len(&self) -> usize {
if self.header.is_null() {
0
} else {
unsafe { (*self.header).len - self.index }
}
}
}
impl Debug for IntoIter {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
f.debug_struct("IntoIter")
.field("index", &self.index)
.finish()
}
}
impl Drop for IntoIter {
fn drop(&mut self) {
while self.next().is_some() {}
}
}
#[repr(transparent)]
#[derive(Clone)]
pub struct IArray(pub(crate) IValue);
value_subtype_impls!(IArray, into_array, as_array, as_array_mut);
static EMPTY_HEADER: Header = Header { len: 0, cap: 0 };
impl IArray {
fn layout(cap: usize) -> Result<Layout, LayoutErr> {
Ok(Layout::new::<Header>()
.extend(Layout::array::<usize>(cap)?)?
.0
.pad_to_align())
}
fn alloc(cap: usize) -> *mut u8 {
unsafe {
let ptr = alloc(Self::layout(cap).unwrap()) as *mut Header;
(*ptr).len = 0;
(*ptr).cap = cap;
ptr as *mut u8
}
}
fn realloc(ptr: *mut u8, new_cap: usize) -> *mut u8 {
unsafe {
let old_layout = Self::layout((*(ptr as *const Header)).cap).unwrap();
let new_layout = Self::layout(new_cap).unwrap();
let ptr = realloc(ptr as *mut u8, old_layout, new_layout.size());
(*(ptr as *mut Header)).cap = new_cap;
ptr
}
}
fn dealloc(ptr: *mut u8) {
unsafe {
let layout = Self::layout((*(ptr as *const Header)).cap).unwrap();
dealloc(ptr, layout);
}
}
pub fn new() -> Self {
unsafe { IArray(IValue::new_ref(&EMPTY_HEADER, TypeTag::ArrayOrFalse)) }
}
pub fn with_capacity(cap: usize) -> Self {
if cap == 0 {
Self::new()
} else {
IArray(unsafe { IValue::new_ptr(Self::alloc(cap), TypeTag::ArrayOrFalse) })
}
}
fn header(&self) -> &Header {
unsafe { &*(self.0.ptr() as *const Header) }
}
unsafe fn header_mut(&mut self) -> &mut Header {
&mut *(self.0.ptr() as *mut Header)
}
fn is_static(&self) -> bool {
self.capacity() == 0
}
pub fn capacity(&self) -> usize {
self.header().cap
}
pub fn len(&self) -> usize {
self.header().len
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn as_slice(&self) -> &[IValue] {
self.header().as_slice()
}
pub fn as_mut_slice(&mut self) -> &mut [IValue] {
if self.is_static() {
&mut []
} else {
unsafe { self.header_mut().as_mut_slice() }
}
}
fn resize_internal(&mut self, cap: usize) {
if self.is_static() || cap == 0 {
*self = Self::with_capacity(cap);
} else {
unsafe {
let new_ptr = Self::realloc(self.0.ptr(), cap);
self.0.set_ptr(new_ptr);
}
}
}
pub fn reserve(&mut self, additional: usize) {
let hd = self.header();
let current_capacity = hd.cap;
let desired_capacity = hd.len.checked_add(additional).unwrap();
if current_capacity >= desired_capacity {
return;
}
self.resize_internal(cmp::max(current_capacity * 2, desired_capacity.max(4)));
}
pub fn truncate(&mut self, len: usize) {
if self.is_static() {
return;
}
unsafe {
let hd = self.header_mut();
while hd.len > len {
hd.pop();
}
}
}
pub fn clear(&mut self) {
self.truncate(0);
}
pub fn insert(&mut self, index: usize, item: impl Into<IValue>) {
self.reserve(1);
unsafe {
let hd = self.header_mut();
assert!(index <= hd.len);
hd.push(item.into());
if index < hd.len {
hd.as_mut_slice()[index..].rotate_right(1);
}
}
}
pub fn remove(&mut self, index: usize) -> Option<IValue> {
if index < self.len() {
unsafe {
let hd = self.header_mut();
hd.as_mut_slice()[index..].rotate_left(1);
hd.pop()
}
} else {
None
}
}
pub fn swap_remove(&mut self, index: usize) -> Option<IValue> {
if index < self.len() {
unsafe {
let hd = self.header_mut();
let last_index = hd.len - 1;
hd.as_mut_slice().swap(index, last_index);
hd.pop()
}
} else {
None
}
}
pub fn push(&mut self, item: impl Into<IValue>) {
self.reserve(1);
unsafe {
self.header_mut().push(item.into());
}
}
pub fn pop(&mut self) -> Option<IValue> {
if self.is_static() {
None
} else {
unsafe { self.header_mut().pop() }
}
}
pub fn shrink_to_fit(&mut self) {
self.resize_internal(self.len());
}
pub(crate) fn clone_impl(&self) -> IValue {
let src = self.header().as_slice();
let l = src.len();
let mut res = Self::with_capacity(l);
if l > 0 {
unsafe {
let hd = res.header_mut();
for v in src {
hd.push(v.clone());
}
}
}
res.0
}
pub(crate) fn drop_impl(&mut self) {
self.clear();
if !self.is_static() {
unsafe {
Self::dealloc(self.0.ptr());
self.0.set_ref(&EMPTY_HEADER);
}
}
}
}
impl IntoIterator for IArray {
type Item = IValue;
type IntoIter = IntoIter;
fn into_iter(mut self) -> Self::IntoIter {
if self.is_static() {
IntoIter {
header: std::ptr::null_mut(),
index: 0,
}
} else {
unsafe {
let header = self.header_mut() as *mut _;
mem::forget(self);
IntoIter { header, index: 0 }
}
}
}
}
impl Deref for IArray {
type Target = [IValue];
fn deref(&self) -> &Self::Target {
self.as_slice()
}
}
impl DerefMut for IArray {
fn deref_mut(&mut self) -> &mut Self::Target {
self.as_mut_slice()
}
}
impl Borrow<[IValue]> for IArray {
fn borrow(&self) -> &[IValue] {
self.as_slice()
}
}
impl BorrowMut<[IValue]> for IArray {
fn borrow_mut(&mut self) -> &mut [IValue] {
self.as_mut_slice()
}
}
impl Hash for IArray {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
self.as_slice().hash(state);
}
}
impl<U: Into<IValue>> Extend<U> for IArray {
fn extend<T: IntoIterator<Item = U>>(&mut self, iter: T) {
let iter = iter.into_iter();
self.reserve(iter.size_hint().0);
for v in iter {
self.push(v);
}
}
}
impl<U: Into<IValue>> FromIterator<U> for IArray {
fn from_iter<T: IntoIterator<Item = U>>(iter: T) -> Self {
let mut res = IArray::new();
res.extend(iter);
res
}
}
impl AsRef<[IValue]> for IArray {
fn as_ref(&self) -> &[IValue] {
self.as_slice()
}
}
impl PartialEq for IArray {
fn eq(&self, other: &Self) -> bool {
if self.0.raw_eq(&other.0) {
true
} else {
self.as_slice() == other.as_slice()
}
}
}
impl Eq for IArray {}
impl PartialOrd for IArray {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
if self.0.raw_eq(&other.0) {
Some(Ordering::Equal)
} else {
self.as_slice().partial_cmp(other.as_slice())
}
}
}
impl<I: SliceIndex<[IValue]>> Index<I> for IArray {
type Output = I::Output;
#[inline]
fn index(&self, index: I) -> &Self::Output {
Index::index(self.as_slice(), index)
}
}
impl<I: SliceIndex<[IValue]>> IndexMut<I> for IArray {
#[inline]
fn index_mut(&mut self, index: I) -> &mut Self::Output {
IndexMut::index_mut(self.as_mut_slice(), index)
}
}
impl Debug for IArray {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
Debug::fmt(self.as_slice(), f)
}
}
impl<T: Into<IValue>> From<Vec<T>> for IArray {
fn from(other: Vec<T>) -> Self {
let mut res = IArray::with_capacity(other.len());
res.extend(other.into_iter().map(Into::into));
res
}
}
impl<T: Into<IValue> + Clone> From<&[T]> for IArray {
fn from(other: &[T]) -> Self {
let mut res = IArray::with_capacity(other.len());
res.extend(other.iter().cloned().map(Into::into));
res
}
}
impl<'a> IntoIterator for &'a IArray {
type Item = &'a IValue;
type IntoIter = std::slice::Iter<'a, IValue>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a> IntoIterator for &'a mut IArray {
type Item = &'a mut IValue;
type IntoIter = std::slice::IterMut<'a, IValue>;
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl Default for IArray {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[mockalloc::test]
fn can_create() {
let x = IArray::new();
let y = IArray::with_capacity(10);
assert_eq!(x, y);
}
#[mockalloc::test]
fn can_collect() {
let x = vec![IValue::NULL, IValue::TRUE, IValue::FALSE];
let y: IArray = x.iter().cloned().collect();
assert_eq!(x.as_slice(), y.as_slice());
}
#[mockalloc::test]
fn can_push_insert() {
let mut x = IArray::new();
x.insert(0, IValue::NULL);
x.push(IValue::TRUE);
x.insert(1, IValue::FALSE);
assert_eq!(x.as_slice(), &[IValue::NULL, IValue::FALSE, IValue::TRUE]);
}
#[mockalloc::test]
fn can_nest() {
let x: IArray = vec![IValue::NULL, IValue::TRUE, IValue::FALSE].into();
let y: IArray = vec![
IValue::NULL,
x.clone().into(),
IValue::FALSE,
x.clone().into(),
]
.into();
assert_eq!(&y[1], x.as_ref());
}
#[mockalloc::test]
fn can_pop_remove() {
let mut x: IArray = vec![IValue::NULL, IValue::TRUE, IValue::FALSE].into();
assert_eq!(x.remove(1), Some(IValue::TRUE));
assert_eq!(x.pop(), Some(IValue::FALSE));
assert_eq!(x.as_slice(), &[IValue::NULL]);
}
#[mockalloc::test]
fn can_swap_remove() {
let mut x: IArray = vec![IValue::NULL, IValue::TRUE, IValue::FALSE].into();
assert_eq!(x.swap_remove(0), Some(IValue::NULL));
assert_eq!(x.as_slice(), &[IValue::FALSE, IValue::TRUE]);
}
#[mockalloc::test]
fn can_index() {
let mut x: IArray = vec![IValue::NULL, IValue::TRUE, IValue::FALSE].into();
assert_eq!(x[1], IValue::TRUE);
x[1] = IValue::FALSE;
assert_eq!(x[1], IValue::FALSE);
}
#[mockalloc::test]
fn can_truncate_and_shrink() {
let mut x: IArray =
vec![IValue::NULL, IValue::TRUE, IArray::with_capacity(10).into()].into();
x.truncate(2);
assert_eq!(x.len(), 2);
assert_eq!(x.capacity(), 3);
x.shrink_to_fit();
assert_eq!(x.len(), 2);
assert_eq!(x.capacity(), 2);
}
#[cfg(not(miri))]
#[mockalloc::test]
fn stress_test() {
use rand::prelude::*;
for i in 0..10 {
let mut rng = StdRng::seed_from_u64(i);
let mut arr = IArray::new();
for j in 0..1000 {
let index = rng.gen_range(0, arr.len() + 1);
if rng.gen() {
arr.insert(index, j);
} else {
arr.remove(index);
}
}
}
}
}