Tpetra_Details_FixedHashTable_def.hpp

// @HEADER
// *****************************************************************************
//          Tpetra: Templated Linear Algebra Services Package
//
// Copyright 2008 NTESS and the Tpetra contributors.
// SPDX-License-Identifier: BSD-3-Clause
// *****************************************************************************
// @HEADER
 
#ifndef TPETRA_DETAILS_FIXEDHASHTABLE_DEF_HPP
#define TPETRA_DETAILS_FIXEDHASHTABLE_DEF_HPP
 
#include "Tpetra_Details_FixedHashTable_decl.hpp"
#include "Tpetra_Details_computeOffsets.hpp"
#ifdef TPETRA_USE_MURMUR_HASH
#include "Kokkos_Functional.hpp"  // hash function used by Kokkos::UnorderedMap
#endif                            // TPETRA_USE_MURMUR_HASH
#if KOKKOS_VERSION >= 40799
#include "KokkosKernels_ArithTraits.hpp"
#else
#include "Kokkos_ArithTraits.hpp"
#endif
#include "Teuchos_TypeNameTraits.hpp"
#include "Tpetra_Details_Behavior.hpp"
#include <type_traits>
 
namespace Tpetra {
namespace Details {
//
// This namespace stores utility functions and Kokkos
// functors for use in FixedHashTable construction.
//
namespace FHT {
 
// Is it worth actually using building the FixedHashTable using
// parallel threads, instead of just counting in a sequential loop?
//
// The parallel version of FixedHashTable construction isn't just a
// parallelization of the sequential loops.  It incurs additional
// overheads.  For example, the CountBuckets kernel uses atomic update
// instructions to count the number of "buckets" per offsets array
// (ptr) entry.  Atomic updates have overhead, even if only one thread
// issues them.  The Kokkos kernels are still correct in that case,
// but I would rather not incur overhead then.  It might make sense to
// set the minimum number of threads to something greater than 1, but
// we would need experiments to find out.
template <class ExecSpace>
bool worthBuildingFixedHashTableInParallel() {
  return ExecSpace().concurrency() > 1;
}
 
//
// Functors for FixedHashTable initialization
//
// NOTE (mfh 23 May 2015): Once we can use lambdas with CUDA, we
// should consider replacing all of these functors with in-line
// lambdas.  The only issue is that we would need to bake the
// execution space into the policy, since the default execution space
// might differ from the one Tpetra wants to use.
 
template <class CountsViewType,
          class KeysViewType,
          class SizeType = typename KeysViewType::size_type>
class CountBuckets {
 public:
  typedef CountsViewType counts_view_type;
  typedef KeysViewType keys_view_type;
  typedef typename CountsViewType::execution_space execution_space;
  typedef typename CountsViewType::memory_space memory_space;
  typedef SizeType size_type;
  typedef typename keys_view_type::non_const_value_type key_type;
  // mfh 21 May 2015: Having a device_type typedef in the functor
  // along with an execution_space typedef causes compilation issues.
  // This is because one of Kokkos' partial specializations picks up
  // on the device_type typedef, and another picks up on the
  // execution_space typedef.  The former is a legacy of a previous
  // design iteration of Kokkos, which did not separate memory and
  // execution spaces.
  typedef Tpetra::Details::Hash<key_type, Kokkos::Device<execution_space, memory_space>> hash_type;
 
  CountBuckets(const counts_view_type& counts,
               const keys_view_type& keys,
               const size_type size)
    : counts_(counts)
    , keys_(keys)
    , size_(size) {}
 
  KOKKOS_INLINE_FUNCTION void
  operator()(const size_type& i) const {
    typedef typename hash_type::result_type hash_value_type;
 
    const hash_value_type hashVal = hash_type::hashFunc(keys_[i], size_);
    Kokkos::atomic_inc(&counts_[hashVal]);
  }
 
  using value_type = Kokkos::pair<int, key_type>;
 
  KOKKOS_INLINE_FUNCTION void
  operator()(const size_type& i, value_type& dst) const {
    using hash_value_type = typename hash_type::result_type;
 
    const key_type keyVal         = keys_[i];
    const hash_value_type hashVal = hash_type::hashFunc(keyVal, size_);
    if (hashVal < hash_value_type(0) ||
        hashVal >= hash_value_type(counts_.extent(0))) {
      dst.first  = 1;
      dst.second = keyVal;
    } else {
      Kokkos::atomic_inc(&counts_[hashVal]);
    }
  }
 
  KOKKOS_INLINE_FUNCTION void init(value_type& dst) const {
    dst.first  = 0;
    dst.second = key_type(0);
  }
 
  KOKKOS_INLINE_FUNCTION void
  join(value_type& dst,
       const value_type& src) const {
    const bool good = dst.first == 0 || src.first == 0;
    dst.first       = good ? 0 : dst.first;
    // leave dst.second as it is, to get the "first" key
  }
 
 private:
  counts_view_type counts_;
  keys_view_type keys_;
  size_type size_;
};
 
template <class KeyType>
struct FillPairsResult {
  KOKKOS_INLINE_FUNCTION
  FillPairsResult()
#if KOKKOS_VERSION >= 40799
    : minKey_(::KokkosKernels::ArithTraits<KeyType>::max())
#else
    : minKey_(::Kokkos::ArithTraits<KeyType>::max())
#endif
    ,
  // min() for a floating-point type returns the minimum _positive_
  // normalized value.  This is different than for integer types.
  // lowest() is new in C++11 and returns the least value, always
  // negative for signed finite types.
  //
  // mfh 23 May 2015: I have heard reports that
  // std::numeric_limits<int>::lowest() does not exist with the
  // Intel compiler.  I'm not sure if the users in question actually
  // enabled C++11.  However, it's easy enough to work around this
  // issue.  The standard floating-point types are signed and have a
  // sign bit, so lowest() is just -max().  For integer types, we
  // can use min() instead.
#if KOKKOS_VERSION >= 40799
    maxKey_(::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max())
#else
    maxKey_(::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max())
#endif
    , success_(true) {
    static_assert(std::is_arithmetic<KeyType>::value,
                  "FillPairsResult: "
                  "KeyType must be some kind of number type.");
  }
 
  KOKKOS_INLINE_FUNCTION
  FillPairsResult(const KeyType& initMinKey,
                  const KeyType& initMaxKey)
    : minKey_(initMinKey)
    , maxKey_(initMaxKey)
    , success_(true) {
    static_assert(std::is_arithmetic<KeyType>::value,
                  "FillPairsResult: "
                  "KeyType must be some kind of number type.");
  }
 
