Struct slab::Slab

source ·
pub struct Slab<T> {
    pub(crate) entries: Vec<Entry<T>>,
    pub(crate) len: usize,
    pub(crate) next: usize,
}
Expand description

Pre-allocated storage for a uniform data type

See the module documentation for more details.

Fields§

§entries: Vec<Entry<T>>§len: usize§next: usize

Implementations§

source§

impl<T> Slab<T>

source

pub const fn new() -> Self

Construct a new, empty Slab.

The function does not allocate and the returned slab will have no capacity until insert is called or capacity is explicitly reserved.

This is const fn on Rust 1.39+.

§Examples
let slab: Slab<i32> = Slab::new();
source

pub fn with_capacity(capacity: usize) -> Slab<T>

Construct a new, empty Slab with the specified capacity.

The returned slab will be able to store exactly capacity without reallocating. If capacity is 0, the slab will not allocate.

It is important to note that this function does not specify the length of the returned slab, but only the capacity. For an explanation of the difference between length and capacity, see Capacity and reallocation.

§Examples
let mut slab = Slab::with_capacity(10);

// The slab contains no values, even though it has capacity for more
assert_eq!(slab.len(), 0);

// These are all done without reallocating...
for i in 0..10 {
    slab.insert(i);
}

// ...but this may make the slab reallocate
slab.insert(11);
source

pub fn capacity(&self) -> usize

Return the number of values the slab can store without reallocating.

§Examples
let slab: Slab<i32> = Slab::with_capacity(10);
assert_eq!(slab.capacity(), 10);
source

pub fn reserve(&mut self, additional: usize)

Reserve capacity for at least additional more values to be stored without allocating.

reserve does nothing if the slab already has sufficient capacity for additional more values. If more capacity is required, a new segment of memory will be allocated and all existing values will be copied into it. As such, if the slab is already very large, a call to reserve can end up being expensive.

The slab may reserve more than additional extra space in order to avoid frequent reallocations. Use reserve_exact instead to guarantee that only the requested space is allocated.

§Panics

Panics if the new capacity exceeds isize::MAX bytes.

§Examples
let mut slab = Slab::new();
slab.insert("hello");
slab.reserve(10);
assert!(slab.capacity() >= 11);
source

pub fn reserve_exact(&mut self, additional: usize)

Reserve the minimum capacity required to store exactly additional more values.

reserve_exact does nothing if the slab already has sufficient capacity for additional more values. If more capacity is required, a new segment of memory will be allocated and all existing values will be copied into it. As such, if the slab is already very large, a call to reserve can end up being expensive.

Note that the allocator may give the slab more space than it requests. Therefore capacity can not be relied upon to be precisely minimal. Prefer reserve if future insertions are expected.

§Panics

Panics if the new capacity exceeds isize::MAX bytes.

§Examples
let mut slab = Slab::new();
slab.insert("hello");
slab.reserve_exact(10);
assert!(slab.capacity() >= 11);
source

pub fn shrink_to_fit(&mut self)

Shrink the capacity of the slab as much as possible without invalidating keys.

Because values cannot be moved to a different index, the slab cannot shrink past any stored values. It will drop down as close as possible to the length but the allocator may still inform the underlying vector that there is space for a few more elements.

This function can take O(n) time even when the capacity cannot be reduced or the allocation is shrunk in place. Repeated calls run in O(1) though.

§Examples
let mut slab = Slab::with_capacity(10);

for i in 0..3 {
    slab.insert(i);
}

slab.shrink_to_fit();
assert!(slab.capacity() >= 3 && slab.capacity() < 10);

The slab cannot shrink past the last present value even if previous values are removed:

let mut slab = Slab::with_capacity(10);

for i in 0..4 {
    slab.insert(i);
}

slab.remove(0);
slab.remove(3);

slab.shrink_to_fit();
assert!(slab.capacity() >= 3 && slab.capacity() < 10);
source

pub(crate) fn recreate_vacant_list(&mut self)

Iterate through all entries to recreate and repair the vacant list. self.len must be correct and is not modified.

source

pub fn compact<F>(&mut self, rekey: F)
where F: FnMut(&mut T, usize, usize) -> bool,

Reduce the capacity as much as possible, changing the key for elements when necessary.

