fast_mesh_scene/
id.rs

1//! Generational ids and the slot map behind them.
2
3use fast_mesh_store::StoreError;
4
5use crate::{Result, SceneError};
6
7/// A handle to a mesh in a [`Scene`](crate::Scene).
8///
9/// Ids are generational: once a mesh is removed its id never matches again,
10/// even when the slot is reused. Ids order by `(index, generation)`.
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
12pub struct MeshId {
13    index: u32,
14    generation: u32,
15}
16
17impl MeshId {
18    /// The slot index, for passing the id across an FFI boundary together
19    /// with [`MeshId::generation`]. Turn the pair back into an id with
20    /// [`Scene::mesh_id`](crate::Scene::mesh_id).
21    pub fn index(self) -> u32 {
22        self.index
23    }
24
25    /// The slot generation; see [`MeshId::index`].
26    pub fn generation(self) -> u32 {
27        self.generation
28    }
29}
30
31struct Slot<T> {
32    generation: u32,
33    value: Option<T>,
34}
35
36/// Values addressed by [`MeshId`], iterated in index order.
37pub(crate) struct SlotMap<T> {
38    slots: Vec<Slot<T>>,
39    /// Indices of empty slots that can be reused.
40    free: Vec<u32>,
41}
42
43fn oom() -> SceneError {
44    SceneError::Store(StoreError::OutOfMemory)
45}
46
47impl<T> SlotMap<T> {
48    pub(crate) fn new() -> Self {
49        SlotMap {
50            slots: Vec::new(),
51            free: Vec::new(),
52        }
53    }
54
55    /// Stores `value` and returns its id. Leaves the map unchanged on error.
56    pub(crate) fn insert(&mut self, value: T) -> Result<MeshId> {
57        if let Some(index) = self.free.pop() {
58            let slot = &mut self.slots[index as usize];
59            slot.value = Some(value);
60            return Ok(MeshId {
61                index,
62                generation: slot.generation,
63            });
64        }
65        let index = u32::try_from(self.slots.len()).map_err(|_| oom())?;
66        self.slots.try_reserve(1).map_err(|_| oom())?;
67        self.slots.push(Slot {
68            generation: 0,
69            value: Some(value),
70        });
71        Ok(MeshId {
72            index,
73            generation: 0,
74        })
75    }
76
77    /// Removes and returns the value; the id stops matching.
78    pub(crate) fn remove(&mut self, id: MeshId) -> Option<T> {
79        let slot = self.slots.get_mut(id.index as usize)?;
80        if slot.generation != id.generation || slot.value.is_none() {
81            return None;
82        }
83        let value = slot.value.take();
84        // A slot whose generation space is used up is retired, not reused. So
85        // is one whose free-list entry cannot be reserved (best effort).
86        if let Some(next) = slot.generation.checked_add(1) {
87            slot.generation = next;
88            if self.free.try_reserve(1).is_ok() {
89                self.free.push(id.index);
90            }
91        }
92        value
93    }
94
95    /// The id of the live value in slot `index` with this `generation`.
96    pub(crate) fn live_id(&self, index: u32, generation: u32) -> Option<MeshId> {
97        let id = MeshId { index, generation };
98        self.get(id).map(|_| id)
99    }
100
101    pub(crate) fn get(&self, id: MeshId) -> Option<&T> {
102        let slot = self.slots.get(id.index as usize)?;
103        if slot.generation == id.generation {
104            slot.value.as_ref()
105        } else {
106            None
107        }
108    }
109
110    pub(crate) fn get_mut(&mut self, id: MeshId) -> Option<&mut T> {
111        let slot = self.slots.get_mut(id.index as usize)?;
112        if slot.generation == id.generation {
113            slot.value.as_mut()
114        } else {
115            None
116        }
117    }
118
119    /// Live `(id, value)` pairs in index order.
120    pub(crate) fn iter(&self) -> impl Iterator<Item = (MeshId, &T)> {
121        self.slots.iter().enumerate().filter_map(|(i, s)| {
122            s.value.as_ref().map(|v| {
123                (
124                    MeshId {
125                        index: i as u32,
126                        generation: s.generation,
127                    },
128                    v,
129                )
130            })
131        })
132    }
133
134    /// Live `(id, value)` pairs in index order, mutably.
135    pub(crate) fn iter_mut(&mut self) -> impl Iterator<Item = (MeshId, &mut T)> {
136        self.slots.iter_mut().enumerate().filter_map(|(i, s)| {
137            let generation = s.generation;
138            s.value.as_mut().map(|v| {
139                (
140                    MeshId {
141                        index: i as u32,
142                        generation,
143                    },
144                    v,
145                )
146            })
147        })
148    }
149}
150
151#[cfg(test)]
152mod tests {
153    use super::*;
154
155    #[test]
156    fn reuse_bumps_generation() {
157        let mut m = SlotMap::new();
158        let a = m.insert("a").unwrap();
159        assert_eq!(m.remove(a), Some("a"));
160        assert_eq!(m.remove(a), None);
161        let b = m.insert("b").unwrap();
162        assert_eq!(a.index, b.index);
163        assert_ne!(a, b);
164        assert!(m.get(a).is_none());
165        assert_eq!(m.get(b), Some(&"b"));
166    }
167}
fast_mesh_scene/id.rs

fast_mesh_scene/
id.rs