  KeyType minKey_;  
  KeyType maxKey_;  
  bool success_;    
};
 
template <class PairsViewType,
          class KeysViewType,
          class CountsViewType,
          class SizeType = typename KeysViewType::size_type>
class FillPairs {
 public:
  typedef typename CountsViewType::non_const_type counts_view_type;
  typedef typename counts_view_type::const_type offsets_view_type;
 
  typedef PairsViewType pairs_view_type;
  typedef typename KeysViewType::const_type keys_view_type;
  typedef typename offsets_view_type::execution_space execution_space;
  typedef typename offsets_view_type::memory_space memory_space;
  typedef SizeType size_type;
 
  typedef typename keys_view_type::non_const_value_type key_type;
  typedef typename pairs_view_type::non_const_value_type pair_type;
 
  typedef FillPairsResult<key_type> value_type;
 
  // mfh 23 May 2015: Having a device_type typedef in the functor
  // along with an execution_space typedef causes compilation issues.
  // This is because one of Kokkos' partial specializations picks up
  // on the device_type typedef, and another picks up on the
  // execution_space typedef.  The former is a legacy of a previous
  // design iteration of Kokkos, which did not separate memory and
  // execution spaces.
  typedef Tpetra::Details::Hash<key_type, Kokkos::Device<execution_space, memory_space>> hash_type;
 
  FillPairs(const pairs_view_type& pairs,
            const counts_view_type& counts,
            const offsets_view_type& ptr,
            const keys_view_type& keys,
            const typename pair_type::second_type startingValue)
    : pairs_(pairs)
    , counts_(counts)
    , ptr_(ptr)
    , keys_(keys)
    , size_(counts.extent(0))
    , startingValue_(startingValue)
#if KOKKOS_VERSION >= 40799
    , initMinKey_(::KokkosKernels::ArithTraits<key_type>::max())
    , initMaxKey_(::KokkosKernels::ArithTraits<key_type>::is_integer ? ::KokkosKernels::ArithTraits<key_type>::min() : -::KokkosKernels::ArithTraits<key_type>::max()){}
#else
    , initMinKey_(::Kokkos::ArithTraits<key_type>::max())
    , initMaxKey_(::Kokkos::ArithTraits<key_type>::is_integer ? ::Kokkos::ArithTraits<key_type>::min() : -::Kokkos::ArithTraits<key_type>::max()) {
  }
#endif
 
    FillPairs(const pairs_view_type& pairs,
              const counts_view_type& counts,
              const offsets_view_type& ptr,
              const keys_view_type& keys,
              const typename pair_type::second_type startingValue,
              const key_type initMinKey,
              const key_type initMaxKey)
    : pairs_(pairs)
    , counts_(counts)
    , ptr_(ptr)
    , keys_(keys)
    , size_(counts.extent(0))
    , startingValue_(startingValue)
    , initMinKey_(initMinKey)
    , initMaxKey_(initMaxKey) {
  }
 
  KOKKOS_INLINE_FUNCTION void init(value_type& dst) const {
    dst.minKey_  = initMinKey_;
    dst.maxKey_  = initMaxKey_;
    dst.success_ = true;
  }
 
  KOKKOS_INLINE_FUNCTION void
  join(value_type& dst,
       const value_type& src) const {
    if (src.maxKey_ > dst.maxKey_) {
      dst.maxKey_ = src.maxKey_;
    }
    if (src.minKey_ < dst.minKey_) {
      dst.minKey_ = src.minKey_;
    }
    dst.success_ = dst.success_ && src.success_;
  }
 
  KOKKOS_INLINE_FUNCTION void
  operator()(const size_type& i, value_type& dst) const {
    typedef typename hash_type::result_type hash_value_type;
    typedef typename offsets_view_type::non_const_value_type offset_type;
    typedef typename pair_type::second_type val_type;
    typedef typename std::remove_reference<decltype(counts_[0])>::type atomic_incr_type;
 
    const key_type key = keys_[i];
    if (key > dst.maxKey_) {
      dst.maxKey_ = key;
    }
    if (key < dst.minKey_) {
      dst.minKey_ = key;
    }
    const val_type theVal         = startingValue_ + static_cast<val_type>(i);
    const hash_value_type hashVal = hash_type::hashFunc(key, size_);
 
    // Return the old count; decrement afterwards.
    const offset_type count = Kokkos::atomic_fetch_add(&counts_[hashVal], atomic_incr_type(-1));
    if (count == 0) {
      dst.success_ = false;  // FAILURE!
    } else {
      const offset_type curPos = ptr_[hashVal + 1] - count;
 
      pairs_[curPos].first  = key;
      pairs_[curPos].second = theVal;
    }
  }
 
 private:
  pairs_view_type pairs_;
  counts_view_type counts_;
  offsets_view_type ptr_;
  keys_view_type keys_;
  size_type size_;
  typename pair_type::second_type startingValue_;
  key_type initMinKey_;
  key_type initMaxKey_;
};
 
template <class OffsetsViewType,
          class PairsViewType,
          class SizeType = typename OffsetsViewType::size_type>
class CheckForDuplicateKeys {
 public:
  typedef typename OffsetsViewType::const_type offsets_view_type;
  typedef typename PairsViewType::const_type pairs_view_type;
  typedef typename offsets_view_type::execution_space execution_space;
  typedef typename offsets_view_type::memory_space memory_space;
  typedef SizeType size_type;
 
  // The result of the check is whether the table has one or more duplicates.
  typedef int value_type;
 
  CheckForDuplicateKeys(const pairs_view_type& pairs,
                        const offsets_view_type& ptr)
    : pairs_(pairs)
    , ptr_(ptr)
    , size_(ptr_.extent(0) == 0 ? size_type(0) : ptr_.extent(0) - 1) {}
 
  KOKKOS_INLINE_FUNCTION void init(value_type& dst) const {
    dst = 0;
  }
 
  KOKKOS_INLINE_FUNCTION void
  join(value_type& dst,
       const value_type& src) const {
    dst = dst + src > 0 ? 1 : 0;
  }
 
  KOKKOS_INLINE_FUNCTION void
  operator()(const size_type& i, value_type& dst) const {
    typedef typename offsets_view_type::non_const_value_type offset_type;
    typedef typename pairs_view_type::non_const_value_type pair_type;
    typedef typename pair_type::first_type key_type;
 
    if (dst > 0) {
      return;  // we've already found duplicate keys elsewhere
    } else {
      const offset_type beg  = ptr_[i];
      const offset_type end  = ptr_[i + 1];
      bool foundDuplicateKey = false;
      // This is an ~ n^2 algorithm in the worst case, where n is the
      // max number of keys that hash to the same bucket.  However, if
      // the hash function is reasonable, n should be much less than
      // the total number of keys.
      for (offset_type j = beg + 1; j < end; ++j) {
        const key_type curKey = pairs_[j].first;
        for (offset_type k = beg; k < j; ++k) {
          if (pairs_[k].first == curKey) {
            foundDuplicateKey = true;
            break;
          }
        }
      }
      dst = (dst > 0) || foundDuplicateKey ? 1 : 0;
    }
  }
 
