Provides a hashmap implementation, relying upon chaining to resolve hash collisions. Simple hashmap for now, future work will use RAJA and Umpire to allow use of map within kernels. Resembles unordered_map, which we can't use due to a lack of host-device decoration. More...

#include </home/docs/checkouts/readthedocs.org/user_builds/axom/checkouts/latest/src/axom/core/Map.hpp>

Public Types
using	key_type = Key

using	mapped_type = T

Public Member Functions
Map &	operator= (Map &&other) noexcept
	Move assignment for Map. More...

	~Map ()

Map Constructors
	Map (IndexType num_buckets, IndexType bucket_len=10)
	Constructs a Map instance with the given number of buckets. More...

	Map (Map &&other) noexcept
	Move constructor for Map. More...

Map Methods
bool	rehash (IndexType buckets=-1, int factor=-1)
	Resizes Map by creating new Map instance and inserting all values from original Map. More...

void	clear ()
	Deallocates memory resources for this Map instance, resets state as if constructed with 0 elements. Also used in destructor. Once this is used, insert will not function properly until init() is used, because there is no memory available for elements to be inserted. More...

void	init (IndexType num_buckets, IndexType bucket_len=10)
	Initializes this Map instance, mostly in case clear() was used and there's a desire to continue use. Required if use is to continue after a clear(). More...

axom_map::Pair< Key, T >	insert (const Key &key, const T &val)
	Inserts given key-value pair into the Map instance. More...

axom_map::Pair< Key, T >	insert_or_assign (const Key &key, const T &val)
	Inserts given key-value pair into the Map instance, or updates value of existing key-value pair if item with supplied key already exists. More...

const T &	operator[] (const Key &key) const
	Finds reference to value of key-value pair mapped to supplied pair, returns value from sentinel node if fails, meaning value at reference will be data type T initialized with 0. More...

bool	erase (const Key &key)
	Removes key-value pair with given key from the Map instance. More...

axom_map::Node< Key, T > &	find (const Key &key) const
	Returns key-value pair with given key from the Map instance. More...

std::size_t	bucket (Key key) const
	Returns id of bucket associated with a 64-bit integer, intended to be the hash of a key. More...

IndexType	bucket_size () const
	Returns the maximum number of items per bucket. More...

IndexType	bucket_count () const
	Returns the number of buckets in the Map. More...

IndexType	size () const
	Returns the amount of items in the Map instance. More...

IndexType	max_size ()
	Returns the overall capacity of the Map instance. More...

bool	empty () const
	Checks if the container has no elements. More...

const axom_map::Node< Key, T > &	end () const
	Returns const reference to "end" node, for comparison to check return results of other Map functions. More...

float	max_load_factor () const
	Returns maximum load factor (ratio between size and bucket count) hash table will reach before check_rehash() returns true. More...

void	max_load_factor (float load_factor)
	Sets maximum load factor (ratio between size and bucket count) hash table will reach before check_rehash returns true. Default value is 1.0. More...

float	load_factor () const
	Returns current load factor (ratio between size and bucket count). More...

bool	check_rehash () const
	Returns whether a rehash is necessary for this Map instance. Does so based on two metrics. The first is whether the load factor of the map (ratio between size and bucket count) has exceeded its maximum load factor (default 1.0). The second is whether any of the buckets are currently full. More...

Detailed Description

template<typename Key, typename T, typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>
class axom::experimental::Map< Key, T, Hash, Policy >

Provides a hashmap implementation, relying upon chaining to resolve hash collisions. Simple hashmap for now, future work will use RAJA and Umpire to allow use of map within kernels. Resembles unordered_map, which we can't use due to a lack of host-device decoration.

Template Parameters

Key	the type of keys. Must allow equality comparison, must be copyable.
T	the type of values to hold, must be copyable.
Hash	functor that takes an object of Key type and returns a hashed value of size_t (for now)

Member Typedef Documentation

◆ key_type

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

using axom::experimental::Map< Key, T, Hash, Policy >::key_type = Key

