safe_arena/
safe_arena.rs

1//! A typed arena allocator implementation with no unsafe code or interior
2//! mutability.
3//!
4//! API inspired by the [`typed_arena`] crate.
5//!
6//! [`typed_arena`]: https://docs.rs/typed-arena/latest/typed_arena/
7
8use std::{cell::Cell, mem};
9
10use loaned::{drop, LoanedMut};
11
12pub struct Arena<'t, T> {
13  cursor: &'t mut [Option<T>],
14  chunks: Vec<LoanedMut<'t, Box<[Option<T>]>>>,
15  capacity: usize,
16}
17
18impl<'t, T> Arena<'t, T> {
19  pub fn with_capacity(capacity: usize) -> Self {
20    let capacity = capacity.max(1);
21    let (cursor, chunk) = Self::new_chunk(capacity);
22    Arena {
23      cursor,
24      chunks: vec![chunk],
25      capacity,
26    }
27  }
28
29  fn new_chunk(capacity: usize) -> (&'t mut [Option<T>], LoanedMut<'t, Box<[Option<T>]>>) {
30    let mut chunk = Vec::with_capacity(capacity);
31    chunk.resize_with(capacity, || None);
32    let chunk = chunk.into_boxed_slice();
33    let (cursor, chunk) = LoanedMut::loan(chunk);
34    (cursor, chunk)
35  }
36
37  pub fn alloc(&mut self, value: T) -> &'t mut T {
38    if self.cursor.is_empty() {
39      self.capacity *= 2;
40      let (cursor, chunk) = Self::new_chunk(self.capacity);
41      self.cursor = cursor;
42      self.chunks.push(chunk);
43    }
44    let cursor = mem::replace(&mut self.cursor, &mut []);
45    let (slot, cursor) = cursor.split_first_mut().unwrap();
46    self.cursor = cursor;
47    *slot = Some(value);
48    let Some(slot) = slot else { unreachable!() };
49    slot
50  }
51
52  pub fn into_inner(self) -> LoanedMut<'t, Vec<Box<[Option<T>]>>> {
53    self.chunks.into()
54  }
55}
56
57#[cfg_attr(test, test)]
58fn main() {
59  let mut arena = Arena::with_capacity(1);
60
61  struct CycleParticipant<'a> {
62    name: &'static str,
63    next: Cell<Option<&'a CycleParticipant<'a>>>,
64  }
65
66  impl<'a> CycleParticipant<'a> {
67    fn next(&self) -> &'a CycleParticipant<'a> {
68      self.next.get().unwrap()
69    }
70  }
71
72  let a = arena.alloc(CycleParticipant {
73    name: "a",
74    next: Cell::new(None),
75  });
76
77  let b = arena.alloc(CycleParticipant {
78    name: "b",
79    next: Cell::new(None),
80  });
81
82  a.next.set(Some(b));
83  b.next.set(Some(a));
84
85  print_assert_eq!(a.name, "a");
86  print_assert_eq!(a.next().name, "b");
87  print_assert_eq!(a.next().next().name, "a");
88
89  drop!(arena.into_inner());
90}
91
92#[macro_export]
93macro_rules! print_assert_eq {
94  ($x:expr, $y:expr) => {
95    println!("{} = {:?}", stringify!($x), $x);
96    assert_eq!($x, $y);
97  };
98}
safe_arena/safe_arena.rs

safe_arena/
safe_arena.rs
