[−][src]Struct idcontain::IdSlab
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]
pub fn new() -> Self
[src]
Creates a new IdSlab
with zero capacity.
The first insertion will cause an allocation.
pub fn with_capacity(capacity: usize) -> Self
[src]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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>
[src]
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]
impl<'a, T: 'a> IntoIterator for &'a mut IdSlab<T>
[src]
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
[src]
impl<T: Clone> Clone for IdSlab<T>
[src]
impl<T> Default for IdSlab<T>
[src]
impl<T: Debug> Debug for IdSlab<T>
[src]
impl<T> Index<Id<T>> for IdSlab<T>
[src]
impl<T> IndexMut<Id<T>> for IdSlab<T>
[src]
Auto Trait Implementations
impl<T> Send for IdSlab<T> where
T: Send,
T: Send,
impl<T> Sync for IdSlab<T> where
T: Sync,
T: Sync,
impl<T> Unpin for IdSlab<T> where
T: Unpin,
T: Unpin,
impl<T> UnwindSafe for IdSlab<T> where
T: UnwindSafe,
T: UnwindSafe,
impl<T> RefUnwindSafe for IdSlab<T> where
T: RefUnwindSafe,
T: RefUnwindSafe,
Blanket Implementations
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> From<T> for T
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,