#![allow(non_snake_case)]
#![feature(allocator_api, alloc_layout_extra)]
macro_rules! soa {
($name:ident, $t1:ident, $($ts:ident),+) => {
pub mod $name {
use second_stack::*;
use std::{alloc::*, cmp::*, marker::*, ptr::*, slice::*};
use std::ops::RangeBounds;
use core::ops::Bound::{Included, Excluded, Unbounded};
pub struct $name<$t1: Sized $(, $ts: Sized)*> {
len: usize,
capacity: usize,
$t1: NonNull<$t1>,
$($ts: NonNull<$ts>,)*
_marker: (PhantomData<$t1> $(, PhantomData<$ts>)*),
}
impl<$t1: Sized $(, $ts: Sized)*> $name<$t1 $(, $ts)*> {
pub fn new() -> $name<$t1 $(, $ts)*> {
$name {
len: 0,
capacity: 0,
$t1: NonNull::dangling(),
$($ts: NonNull::dangling(),)*
_marker: (PhantomData $(, PhantomData::<$ts>)*),
}
}
pub fn with_capacity(capacity: usize) -> $name<$t1 $(, $ts)*> {
if capacity == 0 {
Self::new()
} else {
let ($t1 $(,$ts)*) = Self::alloc(capacity);
Self {
capacity,
len: 0,
$t1: $t1,
$($ts: $ts,)*
_marker: (PhantomData $(, PhantomData::<$ts>)*),
}
}
}
fn dealloc(&mut self) {
if self.capacity > 0 {
let layout = Self::layout_for_capacity(self.capacity).layout;
unsafe { Global.dealloc(self.$t1.cast::<u8>(), layout) }
}
}
fn alloc(capacity: usize) -> (NonNull<$t1> $(, NonNull<$ts>)*) {
unsafe {
let layouts = Self::layout_for_capacity(capacity);
let bytes = Global.alloc(layouts.layout).unwrap();
(
bytes.cast::<$t1>()
$(, NonNull::new_unchecked(bytes.as_ptr().add(layouts.$ts) as *mut $ts))*
)
}
}
fn check_grow(&mut self) {
unsafe {
if self.len == self.capacity {
let capacity = (self.capacity * 2).max(4);
let ($t1 $(, $ts)*) = Self::alloc(capacity);
copy_nonoverlapping(self.$t1.as_ptr(), $t1.as_ptr(), self.len);
$(
copy_nonoverlapping(self.$ts.as_ptr(), $ts.as_ptr(), self.len);
)*
self.dealloc();
self.$t1 = $t1;
$(self.$ts = $ts;)*
self.capacity = capacity;
}
}
}
#[inline(always)]
pub fn len(&self) -> usize { self.len }
#[inline(always)]
pub fn capacity(&self) -> usize { self.capacity }
#[inline(always)]
pub fn is_empty(&self) -> bool { self.len == 0 }
pub fn clear(&mut self) {
while self.len > 0 {
self.pop();
}
}
pub fn push(&mut self, value: ($t1 $(, $ts)*)) {
unsafe {
self.check_grow();
let ($t1 $(, $ts)*) = value;
write(self.$t1.as_ptr().add(self.len), $t1);
$(write(self.$ts.as_ptr().add(self.len), $ts);)*
self.len += 1;
}
}
pub fn insert(&mut self, index: usize, value: ($t1 $(, $ts)*)) {
let len = self.len;
assert!(index <= len);
unsafe {
self.check_grow();
let ($t1 $(, $ts)*) = value;
{
let p = self.$t1.as_ptr().add(index);
copy(p, p.offset(1), len - index);
write(p, $t1);
}
$({
let p = self.$ts.as_ptr().add(index);
copy(p, p.offset(1), len - index);
write(p, $ts);
})*
self.len = len + 1;
}
}
pub fn pop(&mut self) -> Option<($t1 $(, $ts)*)> {
if self.len == 0 {
None
} else {
self.len -= 1;
unsafe {
Some((
read(self.$t1.as_ptr().add(self.len))
$(, read(self.$ts.as_ptr().add(self.len)))*
))
}
}
}
pub fn remove(&mut self, index: usize) -> ($t1 $(, $ts)*) {
let len = self.len;
assert!(index < len);
unsafe {
let $t1;
$(let $ts;)*
{
let ptr = self.$t1.as_ptr().add(index);
$t1 = read(ptr);
copy(ptr.offset(1), ptr, len - index - 1);
}
$({
let ptr = self.$ts.as_ptr().add(index);
$ts = read(ptr);
copy(ptr.offset(1), ptr, len - index - 1);
})*
self.len = len - 1;
($t1 $(, $ts)*)
}
}
pub fn swap_remove(&mut self, index: usize) -> ($t1 $(, $ts)*) {
if index >= self.len {
panic!("Index out of bounds");
}
unsafe {
let $t1 = self.$t1.as_ptr().add(index);
$(let $ts = self.$ts.as_ptr().add(index);)*
let v = (
read($t1)
$(, read($ts))*
);
self.len -= 1;
if self.len != index {
copy_nonoverlapping(self.$t1.as_ptr().add(self.len), $t1, 1);
$(copy_nonoverlapping(self.$ts.as_ptr().add(self.len), $ts, 1);)*
}
v
}
}
fn layout_for_capacity(capacity: usize) -> OwnLayout {
let layout = Layout::array::<$t1>(capacity).unwrap();
$(let (layout, $ts) = layout.extend(Layout::array::<$ts>(capacity).unwrap()).unwrap();)*
OwnLayout {
layout
$(, $ts)*
}
}
#[inline(always)]
pub fn slices<'a>(&self) -> (&'a [$t1] $(, &'a [$ts])*) {
unsafe {
(
from_raw_parts::<'a>(self.$t1.as_ptr(), self.len),
$(from_raw_parts::<'a>(self.$ts.as_ptr(), self.len),)*
)
}
}
#[inline(always)]
pub fn iters<'a>(&self) -> (Iter<'a, $t1> $(, Iter<'a, $ts>)*) {
unsafe {
(
from_raw_parts::<'a>(self.$t1.as_ptr(), self.len).iter()
$(, from_raw_parts::<'a>(self.$ts.as_ptr(), self.len).iter())*
)
}
}
#[inline(always)]
pub fn iters_mut<'a>(&mut self) -> (IterMut<'a, $t1> $(, IterMut<'a, $ts>)*) {
unsafe {
(
from_raw_parts_mut::<'a>(self.$t1.as_ptr(), self.len).iter_mut()
$(, from_raw_parts_mut::<'a>(self.$ts.as_ptr(), self.len).iter_mut())*
)
}
}
#[inline(always)]
pub fn slices_mut<'a>(&self) -> (&'a mut [$t1] $(, &'a mut [$ts])*) {
unsafe {
(
from_raw_parts_mut::<'a>(self.$t1.as_ptr(), self.len),
$(from_raw_parts_mut::<'a>(self.$ts.as_ptr(), self.len),)*
)
}
}
pub fn index<'a>(&self, index: usize) -> (&'a $t1 $(, &'a $ts)*) {
unsafe {
if index >= self.len {
panic!("Index out of range");
}
(
&*self.$t1.as_ptr().add(index)
$(, &*self.$ts.as_ptr().add(index))*
)
}
}
pub fn sort_unstable_by<F: FnMut((&$t1 $(, &$ts)*), (&$t1 $(, &$ts)*))->Ordering>(&mut self, mut f: F) {
if self.len < 2 {
return;
}
let mut indices = acquire(0..self.len);
indices.sort_unstable_by(|a, b| unsafe {
f(
(&*self.$t1.as_ptr().add(*a) $(, &*self.$ts.as_ptr().add(*a))*, ),
(&*self.$t1.as_ptr().add(*b) $(, &*self.$ts.as_ptr().add(*b))*, ),
)});
let mut lookup = unsafe { acquire_uninitialized(self.len) };
for (i, index) in indices.iter().enumerate() {
lookup[*index] = i;
}
let ($t1 $(, $ts)*) = self.slices_mut();
for i in 0..indices.len() {
let dest = indices[i];
if i != dest {
$t1.swap(i, dest);
$($ts.swap(i, dest);)*
indices[lookup[i]] = dest;
lookup[dest] = lookup[i];
}
}
}
pub fn drain<R: RangeBounds<usize>>(&mut self, range: R) -> Drain<$t1 $(, $ts)*> {
let len = self.len();
let start = match range.start_bound() {
Included(&n) => n,
Excluded(&n) => n + 1,
Unbounded => 0,
};
let end = match range.end_bound() {
Included(&n) => n + 1,
Excluded(&n) => n,
Unbounded => len,
};
assert!(start <= end);
assert!(end <= len);
let iter = unsafe { RawValIter::new(&self, start, end - start) };
self.len = start;
Drain {
tail_start: end,
tail_len: len - end,
iter,
soa: NonNull::from(self),
}
}
}
struct OwnLayout {
layout: Layout,
$($ts: usize,)*
}
struct RawValIter<'a, $t1: 'a $(, $ts: 'a)*> {
$t1: StartEnd<'a, $t1>,
$($ts: StartEnd<'a, $ts>,)*
}
impl<'a, $t1: 'a $(, $ts: 'a)*> RawValIter<'a, $t1 $(, $ts)*> {
unsafe fn new(soa: &$name<$t1 $(, $ts)*>, start: usize, len: usize) -> Self {
Self {
$t1: StartEnd::new(soa.$t1, start, len),
$($ts: StartEnd::new(soa.$ts, start, len),)*
}
}
}
impl<'a, $t1: 'a $(, $ts: 'a)*> Iterator for RawValIter<'a, $t1 $(, $ts)*> {
type Item = ($t1 $(, $ts)*);
fn next(&mut self) -> Option<Self::Item> {
if self.$t1.is_empty() {
None
} else {
unsafe { Some((self.$t1.next() $(, self.$ts.next())*)) }
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.$t1.len();
(len, Some(len))
}
}
impl<'a, $t1 $(, $ts)*> ExactSizeIterator for RawValIter<'a, $t1 $(, $ts)*> {
fn len(&self) -> usize {
self.$t1.len()
}
}
impl<'a, $t1: 'a $(, $ts: 'a)*> DoubleEndedIterator for RawValIter<'a, $t1 $(, $ts)*> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.$t1.is_empty() {
None
} else {
unsafe { Some((self.$t1.next_back() $(, self.$ts.next_back())*)) }
}
}
}
struct StartEnd<'a, T: 'a> {
start: *const T,
end: *const T,
_marker: PhantomData<&'a T>,
}
impl<'a, T: 'a> StartEnd<'a, T> {
pub unsafe fn new(ptr: NonNull<T>, offset: usize, len: usize) -> Self {
let start = if len == 0 { ptr.as_ptr() } else { ptr.as_ptr().add(offset) };
Self {
start,
end: if len == 0 { start } else { start.add(len) },
_marker: PhantomData,
}
}
pub unsafe fn next(&mut self) -> T {
let result = read(self.start);
self.start = self.start.offset(1);
result
}
pub unsafe fn next_back(&mut self) -> T {
self.end = self.end.offset(-1);
read(self.end)
}
pub fn is_empty(&self) -> bool {
self.start == self.end
}
pub fn len(&self) -> usize {
(self.end as usize - self.start as usize) / std::mem::size_of::<T>()
}
}
pub struct Drain<'a, $t1: 'a $(, $ts: 'a)*> {
soa: NonNull<$name<$t1 $(, $ts)*>>,
iter: RawValIter<'a, $t1 $(, $ts)*>,
tail_start: usize,
tail_len: usize,
}
impl<'a, $t1: 'a $(, $ts: 'a)*> Iterator for Drain<'a, $t1 $(, $ts)*> {
type Item = ($t1 $(, $ts)*);
fn next(&mut self) -> Option<Self::Item> { self.iter.next() }
fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
}
impl<'a, $t1: 'a $(, $ts: 'a)*> DoubleEndedIterator for Drain<'a, $t1 $(, $ts)*> {
fn next_back(&mut self) -> Option<Self::Item> { self.iter.next_back() }
}
impl<'a, $t1: 'a $(, $ts: 'a)*> ExactSizeIterator for Drain<'a, $t1 $(, $ts)*> {
fn len(&self) -> usize { self.iter.len() }
}
impl<'a, $t1: 'a $(, $ts: 'a)*> Drop for Drain<'a, $t1 $(, $ts)*> {
fn drop(&mut self) {
self.for_each(drop);
if self.tail_len > 0 {
unsafe {
let source_soa = self.soa.as_mut();
let start = source_soa.len();
let tail = self.tail_start;
if tail != start {
{
let src = source_soa.$t1.as_ptr().add(tail);
let dst = source_soa.$t1.as_ptr().add(start);
copy(src, dst, self.tail_len);
}
$({
let src = source_soa.$ts.as_ptr().add(tail);
let dst = source_soa.$ts.as_ptr().add(start);
copy(src, dst, self.tail_len);
})*
}
source_soa.len = start + self.tail_len;
}
}
}
}
impl<$t1: Sized $(, $ts: Sized)*> Drop for $name<$t1 $(, $ts)*> {
fn drop(&mut self) {
self.clear();
self.dealloc()
}
}
impl<$t1: Clone + Sized $(, $ts: Clone + Sized)*> Clone for $name<$t1 $(, $ts)*> {
fn clone(&self) -> Self {
let mut result = Self::with_capacity(self.len);
unsafe {
for i in 0..self.len {
let $t1 = (&*(self.$t1.as_ptr().add(i))).clone();
$(let $ts = (&*(self.$ts.as_ptr().add(i))).clone();)*
write(result.$t1.as_ptr().add(i), $t1);
$(write(result.$ts.as_ptr().add(i), $ts);)*;
result.len = i + 1;
}
}
result
}
}
impl<$t1: Sized $(, $ts: Sized)*> Default for $name<$t1 $(, $ts)*> {
fn default() -> Self { Self::new() }
}
}
};
}
soa!(Soa2, T1, T2);
soa!(Soa3, T1, T2, T3);
soa!(Soa4, T1, T2, T3, T4);
soa!(Soa5, T1, T2, T3, T4, T5);
soa!(Soa6, T1, T2, T3, T4, T5, T6);
soa!(Soa7, T1, T2, T3, T4, T5, T6, T7);
soa!(Soa8, T1, T2, T3, T4, T5, T6, T7, T8);
#[cfg(test)]
mod tests {
use super::{Soa2::Soa2, Soa3::Soa3};
use testdrop::TestDrop;
fn assert_all_dropped(td: &TestDrop) {
assert_eq!(td.num_dropped_items(), td.num_tracked_items());
}
#[test]
fn layouts_do_not_overlap() {
let mut soa_ab = Soa2::new();
let mut soa_ba = Soa2::new();
fn ab(v: usize) -> (u8, f64) {
(v as u8, 200.0 + ((v as f64) / 200.0))
}
fn ba(v: usize) -> (f64, u8) {
(15.0 + ((v as f64) / 16.0), (200 - v) as u8)
}
for i in 0..100 {
soa_ab.push(ab(i));
let (a, b) = soa_ab.slices();
assert_eq!(i + 1, a.len());
assert_eq!(i + 1, b.len());
assert_eq!(ab(0).0, a[0]);
assert_eq!(ab(0).1, b[0]);
assert_eq!(ab(i).0, a[i]);
assert_eq!(ab(i).1, b[i]);
soa_ba.push(ba(i));
let (b, a) = soa_ba.slices();
assert_eq!(i + 1, a.len());
assert_eq!(i + 1, b.len());
assert_eq!(ba(0).0, b[0]);
assert_eq!(ba(0).1, a[0]);
assert_eq!(ba(i).0, b[i]);
assert_eq!(ba(i).1, a[i]);
}
}
#[test]
fn sort() {
let mut soa = Soa3::new();
soa.push((3, 'a', 4.0));
soa.push((1, 'b', 5.0));
soa.push((2, 'c', 6.0));
soa.sort_unstable_by(|(a1, _, _), (a2, _, _)| a1.cmp(a2));
assert_eq!(soa.index(0), (&1, &('b'), &5.0));
assert_eq!(soa.index(1), (&2, &('c'), &6.0));
assert_eq!(soa.index(2), (&3, &('a'), &4.0));
}
#[test]
fn drops() {
let td = TestDrop::new();
let (id, item) = td.new_item();
{
let mut soa = Soa2::new();
soa.push((1.0, item));
td.assert_no_drop(id);
for _ in 0..50 {
soa.push((2.0, td.new_item().1));
}
td.assert_no_drop(id);
}
td.assert_drop(id);
assert_all_dropped(&td);
}
#[test]
fn clones() {
let mut src = Soa2::new();
src.push((1.0, 2.0));
src.push((3.0, 4.0));
let dst = src.clone();
assert_eq!(dst.len(), 2);
assert_eq!(dst.index(0), (&1.0, &2.0));
assert_eq!(dst.index(1), (&3.0, &4.0));
}
#[test]
fn insert() {
let mut src = Soa2::new();
src.insert(0, (1, 2));
src.insert(0, (3, 4));
src.insert(1, (4, 5));
assert_eq!(src.index(0), (&3, &4));
assert_eq!(src.index(1), (&4, &5));
assert_eq!(src.index(2), (&1, &2));
}
#[test]
fn remove() {
let mut src = Soa2::new();
src.push((1, 2));
src.push((3, 4));
assert_eq!(src.remove(0), (1, 2));
assert_eq!(src.remove(0), (3, 4));
assert_eq!(src.len(), 0);
}
#[test]
fn drain() {
let td = TestDrop::new();
let (id, item) = td.new_item();
let mut soa = Soa2::new();
soa.push((1.0, item));
let (_id2, item2) = td.new_item();
soa.push((2.0, item2));
let drain = soa.drain(..1);
td.assert_no_drop(id);
let mut count = 0;
for drained in drain {
count += 1;
assert_eq!(drained.0, 1.0);
}
assert_eq!(1, count);
td.assert_drop(id);
assert_eq!(*soa.index(0).0, 2.0);
drop(soa);
assert_all_dropped(&td);
}
}