Tpetra parallel linear algebra  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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 
53 namespace Tpetra {
54 namespace Details {
55 
56 namespace Impl {
57 
59 int getRecommendedSizeInt (const int size);
60 
61 } // namespace Impl
62 
71 template<class KeyType,
72  class DeviceType,
73  class OffsetType = typename std::make_signed<typename Kokkos::View<KeyType*, DeviceType>::size_type>::type,
74  class ResultType = int>
75 struct Hash {
79  typedef KeyType argument_type;
80 
84  typedef ResultType result_type;
85 
87  typedef OffsetType offset_type;
88 
95  static KOKKOS_INLINE_FUNCTION result_type
96  hashFunc (const argument_type& key, const offset_type& size) {
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 
131 template<class KeyType, class DeviceType, class OffsetType>
132 struct Hash<KeyType, DeviceType, OffsetType, int> {
136  typedef KeyType argument_type;
137 
141  typedef int result_type;
142 
144  typedef OffsetType offset_type;
145 
152  static KOKKOS_INLINE_FUNCTION result_type
153  hashFunc (const argument_type& key, const offset_type& size)
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
static result_type getRecommendedSize(const offset_type size)
Number of &quot;buckets&quot; that the constructor of FixedHashTable should allocate.
static result_type getRecommendedSize(const offset_type size)
Number of &quot;buckets&quot; that the constructor of FixedHashTable should allocate.
ResultType result_type
Type of the return value of the hash function.
KeyType argument_type
Type of the hash function&#39;s input.
OffsetType offset_type
Type of offsets into the hash table&#39;s array of (key,value) pairs.
static KOKKOS_INLINE_FUNCTION result_type hashFunc(const argument_type &key, const offset_type &size)
The hash function.
int result_type
Type of the return value of the hash function.
The hash function for FixedHashTable.
KeyType argument_type
Type of the hash function&#39;s input.
OffsetType offset_type
Type of offsets into the hash table&#39;s array of (key,value) pairs.
static KOKKOS_INLINE_FUNCTION result_type hashFunc(const argument_type &key, const offset_type &size)
The hash function.