pub struct LocklessSlotmap<T, R>{ /* private fields */ }Expand description
LocklessSlotmap is a lockless implementation of a slotmap.
A slotmap is a data structure that allows for stable references to elements while providing fast insertion (in O(1) time) and removal (in O(1) time).
This implementation is (mostly) lockless, meaning that it can be used in a high performance environment where locks are not desired. The only place where locks are used is when the slotmap becomes saturated and a new block needs to be allocated. Because of the ever-growing exponential size of the blocks, this should be a rare occurrence.
§Limitations
Each slot in the slotmap can only be reused so many times. 16-bit generation numbers are kept as guard against ABA problems, this means that each slot can only be reused 65536 times (after which the slot is considered “dead” and will not be reused which can lead to slowly increasing memory usage). Therefore for very long running applications with high insertion and removal rates, this implementation may not be suitable.
§Implementation
Internally, the slotmap is divided into blocks, each block containing a fixed number of elements. When the slotmap is saturated, a new block is allocated without invalidating all the already existing blocks. This allows for fast insertion and removal of elements.
Blocks grow exponentially in size, starting at 64 elements (default) and
growing up to a maximum of MAX_ELEMENTS_PER_BLOCK elements.
§Note
In the current implementation, the insertion of new elements takes the place of the most recently removed element. At high loads this behavior can lead to excessive memory fragmentation. This behavior may be changed in the future.
Implementations§
Source§impl<T, R> LocklessSlotmap<T, R>
impl<T, R> LocklessSlotmap<T, R>
Sourcepub fn with_capacity(capacity: usize) -> Self
pub fn with_capacity(capacity: usize) -> Self
Creates a new slotmap with the specified capacity.
§Arguments
capacity- The capacity (number of elements) of the slotmap. This capacity is limited toMAX_ELEMENTS_PER_BLOCKelements. However, this limit should allow for a slotmap with a capacity of up to 2^32 elements.
§Returns
A new slotmap with the specified capacity.
§Panics
Panics if the capacity is greater than MAX_ELEMENTS_PER_BLOCK.
Sourcepub fn insert(&self, value: T) -> SlotmapTicket
pub fn insert(&self, value: T) -> SlotmapTicket
Inserts a new element into the slotmap.
Atomically inserts a new element into the slotmap. The element is stored in the slotmap and a ticket is returned that can be used to access the element.
§Arguments
value- The value to insert into the slotmap.
§Returns
A ticket that can be used to access the element in the slotmap. The value of the ticket
can then be accessed using the LocklessSlotmap::get method.
Sourcepub fn get(&self, ticket: SlotmapTicket) -> Option<SlotmapEntry<'_, T>>
pub fn get(&self, ticket: SlotmapTicket) -> Option<SlotmapEntry<'_, T>>
Get an element from the slotmap at the specified ticket.
Retrieves the element stored in the slotmap at the specified ticket. The ticket
is invalidated after the element is removed from the slotmap. For more information
you can refer to the SlotmapEntry structure.
§Arguments
ticket- The ticket of the element in the slotmap. Tickets are invalidated after the element is removed from the slotmap. SeeSlotmapTicketfor more details.
§Returns
An Option<T> containing a SlotmapEntry to the element stored in the slotmap
at the specified ticket. If the ticket is invalid or the element has been removed
Sourcepub fn erase(&self, ticket: SlotmapTicket) -> Option<T>
pub fn erase(&self, ticket: SlotmapTicket) -> Option<T>
Erase an element from the slotmap at the specified ticket.
Removes the element stored in the slotmap at the specified ticket. The ticket is
invalidated after the element is removed from the slotmap. For more information
you can refer to the SlotmapEntry structure.
§Deadlocks
This method will wait for all SlotmapEntry corresponding to the ticket to be
dropped before removing the element from the slotmap. Special care should be taken
to ensure that the thread calling this method is not holding a SlotmapEntry
corresponding to the ticket or a deadlock will occur.
§Arguments
ticket- The ticket of the element in the slotmap. Tickets are invalidated
§Returns
An Option<T> containing the element stored in the slotmap at the specified ticket or
Option::None if the ticket is invalid or the element has already been removed.
Sourcepub fn capacity(&self) -> usize
pub fn capacity(&self) -> usize
Get the maximum number of elements that can be stored in the slotmap.
§Returns
The maximum number of elements that can be stored in the slotmap.
Sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Get the number of elements stored in the slotmap.
Notice that in a multithreaded environment, the number of elements stored in the slotmap can change between the time this method is called and the time the result is used, therefore this method should be used as an approximation.
§Returns
The number of elements stored in the slotmap.
Sourcepub fn generation_limit_reached(&self) -> usize
pub fn generation_limit_reached(&self) -> usize
Number of times the generation limit has been reached.
As discussed in the limitations of the LocklessSlotmap structure, each slot can only
be reused so many times (2^16 times). When the generation limit is reached, the slot is
considered “dead” and will not be reused. This method returns the number of times dead
slots have been encountered.
Notice that in a multithreaded environment, the number of times the generation limit has been reached can change between the time this method is called and the time the result is used, therefore this method should be used as an approximation.
§Returns
The number of times the generation limit has been reached.