Struct idcontain::IdSlab

pub struct IdSlab<T> { /* fields omitted */ }

An IdSlab stores an unordered collection of elements with fast access by opaque Id-s.

Inserting an element returns an Id which may later be used for lookup and deletion. It supports O(1) insertion, deletion and id-lookup. Ordering is unstable when elements are added and removed.

The maximum number of elements which can be stored in an IdSlab is MAXIMUM_CAPACITY (currently 2^32). This keeps Id-s at 64bits. A future version may support custom types for the Id-s making the capacity-id-size trade-off customisable.

Example

use idcontain::{IdSlab, Id};

let mut id_slab: IdSlab<&'static str> = IdSlab::new();

// The `Id` type encodes the type of the value, to statically prevent errors caused by mixing
// id-s.
let hello_id: Id<&'static str> = id_slab.insert("hello");
let world_id = id_slab.insert("world");

assert_eq!(id_slab[hello_id], "hello");
assert_eq!(id_slab[world_id], "world");

assert_eq!(id_slab.remove(world_id), Some("world"));  // The value is returned on deletion.
assert!(!id_slab.contains(world_id));

// New id-s are different from previous ones, even though the memory is reused.
let new_world_id = id_slab.insert("new world");
assert!(new_world_id != world_id);

Id Reuse

Removing an Id will cause future lookups with that Id to fail (either returning None for get and remove, or panicking for indexing), but this feature is 'best-effort' and should not be relied on for memory safety or security.

In particular removing and adding an element 2^32 times will cause that Id to be reused. This is, for most workloads unlikely and is made even less likely when operations are more mixed (adding more elements and removing them in between).

Id Mixing

Using an Id from a different IdSlab will fail at compile time, unless both IdSlab-s are of the same type. You are encouraged to newtype liberally to make leverage this as much as possible.

When using Id-s of the same type, lookups are still most likely going to fail at runtime:

let mut id_slab_1 = IdSlab::new();
let id1 = id_slab_1.insert(1);

let mut id_slab_2 = IdSlab::new();
let id2 = id_slab_2.insert(1);

assert!(id1 != id2);
assert!(!id_slab_1.contains(id2));
assert!(!id_slab_2.contains(id1));

The mechanism behind this is built on the same tagging mechanism used for preventing Id reuse of the same IdSlab. As such, this feature is also best-effort and should not be used for memory safety or security.

For all other situations, it's probably fine. The probability curve follows the birthday paradox equation with m=2^32 / avg_num_elements_per_id_slab and n=num_id_slabs. So, for instance, 10 IdSlab-s with 1000 elements each, gives a collision probability of about (n^2/2m) = 0.001% or 1 in 100,000.

Methods

impl<T> IdSlab<T>

pub fn new() -> Self

Creates a new IdSlab with zero capacity.

The first insertion will cause an allocation.

pub fn with_capacity(capacity: usize) -> Self

Creates a new IdSlab with a given capacity.

As long as number of elements stays under this capacity, no re-allocation will be triggered.

pub fn with_capacity_and_seed_tag(capacity: usize, seed_tag: IdTag) -> Self

Creates a new IdSlab with a given capacity and seed tag.

This is an advanced feature which may cause more Id collisions between your IdSlab-s if used incorrectly.

The seed_tag of an IdSlab is the tag assigned to new slots. Removing elements increments this tag and wraps around, providing the mechanism for Id reuse prevention and Id mixing detection.

The new and with_capacity constructors set the seed tag to a random number, but better strategies exist for preventing collisions if you know your workload.

pub fn len(&self) -> usize

Returns the number of elements in the IdSlab.

Panics

None.

Example

let mut id_slab = IdSlab::new();
assert_eq!(id_slab.len(), 0);

let id = id_slab.insert(1);
assert_eq!(id_slab.len(), 1);

id_slab.remove(id);
assert_eq!(id_slab.len(), 0);

pub fn is_empty(&self) -> bool

Returns true if the slab is empty.

Panics

None.

Example

let mut id_slab = IdSlab::new();
assert!(id_slab.is_empty());

let id = id_slab.insert(1);
assert!(!id_slab.is_empty());

id_slab.remove(id);
assert!(id_slab.is_empty());

pub fn contains(&self, id: Id<T>) -> bool

Returns true if there exists an element with the given Id.

