Tpetra parallel linear algebra  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Public Types | Public Member Functions | List of all members
Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType > Class Template Reference

#include <Tpetra_Details_FixedHashTable_decl.hpp>

Inheritance diagram for Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >:
Inheritance graph
[legend]

Public Types

typedef Kokkos::View< const
KeyType *, Kokkos::LayoutLeft,
device_type > 
keys_type
 Type of a 1-D Kokkos::View (array) used to store keys. More...
 

Public Member Functions

 FixedHashTable ()
 Default constructor; makes an empty table. More...
 
 FixedHashTable (const keys_type &keys)
 Constructor for arbitrary keys and contiguous values starting with zero. More...
 
 FixedHashTable (const Teuchos::ArrayView< const KeyType > &keys)
 Constructor for arbitrary keys and contiguous values starting with zero. More...
 
 FixedHashTable (const keys_type &keys, const ValueType startingValue)
 Constructor for arbitrary keys and contiguous values starting with startingValue. More...
 
 FixedHashTable (const Teuchos::ArrayView< const KeyType > &keys, const ValueType startingValue)
 Constructor for arbitrary keys and contiguous values starting with startingValue. More...
 
 FixedHashTable (const keys_type &keys, const KeyType firstContigKey, const KeyType lastContigKey, const ValueType startingValue)
 Constructor for arbitrary keys and contiguous values starting with startingValue, that takes an initial contiguous sequence of keys, stored as a Kokkos::View. More...
 
 FixedHashTable (const Teuchos::ArrayView< const KeyType > &keys, const KeyType firstContigKey, const KeyType lastContigKey, const ValueType startingValue)
 Constructor for arbitrary keys and contiguous values starting with startingValue, that takes an initial contiguous sequence of keys, stored as a Teuchos::ArrayView (host pointer). More...
 
 FixedHashTable (const Teuchos::ArrayView< const KeyType > &keys, const Teuchos::ArrayView< const ValueType > &vals)
 Constructor for arbitrary keys and arbitrary values. More...
 
template<class InDeviceType >
 FixedHashTable (const FixedHashTable< KeyType, ValueType, InDeviceType > &src, typename std::enable_if<!std::is_same< DeviceType, InDeviceType >::value, int >::type *=NULL)
 "Copy" constructor that takes a FixedHashTable with the same KeyType and ValueType, but a different DeviceType. More...
 
KOKKOS_INLINE_FUNCTION ValueType get (const KeyType &key) const
 Get the value corresponding to the given key. More...
 
KOKKOS_INLINE_FUNCTION offset_type numPairs () const
 Number of (key, value) pairs in the table. More...
 
KOKKOS_INLINE_FUNCTION KeyType minKey () const
 The minimum key in the table. More...
 
KOKKOS_INLINE_FUNCTION KeyType maxKey () const
 The maximum key in the table. More...
 
KOKKOS_INLINE_FUNCTION ValueType minVal () const
 The minimum value in the table. More...
 
KOKKOS_INLINE_FUNCTION ValueType maxVal () const
 The maximum value in the table. More...
 
bool hasDuplicateKeys ()
 Whether the table has any duplicate keys. More...
 
std::string description () const
 Implementation of Teuchos::Describable interface. More...
 
void describe (Teuchos::FancyOStream &out, const Teuchos::EVerbosityLevel verbLevel=Teuchos::Describable::verbLevel_default) const
 Print this object with the given verbosity to the output stream. More...
 

Detailed Description

template<class KeyType, class ValueType, class DeviceType>
class Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >

Template Parameters
KeyTypeThe type of the hash table's keys. This must be a built-in signed or unsigned integer type.
ValueTypeThe type of the hash table's values. This must be a built-in signed or unsigned integer type.
DeviceTypeSpecialization of Kokkos::Device.

This class implements a look-up table from integer keys to integer values. All the (key,value) pairs must be added at once, and pairs may not be changed or removed. Keys and values may have different types. Tpetra::Map may use this to implement global-to-local index lookup.

The hash table uses a "compressed sparse row" storage strategy. The hash function maps a key to its "row" in the table, and then we search within that row to find the corresponding value. In each row, we store a key and its value adjacent to each other. This strategy puts (key,value) pairs in a single contiguous array, rather than in separately allocated buckets (as in a conventional dynamically allocated hash table). This saves initialization time, as long as the hash function takes less than half the time of a system call to allocate memory. This is because there are only $O(1)$ memory allocation calls, rather than one for each (key,value) pair or hash bucket. The compressed sparse row strategy may also improve locality for hash table lookups.

Definition at line 86 of file Tpetra_Details_FixedHashTable_decl.hpp.

Member Typedef Documentation

template<class KeyType, class ValueType, class DeviceType>
typedef Kokkos::View<const KeyType*, Kokkos::LayoutLeft, device_type> Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::keys_type

