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::ArithTraits<KeyType>::max ()),
221 maxKey_ (::Kokkos::ArithTraits<KeyType>::is_integer ?
222 ::Kokkos::ArithTraits<KeyType>::min () :
223 -::Kokkos::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::ArithTraits<key_type>::max ()),
326 initMaxKey_ (::Kokkos::ArithTraits<key_type>::is_integer ?
327 ::Kokkos::ArithTraits<key_type>::min () :
328 -::Kokkos::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::ArithTraits<KeyType>::max ();
623 const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ?
624 ::Kokkos::ArithTraits<KeyType>::min () :
625 -::Kokkos::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::ArithTraits<KeyType>::max ();
658 const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ?
659 ::Kokkos::ArithTraits<KeyType>::min () :
660 -::Kokkos::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::ArithTraits<KeyType>::max ();
705 const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ?
706 ::Kokkos::ArithTraits<KeyType>::min () :
707 -::Kokkos::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::ArithTraits<KeyType>::max ();
735 const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ?
736 ::Kokkos::ArithTraits<KeyType>::min () :
737 -::Kokkos::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::ArithTraits<KeyType>::max ();
769 const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ?
770 ::Kokkos::ArithTraits<KeyType>::min () :
771 -::Kokkos::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;
791 const char prefix[] =
"Tpetra::Details::FixedHashTable: ";
793 const offset_type numKeys =
static_cast<offset_type
> (keys.extent (0));
795 const offset_type theMaxVal = ::Kokkos::ArithTraits<offset_type>::max ();
796 const size_type maxValST =
static_cast<size_type
> (theMaxVal);
797 TEUCHOS_TEST_FOR_EXCEPTION
798 (keys.extent (0) > maxValST, std::invalid_argument, prefix <<
"The "
799 "number of keys " << keys.extent (0) <<
" does not fit in "
800 "offset_type = " << TypeNameTraits<offset_type>::name () <<
", whose "
801 "max value is " << theMaxVal <<
". This means that it is not possible to "
802 "use this constructor.");
804 TEUCHOS_TEST_FOR_EXCEPTION
805 (static_cast<unsigned long long> (numKeys) >
806 static_cast<unsigned long long> (::Kokkos::ArithTraits<ValueType>::max ()),
807 std::invalid_argument,
"Tpetra::Details::FixedHashTable: The number of "
808 "keys " << numKeys <<
" is greater than the maximum representable "
809 "ValueType value " << ::Kokkos::ArithTraits<ValueType>::max () <<
". "
810 "This means that it is not possible to use this constructor.");
811 TEUCHOS_TEST_FOR_EXCEPTION
812 (numKeys > static_cast<offset_type> (INT_MAX), std::logic_error, prefix <<
813 "This class currently only works when the number of keys is <= INT_MAX = "
814 << INT_MAX <<
". If this is a problem for you, please talk to the Tpetra "
817 const bool buildInParallel =
818 FHT::worthBuildingFixedHashTableInParallel<execution_space> ();
829 if (computeInitContigKeys) {
843 auto keys_h = Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace(),
845 firstContigKey_ = keys_h[0];
849 lastContigKey_ = firstContigKey_ + 1;
855 for (offset_type k = 1; k < numKeys; ++k) {
856 if (lastContigKey_ != keys_h[k]) {
865 firstContigKey_ = firstContigKey;
866 lastContigKey_ = lastContigKey;
869 offset_type startIndex;
871 initMinKey = std::min (initMinKey, firstContigKey_);
872 initMaxKey = std::max (initMaxKey, lastContigKey_);
873 startIndex =
static_cast<offset_type
> (lastContigKey_ - firstContigKey_);
878 const offset_type theNumKeys = numKeys - startIndex;
879 const offset_type size = hash_type::getRecommendedSize (theNumKeys);
880 #ifdef HAVE_TPETRA_DEBUG
881 TEUCHOS_TEST_FOR_EXCEPTION(
882 size == 0 && numKeys != 0, std::logic_error,
883 "Tpetra::Details::FixedHashTable constructor: "
884 "getRecommendedSize(" << numKeys <<
") returned zero, "
885 "even though the number of keys " << numKeys <<
" is nonzero. "
886 "Please report this bug to the Tpetra developers.");
887 #endif // HAVE_TPETRA_DEBUG
889 subview (keys, std::pair<offset_type, offset_type> (startIndex, numKeys));
896 typedef typename ptr_type::non_const_type counts_type;
897 counts_type counts (
"Tpetra::FixedHashTable::counts", size);
904 typename keys_type::HostMirror theKeysHost;
911 if (buildInParallel) {
912 FHT::CountBuckets<counts_type, keys_type> functor (counts, theKeys, size);
913 using range_type = Kokkos::RangePolicy<execution_space, offset_type>;
914 const char kernelLabel[] =
"Tpetra::Details::FixedHashTable CountBuckets";
916 using key_type =
typename keys_type::non_const_value_type;
917 Kokkos::pair<int, key_type> err;
918 Kokkos::parallel_reduce (kernelLabel, range_type (0, theNumKeys),
920 TEUCHOS_TEST_FOR_EXCEPTION
921 (err.first != 0, std::logic_error,
"Tpetra::Details::FixedHashTable "
922 "constructor: CountBuckets found a key " << err.second <<
" that "
923 "results in an out-of-bounds hash value.");
926 Kokkos::parallel_for (kernelLabel, range_type (0, theNumKeys), functor);
930 Kokkos::HostSpace hostMemSpace;
931 theKeysHost = Kokkos::create_mirror_view(theKeys);
934 auto countsHost = Kokkos::create_mirror_view (hostMemSpace, counts);
936 for (offset_type k = 0; k < theNumKeys; ++k) {
937 using key_type =
typename keys_type::non_const_value_type;
938 const key_type key = theKeysHost[k];
940 using hash_value_type =
typename hash_type::result_type;
941 const hash_value_type hashVal = hash_type::hashFunc (key, size);
942 TEUCHOS_TEST_FOR_EXCEPTION
943 (hashVal < hash_value_type (0) ||
944 hashVal >= hash_value_type (countsHost.extent (0)),
945 std::logic_error,
"Tpetra::Details::FixedHashTable "
946 "constructor: Sequential CountBuckets found a key " << key
947 <<
" that results in an out-of-bounds hash value.");
949 ++countsHost[hashVal];
958 execution_space().fence ();
961 typename ptr_type::non_const_type ptr (
"Tpetra::FixedHashTable::ptr", size+1);
977 if (buildInParallel) {
981 if (! buildInParallel || debug) {
982 Kokkos::HostSpace hostMemSpace;
983 auto counts_h = Kokkos::create_mirror_view_and_copy (hostMemSpace, counts);
984 auto ptr_h = Kokkos::create_mirror_view (hostMemSpace, ptr);
986 #ifdef KOKKOS_ENABLE_SERIAL
987 Kokkos::Serial hostExecSpace;
989 Kokkos::DefaultHostExecutionSpace hostExecSpace;
990 #endif // KOKKOS_ENABLE_SERIAL
998 for (offset_type i = 0; i < size; ++i) {
999 if (ptr_h[i+1] != ptr_h[i] + counts_h[i]) {
1003 TEUCHOS_TEST_FOR_EXCEPTION
1004 (bad, std::logic_error,
"Tpetra::Details::FixedHashTable "
1005 "constructor: computeOffsetsFromCounts gave an incorrect "
1013 execution_space().fence ();
1017 typedef typename val_type::non_const_type nonconst_val_type;
1018 nonconst_val_type val (ViewAllocateWithoutInitializing (
"Tpetra::FixedHashTable::pairs"),
1022 typedef FHT::FillPairs<
typename val_type::non_const_type, keys_type,
1023 typename ptr_type::non_const_type> functor_type;
1024 typename functor_type::value_type result (initMinKey, initMaxKey);
1026 const ValueType newStartingValue = startingValue +
static_cast<ValueType
> (startIndex);
1027 if (buildInParallel) {
1028 functor_type functor (val, counts, ptr, theKeys, newStartingValue,
1029 initMinKey, initMaxKey);
1030 typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
1031 Kokkos::parallel_reduce (
"Tpetra::Details::FixedHashTable::FillPairs", range_type (0, theNumKeys), functor, result);
1034 Kokkos::HostSpace hostMemSpace;
1035 auto counts_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, counts);
1036 auto ptr_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, ptr);
1037 auto val_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, val);
1038 for (offset_type k = 0; k < theNumKeys; ++k) {
1039 typedef typename hash_type::result_type hash_value_type;
1040 const KeyType key = theKeysHost[k];
1041 if (key > result.maxKey_) {
1042 result.maxKey_ = key;
1044 if (key < result.minKey_) {
1045 result.minKey_ = key;
1047 const ValueType theVal = newStartingValue +
static_cast<ValueType
> (k);
1048 const hash_value_type hashVal = hash_type::hashFunc (key, size);
1051 const offset_type count = counts_h[hashVal];
1052 --counts_h[hashVal];
1054 result.success_ =
false;
1058 const offset_type curPos = ptr_h[hashVal+1] - count;
1059 val_h[curPos].first = key;
1060 val_h[curPos].second = theVal;
1079 minKey_ = result.minKey_;
1080 maxKey_ = result.maxKey_;
1085 template<
class KeyType,
class ValueType,
class DeviceType>
1087 FixedHashTable<KeyType, ValueType, DeviceType>::
1088 init (
const host_input_keys_type& keys,
1089 const host_input_vals_type& vals,
1094 const offset_type numKeys =
static_cast<offset_type
> (keys.extent (0));
1095 TEUCHOS_TEST_FOR_EXCEPTION
1096 (static_cast<unsigned long long> (numKeys) > static_cast<unsigned long long> (::Kokkos::ArithTraits<ValueType>::max ()),
1097 std::invalid_argument,
"Tpetra::Details::FixedHashTable: The number of "
1098 "keys " << numKeys <<
" is greater than the maximum representable "
1099 "ValueType value " << ::Kokkos::ArithTraits<ValueType>::max () <<
".");
1100 TEUCHOS_TEST_FOR_EXCEPTION
1101 (numKeys > static_cast<offset_type> (INT_MAX), std::logic_error,
"Tpetra::"
1102 "Details::FixedHashTable: This class currently only works when the number "
1103 "of keys is <= INT_MAX = " << INT_MAX <<
". If this is a problem for you"
1104 ", please talk to the Tpetra developers.");
1111 const offset_type size = hash_type::getRecommendedSize (numKeys);
1112 #ifdef HAVE_TPETRA_DEBUG
1113 TEUCHOS_TEST_FOR_EXCEPTION(
1114 size == 0 && numKeys != 0, std::logic_error,
1115 "Tpetra::Details::FixedHashTable constructor: "
1116 "getRecommendedSize(" << numKeys <<
") returned zero, "
1117 "even though the number of keys " << numKeys <<
" is nonzero. "
1118 "Please report this bug to the Tpetra developers.");
1119 #endif // HAVE_TPETRA_DEBUG
1127 Kokkos::HostSpace hostMemSpace;
1128 typename ptr_type::non_const_type ptr (
"Tpetra::FixedHashTable::ptr", size + 1);
1129 auto ptr_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, ptr);
1133 using Kokkos::ViewAllocateWithoutInitializing;
1134 typedef typename val_type::non_const_type nonconst_val_type;
1135 nonconst_val_type val (ViewAllocateWithoutInitializing (
"Tpetra::FixedHashTable::pairs"),
1137 auto val_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, val);
1140 for (offset_type k = 0; k < numKeys; ++k) {
1141 const typename hash_type::result_type hashVal =
1142 hash_type::hashFunc (keys[k], size);
1154 for (offset_type i = 0; i < size; ++i) {
1155 ptr_h[i+1] += ptr_h[i];
1160 typename ptr_type::non_const_type::HostMirror curRowStart (
"Tpetra::FixedHashTable::curRowStart", size);
1163 FHT::FillPairsResult<KeyType> result (initMinKey, initMaxKey);
1164 for (offset_type k = 0; k < numKeys; ++k) {
1165 typedef typename hash_type::result_type hash_value_type;
1166 const KeyType key = keys[k];
1167 if (key > result.maxKey_) {
1168 result.maxKey_ = key;
1170 if (key < result.minKey_) {
1171 result.minKey_ = key;
1173 const ValueType theVal = vals[k];
1174 if (theVal > maxVal_) {
1177 if (theVal < minVal_) {
1180 const hash_value_type hashVal = hash_type::hashFunc (key, size);
1182 const offset_type offset = curRowStart[hashVal];
1183 const offset_type curPos = ptr_h[hashVal] + offset;
1184 if (curPos >= ptr_h[hashVal+1]) {
1185 result.success_ =
false;
1188 val_h[curPos].first = key;
1189 val_h[curPos].second = theVal;
1190 ++curRowStart[hashVal];
1194 TEUCHOS_TEST_FOR_EXCEPTION
1195 (! result.success_, std::logic_error,
"Tpetra::Details::FixedHashTable::"
1196 "init: Filling the hash table failed! Please report this bug to the "
1197 "Tpetra developers.");
1205 minKey_ = result.minKey_;
1206 maxKey_ = result.maxKey_;
1210 template <
class KeyType,
class ValueType,
class DeviceType>
1215 if (! checkedForDuplicateKeys_) {
1216 hasDuplicateKeys_ = checkForDuplicateKeys ();
1217 checkedForDuplicateKeys_ =
true;
1219 return hasDuplicateKeys_;
1222 template <
class KeyType,
class ValueType,
class DeviceType>
1227 const offset_type size = this->getSize ();
1231 if (size == 0 || this->numPairs () == 0) {
1235 typedef FHT::CheckForDuplicateKeys<ptr_type, val_type> functor_type;
1236 functor_type functor (val_, ptr_);
1238 typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
1239 Kokkos::parallel_reduce (
"Tpetra::Details::FixedHashTable::CheckForDuplicateKeys", range_type (0, size), functor, hasDupKeys);
1240 return hasDupKeys > 0;
1244 template <
class KeyType,
class ValueType,
class DeviceType>
1249 std::ostringstream oss;
1250 oss <<
"FixedHashTable<"
1251 << Teuchos::TypeNameTraits<KeyType>::name () <<
","
1252 << Teuchos::TypeNameTraits<ValueType>::name () <<
">: "
1253 <<
"{ numKeys: " << val_.extent (0)
1254 <<
", tableSize: " << this->getSize () <<
" }";
1258 template <
class KeyType,
class ValueType,
class DeviceType>
1262 const Teuchos::EVerbosityLevel verbLevel)
const
1266 using Teuchos::OSTab;
1267 using Teuchos::rcpFromRef;
1268 using Teuchos::TypeNameTraits;
1269 using Teuchos::VERB_DEFAULT;
1270 using Teuchos::VERB_NONE;
1271 using Teuchos::VERB_LOW;
1272 using Teuchos::VERB_EXTREME;
1277 Teuchos::EVerbosityLevel vl = verbLevel;
1278 if (vl == VERB_DEFAULT) vl = VERB_LOW;
1280 if (vl == VERB_NONE) {
1283 else if (vl == VERB_LOW) {
1284 out << this->description() << endl;
1287 out <<
"FixedHashTable:" << endl;
1289 OSTab tab1 (rcpFromRef (out));
1295 out <<
"Template parameters:" << endl;
1297 OSTab tab2 (rcpFromRef (out));
1298 out <<
"KeyType: " << TypeNameTraits<KeyType>::name () << endl
1299 <<
"ValueType: " << TypeNameTraits<ValueType>::name () << endl;
1302 const offset_type tableSize = this->getSize ();
1303 const offset_type numKeys = val_.extent (0);
1305 out <<
"Table parameters:" << endl;
1307 OSTab tab2 (rcpFromRef (out));
1308 out <<
"numKeys: " << numKeys << endl
1309 <<
"tableSize: " << tableSize << endl;
1312 if (vl >= VERB_EXTREME) {
1313 out <<
"Contents: ";
1314 if (tableSize == 0 || numKeys == 0) {
1315 out <<
"[]" << endl;
1317 out <<
"[ " << endl;
1319 OSTab tab2 (rcpFromRef (out));
1320 for (offset_type i = 0; i < tableSize; ++i) {
1321 OSTab tab3 (rcpFromRef (out));
1323 for (offset_type k = ptr_[i]; k < ptr_[i+1]; ++k) {
1324 out <<
"(" << val_[k].first <<
"," << val_[k].second <<
")";
1325 if (k + 1 < ptr_[i+1]) {
1351 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT_DEFAULTNODE(LO,GO) \
1352 template class FixedHashTable< GO , LO >;
1363 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, DEVICE) \
1364 template class FixedHashTable< GO , LO , DEVICE >;
1366 #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.
static KOKKOS_INLINE_FUNCTION result_type hashFunc(const argument_type &, const offset_type &)
The hash function.
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.
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.