#![doc(html_root_url = "https://doc.rust-lang.org/nightly/",
test(no_crate_inject, attr(deny(warnings))))]
#![deny(rust_2018_idioms)]
#![deny(internal)]
#![feature(rustc_private, core_intrinsics)]
#![feature(dropck_eyepatch)]
#![feature(raw_vec_internals)]
#![cfg_attr(test, feature(test))]
#![allow(deprecated)]
extern crate alloc;
use rustc_data_structures::cold_path;
use rustc_data_structures::sync::MTLock;
use smallvec::SmallVec;
use std::cell::{Cell, RefCell};
use std::cmp;
use std::intrinsics;
use std::marker::{PhantomData, Send};
use std::mem;
use std::ptr;
use std::slice;
use alloc::raw_vec::RawVec;
pub struct TypedArena<T> {
ptr: Cell<*mut T>,
end: Cell<*mut T>,
chunks: RefCell<Vec<TypedArenaChunk<T>>>,
_own: PhantomData<T>,
}
struct TypedArenaChunk<T> {
storage: RawVec<T>,
entries: usize,
}
impl<T> TypedArenaChunk<T> {
#[inline]
unsafe fn new(capacity: usize) -> TypedArenaChunk<T> {
TypedArenaChunk {
storage: RawVec::with_capacity(capacity),
entries: 0,
}
}
#[inline]
unsafe fn destroy(&mut self, len: usize) {
if mem::needs_drop::<T>() {
let mut start = self.start();
for _ in 0..len {
ptr::drop_in_place(start);
start = start.offset(1);
}
}
}
#[inline]
fn start(&self) -> *mut T {
self.storage.ptr()
}
#[inline]
fn end(&self) -> *mut T {
unsafe {
if mem::size_of::<T>() == 0 {
!0 as *mut T
} else {
self.start().add(self.storage.cap())
}
}
}
}
const PAGE: usize = 4096;
impl<T> Default for TypedArena<T> {
fn default() -> TypedArena<T> {
TypedArena {
ptr: Cell::new(0 as *mut T),
end: Cell::new(0 as *mut T),
chunks: RefCell::new(vec![]),
_own: PhantomData,
}
}
}
impl<T> TypedArena<T> {
pub fn in_arena(&self, ptr: *const T) -> bool {
let ptr = ptr as *const T as *mut T;
self.chunks.borrow().iter().any(|chunk| chunk.start() <= ptr && ptr < chunk.end())
}
#[inline]
pub fn alloc(&self, object: T) -> &mut T {
if self.ptr == self.end {
self.grow(1)
}
unsafe {
if mem::size_of::<T>() == 0 {
self.ptr
.set(intrinsics::arith_offset(self.ptr.get() as *mut u8, 1)
as *mut T);
let ptr = mem::align_of::<T>() as *mut T;
ptr::write(ptr, object);
&mut *ptr
} else {
let ptr = self.ptr.get();
self.ptr.set(self.ptr.get().offset(1));
ptr::write(ptr, object);
&mut *ptr
}
}
}
#[inline]
fn can_allocate(&self, len: usize) -> bool {
let available_capacity_bytes = self.end.get() as usize - self.ptr.get() as usize;
let at_least_bytes = len.checked_mul(mem::size_of::<T>()).unwrap();
available_capacity_bytes >= at_least_bytes
}
#[inline]
fn ensure_capacity(&self, len: usize) {
if !self.can_allocate(len) {
self.grow(len);
debug_assert!(self.can_allocate(len));
}
}
#[inline]
unsafe fn alloc_raw_slice(&self, len: usize) -> *mut T {
assert!(mem::size_of::<T>() != 0);
assert!(len != 0);
self.ensure_capacity(len);
let start_ptr = self.ptr.get();
self.ptr.set(start_ptr.add(len));
start_ptr
}
#[inline]
pub fn alloc_slice(&self, slice: &[T]) -> &mut [T]
where
T: Copy,
{
unsafe {
let len = slice.len();
let start_ptr = self.alloc_raw_slice(len);
slice.as_ptr().copy_to_nonoverlapping(start_ptr, len);
slice::from_raw_parts_mut(start_ptr, len)
}
}
#[inline]
pub fn alloc_from_iter<I: IntoIterator<Item = T>>(&self, iter: I) -> &mut [T] {
assert!(mem::size_of::<T>() != 0);
let mut iter = iter.into_iter();
let size_hint = iter.size_hint();
match size_hint {
(min, Some(max)) if min == max => {
let len = min;
if len == 0 {
return &mut [];
}
self.ensure_capacity(len);
let slice = self.ptr.get();
unsafe {
let mut ptr = self.ptr.get();
for _ in 0..len {
ptr::write(ptr, iter.next().unwrap());
ptr = ptr.offset(1);
self.ptr.set(ptr);
}
slice::from_raw_parts_mut(slice, len)
}
}
_ => {
cold_path(move || -> &mut [T] {
let mut vec: SmallVec<[_; 8]> = iter.collect();
if vec.is_empty() {
return &mut [];
}
unsafe {
let len = vec.len();
let start_ptr = self.alloc_raw_slice(len);
vec.as_ptr().copy_to_nonoverlapping(start_ptr, len);
vec.set_len(0);
slice::from_raw_parts_mut(start_ptr, len)
}
})
}
}
}
#[inline(never)]
#[cold]
fn grow(&self, n: usize) {
unsafe {
let mut chunks = self.chunks.borrow_mut();
let (chunk, mut new_capacity);
if let Some(last_chunk) = chunks.last_mut() {
let used_bytes = self.ptr.get() as usize - last_chunk.start() as usize;
let currently_used_cap = used_bytes / mem::size_of::<T>();
last_chunk.entries = currently_used_cap;
if last_chunk.storage.reserve_in_place(currently_used_cap, n) {
self.end.set(last_chunk.end());
return;
} else {
new_capacity = last_chunk.storage.cap();
loop {
new_capacity = new_capacity.checked_mul(2).unwrap();
if new_capacity >= currently_used_cap + n {
break;
}
}
}
} else {
let elem_size = cmp::max(1, mem::size_of::<T>());
new_capacity = cmp::max(n, PAGE / elem_size);
}
chunk = TypedArenaChunk::<T>::new(new_capacity);
self.ptr.set(chunk.start());
self.end.set(chunk.end());
chunks.push(chunk);
}
}
pub fn clear(&mut self) {
unsafe {
let mut chunks_borrow = self.chunks.borrow_mut();
if let Some(mut last_chunk) = chunks_borrow.last_mut() {
self.clear_last_chunk(&mut last_chunk);
let len = chunks_borrow.len();
for mut chunk in chunks_borrow.drain(..len-1) {
chunk.destroy(chunk.entries);
}
}
}
}
fn clear_last_chunk(&self, last_chunk: &mut TypedArenaChunk<T>) {
let start = last_chunk.start() as usize;
let end = self.ptr.get() as usize;
let diff = if mem::size_of::<T>() == 0 {
end - start
} else {
(end - start) / mem::size_of::<T>()
};
unsafe {
last_chunk.destroy(diff);
}
self.ptr.set(last_chunk.start());
}
}
unsafe impl<#[may_dangle] T> Drop for TypedArena<T> {
fn drop(&mut self) {
unsafe {
let mut chunks_borrow = self.chunks.borrow_mut();
if let Some(mut last_chunk) = chunks_borrow.pop() {
self.clear_last_chunk(&mut last_chunk);
for chunk in chunks_borrow.iter_mut() {
chunk.destroy(chunk.entries);
}
}
}
}
}
unsafe impl<T: Send> Send for TypedArena<T> {}
pub struct DroplessArena {
ptr: Cell<*mut u8>,
end: Cell<*mut u8>,
chunks: RefCell<Vec<TypedArenaChunk<u8>>>,
}
unsafe impl Send for DroplessArena {}
impl Default for DroplessArena {
#[inline]
fn default() -> DroplessArena {
DroplessArena {
ptr: Cell::new(0 as *mut u8),
end: Cell::new(0 as *mut u8),
chunks: Default::default(),
}
}
}
impl DroplessArena {
pub fn in_arena<T: ?Sized>(&self, ptr: *const T) -> bool {
let ptr = ptr as *const u8 as *mut u8;
self.chunks.borrow().iter().any(|chunk| chunk.start() <= ptr && ptr < chunk.end())
}
#[inline]
fn align(&self, align: usize) {
let final_address = ((self.ptr.get() as usize) + align - 1) & !(align - 1);
self.ptr.set(final_address as *mut u8);
assert!(self.ptr <= self.end);
}
#[inline(never)]
#[cold]
fn grow(&self, needed_bytes: usize) {
unsafe {
let mut chunks = self.chunks.borrow_mut();
let (chunk, mut new_capacity);
if let Some(last_chunk) = chunks.last_mut() {
let used_bytes = self.ptr.get() as usize - last_chunk.start() as usize;
if last_chunk
.storage
.reserve_in_place(used_bytes, needed_bytes)
{
self.end.set(last_chunk.end());
return;
} else {
new_capacity = last_chunk.storage.cap();
loop {
new_capacity = new_capacity.checked_mul(2).unwrap();
if new_capacity >= used_bytes + needed_bytes {
break;
}
}
}
} else {
new_capacity = cmp::max(needed_bytes, PAGE);
}
chunk = TypedArenaChunk::<u8>::new(new_capacity);
self.ptr.set(chunk.start());
self.end.set(chunk.end());
chunks.push(chunk);
}
}
#[inline]
pub fn alloc_raw(&self, bytes: usize, align: usize) -> &mut [u8] {
unsafe {
assert!(bytes != 0);
self.align(align);
let future_end = intrinsics::arith_offset(self.ptr.get(), bytes as isize);
if (future_end as *mut u8) >= self.end.get() {
self.grow(bytes);
}
let ptr = self.ptr.get();
self.ptr.set(
intrinsics::arith_offset(self.ptr.get(), bytes as isize) as *mut u8,
);
slice::from_raw_parts_mut(ptr, bytes)
}
}
#[inline]
pub fn alloc<T>(&self, object: T) -> &mut T {
assert!(!mem::needs_drop::<T>());
let mem = self.alloc_raw(
mem::size_of::<T>(),
mem::align_of::<T>()) as *mut _ as *mut T;
unsafe {
ptr::write(mem, object);
&mut *mem
}
}
#[inline]
pub fn alloc_slice<T>(&self, slice: &[T]) -> &mut [T]
where
T: Copy,
{
assert!(!mem::needs_drop::<T>());
assert!(mem::size_of::<T>() != 0);
assert!(!slice.is_empty());
let mem = self.alloc_raw(
slice.len() * mem::size_of::<T>(),
mem::align_of::<T>()) as *mut _ as *mut T;
unsafe {
let arena_slice = slice::from_raw_parts_mut(mem, slice.len());
arena_slice.copy_from_slice(slice);
arena_slice
}
}
#[inline]
unsafe fn write_from_iter<T, I: Iterator<Item = T>>(
&self,
mut iter: I,
len: usize,
mem: *mut T,
) -> &mut [T] {
let mut i = 0;
loop {
let value = iter.next();
if i >= len || value.is_none() {
return slice::from_raw_parts_mut(mem, i);
}
ptr::write(mem.offset(i as isize), value.unwrap());
i += 1;
}
}
#[inline]
pub fn alloc_from_iter<T, I: IntoIterator<Item = T>>(&self, iter: I) -> &mut [T] {
let iter = iter.into_iter();
assert!(mem::size_of::<T>() != 0);
assert!(!mem::needs_drop::<T>());
let size_hint = iter.size_hint();
match size_hint {
(min, Some(max)) if min == max => {
let len = min;
if len == 0 {
return &mut []
}
let size = len.checked_mul(mem::size_of::<T>()).unwrap();
let mem = self.alloc_raw(size, mem::align_of::<T>()) as *mut _ as *mut T;
unsafe {
self.write_from_iter(iter, len, mem)
}
}
(_, _) => {
cold_path(move || -> &mut [T] {
let mut vec: SmallVec<[_; 8]> = iter.collect();
if vec.is_empty() {
return &mut [];
}
unsafe {
let len = vec.len();
let start_ptr = self.alloc_raw(
len * mem::size_of::<T>(),
mem::align_of::<T>()
) as *mut _ as *mut T;
vec.as_ptr().copy_to_nonoverlapping(start_ptr, len);
vec.set_len(0);
slice::from_raw_parts_mut(start_ptr, len)
}
})
}
}
}
}
#[derive(Default)]
pub struct SyncTypedArena<T> {
lock: MTLock<TypedArena<T>>,
}
impl<T> SyncTypedArena<T> {
#[inline(always)]
pub fn alloc(&self, object: T) -> &mut T {
unsafe { &mut *(self.lock.lock().alloc(object) as *mut T) }
}
#[inline(always)]
pub fn alloc_slice(&self, slice: &[T]) -> &mut [T]
where
T: Copy,
{
unsafe { &mut *(self.lock.lock().alloc_slice(slice) as *mut [T]) }
}
#[inline(always)]
pub fn clear(&mut self) {
self.lock.get_mut().clear();
}
}
#[derive(Default)]
pub struct SyncDroplessArena {
lock: MTLock<DroplessArena>,
}
impl SyncDroplessArena {
#[inline(always)]
pub fn in_arena<T: ?Sized>(&self, ptr: *const T) -> bool {
self.lock.lock().in_arena(ptr)
}
#[inline(always)]
pub fn alloc_raw(&self, bytes: usize, align: usize) -> &mut [u8] {
unsafe { &mut *(self.lock.lock().alloc_raw(bytes, align) as *mut [u8]) }
}
#[inline(always)]
pub fn alloc<T>(&self, object: T) -> &mut T {
unsafe { &mut *(self.lock.lock().alloc(object) as *mut T) }
}
#[inline(always)]
pub fn alloc_slice<T>(&self, slice: &[T]) -> &mut [T]
where
T: Copy,
{
unsafe { &mut *(self.lock.lock().alloc_slice(slice) as *mut [T]) }
}
}
#[cfg(test)]
mod tests {
extern crate test;
use test::Bencher;
use super::TypedArena;
use std::cell::Cell;
#[allow(dead_code)]
#[derive(Debug, Eq, PartialEq)]
struct Point {
x: i32,
y: i32,
z: i32,
}
#[test]
pub fn test_unused() {
let arena: TypedArena<Point> = TypedArena::default();
assert!(arena.chunks.borrow().is_empty());
}
#[test]
fn test_arena_alloc_nested() {
struct Inner {
value: u8,
}
struct Outer<'a> {
inner: &'a Inner,
}
enum EI<'e> {
I(Inner),
O(Outer<'e>),
}
struct Wrap<'a>(TypedArena<EI<'a>>);
impl<'a> Wrap<'a> {
fn alloc_inner<F: Fn() -> Inner>(&self, f: F) -> &Inner {
let r: &EI<'_> = self.0.alloc(EI::I(f()));
if let &EI::I(ref i) = r {
i
} else {
panic!("mismatch");
}
}
fn alloc_outer<F: Fn() -> Outer<'a>>(&self, f: F) -> &Outer<'_> {
let r: &EI<'_> = self.0.alloc(EI::O(f()));
if let &EI::O(ref o) = r {
o
} else {
panic!("mismatch");
}
}
}
let arena = Wrap(TypedArena::default());
let result = arena.alloc_outer(|| Outer {
inner: arena.alloc_inner(|| Inner { value: 10 }),
});
assert_eq!(result.inner.value, 10);
}
#[test]
pub fn test_copy() {
let arena = TypedArena::default();
for _ in 0..100000 {
arena.alloc(Point { x: 1, y: 2, z: 3 });
}
}
#[bench]
pub fn bench_copy(b: &mut Bencher) {
let arena = TypedArena::default();
b.iter(|| arena.alloc(Point { x: 1, y: 2, z: 3 }))
}
#[bench]
pub fn bench_copy_nonarena(b: &mut Bencher) {
b.iter(|| {
let _: Box<_> = Box::new(Point { x: 1, y: 2, z: 3 });
})
}
#[allow(dead_code)]
struct Noncopy {
string: String,
array: Vec<i32>,
}
#[test]
pub fn test_noncopy() {
let arena = TypedArena::default();
for _ in 0..100000 {
arena.alloc(Noncopy {
string: "hello world".to_string(),
array: vec![1, 2, 3, 4, 5],
});
}
}
#[test]
pub fn test_typed_arena_zero_sized() {
let arena = TypedArena::default();
for _ in 0..100000 {
arena.alloc(());
}
}
#[test]
pub fn test_typed_arena_clear() {
let mut arena = TypedArena::default();
for _ in 0..10 {
arena.clear();
for _ in 0..10000 {
arena.alloc(Point { x: 1, y: 2, z: 3 });
}
}
}
#[bench]
pub fn bench_typed_arena_clear(b: &mut Bencher) {
let mut arena = TypedArena::default();
b.iter(|| {
arena.alloc(Point { x: 1, y: 2, z: 3 });
arena.clear();
})
}
struct DropCounter<'a> {
count: &'a Cell<u32>,
}
impl Drop for DropCounter<'_> {
fn drop(&mut self) {
self.count.set(self.count.get() + 1);
}
}
#[test]
fn test_typed_arena_drop_count() {
let counter = Cell::new(0);
{
let arena: TypedArena<DropCounter<'_>> = TypedArena::default();
for _ in 0..100 {
arena.alloc(DropCounter { count: &counter });
}
};
assert_eq!(counter.get(), 100);
}
#[test]
fn test_typed_arena_drop_on_clear() {
let counter = Cell::new(0);
let mut arena: TypedArena<DropCounter<'_>> = TypedArena::default();
for i in 0..10 {
for _ in 0..100 {
arena.alloc(DropCounter { count: &counter });
}
arena.clear();
assert_eq!(counter.get(), i * 100 + 100);
}
}
thread_local! {
static DROP_COUNTER: Cell<u32> = Cell::new(0)
}
struct SmallDroppable;
impl Drop for SmallDroppable {
fn drop(&mut self) {
DROP_COUNTER.with(|c| c.set(c.get() + 1));
}
}
#[test]
fn test_typed_arena_drop_small_count() {
DROP_COUNTER.with(|c| c.set(0));
{
let arena: TypedArena<SmallDroppable> = TypedArena::default();
for _ in 0..100 {
arena.alloc(SmallDroppable);
}
};
assert_eq!(DROP_COUNTER.with(|c| c.get()), 100);
}
#[bench]
pub fn bench_noncopy(b: &mut Bencher) {
let arena = TypedArena::default();
b.iter(|| {
arena.alloc(Noncopy {
string: "hello world".to_string(),
array: vec![1, 2, 3, 4, 5],
})
})
}
#[bench]
pub fn bench_noncopy_nonarena(b: &mut Bencher) {
b.iter(|| {
let _: Box<_> = Box::new(Noncopy {
string: "hello world".to_string(),
array: vec![1, 2, 3, 4, 5],
});
})
}
}