◆ mapped_type

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

using axom::experimental::Map< Key, T, Hash, Policy >::mapped_type = T

Constructor & Destructor Documentation

◆ Map() [1/2]

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

axom::experimental::Map< Key, T, Hash, Policy >::Map	(	IndexType	num_buckets,
		IndexType	bucket_len = `10`
	)

inline

Constructs a Map instance with the given number of buckets.

Parameters

[in]	num_buckets	the number of buckets used in the Map.
[in]	bucket_len	the maximum number of items that can co-exist in a bucket.

Precondition: num_buckets > 0; bucket_len > 0

References axom::experimental::Map< Key, T, Hash, Policy >::init().

◆ Map() [2/2]

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

axom::experimental::Map< Key, T, Hash, Policy >::Map ( Map< Key, T, Hash, Policy > && other )

inlinenoexcept

Move constructor for Map.

Parameters

[in] other The Map to move from

◆ ~Map()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

axom::experimental::Map< Key, T, Hash, Policy >::~Map ( )

inline

Destructor. Frees associated buffers.

References axom::experimental::Map< Key, T, Hash, Policy >::clear().

Member Function Documentation

◆ operator=()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

Map& axom::experimental::Map< Key, T, Hash, Policy >::operator= ( Map< Key, T, Hash, Policy > && other )

inlinenoexcept

Move assignment for Map.

Parameters

[in] other The Map to move from

References axom::experimental::Map< Key, T, Hash, Policy >::clear().

◆ rehash()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

bool axom::experimental::Map< Key, T, Hash, Policy >::rehash	(	IndexType	buckets = `-1`,
		int	factor = `-1`
	)

inline

Resizes Map by creating new Map instance and inserting all values from original Map.

Parameters

[in]	buckets	user-specified number of buckets in new Map. -1 to fall back to multiplicative factor.
[in]	factor	user-specified multiplicative factor to determine size of new Map based upon current size. -1 to fall back to default – would be more efficient to specify neither input.

Returns: true if the hash table is now in a safe state, false otherwise

Note: if neither input is specified, the new Map will be of size 2*old Map size.; both map instances exist in memory until rehash returns. Risks running out of memory.; Rehash should generally ensure a previously filled bucket is no longer filled, and the load_factor is correct, if used properly. However, since this highly manual process has room for error this implementation does perform a check for if any bucket is now full.

References axom::experimental::Map< Key, T, Hash, Policy >::check_rehash(), axom::deallocate(), and axom::experimental::axom_map::Bucket< Key, T >::insert_no_update().

◆ clear()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

void axom::experimental::Map< Key, T, Hash, Policy >::clear ( )

inline

Deallocates memory resources for this Map instance, resets state as if constructed with 0 elements. Also used in destructor. Once this is used, insert will not function properly until init() is used, because there is no memory available for elements to be inserted.

References axom::deallocate().

◆ init()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

void axom::experimental::Map< Key, T, Hash, Policy >::init	(	IndexType	num_buckets,
		IndexType	bucket_len = `10`
	)

inline

Initializes this Map instance, mostly in case clear() was used and there's a desire to continue use. Required if use is to continue after a clear().

◆ insert()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

axom_map::Pair<Key, T> axom::experimental::Map< Key, T, Hash, Policy >::insert	(	const Key &	key,
		const T &	val
	)

inline

Inserts given key-value pair into the Map instance.

Parameters

[in]	key	the key used to index into the Map to store this item
[in]	val	the data value of the pair to insert into the map

Note: Deviation from STL unordered_map is that insertion fails when map full, rather than automatically rehashing. Manual call of rehash() required.; Can set "full bucket" flag for Map, which is only unset by rehashing.

Returns: A pair whose first element is a pointer to the inserted item and bool set to true if successful. Otherwise, the second element is set to false, and the first to one of two values: a sentinel node if the map is overfilled, and the actual node with the given key if an item with given key already exists.

