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    /// This
46    fn alloc(&mut self, value: T) -> *mut T {
47        assert!(self.len < self.capacity, "arena exhausted");
48
49        let slot = unsafe { self.ptr.as_ptr().add(self.len) };
50        unsafe { ptr::write(slot, value) };
51
52        self.len += 1;
53        slot
54    }
55}
56
57impl<T> Drop for BumpArena<T> {
58    fn drop(&mut self) {
59        unsafe {
60            for i in 0..self.len {
61                ptr::drop_in_place(self.ptr.as_ptr().add(i));
62            }
63
64            let layout = Layout::array::<T>(self.capacity).unwrap();
65            dealloc(self.ptr.as_ptr() as *mut u8, layout);
66        }
67    }
68}
69
70#[allow(unused)]
71struct Test {
72    str: String,
73    size: usize,
74}
75#[test]
76fn arena_test() {
77    let _ = BumpArena::<usize>::new(10);
78
79    let test = Test {
80        str: "Hello, world!".to_string(),
81        size: 42,
82    };
83
84    // LHS annotation
85    let mut v: Vec<&Test> = Vec::with_capacity(64);
86    v.push(&test);
87
88    // Turbofish after function
89    //let mut v = Vec::with_capacity::<&Test>(64);
90    //v.push(&test);
91
92    // Turbofish after type
93    let mut v = Vec::<&Test>::with_capacity(64);
94    v.push(&test);
95
96    // No generic specifier
97    let mut v = Vec::with_capacity(64);
98    v.push(&test);
99
100    // Works with new too
101    let mut v = Vec::new();
102    v.push(&test);
103}
dsa_rust/util/bump_arena.rs

dsa_rust/util/
bump_arena.rs