To allow updating references to the elements which must be moved to a new key, this function takes a closure which is called before moving each element. The second and third parameters to the closure are the current key and new key respectively. In case changing the key for one element turns out not to be possible, the move can be cancelled by returning false from the closure. In that case no further attempts at relocating elements is made. If the closure unwinds, the slab will be left in a consistent state, but the value that the closure panicked on might be removed.

§Examples

let mut slab = Slab::with_capacity(10);
let a = slab.insert('a');
slab.insert('b');
slab.insert('c');
slab.remove(a);
slab.compact(|&mut value, from, to| {
    assert_eq!((value, from, to), ('c', 2, 0));
    true
});
assert!(slab.capacity() >= 2 && slab.capacity() < 10);

The value is not moved when the closure returns Err:


let mut slab = Slab::with_capacity(100);
let a = slab.insert('a');
let b = slab.insert('b');
slab.remove(a);
slab.compact(|&mut value, from, to| false);
assert_eq!(slab.iter().next(), Some((b, &'b')));
source

pub fn clear(&mut self)

Clear the slab of all values.

§Examples
let mut slab = Slab::new();

for i in 0..3 {
    slab.insert(i);
}

slab.clear();
assert!(slab.is_empty());
source

pub fn len(&self) -> usize

Return the number of stored values.

§Examples
let mut slab = Slab::new();

for i in 0..3 {
    slab.insert(i);
}

assert_eq!(3, slab.len());
source

pub fn is_empty(&self) -> bool

Return true if there are no values stored in the slab.

§Examples
let mut slab = Slab::new();
assert!(slab.is_empty());

slab.insert(1);
assert!(!slab.is_empty());
source

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

Return an iterator over the slab.

This function should generally be avoided as it is not efficient. Iterators must iterate over every slot in the slab even if it is vacant. As such, a slab with a capacity of 1 million but only one stored value must still iterate the million slots.

§Examples
let mut slab = Slab::new();

for i in 0..3 {
    slab.insert(i);
}

let mut iterator = slab.iter();

assert_eq!(iterator.next(), Some((0, &0)));
assert_eq!(iterator.next(), Some((1, &1)));
assert_eq!(iterator.next(), Some((2, &2)));
assert_eq!(iterator.next(), None);
source

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

Return an iterator that allows modifying each value.

This function should generally be avoided as it is not efficient. Iterators must iterate over every slot in the slab even if it is vacant. As such, a slab with a capacity of 1 million but only one stored value must still iterate the million slots.

§Examples
let mut slab = Slab::new();

let key1 = slab.insert(0);
let key2 = slab.insert(1);

for (key, val) in slab.iter_mut() {
    if key == key1 {
        *val += 2;
    }
}

assert_eq!(slab[key1], 2);
assert_eq!(slab[key2], 1);
source

pub fn get(&self, key: usize) -> Option<&T>

Return a reference to the value associated with the given key.

If the given key is not associated with a value, then None is returned.

§Examples
let mut slab = Slab::new();
let key = slab.insert("hello");

assert_eq!(slab.get(key), Some(&"hello"));
assert_eq!(slab.get(123), None);
source

pub fn get_mut(&mut self, key: usize) -> Option<&mut T>

Return a mutable reference to the value associated with the given key.

If the given key is not associated with a value, then None is returned.

§Examples
let mut slab = Slab::new();
let key = slab.insert("hello");

*slab.get_mut(key).unwrap() = "world";

assert_eq!(slab[key], "world");
assert_eq!(slab.get_mut(123), None);
source

pub fn get2_mut(&mut self, key1: usize, key2: usize) -> Option<(&mut T, &mut T)>

Return two mutable references to the values associated with the two given keys simultaneously.

If any one of the given keys is not associated with a value, then None is returned.

This function can be used to get two mutable references out of one slab, so that you can manipulate both of them at the same time, eg. swap them.

§Panics

This function will panic if key1 and key2 are the same.

§Examples
use std::mem;

let mut slab = Slab::new();
let key1 = slab.insert(1);
let key2 = slab.insert(2);
let (value1, value2) = slab.get2_mut(key1, key2).unwrap();
mem::swap(value1, value2);
assert_eq!(slab[key1], 2);
assert_eq!(slab[key2], 1);
source

pub unsafe fn get_unchecked(&self, key: usize) -> &T

Return a reference to the value associated with the given key without performing bounds checking.

For a safe alternative see get.

This function should be used with care.

§Safety

The key must be within bounds.

§Examples
let mut slab = Slab::new();
let key = slab.insert(2);