Type of a 1-D Kokkos::View (array) used to store keys.

This is the type preferred by FixedHashTable's constructors.

Definition at line 127 of file Tpetra_Details_FixedHashTable_decl.hpp.

Constructor & Destructor Documentation

template<class KeyType , class ValueType , class DeviceType >
Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::FixedHashTable ( )

Default constructor; makes an empty table.

Definition at line 545 of file Tpetra_Details_FixedHashTable_def.hpp.

template<class KeyType , class ValueType , class DeviceType >
Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::FixedHashTable ( const keys_type keys)

Constructor for arbitrary keys and contiguous values starting with zero.

Add (keys[i], i) to the table, for i = 0, 1, ..., keys.extent(0).

Parameters
keys[in] The keys in the hash table. The table always keeps a (shallow) copy, and thus hasKeys() is true on return.

Definition at line 566 of file Tpetra_Details_FixedHashTable_def.hpp.

template<class KeyType, class ValueType , class DeviceType >
Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::FixedHashTable ( const Teuchos::ArrayView< const KeyType > &  keys)

Constructor for arbitrary keys and contiguous values starting with zero.

Add (keys[i], i) to the table, for i = 0, 1, ..., keys.size().

Parameters
keys[in] The keys in the hash table.

Definition at line 592 of file Tpetra_Details_FixedHashTable_def.hpp.

template<class KeyType, class ValueType, class DeviceType >
Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::FixedHashTable ( const keys_type keys,
const ValueType  startingValue 
)

Constructor for arbitrary keys and contiguous values starting with startingValue.

Add (keys[i], startingValue + i) to the table, for i = 0, 1, ..., keys.extent(0). This version is useful if Map wants to exclude an initial sequence of contiguous GIDs from the table, and start with a given LID.

Parameters
keys[in] The keys in the hash table. The table always keeps a (shallow) copy, and thus hasKeys() is true on return.
startingValue[in] First value in the contiguous sequence of values.

Definition at line 778 of file Tpetra_Details_FixedHashTable_def.hpp.

template<class KeyType, class ValueType, class DeviceType >
Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::FixedHashTable ( const Teuchos::ArrayView< const KeyType > &  keys,
const ValueType  startingValue 
)

Constructor for arbitrary keys and contiguous values starting with startingValue.

Add (keys[i], startingValue + i) to the table, for i = 0, 1, ..., keys.size(). This version is useful if Map wants to exclude an initial sequence of contiguous GIDs from the table, and start with a given LID.

Parameters
keys[in] The keys in the hash table.
startingValue[in] First value in the contiguous sequence of values.

Definition at line 630 of file Tpetra_Details_FixedHashTable_def.hpp.

template<class KeyType, class ValueType, class DeviceType >
Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::FixedHashTable ( const keys_type keys,
const KeyType  firstContigKey,
const KeyType  lastContigKey,
const ValueType  startingValue 
)

Constructor for arbitrary keys and contiguous values starting with startingValue, that takes an initial contiguous sequence of keys, stored as a Kokkos::View.

Add (keys[i], startingValue + i) to the table, for i = 0, 1, ..., keys.size().

Parameters
keys[in] The keys in the hash table. We reserve the right to keep the input View without a deep copy. If you intend to modify this View after calling this constructor, please make a deep copy yourself and give the copy to this constructor.
firstContigKey[in] First key in the initial contiguous sequence of keys.
lastContigKey[in] Last key (inclusive!) in the initial contiguous sequence of keys.
startingValue[in] First value in the contiguous sequence of values.

Definition at line 685 of file Tpetra_Details_FixedHashTable_def.hpp.

template<class KeyType, class ValueType, class DeviceType >
Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::FixedHashTable ( const Teuchos::ArrayView< const KeyType > &  keys,
const KeyType  firstContigKey,
const KeyType  lastContigKey,
const ValueType  startingValue 
)

Constructor for arbitrary keys and contiguous values starting with startingValue, that takes an initial contiguous sequence of keys, stored as a Teuchos::ArrayView (host pointer).

Add (keys[i], startingValue + i) to the table, for i = 0, 1, ..., keys.size().

Parameters
keys[in] The keys in the hash table.
firstContigKey[in] First key in the initial contiguous sequence of keys.
lastContigKey[in] Last key (inclusive!) in the initial contiguous sequence of keys.
startingValue[in] First value in the contiguous sequence of values.

Definition at line 725 of file Tpetra_Details_FixedHashTable_def.hpp.

template<class KeyType, class ValueType, class DeviceType >
Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::FixedHashTable ( const Teuchos::ArrayView< const KeyType > &  keys,
const Teuchos::ArrayView< const ValueType > &  vals 
)

Constructor for arbitrary keys and arbitrary values.

