406 const val_type
theVal = startingValue_ +
static_cast<val_type
> (
i);
412 dst.success_ =
false;
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_;
458template<
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;
477 const offsets_view_type&
ptr) :
480 size_ (ptr_.extent (0) == 0 ?
496 dst = dst + src > 0?1:0;
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];
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) {
532 pairs_view_type pairs_;
533 offsets_view_type ptr_;
543template<
class KeyType,
class ValueType,
class DeviceType>
550 checkedForDuplicateKeys_ (
false)
559template<
class KeyType,
class ValueType,
class DeviceType>
566 checkedForDuplicateKeys_ (
false)
576 using Kokkos::ViewAllocateWithoutInitializing;
587template<
class KeyType,
class ValueType,
class DeviceType>
595 checkedForDuplicateKeys_ (
false)
604 using Kokkos::ViewAllocateWithoutInitializing;
624 ::Kokkos::Details::ArithTraits<KeyType>::min () :
625 -::Kokkos::Details::ArithTraits<KeyType>::max ();
631template<
class KeyType,
class ValueType,
class DeviceType>
643 checkedForDuplicateKeys_ (
false)
659 ::Kokkos::Details::ArithTraits<KeyType>::min () :
660 -::Kokkos::Details::ArithTraits<KeyType>::max ();
665template<
class KeyType,
class ValueType,
class DeviceType>
677 checkedForDuplicateKeys_ (
false)
686 using Kokkos::ViewAllocateWithoutInitializing;
706 ::Kokkos::Details::ArithTraits<KeyType>::min () :
707 -::Kokkos::Details::ArithTraits<KeyType>::max ();
712template<
class KeyType,
class ValueType,
class DeviceType>
720 checkedForDuplicateKeys_ (
false)
736 ::Kokkos::Details::ArithTraits<KeyType>::min () :
737 -::Kokkos::Details::ArithTraits<KeyType>::max ();
742template<
class KeyType,
class ValueType,
class DeviceType>
745 const Teuchos::ArrayView<const ValueType>&
vals) :
746 contiguousValues_ (
false),
747 checkedForDuplicateKeys_ (
false)
770 ::Kokkos::Details::ArithTraits<KeyType>::min () :
771 -::Kokkos::Details::ArithTraits<KeyType>::max ();
775template<
class KeyType,
class ValueType,
class DeviceType>
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 ();
798 "number of keys " <<
keys.extent (0) <<
" does not fit in "
800 "max value is " <<
theMaxVal <<
". This means that it is not possible to "
801 "use this constructor.");
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.");
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 "
817 FHT::worthBuildingFixedHashTableInParallel<execution_space> ();
842 auto keys_h = Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace(),
844 firstContigKey_ =
keys_h[0];
848 lastContigKey_ = firstContigKey_ + 1;
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.");
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);
932 Kokkos::deep_copy(execution_space(), theKeysHost, 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];
951 Kokkos::deep_copy (execution_space(), counts, countsHost);
957 execution_space().fence ();
960 typename ptr_type::non_const_type ptr (
"Tpetra::FixedHashTable::ptr", size+1);
975 using ::Tpetra::Details::computeOffsetsFromCounts;
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;
993 Kokkos::deep_copy (execution_space(), ptr, ptr_h);
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;
1062 Kokkos::deep_copy(counts, counts_h);
1063 Kokkos::deep_copy(val, val_h);
1078 minKey_ = result.minKey_;
1079 maxKey_ = result.maxKey_;
1084template<
class KeyType,
class ValueType,
class DeviceType>
1086FixedHashTable<KeyType, ValueType, DeviceType>::
1087init (
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.");
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.");
1198 Kokkos::deep_copy(ptr, ptr_h);
1199 Kokkos::deep_copy(val, val_h);
1203 minKey_ = result.minKey_;
1204 maxKey_ = result.maxKey_;
1208template <
class KeyType,
class ValueType,
class DeviceType>
1213 if (! checkedForDuplicateKeys_) {
1214 hasDuplicateKeys_ = checkForDuplicateKeys ();
1215 checkedForDuplicateKeys_ =
true;
1217 return hasDuplicateKeys_;
1220template <
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;
1236 typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
1242template <
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 () <<
" }";
1256template <
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;
1282 out << this->description() <<
endl;
1285 out <<
"FixedHashTable:" <<
endl;
1293 out <<
"Template parameters:" <<
endl;
1300 const offset_type
tableSize = this->getSize ();
1301 const offset_type
numKeys = val_.extent (0);
1303 out <<
"Table parameters:" <<
endl;
1311 out <<
"Contents: ";
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]) {