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" 54 #include <type_traits> 79 template<
class ExecSpace>
80 struct WorthBuildingFixedHashTableInParallel {
81 typedef typename ExecSpace::execution_space execution_space;
83 static bool isWorth () {
86 return execution_space::max_hardware_threads () > 1;
90 #ifdef KOKKOS_HAVE_CUDA 92 struct WorthBuildingFixedHashTableInParallel<
Kokkos::Cuda> {
97 static bool isWorth () {
101 #endif // KOKKOS_HAVE_CUDA 115 template<
class ExecSpace>
116 bool worthBuildingFixedHashTableInParallel () {
117 return WorthBuildingFixedHashTableInParallel<ExecSpace>::isWorth ();
128 template<
class KeyType,
130 class InputExecSpace,
131 class OutputExecSpace,
132 const bool mustDeepCopy =
133 ! std::is_same<
typename InputExecSpace::memory_space,
134 typename OutputExecSpace::memory_space>::value>
135 struct DeepCopyIfNeeded {
141 template<
class KeyType,
143 class InputExecSpace,
144 class OutputExecSpace>
145 struct DeepCopyIfNeeded<KeyType, ArrayLayout, InputExecSpace, OutputExecSpace, true>
147 typedef Kokkos::View<
const KeyType*, ArrayLayout,
148 InputExecSpace, Kokkos::MemoryUnmanaged> input_view_type;
154 typedef Kokkos::View<const KeyType*, ArrayLayout, OutputExecSpace> output_view_type;
156 static output_view_type copy (
const input_view_type& src) {
157 typedef typename output_view_type::non_const_type NC;
159 NC dst (Kokkos::ViewAllocateWithoutInitializing (src.tracker ().label ()),
162 return output_view_type (dst);
167 template<
class KeyType,
169 class InputExecSpace,
170 class OutputExecSpace>
171 struct DeepCopyIfNeeded<KeyType, ArrayLayout, InputExecSpace, OutputExecSpace, false> {
172 typedef Kokkos::View<
const KeyType*, ArrayLayout,
173 InputExecSpace, Kokkos::MemoryUnmanaged> input_view_type;
174 typedef Kokkos::View<
const KeyType*, ArrayLayout, OutputExecSpace,
175 Kokkos::MemoryUnmanaged> output_view_type;
177 static output_view_type copy (
const input_view_type& src) {
178 return output_view_type (src);
200 template<
class CountsViewType,
202 class SizeType =
typename KeysViewType::size_type>
205 typedef CountsViewType counts_view_type;
206 typedef KeysViewType keys_view_type;
207 typedef typename CountsViewType::execution_space execution_space;
208 typedef typename CountsViewType::memory_space memory_space;
209 typedef SizeType size_type;
210 typedef typename keys_view_type::non_const_value_type key_type;
226 const keys_view_type& keys,
227 const size_type size) :
237 KOKKOS_INLINE_FUNCTION
void 243 Kokkos::atomic_fetch_add (&counts_[hashVal], 1);
248 counts_view_type counts_;
250 keys_view_type keys_;
265 template<
class KeyType>
267 KOKKOS_INLINE_FUNCTION
269 minKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
282 maxKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
283 ::Kokkos::Details::ArithTraits<KeyType>::min () :
284 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
287 static_assert (std::is_arithmetic<KeyType>::value,
"FillPairsResult: " 288 "KeyType must be some kind of number type.");
291 KOKKOS_INLINE_FUNCTION
293 const KeyType& initMaxKey) :
298 static_assert (std::is_arithmetic<KeyType>::value,
"FillPairsResult: " 299 "KeyType must be some kind of number type.");
336 template<
class PairsViewType,
338 class CountsViewType,
339 class SizeType =
typename KeysViewType::size_type>
342 typedef typename CountsViewType::non_const_type counts_view_type;
343 typedef typename counts_view_type::const_type offsets_view_type;
345 typedef PairsViewType pairs_view_type;
346 typedef typename KeysViewType::const_type keys_view_type;
347 typedef typename offsets_view_type::execution_space execution_space;
348 typedef typename offsets_view_type::memory_space memory_space;
349 typedef SizeType size_type;
351 typedef typename keys_view_type::non_const_value_type key_type;
352 typedef typename pairs_view_type::non_const_value_type pair_type;
376 const counts_view_type& counts,
377 const offsets_view_type& ptr,
378 const keys_view_type& keys,
379 const typename pair_type::second_type startingValue) :
384 size_ (counts.dimension_0 ()),
385 startingValue_ (startingValue),
386 initMinKey_ (::
Kokkos::
Details::ArithTraits<key_type>::max ()),
387 initMaxKey_ (::
Kokkos::
Details::ArithTraits<key_type>::is_integer ?
411 const counts_view_type& counts,
412 const offsets_view_type& ptr,
413 const keys_view_type& keys,
414 const typename pair_type::second_type startingValue,
415 const key_type initMinKey,
416 const key_type initMaxKey) :
421 size_ (counts.dimension_0 ()),
422 startingValue_ (startingValue),
423 initMinKey_ (initMinKey),
424 initMaxKey_ (initMaxKey)
435 KOKKOS_INLINE_FUNCTION
void 436 join (
volatile value_type& dst,
437 const volatile value_type& src)
const 439 if (src.maxKey_ > dst.maxKey_) {
440 dst.maxKey_ = src.maxKey_;
442 if (src.minKey_ < dst.minKey_) {
443 dst.minKey_ = src.minKey_;
445 dst.success_ = dst.success_ && src.success_;
452 KOKKOS_INLINE_FUNCTION
void 456 typedef typename offsets_view_type::non_const_value_type offset_type;
457 typedef typename pair_type::second_type val_type;
459 const key_type key = keys_[i];
466 const val_type theVal = startingValue_ +
static_cast<val_type
> (i);
470 const offset_type count = Kokkos::atomic_fetch_add (&counts_[hashVal], -1);
475 const offset_type curPos = ptr_[hashVal+1] - count;
477 pairs_[curPos].first = key;
478 pairs_[curPos].second = theVal;
483 pairs_view_type pairs_;
484 counts_view_type counts_;
485 offsets_view_type ptr_;
486 keys_view_type keys_;
488 typename pair_type::second_type startingValue_;
490 key_type initMinKey_;
492 key_type initMaxKey_;
518 template<
class OffsetsViewType,
520 class SizeType =
typename OffsetsViewType::size_type>
523 typedef typename OffsetsViewType::const_type offsets_view_type;
524 typedef typename PairsViewType::const_type pairs_view_type;
525 typedef typename offsets_view_type::execution_space execution_space;
526 typedef typename offsets_view_type::memory_space memory_space;
527 typedef SizeType size_type;
530 typedef int value_type;
537 const offsets_view_type& ptr) :
540 size_ (ptr_.dimension_0 () == 0 ?
542 ptr_.dimension_0 () - 1)
546 KOKKOS_INLINE_FUNCTION
void init (value_type& dst)
const 552 KOKKOS_INLINE_FUNCTION
void 553 join (
volatile value_type& dst,
554 const volatile value_type& src)
const 556 dst = dst + src > 0?1:0;
560 KOKKOS_INLINE_FUNCTION
void 563 typedef typename offsets_view_type::non_const_value_type offset_type;
564 typedef typename pairs_view_type::non_const_value_type pair_type;
565 typedef typename pair_type::first_type key_type;
571 const offset_type beg = ptr_[i];
572 const offset_type end = ptr_[i+1];
573 bool foundDuplicateKey =
false;
578 for (offset_type j = beg + 1; j < end; ++j) {
579 const key_type curKey = pairs_[j].first;
580 for (offset_type k = beg; k < j; ++k) {
581 if (pairs_[k].first == curKey) {
582 foundDuplicateKey =
true;
587 dst = (dst>0) || foundDuplicateKey?1:0;
592 pairs_view_type pairs_;
593 offsets_view_type ptr_;
603 template<
class KeyType,
class ValueType,
class DeviceType>
613 return keys_.dimension_0 () == val_.dimension_0 ();
616 template<
class KeyType,
class ValueType,
class DeviceType>
625 template<
class KeyType,
class ValueType,
class DeviceType>
629 maxKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
633 maxVal_ (::
Kokkos::
Details::ArithTraits<ValueType>::is_integer ?
636 firstContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::max ()),
637 lastContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
640 contiguousValues_ (true),
641 checkedForDuplicateKeys_ (true),
642 hasDuplicateKeys_ (false)
644 #ifdef HAVE_TPETRA_DEBUG 646 #endif // HAVE_TPETRA_DEBUG 649 template<
class KeyType,
class ValueType,
class DeviceType>
654 maxKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
658 maxVal_ (keys.size () == 0 ?
659 static_cast<ValueType> (0) :
660 static_cast<ValueType> (keys.size () - 1)),
661 firstContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::max ()),
662 lastContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
665 contiguousValues_ (true),
666 checkedForDuplicateKeys_ (false),
667 hasDuplicateKeys_ (false)
669 const ValueType startingValue =
static_cast<ValueType
> (0);
670 const KeyType initMinKey = this->minKey_;
671 const KeyType initMaxKey = this->maxKey_;
672 this->init (keys, startingValue, initMinKey, initMaxKey,
673 initMinKey, initMinKey,
false);
675 #ifdef HAVE_TPETRA_DEBUG 677 #endif // HAVE_TPETRA_DEBUG 680 template<
class KeyType,
class ValueType,
class DeviceType>
683 const bool keepKeys) :
685 maxKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
689 maxVal_ (keys.size () == 0 ?
690 static_cast<ValueType> (0) :
691 static_cast<ValueType> (keys.size () - 1)),
692 firstContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::max ()),
693 lastContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
696 contiguousValues_ (true),
697 checkedForDuplicateKeys_ (false),
698 hasDuplicateKeys_ (false)
700 typedef typename keys_type::non_const_type nonconst_keys_type;
705 const ValueType startingValue =
static_cast<ValueType
> (0);
706 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
708 using Kokkos::ViewAllocateWithoutInitializing;
709 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
710 keys_k.dimension_0 ());
712 const KeyType initMinKey = this->minKey_;
713 const KeyType initMaxKey = this->maxKey_;
714 this->init (keys_d, startingValue, initMinKey, initMaxKey,
715 initMinKey, initMinKey,
false);
718 #ifdef HAVE_TPETRA_DEBUG 719 typedef typename keys_type::size_type size_type;
720 TEUCHOS_TEST_FOR_EXCEPTION
721 (keys_.dimension_0 () !=
static_cast<size_type
> (keys.size ()),
722 std::logic_error,
"Tpetra::Details::FixedHashTable constructor: " 723 "keepKeys is true, but on return, keys_.dimension_0() = " <<
724 keys_.dimension_0 () <<
" != keys.size() = " << keys.size () <<
725 ". Please report this bug to the Tpetra developers.");
726 #endif // HAVE_TPETRA_DEBUG 729 #ifdef HAVE_TPETRA_DEBUG 731 #endif // HAVE_TPETRA_DEBUG 734 template<
class KeyType,
class ValueType,
class DeviceType>
737 const ValueType startingValue,
738 const bool keepKeys) :
740 maxKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
743 minVal_ (startingValue),
744 maxVal_ (keys.size () == 0 ?
746 static_cast<ValueType> (startingValue + keys.size () - 1)),
747 firstContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::max ()),
748 lastContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
751 contiguousValues_ (true),
752 checkedForDuplicateKeys_ (false),
753 hasDuplicateKeys_ (false)
755 typedef typename keys_type::non_const_type nonconst_keys_type;
760 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
762 using Kokkos::ViewAllocateWithoutInitializing;
763 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
764 keys_k.dimension_0 ());
767 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
780 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
781 ::Kokkos::Details::ArithTraits<KeyType>::min () :
782 -::Kokkos::Details::ArithTraits<KeyType>::max ();
783 this->init (keys_d, startingValue, initMinKey, initMaxKey,
784 initMinKey, initMinKey,
false);
787 #ifdef HAVE_TPETRA_DEBUG 788 typedef typename keys_type::size_type size_type;
789 TEUCHOS_TEST_FOR_EXCEPTION
790 (keys_.dimension_0 () !=
static_cast<size_type
> (keys.size ()),
791 std::logic_error,
"Tpetra::Details::FixedHashTable constructor: " 792 "keepKeys is true, but on return, keys_.dimension_0() = " <<
793 keys_.dimension_0 () <<
" != keys.size() = " << keys.size () <<
794 ". Please report this bug to the Tpetra developers.");
795 #endif // HAVE_TPETRA_DEBUG 798 #ifdef HAVE_TPETRA_DEBUG 800 #endif // HAVE_TPETRA_DEBUG 803 template<
class KeyType,
class ValueType,
class DeviceType>
806 const KeyType firstContigKey,
807 const KeyType lastContigKey,
808 const ValueType startingValue,
809 const bool keepKeys) :
811 maxKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
814 minVal_ (startingValue),
815 maxVal_ (keys.size () == 0 ?
817 static_cast<ValueType> (startingValue + keys.size () - 1)),
818 firstContigKey_ (firstContigKey),
819 lastContigKey_ (lastContigKey),
820 contiguousValues_ (true),
821 checkedForDuplicateKeys_ (false),
822 hasDuplicateKeys_ (false)
824 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
837 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
838 ::Kokkos::Details::ArithTraits<KeyType>::min () :
839 -::Kokkos::Details::ArithTraits<KeyType>::max ();
840 this->init (keys, startingValue, initMinKey, initMaxKey,
841 firstContigKey, lastContigKey,
true);
844 #ifdef HAVE_TPETRA_DEBUG 845 typedef typename keys_type::size_type size_type;
846 TEUCHOS_TEST_FOR_EXCEPTION
847 (keys_.dimension_0 () !=
static_cast<size_type
> (keys.size ()),
848 std::logic_error,
"Tpetra::Details::FixedHashTable constructor: " 849 "keepKeys is true, but on return, keys_.dimension_0() = " <<
850 keys_.dimension_0 () <<
" != keys.size() = " << keys.size () <<
851 ". Please report this bug to the Tpetra developers.");
852 #endif // HAVE_TPETRA_DEBUG 855 #ifdef HAVE_TPETRA_DEBUG 857 #endif // HAVE_TPETRA_DEBUG 860 template<
class KeyType,
class ValueType,
class DeviceType>
863 const KeyType firstContigKey,
864 const KeyType lastContigKey,
865 const ValueType startingValue,
866 const bool keepKeys) :
868 maxKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
871 minVal_ (startingValue),
872 maxVal_ (keys.size () == 0 ?
874 static_cast<ValueType> (startingValue + keys.size () - 1)),
875 firstContigKey_ (firstContigKey),
876 lastContigKey_ (lastContigKey),
877 contiguousValues_ (true),
878 checkedForDuplicateKeys_ (false),
879 hasDuplicateKeys_ (false)
881 typedef typename keys_type::non_const_type nonconst_keys_type;
886 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
888 using Kokkos::ViewAllocateWithoutInitializing;
889 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
890 keys_k.dimension_0 ());
893 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
906 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
907 ::Kokkos::Details::ArithTraits<KeyType>::min () :
908 -::Kokkos::Details::ArithTraits<KeyType>::max ();
909 this->init (keys_d, startingValue, initMinKey, initMaxKey,
910 firstContigKey, lastContigKey,
true);
913 #ifdef HAVE_TPETRA_DEBUG 914 typedef typename keys_type::size_type size_type;
915 TEUCHOS_TEST_FOR_EXCEPTION
916 (keys_.dimension_0 () !=
static_cast<size_type
> (keys.size ()),
917 std::logic_error,
"Tpetra::Details::FixedHashTable constructor: " 918 "keepKeys is true, but on return, keys_.dimension_0() = " <<
919 keys_.dimension_0 () <<
" != keys.size() = " << keys.size () <<
920 ". Please report this bug to the Tpetra developers.");
921 #endif // HAVE_TPETRA_DEBUG 924 #ifdef HAVE_TPETRA_DEBUG 926 #endif // HAVE_TPETRA_DEBUG 929 template<
class KeyType,
class ValueType,
class DeviceType>
932 const ValueType startingValue) :
935 maxKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
938 minVal_ (startingValue),
939 maxVal_ (keys.size () == 0 ?
941 static_cast<ValueType> (startingValue + keys.size () - 1)),
942 firstContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::max ()),
943 lastContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
946 contiguousValues_ (true),
947 checkedForDuplicateKeys_ (false),
948 hasDuplicateKeys_ (false)
950 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
963 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
964 ::Kokkos::Details::ArithTraits<KeyType>::min () :
965 -::Kokkos::Details::ArithTraits<KeyType>::max ();
966 this->init (keys, startingValue, initMinKey, initMaxKey,
967 initMinKey, initMinKey,
false);
969 #ifdef HAVE_TPETRA_DEBUG 971 #endif // HAVE_TPETRA_DEBUG 974 template<
class KeyType,
class ValueType,
class DeviceType>
977 const Teuchos::ArrayView<const ValueType>& vals) :
979 maxKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
983 maxVal_ (::
Kokkos::
Details::ArithTraits<ValueType>::is_integer ?
986 firstContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::max ()),
987 lastContigKey_ (::
Kokkos::
Details::ArithTraits<KeyType>::is_integer ?
990 contiguousValues_ (false),
991 checkedForDuplicateKeys_ (false),
992 hasDuplicateKeys_ (false)
997 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
999 host_input_vals_type vals_k (vals.size () == 0 ? NULL : vals.getRawPtr (),
1001 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
1014 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
1015 ::Kokkos::Details::ArithTraits<KeyType>::min () :
1016 -::Kokkos::Details::ArithTraits<KeyType>::max ();
1017 this->init (keys_k, vals_k, initMinKey, initMaxKey);
1019 #ifdef HAVE_TPETRA_DEBUG 1021 #endif // HAVE_TPETRA_DEBUG 1024 template<
class KeyType,
class ValueType,
class DeviceType>
1027 init (
const keys_type& keys,
1028 ValueType startingValue,
1031 KeyType firstContigKey,
1032 KeyType lastContigKey,
1033 const bool computeInitContigKeys)
1035 using Kokkos::subview;
1036 using Kokkos::ViewAllocateWithoutInitializing;
1037 using Teuchos::TypeNameTraits;
1038 typedef typename std::decay<decltype (keys.dimension_0 ()) >::type size_type;
1039 const char prefix[] =
"Tpetra::Details::FixedHashTable: ";
1041 const offset_type numKeys =
static_cast<offset_type
> (keys.dimension_0 ());
1043 const offset_type maxVal = ::Kokkos::Details::ArithTraits<offset_type>::max ();
1044 const size_type maxValST =
static_cast<size_type
> (maxVal);
1045 TEUCHOS_TEST_FOR_EXCEPTION
1046 (keys.dimension_0 () > maxValST, std::invalid_argument, prefix <<
"The " 1047 "number of keys " << keys.dimension_0 () <<
" does not fit in " 1048 "offset_type = " << TypeNameTraits<offset_type>::name () <<
", whose " 1049 "max value is " << maxVal <<
". This means that it is not possible to " 1050 "use this constructor.");
1052 TEUCHOS_TEST_FOR_EXCEPTION
1053 (static_cast<unsigned long long> (numKeys) >
1054 static_cast<unsigned long long> (::Kokkos::Details::ArithTraits<ValueType>::max ()),
1055 std::invalid_argument,
"Tpetra::Details::FixedHashTable: The number of " 1056 "keys " << numKeys <<
" is greater than the maximum representable " 1057 "ValueType value " << ::Kokkos::Details::ArithTraits<ValueType>::max () <<
". " 1058 "This means that it is not possible to use this constructor.");
1059 TEUCHOS_TEST_FOR_EXCEPTION
1060 (numKeys > static_cast<offset_type> (INT_MAX), std::logic_error, prefix <<
1061 "This class currently only works when the number of keys is <= INT_MAX = " 1062 << INT_MAX <<
". If this is a problem for you, please talk to the Tpetra " 1065 const bool buildInParallel =
1066 FHT::worthBuildingFixedHashTableInParallel<execution_space> ();
1076 if (computeInitContigKeys) {
1095 firstContigKey_ = keys[0];
1099 lastContigKey_ = firstContigKey_ + 1;
1105 for (offset_type k = 1; k < numKeys; ++k) {
1106 if (lastContigKey_ != keys[k]) {
1115 firstContigKey_ = firstContigKey;
1116 lastContigKey_ = lastContigKey;
1119 offset_type startIndex;
1121 initMinKey = std::min (initMinKey, firstContigKey_);
1122 initMaxKey = std::max (initMaxKey, lastContigKey_);
1123 startIndex =
static_cast<offset_type
> (lastContigKey_ - firstContigKey_);
1128 const offset_type theNumKeys = numKeys - startIndex;
1129 const offset_type size = hash_type::getRecommendedSize (theNumKeys);
1130 #ifdef HAVE_TPETRA_DEBUG 1131 TEUCHOS_TEST_FOR_EXCEPTION(
1132 size == 0 && numKeys != 0, std::logic_error,
1133 "Tpetra::Details::FixedHashTable constructor: " 1134 "getRecommendedSize(" << numKeys <<
") returned zero, " 1135 "even though the number of keys " << numKeys <<
" is nonzero. " 1136 "Please report this bug to the Tpetra developers.");
1137 #endif // HAVE_TPETRA_DEBUG 1139 subview (keys, std::pair<offset_type, offset_type> (startIndex, numKeys));
1146 typedef typename ptr_type::non_const_type counts_type;
1147 counts_type counts (
"FixedHashTable::counts", size);
1158 if (buildInParallel) {
1159 FHT::CountBuckets<counts_type, keys_type> functor (counts, theKeys, size);
1160 Kokkos::parallel_for (theNumKeys, functor);
1167 auto countsHost = Kokkos::create_mirror_view (counts);
1171 for (offset_type k = 0; k < theNumKeys; ++k) {
1172 typedef typename hash_type::result_type hash_value_type;
1173 const hash_value_type hashVal = hash_type::hashFunc (theKeys[k], size);
1174 ++countsHost[hashVal];
1181 execution_space::fence ();
1184 typename ptr_type::non_const_type ptr (
"FixedHashTable::ptr", size+1);
1198 if (buildInParallel) {
1204 typename decltype (ptr)::HostMirror ptrHost =
Kokkos::create_mirror_view (ptr);
1207 for (offset_type i = 0; i < size; ++i) {
1209 ptrHost[i+1] = ptrHost[i] + counts[i];
1216 execution_space::fence ();
1220 using Kokkos::ViewAllocateWithoutInitializing;
1221 typedef typename val_type::non_const_type nonconst_val_type;
1222 nonconst_val_type val (ViewAllocateWithoutInitializing (
"FixedHashTable::pairs"),
1226 typedef FHT::FillPairs<
typename val_type::non_const_type, keys_type,
1227 typename ptr_type::non_const_type> functor_type;
1228 typename functor_type::value_type result (initMinKey, initMaxKey);
1230 const ValueType newStartingValue = startingValue +
static_cast<ValueType
> (startIndex);
1231 if (buildInParallel) {
1232 functor_type functor (val, counts, ptr, theKeys, newStartingValue,
1233 initMinKey, initMaxKey);
1234 Kokkos::parallel_reduce (theNumKeys, functor, result);
1237 for (offset_type k = 0; k < theNumKeys; ++k) {
1238 typedef typename hash_type::result_type hash_value_type;
1239 const KeyType key = theKeys[k];
1240 if (key > result.maxKey_) {
1241 result.maxKey_ = key;
1243 if (key < result.minKey_) {
1244 result.minKey_ = key;
1246 const ValueType theVal = newStartingValue +
static_cast<ValueType
> (k);
1247 const hash_value_type hashVal = hash_type::hashFunc (key, size);
1253 const offset_type count = counts[hashVal];
1256 result.success_ =
false;
1261 const offset_type curPos = ptr[hashVal+1] - count;
1264 val[curPos].first = key;
1265 val[curPos].second = theVal;
1282 minKey_ = result.minKey_;
1283 maxKey_ = result.maxKey_;
1288 template<
class KeyType,
class ValueType,
class DeviceType>
1290 FixedHashTable<KeyType, ValueType, DeviceType>::
1291 init (
const host_input_keys_type& keys,
1292 const host_input_vals_type& vals,
1296 const offset_type numKeys =
static_cast<offset_type
> (keys.dimension_0 ());
1297 TEUCHOS_TEST_FOR_EXCEPTION
1298 (static_cast<unsigned long long> (numKeys) > static_cast<unsigned long long> (::Kokkos::Details::ArithTraits<ValueType>::max ()),
1299 std::invalid_argument,
"Tpetra::Details::FixedHashTable: The number of " 1300 "keys " << numKeys <<
" is greater than the maximum representable " 1301 "ValueType value " << ::Kokkos::Details::ArithTraits<ValueType>::max () <<
".");
1302 TEUCHOS_TEST_FOR_EXCEPTION
1303 (numKeys > static_cast<offset_type> (INT_MAX), std::logic_error,
"Tpetra::" 1304 "Details::FixedHashTable: This class currently only works when the number " 1305 "of keys is <= INT_MAX = " << INT_MAX <<
". If this is a problem for you" 1306 ", please talk to the Tpetra developers.");
1313 const offset_type size = hash_type::getRecommendedSize (numKeys);
1314 #ifdef HAVE_TPETRA_DEBUG 1315 TEUCHOS_TEST_FOR_EXCEPTION(
1316 size == 0 && numKeys != 0, std::logic_error,
1317 "Tpetra::Details::FixedHashTable constructor: " 1318 "getRecommendedSize(" << numKeys <<
") returned zero, " 1319 "even though the number of keys " << numKeys <<
" is nonzero. " 1320 "Please report this bug to the Tpetra developers.");
1321 #endif // HAVE_TPETRA_DEBUG 1331 typename ptr_type::non_const_type ptr (
"FixedHashTable::ptr", size + 1);
1335 using Kokkos::ViewAllocateWithoutInitializing;
1336 typedef typename val_type::non_const_type nonconst_val_type;
1337 nonconst_val_type val (ViewAllocateWithoutInitializing (
"FixedHashTable::pairs"),
1341 for (offset_type k = 0; k < numKeys; ++k) {
1342 const typename hash_type::result_type hashVal =
1343 hash_type::hashFunc (keys[k], size);
1355 for (offset_type i = 0; i < size; ++i) {
1361 typename ptr_type::non_const_type curRowStart (
"FixedHashTable::curRowStart", size);
1364 FHT::FillPairsResult<KeyType> result (initMinKey, initMaxKey);
1365 for (offset_type k = 0; k < numKeys; ++k) {
1366 typedef typename hash_type::result_type hash_value_type;
1367 const KeyType key = keys[k];
1368 if (key > result.maxKey_) {
1369 result.maxKey_ = key;
1371 if (key < result.minKey_) {
1372 result.minKey_ = key;
1374 const ValueType theVal = vals[k];
1375 if (theVal > maxVal_) {
1378 if (theVal < minVal_) {
1381 const hash_value_type hashVal = hash_type::hashFunc (key, size);
1383 const offset_type offset = curRowStart[hashVal];
1384 const offset_type curPos = ptr[hashVal] + offset;
1385 if (curPos >= ptr[hashVal+1]) {
1386 result.success_ =
false;
1389 val[curPos].first = key;
1390 val[curPos].second = theVal;
1391 ++curRowStart[hashVal];
1395 TEUCHOS_TEST_FOR_EXCEPTION
1396 (! result.success_, std::logic_error,
"Tpetra::Details::FixedHashTable::" 1397 "init: Filling the hash table failed! Please report this bug to the " 1398 "Tpetra developers.");
1403 minKey_ = result.minKey_;
1404 maxKey_ = result.maxKey_;
1408 template <
class KeyType,
class ValueType,
class DeviceType>
1410 FixedHashTable<KeyType, ValueType, DeviceType>::
1413 if (! checkedForDuplicateKeys_) {
1414 hasDuplicateKeys_ = checkForDuplicateKeys ();
1415 checkedForDuplicateKeys_ =
true;
1417 return hasDuplicateKeys_;
1420 template <
class KeyType,
class ValueType,
class DeviceType>
1425 const offset_type size = this->getSize ();
1429 if (size == 0 || this->numPairs () == 0) {
1433 typedef FHT::CheckForDuplicateKeys<ptr_type, val_type> functor_type;
1434 functor_type functor (val_, ptr_);
1436 Kokkos::parallel_reduce (size, functor, hasDupKeys);
1437 return hasDupKeys>0;
1441 template <
class KeyType,
class ValueType,
class DeviceType>
1443 FixedHashTable<KeyType, ValueType, DeviceType>::
1444 description ()
const 1446 std::ostringstream oss;
1447 oss <<
"FixedHashTable<" 1448 << Teuchos::TypeNameTraits<KeyType>::name () <<
"," 1449 << Teuchos::TypeNameTraits<ValueType>::name () <<
">: " 1450 <<
"{ numKeys: " << val_.dimension_0 ()
1451 <<
", tableSize: " << this->getSize () <<
" }";
1455 template <
class KeyType,
class ValueType,
class DeviceType>
1459 const Teuchos::EVerbosityLevel verbLevel)
const 1463 using Teuchos::OSTab;
1464 using Teuchos::rcpFromRef;
1465 using Teuchos::TypeNameTraits;
1466 using Teuchos::VERB_DEFAULT;
1467 using Teuchos::VERB_NONE;
1468 using Teuchos::VERB_LOW;
1469 using Teuchos::VERB_EXTREME;
1474 Teuchos::EVerbosityLevel vl = verbLevel;
1475 if (vl == VERB_DEFAULT) vl = VERB_LOW;
1477 if (vl == VERB_NONE) {
1480 else if (vl == VERB_LOW) {
1481 out << this->description() << endl;
1484 out <<
"FixedHashTable:" << endl;
1486 OSTab tab1 (rcpFromRef (out));
1488 const std::string label = this->getObjectLabel ();
1490 out <<
"label: " << label << endl;
1492 out <<
"Template parameters:" << endl;
1494 OSTab tab2 (rcpFromRef (out));
1495 out <<
"KeyType: " << TypeNameTraits<KeyType>::name () << endl
1496 <<
"ValueType: " << TypeNameTraits<ValueType>::name () << endl;
1499 const offset_type tableSize = this->getSize ();
1500 const offset_type numKeys = val_.dimension_0 ();
1502 out <<
"Table parameters:" << endl;
1504 OSTab tab2 (rcpFromRef (out));
1505 out <<
"numKeys: " << numKeys << endl
1506 <<
"tableSize: " << tableSize << endl;
1509 if (vl >= VERB_EXTREME) {
1510 out <<
"Contents: ";
1511 if (tableSize == 0 || numKeys == 0) {
1512 out <<
"[]" << endl;
1514 out <<
"[ " << endl;
1516 OSTab tab2 (rcpFromRef (out));
1517 for (offset_type i = 0; i < tableSize; ++i) {
1518 OSTab tab3 (rcpFromRef (out));
1520 for (offset_type k = ptr_[i]; k < ptr_[i+1]; ++k) {
1521 out <<
"(" << val_[k].first <<
"," << val_[k].second <<
")";
1522 if (k + 1 < ptr_[i+1]) {
1548 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT_DEFAULTNODE(LO,GO) \ 1549 template class FixedHashTable< GO , LO >; 1560 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, DEVICE) \ 1561 template class FixedHashTable< GO , LO , DEVICE >; 1563 #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.
Namespace Tpetra contains the class and methods constituting the Tpetra library.
ResultType result_type
Type of the return value of the hash function.
Parallel for functor for counting "buckets" in the FixedHashTable.
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
void deep_copy(MultiVector< DS, DL, DG, DN, dstClassic > &dst, const MultiVector< SS, SL, SG, SN, srcClassic > &src)
Copy the contents of the MultiVector src into dst.
bool success_
Whether fill succeeded (it can only fail on a bug)
KeyType maxKey_
The current maximum key.
Implementation details of Tpetra.
The hash function for FixedHashTable.
KOKKOS_INLINE_FUNCTION void operator()(const size_type &i, value_type &dst) const
Parallel loop body; do this for every entry of keys_.
Declare and define the function Tpetra::Details::computeOffsetsFromCounts, an implementation detail o...
OffsetsViewType::non_const_value_type computeOffsetsFromCounts(const OffsetsViewType &ptr, const CountsViewType &counts)
Compute offsets from counts.
KOKKOS_INLINE_FUNCTION void operator()(const size_type &i, value_type &dst) const
Parallel loop body.
FixedHashTable()
Default constructor; makes an empty table.
KOKKOS_INLINE_FUNCTION void operator()(const size_type &i) const
Do this for every entry of keys_.
bool hasKeys() const
Whether it is safe to call getKey().
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
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.
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.
Functor for checking whether a FixedHashTable has one or more duplicate entries.
KOKKOS_INLINE_FUNCTION void join(volatile value_type &dst, const volatile value_type &src) const
Combine two intermediate reduction results.
KeyType minKey_
The current minimum key.
Reduction result for FillPairs functor below.
Kokkos::View< const GlobalOrdinal *, Kokkos::LayoutLeft, device_type > keys_type
Type of a 1-D Kokkos::View (array) used to store keys.