Tpetra_Details_FixedHashTable_decl.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_DECL_HPP
#define TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP

#include "Tpetra_Details_Hash.hpp"
#include "Tpetra_Details_OrdinalTraits.hpp"
#include "Tpetra_Details_copyOffsets.hpp"
#include "Tpetra_Details_Profiling.hpp"

#include "Teuchos_Describable.hpp"
#include "Teuchos_FancyOStream.hpp"
#include "Teuchos_VerbosityLevel.hpp"

#include "Kokkos_Core.hpp"
#if KOKKOS_VERSION >= 40799
#include "KokkosKernels_ArithTraits.hpp"
#else
#include "Kokkos_ArithTraits.hpp"
#endif

namespace Tpetra {
namespace Details {

template <class KeyType,
          class ValueType,
          class DeviceType>
class FixedHashTable {
 private:
  typedef typename DeviceType::execution_space execution_space;
  typedef typename DeviceType::memory_space memory_space;
  typedef Kokkos::Device<execution_space, memory_space> device_type;

  typedef Hash<KeyType, device_type> hash_type;
  typedef typename hash_type::offset_type offset_type;

  typedef typename Kokkos::View<const offset_type*, Kokkos::LayoutLeft,
                                device_type>
      ptr_type;
  typedef typename Kokkos::View<const Kokkos::pair<KeyType, ValueType>*,
                                Kokkos::LayoutLeft, device_type>
      val_type;

  KOKKOS_INLINE_FUNCTION bool hasContiguousValues() const {
    return contiguousValues_;
  }

 public:
  typedef Kokkos::View<const KeyType*, Kokkos::LayoutLeft, device_type> keys_type;

  KOKKOS_DEFAULTED_FUNCTION FixedHashTable() = default;

  FixedHashTable(const keys_type& keys);

  FixedHashTable(const Teuchos::ArrayView<const KeyType>& keys);

  FixedHashTable(const keys_type& keys,
                 const ValueType startingValue);

  FixedHashTable(const Teuchos::ArrayView<const KeyType>& keys,
                 const ValueType startingValue);

  FixedHashTable(const keys_type& keys,
                 const KeyType firstContigKey,
                 const KeyType lastContigKey,
                 const ValueType startingValue);

  FixedHashTable(const Teuchos::ArrayView<const KeyType>& keys,
                 const KeyType firstContigKey,
                 const KeyType lastContigKey,
                 const ValueType startingValue);

  FixedHashTable(const Teuchos::ArrayView<const KeyType>& keys,
                 const Teuchos::ArrayView<const ValueType>& vals);

  template <class K, class V, class D>
  friend class FixedHashTable;

  template <class InDeviceType>
  FixedHashTable(const FixedHashTable<KeyType, ValueType, InDeviceType>& src,
                 typename std::enable_if<!std::is_same<DeviceType, InDeviceType>::value, int>::type* = NULL) {
    using Kokkos::ViewAllocateWithoutInitializing;
    typedef typename ptr_type::non_const_type nonconst_ptr_type;
    typedef typename val_type::non_const_type nonconst_val_type;

    Tpetra::Details::ProfilingRegion pr("Tpetra::Details::FixedHashTable::ctor(InDeviceType)");

    // FIXME (mfh 28 May 2015) The code below _always_ copies.  This
    // shouldn't be necessary if the input and output memory spaces
    // are the same.  However, it is always correct.

    // Different Devices may have different offset_type, because
    // offset_type comes from the memory space's size_type typedef.
    // That's why we use a specialized deep copy function here instead
    // of Kokkos::deep_copy.
    nonconst_ptr_type ptr(ViewAllocateWithoutInitializing("Tpetra::FixedHashTable::ptr"),
                          src.ptr_.extent(0));
    ::Tpetra::Details::copyOffsets(ptr, src.ptr_);
    nonconst_val_type val(ViewAllocateWithoutInitializing("Tpetra::FixedHashTable::val"),
                          src.val_.extent(0));
    // val and src.val_ have the same entry types, unlike (possibly)
    // ptr and src.ptr_.  Thus, we can use Kokkos::deep_copy here.
    // DEEP_COPY REVIEW - DEVICE-TO-DEVICE
    Kokkos::deep_copy(execution_space(), val, src.val_);

    this->ptr_                     = ptr;
    this->val_                     = val;
    this->minKey_                  = src.minKey_;
    this->maxKey_                  = src.maxKey_;
    this->minVal_                  = src.minVal_;
    this->maxVal_                  = src.maxVal_;
    this->firstContigKey_          = src.firstContigKey_;
    this->lastContigKey_           = src.lastContigKey_;
    this->contiguousValues_        = src.contiguousValues_;
    this->checkedForDuplicateKeys_ = src.checkedForDuplicateKeys_;
    this->hasDuplicateKeys_        = src.hasDuplicateKeys_;
  }

