44 #ifndef TPETRA_DETAILS_FIXEDHASHTABLE_DEF_HPP 45 #define TPETRA_DETAILS_FIXEDHASHTABLE_DEF_HPP 47 #include "Tpetra_Details_FixedHashTable_decl.hpp" 48 #ifdef TPETRA_USE_MURMUR_HASH 49 # include <Kokkos_Functional.hpp> 50 #endif // TPETRA_USE_MURMUR_HASH 52 #include <type_traits> 77 template<
class ExecSpace>
78 struct WorthBuildingFixedHashTableInParallel {
79 typedef typename ExecSpace::execution_space execution_space;
81 static bool isWorth () {
84 return execution_space::max_hardware_threads () > 1;
88 #ifdef KOKKOS_HAVE_CUDA 90 struct WorthBuildingFixedHashTableInParallel<
Kokkos::Cuda> {
95 static bool isWorth () {
99 #endif // KOKKOS_HAVE_CUDA 113 template<
class ExecSpace>
114 bool worthBuildingFixedHashTableInParallel () {
115 return WorthBuildingFixedHashTableInParallel<ExecSpace>::isWorth ();
126 template<
class KeyType,
128 class InputExecSpace,
129 class OutputExecSpace,
130 const bool mustDeepCopy =
131 ! std::is_same<
typename InputExecSpace::memory_space,
132 typename OutputExecSpace::memory_space>::value>
133 struct DeepCopyIfNeeded {
139 template<
class KeyType,
141 class InputExecSpace,
142 class OutputExecSpace>
143 struct DeepCopyIfNeeded<KeyType, ArrayLayout, InputExecSpace, OutputExecSpace, true>
145 typedef Kokkos::View<
const KeyType*, ArrayLayout,
146 InputExecSpace, Kokkos::MemoryUnmanaged> input_view_type;
152 typedef Kokkos::View<const KeyType*, ArrayLayout, OutputExecSpace> output_view_type;
154 static output_view_type copy (
const input_view_type& src) {
155 typedef typename output_view_type::non_const_type NC;
157 NC dst (Kokkos::ViewAllocateWithoutInitializing (src.tracker ().label ()),
160 return output_view_type (dst);
165 template<
class KeyType,
167 class InputExecSpace,
168 class OutputExecSpace>
169 struct DeepCopyIfNeeded<KeyType, ArrayLayout, InputExecSpace, OutputExecSpace, false> {
170 typedef Kokkos::View<
const KeyType*, ArrayLayout,
171 InputExecSpace, Kokkos::MemoryUnmanaged> input_view_type;
172 typedef Kokkos::View<
const KeyType*, ArrayLayout, OutputExecSpace,
173 Kokkos::MemoryUnmanaged> output_view_type;
175 static output_view_type copy (
const input_view_type& src) {
176 return output_view_type (src);
198 template<
class CountsViewType,
200 class SizeType =
typename KeysViewType::size_type>
203 typedef CountsViewType counts_view_type;
204 typedef KeysViewType keys_view_type;
205 typedef typename CountsViewType::execution_space execution_space;
206 typedef typename CountsViewType::memory_space memory_space;
207 typedef SizeType size_type;
208 typedef typename keys_view_type::non_const_value_type key_type;
224 const keys_view_type& keys,
225 const size_type size) :
235 KOKKOS_INLINE_FUNCTION
void 236 operator () (
const size_type& i)
const 240 const hash_value_type hashVal = hash_type::hashFunc (keys_[i], size_);
241 Kokkos::atomic_fetch_add (&counts_[hashVal], 1);
246 counts_view_type counts_;
248 keys_view_type keys_;
264 template<
class OffsetsViewType,
265 class SizeType =
typename OffsetsViewType::size_type>
268 typedef OffsetsViewType offsets_view_type;
269 typedef typename OffsetsViewType::const_type counts_view_type;
270 typedef typename OffsetsViewType::execution_space execution_space;
271 typedef typename OffsetsViewType::memory_space memory_space;
272 typedef SizeType size_type;
273 typedef typename OffsetsViewType::non_const_value_type value_type;
281 const counts_view_type& counts) :
284 size_ (counts.dimension_0 ())
288 KOKKOS_INLINE_FUNCTION
void init (value_type& dst)
const 293 KOKKOS_INLINE_FUNCTION
void 294 join (
volatile value_type& dst,
295 const volatile value_type& src)
const 300 KOKKOS_INLINE_FUNCTION
void 301 operator () (
const size_type& i, value_type& update,
const bool final)
const 304 offsets_[i] = update;
307 update += counts_[i];
313 offsets_view_type offsets_;
315 counts_view_type counts_;
330 template<
class KeyType>
333 minKey_ (std::numeric_limits<KeyType>::max ()),
346 maxKey_ (std::numeric_limits<KeyType>::is_integer ?
347 std::numeric_limits<KeyType>::min () :
348 -std::numeric_limits<KeyType>::max ()),
351 static_assert (std::is_arithmetic<KeyType>::value,
"FillPairsResult: " 352 "KeyType must be some kind of number type.");
356 const KeyType& initMaxKey) :
357 minKey_ (initMinKey),
358 maxKey_ (initMaxKey),
361 static_assert (std::is_arithmetic<KeyType>::value,
"FillPairsResult: " 362 "KeyType must be some kind of number type.");
399 template<
class PairsViewType,
401 class CountsViewType,
402 class SizeType =
typename KeysViewType::size_type>
405 typedef typename CountsViewType::non_const_type counts_view_type;
406 typedef typename counts_view_type::const_type offsets_view_type;
408 typedef PairsViewType pairs_view_type;
409 typedef typename KeysViewType::const_type keys_view_type;
410 typedef typename offsets_view_type::execution_space execution_space;
411 typedef typename offsets_view_type::memory_space memory_space;
412 typedef SizeType size_type;
414 typedef typename keys_view_type::non_const_value_type key_type;
415 typedef typename pairs_view_type::non_const_value_type pair_type;
439 const counts_view_type& counts,
440 const offsets_view_type& ptr,
441 const keys_view_type& keys,
442 const typename pair_type::second_type startingValue) :
447 size_ (counts.dimension_0 ()),
448 startingValue_ (startingValue),
449 initMinKey_ (std::numeric_limits<key_type>::max ()),
450 initMaxKey_ (std::numeric_limits<key_type>::is_integer ?
451 std::numeric_limits<key_type>::min () :
452 -std::numeric_limits<key_type>::max ())
474 const counts_view_type& counts,
475 const offsets_view_type& ptr,
476 const keys_view_type& keys,
477 const typename pair_type::second_type startingValue,
478 const key_type initMinKey,
479 const key_type initMaxKey) :
484 size_ (counts.dimension_0 ()),
485 startingValue_ (startingValue),
486 initMinKey_ (initMinKey),
487 initMaxKey_ (initMaxKey)
491 KOKKOS_INLINE_FUNCTION
void init (value_type& dst)
const 498 KOKKOS_INLINE_FUNCTION
void 499 join (
volatile value_type& dst,
500 const volatile value_type& src)
const 515 KOKKOS_INLINE_FUNCTION
void 516 operator () (
const size_type& i, value_type& dst)
const 519 typedef typename offsets_view_type::non_const_value_type offset_type;
520 typedef typename pair_type::second_type val_type;
522 const key_type key = keys_[i];
529 const val_type theVal = startingValue_ +
static_cast<val_type
> (i);
530 const hash_value_type hashVal = hash_type::hashFunc (key, size_);
533 const offset_type count = Kokkos::atomic_fetch_add (&counts_[hashVal], -1);
538 const offset_type curPos = ptr_[hashVal+1] - count;
540 pairs_[curPos].first = key;
541 pairs_[curPos].second = theVal;
546 pairs_view_type pairs_;
547 counts_view_type counts_;
548 offsets_view_type ptr_;
549 keys_view_type keys_;
551 typename pair_type::second_type startingValue_;
553 key_type initMinKey_;
555 key_type initMaxKey_;
581 template<
class OffsetsViewType,
583 class SizeType =
typename OffsetsViewType::size_type>
586 typedef typename OffsetsViewType::const_type offsets_view_type;
587 typedef typename PairsViewType::const_type pairs_view_type;
588 typedef typename offsets_view_type::execution_space execution_space;
589 typedef typename offsets_view_type::memory_space memory_space;
590 typedef SizeType size_type;
593 typedef bool value_type;
600 const offsets_view_type& ptr) :
603 size_ (ptr_.dimension_0 () == 0 ?
605 ptr_.dimension_0 () - 1)
609 KOKKOS_INLINE_FUNCTION
void init (value_type& dst)
const 615 KOKKOS_INLINE_FUNCTION
void 616 join (
volatile value_type& dst,
617 const volatile value_type& src)
const 623 KOKKOS_INLINE_FUNCTION
void 624 operator () (
const size_type& i, value_type& dst)
const 626 typedef typename offsets_view_type::non_const_value_type offset_type;
627 typedef typename pairs_view_type::non_const_value_type pair_type;
628 typedef typename pair_type::first_type key_type;
634 const offset_type beg = ptr_[i];
635 const offset_type end = ptr_[i+1];
636 bool foundDuplicateKey =
false;
641 for (offset_type j = beg + 1; j < end; ++j) {
642 const key_type curKey = pairs_[j].first;
643 for (offset_type k = beg; k < j; ++k) {
644 if (pairs_[k].first == curKey) {
645 foundDuplicateKey =
true;
650 dst = dst || foundDuplicateKey;
655 pairs_view_type pairs_;
656 offsets_view_type ptr_;
666 template<
class KeyType,
class ValueType,
class DeviceType>
676 return keys_.dimension_0 () == val_.dimension_0 ();
679 template<
class KeyType,
class ValueType,
class DeviceType>
688 template<
class KeyType,
class ValueType,
class DeviceType>
691 minKey_ (std::numeric_limits<KeyType>::max ()),
692 maxKey_ (std::numeric_limits<KeyType>::is_integer ?
693 std::numeric_limits<KeyType>::min () :
694 -std::numeric_limits<KeyType>::max ()),
695 minVal_ (std::numeric_limits<ValueType>::max ()),
696 maxVal_ (std::numeric_limits<ValueType>::is_integer ?
697 std::numeric_limits<ValueType>::min () :
698 -std::numeric_limits<ValueType>::max ()),
699 firstContigKey_ (std::numeric_limits<KeyType>::max ()),
700 lastContigKey_ (std::numeric_limits<KeyType>::is_integer ?
701 std::numeric_limits<KeyType>::min () :
702 -std::numeric_limits<KeyType>::max ()),
703 contiguousValues_ (true),
704 checkedForDuplicateKeys_ (true),
705 hasDuplicateKeys_ (false)
707 #ifdef HAVE_TPETRA_DEBUG 709 #endif // HAVE_TPETRA_DEBUG 712 template<
class KeyType,
class ValueType,
class DeviceType>
716 minKey_ (std::numeric_limits<KeyType>::max ()),
717 maxKey_ (std::numeric_limits<KeyType>::is_integer ?
718 std::numeric_limits<KeyType>::min () :
719 -std::numeric_limits<KeyType>::max ()),
721 maxVal_ (keys.size () == 0 ?
722 static_cast<ValueType> (0) :
723 static_cast<ValueType> (keys.size () - 1)),
724 firstContigKey_ (std::numeric_limits<KeyType>::max ()),
725 lastContigKey_ (std::numeric_limits<KeyType>::is_integer ?
726 std::numeric_limits<KeyType>::min () :
727 -std::numeric_limits<KeyType>::max ()),
728 contiguousValues_ (true),
729 checkedForDuplicateKeys_ (false),
730 hasDuplicateKeys_ (false)
732 const ValueType startingValue =
static_cast<ValueType
> (0);
733 const KeyType initMinKey = this->minKey_;
734 const KeyType initMaxKey = this->maxKey_;
735 this->init (keys, startingValue, initMinKey, initMaxKey,
736 initMinKey, initMinKey,
false);
738 #ifdef HAVE_TPETRA_DEBUG 740 #endif // HAVE_TPETRA_DEBUG 743 template<
class KeyType,
class ValueType,
class DeviceType>
746 const bool keepKeys) :
747 minKey_ (std::numeric_limits<KeyType>::max ()),
748 maxKey_ (std::numeric_limits<KeyType>::is_integer ?
749 std::numeric_limits<KeyType>::min () :
750 -std::numeric_limits<KeyType>::max ()),
752 maxVal_ (keys.size () == 0 ?
753 static_cast<ValueType> (0) :
754 static_cast<ValueType> (keys.size () - 1)),
755 firstContigKey_ (std::numeric_limits<KeyType>::max ()),
756 lastContigKey_ (std::numeric_limits<KeyType>::is_integer ?
757 std::numeric_limits<KeyType>::min () :
758 -std::numeric_limits<KeyType>::max ()),
759 contiguousValues_ (true),
760 checkedForDuplicateKeys_ (false),
761 hasDuplicateKeys_ (false)
763 typedef typename keys_type::non_const_type nonconst_keys_type;
768 const ValueType startingValue =
static_cast<ValueType
> (0);
769 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
771 using Kokkos::ViewAllocateWithoutInitializing;
772 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
773 keys_k.dimension_0 ());
775 const KeyType initMinKey = this->minKey_;
776 const KeyType initMaxKey = this->maxKey_;
777 this->init (keys_d, startingValue, initMinKey, initMaxKey,
778 initMinKey, initMinKey,
false);
781 #ifdef HAVE_TPETRA_DEBUG 782 typedef typename keys_type::size_type size_type;
783 TEUCHOS_TEST_FOR_EXCEPTION
784 (keys_.dimension_0 () !=
static_cast<size_type
> (keys.size ()),
785 std::logic_error,
"Tpetra::Details::FixedHashTable constructor: " 786 "keepKeys is true, but on return, keys_.dimension_0() = " <<
787 keys_.dimension_0 () <<
" != keys.size() = " << keys.size () <<
788 ". Please report this bug to the Tpetra developers.");
789 #endif // HAVE_TPETRA_DEBUG 792 #ifdef HAVE_TPETRA_DEBUG 794 #endif // HAVE_TPETRA_DEBUG 797 template<
class KeyType,
class ValueType,
class DeviceType>
800 const ValueType startingValue,
801 const bool keepKeys) :
802 minKey_ (std::numeric_limits<KeyType>::max ()),
803 maxKey_ (std::numeric_limits<KeyType>::is_integer ?
804 std::numeric_limits<KeyType>::min () :
805 -std::numeric_limits<KeyType>::max ()),
806 minVal_ (startingValue),
807 maxVal_ (keys.size () == 0 ?
809 static_cast<ValueType> (startingValue + keys.size () - 1)),
810 firstContigKey_ (std::numeric_limits<KeyType>::max ()),
811 lastContigKey_ (std::numeric_limits<KeyType>::is_integer ?
812 std::numeric_limits<KeyType>::min () :
813 -std::numeric_limits<KeyType>::max ()),
814 contiguousValues_ (true),
815 checkedForDuplicateKeys_ (false),
816 hasDuplicateKeys_ (false)
818 typedef typename keys_type::non_const_type nonconst_keys_type;
823 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
825 using Kokkos::ViewAllocateWithoutInitializing;
826 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
827 keys_k.dimension_0 ());
830 const KeyType initMinKey = std::numeric_limits<KeyType>::max ();
843 const KeyType initMaxKey = std::numeric_limits<KeyType>::is_integer ?
844 std::numeric_limits<KeyType>::min () :
845 -std::numeric_limits<KeyType>::max ();
846 this->init (keys_d, startingValue, initMinKey, initMaxKey,
847 initMinKey, initMinKey,
false);
850 #ifdef HAVE_TPETRA_DEBUG 851 typedef typename keys_type::size_type size_type;
852 TEUCHOS_TEST_FOR_EXCEPTION
853 (keys_.dimension_0 () !=
static_cast<size_type
> (keys.size ()),
854 std::logic_error,
"Tpetra::Details::FixedHashTable constructor: " 855 "keepKeys is true, but on return, keys_.dimension_0() = " <<
856 keys_.dimension_0 () <<
" != keys.size() = " << keys.size () <<
857 ". Please report this bug to the Tpetra developers.");
858 #endif // HAVE_TPETRA_DEBUG 861 #ifdef HAVE_TPETRA_DEBUG 863 #endif // HAVE_TPETRA_DEBUG 866 template<
class KeyType,
class ValueType,
class DeviceType>
869 const KeyType firstContigKey,
870 const KeyType lastContigKey,
871 const ValueType startingValue,
872 const bool keepKeys) :
873 minKey_ (std::numeric_limits<KeyType>::max ()),
874 maxKey_ (std::numeric_limits<KeyType>::is_integer ?
875 std::numeric_limits<KeyType>::min () :
876 -std::numeric_limits<KeyType>::max ()),
877 minVal_ (startingValue),
878 maxVal_ (keys.size () == 0 ?
880 static_cast<ValueType> (startingValue + keys.size () - 1)),
881 firstContigKey_ (firstContigKey),
882 lastContigKey_ (lastContigKey),
883 contiguousValues_ (true),
884 checkedForDuplicateKeys_ (false),
885 hasDuplicateKeys_ (false)
887 typedef typename keys_type::non_const_type nonconst_keys_type;
892 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
894 using Kokkos::ViewAllocateWithoutInitializing;
895 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
896 keys_k.dimension_0 ());
899 const KeyType initMinKey = std::numeric_limits<KeyType>::max ();
912 const KeyType initMaxKey = std::numeric_limits<KeyType>::is_integer ?
913 std::numeric_limits<KeyType>::min () :
914 -std::numeric_limits<KeyType>::max ();
915 this->init (keys_d, startingValue, initMinKey, initMaxKey,
916 firstContigKey, lastContigKey,
true);
919 #ifdef HAVE_TPETRA_DEBUG 920 typedef typename keys_type::size_type size_type;
921 TEUCHOS_TEST_FOR_EXCEPTION
922 (keys_.dimension_0 () !=
static_cast<size_type
> (keys.size ()),
923 std::logic_error,
"Tpetra::Details::FixedHashTable constructor: " 924 "keepKeys is true, but on return, keys_.dimension_0() = " <<
925 keys_.dimension_0 () <<
" != keys.size() = " << keys.size () <<
926 ". Please report this bug to the Tpetra developers.");
927 #endif // HAVE_TPETRA_DEBUG 930 #ifdef HAVE_TPETRA_DEBUG 932 #endif // HAVE_TPETRA_DEBUG 935 template<
class KeyType,
class ValueType,
class DeviceType>
938 const ValueType startingValue) :
940 minKey_ (std::numeric_limits<KeyType>::max ()),
941 maxKey_ (std::numeric_limits<KeyType>::is_integer ?
942 std::numeric_limits<KeyType>::min () :
943 -std::numeric_limits<KeyType>::max ()),
944 minVal_ (startingValue),
945 maxVal_ (keys.size () == 0 ?
947 static_cast<ValueType> (startingValue + keys.size () - 1)),
948 firstContigKey_ (std::numeric_limits<KeyType>::max ()),
949 lastContigKey_ (std::numeric_limits<KeyType>::is_integer ?
950 std::numeric_limits<KeyType>::min () :
951 -std::numeric_limits<KeyType>::max ()),
952 contiguousValues_ (true),
953 checkedForDuplicateKeys_ (false),
954 hasDuplicateKeys_ (false)
956 const KeyType initMinKey = std::numeric_limits<KeyType>::max ();
969 const KeyType initMaxKey = std::numeric_limits<KeyType>::is_integer ?
970 std::numeric_limits<KeyType>::min () :
971 -std::numeric_limits<KeyType>::max ();
972 this->init (keys, startingValue, initMinKey, initMaxKey,
973 initMinKey, initMinKey,
false);
975 #ifdef HAVE_TPETRA_DEBUG 977 #endif // HAVE_TPETRA_DEBUG 980 template<
class KeyType,
class ValueType,
class DeviceType>
983 const Teuchos::ArrayView<const ValueType>& vals) :
984 minKey_ (std::numeric_limits<KeyType>::max ()),
985 maxKey_ (std::numeric_limits<KeyType>::is_integer ?
986 std::numeric_limits<KeyType>::min () :
987 -std::numeric_limits<KeyType>::max ()),
988 minVal_ (std::numeric_limits<ValueType>::max ()),
989 maxVal_ (std::numeric_limits<ValueType>::is_integer ?
990 std::numeric_limits<ValueType>::min () :
991 -std::numeric_limits<ValueType>::max ()),
992 firstContigKey_ (std::numeric_limits<KeyType>::max ()),
993 lastContigKey_ (std::numeric_limits<KeyType>::is_integer ?
994 std::numeric_limits<KeyType>::min () :
995 -std::numeric_limits<KeyType>::max ()),
996 contiguousValues_ (false),
997 checkedForDuplicateKeys_ (false),
998 hasDuplicateKeys_ (false)
1003 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
1005 host_input_vals_type vals_k (vals.size () == 0 ? NULL : vals.getRawPtr (),
1007 const KeyType initMinKey = std::numeric_limits<KeyType>::max ();
1020 const KeyType initMaxKey = std::numeric_limits<KeyType>::is_integer ?
1021 std::numeric_limits<KeyType>::min () :
1022 -std::numeric_limits<KeyType>::max ();
1023 this->init (keys_k, vals_k, initMinKey, initMaxKey);
1025 #ifdef HAVE_TPETRA_DEBUG 1027 #endif // HAVE_TPETRA_DEBUG 1030 template<
class KeyType,
class ValueType,
class DeviceType>
1034 ValueType startingValue,
1037 KeyType firstContigKey,
1038 KeyType lastContigKey,
1039 const bool computeInitContigKeys)
1041 using Kokkos::subview;
1043 const offset_type numKeys =
static_cast<offset_type
> (keys.dimension_0 ());
1044 TEUCHOS_TEST_FOR_EXCEPTION
1045 (static_cast<unsigned long long> (numKeys) >
1046 static_cast<unsigned long long> (std::numeric_limits<ValueType>::max ()),
1047 std::invalid_argument,
"Tpetra::Details::FixedHashTable: The number of " 1048 "keys " << numKeys <<
" is greater than the maximum representable " 1049 "ValueType value " << std::numeric_limits<ValueType>::max () <<
". " 1050 "This means that it is not possible to use this constructor.");
1051 TEUCHOS_TEST_FOR_EXCEPTION
1052 (numKeys > static_cast<offset_type> (INT_MAX), std::logic_error,
"Tpetra::" 1053 "Details::FixedHashTable: This class currently only works when the number " 1054 "of keys is <= INT_MAX = " << INT_MAX <<
". If this is a problem for you" 1055 ", please talk to the Tpetra developers.");
1057 const bool buildInParallel =
1058 FHT::worthBuildingFixedHashTableInParallel<execution_space> ();
1068 if (computeInitContigKeys) {
1083 firstContigKey_ = keys[0];
1087 lastContigKey_ = firstContigKey_ + 1;
1093 for (offset_type k = 1; k < numKeys; ++k) {
1094 if (lastContigKey_ != keys[k]) {
1103 firstContigKey_ = firstContigKey;
1104 lastContigKey_ = lastContigKey;
1107 offset_type startIndex;
1109 initMinKey = std::min (initMinKey, firstContigKey_);
1110 initMaxKey = std::max (initMaxKey, lastContigKey_);
1111 startIndex =
static_cast<offset_type
> (lastContigKey_ - firstContigKey_);
1116 const offset_type theNumKeys = numKeys - startIndex;
1118 #ifdef HAVE_TPETRA_DEBUG 1119 TEUCHOS_TEST_FOR_EXCEPTION(
1120 size == 0 && numKeys != 0, std::logic_error,
1121 "Tpetra::Details::FixedHashTable constructor: " 1122 "getRecommendedSize(" << numKeys <<
") returned zero, " 1123 "even though the number of keys " << numKeys <<
" is nonzero. " 1124 "Please report this bug to the Tpetra developers.");
1125 #endif // HAVE_TPETRA_DEBUG 1127 subview (keys, std::pair<offset_type, offset_type> (startIndex, numKeys));
1131 typedef typename ptr_type::non_const_type counts_type;
1132 counts_type counts (
"FixedHashTable::counts", size);
1143 if (buildInParallel) {
1145 Kokkos::parallel_for (theNumKeys, functor);
1148 for (offset_type k = 0; k < theNumKeys; ++k) {
1157 typename ptr_type::non_const_type ptr (
"FixedHashTable::ptr", size + 1);
1171 if (buildInParallel) {
1173 functor_type functor (ptr, counts);
1174 Kokkos::parallel_scan (size+1, functor);
1177 for (offset_type i = 0; i < size; ++i) {
1179 ptr[i+1] = ptr[i] + counts[i];
1186 using Kokkos::ViewAllocateWithoutInitializing;
1187 typedef typename val_type::non_const_type nonconst_val_type;
1188 nonconst_val_type val (ViewAllocateWithoutInitializing (
"FixedHashTable::pairs"),
1193 typename ptr_type::non_const_type> functor_type;
1194 typename functor_type::value_type result (initMinKey, initMaxKey);
1196 const ValueType newStartingValue = startingValue +
static_cast<ValueType
> (startIndex);
1197 if (buildInParallel) {
1198 functor_type functor (val, counts, ptr, theKeys, newStartingValue,
1199 initMinKey, initMaxKey);
1200 Kokkos::parallel_reduce (theNumKeys, functor, result);
1203 for (offset_type k = 0; k < theNumKeys; ++k) {
1205 const KeyType key = theKeys[k];
1206 if (key > result.maxKey_) {
1207 result.maxKey_ = key;
1209 if (key < result.minKey_) {
1210 result.minKey_ = key;
1212 const ValueType theVal = newStartingValue +
static_cast<ValueType
> (k);
1216 const offset_type count = counts[hashVal];
1219 result.success_ =
false;
1223 const offset_type curPos = ptr[hashVal+1] - count;
1225 val[curPos].first = key;
1226 val[curPos].second = theVal;
1243 minKey_ = result.minKey_;
1244 maxKey_ = result.maxKey_;
1249 template<
class KeyType,
class ValueType,
class DeviceType>
1252 init (
const host_input_keys_type& keys,
1253 const host_input_vals_type& vals,
1257 const offset_type numKeys =
static_cast<offset_type
> (keys.dimension_0 ());
1258 TEUCHOS_TEST_FOR_EXCEPTION
1259 (static_cast<unsigned long long> (numKeys) > static_cast<unsigned long long> (std::numeric_limits<ValueType>::max ()),
1260 std::invalid_argument,
"Tpetra::Details::FixedHashTable: The number of " 1261 "keys " << numKeys <<
" is greater than the maximum representable " 1262 "ValueType value " << std::numeric_limits<ValueType>::max () <<
".");
1263 TEUCHOS_TEST_FOR_EXCEPTION
1264 (numKeys > static_cast<offset_type> (INT_MAX), std::logic_error,
"Tpetra::" 1265 "Details::FixedHashTable: This class currently only works when the number " 1266 "of keys is <= INT_MAX = " << INT_MAX <<
". If this is a problem for you" 1267 ", please talk to the Tpetra developers.");
1275 #ifdef HAVE_TPETRA_DEBUG 1276 TEUCHOS_TEST_FOR_EXCEPTION(
1277 size == 0 && numKeys != 0, std::logic_error,
1278 "Tpetra::Details::FixedHashTable constructor: " 1279 "getRecommendedSize(" << numKeys <<
") returned zero, " 1280 "even though the number of keys " << numKeys <<
" is nonzero. " 1281 "Please report this bug to the Tpetra developers.");
1282 #endif // HAVE_TPETRA_DEBUG 1292 typename ptr_type::non_const_type ptr (
"FixedHashTable::ptr", size + 1);
1296 using Kokkos::ViewAllocateWithoutInitializing;
1297 typedef typename val_type::non_const_type nonconst_val_type;
1298 nonconst_val_type val (ViewAllocateWithoutInitializing (
"FixedHashTable::pairs"),
1302 for (offset_type k = 0; k < numKeys; ++k) {
1316 for (offset_type i = 0; i < size; ++i) {
1322 typename ptr_type::non_const_type curRowStart (
"FixedHashTable::curRowStart", size);
1326 for (offset_type k = 0; k < numKeys; ++k) {
1328 const KeyType key = keys[k];
1335 const ValueType theVal = vals[k];
1336 if (theVal > maxVal_) {
1339 if (theVal < minVal_) {
1344 const offset_type offset = curRowStart[hashVal];
1345 const offset_type curPos = ptr[hashVal] + offset;
1346 if (curPos >= ptr[hashVal+1]) {
1350 val[curPos].first = key;
1351 val[curPos].second = theVal;
1352 ++curRowStart[hashVal];
1356 TEUCHOS_TEST_FOR_EXCEPTION
1357 (! result.
success_, std::logic_error,
"Tpetra::Details::FixedHashTable::" 1358 "init: Filling the hash table failed! Please report this bug to the " 1359 "Tpetra developers.");
1369 template <
class KeyType,
class ValueType,
class DeviceType>
1374 if (! checkedForDuplicateKeys_) {
1375 hasDuplicateKeys_ = checkForDuplicateKeys ();
1376 checkedForDuplicateKeys_ =
true;
1378 return hasDuplicateKeys_;
1381 template <
class KeyType,
class ValueType,
class DeviceType>
1386 const offset_type size = this->getSize ();
1392 functor_type functor (val_, ptr_);
1393 bool hasDupKeys =
false;
1394 Kokkos::parallel_reduce (size, functor, hasDupKeys);
1399 template <
class KeyType,
class ValueType,
class DeviceType>
1404 std::ostringstream oss;
1405 oss <<
"FixedHashTable<" 1406 << Teuchos::TypeNameTraits<KeyType>::name () <<
"," 1407 << Teuchos::TypeNameTraits<ValueType>::name () <<
">: " 1408 <<
"{ numKeys: " << val_.dimension_0 ()
1409 <<
", tableSize: " << this->getSize () <<
" }";
1413 template <
class KeyType,
class ValueType,
class DeviceType>
1417 const Teuchos::EVerbosityLevel verbLevel)
const 1421 using Teuchos::OSTab;
1422 using Teuchos::rcpFromRef;
1423 using Teuchos::TypeNameTraits;
1424 using Teuchos::VERB_DEFAULT;
1425 using Teuchos::VERB_NONE;
1426 using Teuchos::VERB_LOW;
1427 using Teuchos::VERB_EXTREME;
1432 Teuchos::EVerbosityLevel vl = verbLevel;
1433 if (vl == VERB_DEFAULT) vl = VERB_LOW;
1435 if (vl == VERB_NONE) {
1438 else if (vl == VERB_LOW) {
1442 out <<
"FixedHashTable:" << endl;
1444 OSTab tab1 (rcpFromRef (out));
1446 const std::string label = this->getObjectLabel ();
1448 out <<
"label: " << label << endl;
1450 out <<
"Template parameters:" << endl;
1452 OSTab tab2 (rcpFromRef (out));
1453 out <<
"KeyType: " << TypeNameTraits<KeyType>::name () << endl
1454 <<
"ValueType: " << TypeNameTraits<ValueType>::name () << endl;
1457 const offset_type tableSize = this->getSize ();
1458 const offset_type numKeys = val_.dimension_0 ();
1460 out <<
"Table parameters:" << endl;
1462 OSTab tab2 (rcpFromRef (out));
1463 out <<
"numKeys: " << numKeys << endl
1464 <<
"tableSize: " << tableSize << endl;
1467 if (vl >= VERB_EXTREME) {
1468 out <<
"Contents: ";
1469 if (tableSize == 0 || numKeys == 0) {
1470 out <<
"[]" << endl;
1472 out <<
"[ " << endl;
1474 OSTab tab2 (rcpFromRef (out));
1475 for (offset_type i = 0; i < tableSize; ++i) {
1476 OSTab tab3 (rcpFromRef (out));
1478 for (offset_type k = ptr_[i]; k < ptr_[i+1]; ++k) {
1479 out <<
"(" << val_[k].first <<
"," << val_[k].second <<
")";
1480 if (k + 1 < ptr_[i+1]) {
1506 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT_DEFAULTNODE(LO,GO) \ 1507 template class FixedHashTable< GO , LO >; 1518 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, DEVICE) \ 1519 template class FixedHashTable< GO , LO , DEVICE >; 1521 #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.
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
KOKKOS_INLINE_FUNCTION void join(volatile value_type &dst, const volatile value_type &src) const
Combine two intermediate reduction results.
static result_type getRecommendedSize(const offset_type size)
Number of "buckets" that the constructor of FixedHashTable should allocate.
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.
void deep_copy(const LittleBlock< ST2, LO > &dst, const LittleBlock< ST1, LO > &src, typename std::enable_if< std::is_convertible< ST1, ST2 >::value &&!std::is_const< ST2 >::value, int >::type *=NULL)
Copy the LittleBlock src into the LittleBlock dst.
Parallel scan functor for computing "row" offsets.
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
bool hasKeys() const
Whether it is safe to call getKey().
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.
std::string description() const
Implementation of Teuchos::Describable.
FixedHashTable()
Default constructor; makes an empty table.
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.
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.
ComputeRowOffsets(const offsets_view_type &offsets, const counts_view_type &counts)
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.
KeyType minKey_
The current minimum key.
Reduction result for FillPairs functor below.
Kokkos::View< const KeyType *, Kokkos::LayoutLeft, device_type > keys_type
Type of a 1-D Kokkos::View (array) used to store keys.