Struct idcontain::IdSlab [−][src]
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>
[src]
impl<T> IdSlab<T>
pub fn new() -> Self
[src]
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
[src]
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
[src]
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
[src]
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
[src]
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
[src]
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>
[src]
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>
[src]
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>
[src]
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>
[src]
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>pub fn iter(&self) -> Iter<T>
[src]
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>pub fn iter_mut(&mut self) -> IterMut<T>
[src]
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>
[src]
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>
[src]
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>>
[src]
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<T: Clone> Clone for IdSlab<T>
[src]
impl<T: Clone> Clone for IdSlab<T>
fn clone(&self) -> IdSlab<T>
[src]
fn clone(&self) -> IdSlab<T>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
impl<T: Debug> Debug for IdSlab<T>
[src]
impl<T: Debug> Debug for IdSlab<T>
fn fmt(&self, f: &mut Formatter) -> Result
[src]
fn fmt(&self, f: &mut Formatter) -> Result
Formats the value using the given formatter. Read more
impl<T> Default for IdSlab<T>
[src]
impl<T> Default for IdSlab<T>
impl<T> Index<Id<T>> for IdSlab<T>
[src]
impl<T> Index<Id<T>> for IdSlab<T>
type Output = T
The returned type after indexing.
fn index(&self, id: Id<T>) -> &Self::Output
[src]
fn index(&self, id: Id<T>) -> &Self::Output
Performs the indexing (container[index]
) operation.
impl<T> IndexMut<Id<T>> for IdSlab<T>
[src]
impl<T> IndexMut<Id<T>> for IdSlab<T>
fn index_mut(&mut self, id: Id<T>) -> &mut Self::Output
[src]
fn index_mut(&mut self, id: Id<T>) -> &mut Self::Output
Performs the mutable indexing (container[index]
) operation.
impl<'a, T: 'a> IntoIterator for &'a IdSlab<T>
[src]
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
[src]
fn into_iter(self) -> Self::IntoIter
Creates an iterator from a value. Read more
impl<'a, T: 'a> IntoIterator for &'a mut IdSlab<T>
[src]
impl<'a, T: 'a> IntoIterator for &'a mut IdSlab<T>