References axom::experimental::Map< Key, T, Hash, Policy >::bucket(), axom::experimental::axom_map::Bucket< Key, T >::get_capacity(), axom::experimental::axom_map::Bucket< Key, T >::get_size(), axom::experimental::axom_map::Bucket< Key, T >::insert_no_update(), and axom::experimental::axom_map::Pair< Key, T >::second.

◆ insert_or_assign()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

axom_map::Pair<Key, T> axom::experimental::Map< Key, T, Hash, Policy >::insert_or_assign	(	const Key &	key,
		const T &	val
	)

inline

Inserts given key-value pair into the Map instance, or updates value of existing key-value pair if item with supplied key already exists.

Parameters

[in]	key	the key used to index into the Map to store this item
[in]	val	the data value of the pair to insert into the map

Note: Deviation from STL unordered_map is that insertion fails when map full, rather than automatically rehashing. Manual call of rehash() required.; Can set "full bucket" flag for Map, which is only unset by rehashing.

Returns: A pair whose first element is a pointer to the inserted item and bool set to true if insertion was performed. Otherwise, the second element is set to false, and the first to one of two values: a sentinel node if the map is overfilled, and the actual node with the given key if an assignment occured.

References axom::experimental::Map< Key, T, Hash, Policy >::bucket(), axom::experimental::axom_map::Bucket< Key, T >::get_capacity(), axom::experimental::axom_map::Bucket< Key, T >::get_size(), axom::experimental::axom_map::Bucket< Key, T >::insert_update(), and axom::experimental::axom_map::Pair< Key, T >::second.

◆ operator[]()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

const T& axom::experimental::Map< Key, T, Hash, Policy >::operator[] ( const Key & key ) const

inline

Finds reference to value of key-value pair mapped to supplied pair, returns value from sentinel node if fails, meaning value at reference will be data type T initialized with 0.

Parameters

[in] key the key used to index into the Map to find item

Note: Major deviation from STL unordered_map in that this function will not perform insertions, and cannot stand in for insert(), nor can accesses be guaranteed to point to valid data. Also returns a const reference, thus meaning it cannot update existing values. Use insert_or_assign() for such functionality.

Returns: A const reference to the value of key-value pair in the Map instance that is associated with supplied Key.

References axom::experimental::Map< Key, T, Hash, Policy >::find(), and axom::experimental::axom_map::Node< Key, T >::value.

◆ erase()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

bool axom::experimental::Map< Key, T, Hash, Policy >::erase ( const Key & key )

inline

Removes key-value pair with given key from the Map instance.

Parameters

[in] key the key of the item to be removed from the Map instance.

Note: Deviation from STL unordered_map in returning a boolean instead of an iterator to next item in map. Mostly useful on sparing logic when this moves to paralellism, since the bucket boundaries would become inconvenient.

Returns: A bool value of true if the item was successfully removed, false otherwise.

References axom::experimental::Map< Key, T, Hash, Policy >::bucket(), and axom::experimental::axom_map::Bucket< Key, T >::remove().

◆ find()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

axom_map::Node<Key, T>& axom::experimental::Map< Key, T, Hash, Policy >::find ( const Key & key ) const

inline

Returns key-value pair with given key from the Map instance.

Parameters

[in] key the key of the item to be searched for in the Map instance.

Returns: A reference to the requested item if found, sentinel node end otherwise.

References axom::experimental::Map< Key, T, Hash, Policy >::bucket(), and axom::experimental::axom_map::Bucket< Key, T >::find().

◆ bucket()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

std::size_t axom::experimental::Map< Key, T, Hash, Policy >::bucket ( Key key ) const

inline

Returns id of bucket associated with a 64-bit integer, intended to be the hash of a key.

Parameters

[in] hash the id of the bucket to be queried.

Note: Likely better off inlined, included here in case of later changes to hash collision resolution method.

Returns: A pointer to the queried bucket.

◆ bucket_size()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

IndexType axom::experimental::Map< Key, T, Hash, Policy >::bucket_size ( ) const

inline

