sparse_slot/
lib.rs

1/*
2 * Copyright (c) Peter Bjorklund. All rights reserved. https://github.com/piot/sparse-slot
3 * Licensed under the MIT License. See LICENSE in the project root for license information.
4 */
5pub mod prelude;
6
7use std::fmt::{Debug, Display, Formatter};
8
9#[derive(Debug, PartialEq, Eq)]
10pub enum SparseSlotError {
11    IndexOutOfBounds(usize),
12    Occupied(usize),
13    //    GenerationMismatch(u8),
14    IllegalZeroGeneration,
15}
16
17/// A fixed-size sparse collection that maintains optional values at specified indices.
18///
19/// `SparseSlot<T>` provides a fixed-capacity container where each slot can either be empty (`None`)
20/// or contain a value (`Some(T)`). Once initialized, the capacity cannot be changed. Values can only
21/// be set once in empty slots - attempting to overwrite an existing value will be ignored.
22///
23/// # Type Parameters
24///
25/// * `T` - The type of elements stored in the collection
26///
27/// # Characteristics
28///
29/// * Fixed size - Capacity is determined at creation
30/// * Sparse storage - Slots can be empty or filled
31/// * One-time assignment - Values can only be set once per slot
32/// * Index-based access - Direct access to elements via indices
33/// * Iterator support - Both immutable and mutable iteration over non-empty slots
34///
35#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
36
37pub struct Id {
38    pub index: usize,
39    pub generation: u8,
40}
41
42impl Display for Id {
43    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
44        write!(f, "{:0>4}:{:04X}", self.index, self.generation)
45    }
46}
47
48impl Id {
49    #[must_use]
50    pub fn new(index: usize, generation: u8) -> Self {
51        Self { index, generation }
52    }
53
54    #[must_use]
55    pub fn index(&self) -> usize {
56        self.index
57    }
58
59    #[must_use]
60    pub fn generation(&self) -> u8 {
61        self.generation
62    }
63
64    #[must_use]
65    pub fn next(&self) -> Self {
66        Self {
67            index: self.index,
68            generation: self.generation.wrapping_add(1),
69        }
70    }
71}
72
73impl From<((usize, u8),)> for Id {
74    fn from(((index, generation),): ((usize, u8),)) -> Self {
75        Self { index, generation }
76    }
77}
78
79pub struct Iter<'a, T> {
80    items: &'a [Entry<T>],
81    next_index: Option<usize>,
82}
83
84impl<'a, T> Iterator for Iter<'a, T> {
85    type Item = (Id, &'a T);
86
87    fn next(&mut self) -> Option<Self::Item> {
88        let current_index = self.next_index?;
89        let entry = &self.items[current_index];
90
91        self.next_index = entry.next_index;
92
93        entry
94            .item
95            .as_ref()
96            .map(|item| (Id::new(current_index, entry.generation), item))
97    }
98}
99
100pub struct IterMut<'a, T> {
101    items: &'a mut [Entry<T>],
102    next_index: Option<usize>,
103}
104
105impl<'a, T> Iterator for IterMut<'a, T> {
106    type Item = (Id, &'a mut T);
107
108    fn next(&mut self) -> Option<Self::Item> {
109        let current_index = self.next_index?;
110
111        let entry = unsafe { &mut *(self.items.get_unchecked_mut(current_index) as *mut Entry<T>) };
112
113        let next = entry.next_index;
114        self.next_index = next;
115
116        entry
117            .item
118            .as_mut()
119            .map(|item| (Id::new(current_index, entry.generation), item))
120    }
121}
122
123pub struct IntoIter<T> {
124    items: Vec<Entry<T>>,
125    next_index: Option<usize>,
126}
127
128impl<T> Iterator for IntoIter<T> {
129    type Item = (Id, T);
130
131    fn next(&mut self) -> Option<Self::Item> {
132        let current_index = self.next_index?;
133        let entry = &mut self.items[current_index];
134
135        // Store next index before taking the item
136        let next = entry.next_index;
137        self.next_index = next;
138
139        entry
140            .item
141            .take()
142            .map(|item| (Id::new(current_index, entry.generation), item))
143    }
144}
145
146impl<T> FromIterator<(Id, T)> for SparseSlot<T> {
147    fn from_iter<I: IntoIterator<Item = (Id, T)>>(iter: I) -> Self {
148        let iter = iter.into_iter();
149        let (lower, _) = iter.size_hint();
150        let mut slot = Self::new(lower.max(16)); // Default minimum capacity
151
152        for (id, value) in iter {
153            let _ = slot.try_set(id, value);
154        }
155        slot
156    }
157}
158
159impl<T> IntoIterator for SparseSlot<T> {
160    type Item = (Id, T);
161    type IntoIter = IntoIter<T>;
162
163    fn into_iter(self) -> Self::IntoIter {
164        IntoIter {
165            items: self.items,
166            next_index: self.first_occupied,
167        }
168    }
169}
170
171pub struct Keys<'a, T> {
172    iter: Iter<'a, T>,
173}
174
175pub struct Values<'a, T> {
176    iter: Iter<'a, T>,
177}
178
179pub struct ValuesMut<'a, T> {
180    iter: IterMut<'a, T>,
181}
182
183impl<'a, T> Iterator for Keys<'a, T> {
184    type Item = Id;
185
186    fn next(&mut self) -> Option<Self::Item> {
187        self.iter.next().map(|(id, _)| id)
188    }
189}
190
191impl<'a, T> Iterator for Values<'a, T> {
192    type Item = &'a T;
193
194    fn next(&mut self) -> Option<Self::Item> {
195        self.iter.next().map(|(_, value)| value)
196    }
197}
198
199impl<'a, T> Iterator for ValuesMut<'a, T> {
200    type Item = &'a mut T;
201
202    fn next(&mut self) -> Option<Self::Item> {
203        self.iter.next().map(|(_, value)| value)
204    }
205}
206
207#[derive(PartialEq, Eq, Debug)]
208struct Entry<T> {
209    pub generation: u8,
210    pub item: Option<T>,
211    pub next_index: Option<usize>,
212    pub previous_index: Option<usize>,
213}
214
215impl<T> Default for Entry<T> {
216    fn default() -> Self {
217        Self {
218            generation: 0,
219            item: None,
220            next_index: None,
221            previous_index: None,
222        }
223    }
224}
225
226#[derive(Debug, Eq, PartialEq)]
227pub struct SparseSlot<T> {
228    items: Vec<Entry<T>>,
229    first_occupied: Option<usize>,
230}
231
232impl<T> SparseSlot<T> {
233    /// Creates a new `SparseSlot` with the specified capacity.
234    ///
235    /// # Arguments
236    ///
237    /// * `capacity` - The fixed size of the collection
238    ///
239    /// # Returns
240    ///
241    /// A new `SparseSlot` instance with all slots initialized to `None`
242    ///
243    /// # Examples
244    ///
245    /// ```rust
246    /// use sparse_slot::SparseSlot;
247    /// let slot: SparseSlot<i32> = SparseSlot::new(5);
248    /// assert_eq!(slot.len(), 0);
249    /// assert_eq!(slot.capacity(), 5);
250    /// ```
251    #[must_use]
252    pub fn new(capacity: usize) -> Self {
253        let mut items = Vec::with_capacity(capacity);
254        items.extend((0..capacity).map(|_| Entry::default()));
255        Self {
256            items,
257            first_occupied: None,
258        }
259    }
260
261    // Mutation ------------------------------------------------------------------------------------
262
263    pub fn try_set(&mut self, id: Id, item: T) -> Result<(), SparseSlotError> {
264        if id.index >= self.items.len() {
265            return Err(SparseSlotError::IndexOutOfBounds(id.index));
266        }
267
268        // First, validate the entry
269        {
270            let entry = &self.items[id.index];
271            if entry.item.is_some() {
272                return Err(SparseSlotError::Occupied(id.index));
273            }
274            if entry.generation != id.generation {
275                // return Err(SparseSlotError::GenerationMismatch(entry.generation));
276            }
277        }
278
279        let mut prev_index = None;
280        let mut next_index = self.first_occupied;
281
282        while let Some(current) = next_index {
283            if current > id.index {
284                break;
285            }
286            prev_index = Some(current);
287            next_index = self.items[current].next_index;
288        }
289
290        {
291            let entry = &mut self.items[id.index];
292            entry.item = Some(item);
293            entry.generation = id.generation;
294            entry.previous_index = prev_index;
295            entry.next_index = next_index;
296        }
297
298        if let Some(prev_idx) = prev_index {
299            self.items[prev_idx].next_index = Some(id.index);
300        } else {
301            self.first_occupied = Some(id.index);
302        }
303
304        if let Some(next_idx) = next_index {
305            self.items[next_idx].previous_index = Some(id.index);
306        }
307
308        Ok(())
309    }
310
311    pub fn remove(&mut self, id: Id) -> Option<T> {
312        let (prev_index, next_index) = {
313            let entry = &self.items[id.index];
314            if entry.generation != id.generation || entry.item.is_none() {
315                return None;
316            }
317            (entry.previous_index, entry.next_index)
318        };
319
320        if Some(id.index) == self.first_occupied {
321            self.first_occupied = next_index;
322        }
323
324        if let Some(prev_idx) = prev_index {
325            self.items[prev_idx].next_index = next_index;
326        }
327        if let Some(next_idx) = next_index {
328            self.items[next_idx].previous_index = prev_index;
329        }
330
331        let entry = &mut self.items[id.index];
332        let item = entry.item.take();
333        entry.generation = entry.generation.wrapping_add(1);
334        entry.next_index = None;
335        entry.previous_index = None;
336
337        item
338    }
339
340    pub fn clear(&mut self) {
341        for entry in &mut self.items {
342            if entry.item.take().is_some() {
343                entry.generation = entry.generation.wrapping_add(1);
344                entry.next_index = None;
345                entry.previous_index = None;
346            }
347        }
348        self.first_occupied = None;
349    }
350
351    // Mutation getters ------------------------------------------------------------------------------------
352
353    pub fn values_mut(&mut self) -> ValuesMut<'_, T> {
354        ValuesMut {
355            iter: self.iter_mut(),
356        }
357    }
358
359    #[must_use]
360    #[inline(always)]
361    pub fn get_mut(&mut self, id: Id) -> Option<&mut T> {
362        let entry = self.items.get_mut(id.index)?;
363        if entry.generation != id.generation {
364            return None;
365        }
366        entry.item.as_mut()
367    }
368
369    // Iterators ------------------------------------------------------------------------------------
370    pub fn iter(&self) -> Iter<'_, T> {
371        Iter {
372            items: &self.items,
373            next_index: self.first_occupied,
374        }
375    }
376
377    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
378        let first = self.first_occupied;
379        IterMut {
380            items: &mut self.items,
381            next_index: first,
382        }
383    }
384
385    pub fn keys(&self) -> Keys<'_, T> {
386        Keys { iter: self.iter() }
387    }
388
389    pub fn values(&self) -> Values<'_, T> {
390        Values { iter: self.iter() }
391    }
392
393    pub fn drain(&mut self) -> impl Iterator<Item = (Id, T)> + '_ {
394        let mut index = self.first_occupied;
395        std::iter::from_fn(move || {
396            while let Some(current_index) = index {
397                let entry = &mut self.items[current_index];
398                index = entry.next_index;
399
400                if let Some(item) = entry.item.take() {
401                    entry.generation = entry.generation.wrapping_add(1);
402                    return Some((Id::new(current_index, entry.generation - 1), item));
403                }
404            }
405            None
406        })
407    }
408
409    // Query ------------------------------------------------------------------------------------
410
411    pub fn capacity(&self) -> usize {
412        self.items.len()
413    }
414
415    #[must_use]
416    pub fn len(&self) -> usize {
417        self.items.iter().filter(|x| x.item.is_some()).count()
418    }
419
420    #[must_use]
421    pub fn is_empty(&self) -> bool {
422        self.len() == 0
423    }
424
425    #[must_use]
426    pub fn first_id(&self) -> Option<Id> {
427        self.first_occupied.map(|index| {
428            let entry = &self.items[index];
429            Id::new(index, entry.generation)
430        })
431    }
432
433    // TODO: This is not efficient, should have a self.last_occupied in the future
434    pub fn last_id(&self) -> Option<Id> {
435        self.items
436            .iter()
437            .enumerate()
438            .rev()
439            .find(|(_, entry)| entry.item.is_some())
440            .map(|(index, entry)| Id::new(index, entry.generation))
441    }
442
443    // Getters ------------------------------------------------------------------------------------
444    #[must_use]
445    #[inline(always)]
446    pub fn get(&self, id: Id) -> Option<&T> {
447        let entry = &self.items[id.index];
448        if entry.generation != id.generation {
449            return None;
450        }
451        entry.item.as_ref()
452    }
453}
sparse_slot/lib.rs

sparse_slot/
lib.rs
