High-performance associative container. More...

#include <slotmap.hpp>

Classes
class	ConstSlotMapIterator
	Const iterator type for the `SlotMap`. More...

struct	Slot
	Internal data structure for slots. More...

class	SlotMapIterator
	Iterator type for the `SlotMap`. More...

Public Types
using	KeyType = Key

using	ValueType = V

Public Member Functions
	SlotMap ()
	Construct `SlotMap` with initial capacity zero. More...

SlotMapIterator	begin ()

ConstSlotMapIterator	begin () const

std::size_t	bytes () const

Index	capacity () const
	Retrieve current capacity of the `SlotMap`. More...

bool	contains_key (const Key &key) const
	Check if given key is still valid. More...

V *	data ()

const V *	data () const

SlotMapIterator	end ()

ConstSlotMapIterator	end () const

void	erase (const Key &key)
	Remove a key from the `SlotMap`. More...

Key	insert (const V &value)
	Insert a value into the `SlotMap`. More...

Key	insert (V &&value)
	Insert `value` into the `SlotMap`. More...

V &	operator[] (const Key &key)
	Access Operator. More...

const V &	operator[] (const Key &key) const
	Access Operator. More...

Key	replace (Key &key, V &&value)
	Replace the value stored at `key` with `value`. More...

Key	replace (Key &key, V &value)
	Replace the value stored at `key` with `value`. More...

void	reserve (Index capacity)
	Reserve at least `capacity` space in the `SlotMap`. More...

Index	size () const
	Retrieve current size of the `SlotMap`. More...

Private Member Functions
Slot &	try_get_slot (const Key &key)
	Helper method to retrieve a slot. More...

const Slot &	try_get_slot (const Key &key) const

Private Attributes
std::vector< V >	_data

std::vector< std::uint32_t >	_erase

std::vector< Slot >	_slots

struct {
std::uint32_t head

std::uint32_t tail

}	freelist

Detailed Description

template<typename V, typename Key = SlotMapKey>
class FEAT::Util::SlotMap< V, Key >

High-performance associative container.

Template Parameters

V	Type of value to be stored.
Key	Type of keys returned by this SlotMap. SlotMapKey by default.

A SlotMap is a high-performance associative container. It:

allows for O(1) insertion, deletion, lookup
stores its elements densely
avoids the ABA problem, i.e. the user can notice that data stored at a key has changed

To do so it hands out its own keys, instead of letting the user provide a key like a traditional hashmap would do. Keys consist of an index into the SlotMap used to access elements, and a generation used to detect if the slot has been reused since the key has been issued.

Implementation

The implementation consists of three dynamic arrays (std::vectors) called slots, data, erase, as well as head and tail indices for a list of free slots.

The data array is where the inserted elements are stored.

The slots array provides the indirection required to keep keys stable while guaranteeing to store the elements densely. Each entry in the slots array consists of an index and a generation. The generation indicates how often this slot has been reused. This is what allows detecting if an old key is used to access new data. The index either points into the data array (if the slot is currently occupied) or to the next free slot (if the slot is currently not occupied). The keys given out by the SlotMap point towards slots. This way elements in the data array can be shifted around and only indices in the slots array need to be fixed, while the keys stay valid.

The erase array contains the index of the slot pointing towards itself (and the associated element in the data array). In short slots[erase[i]].index == i. It is used to quickly find affected slots during deletion of a key, allowing O(1) deletions.

The freelist tracks the start and end of the linked list of unoccupied slots established. As an invariant the SlotMap always keeps at least one Slot unoccupied to guarantee that freelist.head and freelist.tail point towards a valid slot. Note that keeping track of the tail is not strictly required. A stack of unoccupied slots could be used instead, but using a list increments the slots generations more evenly.

Inserting a new value works as follows

Retrieve the next unoccupied slot from the freelist
Advance the freelist head or push a new slot to maintain freelist invariant
Point retrieved slot to new element
Push value into data array
Push slot index into erase array
Return key pointing to retrieved slot to user. Keys generation matches that of the slot.

Deleting a value works as follows

Retrieve the slot for the given key, if the key is valid
Increment the slots generation. This invalidates all prior keys.
Delete the data and erase entries the slot is pointing to
Move the back elements of data and erase into the now free positions
Fix the slot pointing to the previously last element using the erase array
Add the now unoccupied slot to the back of the freelist

See https://www.youtube.com/watch?v=SHaAR7XPtNU for more details.

Custom Keys

The SlotMap returns keys of type SlotMapKey per default. For more type safety when using multiple SlotMaps simultaneously a custom key type can be provided as a second template argument.

A valid key type requires a constructor accepting the index and the generation in that order, a public member index and a public member generation.

Author: Markus Muegge

Definition at line 148 of file slotmap.hpp.

Member Typedef Documentation

◆ KeyType

template<typename V , typename Key = SlotMapKey>

using FEAT::Util::SlotMap< V, Key >::KeyType = Key

Definition at line 152 of file slotmap.hpp.

◆ ValueType