Returns the maximum number of items per bucket.

Returns: bucket_len the maximum number of items per bucket.

◆ bucket_count()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

IndexType axom::experimental::Map< Key, T, Hash, Policy >::bucket_count ( ) const

inline

Returns the number of buckets in the Map.

Returns: bucket_count

◆ size()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

IndexType axom::experimental::Map< Key, T, Hash, Policy >::size ( ) const

inline

Returns the amount of items in the Map instance.

Returns: size the amount of items in the Map instance.

◆ max_size()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

IndexType axom::experimental::Map< Key, T, Hash, Policy >::max_size ( )

inline

Returns the overall capacity of the Map instance.

Returns: capacity the overall capacity of the Map instance.

◆ empty()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

bool axom::experimental::Map< Key, T, Hash, Policy >::empty ( ) const

inline

Checks if the container has no elements.

Returns: true if the container is empty, false otherwise

◆ end()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

const axom_map::Node<Key, T>& axom::experimental::Map< Key, T, Hash, Policy >::end ( ) const

inline

Returns const reference to "end" node, for comparison to check return results of other Map functions.

Returns: m_end the values of the sentinel node for failure checks

◆ max_load_factor() [1/2]

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

float axom::experimental::Map< Key, T, Hash, Policy >::max_load_factor ( ) const

inline

Returns maximum load factor (ratio between size and bucket count) hash table will reach before check_rehash() returns true.

Returns: max_load_factor maximum load factor desired for this hash table. Default 1.0

◆ max_load_factor() [2/2]

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

void axom::experimental::Map< Key, T, Hash, Policy >::max_load_factor ( float load_factor )

inline

Sets maximum load factor (ratio between size and bucket count) hash table will reach before check_rehash returns true. Default value is 1.0.

Parameters

[in] load_factor desired maximum load factor

References axom::experimental::Map< Key, T, Hash, Policy >::load_factor().

◆ load_factor()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

float axom::experimental::Map< Key, T, Hash, Policy >::load_factor ( ) const

inline

Returns current load factor (ratio between size and bucket count).

Returns: load_factor the ratio between the amount of items in the Map and the amount of buckets.

◆ check_rehash()

template<typename Key , typename T , typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>

bool axom::experimental::Map< Key, T, Hash, Policy >::check_rehash ( ) const

inline

Returns whether a rehash is necessary for this Map instance. Does so based on two metrics. The first is whether the load factor of the map (ratio between size and bucket count) has exceeded its maximum load factor (default 1.0). The second is whether any of the buckets are currently full.

Note: This function does not exist in the STL unordered_map, because it performs automatic rehashes as necessary. To support the portability constraints put on this data structure, the user must regularly call this function to verify whether they need to rehash to maintain performance. Another metric is when an insertion fails and returns end(), but this will yield an answer before such an event.

Returns: true if Map should be rehashed now, false otherwise

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

/home/docs/checkouts/readthedocs.org/user_builds/axom/checkouts/latest/src/axom/core/Map.hpp

Public Types

Public Member Functions

Detailed Description

template<typename Key, typename T, typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC> class axom::experimental::Map< Key, T, Hash, Policy >

Member Typedef Documentation

◆ key_type

◆ mapped_type

Constructor & Destructor Documentation

◆ Map() [1/2]

◆ Map() [2/2]

◆ ~Map()

Member Function Documentation

◆ operator=()

◆ rehash()

◆ clear()

◆ init()

◆ insert()

◆ insert_or_assign()

◆ operator[]()

◆ erase()

◆ find()

◆ bucket()

◆ bucket_size()

◆ bucket_count()

◆ size()

◆ max_size()

◆ empty()

◆ end()

◆ max_load_factor() [1/2]

◆ max_load_factor() [2/2]

◆ load_factor()

◆ check_rehash()

template<typename Key, typename T, typename Hash = std::hash<Key>, typename Policy = axom::SEQ_EXEC>
class axom::experimental::Map< Key, T, Hash, Policy >