 private:
  pairs_view_type pairs_;
  offsets_view_type ptr_;
  size_type size_;
};
 
}  // namespace FHT
 
//
// Here begins the actual implementation of FixedHashTable.
//
 
template <class KeyType, class ValueType, class DeviceType>
FixedHashTable<KeyType, ValueType, DeviceType>::
    FixedHashTable(const keys_type& keys)
  : minVal_(0)
  , maxVal_(keys.size() == 0 ? static_cast<ValueType>(0) : static_cast<ValueType>(keys.size() - 1))
  , checkedForDuplicateKeys_(false) {
  const ValueType startingValue = static_cast<ValueType>(0);
  const KeyType initMinKey      = this->minKey_;
  const KeyType initMaxKey      = this->maxKey_;
  this->init(keys, startingValue, initMinKey, initMaxKey,
             initMinKey, initMinKey, false);
}
 
template <class KeyType, class ValueType, class DeviceType>
FixedHashTable<KeyType, ValueType, DeviceType>::
    FixedHashTable(const Teuchos::ArrayView<const KeyType>& keys)
  : minVal_(0)
  , maxVal_(keys.size() == 0 ? static_cast<ValueType>(0) : static_cast<ValueType>(keys.size() - 1))
  , checkedForDuplicateKeys_(false) {
  typedef typename keys_type::non_const_type nonconst_keys_type;
 
  // mfh 01 May 2015: I don't trust that
  // Teuchos::ArrayView::getRawPtr() returns NULL when the size is 0,
  // so I ensure this manually.
  const ValueType startingValue = static_cast<ValueType>(0);
  host_input_keys_type keys_k(keys.size() == 0 ? NULL : keys.getRawPtr(),
                              keys.size());
  using Kokkos::ViewAllocateWithoutInitializing;
  nonconst_keys_type keys_d(ViewAllocateWithoutInitializing("FixedHashTable::keys"),
                            keys_k.extent(0));
  // DEEP_COPY REVIEW - NOT TESTED
  Kokkos::deep_copy(keys_d, keys_k);
  const KeyType initMinKey = this->minKey_;
  const KeyType initMaxKey = this->maxKey_;
  this->init(keys_d, startingValue, initMinKey, initMaxKey,
             initMinKey, initMinKey, false);
}
 
template <class KeyType, class ValueType, class DeviceType>
FixedHashTable<KeyType, ValueType, DeviceType>::
    FixedHashTable(const Teuchos::ArrayView<const KeyType>& keys,
                   const ValueType startingValue)
  : minVal_(startingValue)
  , maxVal_(keys.size() == 0 ? startingValue : static_cast<ValueType>(startingValue + keys.size() - 1))
  , checkedForDuplicateKeys_(false) {
  typedef typename keys_type::non_const_type nonconst_keys_type;
 
  // mfh 01 May 2015: I don't trust that
  // Teuchos::ArrayView::getRawPtr() returns NULL when the size is 0,
  // so I ensure this manually.
  host_input_keys_type keys_k(keys.size() == 0 ? NULL : keys.getRawPtr(),
                              keys.size());
  using Kokkos::ViewAllocateWithoutInitializing;
  nonconst_keys_type keys_d(ViewAllocateWithoutInitializing("FixedHashTable::keys"),
                            keys_k.extent(0));
  // DEEP_COPY REVIEW - HOST-TO_DEVICE
  Kokkos::deep_copy(execution_space(), keys_d, keys_k);
 
#if KOKKOS_VERSION >= 40799
  const KeyType initMinKey = ::KokkosKernels::ArithTraits<KeyType>::max();
#else
  const KeyType initMinKey = ::Kokkos::ArithTraits<KeyType>::max();
#endif
  // min() for a floating-point type returns the minimum _positive_
  // normalized value.  This is different than for integer types.
  // lowest() is new in C++11 and returns the least value, always
  // negative for signed finite types.
  //
  // mfh 23 May 2015: I have heard reports that
  // std::numeric_limits<int>::lowest() does not exist with the Intel
  // compiler.  I'm not sure if the users in question actually enabled
  // C++11.  However, it's easy enough to work around this issue.  The
  // standard floating-point types are signed and have a sign bit, so
  // lowest() is just -max().  For integer types, we can use min()
  // instead.
#if KOKKOS_VERSION >= 40799
  const KeyType initMaxKey = ::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max();
#else
  const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max();
#endif
  this->init(keys_d, startingValue, initMinKey, initMaxKey,
             initMinKey, initMinKey, false);
}
 
template <class KeyType, class ValueType, class DeviceType>
FixedHashTable<KeyType, ValueType, DeviceType>::
    FixedHashTable(const keys_type& keys,
                   const KeyType firstContigKey,
                   const KeyType lastContigKey,
                   const ValueType startingValue)
  : minVal_(startingValue)
  , maxVal_(keys.size() == 0 ? startingValue : static_cast<ValueType>(startingValue + keys.size() - 1))
  , firstContigKey_(firstContigKey)
  , lastContigKey_(lastContigKey)
  , checkedForDuplicateKeys_(false) {
#if KOKKOS_VERSION >= 40799
  const KeyType initMinKey = ::KokkosKernels::ArithTraits<KeyType>::max();
#else
  const KeyType initMinKey = ::Kokkos::ArithTraits<KeyType>::max();
#endif
  // min() for a floating-point type returns the minimum _positive_
  // normalized value.  This is different than for integer types.
  // lowest() is new in C++11 and returns the least value, always
  // negative for signed finite types.
  //
  // mfh 23 May 2015: I have heard reports that
  // std::numeric_limits<int>::lowest() does not exist with the Intel
  // compiler.  I'm not sure if the users in question actually enabled
  // C++11.  However, it's easy enough to work around this issue.  The
  // standard floating-point types are signed and have a sign bit, so
  // lowest() is just -max().  For integer types, we can use min()
  // instead.
#if KOKKOS_VERSION >= 40799
  const KeyType initMaxKey = ::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max();
#else
  const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max();
#endif
  this->init(keys, startingValue, initMinKey, initMaxKey,
             firstContigKey, lastContigKey, true);
}
 
template <class KeyType, class ValueType, class DeviceType>
FixedHashTable<KeyType, ValueType, DeviceType>::
    FixedHashTable(const Teuchos::ArrayView<const KeyType>& keys,
                   const KeyType firstContigKey,
                   const KeyType lastContigKey,
                   const ValueType startingValue)
  : minVal_(startingValue)
  , maxVal_(keys.size() == 0 ? startingValue : static_cast<ValueType>(startingValue + keys.size() - 1))
  , firstContigKey_(firstContigKey)
  , lastContigKey_(lastContigKey)
  , checkedForDuplicateKeys_(false) {
  typedef typename keys_type::non_const_type nonconst_keys_type;
 
  // mfh 01 May 2015: I don't trust that
  // Teuchos::ArrayView::getRawPtr() returns NULL when the size is 0,
  // so I ensure this manually.
  host_input_keys_type keys_k(keys.size() == 0 ? NULL : keys.getRawPtr(),
                              keys.size());
  using Kokkos::ViewAllocateWithoutInitializing;
  nonconst_keys_type keys_d(ViewAllocateWithoutInitializing("FixedHashTable::keys"),
                            keys_k.extent(0));
  // DEEP_COPY REVIEW - NOT TESTED
  Kokkos::deep_copy(keys_d, keys_k);
 
#if KOKKOS_VERSION >= 40799
  const KeyType initMinKey = ::KokkosKernels::ArithTraits<KeyType>::max();
#else
  const KeyType initMinKey = ::Kokkos::ArithTraits<KeyType>::max();
#endif
  // min() for a floating-point type returns the minimum _positive_
  // normalized value.  This is different than for integer types.
  // lowest() is new in C++11 and returns the least value, always
  // negative for signed finite types.
  //
  // mfh 23 May 2015: I have heard reports that
  // std::numeric_limits<int>::lowest() does not exist with the Intel
  // compiler.  I'm not sure if the users in question actually enabled
  // C++11.  However, it's easy enough to work around this issue.  The
  // standard floating-point types are signed and have a sign bit, so
  // lowest() is just -max().  For integer types, we can use min()
  // instead.
#if KOKKOS_VERSION >= 40799
  const KeyType initMaxKey = ::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max();
#else
  const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max();
#endif
  this->init(keys_d, startingValue, initMinKey, initMaxKey,
             firstContigKey, lastContigKey, true);
}
 
template <class KeyType, class ValueType, class DeviceType>
FixedHashTable<KeyType, ValueType, DeviceType>::
    FixedHashTable(const keys_type& keys,
                   const ValueType startingValue)
  : minVal_(startingValue)
  , maxVal_(keys.size() == 0 ? startingValue : static_cast<ValueType>(startingValue + keys.size() - 1))
  , checkedForDuplicateKeys_(false) {
#if KOKKOS_VERSION >= 40799
  const KeyType initMinKey = ::KokkosKernels::ArithTraits<KeyType>::max();
#else
  const KeyType initMinKey = ::Kokkos::ArithTraits<KeyType>::max();
#endif
  // min() for a floating-point type returns the minimum _positive_
  // normalized value.  This is different than for integer types.
  // lowest() is new in C++11 and returns the least value, always
  // negative for signed finite types.
  //
  // mfh 23 May 2015: I have heard reports that
  // std::numeric_limits<int>::lowest() does not exist with the Intel
  // compiler.  I'm not sure if the users in question actually enabled
  // C++11.  However, it's easy enough to work around this issue.  The
  // standard floating-point types are signed and have a sign bit, so
  // lowest() is just -max().  For integer types, we can use min()
  // instead.
#if KOKKOS_VERSION >= 40799
  const KeyType initMaxKey = ::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max();
#else
  const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max();
#endif
  this->init(keys, startingValue, initMinKey, initMaxKey,
             initMinKey, initMinKey, false);
}
 
template <class KeyType, class ValueType, class DeviceType>
FixedHashTable<KeyType, ValueType, DeviceType>::
    FixedHashTable(const Teuchos::ArrayView<const KeyType>& keys,
                   const Teuchos::ArrayView<const ValueType>& vals)
  : contiguousValues_(false)
  , checkedForDuplicateKeys_(false) {
  // mfh 01 May 2015: I don't trust that
  // Teuchos::ArrayView::getRawPtr() returns NULL when the size is 0,
  // so I ensure this manually.
  host_input_keys_type keys_k(keys.size() == 0 ? NULL : keys.getRawPtr(),
                              keys.size());
  host_input_vals_type vals_k(vals.size() == 0 ? NULL : vals.getRawPtr(),
                              vals.size());
#if KOKKOS_VERSION >= 40799
  const KeyType initMinKey = ::KokkosKernels::ArithTraits<KeyType>::max();
#else
  const KeyType initMinKey = ::Kokkos::ArithTraits<KeyType>::max();
#endif
  // min() for a floating-point type returns the minimum _positive_
  // normalized value.  This is different than for integer types.
  // lowest() is new in C++11 and returns the least value, always
  // negative for signed finite types.
  //
  // mfh 23 May 2015: I have heard reports that
  // std::numeric_limits<int>::lowest() does not exist with the Intel
  // compiler.  I'm not sure if the users in question actually enabled
  // C++11.  However, it's easy enough to work around this issue.  The
  // standard floating-point types are signed and have a sign bit, so
  // lowest() is just -max().  For integer types, we can use min()
  // instead.
#if KOKKOS_VERSION >= 40799
  const KeyType initMaxKey = ::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max();
#else
  const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max();
#endif
  this->init(keys_k, vals_k, initMinKey, initMaxKey);
}
 
template <class KeyType, class ValueType, class DeviceType>
void FixedHashTable<KeyType, ValueType, DeviceType>::
    init(const keys_type& keys,
         ValueType startingValue,
         KeyType initMinKey,
         KeyType initMaxKey,
         KeyType firstContigKey,
         KeyType lastContigKey,
         const bool computeInitContigKeys) {
  using Kokkos::subview;
  using Kokkos::ViewAllocateWithoutInitializing;
  using Teuchos::TypeNameTraits;
  typedef typename std::decay<decltype(keys.extent(0))>::type size_type;
  Tpetra::Details::ProfilingRegion pr("Tpetra::Details::FixedHashTable::init(7-arg)");
  const char prefix[] = "Tpetra::Details::FixedHashTable: ";
 
  const offset_type numKeys = static_cast<offset_type>(keys.extent(0));
  {
#if KOKKOS_VERSION >= 40799
    const offset_type theMaxVal = ::KokkosKernels::ArithTraits<offset_type>::max();
#else
    const offset_type theMaxVal = ::Kokkos::ArithTraits<offset_type>::max();
#endif
    const size_type maxValST = static_cast<size_type>(theMaxVal);
    TEUCHOS_TEST_FOR_EXCEPTION(keys.extent(0) > maxValST, std::invalid_argument, prefix << "The "
                                                                                           "number of keys "
                                                                                        << keys.extent(0) << " does not fit in "
                                                                                                             "offset_type = "
                                                                                        << TypeNameTraits<offset_type>::name() << ", whose "
                                                                                                                                  "max value is "
                                                                                        << theMaxVal << ".  This means that it is not possible to "
                                                                                                        "use this constructor.");
  }
#if KOKKOS_VERSION >= 40799
  TEUCHOS_TEST_FOR_EXCEPTION(static_cast<unsigned long long>(numKeys) >
                                 static_cast<unsigned long long>(::KokkosKernels::ArithTraits<ValueType>::max()),
                             std::invalid_argument,
                             "Tpetra::Details::FixedHashTable: The number of "
                             "keys "
                                 << numKeys << " is greater than the maximum representable "
                                               "ValueType value "
                                 << ::KokkosKernels::ArithTraits<ValueType>::max() << ".  "
                                                                                      "This means that it is not possible to use this constructor.");
#else
  TEUCHOS_TEST_FOR_EXCEPTION(static_cast<unsigned long long>(numKeys) >
                                 static_cast<unsigned long long>(::Kokkos::ArithTraits<ValueType>::max()),
                             std::invalid_argument,
                             "Tpetra::Details::FixedHashTable: The number of "
                             "keys "
                                 << numKeys << " is greater than the maximum representable "
                                               "ValueType value "
                                 << ::Kokkos::ArithTraits<ValueType>::max() << ".  "
                                                                               "This means that it is not possible to use this constructor.");
#endif
  TEUCHOS_TEST_FOR_EXCEPTION(numKeys > static_cast<offset_type>(INT_MAX), std::logic_error, prefix << "This class currently only works when the number of keys is <= INT_MAX = " << INT_MAX << ".  If this is a problem for you, please talk to the Tpetra "
                                                                                                                                                                                               "developers.");
 
  const bool buildInParallel =
      FHT::worthBuildingFixedHashTableInParallel<execution_space>();
  const bool debug = ::Tpetra::Details::Behavior::debug();
 
  // NOTE (mfh 14 May 2015) This method currently assumes UVM.  We
  // could change that by setting up ptr and val as Kokkos::DualView
  // instances.  If we do that, since we are filling on host for now,
  // we want to make sure that we only zero-fill ptr on host
  // initially, and that we don't fill val at all.  Once we finish
  // Kokkos-izing all the set-up kernels, we won't need DualView for
  // either ptr or val.
 
  if (computeInitContigKeys) {
    // Find the first and last initial contiguous keys.  If we find a
    // long sequence of initial contiguous keys, we can save space by
    // not storing them explicitly as pairs in the hash table.
    //
    // NOTE (mfh 01 Jun 2015) Doing this in parallel requires a scan
    // ("min index such that the difference between the current key and
    // the next != 1"), which takes multiple passes over the data.  We
    // could fuse it with CountBuckets (only update counts on 'final'
    // pass).  However, we're really just moving this sequential search
    // out of Map's constructor here, so there is no loss in doing it
    // sequentially for now.  Later, we can work on parallelization.
    if (numKeys > 0) {
      // FIXME: make it a parallel kernel with no host copy
      auto keys_h     = Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace(),
                                                            keys);
      firstContigKey_ = keys_h[0];
      // Start with one plus, then decrement at the end.  That lets us do
      // only one addition per loop iteration, rather than two (if we test
      // against lastContigKey + 1 and then increment lastContigKey).
      lastContigKey_ = firstContigKey_ + 1;
 
      // We will only store keys in the table that are not part of the
      // initial contiguous sequence.  It's possible for the initial
      // contiguous sequence to be trivial, which for a nonzero number of
      // keys means that the "sequence" has length 1.
      for (offset_type k = 1; k < numKeys; ++k) {
        if (lastContigKey_ != keys_h[k]) {
          break;
        }
        ++lastContigKey_;
      }
      --lastContigKey_;
    }
  } else {
    firstContigKey_ = firstContigKey;
    lastContigKey_  = lastContigKey;
  }
 
