Tpetra parallel linear algebra Version of the Day
Loading...
Searching...
No Matches
Tpetra_Details_Hash.hpp
1/*
2// @HEADER
3// ***********************************************************************
4//
5// Tpetra: Templated Linear Algebra Services Package
6// Copyright (2008) Sandia Corporation
7//
8// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9// the U.S. Government retains certain rights in this software.
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17//
18// 2. Redistributions in binary form must reproduce the above copyright
19// notice, this list of conditions and the following disclaimer in the
20// documentation and/or other materials provided with the distribution.
21//
22// 3. Neither the name of the Corporation nor the names of the
23// contributors may be used to endorse or promote products derived from
24// this software without specific prior written permission.
25//
26// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37//
38// Questions? Contact Michael A. Heroux (maherou@sandia.gov)
39//
40// ************************************************************************
41// @HEADER
42*/
43
44#ifndef TPETRA_DETAILS_HASH_HPP
45#define TPETRA_DETAILS_HASH_HPP
46
47#include "Tpetra_ConfigDefs.hpp"
48#ifdef TPETRA_USE_MURMUR_HASH
49# include <Kokkos_Functional.hpp> // hash function used by Kokkos::UnorderedMap
50#endif // TPETRA_USE_MURMUR_HASH
51#include <type_traits> // make_signed
52
53namespace Tpetra {
54namespace Details {
55
56namespace Impl {
57
59int getRecommendedSizeInt (const int size);
60
61} // namespace Impl
62
71template<class KeyType,
72 class DeviceType,
73 class OffsetType = typename std::make_signed<typename Kokkos::View<KeyType*, DeviceType>::size_type>::type,
74 class ResultType = int>
75struct Hash {
80
85
88
97 static_assert (! std::is_same<result_type, int>::value,
98 "Not yet implemented for ResultType != int");
99 }
100
113 static_assert (! std::is_same<result_type, int>::value,
114 "Not yet implemented for ResultType != int");
115 }
116};
117
131template<class KeyType, class DeviceType, class OffsetType>
132struct Hash<KeyType, DeviceType, OffsetType, int> {
137
141 typedef int result_type;
142
145
154 {
155#ifdef TPETRA_USE_MURMUR_HASH
156 Kokkos::pod_hash<argument_type> hash;
157 const uint32_t k = hash (key);
158 return static_cast<result_type> (k % size);
159#else
160 // We are using Epetra's hash function by default, as we have
161 // observed that it is much faster than the Murmur hash
162 // function. However, this is not a good hash function for general
163 // sets of keys. For our typical use case, this is good. Use
164 // Murmur hash if the maps are sparse.
165 const unsigned int seed = (2654435761U);
166 const int intkey = (int) ((key & 0x000000007fffffffLL) +
167 ((key & 0x7fffffff80000000LL) >> 31));
168 return static_cast<result_type> ((seed ^ intkey) % static_cast<int> (size));
169#endif
170 }
171
179 {
180 return Impl::getRecommendedSizeInt (static_cast<int> (size));
181 }
182};
183
184} // namespace Details
185} // namespace Tpetra
186
187#endif // TPETRA_DETAILS_HASH_HPP
Struct that holds views of the contents of a CrsMatrix.
Implementation details of Tpetra.
Namespace Tpetra contains the class and methods constituting the Tpetra library.
OffsetType offset_type
Type of offsets into the hash table's array of (key,value) pairs.
static KOKKOS_INLINE_FUNCTION result_type hashFunc(const argument_type &key, const offset_type &size)
The hash function.
static result_type getRecommendedSize(const offset_type size)
Number of "buckets" that the constructor of FixedHashTable should allocate.
int result_type
Type of the return value of the hash function.
The hash function for FixedHashTable.
ResultType result_type
Type of the return value of the hash function.
KeyType argument_type
Type of the hash function's input.
static KOKKOS_INLINE_FUNCTION result_type hashFunc(const argument_type &key, const offset_type &size)
The hash function.
OffsetType offset_type
Type of offsets into the hash table's array of (key,value) pairs.
static result_type getRecommendedSize(const offset_type size)
Number of "buckets" that the constructor of FixedHashTable should allocate.