#[derive(Debug, Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
pub struct Handle {
gen: usize,
idx: usize,
}
#[derive(Debug, Clone)]
pub struct Iterator<'a, T> {
i: std::iter::Enumerate<std::slice::Iter<'a, (usize, Slot<T>)>>,
}
#[derive(Debug, Clone)]
enum Slot<T> {
Occupied { itm: T },
Empty { next_free: Option<usize> },
}
#[derive(Debug, Clone, Default)]
pub struct GenMap<T> {
slots: Vec<(usize, Slot<T>)>,
freelist_head: Option<usize>,
count: usize,
}
impl<T> GenMap<T> {
pub fn with_capacity(capacity: usize) -> Self {
GenMap {
slots: Vec::with_capacity(capacity),
freelist_head: None,
count: 0,
}
}
pub fn insert(&mut self, itm: T) -> Handle {
self.count = self
.count
.checked_add(1)
.expect("Count overflow; I bet this is a bug.");
if let Some(i) = self.freelist_head {
let slot = self
.slots
.get_mut(i)
.expect("Invalid freelist head? Should never happen!");
let gen = match slot {
(_gen, Slot::Occupied { .. }) => {
unreachable!("Freelist points at an occupied slot, should never happen!");
}
(gen, Slot::Empty { next_free }) => {
self.freelist_head = *next_free;
gen
}
};
let new_gen = gen.checked_add(1).expect("Aiee, generation overflowed!");
*slot = (new_gen, Slot::Occupied { itm });
Handle {
gen: new_gen,
idx: i,
}
} else {
let idx = self.slots.len();
let gen = 1;
self.slots.push((gen, Slot::Occupied { itm }));
Handle { gen, idx }
}
}
pub fn get(&self, h: Handle) -> Option<&T> {
match self.slots.get(h.idx) {
None => None,
Some((_, Slot::Empty { .. })) => None,
Some((gen, Slot::Occupied { .. })) if *gen != h.gen => None,
Some((_gen, Slot::Occupied { itm })) => Some(itm),
}
}
pub fn get_mut(&mut self, h: Handle) -> Option<&mut T> {
match self.slots.get_mut(h.idx) {
None => None,
Some((_, Slot::Empty { .. })) => None,
Some((gen, Slot::Occupied { .. })) if *gen != h.gen => None,
Some((_gen, Slot::Occupied { itm })) => Some(itm),
}
}
pub fn remove(&mut self, h: Handle) -> Option<T> {
let s = self.slots.get_mut(h.idx);
let slot_contents = match s {
None => return None,
Some((_gen, Slot::Empty { .. })) => return None,
Some((gen, Slot::Occupied { .. })) if *gen != h.gen => return None,
Some(t) => t,
};
self.count = self
.count
.checked_sub(1)
.expect("Count underflow; should never happen");
let gen = slot_contents.0;
let new_slot = (
gen,
Slot::Empty {
next_free: self.freelist_head,
},
);
let old_contents = std::mem::replace(slot_contents, new_slot);
self.freelist_head = Some(h.idx);
match old_contents {
(_, Slot::Occupied { itm }) => Some(itm),
_ => unreachable!("A slot magically went from occupied to empty!"),
}
}
pub fn count(&self) -> usize {
self.count
}
pub fn capacity(&self) -> usize {
self.slots.capacity()
}
pub fn iter(&self) -> Iterator<T> {
Iterator {
i: self.slots.iter().enumerate(),
}
}
#[allow(dead_code)]
pub(crate) fn freelist_len(&self) -> usize {
let mut len = 0;
let mut head = self.freelist_head;
while let Some(i) = head {
len += 1;
match self.slots[i] {
(_gen, Slot::Empty { next_free }) => {
head = next_free;
}
_ => panic!("Freelist contains pointer to non-free slot?"),
}
}
len
}
}
impl<T> std::iter::Iterator for Iterator<'_, T> {
type Item = Handle;
fn next(&mut self) -> Option<Self::Item> {
loop {
match self.i.next() {
Some((_, (_, Slot::Empty { .. }))) => {
continue;
}
Some((idx, (gen, Slot::Occupied { .. }))) => {
return Some(Handle { idx, gen: *gen });
}
None => {
return None;
}
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_insert() {
let mut m: GenMap<String> = GenMap::default();
let v1 = "thing1".to_owned();
let v2 = "thing2".to_owned();
let h1 = m.insert(v1.clone());
let h2 = m.insert(v2.clone());
assert_eq!(m.count(), 2);
assert_eq!(&v1, m.get(h1).unwrap());
assert_eq!(&v2, m.get(h2).unwrap());
assert_ne!(&v1, m.get(h2).unwrap());
assert_ne!(&v2, m.get(h1).unwrap());
}
#[test]
fn test_remove() {
let mut m: GenMap<String> = GenMap::default();
let v1 = "thing1".to_owned();
let v2 = "thing2".to_owned();
let h1 = m.insert(v1.clone());
let h2 = m.insert(v2.clone());
assert_eq!(m.count(), 2);
assert_eq!(&v1, m.get(h1).unwrap());
assert_eq!(&v2, m.get(h2).unwrap());
m.remove(h1);
assert!(m.get(h1).is_none());
assert!(m.get(h2).is_some());
assert_eq!(m.count(), 1);
m.remove(h2);
assert!(m.get(h1).is_none());
assert!(m.get(h2).is_none());
assert_eq!(m.count(), 0);
}
#[test]
fn test_remove_then_add() {
let mut m: GenMap<String> = GenMap::default();
let v1 = "thing1".to_owned();
let v2 = "thing2".to_owned();
let h1 = m.insert(v1.clone());
let h2 = m.insert(v2.clone());
assert_eq!(&v1, m.get(h1).unwrap());
assert_eq!(&v2, m.get(h2).unwrap());
m.remove(h1);
assert_eq!(m.count(), 1);
assert!(m.get(h1).is_none());
assert!(m.get(h2).is_some());
let v3 = "thing3".to_owned();
let h3 = m.insert(v3.clone());
assert!(m.get(h1).is_none());
assert!(m.get(h3).is_some());
assert_eq!(m.count(), 2);
}
#[test]
fn test_freelist() {
let mut m: GenMap<String> = GenMap::default();
let v1 = "thing1".to_owned();
let v2 = "thing2".to_owned();
let v3 = "thing3".to_owned();
let h1 = m.insert(v1.clone());
let h2 = m.insert(v2.clone());
let _h3 = m.insert(v3.clone());
assert_eq!(&v1, m.get(h1).unwrap());
assert_eq!(&v2, m.get(h2).unwrap());
assert_eq!(m.freelist_len(), 0);
assert_eq!(m.count(), 3);
m.remove(h1);
assert_eq!(m.freelist_len(), 1);
assert_eq!(m.count(), 2);
m.remove(h1);
assert_eq!(m.freelist_len(), 1);
assert_eq!(m.count(), 2);
m.remove(h2);
assert_eq!(m.freelist_len(), 2);
assert_eq!(m.count(), 1);
let h4 = m.insert("thing4".to_owned());
assert_eq!(m.freelist_len(), 1);
assert_eq!(m.count(), 2);
m.remove(h4);
assert_eq!(m.freelist_len(), 2);
assert_eq!(m.count(), 1);
}
}