  offset_type startIndex;
  if (numKeys > 0) {
    initMinKey = std::min(initMinKey, firstContigKey_);
    initMaxKey = std::max(initMaxKey, lastContigKey_);
    startIndex = static_cast<offset_type>(lastContigKey_ - firstContigKey_);
  } else {
    startIndex = 0;
  }
 
  const offset_type theNumKeys = numKeys - startIndex;
  const offset_type size       = hash_type::getRecommendedSize(theNumKeys);
#ifdef HAVE_TPETRA_DEBUG
  TEUCHOS_TEST_FOR_EXCEPTION(
      size == 0 && numKeys != 0, std::logic_error,
      "Tpetra::Details::FixedHashTable constructor: "
      "getRecommendedSize("
          << numKeys << ") returned zero, "
                        "even though the number of keys "
          << numKeys << " is nonzero.  "
                        "Please report this bug to the Tpetra developers.");
#endif  // HAVE_TPETRA_DEBUG
  keys_type theKeys =
      subview(keys, std::pair<offset_type, offset_type>(startIndex, numKeys));
 
  // FIXME (mfh 28 Mar 2016) For some reason, we don't seem to need a
  // fence here, but we do before other allocations.
 
  // The array of counts must be separate from the array of offsets,
  // in order for parallel_scan to work correctly.
  typedef typename ptr_type::non_const_type counts_type;
  counts_type counts("Tpetra::FixedHashTable::counts", size);
 
