#![no_std]
extern crate alloc;
#[cfg(test)]
extern crate std;
use alloc::vec::Vec;
use core::{fmt, hash::Hash, marker::PhantomData};
#[cfg(feature = "serde")]
use serde::de::{MapAccess, Visitor};
#[cfg(feature = "serde")]
use serde::ser::SerializeMap;
#[cfg(feature = "serde")]
use serde::{Deserialize, Deserializer, Serialize, Serializer};
pub trait SlabKey: Copy + Eq + Hash {
fn index(self) -> usize;
fn from_index(index: usize) -> Self;
}
impl SlabKey for usize {
#[inline]
fn index(self) -> usize {
self
}
#[inline]
fn from_index(index: usize) -> Self {
index
}
}
impl SlabKey for u32 {
#[inline]
fn index(self) -> usize {
self as usize
}
#[inline]
fn from_index(index: usize) -> Self {
assert!(index <= u32::MAX as usize, "slot index does not fit in u32");
index as u32
}
}
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
#[cfg_attr(feature = "facet", derive(facet::Facet))]
#[cfg_attr(
feature = "rkyv",
derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize)
)]
pub struct IdSlab<K, V> {
slots: Vec<Option<V>>,
len: usize,
#[cfg_attr(feature = "rkyv", rkyv(omit_bounds))]
key: PhantomData<fn() -> K>,
}
impl<K: SlabKey, V> IdSlab<K, V> {
#[must_use]
pub fn new() -> Self {
Self {
slots: Vec::new(),
len: 0,
key: PhantomData,
}
}
#[must_use]
pub fn with_capacity(capacity: usize) -> Self {
Self {
slots: Vec::with_capacity(capacity),
len: 0,
key: PhantomData,
}
}
#[must_use]
pub fn len(&self) -> usize {
self.len
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len == 0
}
#[must_use]
pub fn slot_count(&self) -> usize {
self.slots.len()
}
#[must_use]
pub fn contains_key(&self, key: K) -> bool {
self.slots.get(key.index()).is_some_and(Option::is_some)
}
#[must_use]
pub fn get(&self, key: K) -> Option<&V> {
self.slots.get(key.index()).and_then(Option::as_ref)
}
#[must_use]
pub fn get_mut(&mut self, key: K) -> Option<&mut V> {
self.slots.get_mut(key.index()).and_then(Option::as_mut)
}
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
let index = key.index();
if index >= self.slots.len() {
self.slots.resize_with(index + 1, || None);
}
let previous = self.slots[index].replace(value);
if previous.is_none() {
self.len += 1;
}
previous
}
pub fn remove(&mut self, key: K) -> Option<V> {
let previous = self.slots.get_mut(key.index()).and_then(Option::take);
if previous.is_some() {
self.len -= 1;
}
previous
}
pub fn clear(&mut self) {
self.slots.clear();
self.len = 0;
}
#[must_use]
pub fn from_slots(mut slots: Vec<Option<V>>) -> Self {
while slots.last().is_some_and(Option::is_none) {
slots.pop();
}
let len = slots.iter().filter(|slot| slot.is_some()).count();
Self {
slots,
len,
key: PhantomData,
}
}
#[must_use]
pub fn into_slots(self) -> Vec<Option<V>> {
self.slots
}
pub fn values(&self) -> impl Iterator<Item = &V> {
self.slots.iter().filter_map(Option::as_ref)
}
pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
self.slots.iter_mut().filter_map(Option::as_mut)
}
pub fn keys(&self) -> impl Iterator<Item = K> + '_ {
self.slots
.iter()
.enumerate()
.filter(|(_, slot)| slot.is_some())
.map(|(index, _)| K::from_index(index))
}
#[must_use]
pub fn iter(&self) -> Iter<'_, K, V> {
Iter {
inner: self.slots.iter().enumerate(),
key: PhantomData,
}
}
pub fn iter_mut(&mut self) -> impl Iterator<Item = (K, &mut V)> + '_ {
self.slots
.iter_mut()
.enumerate()
.filter_map(|(index, slot)| {
slot.as_mut().map(|value| (K::from_index(index), value))
})
}
pub fn retain(&mut self, mut f: impl FnMut(K, &mut V) -> bool) {
self.slots.iter_mut().enumerate().for_each(|(index, slot)| {
if let Some(value) = slot.as_mut() {
let keep = f(K::from_index(index), value);
if !keep {
*slot = None;
self.len -= 1;
}
}
});
}
#[must_use]
pub fn as_slots(&self) -> &[Option<V>] {
&self.slots
}
#[must_use]
pub fn as_slots_mut(&mut self) -> &mut [Option<V>] {
&mut self.slots
}
}
impl<K: SlabKey, V> Default for IdSlab<K, V> {
fn default() -> Self {
Self::new()
}
}
impl<K: SlabKey, V> FromIterator<(K, V)> for IdSlab<K, V> {
fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
let mut slab = Self::new();
iter.into_iter().for_each(|(key, value)| {
slab.insert(key, value);
});
slab
}
}
impl<K: SlabKey, V> core::ops::Index<K> for IdSlab<K, V> {
type Output = V;
fn index(&self, key: K) -> &Self::Output {
self.get(key).expect("IdSlab: no entry for key")
}
}
impl<K: SlabKey, V> core::ops::IndexMut<K> for IdSlab<K, V> {
fn index_mut(&mut self, key: K) -> &mut Self::Output {
self.get_mut(key).expect("IdSlab: no entry for key")
}
}
pub struct Iter<'a, K, V> {
inner: core::iter::Enumerate<core::slice::Iter<'a, Option<V>>>,
key: PhantomData<fn() -> K>,
}
impl<K, V> Clone for Iter<'_, K, V> {
fn clone(&self) -> Self {
Self {
inner: self.inner.clone(),
key: PhantomData,
}
}
}
impl<K, V> fmt::Debug for Iter<'_, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Iter").finish_non_exhaustive()
}
}
impl<'a, K: SlabKey, V> Iterator for Iter<'a, K, V> {
type Item = (K, &'a V);
fn next(&mut self) -> Option<Self::Item> {
self.inner.by_ref().find_map(|(index, slot)| {
slot.as_ref().map(|value| (K::from_index(index), value))
})
}
}
pub struct IntoIter<K, V> {
inner: core::iter::Enumerate<alloc::vec::IntoIter<Option<V>>>,
key: PhantomData<fn() -> K>,
}
impl<K, V> fmt::Debug for IntoIter<K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("IntoIter").finish_non_exhaustive()
}
}
impl<K: SlabKey, V> Iterator for IntoIter<K, V> {
type Item = (K, V);
fn next(&mut self) -> Option<Self::Item> {
self.inner.by_ref().find_map(|(index, slot)| {
slot.map(|value| (K::from_index(index), value))
})
}
}
impl<'a, K: SlabKey, V> IntoIterator for &'a IdSlab<K, V> {
type IntoIter = Iter<'a, K, V>;
type Item = (K, &'a V);
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<K: SlabKey, V> IntoIterator for IdSlab<K, V> {
type IntoIter = IntoIter<K, V>;
type Item = (K, V);
fn into_iter(self) -> Self::IntoIter {
IntoIter {
inner: self.slots.into_iter().enumerate(),
key: PhantomData,
}
}
}
#[cfg(feature = "serde")]
impl<K, V> Serialize for IdSlab<K, V>
where
K: SlabKey + Serialize,
V: Serialize,
{
fn serialize<S: Serializer>(
&self,
serializer: S,
) -> Result<S::Ok, S::Error> {
let mut map = serializer.serialize_map(Some(self.len))?;
self.iter()
.try_for_each(|(key, value)| map.serialize_entry(&key, value))?;
map.end()
}
}
#[cfg(feature = "serde")]
impl<'de, K, V> Deserialize<'de> for IdSlab<K, V>
where
K: SlabKey + Deserialize<'de>,
V: Deserialize<'de>,
{
fn deserialize<D: Deserializer<'de>>(
deserializer: D,
) -> Result<Self, D::Error> {
deserializer.deserialize_map(IdSlabVisitor {
key: PhantomData,
value: PhantomData,
})
}
}
#[cfg(feature = "serde")]
struct IdSlabVisitor<K, V> {
key: PhantomData<fn() -> K>,
value: PhantomData<fn() -> V>,
}
#[cfg(feature = "serde")]
impl<'de, K, V> Visitor<'de> for IdSlabVisitor<K, V>
where
K: SlabKey + Deserialize<'de>,
V: Deserialize<'de>,
{
type Value = IdSlab<K, V>;
fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
formatter.write_str("a map from dense ids to values")
}
fn visit_map<A: MapAccess<'de>>(
self,
mut access: A,
) -> Result<Self::Value, A::Error> {
let mut slab = access
.size_hint()
.map(IdSlab::with_capacity)
.unwrap_or_default();
while let Some((key, value)) = access.next_entry()? {
slab.insert(key, value);
}
Ok(slab)
}
}
#[cfg(test)]
mod tests {
use alloc::{vec, vec::Vec};
use super::*;
#[cfg(feature = "serde")]
use alloc::string::String;
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
#[cfg_attr(feature = "facet", derive(facet::Facet))]
#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
#[cfg_attr(
feature = "rkyv",
derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize)
)]
#[cfg_attr(feature = "rkyv", rkyv(derive(Debug, Eq, PartialEq)))]
struct NodeId(u32);
impl SlabKey for NodeId {
fn index(self) -> usize {
self.0 as usize
}
fn from_index(index: usize) -> Self {
NodeId(index as u32)
}
}
#[test]
fn insert_get_and_replace_use_the_key_index() {
let mut slab = IdSlab::new();
assert_eq!(slab.insert(NodeId(2), "a"), None);
assert_eq!(slab.get(NodeId(2)), Some(&"a"));
assert_eq!(slab.insert(NodeId(2), "b"), Some("a"));
assert_eq!(slab.get(NodeId(2)), Some(&"b"));
assert_eq!(slab.len(), 1);
assert_eq!(slab.slot_count(), 3);
}
#[test]
fn remove_leaves_an_empty_slot() {
let mut slab = IdSlab::new();
slab.insert(NodeId(3), "a");
assert_eq!(slab.remove(NodeId(3)), Some("a"));
assert_eq!(slab.get(NodeId(3)), None);
assert_eq!(slab.len(), 0);
assert_eq!(slab.slot_count(), 4);
}
#[test]
fn iteration_is_in_ascending_key_order() {
let slab = [(NodeId(3), "c"), (NodeId(1), "a"), (NodeId(2), "b")]
.into_iter()
.collect::<IdSlab<_, _>>();
let keys = slab.keys().map(|key| key.0).collect::<Vec<_>>();
let values = slab.values().copied().collect::<Vec<_>>();
let pairs = slab
.iter()
.map(|(key, value)| (key.0, *value))
.collect::<Vec<_>>();
assert_eq!(keys, vec![1, 2, 3]);
assert_eq!(values, vec!["a", "b", "c"]);
assert_eq!(pairs, vec![(1, "a"), (2, "b"), (3, "c")]);
}
#[test]
fn from_slots_drops_trailing_empty_slots() {
let slab = IdSlab::<NodeId, _>::from_slots(vec![
Some("a"),
None,
Some("c"),
None,
]);
assert_eq!(slab.len(), 2);
assert_eq!(slab.slot_count(), 3);
assert_eq!(slab.get(NodeId(0)), Some(&"a"));
assert_eq!(slab.get(NodeId(1)), None);
assert_eq!(slab.get(NodeId(2)), Some(&"c"));
}
#[test]
fn retain_updates_length() {
let mut slab = [(NodeId(0), 10), (NodeId(1), 20), (NodeId(2), 30)]
.into_iter()
.collect::<IdSlab<_, _>>();
slab.retain(|key, value| {
*value += 1;
key.0 != 1
});
assert_eq!(slab.len(), 2);
assert_eq!(slab.get(NodeId(0)), Some(&11));
assert_eq!(slab.get(NodeId(1)), None);
assert_eq!(slab.get(NodeId(2)), Some(&31));
}
#[cfg(feature = "serde")]
#[test]
fn serde_serializes_live_values_as_a_map() {
let slab = [(NodeId(2), "b"), (NodeId(0), "a")]
.into_iter()
.collect::<IdSlab<_, _>>();
let json = serde_json::to_string(&slab).expect("slab must serialize");
let decoded = serde_json::from_str::<IdSlab<NodeId, String>>(&json)
.expect("slab must deserialize");
assert_eq!(decoded.get(NodeId(0)).map(String::as_str), Some("a"));
assert_eq!(decoded.get(NodeId(1)), None);
assert_eq!(decoded.get(NodeId(2)).map(String::as_str), Some("b"));
}
#[cfg(feature = "rkyv")]
#[test]
fn rkyv_round_trips_the_slot_representation() {
use rkyv::rancor::Error;
let slab = [(NodeId(0), 10), (NodeId(2), 30)]
.into_iter()
.collect::<IdSlab<_, _>>();
let bytes = rkyv::to_bytes::<Error>(&slab).expect("slab must archive");
let archived =
rkyv::access::<ArchivedIdSlab<NodeId, i32>, Error>(&bytes)
.expect("archive is valid");
let decoded = rkyv::deserialize::<IdSlab<NodeId, i32>, Error>(archived)
.expect("slab must decode");
assert_eq!(decoded, slab);
}
#[cfg(feature = "facet")]
#[test]
fn facet_exposes_a_shape() {
let shape = <IdSlab<NodeId, i32> as facet::Facet>::SHAPE;
assert_eq!(shape.type_identifier, "IdSlab");
}
}