Template Class atomic_sparse_map

Class Documentation

template<typename key_type, typename value_type, template<typename...> typename dense_type = std::vector, template<typename...> typename sparse_type = std::unordered_map>
class legion::core::atomic_sparse_map

Atomic quick lookup contiguous map. A specialized version of sparse_map that uses legion::core::async::transferable_atomic and legion::core::async::rw_spinlock.

Note

With default container parameters iterators may be invalidated upon resize. See reference of std::vector.

Note

Removing item might invalidate the iterator of the last item in the dense container.

Template Parameters

  • key_type: The type to be used as the key.

  • value_type: The type to be used as the value.

  • dense_type: Container to be used to store the values.

  • sparse_type: Container to be used to store the keys.

Public Types

using self_type = atomic_sparse_map<key_type, value_type, dense_type, sparse_type>
using self_reference = self_type&
using self_const_reference = const self_type&
using key_reference = key_type&
using key_const_reference = const key_type&
using key_pointer = key_type*
using value_reference = value_type&
using value_const_reference = const value_type&
using value_pointer = value_type*
using sparse_container = sparse_type<key_type, size_type>
using dense_value_container = dense_type<value_type>
using dense_key_container = dense_type<key_type>
using iterator = core::key_value_pair_iterator<typename dense_key_container::iterator, typename dense_value_container::iterator>
using const_iterator = core::key_value_pair_iterator<typename dense_key_container::const_iterator, typename dense_value_container::const_iterator>

Public Functions

inline async::rw_spinlock &get_lock() const
inline dense_value_container &values()
inline const dense_value_container &values() const
inline dense_key_container &keys()
inline const dense_key_container &keys() const
inline iterator begin()
inline const_iterator begin() const
inline const_iterator cbegin() const
inline iterator end()
inline const_iterator end() const
inline const_iterator cend() const
inline size_type size(std::memory_order order = std::memory_order_acquire) const noexcept

Returns the amount of items in the sparse_map.

Return

size_type Current amount of items contained in sparse_map.

inline size_type capacity(std::memory_order order = std::memory_order_acquire) const noexcept

Returns the capacity of items the sparse_map could at least store without invalidating the iterators.

Return

size_type Current capacity of the dense container.

inline size_type max_size() const noexcept

Returns the maximum number of items the atomic_sparse_map could at most store without crashing.

Note

This value typically reflects the theoretical limit on the size of the container, at most std::numeric_limits<difference_type>::max(). At runtime, the size of the container may be limited to a value smaller than max_size() by the amount of RAM available.

Return

size_type

inline bool empty(std::memory_order order = std::memory_order_acquire) const noexcept

Returns whether the sparse_map is empty.

Return

bool True if the sparse_map is empty, otherwise false.

inline void clear(std::memory_order order = std::memory_order_release) noexcept

Clears sparse_map.

Note

Will not update capacity.

inline void reserve(size_type size, std::memory_order loadOrder = std::memory_order_acquire, std::memory_order storeOrder = std::memory_order_release)

Reserves space in dense container for more items.

Note

Will update capacity if resize happened.

Parameters

  • size: Amount of items to reserve space for (would be the new capacity).

inline size_type count(key_const_reference key) const

Returns the amount of items linked to a certain key.

Return

size_type Amount of items linked to the key (either 0 or 1).

Note

Function is only available for compatibility reasons, it is advised to use contains instead. legion::core::sparse_map::contains

Parameters

  • key: Key to look for.

inline size_type count(key_type &&key) const

Returns the amount of items linked to a certain key.

Return

size_type Amount of items linked to the key (either 0 or 1).

Note

Function is only available for compatibility reasons, it is advised to use contains instead. legion::core::sparse_map::contains

Parameters

  • key: Key to look for.

inline bool contains(key_const_reference key)

Checks whether a certain key is contained in the sparse_map.

Return

bool true if the key was found, otherwise false.

Parameters

  • key: Key to check for.

inline bool contains(key_type &&key)

Checks whether a certain key is contained in the sparse_map.

Return

bool true if the key was found, otherwise false.

Parameters

  • key: Key to check for.

inline bool contains(key_const_reference key) const

Checks whether a certain key is contained in the sparse_map.

Return

bool true if the key was found, otherwise false.

Parameters

  • key: Key to check for.

inline bool contains(key_type &&key) const

Checks whether a certain key is contained in the sparse_map.

Return

bool true if the key was found, otherwise false.

Parameters

  • key: Key to check for.

inline iterator find(value_const_reference val)

Finds the iterator of a value using std::find.

Return

Iterator to the value if found, otherwise end.

Parameters

  • val: Value to find.

inline const_iterator find(value_const_reference val) const

Finds the iterator of a value using std::find.

Return

Iterator to the value if found, otherwise end.

Parameters

  • val: Value to find.

inline std::pair<iterator, bool> insert(key_const_reference key, value_const_reference val, std::memory_order incrementOrder = std::memory_order_acq_rel)

