Crate generic_slab 

generic_slab is a fork of slab that keeps the familiar Slab<T> API but provides more control over the key and storage types. Using a generic approach you can for example implement strong typed keys that must fit the data type stored in the slab, or you can use a fixed size array as backing storage for the slab data.

At its core is GenericSlab<T, TKey, TEntries>, which lets you customize

• the key type (TKey: Key<T>) and
• the backing storage (TEntries: Entries<T, TKey>).

This enables things like:

• strong, type-safe handles that can’t be mixed across element types
• fixed-capacity slabs backed by arrays or ArrayVec
• alternative storage layouts, as long as they implement Entries

Differences from the original slab crate

Compared to slab:

• generic_slab::Slab<T> is a drop-in replacement for slab::Slab<T>: it uses usize keys and a Vec<Entry<_, _>> behind the scenes.
• You can use GenericSlab<T, TKey, TEntries> directly to plug in a custom key type (anything that implements Key<T>, e.g. Handle<T>).
• You can plug in a custom storage type for entries by implementing Entries<T, TKey> for your own collection type.
• The crate provides StrongSlab<T>, which uses Handle<T> for keys and protects you from accidentally mixing keys from different slabs or different element types.

• generic_slab is no_std-friendly (it works without std if you disable the default std feature).

If you just need the behavior of the original slab, use Slab<T>. If you need more control, use GenericSlab<T, TKey, TEntries> or StrongSlab<T>.

Basic usage (drop-in for slab)

use generic_slab::Slab;

let mut slab = Slab::new();

let hello = slab.insert("hello");
let world = slab.insert("world");

assert_eq!(slab[hello], "hello");
assert_eq!(slab[world], "world");

slab[world] = "earth";
assert_eq!(slab[world], "earth");

Custom Entries Storage (with fixed capacity)

This example shows how to replace the default Vec<Entry<_, _>> with a fixed-capacity ArrayVec-based storage.

use arrayvec::ArrayVec;
use generic_slab::{GenericSlab, Entries, Entry, Key};

#[derive(Default)]
struct FixedEntries<T, K, const N: usize>(ArrayVec<Entry<T, K>, N>)
where
    K: Key<T>;

impl<T, K, const N: usize> AsRef<[Entry<T, K>]> for FixedEntries<T, K, N>
where
    K: Key<T>,
{
    fn as_ref(&self) -> &[Entry<T, K>] {
        &self.0
    }
}

impl<T, K, const N: usize> AsMut<[Entry<T, K>]> for FixedEntries<T, K, N>
where
    K: Key<T>,
{
    fn as_mut(&mut self) -> &mut [Entry<T, K>] {
        &mut self.0
    }
}

impl<T, K, const N: usize> Entries<T, K> for FixedEntries<T, K, N>
where
    K: Key<T>,
{
    fn capacity(&self) -> usize {
        N
    }

    fn push(&mut self, entry: Entry<T, K>) {
        self.0.push(entry);
    }

    fn pop(&mut self) -> Option<Entry<T, K>> {
        self.0.pop()
    }

    fn clear(&mut self) {
        self.0.clear();
    }
}

/// A slab with a fixed maximum of `N` entries, using `usize` keys.
type FixedSlab<T, const N: usize> = GenericSlab<T, usize, FixedEntries<T, usize, N>>;

// Use it like a normal slab, but it will never reallocate:
let mut slab: FixedSlab<&str, 4> = GenericSlab::new();
let k0 = slab.insert("zero");
let k1 = slab.insert("one");
let k2 = slab.insert("two");
let k3 = slab.insert("three");

assert_eq!(slab[k0], "zero");
assert_eq!(slab[k3], "three");

// Inserting a 5th element would panic here because the ArrayVec is full.

Example: Custom Key Type using Handle

This example uses StrongSlab<T>, which is a GenericSlab configured with Handle<T> as key type. Handle<T> is strongly typed and carries enough metadata to detect stale or cross-slab keys.

use generic_slab::StrongSlab;

// Keys are `Handle<String>` instead of `usize`.
let mut slab: StrongSlab<String> = StrongSlab::default();

let a = slab.insert("hello".into());
let b = slab.insert("world".into());

assert_eq!(slab[a], "hello");
assert_eq!(slab[b], "world");

// Handles are `Copy` and cheap to pass around.
let a2 = a;
assert_eq!(slab[a2], "hello");