Add (keys[i], vals[i]) to the table, for i = 0, 1, ..., keys.size(). This version is useful for applications other than Map's GID-to-LID lookup table.

Parameters
keys[in] The keys in the hash table.
vals[in] The values in the hash table.

Definition at line 818 of file Tpetra_Details_FixedHashTable_def.hpp.

template<class KeyType, class ValueType, class DeviceType>
template<class InDeviceType >
Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::FixedHashTable ( const FixedHashTable< KeyType, ValueType, InDeviceType > &  src,
typename std::enable_if<!std::is_same< DeviceType, InDeviceType >::value, int >::type *  = NULL 
)
inline

"Copy" constructor that takes a FixedHashTable with the same KeyType and ValueType, but a different DeviceType.

This constructor makes a deep copy of the input's data if necessary.

Definition at line 245 of file Tpetra_Details_FixedHashTable_decl.hpp.

Member Function Documentation

template<class KeyType, class ValueType, class DeviceType>
KOKKOS_INLINE_FUNCTION ValueType Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::get ( const KeyType &  key) const
inline

Get the value corresponding to the given key.

Definition at line 284 of file Tpetra_Details_FixedHashTable_decl.hpp.

template<class KeyType, class ValueType, class DeviceType>
KOKKOS_INLINE_FUNCTION offset_type Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::numPairs ( ) const
inline

Number of (key, value) pairs in the table.

This counts pairs with the same key value as separate pairs.

Definition at line 318 of file Tpetra_Details_FixedHashTable_decl.hpp.

template<class KeyType, class ValueType, class DeviceType>
KOKKOS_INLINE_FUNCTION KeyType Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::minKey ( ) const
inline

The minimum key in the table.

This function does not throw. If the table is empty, the return value is undefined. Furthermore, if the table is empty, we do not promise that minKey() <= maxKey().

This class assumes that both keys and values are numbers. Therefore, keys are less-than comparable.

Definition at line 340 of file Tpetra_Details_FixedHashTable_decl.hpp.

template<class KeyType, class ValueType, class DeviceType>
KOKKOS_INLINE_FUNCTION KeyType Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::maxKey ( ) const
inline

The maximum key in the table.

This function does not throw. If the table is empty, the return value is undefined. Furthermore, if the table is empty, we do not promise that minKey() <= maxKey().

This class assumes that both keys and values are numbers. Therefore, keys are less-than comparable.

Definition at line 352 of file Tpetra_Details_FixedHashTable_decl.hpp.

template<class KeyType, class ValueType, class DeviceType>
KOKKOS_INLINE_FUNCTION ValueType Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::minVal ( ) const
inline

The minimum value in the table.

A "value" is the result of calling get() on a key.

This function does not throw. If the table is empty, the return value is undefined. Furthermore, if the table is empty, we do not promise that minVal() <= maxVal().

Definition at line 363 of file Tpetra_Details_FixedHashTable_decl.hpp.

template<class KeyType, class ValueType, class DeviceType>
KOKKOS_INLINE_FUNCTION ValueType Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::maxVal ( ) const
inline

The maximum value in the table.

A "value" is the result of calling get() on a key.

This function does not throw. If the table is empty, the return value is undefined. Furthermore, if the table is empty, we do not promise that minVal() <= maxVal().

Definition at line 374 of file Tpetra_Details_FixedHashTable_decl.hpp.

template<class KeyType , class ValueType , class DeviceType >
bool Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::hasDuplicateKeys ( )

Whether the table has any duplicate keys.

This is a nonconst function because it requires running a Kokkos kernel to search the keys. The result of the first call is cached and reused on subsequent calls.

This function is the "local" (to an MPI process) version of Tpetra::Map::isOneToOne. If a Tpetra::Map has duplicate keys (global indices) on any one MPI process, then it is most certainly not one to one. The opposite may not necessarily be true, because a Tpetra::Map might have duplicate global indices that occur on different MPI processes.

Definition at line 1299 of file Tpetra_Details_FixedHashTable_def.hpp.

template<class KeyType , class ValueType , class DeviceType >
std::string Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::description ( ) const

Implementation of Teuchos::Describable interface.

FixedHashTable can't actually inherit from Teuchos::Describable, because that would prevent instances of this class from living in GPU device code. See GitHub issue #1623. Return a simple one-line description of this object.

Definition at line 1333 of file Tpetra_Details_FixedHashTable_def.hpp.

template<class KeyType , class ValueType , class DeviceType >
void Tpetra::Details::FixedHashTable< KeyType, ValueType, DeviceType >::describe ( Teuchos::FancyOStream &  out,
const Teuchos::EVerbosityLevel  verbLevel = Teuchos::Describable::verbLevel_default 
) const

Print this object with the given verbosity to the output stream.

Definition at line 1347 of file Tpetra_Details_FixedHashTable_def.hpp.


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