unsafe {
    assert_eq!(slab.get_unchecked(key), &2);
}
source

pub unsafe fn get_unchecked_mut(&mut self, key: usize) -> &mut T

Return a mutable reference to the value associated with the given key without performing bounds checking.

For a safe alternative see get_mut.

This function should be used with care.

§Safety

The key must be within bounds.

§Examples
let mut slab = Slab::new();
let key = slab.insert(2);

unsafe {
    let val = slab.get_unchecked_mut(key);
    *val = 13;
}

assert_eq!(slab[key], 13);
source

pub unsafe fn get2_unchecked_mut( &mut self, key1: usize, key2: usize, ) -> (&mut T, &mut T)

Return two mutable references to the values associated with the two given keys simultaneously without performing bounds checking and safety condition checking.

For a safe alternative see get2_mut.

This function should be used with care.

§Safety
  • Both keys must be within bounds.
  • The condition key1 != key2 must hold.
§Examples
use std::mem;

let mut slab = Slab::new();
let key1 = slab.insert(1);
let key2 = slab.insert(2);
let (value1, value2) = unsafe { slab.get2_unchecked_mut(key1, key2) };
mem::swap(value1, value2);
assert_eq!(slab[key1], 2);
assert_eq!(slab[key2], 1);
source

pub fn key_of(&self, present_element: &T) -> usize

Get the key for an element in the slab.

The reference must point to an element owned by the slab. Otherwise this function will panic. This is a constant-time operation because the key can be calculated from the reference with pointer arithmetic.

§Panics

This function will panic if the reference does not point to an element of the slab.

§Examples

let mut slab = Slab::new();
let key = slab.insert(String::from("foo"));
let value = &slab[key];
assert_eq!(slab.key_of(value), key);

Values are not compared, so passing a reference to a different location will result in a panic:


let mut slab = Slab::new();
let key = slab.insert(0);
let bad = &0;
slab.key_of(bad); // this will panic
unreachable!();
source

pub fn insert(&mut self, val: T) -> usize

Insert a value in the slab, returning key assigned to the value.

The returned key can later be used to retrieve or remove the value using indexed lookup and remove. Additional capacity is allocated if needed. See Capacity and reallocation.

§Panics

Panics if the new storage in the vector exceeds isize::MAX bytes.

§Examples
let mut slab = Slab::new();
let key = slab.insert("hello");
assert_eq!(slab[key], "hello");
source

pub fn vacant_key(&self) -> usize

Returns the key of the next vacant entry.

This function returns the key of the vacant entry which will be used for the next insertion. This is equivalent to slab.vacant_entry().key(), but it doesn’t require mutable access.

§Examples
let mut slab = Slab::new();
assert_eq!(slab.vacant_key(), 0);

slab.insert(0);
assert_eq!(slab.vacant_key(), 1);

slab.insert(1);
slab.remove(0);
assert_eq!(slab.vacant_key(), 0);
source

pub fn vacant_entry(&mut self) -> VacantEntry<'_, T>

Return a handle to a vacant entry allowing for further manipulation.

This function is useful when creating values that must contain their slab key. The returned VacantEntry reserves a slot in the slab and is able to query the associated key.

§Examples
let mut slab = Slab::new();

let hello = {
    let entry = slab.vacant_entry();
    let key = entry.key();

    entry.insert((key, "hello"));
    key
};

assert_eq!(hello, slab[hello].0);
assert_eq!("hello", slab[hello].1);
source

pub(crate) fn insert_at(&mut self, key: usize, val: T)

source

pub fn try_remove(&mut self, key: usize) -> Option<T>

Tries to remove the value associated with the given key, returning the value if the key existed.

The key is then released and may be associated with future stored values.

§Examples
let mut slab = Slab::new();

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

assert_eq!(slab.try_remove(hello), Some("hello"));
assert!(!slab.contains(hello));
source

pub fn remove(&mut self, key: usize) -> T

Remove and return the value associated with the given key.

The key is then released and may be associated with future stored values.

§Panics

Panics if key is not associated with a value.

§Examples
let mut slab = Slab::new();

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

assert_eq!(slab.remove(hello), "hello");
assert!(!slab.contains(hello));
source

pub fn contains(&self, key: usize) -> bool

Return true if a value is associated with the given key.

§Examples
let mut slab = Slab::new();