  //
  // Count the number of "buckets" per offsets array (ptr) entry.
  //
 
  // Will only create the mirror for buildInParallel false - but then use it in two places
  typename keys_type::host_mirror_type theKeysHost;
 
  // The Kokkos kernel uses atomic update instructions to count the
  // number of "buckets" per offsets array (ptr) entry.  Atomic
  // updates incur overhead, even in the sequential case.  The Kokkos
  // kernel is still correct in that case, but I would rather not
  // incur overhead then.
  if (buildInParallel) {
    FHT::CountBuckets<counts_type, keys_type> functor(counts, theKeys, size);
    using range_type         = Kokkos::RangePolicy<execution_space, offset_type>;
    const char kernelLabel[] = "Tpetra::Details::FixedHashTable CountBuckets";
    if (debug) {
      using key_type = typename keys_type::non_const_value_type;
      Kokkos::pair<int, key_type> err;
      Kokkos::parallel_reduce(kernelLabel, range_type(0, theNumKeys),
                              functor, err);
      TEUCHOS_TEST_FOR_EXCEPTION(err.first != 0, std::logic_error,
                                 "Tpetra::Details::FixedHashTable "
                                 "constructor: CountBuckets found a key "
                                     << err.second << " that "
                                                      "results in an out-of-bounds hash value.");
    } else {
      Kokkos::parallel_for(kernelLabel, range_type(0, theNumKeys), functor);
    }
  } else {
    Kokkos::HostSpace hostMemSpace;
    theKeysHost = Kokkos::create_mirror_view(theKeys);
    // DEEP_COPY REVIEW - DEVICE-TO-HOSTMIRROR
    Kokkos::deep_copy(execution_space(), theKeysHost, theKeys);
    auto countsHost = Kokkos::create_mirror_view(hostMemSpace, counts);
 
    for (offset_type k = 0; k < theNumKeys; ++k) {
      using key_type     = typename keys_type::non_const_value_type;
      const key_type key = theKeysHost[k];
 
      using hash_value_type         = typename hash_type::result_type;
      const hash_value_type hashVal = hash_type::hashFunc(key, size);
      TEUCHOS_TEST_FOR_EXCEPTION(hashVal < hash_value_type(0) ||
                                     hashVal >= hash_value_type(countsHost.extent(0)),
                                 std::logic_error,
                                 "Tpetra::Details::FixedHashTable "
                                 "constructor: Sequential CountBuckets found a key "
                                     << key
                                     << " that results in an out-of-bounds hash value.");
 
      ++countsHost[hashVal];
    }
    // DEEP_COPY REVIEW - HOSTMIRROR-TO-DEVICE
    Kokkos::deep_copy(execution_space(), counts, countsHost);
  }
 
