wasmi_arena/
lib.rs

1//! Fast arena allocators for different usage purposes.
2//!
3//! They cannot deallocate single allocated entities for extra efficiency.
4//! These allocators mainly serve as the backbone for an efficient Wasm store
5//! implementation.
6
7#![no_std]
8#![warn(
9    clippy::cast_lossless,
10    clippy::missing_errors_doc,
11    clippy::used_underscore_binding,
12    clippy::redundant_closure_for_method_calls,
13    clippy::type_repetition_in_bounds,
14    clippy::inconsistent_struct_constructor,
15    clippy::default_trait_access,
16    clippy::map_unwrap_or,
17    clippy::items_after_statements
18)]
19
20#[cfg(not(feature = "std"))]
21extern crate alloc as std;
22
23#[cfg(feature = "std")]
24extern crate std;
25
26mod component_vec;
27mod dedup;
28mod guarded;
29
30#[cfg(test)]
31mod tests;
32
33pub use self::{component_vec::ComponentVec, dedup::DedupArena, guarded::GuardedEntity};
34use core::{
35    iter::Enumerate,
36    marker::PhantomData,
37    ops::{Index, IndexMut},
38    slice,
39};
40use std::vec::Vec;
41
42/// Types that can be used as indices for arenas.
43pub trait ArenaIndex: Copy {
44    /// Converts the [`ArenaIndex`] into the underlying `usize` value.
45    fn into_usize(self) -> usize;
46    /// Converts the `usize` value into the associated [`ArenaIndex`].
47    fn from_usize(value: usize) -> Self;
48}
49
50/// An arena allocator with a given index and entity type.
51///
52/// For performance reasons the arena cannot deallocate single entities.
53#[derive(Debug)]
54pub struct Arena<Idx, T> {
55    entities: Vec<T>,
56    marker: PhantomData<Idx>,
57}
58
59/// `Arena` does not store `Idx` therefore it is `Send` without its bound.
60unsafe impl<Idx, T> Send for Arena<Idx, T> where T: Send {}
61
62/// `Arena` does not store `Idx` therefore it is `Sync` without its bound.
63unsafe impl<Idx, T> Sync for Arena<Idx, T> where T: Send {}
64
65impl<Idx, T> Default for Arena<Idx, T> {
66    fn default() -> Self {
67        Self::new()
68    }
69}
70
71impl<Idx, T> PartialEq for Arena<Idx, T>
72where
73    T: PartialEq,
74{
75    fn eq(&self, other: &Self) -> bool {
76        self.entities.eq(&other.entities)
77    }
78}
79
80impl<Idx, T> Eq for Arena<Idx, T> where T: Eq {}
81
82impl<Idx, T> Arena<Idx, T> {
83    /// Creates a new empty entity arena.
84    pub fn new() -> Self {
85        Self {
86            entities: Vec::new(),
87            marker: PhantomData,
88        }
89    }
90
91    /// Returns the allocated number of entities.
92    #[inline]
93    pub fn len(&self) -> usize {
94        self.entities.len()
95    }
96
97    /// Returns `true` if the arena has not yet allocated entities.
98    #[inline]
99    pub fn is_empty(&self) -> bool {
100        self.len() == 0
101    }
102
103    /// Clears all entities from the arena.
104    pub fn clear(&mut self) {
105        self.entities.clear();
106    }
107
108    /// Returns an iterator over the shared reference of the arena entities.
109    pub fn iter(&self) -> Iter<Idx, T> {
110        Iter {
111            iter: self.entities.iter().enumerate(),
112            marker: PhantomData,
113        }
114    }
115
116    /// Returns an iterator over the exclusive reference of the arena entities.
117    pub fn iter_mut(&mut self) -> IterMut<Idx, T> {
118        IterMut {
119            iter: self.entities.iter_mut().enumerate(),
120            marker: PhantomData,
121        }
122    }
123}
124
125impl<Idx, T> Arena<Idx, T>
126where
127    Idx: ArenaIndex,
128{
129    /// Returns the next entity index.
130    fn next_index(&self) -> Idx {
131        Idx::from_usize(self.entities.len())
132    }
133
134    /// Allocates a new entity and returns its index.
135    #[inline]
136    pub fn alloc(&mut self, entity: T) -> Idx {
137        let index = self.next_index();
138        self.entities.push(entity);
139        index
140    }
141
142    /// Returns a shared reference to the entity at the given index if any.
143    #[inline]
144    pub fn get(&self, index: Idx) -> Option<&T> {
145        self.entities.get(index.into_usize())
146    }
147
148    /// Returns an exclusive reference to the entity at the given index if any.
149    #[inline]
150    pub fn get_mut(&mut self, index: Idx) -> Option<&mut T> {
151        self.entities.get_mut(index.into_usize())
152    }
153
154    /// Returns an exclusive reference to the pair of entities at the given indices if any.
155    ///
156    /// Returns `None` if `fst` and `snd` refer to the same entity.
157    /// Returns `None` if either `fst` or `snd` is invalid for this [`Arena`].
158    #[inline]
159    pub fn get_pair_mut(&mut self, fst: Idx, snd: Idx) -> Option<(&mut T, &mut T)> {
160        let fst_index = fst.into_usize();
161        let snd_index = snd.into_usize();
162        if fst_index == snd_index {
163            return None;
164        }
165        if fst_index > snd_index {
166            let (fst, snd) = self.get_pair_mut(snd, fst)?;
167            return Some((snd, fst));
168        }
169        // At this point we know that fst_index < snd_index.
170        let (fst_set, snd_set) = self.entities.split_at_mut(snd_index);
171        let fst = fst_set.get_mut(fst_index)?;
172        let snd = snd_set.get_mut(0)?;
173        Some((fst, snd))
174    }
175}
176
177impl<Idx, T> FromIterator<T> for Arena<Idx, T> {
178    fn from_iter<I>(iter: I) -> Self
179    where
180        I: IntoIterator<Item = T>,
181    {
182        Self {
183            entities: Vec::from_iter(iter),
184            marker: PhantomData,
185        }
186    }
187}
188
189impl<'a, Idx, T> IntoIterator for &'a Arena<Idx, T>
190where
191    Idx: ArenaIndex,
192{
193    type Item = (Idx, &'a T);
194    type IntoIter = Iter<'a, Idx, T>;
195
196    fn into_iter(self) -> Self::IntoIter {
197        self.iter()
198    }
199}
200
201impl<'a, Idx, T> IntoIterator for &'a mut Arena<Idx, T>
202where
203    Idx: ArenaIndex,
204{
205    type Item = (Idx, &'a mut T);
206    type IntoIter = IterMut<'a, Idx, T>;
207
208    fn into_iter(self) -> Self::IntoIter {
209        self.iter_mut()
210    }
211}
212
213/// An iterator over shared references of arena entities and their indices.
214#[derive(Debug)]
215pub struct Iter<'a, Idx, T> {
216    iter: Enumerate<slice::Iter<'a, T>>,
217    marker: PhantomData<fn() -> Idx>,
218}
219
220impl<'a, Idx, T> Iterator for Iter<'a, Idx, T>
221where
222    Idx: ArenaIndex,
223{
224    type Item = (Idx, &'a T);
225
226    #[inline]
227    fn next(&mut self) -> Option<Self::Item> {
228        self.iter
229            .next()
230            .map(|(idx, entity)| (Idx::from_usize(idx), entity))
231    }
232
233    #[inline]
234    fn size_hint(&self) -> (usize, Option<usize>) {
235        self.iter.size_hint()
236    }
237}
238
239impl<'a, Idx, T> DoubleEndedIterator for Iter<'a, Idx, T>
240where
241    Idx: ArenaIndex,
242{
243    #[inline]
244    fn next_back(&mut self) -> Option<Self::Item> {
245        self.iter
246            .next()
247            .map(|(idx, entity)| (Idx::from_usize(idx), entity))
248    }
249}
250
251impl<'a, Idx, T> ExactSizeIterator for Iter<'a, Idx, T>
252where
253    Idx: ArenaIndex,
254{
255    fn len(&self) -> usize {
256        self.iter.len()
257    }
258}
259
260/// An iterator over exclusive references of arena entities and their indices.
261#[derive(Debug)]
262pub struct IterMut<'a, Idx, T> {
263    iter: Enumerate<slice::IterMut<'a, T>>,
264    marker: PhantomData<fn() -> Idx>,
265}
266
267impl<'a, Idx, T> Iterator for IterMut<'a, Idx, T>
268where
269    Idx: ArenaIndex,
270{
271    type Item = (Idx, &'a mut T);
272
273    #[inline]
274    fn next(&mut self) -> Option<Self::Item> {
275        self.iter
276            .next()
277            .map(|(idx, entity)| (Idx::from_usize(idx), entity))
278    }
279
280    #[inline]
281    fn size_hint(&self) -> (usize, Option<usize>) {
282        self.iter.size_hint()
283    }
284}
285
286impl<'a, Idx, T> DoubleEndedIterator for IterMut<'a, Idx, T>
287where
288    Idx: ArenaIndex,
289{
290    #[inline]
291    fn next_back(&mut self) -> Option<Self::Item> {
292        self.iter
293            .next()
294            .map(|(idx, entity)| (Idx::from_usize(idx), entity))
295    }
296}
297
298impl<'a, Idx, T> ExactSizeIterator for IterMut<'a, Idx, T>
299where
300    Idx: ArenaIndex,
301{
302    #[inline]
303    fn len(&self) -> usize {
304        self.iter.len()
305    }
306}
307
308impl<Idx, T> Arena<Idx, T> {
309    /// Panics with an index out of bounds message.
310    fn index_out_of_bounds(len: usize, index: usize) -> ! {
311        panic!("index out of bounds: the len is {len} but the index is {index}")
312    }
313}
314
315impl<Idx, T> Index<Idx> for Arena<Idx, T>
316where
317    Idx: ArenaIndex,
318{
319    type Output = T;
320
321    #[inline]
322    fn index(&self, index: Idx) -> &Self::Output {
323        self.get(index)
324            .unwrap_or_else(|| Self::index_out_of_bounds(self.len(), index.into_usize()))
325    }
326}
327
328impl<Idx, T> IndexMut<Idx> for Arena<Idx, T>
329where
330    Idx: ArenaIndex,
331{
332    #[inline]
333    fn index_mut(&mut self, index: Idx) -> &mut Self::Output {
334        let len = self.len();
335        self.get_mut(index)
336            .unwrap_or_else(|| Self::index_out_of_bounds(len, index.into_usize()))
337    }
338}
wasmi_arena/lib.rs

wasmi_arena/
lib.rs