template<typename V , typename Key = SlotMapKey>

using FEAT::Util::SlotMap< V, Key >::ValueType = V

Definition at line 151 of file slotmap.hpp.

Constructor & Destructor Documentation

◆ SlotMap()

template<typename V , typename Key = SlotMapKey>

FEAT::Util::SlotMap< V, Key >::SlotMap ( )

inline

Construct SlotMap with initial capacity zero.

Definition at line 157 of file slotmap.hpp.

Member Function Documentation

◆ begin() [1/2]

template<typename V , typename Key = SlotMapKey>

SlotMapIterator FEAT::Util::SlotMap< V, Key >::begin ( )

inline

Definition at line 498 of file slotmap.hpp.

◆ begin() [2/2]

template<typename V , typename Key = SlotMapKey>

ConstSlotMapIterator FEAT::Util::SlotMap< V, Key >::begin ( ) const

inline

Definition at line 508 of file slotmap.hpp.

◆ bytes()

template<typename V , typename Key = SlotMapKey>

std::size_t FEAT::Util::SlotMap< V, Key >::bytes ( ) const

inline

Definition at line 399 of file slotmap.hpp.

◆ capacity()

template<typename V , typename Key = SlotMapKey>

Index FEAT::Util::SlotMap< V, Key >::capacity ( ) const

inline

Retrieve current capacity of the SlotMap.

Returns: Capacity of the SlotMap

Definition at line 374 of file slotmap.hpp.

Referenced by FEAT::Util::SlotMap< V, Key >::reserve().

◆ contains_key()

template<typename V , typename Key = SlotMapKey>

bool FEAT::Util::SlotMap< V, Key >::contains_key ( const Key & key ) const

inline

Check if given key is still valid.

Parameters

[in] key The key to check.

Returns: true if the key is valid, false otherwise.

A key is valid if it points to an existing slot and matches that slots generation.

Definition at line 322 of file slotmap.hpp.

Referenced by FEAT::Util::SlotMap< V, Key >::erase().

◆ data() [1/2]

template<typename V , typename Key = SlotMapKey>

V * FEAT::Util::SlotMap< V, Key >::data ( )

inline

Definition at line 389 of file slotmap.hpp.

◆ data() [2/2]

template<typename V , typename Key = SlotMapKey>

const V * FEAT::Util::SlotMap< V, Key >::data ( ) const

inline

Definition at line 394 of file slotmap.hpp.

◆ end() [1/2]

template<typename V , typename Key = SlotMapKey>

SlotMapIterator FEAT::Util::SlotMap< V, Key >::end ( )

inline

Definition at line 503 of file slotmap.hpp.

◆ end() [2/2]

template<typename V , typename Key = SlotMapKey>

ConstSlotMapIterator FEAT::Util::SlotMap< V, Key >::end ( ) const

inline

Definition at line 513 of file slotmap.hpp.

◆ erase()

template<typename V , typename Key = SlotMapKey>

void FEAT::Util::SlotMap< V, Key >::erase ( const Key & key )

inline

Remove a key from the SlotMap.

Will invalidate all further uses of the key.

Parameters

[in] key The key to remove

Definition at line 249 of file slotmap.hpp.

References FEAT::Util::SlotMap< V, Key >::contains_key(), and FEAT::Util::SlotMap< V, Key >::try_get_slot().

Referenced by FEAT::Geometry::Intern::MeshLayer< TemplateSet_, MeshShape_, VertexType_, 0 >::erase(), and FEAT::Util::SlotMap< V, Key >::replace().

◆ insert() [1/2]

template<typename V , typename Key = SlotMapKey>

Key FEAT::Util::SlotMap< V, Key >::insert ( const V & value )

inline

Insert a value into the SlotMap.

Parameters

[in] value The value to be inserted.

Returns: A key pointing to the stored value.

Definition at line 211 of file slotmap.hpp.

References FEAT::value.

◆ insert() [2/2]

template<typename V , typename Key = SlotMapKey>

Key FEAT::Util::SlotMap< V, Key >::insert ( V && value )

inline

Insert value into the SlotMap.

Parameters

[in] value The value to be inserted.

Returns: A key pointing to the stored value.

Definition at line 171 of file slotmap.hpp.

References FEAT::value.

Referenced by FEAT::Geometry::Intern::MeshLayer< TemplateSet_, MeshShape_, VertexType_, 0 >::insert_vertex(), and FEAT::Util::SlotMap< V, Key >::replace().

◆ operator[]() [1/2]

template<typename V , typename Key = SlotMapKey>

V & FEAT::Util::SlotMap< V, Key >::operator[] ( const Key & key )

inline

Access Operator.

Parameters

[in] key The key to retrieve

Returns: A reference to the data pointed to by the key

Aborts if the given key is not valid.

Definition at line 350 of file slotmap.hpp.

References ASSERTM, and FEAT::Util::SlotMap< V, Key >::try_get_slot().

◆ operator[]() [2/2]

template<typename V , typename Key = SlotMapKey>

const V & FEAT::Util::SlotMap< V, Key >::operator[] ( const Key & key ) const

