/usr/include/trilinos/Tpetra_Details_Hash.hpp is in libtrilinos-tpetra-dev 12.12.1-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 | /*
// @HEADER
// ***********************************************************************
//
// Tpetra: Templated Linear Algebra Services Package
// Copyright (2008) Sandia Corporation
//
// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
// the U.S. Government retains certain rights in this software.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the Corporation nor the names of the
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Questions? Contact Michael A. Heroux (maherou@sandia.gov)
//
// ************************************************************************
// @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 {
//! Implementation of getRecommendedSize (see below) for int result_type.
int getRecommendedSizeInt (const int size);
} // namespace Impl
/// \brief The hash function for FixedHashTable.
///
/// \tparam KeyType The type of hash function inputs. Corresponds to
/// Tpetra's GlobalOrdinal type.
/// \tparam DeviceType Kokkos::Device specialization.
/// \tparam OffsetType Type of each entry of the "buckets" (offsets)
/// array \c ptr_ in FixedHashTable.
/// \tparam ResultType Type of the return value of the hash function.
template<class KeyType,
class DeviceType,
class OffsetType = typename std::make_signed<typename Kokkos::View<KeyType*, DeviceType>::size_type>::type,
class ResultType = int>
struct Hash {
/// \brief Type of the hash function's input.
///
/// This is the same typedef as found in std::hash.
typedef KeyType argument_type;
/// \brief Type of the return value of the hash function.
///
/// This is the same typedef as found in std::hash.
typedef ResultType result_type;
//! Type of offsets into the hash table's array of (key,value) pairs.
typedef OffsetType offset_type;
/// \brief The hash function.
///
/// \param key [in] The key to hash.
/// \param size [in] Number of "buckets" in the hash table.
///
/// It is legal to call this function in a Kokkos parallel kernel.
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");
}
/// \brief Number of "buckets" that the constructor of
/// FixedHashTable should allocate.
///
/// \param size [in] Number of entries in the table.
/// (FixedHashTable fixes the number of entries in its
/// constructor.)
///
/// This is included in Hash, because a correct and efficient
/// implementation is a function of result_type. The point is to
/// factor out all of the non-generic stuff into this Hash struct,
/// which can be specialized for the types of interest.
static result_type getRecommendedSize (const offset_type size) {
static_assert (! std::is_same<result_type, int>::value,
"Not yet implemented for ResultType != int");
}
};
/// \brief Specialization for ResultType = int.
///
/// \tparam KeyType The type of hash function inputs. Corresponds to
/// Tpetra's GlobalOrdinal type.
/// \tparam DeviceType Kokkos::Device specialization.
/// \tparam OffsetType Type of each entry of the "buckets" (offsets)
/// array \c ptr_ in FixedHashTable.
///
/// This hash function currently always returns \c int, no matter the
/// value type. This is unfortunate, because it limits Tpetra to have
/// <tt>LocalOrdinal = int</tt> (or smaller). I would like to fix
/// this at some point. Tpetra provides this partial specialization
/// as a hook for fixing this later.
template<class KeyType, class DeviceType, class OffsetType>
struct Hash<KeyType, DeviceType, OffsetType, int> {
/// \brief Type of the hash function's input.
///
/// This is the same typedef as found in std::hash.
typedef KeyType argument_type;
/// \brief Type of the return value of the hash function.
///
/// This is the same typedef as found in std::hash.
typedef int result_type;
//! Type of offsets into the hash table's array of (key,value) pairs.
typedef OffsetType offset_type;
/// \brief The hash function.
///
/// \param key [in] The key to hash.
/// \param size [in] Number of "buckets" in the hash table.
///
/// It is legal to call this function in a Kokkos parallel kernel.
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
}
/// \brief Number of "buckets" that the constructor of
/// FixedHashTable should allocate.
///
/// \param size [in] Number of entries in the table.
/// (FixedHashTable fixes the number of entries in its
/// constructor.)
static result_type getRecommendedSize (const offset_type size)
{
return Impl::getRecommendedSizeInt (static_cast<int> (size));
}
};
} // namespace Details
} // namespace Tpetra
#endif // TPETRA_DETAILS_HASH_HPP
|