managed/src/slotmap.rs

//! 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));
    }
}