44 #ifndef TPETRA_DETAILS_FIXEDHASHTABLE_DEF_HPP
45 #define TPETRA_DETAILS_FIXEDHASHTABLE_DEF_HPP
47 #include "Tpetra_Details_FixedHashTable_decl.hpp"
49 #ifdef TPETRA_USE_MURMUR_HASH
50 # include "Kokkos_Functional.hpp"
51 #endif // TPETRA_USE_MURMUR_HASH
52 #include "Kokkos_ArithTraits.hpp"
53 #include "Teuchos_TypeNameTraits.hpp"
55 #include <type_traits>
78 template<
class ExecSpace>
79 bool worthBuildingFixedHashTableInParallel () {
80 return ExecSpace().concurrency() > 1;
101 template<
class CountsViewType,
103 class SizeType =
typename KeysViewType::size_type>
106 typedef CountsViewType counts_view_type;
107 typedef KeysViewType keys_view_type;
108 typedef typename CountsViewType::execution_space execution_space;
109 typedef typename CountsViewType::memory_space memory_space;
110 typedef SizeType size_type;
111 typedef typename keys_view_type::non_const_value_type key_type;
127 const keys_view_type& keys,
128 const size_type size) :
138 KOKKOS_INLINE_FUNCTION
void
144 Kokkos::atomic_increment (&counts_[hashVal]);
147 using value_type = Kokkos::pair<int, key_type>;
152 KOKKOS_INLINE_FUNCTION
void
157 const key_type keyVal = keys_[i];
159 if (hashVal < hash_value_type (0) ||
160 hashVal >= hash_value_type (counts_.extent (0))) {
165 Kokkos::atomic_increment (&counts_[hashVal]);
170 KOKKOS_INLINE_FUNCTION
void init (value_type& dst)
const
173 dst.second = key_type (0);
176 KOKKOS_INLINE_FUNCTION
void
177 join (value_type& dst,
178 const value_type& src)
const
180 const bool good = dst.first == 0 || src.first == 0;
181 dst.first = good ? 0 : dst.first;
187 counts_view_type counts_;
189 keys_view_type keys_;
204 template<
class KeyType>
206 KOKKOS_INLINE_FUNCTION
208 minKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
221 maxKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
222 ::Kokkos::Details::ArithTraits<KeyType>::min () :
223 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
226 static_assert (std::is_arithmetic<KeyType>::value,
"FillPairsResult: "
227 "KeyType must be some kind of number type.");
230 KOKKOS_INLINE_FUNCTION
231 FillPairsResult (
const KeyType& initMinKey,
232 const KeyType& initMaxKey) :
237 static_assert (std::is_arithmetic<KeyType>::value,
"FillPairsResult: "
238 "KeyType must be some kind of number type.");
275 template<
class PairsViewType,
277 class CountsViewType,
278 class SizeType =
typename KeysViewType::size_type>
281 typedef typename CountsViewType::non_const_type counts_view_type;
282 typedef typename counts_view_type::const_type offsets_view_type;
284 typedef PairsViewType pairs_view_type;
285 typedef typename KeysViewType::const_type keys_view_type;
286 typedef typename offsets_view_type::execution_space execution_space;
287 typedef typename offsets_view_type::memory_space memory_space;
288 typedef SizeType size_type;
290 typedef typename keys_view_type::non_const_value_type key_type;
291 typedef typename pairs_view_type::non_const_value_type pair_type;
315 const counts_view_type& counts,
316 const offsets_view_type& ptr,
317 const keys_view_type& keys,
318 const typename pair_type::second_type startingValue) :
323 size_ (counts.extent (0)),
324 startingValue_ (startingValue),
325 initMinKey_ (::Kokkos::Details::ArithTraits<key_type>::max ()),
326 initMaxKey_ (::Kokkos::Details::ArithTraits<key_type>::is_integer ?
327 ::Kokkos::Details::ArithTraits<key_type>::min () :
328 -::Kokkos::Details::ArithTraits<key_type>::max ())
350 const counts_view_type& counts,
351 const offsets_view_type& ptr,
352 const keys_view_type& keys,
353 const typename pair_type::second_type startingValue,
354 const key_type initMinKey,
355 const key_type initMaxKey) :
360 size_ (counts.extent (0)),
361 startingValue_ (startingValue),
362 initMinKey_ (initMinKey),
363 initMaxKey_ (initMaxKey)
374 KOKKOS_INLINE_FUNCTION
void
375 join (value_type& dst,
376 const value_type& src)
const
378 if (src.maxKey_ > dst.maxKey_) {
379 dst.maxKey_ = src.maxKey_;
381 if (src.minKey_ < dst.minKey_) {
382 dst.minKey_ = src.minKey_;
384 dst.success_ = dst.success_ && src.success_;
391 KOKKOS_INLINE_FUNCTION
void
395 typedef typename offsets_view_type::non_const_value_type offset_type;
396 typedef typename pair_type::second_type val_type;
397 typedef typename std::remove_reference< decltype( counts_[0] ) >::type atomic_incr_type;
399 const key_type key = keys_[i];
406 const val_type theVal = startingValue_ +
static_cast<val_type
> (i);
410 const offset_type count = Kokkos::atomic_fetch_add (&counts_[hashVal], atomic_incr_type(-1));
415 const offset_type curPos = ptr_[hashVal+1] - count;
417 pairs_[curPos].first = key;
418 pairs_[curPos].second = theVal;
423 pairs_view_type pairs_;
424 counts_view_type counts_;
425 offsets_view_type ptr_;
426 keys_view_type keys_;
428 typename pair_type::second_type startingValue_;
430 key_type initMinKey_;
432 key_type initMaxKey_;
458 template<
class OffsetsViewType,
460 class SizeType =
typename OffsetsViewType::size_type>
463 typedef typename OffsetsViewType::const_type offsets_view_type;
464 typedef typename PairsViewType::const_type pairs_view_type;
465 typedef typename offsets_view_type::execution_space execution_space;
466 typedef typename offsets_view_type::memory_space memory_space;
467 typedef SizeType size_type;
470 typedef int value_type;
477 const offsets_view_type& ptr) :
480 size_ (ptr_.extent (0) == 0 ?
486 KOKKOS_INLINE_FUNCTION
void init (value_type& dst)
const
492 KOKKOS_INLINE_FUNCTION
void
494 const value_type& src)
const
496 dst = dst + src > 0?1:0;
500 KOKKOS_INLINE_FUNCTION
void
503 typedef typename offsets_view_type::non_const_value_type offset_type;
504 typedef typename pairs_view_type::non_const_value_type pair_type;
505 typedef typename pair_type::first_type key_type;
511 const offset_type beg = ptr_[i];
512 const offset_type end = ptr_[i+1];
513 bool foundDuplicateKey =
false;
518 for (offset_type j = beg + 1; j < end; ++j) {
519 const key_type curKey = pairs_[j].first;
520 for (offset_type k = beg; k < j; ++k) {
521 if (pairs_[k].first == curKey) {
522 foundDuplicateKey =
true;
527 dst = (dst>0) || foundDuplicateKey?1:0;
532 pairs_view_type pairs_;
533 offsets_view_type ptr_;
543 template<
class KeyType,
class ValueType,
class DeviceType>
547 maxVal_ (keys.size () == 0 ?
548 static_cast<ValueType> (0) :
549 static_cast<ValueType> (keys.size () - 1)),
550 checkedForDuplicateKeys_ (false)
552 const ValueType startingValue =
static_cast<ValueType
> (0);
553 const KeyType initMinKey = this->minKey_;
554 const KeyType initMaxKey = this->maxKey_;
555 this->init (keys, startingValue, initMinKey, initMaxKey,
556 initMinKey, initMinKey,
false);
559 template<
class KeyType,
class ValueType,
class DeviceType>
563 maxVal_ (keys.size () == 0 ?
564 static_cast<ValueType> (0) :
565 static_cast<ValueType> (keys.size () - 1)),
566 checkedForDuplicateKeys_ (false)
568 typedef typename keys_type::non_const_type nonconst_keys_type;
573 const ValueType startingValue =
static_cast<ValueType
> (0);
574 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
576 using Kokkos::ViewAllocateWithoutInitializing;
577 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
581 const KeyType initMinKey = this->minKey_;
582 const KeyType initMaxKey = this->maxKey_;
583 this->init (keys_d, startingValue, initMinKey, initMaxKey,
584 initMinKey, initMinKey,
false);
587 template<
class KeyType,
class ValueType,
class DeviceType>
590 const ValueType startingValue) :
591 minVal_ (startingValue),
592 maxVal_ (keys.size () == 0 ?
594 static_cast<ValueType> (startingValue + keys.size () - 1)),
595 checkedForDuplicateKeys_ (false)
597 typedef typename keys_type::non_const_type nonconst_keys_type;
602 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
604 using Kokkos::ViewAllocateWithoutInitializing;
605 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
610 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
623 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
624 ::Kokkos::Details::ArithTraits<KeyType>::min () :
625 -::Kokkos::Details::ArithTraits<KeyType>::max ();
626 this->init (keys_d, startingValue, initMinKey, initMaxKey,
627 initMinKey, initMinKey,
false);
631 template<
class KeyType,
class ValueType,
class DeviceType>
634 const KeyType firstContigKey,
635 const KeyType lastContigKey,
636 const ValueType startingValue) :
637 minVal_ (startingValue),
638 maxVal_ (keys.size () == 0 ?
640 static_cast<ValueType> (startingValue + keys.size () - 1)),
641 firstContigKey_ (firstContigKey),
642 lastContigKey_ (lastContigKey),
643 checkedForDuplicateKeys_ (false)
645 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
658 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
659 ::Kokkos::Details::ArithTraits<KeyType>::min () :
660 -::Kokkos::Details::ArithTraits<KeyType>::max ();
661 this->init (keys, startingValue, initMinKey, initMaxKey,
662 firstContigKey, lastContigKey,
true);
665 template<
class KeyType,
class ValueType,
class DeviceType>
668 const KeyType firstContigKey,
669 const KeyType lastContigKey,
670 const ValueType startingValue) :
671 minVal_ (startingValue),
672 maxVal_ (keys.size () == 0 ?
674 static_cast<ValueType> (startingValue + keys.size () - 1)),
675 firstContigKey_ (firstContigKey),
676 lastContigKey_ (lastContigKey),
677 checkedForDuplicateKeys_ (false)
679 typedef typename keys_type::non_const_type nonconst_keys_type;
684 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
686 using Kokkos::ViewAllocateWithoutInitializing;
687 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
692 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
705 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
706 ::Kokkos::Details::ArithTraits<KeyType>::min () :
707 -::Kokkos::Details::ArithTraits<KeyType>::max ();
708 this->init (keys_d, startingValue, initMinKey, initMaxKey,
709 firstContigKey, lastContigKey,
true);
712 template<
class KeyType,
class ValueType,
class DeviceType>
715 const ValueType startingValue) :
716 minVal_ (startingValue),
717 maxVal_ (keys.size () == 0 ?
719 static_cast<ValueType> (startingValue + keys.size () - 1)),
720 checkedForDuplicateKeys_ (false)
722 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
735 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
736 ::Kokkos::Details::ArithTraits<KeyType>::min () :
737 -::Kokkos::Details::ArithTraits<KeyType>::max ();
738 this->init (keys, startingValue, initMinKey, initMaxKey,
739 initMinKey, initMinKey,
false);
742 template<
class KeyType,
class ValueType,
class DeviceType>
745 const Teuchos::ArrayView<const ValueType>& vals) :
746 contiguousValues_ (false),
747 checkedForDuplicateKeys_ (false)
752 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
754 host_input_vals_type vals_k (vals.size () == 0 ? NULL : vals.getRawPtr (),
756 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
769 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
770 ::Kokkos::Details::ArithTraits<KeyType>::min () :
771 -::Kokkos::Details::ArithTraits<KeyType>::max ();
772 this->init (keys_k, vals_k, initMinKey, initMaxKey);
775 template<
class KeyType,
class ValueType,
class DeviceType>
778 init (
const keys_type& keys,
779 ValueType startingValue,
782 KeyType firstContigKey,
783 KeyType lastContigKey,
784 const bool computeInitContigKeys)
786 using Kokkos::subview;
787 using Kokkos::ViewAllocateWithoutInitializing;
788 using Teuchos::TypeNameTraits;
789 typedef typename std::decay<decltype (keys.extent (0)) >::type size_type;
790 const char prefix[] =
"Tpetra::Details::FixedHashTable: ";
792 const offset_type numKeys =
static_cast<offset_type
> (keys.extent (0));
794 const offset_type theMaxVal = ::Kokkos::Details::ArithTraits<offset_type>::max ();
795 const size_type maxValST =
static_cast<size_type
> (theMaxVal);
796 TEUCHOS_TEST_FOR_EXCEPTION
797 (keys.extent (0) > maxValST, std::invalid_argument, prefix <<
"The "
798 "number of keys " << keys.extent (0) <<
" does not fit in "
799 "offset_type = " << TypeNameTraits<offset_type>::name () <<
", whose "
800 "max value is " << theMaxVal <<
". This means that it is not possible to "
801 "use this constructor.");
803 TEUCHOS_TEST_FOR_EXCEPTION
804 (static_cast<unsigned long long> (numKeys) >
805 static_cast<unsigned long long> (::Kokkos::Details::ArithTraits<ValueType>::max ()),
806 std::invalid_argument,
"Tpetra::Details::FixedHashTable: The number of "
807 "keys " << numKeys <<
" is greater than the maximum representable "
808 "ValueType value " << ::Kokkos::Details::ArithTraits<ValueType>::max () <<
". "
809 "This means that it is not possible to use this constructor.");
810 TEUCHOS_TEST_FOR_EXCEPTION
811 (numKeys > static_cast<offset_type> (INT_MAX), std::logic_error, prefix <<
812 "This class currently only works when the number of keys is <= INT_MAX = "
813 << INT_MAX <<
". If this is a problem for you, please talk to the Tpetra "
816 const bool buildInParallel =
817 FHT::worthBuildingFixedHashTableInParallel<execution_space> ();
828 if (computeInitContigKeys) {
842 auto keys_h = Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace(),
844 firstContigKey_ = keys_h[0];
848 lastContigKey_ = firstContigKey_ + 1;
854 for (offset_type k = 1; k < numKeys; ++k) {
855 if (lastContigKey_ != keys_h[k]) {
864 firstContigKey_ = firstContigKey;
865 lastContigKey_ = lastContigKey;
868 offset_type startIndex;
870 initMinKey = std::min (initMinKey, firstContigKey_);
871 initMaxKey = std::max (initMaxKey, lastContigKey_);
872 startIndex =
static_cast<offset_type
> (lastContigKey_ - firstContigKey_);
877 const offset_type theNumKeys = numKeys - startIndex;
878 const offset_type size = hash_type::getRecommendedSize (theNumKeys);
879 #ifdef HAVE_TPETRA_DEBUG
880 TEUCHOS_TEST_FOR_EXCEPTION(
881 size == 0 && numKeys != 0, std::logic_error,
882 "Tpetra::Details::FixedHashTable constructor: "
883 "getRecommendedSize(" << numKeys <<
") returned zero, "
884 "even though the number of keys " << numKeys <<
" is nonzero. "
885 "Please report this bug to the Tpetra developers.");
886 #endif // HAVE_TPETRA_DEBUG
888 subview (keys, std::pair<offset_type, offset_type> (startIndex, numKeys));
895 typedef typename ptr_type::non_const_type counts_type;
896 counts_type counts (
"Tpetra::FixedHashTable::counts", size);
903 typename keys_type::HostMirror theKeysHost;
910 if (buildInParallel) {
911 FHT::CountBuckets<counts_type, keys_type> functor (counts, theKeys, size);
912 using range_type = Kokkos::RangePolicy<execution_space, offset_type>;
913 const char kernelLabel[] =
"Tpetra::Details::FixedHashTable CountBuckets";
915 using key_type =
typename keys_type::non_const_value_type;
916 Kokkos::pair<int, key_type> err;
917 Kokkos::parallel_reduce (kernelLabel, range_type (0, theNumKeys),
919 TEUCHOS_TEST_FOR_EXCEPTION
920 (err.first != 0, std::logic_error,
"Tpetra::Details::FixedHashTable "
921 "constructor: CountBuckets found a key " << err.second <<
" that "
922 "results in an out-of-bounds hash value.");
925 Kokkos::parallel_for (kernelLabel, range_type (0, theNumKeys), functor);
929 Kokkos::HostSpace hostMemSpace;
930 theKeysHost = Kokkos::create_mirror_view(theKeys);
933 auto countsHost = Kokkos::create_mirror_view (hostMemSpace, counts);
935 for (offset_type k = 0; k < theNumKeys; ++k) {
936 using key_type =
typename keys_type::non_const_value_type;
937 const key_type key = theKeysHost[k];
939 using hash_value_type =
typename hash_type::result_type;
940 const hash_value_type hashVal = hash_type::hashFunc (key, size);
941 TEUCHOS_TEST_FOR_EXCEPTION
942 (hashVal < hash_value_type (0) ||
943 hashVal >= hash_value_type (countsHost.extent (0)),
944 std::logic_error,
"Tpetra::Details::FixedHashTable "
945 "constructor: Sequential CountBuckets found a key " << key
946 <<
" that results in an out-of-bounds hash value.");
948 ++countsHost[hashVal];
957 execution_space().fence ();
960 typename ptr_type::non_const_type ptr (
"Tpetra::FixedHashTable::ptr", size+1);
976 if (buildInParallel) {
980 if (! buildInParallel || debug) {
981 Kokkos::HostSpace hostMemSpace;
982 auto counts_h = Kokkos::create_mirror_view_and_copy (hostMemSpace, counts);
983 auto ptr_h = Kokkos::create_mirror_view (hostMemSpace, ptr);
985 #ifdef KOKKOS_ENABLE_SERIAL
986 Kokkos::Serial hostExecSpace;
988 Kokkos::DefaultHostExecutionSpace hostExecSpace;
989 #endif // KOKKOS_ENABLE_SERIAL
997 for (offset_type i = 0; i < size; ++i) {
998 if (ptr_h[i+1] != ptr_h[i] + counts_h[i]) {
1002 TEUCHOS_TEST_FOR_EXCEPTION
1003 (bad, std::logic_error,
"Tpetra::Details::FixedHashTable "
1004 "constructor: computeOffsetsFromCounts gave an incorrect "
1012 execution_space().fence ();
1016 typedef typename val_type::non_const_type nonconst_val_type;
1017 nonconst_val_type val (ViewAllocateWithoutInitializing (
"Tpetra::FixedHashTable::pairs"),
1021 typedef FHT::FillPairs<
typename val_type::non_const_type, keys_type,
1022 typename ptr_type::non_const_type> functor_type;
1023 typename functor_type::value_type result (initMinKey, initMaxKey);
1025 const ValueType newStartingValue = startingValue +
static_cast<ValueType
> (startIndex);
1026 if (buildInParallel) {
1027 functor_type functor (val, counts, ptr, theKeys, newStartingValue,
1028 initMinKey, initMaxKey);
1029 typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
1030 Kokkos::parallel_reduce (range_type (0, theNumKeys), functor, result);
1033 Kokkos::HostSpace hostMemSpace;
1034 auto counts_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, counts);
1035 auto ptr_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, ptr);
1036 auto val_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, val);
1037 for (offset_type k = 0; k < theNumKeys; ++k) {
1038 typedef typename hash_type::result_type hash_value_type;
1039 const KeyType key = theKeysHost[k];
1040 if (key > result.maxKey_) {
1041 result.maxKey_ = key;
1043 if (key < result.minKey_) {
1044 result.minKey_ = key;
1046 const ValueType theVal = newStartingValue +
static_cast<ValueType
> (k);
1047 const hash_value_type hashVal = hash_type::hashFunc (key, size);
1050 const offset_type count = counts_h[hashVal];
1051 --counts_h[hashVal];
1053 result.success_ =
false;
1057 const offset_type curPos = ptr_h[hashVal+1] - count;
1058 val_h[curPos].first = key;
1059 val_h[curPos].second = theVal;
1078 minKey_ = result.minKey_;
1079 maxKey_ = result.maxKey_;
1084 template<
class KeyType,
class ValueType,
class DeviceType>
1086 FixedHashTable<KeyType, ValueType, DeviceType>::
1087 init (
const host_input_keys_type& keys,
1088 const host_input_vals_type& vals,
1092 const offset_type numKeys =
static_cast<offset_type
> (keys.extent (0));
1093 TEUCHOS_TEST_FOR_EXCEPTION
1094 (static_cast<unsigned long long> (numKeys) > static_cast<unsigned long long> (::Kokkos::Details::ArithTraits<ValueType>::max ()),
1095 std::invalid_argument,
"Tpetra::Details::FixedHashTable: The number of "
1096 "keys " << numKeys <<
" is greater than the maximum representable "
1097 "ValueType value " << ::Kokkos::Details::ArithTraits<ValueType>::max () <<
".");
1098 TEUCHOS_TEST_FOR_EXCEPTION
1099 (numKeys > static_cast<offset_type> (INT_MAX), std::logic_error,
"Tpetra::"
1100 "Details::FixedHashTable: This class currently only works when the number "
1101 "of keys is <= INT_MAX = " << INT_MAX <<
". If this is a problem for you"
1102 ", please talk to the Tpetra developers.");
1109 const offset_type size = hash_type::getRecommendedSize (numKeys);
1110 #ifdef HAVE_TPETRA_DEBUG
1111 TEUCHOS_TEST_FOR_EXCEPTION(
1112 size == 0 && numKeys != 0, std::logic_error,
1113 "Tpetra::Details::FixedHashTable constructor: "
1114 "getRecommendedSize(" << numKeys <<
") returned zero, "
1115 "even though the number of keys " << numKeys <<
" is nonzero. "
1116 "Please report this bug to the Tpetra developers.");
1117 #endif // HAVE_TPETRA_DEBUG
1125 Kokkos::HostSpace hostMemSpace;
1126 typename ptr_type::non_const_type ptr (
"Tpetra::FixedHashTable::ptr", size + 1);
1127 auto ptr_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, ptr);
1131 using Kokkos::ViewAllocateWithoutInitializing;
1132 typedef typename val_type::non_const_type nonconst_val_type;
1133 nonconst_val_type val (ViewAllocateWithoutInitializing (
"Tpetra::FixedHashTable::pairs"),
1135 auto val_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, val);
1138 for (offset_type k = 0; k < numKeys; ++k) {
1139 const typename hash_type::result_type hashVal =
1140 hash_type::hashFunc (keys[k], size);
1152 for (offset_type i = 0; i < size; ++i) {
1153 ptr_h[i+1] += ptr_h[i];
1158 typename ptr_type::non_const_type::HostMirror curRowStart (
"Tpetra::FixedHashTable::curRowStart", size);
1161 FHT::FillPairsResult<KeyType> result (initMinKey, initMaxKey);
1162 for (offset_type k = 0; k < numKeys; ++k) {
1163 typedef typename hash_type::result_type hash_value_type;
1164 const KeyType key = keys[k];
1165 if (key > result.maxKey_) {
1166 result.maxKey_ = key;
1168 if (key < result.minKey_) {
1169 result.minKey_ = key;
1171 const ValueType theVal = vals[k];
1172 if (theVal > maxVal_) {
1175 if (theVal < minVal_) {
1178 const hash_value_type hashVal = hash_type::hashFunc (key, size);
1180 const offset_type offset = curRowStart[hashVal];
1181 const offset_type curPos = ptr_h[hashVal] + offset;
1182 if (curPos >= ptr_h[hashVal+1]) {
1183 result.success_ =
false;
1186 val_h[curPos].first = key;
1187 val_h[curPos].second = theVal;
1188 ++curRowStart[hashVal];
1192 TEUCHOS_TEST_FOR_EXCEPTION
1193 (! result.success_, std::logic_error,
"Tpetra::Details::FixedHashTable::"
1194 "init: Filling the hash table failed! Please report this bug to the "
1195 "Tpetra developers.");
1203 minKey_ = result.minKey_;
1204 maxKey_ = result.maxKey_;
1208 template <
class KeyType,
class ValueType,
class DeviceType>
1213 if (! checkedForDuplicateKeys_) {
1214 hasDuplicateKeys_ = checkForDuplicateKeys ();
1215 checkedForDuplicateKeys_ =
true;
1217 return hasDuplicateKeys_;
1220 template <
class KeyType,
class ValueType,
class DeviceType>
1225 const offset_type size = this->getSize ();
1229 if (size == 0 || this->numPairs () == 0) {
1233 typedef FHT::CheckForDuplicateKeys<ptr_type, val_type> functor_type;
1234 functor_type functor (val_, ptr_);
1236 typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
1237 Kokkos::parallel_reduce (range_type (0, size), functor, hasDupKeys);
1238 return hasDupKeys > 0;
1242 template <
class KeyType,
class ValueType,
class DeviceType>
1247 std::ostringstream oss;
1248 oss <<
"FixedHashTable<"
1249 << Teuchos::TypeNameTraits<KeyType>::name () <<
","
1250 << Teuchos::TypeNameTraits<ValueType>::name () <<
">: "
1251 <<
"{ numKeys: " << val_.extent (0)
1252 <<
", tableSize: " << this->getSize () <<
" }";
1256 template <
class KeyType,
class ValueType,
class DeviceType>
1260 const Teuchos::EVerbosityLevel verbLevel)
const
1264 using Teuchos::OSTab;
1265 using Teuchos::rcpFromRef;
1266 using Teuchos::TypeNameTraits;
1267 using Teuchos::VERB_DEFAULT;
1268 using Teuchos::VERB_NONE;
1269 using Teuchos::VERB_LOW;
1270 using Teuchos::VERB_EXTREME;
1275 Teuchos::EVerbosityLevel vl = verbLevel;
1276 if (vl == VERB_DEFAULT) vl = VERB_LOW;
1278 if (vl == VERB_NONE) {
1281 else if (vl == VERB_LOW) {
1282 out << this->description() << endl;
1285 out <<
"FixedHashTable:" << endl;
1287 OSTab tab1 (rcpFromRef (out));
1293 out <<
"Template parameters:" << endl;
1295 OSTab tab2 (rcpFromRef (out));
1296 out <<
"KeyType: " << TypeNameTraits<KeyType>::name () << endl
1297 <<
"ValueType: " << TypeNameTraits<ValueType>::name () << endl;
1300 const offset_type tableSize = this->getSize ();
1301 const offset_type numKeys = val_.extent (0);
1303 out <<
"Table parameters:" << endl;
1305 OSTab tab2 (rcpFromRef (out));
1306 out <<
"numKeys: " << numKeys << endl
1307 <<
"tableSize: " << tableSize << endl;
1310 if (vl >= VERB_EXTREME) {
1311 out <<
"Contents: ";
1312 if (tableSize == 0 || numKeys == 0) {
1313 out <<
"[]" << endl;
1315 out <<
"[ " << endl;
1317 OSTab tab2 (rcpFromRef (out));
1318 for (offset_type i = 0; i < tableSize; ++i) {
1319 OSTab tab3 (rcpFromRef (out));
1321 for (offset_type k = ptr_[i]; k < ptr_[i+1]; ++k) {
1322 out <<
"(" << val_[k].first <<
"," << val_[k].second <<
")";
1323 if (k + 1 < ptr_[i+1]) {
1349 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT_DEFAULTNODE(LO,GO) \
1350 template class FixedHashTable< GO , LO >;
1361 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, DEVICE) \
1362 template class FixedHashTable< GO , LO , DEVICE >;
1364 #endif // TPETRA_DETAILS_FIXEDHASHTABLE_DEF_HPP
CheckForDuplicateKeys(const pairs_view_type &pairs, const offsets_view_type &ptr)
Constructor.
Parallel reduce functor for filling the FixedHashTable, and computing the min and max keys...
FillPairs(const pairs_view_type &pairs, const counts_view_type &counts, const offsets_view_type &ptr, const keys_view_type &keys, const typename pair_type::second_type startingValue, const key_type initMinKey, const key_type initMaxKey)
Constructor that takes initial min and max key values.
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
KOKKOS_DEFAULTED_FUNCTION FixedHashTable()=default
Default constructor; makes an empty table.
KOKKOS_INLINE_FUNCTION void operator()(const size_type &i) const
Do this for every entry of keys_.
void describe(Teuchos::FancyOStream &out, const Teuchos::EVerbosityLevel verbLevel=Teuchos::Describable::verbLevel_default) const
Print this object with the given verbosity to the output stream.
ResultType result_type
Type of the return value of the hash function.
Parallel for functor for counting "buckets" in the FixedHashTable.
static bool debug()
Whether Tpetra is in debug mode.
bool success_
Whether fill succeeded (it can only fail on a bug)
KeyType maxKey_
The current maximum key.
void deep_copy(MultiVector< DS, DL, DG, DN > &dst, const MultiVector< SS, SL, SG, SN > &src)
Copy the contents of the MultiVector src into dst.
The hash function for FixedHashTable.
Declare and define the functions Tpetra::Details::computeOffsetsFromCounts and Tpetra::computeOffsets...
std::string description() const
Implementation of Teuchos::Describable interface.
KOKKOS_INLINE_FUNCTION void operator()(const size_type &i, value_type &dst) const
Parallel loop body; do this for every entry of keys_.
FillPairs(const pairs_view_type &pairs, const counts_view_type &counts, const offsets_view_type &ptr, const keys_view_type &keys, const typename pair_type::second_type startingValue)
Constructor.
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
bool hasDuplicateKeys()
Whether the table has any duplicate keys.
static KOKKOS_INLINE_FUNCTION result_type hashFunc(const argument_type &key, const offset_type &size)
The hash function.
CountBuckets(const counts_view_type &counts, const keys_view_type &keys, const size_type size)
Constructor.
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
Functor for checking whether a FixedHashTable has one or more duplicate entries.
KOKKOS_INLINE_FUNCTION void join(value_type &dst, const value_type &src) const
Combine two intermediate reduction results.
OffsetsViewType::non_const_value_type computeOffsetsFromCounts(const ExecutionSpace &execSpace, const OffsetsViewType &ptr, const CountsViewType &counts)
Compute offsets from counts.
KeyType minKey_
The current minimum key.
Reduction result for FillPairs functor below.
KOKKOS_INLINE_FUNCTION void operator()(const size_type &i, value_type &dst) const
Parallel loop body.
Kokkos::View< const KeyType *, Kokkos::LayoutLeft, device_type > keys_type
Type of a 1-D Kokkos::View (array) used to store keys.
Declaration of Tpetra::Details::Behavior, a class that describes Tpetra's behavior.