  KOKKOS_INLINE_FUNCTION ValueType get(const KeyType& key) const {
    const offset_type size = this->getSize();
    if (size == 0) {
      // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
      // because neither have the right device function markings.
      return Tpetra::Details::OrdinalTraits<ValueType>::invalid();
    }

    // If this object assumes contiguous values, then it doesn't store
    // the initial sequence of >= 1 contiguous keys in the table.
    if (this->hasContiguousValues() &&
        key >= firstContigKey_ && key <= lastContigKey_) {
      return static_cast<ValueType>(key - firstContigKey_) + this->minVal();
    }

    const typename hash_type::result_type hashVal =
        hash_type::hashFunc(key, size);

    const offset_type start = ptr_[hashVal];
    const offset_type end   = ptr_[hashVal + 1];
    for (offset_type k = start; k < end; ++k) {
      if (val_[k].first == key) {
        return val_[k].second;
      }
    }

    // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
    // because neither have the right device function markings.
    return Tpetra::Details::OrdinalTraits<ValueType>::invalid();
  }

  KOKKOS_INLINE_FUNCTION offset_type numPairs() const {
    // NOTE (mfh 26 May 2015) Using val_.extent(0) only works
    // because the table stores pairs with duplicate keys separately.
    // If the table didn't do that, we would have to keep a separate
    // numPairs_ field (remembering the size of the input array of
    // keys).
    if (this->hasContiguousValues()) {
      return val_.extent(0) + static_cast<offset_type>(lastContigKey_ - firstContigKey_);
    } else {
      return val_.extent(0);
    }
  }

  KOKKOS_INLINE_FUNCTION KeyType minKey() const {
    return minKey_;
  }

  KOKKOS_INLINE_FUNCTION KeyType maxKey() const {
    return maxKey_;
  }

  KOKKOS_INLINE_FUNCTION ValueType minVal() const {
    return minVal_;
  }

  KOKKOS_INLINE_FUNCTION ValueType maxVal() const {
    return maxVal_;
  }

  bool hasDuplicateKeys();


  std::string description() const;

  void
  describe(Teuchos::FancyOStream& out,
           const Teuchos::EVerbosityLevel verbLevel =
               Teuchos::Describable::verbLevel_default) const;

 private:
  ptr_type ptr_;
  val_type val_;

#if KOKKOS_VERSION >= 40799
  KeyType minKey_ = ::KokkosKernels::ArithTraits<KeyType>::max();
#else
  KeyType minKey_         = ::Kokkos::ArithTraits<KeyType>::max();
#endif

#if KOKKOS_VERSION >= 40799
  KeyType maxKey_ = ::KokkosKernels::ArithTraits<KeyType>::max();
#else
  KeyType maxKey_         = ::Kokkos::ArithTraits<KeyType>::max();
#endif

#if KOKKOS_VERSION >= 40799
  ValueType minVal_ = ::KokkosKernels::ArithTraits<ValueType>::max();
#else
  ValueType minVal_       = ::Kokkos::ArithTraits<ValueType>::max();
#endif

#if KOKKOS_VERSION >= 40799
  ValueType maxVal_ = ::KokkosKernels::ArithTraits<ValueType>::is_integer ? ::KokkosKernels::ArithTraits<ValueType>::min() : -::KokkosKernels::ArithTraits<ValueType>::max();
#else
  ValueType maxVal_       = ::Kokkos::ArithTraits<ValueType>::is_integer ? ::Kokkos::ArithTraits<ValueType>::min() : -::Kokkos::ArithTraits<ValueType>::max();
#endif

#if KOKKOS_VERSION >= 40799
  KeyType firstContigKey_ = ::KokkosKernels::ArithTraits<KeyType>::max();
#else
  KeyType firstContigKey_ = ::Kokkos::ArithTraits<KeyType>::max();
#endif

#if KOKKOS_VERSION >= 40799
  KeyType lastContigKey_ = ::KokkosKernels::ArithTraits<KeyType>::max();
#else
  KeyType lastContigKey_  = ::Kokkos::ArithTraits<KeyType>::max();
#endif

  bool contiguousValues_ = true;

  bool checkedForDuplicateKeys_ = true;

  bool hasDuplicateKeys_ = false;

  bool checkForDuplicateKeys() const;

  KOKKOS_INLINE_FUNCTION offset_type getSize() const {
    return ptr_.extent(0) == 0 ? static_cast<offset_type>(0) : static_cast<offset_type>(ptr_.extent(0) - 1);
  }

  typedef Kokkos::View<const KeyType*,
                       typename ptr_type::host_mirror_type::array_layout,
                       typename ptr_type::host_mirror_type::execution_space,
                       Kokkos::MemoryUnmanaged>
      host_input_keys_type;

  typedef Kokkos::View<const ValueType*,
                       typename ptr_type::host_mirror_type::array_layout,
                       typename ptr_type::host_mirror_type::execution_space,
                       Kokkos::MemoryUnmanaged>
      host_input_vals_type;

  void
  init(const keys_type& keys,
       const ValueType startingValue,
       KeyType initMinKey,
       KeyType initMaxKey,
       KeyType firstContigKey,
       KeyType lastContigKey,
       const bool computeInitContigKeys);

  void
  init(const host_input_keys_type& keys,
       const host_input_vals_type& vals,
       KeyType initMinKey,
       KeyType initMaxKey);
};

}  // namespace Details
}  // namespace Tpetra

#endif  // TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP