| //! A slotmap, a vector-like container with unique keys instead of indices. |
| //! |
| //! See the documentation of [`SlotMap`] for details. |
| //! |
| //! [`SlotMap`]: struct.SlotMap.html |
| use super::{ManagedSlice as Slice}; |
| |
| /// Provides links between slots and elements. |
| /// |
| /// The benefit of separating this struct from the elements is that it is unconditionally `Copy` |
| /// and `Default`. It also provides better locality for both the indices and the elements which |
| /// could help with iteration or very large structs. |
| #[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)] |
| pub struct Slot { |
| /// The id of this slot. |
| /// |
| /// If the given out index mismatches the `generation_id` then the element was removed already |
| /// and we can return `None` on lookup. |
| /// |
| /// If the slot is currently unused we will instead provide the index to the previous slot in |
| /// the slot-free-list. |
| generation_id: GenerationOrFreelink, |
| } |
| |
| /// Provides a slotmap based on external memory. |
| /// |
| /// A slotmap provides a `Vec`-like interface where each entry is associated with a stable |
| /// index-like key. Lookup with the key will detect if an entry has been removed but does not |
| /// require a lifetime relation. Compared to other slotmap implementations this does not internally |
| /// allocate any memory on its own but only relies on the [`Slice`] arguments in the constructor. |
| /// |
| /// [`Slice`]: ../enum.Slice.html |
| /// |
| /// ## Usage |
| /// |
| /// The important aspect is that the slotmap does not create the storage of its own elements, it |
| /// merely manages one given to it at construction time. |
| /// |
| /// ``` |
| /// # use managed::{ManagedSlice, SlotMap, SlotIndex}; |
| /// |
| /// let mut elements = [0usize; 1024]; |
| /// let mut slots = [SlotIndex::default(); 1024]; |
| /// |
| /// let mut map = SlotMap::new( |
| /// ManagedSlice::Borrowed(&mut elements[..]), |
| /// ManagedSlice::Borrowed(&mut slots[..])); |
| /// let index = map.insert(42).unwrap(); |
| /// assert_eq!(map.get(index).cloned(), Some(42)); |
| /// ``` |
| pub struct SlotMap<'a, T> { |
| /// The slice where elements are placed. |
| /// All of them are initialized at all times but not all are logically part of the map. |
| elements: Slice<'a, T>, |
| /// The logical list of used slots. |
| /// Note that a slot is never remove from this list but instead used to track the generation_id |
| /// and the link in the free list. |
| slots: Partial<'a, Slot>, |
| /// The source of generation ids. |
| /// Generation ids are a positive, non-zero value. |
| generation: Generation, |
| /// An index to the top element of the free list. |
| /// Refers to the one-past-the-end index of `slots` if there are no elements. |
| free_top: usize, |
| /// An abstraction around computing wrapped indices in the free list. |
| indices: IndexComputer, |
| } |
| |
| /// A backing slice tracking an index how far it is logically initialized. |
| struct Partial<'a, T> { |
| slice: Slice<'a, T>, |
| next_idx: usize, |
| } |
| |
| /// An index into a slotmap. |
| /// |
| /// The index remains valid until the entry is removed. If accessing the slotmap with the index |
| /// again after the entry was removed will fail, even if the index where the element was previously |
| /// stored has been reused for another element. |
| #[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)] |
| pub struct Key { |
| idx: usize, |
| generation: Generation, |
| } |
| |
| #[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)] |
| struct GenerationOrFreelink(isize); |
| |
| /// Newtype wrapper around the index of a free slot. |
| #[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)] |
| struct FreeIndex(usize); |
| |
| /// The generation counter. |
| /// |
| /// Has a strictly positive value. |
| #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] |
| struct Generation(isize); |
| |
| /// Offset of a freelist entry to the next entry. |
| /// |
| /// Has a negative or zero value. Represents the negative of the offset to the next element in the |
| /// free list, wrapping around at the capacity. |
| /// The base for the offset is the *next* element for two reasons: |
| /// * Offset of `0` points to the natural successor. |
| /// * Offset of `len` would point to the element itself and should not occur. |
| #[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)] |
| struct Offset(isize); |
| |
| /// Links FreeIndex and Offset. |
| struct IndexComputer(usize); |
| |
| impl<T> SlotMap<'_, T> { |
| /// Retrieve a value by index. |
| pub fn get(&self, index: Key) -> Option<&T> { |
| let slot_generation = self.slots |
| .get(index.idx)? |
| .generation_id |
| .generation().ok()?; |
| |
| if slot_generation != index.generation { |
| return None; |
| } |
| |
| self.elements.get(index.idx) |
| } |
| |
| /// Retrieve a mutable value by index. |
| pub fn get_mut(&mut self, index: Key) -> Option<&mut T> { |
| let slot_generation = self.slots |
| .get(index.idx)? |
| .generation_id |
| .generation().ok()?; |
| |
| if slot_generation != index.generation { |
| return None; |
| } |
| |
| self.elements.get_mut(index.idx) |
| } |
| |
| /// Reserve a new entry. |
| /// |
| /// In case of success, the returned key refers to the entry until it is removed. The entry |
| /// itself is not initialized with any particular value but instead retains the value it had in |
| /// the backing slice. It is only logically placed into the slot map. |
| pub fn reserve(&mut self) -> Option<(Key, &mut T)> { |
| let index = self.next_free_slot()?; |
| let slot = self.slots.get_mut(index.0).unwrap(); |
| let element = &mut self.elements[index.0]; |
| |
| let offset = slot.generation_id |
| .free_link() |
| .expect("Free link should be free"); |
| slot.generation_id = self.generation.into(); |
| let key = Key { |
| idx: index.0, |
| generation: self.generation, |
| }; |
| |
| self.free_top = self.indices.free_list_next(index, offset); |
| self.generation.advance(); |
| Some((key, element)) |
| } |
| |
| /// Try to insert a value into the map. |
| /// |
| /// This will fail if there is not enough space. Sugar wrapper around `reserve` for inserting |
| /// values. Note that on success, an old value stored in the backing slice will be overwritten. |
| /// Use `reserve` directly if it is vital that no old value is dropped. |
| pub fn insert(&mut self, value: T) -> Option<Key> { |
| // Insertion must work but we don't care about the value. |
| let (index, element) = self.reserve()?; |
| *element = value; |
| Some(index) |
| } |
| |
| /// Remove an element. |
| /// |
| /// If successful, return a mutable reference to the removed element so that the caller can |
| /// swap it with a logically empty value. Returns `None` if the provided index did not refer to |
| /// an element that could be freed. |
| pub fn remove(&mut self, index: Key) -> Option<&mut T> { |
| if self.get(index).is_none() { |
| return None |
| } |
| |
| // The slot can be freed. |
| let free = FreeIndex(index.idx); |
| let slot = self.slots.get_mut(index.idx).unwrap(); |
| assert!(slot.generation_id.generation().is_ok()); |
| |
| let offset = self.indices.free_list_offset(free, self.free_top); |
| slot.generation_id = offset.into(); |
| self.free_top = index.idx; |
| |
| Some(&mut self.elements[index.idx]) |
| } |
| |
| /// Get the next free slot. |
| fn next_free_slot(&mut self) -> Option<FreeIndex> { |
| // If free_top is one-past-the-end marker one of those is going to fail. Note that this |
| // also means extracting one of these statements out of the function may change the |
| // semantics if `elements.len() != slots.len()`. |
| |
| // Ensure the index refers to an element within the slice or try to allocate a new slot |
| // wherein we can fit the element. |
| let free = match self.slots.get_mut(self.free_top) { |
| // There is a free element in our free list. |
| Some(_) => { |
| // Ensure that there is also a real element there. |
| let _= self.elements.get_mut(self.free_top)?; |
| FreeIndex(self.free_top) |
| }, |
| // Need to try an get a new element from the slot slice. |
| None => { // Try to get the next one |
| // Will not actually wrap if pushing is successful. |
| let new_index = self.slots.len(); |
| // Ensure there is an element where we want to push to. |
| let _ = self.elements.get_mut(new_index)?; |
| |
| let free_slot = self.slots.try_reserve()?; |
| let free_index = FreeIndex(new_index); |
| // New top is the new one-past-the-end. |
| let new_top = new_index.checked_add(1).unwrap(); |
| |
| let offset = self.indices.free_list_offset(free_index, new_top); |
| free_slot.generation_id = offset.into(); |
| self.free_top = free_index.0; |
| |
| free_index |
| } |
| }; |
| |
| |
| // index refers to elements within the slices |
| Some(free) |
| } |
| } |
| |
| impl<'a, T> SlotMap<'a, T> { |
| /// Create a slot map. |
| /// |
| /// The capacity is the minimum of the capacity of the element and slot slices. |
| pub fn new(elements: Slice<'a, T>, slots: Slice<'a, Slot>) -> Self { |
| let capacity = elements.len().min(slots.len()); |
| SlotMap { |
| elements, |
| slots: Partial { |
| slice: slots, |
| next_idx: 0, |
| }, |
| generation: Generation::default(), |
| free_top: 0, |
| indices: IndexComputer::from_capacity(capacity), |
| } |
| } |
| } |
| |
| impl<'a, T> Partial<'a, T> { |
| fn get(&self, idx: usize) -> Option<&T> { |
| if idx >= self.next_idx { |
| None |
| } else { |
| Some(&self.slice[idx]) |
| } |
| } |
| |
| fn get_mut(&mut self, idx: usize) -> Option<&mut T> { |
| if idx >= self.next_idx { |
| None |
| } else { |
| Some(&mut self.slice[idx]) |
| } |
| } |
| |
| fn len(&self) -> usize { |
| self.next_idx |
| } |
| |
| fn try_reserve(&mut self) -> Option<&mut T> { |
| if self.next_idx == self.slice.len() { |
| None |
| } else { |
| let idx = self.next_idx; |
| self.next_idx += 1; |
| Some(&mut self.slice[idx]) |
| } |
| } |
| } |
| |
| impl GenerationOrFreelink { |
| pub(crate) fn free_link(self) -> Result<Offset, Generation> { |
| if self.0 > 0 { |
| Err(Generation(self.0)) |
| } else { |
| Ok(Offset(self.0)) |
| } |
| } |
| |
| pub(crate) fn generation(self) -> Result<Generation, Offset> { |
| match self.free_link() { |
| Ok(offset) => Err(offset), |
| Err(generation) => Ok(generation), |
| } |
| } |
| } |
| |
| impl IndexComputer { |
| pub(crate) fn from_capacity(capacity: usize) -> Self { |
| assert!(capacity < isize::max_value() as usize); |
| IndexComputer(capacity) |
| } |
| |
| /// Get the next free list entry. |
| /// This applies the offset to the base index, wrapping around if required. |
| /// |
| /// This is the reverse of `free_list_offset`. |
| fn free_list_next(&self, FreeIndex(base): FreeIndex, offset: Offset) |
| -> usize |
| { |
| let capacity = self.0; |
| let offset = offset.int_offset(); |
| |
| assert!(base < capacity); |
| assert!(offset <= capacity); |
| let base = base + 1; |
| |
| if capacity - offset >= base { |
| offset + base // Fine within the range |
| } else { |
| // Mathematically, capacity < offset + base < 2*capacity |
| // Wrap once, mod (capacity + 1), result again in range |
| offset |
| .wrapping_add(base) |
| .wrapping_sub(capacity + 1) |
| } |
| } |
| |
| /// Get the offset difference between the index and the next element. |
| /// Computes a potentially wrapping positive offset where zero is the element following the |
| /// base. |
| /// |
| /// This is the reverse of `free_list_next`. |
| fn free_list_offset(&self, FreeIndex(base): FreeIndex, to: usize) |
| -> Offset |
| { |
| let capacity = self.0; |
| |
| assert!(base != to, "Cant offset element to itself"); |
| assert!(base < capacity, "Should never have to offset the end-of-list marker"); |
| assert!(to <= capacity, "Can only offset to the end-of-list marker"); |
| let base = base + 1; |
| |
| Offset::from_int_offset(if base <= to { |
| to - base |
| } else { |
| // Wrap once, mod (capacity + 1), result again in range |
| to |
| .wrapping_add(capacity + 1) |
| .wrapping_sub(base) |
| }) |
| } |
| } |
| |
| impl Generation { |
| pub(crate) fn advance(&mut self) { |
| assert!(self.0 > 0); |
| self.0 = self.0.wrapping_add(1).max(1) |
| } |
| } |
| |
| impl Offset { |
| pub(crate) fn from_int_offset(offset: usize) -> Self { |
| assert!(offset < isize::max_value() as usize); |
| Offset((offset as isize).checked_neg().unwrap()) |
| } |
| |
| pub(crate) fn int_offset(self) -> usize { |
| self.0.checked_neg().unwrap() as usize |
| } |
| } |
| |
| impl Default for Generation { |
| fn default() -> Self { |
| Generation(1) |
| } |
| } |
| |
| impl From<Generation> for GenerationOrFreelink { |
| fn from(gen: Generation) -> GenerationOrFreelink { |
| GenerationOrFreelink(gen.0) |
| } |
| } |
| |
| impl From<Offset> for GenerationOrFreelink { |
| fn from(offset: Offset) -> GenerationOrFreelink { |
| GenerationOrFreelink(offset.0) |
| } |
| } |
| |
| #[cfg(test)] |
| mod tests { |
| use super::*; |
| use crate::slice::ManagedSlice as Slice; |
| |
| #[test] |
| fn simple() { |
| let mut elements = [0u32; 2]; |
| let mut slots = [Slot::default(); 2]; |
| |
| let mut map = SlotMap::new( |
| Slice::Borrowed(&mut elements[..]), |
| Slice::Borrowed(&mut slots[..])); |
| let key42 = map.insert(42).unwrap(); |
| let keylo = map.insert('K' as _).unwrap(); |
| |
| assert_eq!(map.insert(0x9999), None); |
| assert_eq!(map.get(key42).cloned(), Some(42)); |
| assert_eq!(map.get(keylo).cloned(), Some('K' as _)); |
| |
| assert!(map.remove(key42).is_some()); |
| assert_eq!(map.get(key42), None); |
| |
| let lastkey = map.insert(0x9999).unwrap(); |
| assert_eq!(map.get(lastkey).cloned(), Some(0x9999)); |
| |
| *map.remove(keylo).unwrap() = 0; |
| assert_eq!(map.get(lastkey).cloned(), Some(0x9999)); |
| assert!(map.remove(lastkey).is_some()); |
| } |
| |
| #[test] |
| fn retained() { |
| let mut elements = [0u32; 1]; |
| let mut slots = [Slot::default(); 1]; |
| |
| let mut map = SlotMap::new( |
| Slice::Borrowed(&mut elements[..]), |
| Slice::Borrowed(&mut slots[..])); |
| let key = map.insert(0xde).unwrap(); |
| map.remove(key).unwrap(); |
| assert_eq!(map.get(key), None); |
| |
| let new_key = map.insert(0xad).unwrap(); |
| |
| assert_eq!(map.get(key), None); |
| assert_eq!(map.get(new_key).cloned(), Some(0xad)); |
| |
| assert_eq!(map.remove(key), None); |
| map.remove(new_key).unwrap(); |
| |
| assert_eq!(map.get(key), None); |
| assert_eq!(map.get(new_key), None); |
| } |
| |
| #[test] |
| fn non_simple_free_list() { |
| // Check the free list implementation |
| let mut elements = [0u32; 3]; |
| let mut slots = [Slot::default(); 3]; |
| |
| let mut map = SlotMap::new( |
| Slice::Borrowed(&mut elements[..]), |
| Slice::Borrowed(&mut slots[..])); |
| |
| let key0 = map.insert(0).unwrap(); |
| let key1 = map.insert(1).unwrap(); |
| let key2 = map.insert(2).unwrap(); |
| |
| *map.remove(key1).unwrap() = 0xF; |
| assert_eq!(map.free_top, 1); |
| assert_eq!(map.get(key0).cloned(), Some(0)); |
| assert_eq!(map.get(key2).cloned(), Some(2)); |
| |
| *map.remove(key2).unwrap() = 0xF; |
| assert_eq!(map.free_top, 2); |
| assert_eq!(map.get(key0).cloned(), Some(0)); |
| |
| *map.remove(key0).unwrap() = 0xF; |
| assert_eq!(map.free_top, 0); |
| |
| let key0 = map.insert(0).unwrap(); |
| assert_eq!(map.free_top, 2); |
| let key1 = map.insert(1).unwrap(); |
| let key2 = map.insert(2).unwrap(); |
| assert_eq!(map.get(key0).cloned(), Some(0)); |
| assert_eq!(map.get(key1).cloned(), Some(1)); |
| assert_eq!(map.get(key2).cloned(), Some(2)); |
| } |
| } |