slab

slab.rs

enum Entry<T> {
    Vacant(usize),
    Occupied(T),
}

pub struct Slab<T> {
    entries: Vec<Entry<T>>,
    next: usize,
}

impl<T> Slab<T> {
    pub const fn new() -> Self {
        Self { entries: vec![], next: usize::MAX, }
    }
    pub fn insert(&mut self, v: T) -> usize {
        let entry = Entry::Occupied(v);
        let next = self.next;
        if next == usize::MAX {
            self.entries.push(entry);
            self.entries.len() - 1
        } else {
            match std::mem::replace(&mut self.entries[next], entry) {
                Entry::Vacant(next2) => {
                    self.next = next2;
                    next
                }
                _ => unreachable!(),
            }
        }
    }
    pub fn remove(&mut self, i: usize) {
        match self.entries[i] {
            Entry::Occupied(_) => {
                self.entries[i] = Entry::Vacant(self.next);
                self.next = i;
            }
            _ => unreachable!(),
        }
    }
    pub fn get(&self, i: usize) -> Option<&T> {
        self.entries.get(i).and_then(|entry| match entry {
            Entry::Vacant(_) => None,
            Entry::Occupied(v) => Some(v)
        })
    }

    pub fn get_mut(&mut self, i: usize) -> Option<&mut T> {
        self.entries.get_mut(i).and_then(|entry| match entry {
            Entry::Vacant(_) => None,
            Entry::Occupied(v) => Some(v)
        })
    }
}