Arena crate selection guide

help
#1

Does anyone know of a good summary of the different arena crates? I know the properties I'm looking for, but can't seem to find one that supports all of the operations I need:

  • Single-type storage, will drop contents when dropped
  • ID-based (i.e. 'static keys)
  • Insertions via shared reference
  • Shared and mutable item getters (via & and &mut arena references, respectively)
  • Individual item removal not necessary
  • Capacity can be either fixed or auto-growing
1 Like
#2

As far as I can tell this

and

seem contradictory unless the type itself is Copy. Maybe I am not understanding something.

#3

They aren't; insertion via shared references merely means the arena contains interior mutability. If you don't use that, it's still possible to get regular mutable references to its elements. (Cf.: RefCell::get_mut())

2 Likes
#4

To provide a bit more context, I'm trying to write an arena with a copying GC. Normal object allocation and access will be via shared reference, but the GC cycle itself will have exclusive access while running.

1 Like
#5

I had hoped to avoid writing any unsafe code myself, but I ended up writing this primitive instead of continuing my search for an appropriate crate. Does this look sound?

Also, do I need MaybeUninit here, or is it redundant with UnsafeCell?

use std::mem::MaybeUninit;
use std::cell::{Cell, UnsafeCell};

pub struct Page<T, const CAP:usize> {
    len: Cell<usize>,
    buf: UnsafeCell<[MaybeUninit<T>; CAP]>,
}

impl<T, const CAP:usize> Page<T, CAP> {
    pub fn new()->Box<Self> {
        Box::new(Page {
            buf: UnsafeCell::new(
                unsafe { MaybeUninit::uninit().assume_init() }
            ),
            len: Cell::new(0)
        })
    }
    
    unsafe fn elem_ptr(&self, i:usize)->*mut MaybeUninit<T> {
        assert!(i < CAP);
        (self.buf.get() as *mut MaybeUninit<T>).add(i)
    }
    
    pub fn try_insert(&self, val:T)->Result<usize, T> {
        let i = self.len.get();
        if i < CAP {
            unsafe {
                // Safety: Shared references can only exist to
                // indices less than self.len(), so there is no
                // aliasing here
                *self.elem_ptr(i) = MaybeUninit::new(val);
            }
            self.len.set(i+1);
            Ok(i)
        } else {
            Err(val)
        }
    }
    
    pub fn get(&self, idx:usize)->Option<&T> {
        if idx >= self.len.get() { None }
        else {
            Some(unsafe { (&*self.elem_ptr(idx)).assume_init_ref() } )
        }
    }
    
    pub fn get_mut(&mut self, idx:usize)->Option<&mut T> {
        if idx >= self.len.get() { None }
        else {
            let slot = &mut self.buf.get_mut()[idx];
            // Safety: Because of &mut self,
            // there are no shared references to the buffer
            Some(unsafe{ slot.assume_init_mut() })
        }
    }
    
    /// Remove the most-recently inserted object
    pub fn pop(&mut self)->Option<T> {
        if self.len.get() == 0 { None }
        else {
            let idx = self.len.get() - 1;
            self.len.set(idx);
            // Safety: Because of &mut self,
            // there are no shared references to the buffer
            Some(unsafe { (&mut *self.elem_ptr(idx)).as_mut_ptr().read() })
        }
    }
    
    /// Drop all objects, but keep the allocation
    pub fn truncate(&mut self) {
        if std::mem::needs_drop::<T>() {
            while self.len.get() > 0 { self.pop(); }
        }
        else { self.len.set(0) }
    }
}

impl<T,const CAP:usize> Drop for Page<T,CAP> {
    fn drop(&mut self) { self.truncate() }
}
1 Like
#6

Looks good to me. I don't think the UnsafeCell is redundant with MaybeUninit – as far as I know, neither type provides a superset of guarantees of the other. You need UnsafeCell for interior mutability and MaybeUninit for manual late initialization.

3 Likes