let hello = slab.insert("hello");
assert!(slab.contains(hello));

slab.remove(hello);

assert!(!slab.contains(hello));
source

pub fn retain<F>(&mut self, f: F)
where F: FnMut(usize, &mut T) -> bool,

Retain only the elements specified by the predicate.

In other words, remove all elements e such that f(usize, &mut e) returns false. This method operates in place and preserves the key associated with the retained values.

§Examples
let mut slab = Slab::new();

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

slab.retain(|key, val| key == k1 || *val == 1);

assert!(slab.contains(k1));
assert!(slab.contains(k2));
assert!(!slab.contains(k3));

assert_eq!(2, slab.len());
source

pub fn drain(&mut self) -> Drain<'_, T>

Return a draining iterator that removes all elements from the slab and yields the removed items.

Note: Elements are removed even if the iterator is only partially consumed or not consumed at all.

§Examples
let mut slab = Slab::new();

let _ = slab.insert(0);
let _ = slab.insert(1);
let _ = slab.insert(2);

{
    let mut drain = slab.drain();

    assert_eq!(Some(0), drain.next());
    assert_eq!(Some(1), drain.next());
    assert_eq!(Some(2), drain.next());
    assert_eq!(None, drain.next());
}

assert!(slab.is_empty());

Trait Implementations§

source§

impl<T> Clone for Slab<T>
where T: Clone,

source§

fn clone(&self) -> Self

Returns a copy of the value. Read more
source§

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

Performs copy-assignment from source. Read more
source§

impl<T> Debug for Slab<T>
where T: Debug,

source§

fn fmt(&self, fmt: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
source§

impl<T> Default for Slab<T>

source§

fn default() -> Self

Returns the “default value” for a type. Read more
source§

impl<T> FromIterator<(usize, T)> for Slab<T>

Create a slab from an iterator of key-value pairs.

If the iterator produces duplicate keys, the previous value is replaced with the later one. The keys does not need to be sorted beforehand, and this function always takes O(n) time. Note that the returned slab will use space proportional to the largest key, so don’t use Slab with untrusted keys.

§Examples


let vec = vec![(2,'a'), (6,'b'), (7,'c')];
let slab = vec.into_iter().collect::<Slab<char>>();
assert_eq!(slab.len(), 3);
assert!(slab.capacity() >= 8);
assert_eq!(slab[2], 'a');

With duplicate and unsorted keys:


let vec = vec![(20,'a'), (10,'b'), (11,'c'), (10,'d')];
let slab = vec.into_iter().collect::<Slab<char>>();
assert_eq!(slab.len(), 3);
assert_eq!(slab[10], 'd');
source§

fn from_iter<I>(iterable: I) -> Self
where I: IntoIterator<Item = (usize, T)>,

Creates a value from an iterator. Read more
source§

impl<T> Index<usize> for Slab<T>

source§

type Output = T

The returned type after indexing.
source§

fn index(&self, key: usize) -> &T

Performs the indexing (container[index]) operation. Read more
source§

impl<T> IndexMut<usize> for Slab<T>

source§

fn index_mut(&mut self, key: usize) -> &mut T

Performs the mutable indexing (container[index]) operation. Read more
source§

impl<'a, T> IntoIterator for &'a Slab<T>

source§

type Item = (usize, &'a T)

The type of the elements being iterated over.
source§

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?
source§

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value. Read more
source§

impl<'a, T> IntoIterator for &'a mut Slab<T>

source§

type Item = (usize, &'a mut T)

The type of the elements being iterated over.
source§

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?
source§

fn into_iter(self) -> IterMut<'a, T>

Creates an iterator from a value. Read more
source§

impl<T> IntoIterator for Slab<T>

source§

type Item = (usize, T)

The type of the elements being iterated over.
source§

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?
source§

fn into_iter(self) -> IntoIter<T>

Creates an iterator from a value. Read more

Auto Trait Implementations§

§

impl<T> Freeze for Slab<T>

§

impl<T> RefUnwindSafe for Slab<T>
where T: RefUnwindSafe,

§

impl<T> Send for Slab<T>
where T: Send,

§

impl<T> Sync for Slab<T>
where T: Sync,

§

impl<T> Unpin for Slab<T>
where T: Unpin,

§

impl<T> UnwindSafe for Slab<T>
where T: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> CloneToUninit for T
where T: Clone,

source§

unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for T
where T: Clone,

source§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

source§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.