  // KJ: This fence is not required for the 2-argument deep_copy which calls
  // fence, but will be required if switched to the 3-argumemt deep_copy which
  // passes a space. The 3-argument form does not fence.
  execution_space().fence();
 
  // Kokkos::View fills with zeros by default.
  typename ptr_type::non_const_type ptr("Tpetra::FixedHashTable::ptr", size + 1);
 
  // Compute row offsets via prefix sum:
  //
  // ptr[i+1] = \sum_{j=0}^{i} counts[j].
  //
  // Thus, ptr[i+1] - ptr[i] = counts[i], so that ptr[i+1] = ptr[i] +
  // counts[i].  If we stored counts[i] in ptr[i+1] on input, then the
  // formula is ptr[i+1] += ptr[i].
  //
  // parallel_scan does not incur overhead with Kokkos::Serial, but
  // with actual parallel execution spaces, it does require multiple
  // passes over the data.  Thus, it still makes sense to have a
  // sequential fall-back.
 
  using ::Tpetra::Details::computeOffsetsFromCounts;
  if (buildInParallel) {
    computeOffsetsFromCounts(ptr, counts);
  }
 
  if (!buildInParallel || debug) {
    Kokkos::HostSpace hostMemSpace;
    auto counts_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, counts);
    auto ptr_h    = Kokkos::create_mirror_view(hostMemSpace, ptr);
 
#ifdef KOKKOS_ENABLE_SERIAL
    Kokkos::Serial hostExecSpace;
#else
    Kokkos::DefaultHostExecutionSpace hostExecSpace;
#endif  // KOKKOS_ENABLE_SERIAL
 
    computeOffsetsFromCounts(hostExecSpace, ptr_h, counts_h);
    // DEEP_COPY REVIEW - HOSTMIRROR-TO-DEVICE
    Kokkos::deep_copy(execution_space(), ptr, ptr_h);
 
    if (debug) {
      bool bad = false;
      for (offset_type i = 0; i < size; ++i) {
        if (ptr_h[i + 1] != ptr_h[i] + counts_h[i]) {
          bad = true;
        }
      }
      TEUCHOS_TEST_FOR_EXCEPTION(bad, std::logic_error,
                                 "Tpetra::Details::FixedHashTable "
                                 "constructor: computeOffsetsFromCounts gave an incorrect "
                                 "result.");
    }
  }
 
  // KJ: computeOffsetsFromCounts calls parallel_scan which does not fence.
  // This fence is necessary as we need to make sure that the offset view
  // completes before the view is used in the next functor.
  execution_space().fence();
 
  // Allocate the array of (key,value) pairs.  Don't fill it with
  // zeros, because we will fill it with actual data below.
  typedef typename val_type::non_const_type nonconst_val_type;
  nonconst_val_type val(ViewAllocateWithoutInitializing("Tpetra::FixedHashTable::pairs"),
                        theNumKeys);
 
  // Fill in the hash table's "values" (the (key,value) pairs).
  typedef FHT::FillPairs<typename val_type::non_const_type, keys_type,
                         typename ptr_type::non_const_type>
      functor_type;
  typename functor_type::value_type result(initMinKey, initMaxKey);
 
  const ValueType newStartingValue = startingValue + static_cast<ValueType>(startIndex);
  if (buildInParallel) {
    functor_type functor(val, counts, ptr, theKeys, newStartingValue,
                         initMinKey, initMaxKey);
    typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
    Kokkos::parallel_reduce("Tpetra::Details::FixedHashTable::FillPairs", range_type(0, theNumKeys), functor, result);
  } else {
    Kokkos::HostSpace hostMemSpace;
    auto counts_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, counts);
    auto ptr_h    = Kokkos::create_mirror_view_and_copy(hostMemSpace, ptr);
    auto val_h    = Kokkos::create_mirror_view_and_copy(hostMemSpace, val);
    for (offset_type k = 0; k < theNumKeys; ++k) {
      typedef typename hash_type::result_type hash_value_type;
      const KeyType key = theKeysHost[k];
      if (key > result.maxKey_) {
        result.maxKey_ = key;
      }
      if (key < result.minKey_) {
        result.minKey_ = key;
      }
      const ValueType theVal        = newStartingValue + static_cast<ValueType>(k);
      const hash_value_type hashVal = hash_type::hashFunc(key, size);
 
      // Return the old count; decrement afterwards.
      const offset_type count = counts_h[hashVal];
      --counts_h[hashVal];
      if (count == 0) {
        result.success_ = false;  // FAILURE!
        break;
      } else {
        const offset_type curPos = ptr_h[hashVal + 1] - count;
        val_h[curPos].first      = key;
        val_h[curPos].second     = theVal;
      }
    }
    Kokkos::deep_copy(counts, counts_h);  // restore
    Kokkos::deep_copy(val, val_h);        // restore
  }
 
  // FIXME (mfh 01 Jun 2015) Temporarily commented out because of
  // reports of exceptions being thrown in Albany.
  //
  // TEUCHOS_TEST_FOR_EXCEPTION
  //   (! result.success_, std::logic_error, "Tpetra::Details::FixedHashTable::"
  //    "init: Filling the hash table failed!  Please report this bug to the "
  //    "Tpetra developers.");
  (void)result;  // prevent build warning (set but unused variable)
 
  // "Commit" the computed arrays and other computed quantities.
  ptr_    = ptr;
  val_    = val;
  minKey_ = result.minKey_;
  maxKey_ = result.maxKey_;
  // We've already set firstContigKey_ and lastContigKey_ above.
}
 