StrongSlab<T> and Handle<T> prevent mixing keys of different element types:

use generic_slab::StrongSlab;

let mut slab: StrongSlab<String> = StrongSlab::default();
let a = slab.insert("hello".into());

let mut ints: StrongSlab<i32> = StrongSlab::default();
ints[a]; // <- does not compile: `Handle<String>` is not a key for `StrongSlab<i32>`.

It also prevents reusing old handles for new data that was inserted at the same place:

use generic_slab::StrongSlab;

let mut slab: StrongSlab<String> = StrongSlab::default();
let handle0 = slab.insert("hello".into());
slab.remove(handle0);

let handle1 = slab.insert("world".into()); // Will be placed at the same position than the old `handle0`.
assert!(slab.get(handle0).is_none()); // But you cant get the new entry from the old handle.
assert!(slab.get(handle1).is_some());

For even more control, you can implement Key<T> for your own key type and plug it into GenericSlab<T, TKey, TEntries> together with a custom Entries<T, TKey> implementation.

Range iterators (feature range)

When the optional range feature is enabled, slabs gain efficient range iterators that only visit occupied entries and respect the insertion order.

The following APIs are available on GenericSlab (and therefore on Slab and StrongSlab) when feature = "range" is enabled:

• GenericSlab::range -> RangeIter over (&T)
• GenericSlab::range_mut -> RangeIterMut over (&mut T)

Both methods accept any R: RangeBounds<TKey> (e.g. key_a..key_b, ..key_b, key_a.., ..= etc.). Only valid, occupied keys in the specified range are yielded. If all bounds are invalid, the iterator is empty.

Iteration order and “reverse” ranges

Range iterators always walk the slab in insertion order, starting from the first element that falls into the range and then wrapping around until the upper bound is reached.

A “reverse” range like key_b..key_a behaves as a negated range: it yields all occupied entries that are not in key_a..key_b, still in insertion order.

Example: simple range

use generic_slab::Slab;

let mut slab = Slab::new();

let k0 = slab.insert(0);
let k1 = slab.insert(1);
let k2 = slab.insert(2);
let k3 = slab.insert(3);

let mut it = slab.range(k1..k3);

assert_eq!(it.next(), Some((k1, &1)));
assert_eq!(it.next(), Some((k2, &2)));
assert_eq!(it.next(), None);

Example: “negated” range using reversed bounds

use generic_slab::Slab;

let mut slab = Slab::new();

let k0 = slab.insert(0);
let k1 = slab.insert(1);
let k2 = slab.insert(2);
let k3 = slab.insert(3);

// `k3..k1` yields everything that is *not* in `k1..k3`
let mut it = slab.range(k3..k1);

assert_eq!(it.next(), Some((k3, &3))); // after k3, wrap to start
assert_eq!(it.next(), Some((k0, &0)));
assert_eq!(it.next(), None);

These iterators are thin wrappers around RangeIter and RangeIterMut, which you can also name explicitly if you need to store them in a concrete type.

Capacity and reallocation

The capacity of a slab is the amount of space allocated for any future values that will be inserted in the slab. This is not to be confused with the length of the slab, which specifies the number of actual values currently being inserted. If a slab’s length is equal to its capacity, the next value inserted into the slab will require growing (if the underlying buffer supports it).

Implementation

GenericSlab is backed by a generic storage of slots. Each slot is either occupied or vacant. GenericSlab maintains a stack of vacant slots using a linked list. To find a vacant slot, the stack is popped. When a slot is released, it is pushed onto the stack.

Re-exports

pub use crate::generic::GenericSlab;

Modules

generic

Module that contains the generic base implementation of Slab

Structs

Handle

Strong typed, safe handle that can be used as key for the GenericSlab.

Enums

Entry

Represents the entry that is used internally to store the items

Traits

Entries

Trait that represents any type of collection that can store slab entries.

Key

Trait that represents any type that can be used as key for the GenericSlab.

Type Aliases

IntoIter

A consuming iterator over the values stored in a Slab

Iter

An iterator over the values stored in the Slab

IterMut

A mutable iterator over the values stored in the Slab

RangeIter

A iterator over a specific range of values stored in the Slab

RangeIterMut

A mutable iterator over a specific range of values stored in the Slab

Slab

Pre-allocated storage for a uniform data type

StrongSlab

Pre-allocated storage for a uniform data type with a Handle as strong key.

VacantEntry

A handle to a vacant entry in a Slab.