Kokkos Core Kernels Package  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
List of all members
Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo > Class Template Reference

Thread-safe, performance-portable lookup table. More...

#include <Kokkos_UnorderedMap.hpp>

Public types and constants

using declared_key_type = Key
 
using key_type = std::remove_const_t< declared_key_type >
 
using const_key_type = std::add_const_t< key_type >
 
using declared_value_type = Value
 
using value_type = std::remove_const_t< declared_value_type >
 
using const_value_type = std::add_const_t< value_type >
 
using device_type = Device
 
using execution_space = typename Device::execution_space
 
using hasher_type = Hasher
 
using equal_to_type = EqualTo
 
using size_type = uint32_t
 
using declared_map_type = UnorderedMap< declared_key_type, declared_value_type, device_type, hasher_type, equal_to_type >
 
using insertable_map_type = UnorderedMap< key_type, value_type, device_type, hasher_type, equal_to_type >
 
using modifiable_map_type = UnorderedMap< const_key_type, value_type, device_type, hasher_type, equal_to_type >
 
using const_map_type = UnorderedMap< const_key_type, const_value_type, device_type, hasher_type, equal_to_type >
 
using insert_result = UnorderedMapInsertResult
 
using HostMirror = UnorderedMap< Key, Value, host_mirror_space, Hasher, EqualTo >
 
using histogram_type = Impl::UnorderedMapHistogram< const_map_type >
 
static constexpr bool is_set = std::is_void_v<value_type>
 
static constexpr bool has_const_key
 
static constexpr bool has_const_value
 
static constexpr bool is_insertable_map
 
static constexpr bool is_modifiable_map = has_const_key && !has_const_value
 
static constexpr bool is_const_map = has_const_key && has_const_value
 

Public member functions

using default_op_type = typename UnorderedMapInsertOpTypes< value_type_view, uint32_t >::NoOp
 
 UnorderedMap (size_type capacity_hint=0, hasher_type hasher=hasher_type(), equal_to_type equal_to=equal_to_type())
 Constructor. More...
 
template<class... P>
 UnorderedMap (const Impl::ViewCtorProp< P...> &arg_prop, size_type capacity_hint=0, hasher_type hasher=hasher_type(), equal_to_type equal_to=equal_to_type())
 
void reset_failed_insert_flag ()
 
histogram_type get_histogram ()
 
void clear ()
 Clear all entries in the table. More...
 
KOKKOS_INLINE_FUNCTION
constexpr bool 
is_allocated () const
 
bool rehash (size_type requested_capacity=0)
 Change the capacity of the the map. More...
 
bool rehash (size_type requested_capacity, bool bounded_insert)
 
size_type size () const
 The number of entries in the table. More...
 
bool failed_insert () const
 The current number of failed insert() calls. More...
 
bool erasable () const
 
bool begin_erase ()
 
bool end_erase ()
 
KOKKOS_FORCEINLINE_FUNCTION
size_type 
capacity () const
 The maximum number of entries that the table can hold. More...
 
KOKKOS_INLINE_FUNCTION size_type hash_capacity () const
 The number of hash table "buckets.". More...
 
template<typename InsertOpType = default_op_type>
KOKKOS_INLINE_FUNCTION
insert_result 
insert (key_type const &k, impl_value_type const &v=impl_value_type(), [[maybe_unused]] InsertOpType arg_insert_op=InsertOpType()) const
 
KOKKOS_INLINE_FUNCTION bool erase (key_type const &k) const
 
KOKKOS_INLINE_FUNCTION size_type find (const key_type &k) const
 Find the given key k, if it exists in the table. More...
 
KOKKOS_INLINE_FUNCTION bool exists (const key_type &k) const
 Does the key exist in the map. More...
 
template<typename Dummy = value_type>
KOKKOS_FORCEINLINE_FUNCTION
std::enable_if_t
< !std::is_void_v< Dummy >
, std::conditional_t
< has_const_value,
impl_value_type,
impl_value_type & > > 
value_at (size_type i) const
 Get the value with i as its direct index. More...
 
KOKKOS_FORCEINLINE_FUNCTION
key_type 
key_at (size_type i) const
 Get the key with i as its direct index. More...
 
KOKKOS_FORCEINLINE_FUNCTION bool valid_at (size_type i) const
 
template<typename SKey , typename SValue >
 UnorderedMap (UnorderedMap< SKey, SValue, Device, Hasher, EqualTo > const &src, std::enable_if_t< Impl::UnorderedMapCanAssign< declared_key_type, declared_value_type, SKey, SValue >::value, int >=0)
 