template <class KeyType, class ValueType, class DeviceType>
void FixedHashTable<KeyType, ValueType, DeviceType>::
    init(const host_input_keys_type& keys,
         const host_input_vals_type& vals,
         KeyType initMinKey,
         KeyType initMaxKey) {
  Tpetra::Details::ProfilingRegion pr("Tpetra::Details::FixedHashTable::init(4-arg)");
  const offset_type numKeys = static_cast<offset_type>(keys.extent(0));
#if KOKKOS_VERSION >= 40799
  TEUCHOS_TEST_FOR_EXCEPTION(static_cast<unsigned long long>(numKeys) > static_cast<unsigned long long>(::KokkosKernels::ArithTraits<ValueType>::max()),
                             std::invalid_argument,
                             "Tpetra::Details::FixedHashTable: The number of "
                             "keys "
                                 << numKeys << " is greater than the maximum representable "
                                               "ValueType value "
                                 << ::KokkosKernels::ArithTraits<ValueType>::max() << ".");
#else
  TEUCHOS_TEST_FOR_EXCEPTION(static_cast<unsigned long long>(numKeys) > static_cast<unsigned long long>(::Kokkos::ArithTraits<ValueType>::max()),
                             std::invalid_argument,
                             "Tpetra::Details::FixedHashTable: The number of "
                             "keys "
                                 << numKeys << " is greater than the maximum representable "
                                               "ValueType value "
                                 << ::Kokkos::ArithTraits<ValueType>::max() << ".");
#endif
  TEUCHOS_TEST_FOR_EXCEPTION(numKeys > static_cast<offset_type>(INT_MAX), std::logic_error,
                             "Tpetra::"
                             "Details::FixedHashTable: This class currently only works when the number "
                             "of keys is <= INT_MAX = "
                                 << INT_MAX << ".  If this is a problem for you"
                                               ", please talk to the Tpetra developers.");
 
  // There's no need to find the first and last initial contiguous
  // keys in this case, because if we reach this init() function, then
  // hasContiguousValues() is false and so get() doesn't use the
  // initial contiguous sequence of keys.
 
  const offset_type size = hash_type::getRecommendedSize(numKeys);
#ifdef HAVE_TPETRA_DEBUG
  TEUCHOS_TEST_FOR_EXCEPTION(
      size == 0 && numKeys != 0, std::logic_error,
      "Tpetra::Details::FixedHashTable constructor: "
      "getRecommendedSize("
          << numKeys << ") returned zero, "
                        "even though the number of keys "
          << numKeys << " is nonzero.  "
                        "Please report this bug to the Tpetra developers.");
#endif  // HAVE_TPETRA_DEBUG
 
  // FIXME: Investigate a couple options:
  // 1. Allocate ptr_h, val_h directly on host and only deep_copy to ptr_ and val_ once at the end
  // 2. Do all this work as a parallel kernel with the same execution/memory spaces as ptr_ and val_
  // An old comment from MFH noted ptr_h should be zero-initialized, while val_h should not be initialized.
  // It further noted that we shouldn't need a DualView type arrangement when all setup kernels have
  // been "Kokkos-ized".
  Kokkos::HostSpace hostMemSpace;
  typename ptr_type::non_const_type ptr("Tpetra::FixedHashTable::ptr", size + 1);
  auto ptr_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, ptr);
 
  // Allocate the array of key,value pairs.  Don't waste time filling
  // it with zeros, because we will fill it with actual data below.
  using Kokkos::ViewAllocateWithoutInitializing;
  typedef typename val_type::non_const_type nonconst_val_type;
  nonconst_val_type val(ViewAllocateWithoutInitializing("Tpetra::FixedHashTable::pairs"),
                        numKeys);
  auto val_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, val);
 
  // Compute number of entries in each hash table position.
  for (offset_type k = 0; k < numKeys; ++k) {
    const typename hash_type::result_type hashVal =
        hash_type::hashFunc(keys[k], size);
    // Shift over one, so that counts[j] = ptr[j+1].  See below.
    ++ptr_h[hashVal + 1];
  }
 
  // Compute row offsets via prefix sum:
  //
  // ptr[i+1] = \sum_{j=0}^{i} counts[j].
  //
  // Thus, ptr[i+1] - ptr[i] = counts[i], so that ptr[i+1] = ptr[i] +
  // counts[i].  If we stored counts[i] in ptr[i+1] on input, then the
  // formula is ptr[i+1] += ptr[i].
  for (offset_type i = 0; i < size; ++i) {
    ptr_h[i + 1] += ptr_h[i];
  }
  // ptr[0] = 0; // We've already done this when initializing ptr above.
 
  // curRowStart[i] is the offset of the next element in row i.
  typename ptr_type::non_const_type::host_mirror_type curRowStart("Tpetra::FixedHashTable::curRowStart", size);
 
  // Fill in the hash table.
  FHT::FillPairsResult<KeyType> result(initMinKey, initMaxKey);
  for (offset_type k = 0; k < numKeys; ++k) {
    typedef typename hash_type::result_type hash_value_type;
    const KeyType key = keys[k];
    if (key > result.maxKey_) {
      result.maxKey_ = key;
    }
    if (key < result.minKey_) {
      result.minKey_ = key;
    }
    const ValueType theVal = vals[k];
    if (theVal > maxVal_) {
      maxVal_ = theVal;
    }
    if (theVal < minVal_) {
      minVal_ = theVal;
    }
    const hash_value_type hashVal = hash_type::hashFunc(key, size);
 
    const offset_type offset = curRowStart[hashVal];
    const offset_type curPos = ptr_h[hashVal] + offset;
    if (curPos >= ptr_h[hashVal + 1]) {
      result.success_ = false;  // FAILURE!
    } else {
      val_h[curPos].first  = key;
      val_h[curPos].second = theVal;
      ++curRowStart[hashVal];
    }
  }
 
  TEUCHOS_TEST_FOR_EXCEPTION(!result.success_, std::logic_error,
                             "Tpetra::Details::FixedHashTable::"
                             "init: Filling the hash table failed!  Please report this bug to the "
                             "Tpetra developers.");
 
  // "Commit" the computed arrays and other computed quantities.
  Kokkos::deep_copy(ptr, ptr_h);
  Kokkos::deep_copy(val, val_h);
 
  ptr_    = ptr;
  val_    = val;
  minKey_ = result.minKey_;
  maxKey_ = result.maxKey_;
  // We've already assigned to minVal_ and maxVal_ above.
}
 
