incular_core/
arena.rs

1//! Safe generational storage used by retained framework trees.
2
3use std::fmt;
4
5/// Stable slot identity. A removed slot increments its generation before reuse.
6#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
7pub struct ArenaId {
8    index: u32,
9    generation: u32,
10}
11
12impl ArenaId {
13    #[must_use]
14    pub const fn from_parts(index: u32, generation: u32) -> Self {
15        Self { index, generation }
16    }
17
18    #[must_use]
19    pub const fn index(self) -> u32 {
20        self.index
21    }
22
23    /// Slot generation, bumped on removal so reused slots are distinguishable.
24    #[must_use]
25    pub const fn generation(self) -> u32 {
26        self.generation
27    }
28}
29
30impl fmt::Debug for ArenaId {
31    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
32        write!(f, "ArenaId({}, {})", self.index, self.generation)
33    }
34}
35
36struct Slot<T> {
37    generation: u32,
38    value: Option<T>,
39}
40
41/// Compact safe arena used by persistent framework trees. It never exposes
42/// references across mutations, so tree algorithms can remain ordinary
43/// `&mut self` code.
44pub struct Arena<T> {
45    slots: Vec<Slot<T>>,
46    free: Vec<u32>,
47    len: usize,
48}
49
50impl<T> Default for Arena<T> {
51    fn default() -> Self {
52        Self::new()
53    }
54}
55
56impl<T> Arena<T> {
57    #[must_use]
58    pub const fn new() -> Self {
59        Self {
60            slots: Vec::new(),
61            free: Vec::new(),
62            len: 0,
63        }
64    }
65
66    pub fn insert(&mut self, value: T) -> ArenaId {
67        if let Some(index) = self.free.pop() {
68            let slot = &mut self.slots[index as usize];
69            debug_assert!(slot.value.is_none());
70            slot.value = Some(value);
71            self.len += 1;
72            ArenaId::from_parts(index, slot.generation)
73        } else {
74            let index = u32::try_from(self.slots.len()).expect("arena identity space exhausted");
75            if self.slots.len() == self.slots.capacity() {
76                // Grow by half instead of doubling. Retained trees settle at
77                // arbitrary sizes and their slots are large, so doubling can
78                // leave nearly half of a big allocation unused; 1.5x growth
79                // keeps inserts amortized O(1) with much less slack.
80                self.slots.reserve_exact((self.slots.len() / 2).max(8));
81            }
82            self.slots.push(Slot {
83                generation: 0,
84                value: Some(value),
85            });
86            self.len += 1;
87            ArenaId::from_parts(index, 0)
88        }
89    }
90
91    #[must_use]
92    pub fn get(&self, id: ArenaId) -> Option<&T> {
93        let slot = self.slots.get(id.index as usize)?;
94        (slot.generation == id.generation)
95            .then_some(slot.value.as_ref())
96            .flatten()
97    }
98
99    pub fn get_mut(&mut self, id: ArenaId) -> Option<&mut T> {
100        let slot = self.slots.get_mut(id.index as usize)?;
101        (slot.generation == id.generation)
102            .then_some(slot.value.as_mut())
103            .flatten()
104    }
105
106    pub fn remove(&mut self, id: ArenaId) -> Option<T> {
107        let slot = self.slots.get_mut(id.index as usize)?;
108        if slot.generation != id.generation {
109            return None;
110        }
111        let value = slot.value.take()?;
112        if let Some(next_generation) = slot.generation.checked_add(1) {
113            slot.generation = next_generation;
114            self.free.push(id.index);
115        }
116        self.len -= 1;
117        Some(value)
118    }
119
120    #[must_use]
121    pub fn contains(&self, id: ArenaId) -> bool {
122        self.get(id).is_some()
123    }
124
125    #[must_use]
126    pub const fn len(&self) -> usize {
127        self.len
128    }
129
130    #[must_use]
131    pub const fn is_empty(&self) -> bool {
132        self.len == 0
133    }
134
135    pub fn iter(&self) -> impl Iterator<Item = (ArenaId, &T)> {
136        self.slots.iter().enumerate().filter_map(|(index, slot)| {
137            slot.value.as_ref().map(|value| {
138                (
139                    ArenaId::from_parts(
140                        u32::try_from(index).expect("arena index was validated on insertion"),
141                        slot.generation,
142                    ),
143                    value,
144                )
145            })
146        })
147    }
148
149    pub fn iter_mut(&mut self) -> impl Iterator<Item = (ArenaId, &mut T)> {
150        self.slots
151            .iter_mut()
152            .enumerate()
153            .filter_map(|(index, slot)| {
154                let generation = slot.generation;
155                slot.value.as_mut().map(|value| {
156                    (
157                        ArenaId::from_parts(
158                            u32::try_from(index).expect("arena index was validated on insertion"),
159                            generation,
160                        ),
161                        value,
162                    )
163                })
164            })
165    }
166}
incular_core/arena.rs

incular_core/
arena.rs
