dsa_rust/util/
bump_arena.rs

1/*! A naive bump arena
2
3# About
4A simple bump arena (allocator) that allocates objects sequentially from a single contiguous memory region. Allocation is performed by pointer arithmetic and does not support individual deallocation; instead, all objects are dropped and the backing memory is released when the arena itself is dropped.
5
6Objects allocated from the arena have stable addresses for the lifetime of the arena, making this structure well suited for data structures that rely on pointer stability, such as positional lists or graph nodes. The contiguous layout provides array-like cache locality, while avoiding the overhead of per-allocation heap management or reference counting.
7
8This arena was written to support a simple positional list abstraction, but the same allocation strategy applies naturally to graph representations. In practice, higher-level abstractions such as maps or indexed containers are often layered on top of arenas to provide more flexible access patterns.
9
10# Design
11In contrast with a simple [pointer bag]() (typcally as a `Vec` of pointers), this design represents a real minimal bump allocator.
12
13# Example
14
15*/
16
17use std::alloc::{alloc, dealloc, Layout};
18use std::ptr::{self, NonNull};
19
20pub struct BumpArena<T> {
21    ptr: NonNull<T>,
22    capacity: usize,
23    len: usize,
24}
25
26impl<T> BumpArena<T> {
27    /// Self contains a pointer to the first slot,
28    /// a capacity mirroring the input, and a length
29    /// as the number of slots used in the arena
30    pub fn new(capacity: usize) -> Self {
31        assert!(capacity > 0);
32
33        let layout = Layout::array::<T>(capacity).unwrap();
34        let raw = unsafe { alloc(layout) as *mut T };
35
36        let ptr = NonNull::new(raw).expect("allocation failed");
37
38        Self {
39            ptr,
40            capacity,
41            len: 0,
42        }
43    }
44
45    #[allow(dead_code)]
46    /// This
47    fn alloc(&mut self, value: T) -> *mut T {
48        assert!(self.len < self.capacity, "arena exhausted");
49
50        let slot = unsafe { self.ptr.as_ptr().add(self.len) };
51        unsafe { ptr::write(slot, value) };
52
53        self.len += 1;
54        slot
55    }
56}
57
58impl<T> Drop for BumpArena<T> {
59    fn drop(&mut self) {
60        unsafe {
61            for i in 0..self.len {
62                ptr::drop_in_place(self.ptr.as_ptr().add(i));
63            }
64
65            let layout = Layout::array::<T>(self.capacity).unwrap();
66            dealloc(self.ptr.as_ptr() as *mut u8, layout);
67        }
68    }
69}
70
71#[allow(unused)]
72struct Test {
73    str: String,
74    size: usize,
75}
76#[test]
77fn arena_test() {
78    let _ = BumpArena::<usize>::new(10);
79
80    let test = Test {
81        str: "Hello, world!".to_string(),
82        size: 42,
83    };
84
85    // LHS annotation
86    let mut v: Vec<&Test> = Vec::with_capacity(64);
87    v.push(&test);
88
89    // Turbofish after function
90    //let mut v = Vec::with_capacity::<&Test>(64);
91    //v.push(&test);
92
93    // Turbofish after type
94    let mut v = Vec::<&Test>::with_capacity(64);
95    v.push(&test);
96
97    // No generic specifier
98    let mut v = Vec::with_capacity(64);
99    v.push(&test);
100
101    // Works with new too
102    let mut v = Vec::new();
103    v.push(&test);
104}
dsa_rust/util/bump_arena.rs

dsa_rust/util/
bump_arena.rs
