Tpetra_Details_Hash.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_HASH_HPP
#define TPETRA_DETAILS_HASH_HPP

#include "Tpetra_ConfigDefs.hpp"
#ifdef TPETRA_USE_MURMUR_HASH
#include <Kokkos_Functional.hpp>  // hash function used by Kokkos::UnorderedMap
#endif                            // TPETRA_USE_MURMUR_HASH
#include <type_traits>            // make_signed

namespace Tpetra {
namespace Details {

namespace Impl {

int getRecommendedSizeInt(const int size);

}  // namespace Impl

template <class KeyType,
          class DeviceType,
          class OffsetType = typename std::make_signed<typename Kokkos::View<KeyType*, DeviceType>::size_type>::type,
          class ResultType = int>
struct Hash {
  typedef KeyType argument_type;

  typedef ResultType result_type;

  typedef OffsetType offset_type;

  static KOKKOS_INLINE_FUNCTION result_type
  hashFunc(const argument_type& /*key*/, const offset_type& /*size*/) {
    static_assert(!std::is_same<result_type, int>::value,
                  "Not yet implemented for ResultType != int");
  }

  static result_type getRecommendedSize(const offset_type /*size*/) {
    static_assert(!std::is_same<result_type, int>::value,
                  "Not yet implemented for ResultType != int");
  }
};

template <class KeyType, class DeviceType, class OffsetType>
struct Hash<KeyType, DeviceType, OffsetType, int> {
  typedef KeyType argument_type;

  typedef int result_type;

  typedef OffsetType offset_type;

  static KOKKOS_INLINE_FUNCTION result_type
  hashFunc(const argument_type& key, const offset_type& size) {
#ifdef TPETRA_USE_MURMUR_HASH
    Kokkos::pod_hash<argument_type> hash;
    const uint32_t k = hash(key);
    return static_cast<result_type>(k % size);
#else
    // We are using Epetra's hash function by default, as we have
    // observed that it is much faster than the Murmur hash
    // function. However, this is not a good hash function for general
    // sets of keys.  For our typical use case, this is good.  Use
    // Murmur hash if the maps are sparse.
    const unsigned int seed = (2654435761U);
    const int intkey        = (int)((key & 0x000000007fffffffLL) +
                             ((key & 0x7fffffff80000000LL) >> 31));
    return static_cast<result_type>((seed ^ intkey) % static_cast<int>(size));
#endif
  }

  static result_type getRecommendedSize(const offset_type size) {
    return Impl::getRecommendedSizeInt(static_cast<int>(size));
  }
};

}  // namespace Details
}  // namespace Tpetra

#endif  // TPETRA_DETAILS_HASH_HPP