template<typename SKey , typename SValue >
std::enable_if_t
< Impl::UnorderedMapCanAssign
< declared_key_type,
declared_value_type, SKey,
SValue >::value,
declared_map_type & > 
operator= (UnorderedMap< SKey, SValue, Device, Hasher, EqualTo > const &src)
 
template<typename SKey , typename SValue , typename SDevice >
std::enable_if_t
< std::is_same_v
< std::remove_const_t< SKey >
, key_type > &&std::is_same_v
< std::remove_const_t< SValue >
, value_type > > 
create_copy_view (UnorderedMap< SKey, SValue, SDevice, Hasher, EqualTo > const &src)
 
template<typename SKey , typename SValue , typename SDevice >
std::enable_if_t
< std::is_same_v
< std::remove_const_t< SKey >
, key_type > &&std::is_same_v
< std::remove_const_t< SValue >
, value_type > > 
allocate_view (UnorderedMap< SKey, SValue, SDevice, Hasher, EqualTo > const &src)
 
template<typename SKey , typename SValue , typename SDevice >
std::enable_if_t
< std::is_same_v
< std::remove_const_t< SKey >
, key_type > &&std::is_same_v
< std::remove_const_t< SValue >
, value_type > > 
deep_copy_view (UnorderedMap< SKey, SValue, SDevice, Hasher, EqualTo > const &src)
 

Detailed Description

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
class Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >

Thread-safe, performance-portable lookup table.

This class provides a lookup table. In terms of functionality, this class compares to std::unordered_map (new in C++11). "Unordered" means that keys are not stored in any particular order, unlike (for example) std::map. "Thread-safe" means that lookups, insertion, and deletion are safe to call by multiple threads in parallel. "Performance-portable" means that parallel performance of these operations is reasonable, on multiple hardware platforms. Platforms on which performance has been tested include conventional Intel x86 multicore processors, Intel Xeon Phi ("MIC"), and NVIDIA GPUs.

Parallel performance portability entails design decisions that might differ from one's expectation for a sequential interface. This particularly affects insertion of single elements. In an interface intended for sequential use, insertion might reallocate memory if the original allocation did not suffice to hold the new element. In this class, insertion does not reallocate memory. This means that it might fail. insert() returns an enum which indicates whether the insert failed. There are three possible conditions:

  1. INSERT_FAILED: The insert failed. This usually means that the UnorderedMap ran out of space.
  2. INSERT_SUCCESS: The insert succeeded, and the key did not exist in the table before.
  3. INSERT_EXISTING: The insert succeeded, and the key did exist in the table before. The new value was ignored and the old value was left in place.
Template Parameters
KeyType of keys of the lookup table. If const, users are not allowed to add or remove keys, though they are allowed to change values. In that case, the implementation may make optimizations specific to the Device. For example, if Device is Cuda, it may use texture fetches to access keys.
ValueType of values stored in the lookup table. You may use void here, in which case the table will be a set of keys. If const, users are not allowed to change entries. In that case, the implementation may make optimizations specific to the Device, such as using texture fetches to access values.
DeviceThe Kokkos Device type.
HasherDefinition of the hash function for instances of Key. The default will calculate a bitwise hash.
EqualToDefinition of the equality function for instances of Key. The default will do a bitwise equality comparison.

Definition at line 210 of file Kokkos_UnorderedMap.hpp.

Constructor & Destructor Documentation

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::UnorderedMap ( size_type  capacity_hint = 0,
hasher_type  hasher = hasher_type(),
equal_to_type  equal_to = equal_to_type() 
)
inline

Constructor.

Parameters
capacity_hint[in] Initial guess of how many unique keys will be inserted into the map.
hash[in] Hasher function for Key instances. The default value usually suffices.
equal_to[in] The operator used for determining if two keys are equal.

Definition at line 304 of file Kokkos_UnorderedMap.hpp.

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
template<class... P>
Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::UnorderedMap ( const Impl::ViewCtorProp< P...> &  arg_prop,
size_type  capacity_hint = 0,
hasher_type  hasher = hasher_type(),
equal_to_type  equal_to = equal_to_type() 
)
inline

Ensure that allocation properties are consistent.

Update allocation properties with 'label' and 'without initializing' properties.

Initialize member views.

Deep copies should also be done using the space instance if given. Instead of the if/else we could use the get_property_or_default, but giving even the default execution space instance will change the behavior of deep_copy.

Definition at line 309 of file Kokkos_UnorderedMap.hpp.

Member Function Documentation

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
void Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::clear ( )
inline

Clear all entries in the table.

Definition at line 383 of file Kokkos_UnorderedMap.hpp.

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
bool Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::rehash ( size_type  requested_capacity = 0)
inline

Change the capacity of the the map.

If there are no failed inserts the current size of the map will be used as a lower bound for the input capacity. If the map is not empty and does not have failed inserts and the capacity changes then the current data is copied into the resized / rehashed map.

This is not a device function; it may not be called in a parallel kernel.

Definition at line 415 of file Kokkos_UnorderedMap.hpp.

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
size_type Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::size ( ) const
inline

The number of entries in the table.

This method has undefined behavior when erasable() is true.

Note that this is not a device function; it cannot be called in a parallel kernel. The value is not stored as a variable; it must be computed. m_size is a mutable cache of that value.

Definition at line 448 of file Kokkos_UnorderedMap.hpp.

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
bool Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::failed_insert ( ) const
inline

The current number of failed insert() calls.

This is not a device function; it may not be called in a parallel kernel. The value is not stored as a variable; it must be computed.

Definition at line 462 of file Kokkos_UnorderedMap.hpp.

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
KOKKOS_FORCEINLINE_FUNCTION size_type Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::capacity ( ) const
inline

The maximum number of entries that the table can hold.

This is a device function; it may be called in a parallel kernel.

Definition at line 498 of file Kokkos_UnorderedMap.hpp.

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
KOKKOS_INLINE_FUNCTION size_type Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::hash_capacity ( ) const
inline

The number of hash table "buckets.".

This is different than the number of entries that the table can hold. Each key hashes to an index in [0, hash_capacity() - 1]. That index can hold zero or more entries. This class decides what hash_capacity() should be, given the user's upper bound on the number of entries the table must be able to hold.

This is a device function; it may be called in a parallel kernel.

Definition at line 511 of file Kokkos_UnorderedMap.hpp.

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
template<typename InsertOpType = default_op_type>
KOKKOS_INLINE_FUNCTION insert_result Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::insert ( key_type const &  k,
impl_value_type const &  v = impl_value_type(),
[[maybe_unused] ] InsertOpType  arg_insert_op = InsertOpType() 
) const
inline

This is a device function; it may be called in a parallel kernel. As discussed in the class documentation, it need not succeed. The return value tells you if it did.

Parameters
k[in] The key to attempt to insert.
v[in] The corresponding value to attempt to insert. If using this class as a set (with Value = void), then you need not provide this value.
insert_op[in] The operator used for combining values if a key already exists. See Kokkos::UnorderedMapInsertOpTypes for more ops.

Definition at line 529 of file Kokkos_UnorderedMap.hpp.

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
KOKKOS_INLINE_FUNCTION size_type Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::find ( const key_type &  k) const
inline

Find the given key k, if it exists in the table.

Returns
If the key exists in the table, the index of the value corresponding to that key; otherwise, an invalid index.

This is a device function; it may be called in a parallel kernel.

Definition at line 717 of file Kokkos_UnorderedMap.hpp.

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
KOKKOS_INLINE_FUNCTION bool Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::exists ( const key_type &  k) const
inline

Does the key exist in the map.

This is a device function; it may be called in a parallel kernel.

Definition at line 737 of file Kokkos_UnorderedMap.hpp.

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
template<typename Dummy = value_type>
KOKKOS_FORCEINLINE_FUNCTION std::enable_if_t< !std::is_void_v<Dummy>, std::conditional_t<has_const_value, impl_value_type, impl_value_type &> > Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::value_at ( size_type  i) const
inline

Get the value with i as its direct index.

Parameters
i[in] Index directly into the array of entries.

This is a device function; it may be called in a parallel kernel.

'const value_type' via Cuda texture fetch must return by value.

Definition at line 751 of file Kokkos_UnorderedMap.hpp.

template<typename Key, typename Value, typename Device = Kokkos::DefaultExecutionSpace, typename Hasher = pod_hash<std::remove_const_t<Key>>, typename EqualTo = pod_equal_to<std::remove_const_t<Key>>>
KOKKOS_FORCEINLINE_FUNCTION key_type Kokkos::UnorderedMap< Key, Value, Device, Hasher, EqualTo >::key_at ( size_type  i) const
inline

Get the key with i as its direct index.

Parameters
i[in] Index directly into the array of entries.

This is a device function; it may be called in a parallel kernel.

Definition at line 763 of file Kokkos_UnorderedMap.hpp.


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