slot_arena/
lib.rs

1#![doc = include_str!("../README.md")]
2
3mod r#ref;
4
5use std::fmt::Debug;
6
7pub use r#ref::*;
8
9/// A block of memory accessed using 32-bit [Ref]s rather than 64-bit memory addresses.
10#[derive(Clone, Default, PartialEq, Eq, PartialOrd, Ord)]
11pub struct SlotArena<T> {
12    raw: Vec<T>,
13    free: Vec<Ref<T>>,
14}
15
16impl<T> SlotArena<T> {
17    /// Creates an empty [SlotArena].  Does not pre-allocate any memory.
18    #[inline]
19    pub const fn new() -> Self {
20        Self {
21            raw: Vec::new(),
22            free: Vec::new(),
23        }
24    }
25
26    /// Creates an empty [SlotArena], pre-allocated for the provided capacity.
27    #[inline]
28    pub fn with_capacity(capacity: u32) -> Self {
29        Self {
30            raw: Vec::with_capacity(capacity as usize),
31            free: Vec::new(),
32        }
33    }
34
35    /// Frees the provided value.  A value should not be used once it is freed, as it may be
36    /// replaced by another value.
37    #[inline]
38    pub fn free(&mut self, value: Ref<T>) {
39        self.free.push(value);
40    }
41
42    /// Inserts a value into the [SlotArena], returning a [Ref] to it.
43    ///
44    /// # Panics
45    /// Panics if the number of items in this [SlotArena] exceeds `u32::MAX`.
46    pub fn insert(&mut self, value: T) -> Ref<T> {
47        match self.free.pop() {
48            Some(idx) => {
49                self.raw[idx.to_raw() as usize] = value;
50                idx
51            }
52            None => {
53                let idx = Ref::from_raw(self.raw.len() as u32);
54                self.raw.push(value);
55                idx
56            }
57        }
58    }
59
60    /// Attempts to insert a value into the [SlotArena], returning [`None`] if it is full.
61    pub fn try_insert(&mut self, value: T) -> Option<Ref<T>> {
62        match self.free.pop() {
63            Some(idx) => {
64                self.raw[idx.to_raw() as usize] = value;
65                Some(idx)
66            }
67            None => {
68                if self.raw.len() == u32::MAX as usize {
69                    return None;
70                }
71
72                let idx = Ref::from_raw(self.raw.len() as u32);
73                self.raw.push(value);
74                Some(idx)
75            }
76        }
77    }
78
79    /// Returns `true` if the provided reference is valid (if the reference is in the bounds of the
80    /// memory block AND the reference is not free).
81    #[inline]
82    pub fn is_valid(&self, value: Ref<T>) -> bool {
83        !self.free.contains(&value) && (value.to_raw() as usize) < self.raw.len()
84    }
85
86    /// Returns a non-opaque reference to the provided value.
87    ///
88    /// # Panics
89    /// Panics if the provided reference is invalid.
90    #[inline]
91    pub fn get(&self, value: Ref<T>) -> &T {
92        debug_assert!(self.is_valid(value));
93        &self.raw[value.to_raw() as usize]
94    }
95
96    /// Attempts to get the value of the provided reference, returns [`None`] if the reference was
97    /// invalid.
98    pub fn try_get(&self, value: Ref<T>) -> Option<&T> {
99        if self.is_valid(value) {
100            Some(&self.raw[value.to_raw() as usize])
101        } else {
102            None
103        }
104    }
105
106    /// Returns a non-opaque reference to the provided value.
107    ///
108    /// # Panics
109    /// Panics if the provided reference is invalid.
110    #[inline]
111    pub fn get_mut(&mut self, value: Ref<T>) -> &mut T {
112        debug_assert!(self.is_valid(value));
113        &mut self.raw[value.to_raw() as usize]
114    }
115
116    /// Attempts to get the value of the provided reference, returns [`None`] if the reference was
117    /// invalid.
118    pub fn try_get_mut(&mut self, value: Ref<T>) -> Option<&mut T> {
119        if self.is_valid(value) {
120            Some(&mut self.raw[value.to_raw() as usize])
121        } else {
122            None
123        }
124    }
125
126    /// Returns an iterator through the alive items in the [SlotArena].
127    pub fn iter(&self) -> impl Iterator<Item = (Ref<T>, &T)> {
128        self.raw
129            .iter()
130            .enumerate()
131            .map(|(idx, item)| (Ref::from_raw(idx as u32), item))
132            .filter(|(idx, _)| !self.free.contains(&idx))
133    }
134
135    /// Returns an iterator through the alive items in the [SlotArena].
136    pub fn iter_mut(&mut self) -> impl Iterator<Item = (Ref<T>, &mut T)> {
137        self.raw
138            .iter_mut()
139            .enumerate()
140            .map(|(idx, item)| (Ref::from_raw(idx as u32), item))
141            .filter(|(idx, _)| !self.free.contains(&idx))
142    }
143}
144
145impl<T: Debug> Debug for SlotArena<T> {
146    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
147        f.debug_map().entries(self.iter()).finish()
148    }
149}
slot_arena/lib.rs

slot_arena/
lib.rs
