bumpslab/
lib.rs

1use bumpalo::Bump;
2use std::cell::{Cell, UnsafeCell};
3use std::marker::PhantomData;
4use std::mem::ManuallyDrop;
5use std::ptr::NonNull;
6
7pub struct BumpSlab<T: Sized> {
8    bump: Bump,
9    next: Cell<Option<NonNull<SlotInner<T>>>>,
10    _p: PhantomData<T>,
11}
12
13impl<'a, T> BumpSlab<T> {
14    pub fn new() -> Self {
15        Self {
16            bump: Bump::new(),
17            next: Cell::new(None),
18            _p: PhantomData,
19        }
20    }
21
22    /// By default, you need to remove the slot by calling "remove". Otherwise you will be leaking memory
23    pub fn push(&'a self, value: T) -> Slot<'a, T> {
24        let current = self.next.get();
25
26        match current {
27            None => Slot(self.bump.alloc(SlotInner {
28                value: ManuallyDrop::new(UnsafeCell::new(value)),
29            })),
30            Some(mut current) => {
31                let available = unsafe { current.as_mut() };
32                unsafe {
33                    self.next.set(available.next);
34                }
35
36                available.value = ManuallyDrop::new(UnsafeCell::new(value));
37                Slot(available)
38            }
39        }
40    }
41
42    /// Acquire the internal bump allocator
43    pub fn bump(&self) -> &Bump {
44        &self.bump
45    }
46
47    pub fn remove(&'a self, slot: Slot<'a, T>) {
48        // Drop the value
49        unsafe { ManuallyDrop::drop(&mut slot.0.value) };
50
51        // Assign the next item in the linked list
52        // point this slot to the head, and then the bumpslab head to the new slot
53        slot.0.next = self.next.get();
54        self.next.set(Some(slot.0.into()));
55    }
56}
57
58/// A keyed container for the BumpSlab
59pub struct Slot<'a, T>(&'a mut SlotInner<T>);
60
61/// The inner is a union between the value and the next item in the linked list
62///
63/// This forms a intruisive linked list which let us chase down free spots as they become available
64union SlotInner<T> {
65    value: ManuallyDrop<UnsafeCell<T>>,
66    next: Option<NonNull<SlotInner<T>>>,
67}
68
69impl<T> Slot<'_, T> {
70    pub fn ptr(&self) -> *const T {
71        unsafe { self.0.value.get() }
72    }
73
74    pub fn ptr_mut(&self) -> *mut T {
75        unsafe { self.0.value.get() }
76    }
77}
78
79impl<T> std::ops::Deref for SlotInner<T> {
80    type Target = T;
81
82    fn deref(&self) -> &Self::Target {
83        unsafe { &*self.value.get() }
84    }
85}
86
87impl<T> std::ops::DerefMut for SlotInner<T> {
88    fn deref_mut(&mut self) -> &mut Self::Target {
89        unsafe { &mut *self.value.get_mut() }
90    }
91}
bumpslab/lib.rs

bumpslab/
lib.rs
