use super::NONE;
const INLINE: usize = 4;
const CHUNKS: usize = 31;
#[derive(Clone, Debug)]
enum Entry<T> {
Live(T),
Free(u32),
}
#[derive(Debug)]
pub(super) struct Slab<T> {
inline: [Entry<T>; INLINE],
chunks: [Vec<Entry<T>>; CHUNKS],
len: u32,
free_head: u32,
free_len: u32,
#[cfg(test)]
cap: u32,
}
impl<T> Default for Slab<T> {
fn default() -> Self {
Self {
inline: core::array::from_fn(|_| Entry::Free(NONE)),
chunks: core::array::from_fn(|_| Vec::new()),
len: 0,
free_head: NONE,
free_len: 0,
#[cfg(test)]
cap: NONE,
}
}
}
impl<T: Clone> Clone for Slab<T> {
fn clone(&self) -> Self {
Self {
inline: self.inline.clone(),
chunks: core::array::from_fn(|c| {
let Some(src) = self.chunks.get(c) else {
return Vec::new();
};
if src.capacity() == 0 {
return Vec::new();
}
let mut v = Vec::with_capacity(chunk_cap(c));
v.extend(src.iter().cloned());
v
}),
len: self.len,
free_head: self.free_head,
free_len: self.free_len,
#[cfg(test)]
cap: self.cap,
}
}
}
fn chunk_cap(c: usize) -> usize {
u32::try_from(c)
.ok()
.and_then(|c| INLINE.checked_shl(c))
.unwrap_or(0)
}
#[inline]
fn place(i: u32) -> Option<(usize, usize)> {
let i = i as usize;
if i < INLINE {
return None;
}
let q = i / INLINE;
let c = (usize::BITS - 1).saturating_sub(q.leading_zeros()) as usize;
let off = i.saturating_sub(chunk_cap(c));
Some((c, off))
}
impl<T> Slab<T> {
fn entry(&self, i: u32) -> Option<&Entry<T>> {
if i >= self.len {
return None;
}
match place(i) {
None => self.inline.get(i as usize),
Some((c, off)) => self.chunks.get(c)?.get(off),
}
}
fn entry_mut(&mut self, i: u32) -> Option<&mut Entry<T>> {
if i >= self.len {
return None;
}
match place(i) {
None => self.inline.get_mut(i as usize),
Some((c, off)) => self.chunks.get_mut(c)?.get_mut(off),
}
}
#[inline]
pub(super) fn get(&self, i: u32) -> Option<&T> {
match self.entry(i)? {
Entry::Live(t) => Some(t),
Entry::Free(_) => None,
}
}
pub(super) fn insert(&mut self, t: T) -> Option<u32> {
if self.free_head != NONE {
let i = self.free_head;
let entry = self.entry_mut(i)?;
let Entry::Free(next) = *entry else {
return None;
};
*entry = Entry::Live(t);
self.free_head = next;
self.free_len = self.free_len.saturating_sub(1);
return Some(i);
}
let i = self.len;
#[cfg(test)]
if i >= self.cap {
return None;
}
if i == NONE {
return None;
}
match place(i) {
None => {
*self.inline.get_mut(i as usize)? = Entry::Live(t);
}
Some((c, _)) => {
let chunk = self.chunks.get_mut(c)?;
if chunk.capacity() == 0 {
*chunk = Vec::with_capacity(chunk_cap(c));
}
chunk.push(Entry::Live(t));
}
}
self.len = i.saturating_add(1);
Some(i)
}
pub(super) fn remove(&mut self, i: u32) -> Option<T> {
let head = self.free_head;
let entry = self.entry_mut(i)?;
if matches!(entry, Entry::Free(_)) {
return None;
}
let Entry::Live(t) = core::mem::replace(entry, Entry::Free(head)) else {
return None;
};
self.free_head = i;
self.free_len = self.free_len.saturating_add(1);
Some(t)
}
pub(super) fn free_len(&self) -> usize {
self.free_len as usize
}
#[cfg(test)]
pub(super) fn len(&self) -> usize {
self.len as usize
}
#[cfg(test)]
pub(super) fn iter(&self) -> impl Iterator<Item = &T> {
fn live<T>(e: &Entry<T>) -> Option<&T> {
match e {
Entry::Live(t) => Some(t),
Entry::Free(_) => None,
}
}
let inline = self.inline.iter().take(self.len as usize).filter_map(live);
inline.chain(self.chunks.iter().flatten().filter_map(live))
}
pub(super) fn compacted(self) -> (Self, Vec<u32>) {
let mut map = Vec::with_capacity(self.len as usize);
let mut out = Self::default();
#[cfg(test)]
{
out.cap = self.cap;
}
let len = self.len as usize;
let all = self
.inline
.into_iter()
.take(len)
.chain(self.chunks.into_iter().flatten());
for e in all {
super::cost::count(super::cost::Step::Visit);
match e {
Entry::Live(t) => map.push(out.insert(t).unwrap_or(NONE)),
Entry::Free(_) => map.push(NONE),
}
}
(out, map)
}
#[cfg(test)]
pub(super) fn limit_entries(&mut self, cap: usize) {
self.cap = u32::try_from(cap).unwrap_or(NONE);
}
#[cfg(test)]
pub(super) fn heap_bytes(&self) -> usize {
let each = core::mem::size_of::<Entry<T>>();
self.chunks
.iter()
.map(|c| c.capacity().saturating_mul(each))
.fold(0usize, usize::saturating_add)
}
}
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used, clippy::indexing_slicing)]
use super::*;
#[test]
fn places_cover_the_index_space_in_order() {
let mut want = (0usize, 0usize);
for i in INLINE as u32..10_000 {
let (c, off) = place(i).unwrap();
assert!(off < chunk_cap(c), "{i}");
assert_eq!((c, off), want, "{i}");
want = if off + 1 == chunk_cap(c) {
(c + 1, 0)
} else {
(c, off + 1)
};
}
assert!(place(u32::MAX - 1).unwrap().0 < CHUNKS);
}
#[test]
fn entries_never_move_and_are_reused() {
let mut s: Slab<u64> = Slab::default();
let ids: Vec<u32> = (0..100).map(|v| s.insert(v).unwrap()).collect();
assert_eq!(ids, (0..100).collect::<Vec<u32>>());
let first = s.get(10).unwrap() as *const u64;
for v in 100..1000 {
s.insert(v).unwrap();
}
assert_eq!(s.get(10).unwrap() as *const u64, first);
assert_eq!(s.remove(7), Some(7));
assert_eq!(s.remove(7), None);
assert_eq!(s.get(7), None);
assert_eq!(s.remove(500), Some(500));
assert_eq!(s.free_len(), 2);
assert_eq!(s.insert(5000).unwrap(), 500);
assert_eq!(s.insert(5001).unwrap(), 7);
assert_eq!(s.get(7), Some(&5001));
assert_eq!(s.free_len(), 0);
assert_eq!(s.get(1000), None);
let mut c = s.clone();
let at = c.get(500).unwrap() as *const u64;
c.insert(1).unwrap();
assert_eq!(c.get(500).unwrap() as *const u64, at);
for (k, ch) in c.chunks.iter().enumerate() {
assert!(ch.capacity() == 0 || ch.capacity() == chunk_cap(k));
}
for i in (0..1000).step_by(2) {
s.remove(i);
}
let (s, map) = s.compacted();
assert_eq!(s.iter().count(), 500);
assert_eq!(map[0], NONE);
assert_eq!(s.get(map[1]), Some(&1));
assert_eq!(s.get(map[999]), Some(&999));
assert_eq!(s.free_len(), 0);
assert_eq!(s.len(), 500);
}
#[test]
fn a_few_entries_allocate_nothing() {
let mut s: Slab<u64> = Slab::default();
for v in 0..INLINE as u64 {
s.insert(v).unwrap();
}
s.remove(1);
s.insert(9).unwrap();
assert_eq!(s.heap_bytes(), 0);
s.insert(10).unwrap();
assert_eq!(s.heap_bytes(), INLINE * core::mem::size_of::<Entry<u64>>());
}
#[test]
fn a_limited_slab_refuses_new_entries() {
let mut s: Slab<u64> = Slab::default();
s.limit_entries(2);
assert_eq!(s.insert(1), Some(0));
assert_eq!(s.insert(2), Some(1));
assert_eq!(s.insert(3), None);
s.remove(0);
assert_eq!(s.insert(4), Some(0));
}
}