Inserts new item into sparse_map.

Return

std::pair<iterator, bool> Iterator at the location of the key and true if succeeded, end and false if it didn’t succeed.

Parameters

  • key: Key to insert the new item to.

  • val: Value to insert and link to the key.

inline std::pair<iterator, bool> insert(key_type &&key, value_const_reference val, std::memory_order incrementOrder = std::memory_order_acq_rel)

Inserts new item into sparse_map.

Return

std::pair<iterator, bool> Iterator at the location of the key and true if succeeded, end and false if it didn’t succeed.

Parameters

  • key: Key to insert the new item to.

  • val: Value to insert and link to the key.

inline std::pair<iterator, bool> insert(key_const_reference key, value_type &&val, std::memory_order incrementOrder = std::memory_order_acq_rel)

Inserts new item into sparse_map.

Return

std::pair<iterator, bool> Iterator at the location of the key and true if succeeded, end and false if it didn’t succeed.

Parameters

  • key: Key to insert the new item to.

  • val: Value to insert and link to the key.

inline std::pair<iterator, bool> insert(key_type &&key, value_type &&val, std::memory_order incrementOrder = std::memory_order_acq_rel)

Inserts new item into sparse_map.

Return

std::pair<iterator, bool> Iterator at the location of the key and true if succeeded, end and false if it didn’t succeed.

Parameters

  • key: Key to insert the new item to.

  • val: Value to insert and link to the key.

template<typename ...Arguments>
inline std::pair<iterator, bool> emplace(key_const_reference key, std::memory_order incrementOrder, Arguments&&... arguments)

Construct item in place.

Parameters

  • key: Key to which the item should be created.

  • incrementOrer: Memory order for incrementing the size.

  • arguments: Arguments to pass to the item constructor.

template<typename ...Arguments>
inline std::pair<iterator, bool> emplace(key_type &&key, std::memory_order incrementOrder, Arguments&&... arguments)

Construct item in place.

Parameters

  • key: Key to which the item should be created.

  • incrementOrer: Memory order for incrementing the size.

  • arguments: Arguments to pass to the item constructor.

template<typename ...Arguments>
inline std::pair<iterator, bool> emplace(key_const_reference key, Arguments&&... arguments)

Construct item in place.

Parameters

  • key: Key to which the item should be created.

  • arguments: Arguments to pass to the item constructor.

template<typename ...Arguments>
inline std::pair<iterator, bool> emplace(key_type &&key, Arguments&&... arguments)

Construct item in place.

Parameters

  • key: Key to which the item should be created.

  • arguments: Arguments to pass to the item constructor.

inline value_reference operator[](key_type &&key)

Thread unsafe retrieve item from sparse_map, inserts default value if it doesn’t exist yet.

Parameters

  • key: Key value that needs to be retrieved.

inline value_reference operator[](key_const_reference key)

Thread unsafe retrieve item from sparse_map, inserts default value if it doesn’t exist yet.

Parameters

  • key: Key value that needs to be retrieved.

inline value_const_reference operator[](key_type &&key) const

Thread unsafe retrieve const item from const sparse_map.

Parameters

  • key: Key value that needs to be retrieved.

inline value_const_reference operator[](key_const_reference key) const

Thread unsafe retrieve const item from const sparse_map.

Parameters

  • key: Key value that needs to be retrieved.

inline value_type get(key_type &&key)

Returns item from sparse_map, throws exception if it doesn’t exist yet.

Parameters

  • key: Key value that needs to be retrieved.

inline value_type get(key_const_reference key)

Returns item from sparse_map, throws exception if it doesn’t exist yet.

Parameters

  • key: Key value that needs to be retrieved.

inline value_type get(key_type &&key) const

Returns const item from const sparse_map.

Parameters

  • key: Key value that needs to be retrieved.

inline value_type get(key_const_reference key) const

Returns const item from const sparse_map.

Parameters

  • key: Key value that needs to be retrieved.

inline void set(key_type &&key, value_const_reference val)

Sets item in sparse_map, throws exception if it doesn’t exist yet.

Parameters

  • key: Key of value that needs to be set.

  • val: New value for the item that needs to be set.

inline void set(key_const_reference key, value_const_reference val)

Sets item in sparse_map, throws exception if it doesn’t exist yet.

Parameters

  • key: Key of value that needs to be set.

  • val: New value for the item that needs to be set.

inline void set(key_type &&key, value_type &&val)

Sets item in sparse_map, throws exception if it doesn’t exist yet.

Parameters

  • key: Key of value that needs to be set.

  • val: New value for the item that needs to be set.

inline void set(key_const_reference key, value_type &&val)

Sets item in sparse_map, throws exception if it doesn’t exist yet.

Parameters

  • key: Key of value that needs to be set.

  • val: New value for the item that needs to be set.

inline size_type erase(key_const_reference key)

Erases item from sparse_map.

Return

size_type Number of items removed from the map.

Parameters

  • key: Key value that needs to be erased.