inline

Access Operator.

Parameters

[in] key The key to retrieve

Returns: A reference to the data pointed to by the key

Aborts if the given key is not valid.

Definition at line 335 of file slotmap.hpp.

References ASSERTM, and FEAT::Util::SlotMap< V, Key >::try_get_slot().

◆ replace() [1/2]

template<typename V , typename Key = SlotMapKey>

Key FEAT::Util::SlotMap< V, Key >::replace	(	Key &	key,
		V &&	value
	)

inline

Replace the value stored at key with value.

Parameters

[in]	key	The key to replace
[in]	value	The new value to store

Returns: The key of the new value

Shortcut to erasing a key and then inserting a new value. The new value is not guaranteed to be stored at the same memory location as the previous one.

Definition at line 291 of file slotmap.hpp.

References FEAT::Util::SlotMap< V, Key >::erase(), FEAT::Util::SlotMap< V, Key >::insert(), and FEAT::value.

◆ replace() [2/2]

template<typename V , typename Key = SlotMapKey>

Key FEAT::Util::SlotMap< V, Key >::replace	(	Key &	key,
		V &	value
	)

inline

Replace the value stored at key with value.

Parameters

[in]	key	The key to replace
[in]	value	The new value to store

Returns: The key of the new value

Shortcut to erasing a key and then inserting a new value. The new value is not guaranteed to be stored at the same memory location as the previous one.

Definition at line 308 of file slotmap.hpp.

References FEAT::Util::SlotMap< V, Key >::erase(), FEAT::Util::SlotMap< V, Key >::insert(), and FEAT::value.

◆ reserve()

template<typename V , typename Key = SlotMapKey>

void FEAT::Util::SlotMap< V, Key >::reserve ( Index capacity )

inline

Reserve at least capacity space in the SlotMap.

Parameters

[in] capacity Minimum capacity

Definition at line 362 of file slotmap.hpp.

References FEAT::Util::SlotMap< V, Key >::capacity().

◆ size()

template<typename V , typename Key = SlotMapKey>

Index FEAT::Util::SlotMap< V, Key >::size ( ) const

inline

Retrieve current size of the SlotMap.

Returns: Size of the SlotMap

Definition at line 384 of file slotmap.hpp.

Referenced by FEAT::Geometry::Intern::MeshLayer< TemplateSet_, MeshShape_, VertexType_, 0 >::num_vertices().

◆ try_get_slot() [1/2]

template<typename V , typename Key = SlotMapKey>

Slot & FEAT::Util::SlotMap< V, Key >::try_get_slot ( const Key & key )

inlineprivate

Helper method to retrieve a slot.

Parameters

[in] key Key

Returns: Slot pointed to by key

Aborts if given key is not valid, returns reference to slot otherwise.

Definition at line 543 of file slotmap.hpp.

References ASSERTM.

Referenced by FEAT::Util::SlotMap< V, Key >::erase(), and FEAT::Util::SlotMap< V, Key >::operator[]().

◆ try_get_slot() [2/2]

template<typename V , typename Key = SlotMapKey>

const Slot & FEAT::Util::SlotMap< V, Key >::try_get_slot ( const Key & key ) const

inlineprivate

Definition at line 551 of file slotmap.hpp.

Member Data Documentation

◆ _data

template<typename V , typename Key = SlotMapKey>

std::vector<V> FEAT::Util::SlotMap< V, Key >::_data

private

Definition at line 566 of file slotmap.hpp.

◆ _erase

template<typename V , typename Key = SlotMapKey>

std::vector<std::uint32_t> FEAT::Util::SlotMap< V, Key >::_erase

private

Definition at line 567 of file slotmap.hpp.

◆ _slots

template<typename V , typename Key = SlotMapKey>

std::vector<Slot> FEAT::Util::SlotMap< V, Key >::_slots

private

Definition at line 565 of file slotmap.hpp.

◆ head

template<typename V , typename Key = SlotMapKey>

std::uint32_t FEAT::Util::SlotMap< V, Key >::head

Definition at line 561 of file slotmap.hpp.

◆ tail

template<typename V , typename Key = SlotMapKey>

std::uint32_t FEAT::Util::SlotMap< V, Key >::tail

Definition at line 562 of file slotmap.hpp.

The documentation for this class was generated from the following file:

kernel/util/slotmap.hpp

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Implementation

Custom Keys

Member Typedef Documentation

◆ KeyType

◆ ValueType

Constructor & Destructor Documentation

◆ SlotMap()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ bytes()

◆ capacity()

◆ contains_key()

◆ data() [1/2]

◆ data() [2/2]

◆ end() [1/2]

◆ end() [2/2]

◆ erase()

◆ insert() [1/2]

◆ insert() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ replace() [1/2]

◆ replace() [2/2]

◆ reserve()

◆ size()

◆ try_get_slot() [1/2]

◆ try_get_slot() [2/2]

Member Data Documentation

◆ _data

◆ _erase

◆ _slots

◆ head

◆ tail