See struct-level docs for caveats about Id reuse and mixing (almost always fine, but contains may give you false positives in pathological cases so don't rely on it for memory safety or security).

Panics

None.

Example

let mut id_slab = IdSlab::new();
assert_eq!(id_slab.len(), 0);

let id = id_slab.insert(1);
assert!(id_slab.contains(id));

id_slab.remove(id);
assert!(!id_slab.contains(id));

pub fn get(&self, id: Id<T>) -> Option<&T>

Returns a reference to an element by Id or None if it doesn't exist.

Use indexing for a panicking version of this operation.

Panics

None.

Example

let mut id_slab = IdSlab::new();
let id = id_slab.insert(1);

assert_eq!(id_slab.get(id), Some(&1));

id_slab.remove(id);
assert_eq!(id_slab.get(id), None);

pub fn get_mut(&mut self, id: Id<T>) -> Option<&mut T>

Returns a mutable reference to an element by Id or None if it doesn't exist.

Use indexing for a panicking version of this operation.

Panics

None.

Example

let mut id_slab = IdSlab::new();
let id = id_slab.insert(1);

*id_slab.get_mut(id).unwrap() = 10;
assert_eq!(id_slab[id], 10);

id_slab.remove(id);
assert_eq!(id_slab.get_mut(id), None);

pub fn insert(&mut self, value: T) -> Id<T>

Inserts a new element into the IdSlab, returning its Id<T>.

In general the Id-s do not get reused and should not collide with other IdSlab-s, but caveats apply, see the struct-level doc for more details.

Panics

If self.len() == MAXIMUM_CAPACITY.

Example

let mut id_slab = IdSlab::new();
let id1 = id_slab.insert(1);
let id2 = id_slab.insert(2);

assert_eq!(id_slab[id1], 1);
assert_eq!(id_slab[id2], 2);

// Id-s are not (caveats apply) shared between `IdSlab`-s.
let mut new_id_slab = IdSlab::new();
let new_id1 = new_id_slab.insert(1);
assert!(new_id1 != id1);

// Id-s are not (caveats apply) reused.
id_slab.remove(id1);
let id3 = id_slab.insert(3);
assert!(id3 != id1);

pub fn remove(&mut self, id: Id<T>) -> Option<T>

Removes an element by Id returning its value.

Returns None if no element with the given Id exists. See the struct level docs for the pathological cases where this may not be the case.

Panics

None.

Example

let mut id_slab = IdSlab::new();
let id1 = id_slab.insert(1);

assert_eq!(id_slab[id1], 1);
assert_eq!(id_slab.remove(id1), Some(1));

assert!(!id_slab.contains(id1));
assert_eq!(id_slab.remove(id1), None);

Important traits for Iter<'a, T>

impl<'a, T: 'a> Iterator for Iter<'a, T> type Item = &'a T;

pub fn iter(&self) -> Iter<T>

Iterates over references to the elements in the IdSlab.

While this operation has good cache locality, its worst-case complexity is O(max_number_of_elements_ever). I.e. there are pathological cases where adding and removing 1 million elements, then adding one element back will cause iteration to be O(1 million).

The iteration order is unspecified, but it doesn't change unless the IdSlab is mutated.

Panics

None.

Example

let mut id_slab = IdSlab::new();
id_slab.insert(1);
id_slab.insert(2);
id_slab.insert(3);

for i in id_slab.iter() {
    println!("{}", i);  // Prints 1, 2, 3.
}

// Can use `&id_slab` instead:
for i in &id_slab {
    println!("{}", i);  // Prints 1, 2, 3.
}

Important traits for IterMut<'a, T>

impl<'a, T: 'a> Iterator for IterMut<'a, T> type Item = &'a mut T;

pub fn iter_mut(&mut self) -> IterMut<T>

Iterates over mutable references to the elements in the IdSlab.

See iter for notes on complexity and iteration order.

Panics

None.

Example

let mut id_slab = IdSlab::new();
id_slab.insert(1);
id_slab.insert(2);
id_slab.insert(3);

for value in id_slab.iter_mut() {  // Or `&mut id_slab`.
    *value += 1;
}

for i in &id_slab {
    println!("{}", i);  // Prints 2, 3, 4.
}

pub fn by_index(&self, index: u32) -> Option<&T>

Returns a reference to an element by index or None if it doesn't exist.

This is a low-level operation that bypasses the tag check. Useful for building other containers on top.

Panics

None.

Example

let mut id_slab = IdSlab::new();
let id = id_slab.insert(1);

assert_eq!(id_slab.by_index(0), Some(&1));

pub fn by_index_mut(&mut self, index: u32) -> Option<&mut T>

Returns a mutable reference to an element by index or None if it doesn't exist.

This is a low-level operation that bypasses the tag check. Useful for building other containers on top.

Panics

None.

Example

let mut id_slab = IdSlab::new();
let id = id_slab.insert(1);

*id_slab.by_index_mut(0).unwrap() = 10;
assert_eq!(id_slab[id], 10);

pub fn index_to_id(&self, index: u32) -> Option<Id<T>>

Returns the Id for a given occupied index.

Returns None if the index is invalid.

This is a low-level operation that bypasses the tag check. Useful for building other containers on top.

Panics

None.

Example

let mut id_slab = IdSlab::new();
let id = id_slab.insert(1);

assert_eq!(id_slab.index_to_id(0), Some(id));

Trait Implementations

impl<'a, T: 'a> IntoIterator for &'a IdSlab<T>

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

type Item = <Self::IntoIter as Iterator>::Item

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T: 'a> IntoIterator for &'a mut IdSlab<T>

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

type Item = <Self::IntoIter as Iterator>::Item

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Clone> Clone for IdSlab<T>

fn clone(&self) -> IdSlab<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Default for IdSlab<T>

fn default() -> Self

Returns the "default value" for a type.

impl<T: Debug> Debug for IdSlab<T>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T> Index<Id<T>> for IdSlab<T>

type Output = T

The returned type after indexing.

fn index(&self, id: Id<T>) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> IndexMut<Id<T>> for IdSlab<T>

fn index_mut(&mut self, id: Id<T>) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.