template <class KeyType, class ValueType, class DeviceType>
bool FixedHashTable<KeyType, ValueType, DeviceType>::
    hasDuplicateKeys() {
  if (!checkedForDuplicateKeys_) {
    hasDuplicateKeys_        = checkForDuplicateKeys();
    checkedForDuplicateKeys_ = true;
  }
  return hasDuplicateKeys_;
}
 
template <class KeyType, class ValueType, class DeviceType>
bool FixedHashTable<KeyType, ValueType, DeviceType>::
    checkForDuplicateKeys() const {
  const offset_type size = this->getSize();
  // It's allowed for the hash table to have a positive number of
  // buckets (getSize()), but still store no entries (numPairs()).
  // Both cases trivially entail no duplicates.
  if (size == 0 || this->numPairs() == 0) {
    return false;
  } else {
    typedef FHT::CheckForDuplicateKeys<ptr_type, val_type> functor_type;
    functor_type functor(val_, ptr_);
    int hasDupKeys = 0;
    typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
    Kokkos::parallel_reduce("Tpetra::Details::FixedHashTable::CheckForDuplicateKeys", range_type(0, size), functor, hasDupKeys);
    return hasDupKeys > 0;
  }
}
 
template <class KeyType, class ValueType, class DeviceType>
std::string
FixedHashTable<KeyType, ValueType, DeviceType>::
    description() const {
  std::ostringstream oss;
  oss << "FixedHashTable<"
      << Teuchos::TypeNameTraits<KeyType>::name() << ","
      << Teuchos::TypeNameTraits<ValueType>::name() << ">: "
      << "{ numKeys: " << val_.extent(0)
      << ", tableSize: " << this->getSize() << " }";
  return oss.str();
}
 
template <class KeyType, class ValueType, class DeviceType>
void FixedHashTable<KeyType, ValueType, DeviceType>::
    describe(Teuchos::FancyOStream& out,
             const Teuchos::EVerbosityLevel verbLevel) const {
  using std::endl;
  using std::setw;
  using Teuchos::OSTab;
  using Teuchos::rcpFromRef;
  using Teuchos::TypeNameTraits;
  using Teuchos::VERB_DEFAULT;
  using Teuchos::VERB_EXTREME;
  using Teuchos::VERB_LOW;
  using Teuchos::VERB_NONE;
 
  // NOTE (mfh 14 May 2015) This method currently assumes UVM for
  // access to ptr_ and val_ from the host.
 
  Teuchos::EVerbosityLevel vl = verbLevel;
  if (vl == VERB_DEFAULT) vl = VERB_LOW;
 
  if (vl == VERB_NONE) {
    // do nothing
  } else if (vl == VERB_LOW) {
    out << this->description() << endl;
  } else {  // MEDIUM, HIGH or EXTREME
    out << "FixedHashTable:" << endl;
    {
      OSTab tab1(rcpFromRef(out));
 
      // const std::string label = this->getObjectLabel ();
      // if (label != "") {
      //   out << "label: " << label << endl;
      // }
      out << "Template parameters:" << endl;
      {
        OSTab tab2(rcpFromRef(out));
        out << "KeyType: " << TypeNameTraits<KeyType>::name() << endl
            << "ValueType: " << TypeNameTraits<ValueType>::name() << endl;
      }
 
      const offset_type tableSize = this->getSize();
      const offset_type numKeys   = val_.extent(0);
 
      out << "Table parameters:" << endl;
      {
        OSTab tab2(rcpFromRef(out));
        out << "numKeys: " << numKeys << endl
            << "tableSize: " << tableSize << endl;
      }
 
      if (vl >= VERB_EXTREME) {
        out << "Contents: ";
        if (tableSize == 0 || numKeys == 0) {
          out << "[]" << endl;
        } else {
          out << "[ " << endl;
          {
            OSTab tab2(rcpFromRef(out));
            for (offset_type i = 0; i < tableSize; ++i) {
              OSTab tab3(rcpFromRef(out));
              out << "[";
              for (offset_type k = ptr_[i]; k < ptr_[i + 1]; ++k) {
                out << "(" << val_[k].first << "," << val_[k].second << ")";
                if (k + 1 < ptr_[i + 1]) {
                  out << ", ";
                }
              }
              out << "]" << endl;
            }  // for each table position i
          }
          out << "]" << endl;
        }  // The table contains entries
      }    // vl >= VERB_EXTREME
    }
    out << endl;
  }  // if vl > VERB_LOW
}
 
}  // namespace Details
}  // namespace Tpetra
 
// Macro that explicitly instantiates FixedHashTable for the given
// local ordinal (LO), global ordinal (GO), and Kokkos device (NODE::device_type)
// types.  Note that FixedHashTable's first two template parameters
// occur in the opposite order of most Tpetra classes.  This is
// because FixedHashTable performs global-to-local lookup, and the
// convention in templated C++ lookup tables (such as std::map) is
// <KeyType, ValueType>.
//
// This macro must be explanded within the Tpetra::Details namespace.
// Moreover, we need (GO,LO,Host) and (LO,LO,Host)
#if defined(HAVE_TPETRA_INST_SERIAL)
#if defined(HAVE_TPETRA_INST_INT_INT)
#define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE) \
  template class Details::FixedHashTable<GO, LO, typename NODE::device_type>;
#else
#define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE)                   \
  template class Details::FixedHashTable<GO, LO, typename NODE::device_type>; \
  template class Details::FixedHashTable<LO, LO, typename NODE::device_type>;
#endif
#elif defined(HAVE_TPETRA_INST_OPENMP)
#if defined(HAVE_TPETRA_INST_INT_INT)
#define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE)                   \
  template class Details::FixedHashTable<GO, LO, typename NODE::device_type>; \
  template class Details::FixedHashTable<GO, LO, Kokkos::HostSpace::device_type>;
#else
#define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE)                                          \
  template class Details::FixedHashTable<GO, LO, typename NODE::device_type>;                        \
  template class Details::FixedHashTable<LO, LO, typename NODE::device_type>;                        \
  template class Details::FixedHashTable<GO, LO, Kokkos::Device<Kokkos::Serial, Kokkos::HostSpace>>; \
  template class Details::FixedHashTable<LO, LO, Kokkos::Device<Kokkos::Serial, Kokkos::HostSpace>>;
#endif
#else
#define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE)                       \
  template class Details::FixedHashTable<GO, LO, typename NODE::device_type>;     \
  template class Details::FixedHashTable<GO, LO, Kokkos::HostSpace::device_type>; \
  template class Details::FixedHashTable<LO, LO, Kokkos::HostSpace::device_type>;
#endif
#endif