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 () {
86 return ExecSpace::concurrency() > 1;
99 template<
class KeyType,
101 class InputExecSpace,
102 class OutputExecSpace,
103 const bool mustDeepCopy =
104 ! std::is_same<
typename InputExecSpace::memory_space,
105 typename OutputExecSpace::memory_space>::value>
106 struct DeepCopyIfNeeded {
112 template<
class KeyType,
114 class InputExecSpace,
115 class OutputExecSpace>
116 struct DeepCopyIfNeeded<KeyType, ArrayLayout, InputExecSpace, OutputExecSpace, true>
118 typedef Kokkos::View<
const KeyType*, ArrayLayout,
119 InputExecSpace, Kokkos::MemoryUnmanaged> input_view_type;
125 typedef Kokkos::View<const KeyType*, ArrayLayout, OutputExecSpace> output_view_type;
127 static output_view_type copy (
const input_view_type& src) {
128 typedef typename output_view_type::non_const_type NC;
130 NC dst (Kokkos::ViewAllocateWithoutInitializing (src.tracker ().label ()),
133 return output_view_type (dst);
138 template<
class KeyType,
140 class InputExecSpace,
141 class OutputExecSpace>
142 struct DeepCopyIfNeeded<KeyType, ArrayLayout, InputExecSpace, OutputExecSpace, false> {
143 typedef Kokkos::View<
const KeyType*, ArrayLayout,
144 InputExecSpace, Kokkos::MemoryUnmanaged> input_view_type;
145 typedef Kokkos::View<
const KeyType*, ArrayLayout, OutputExecSpace,
146 Kokkos::MemoryUnmanaged> output_view_type;
148 static output_view_type copy (
const input_view_type& src) {
149 return output_view_type (src);
171 template<
class CountsViewType,
173 class SizeType =
typename KeysViewType::size_type>
176 typedef CountsViewType counts_view_type;
177 typedef KeysViewType keys_view_type;
178 typedef typename CountsViewType::execution_space execution_space;
179 typedef typename CountsViewType::memory_space memory_space;
180 typedef SizeType size_type;
181 typedef typename keys_view_type::non_const_value_type key_type;
197 const keys_view_type& keys,
198 const size_type size) :
208 KOKKOS_INLINE_FUNCTION
void
214 Kokkos::atomic_increment (&counts_[hashVal]);
217 using value_type = Kokkos::pair<int, key_type>;
222 KOKKOS_INLINE_FUNCTION
void
227 const key_type keyVal = keys_[i];
229 if (hashVal < hash_value_type (0) ||
230 hashVal >= hash_value_type (counts_.extent (0))) {
235 Kokkos::atomic_increment (&counts_[hashVal]);
240 KOKKOS_INLINE_FUNCTION
void init (value_type& dst)
const
243 dst.second = key_type (0);
246 KOKKOS_INLINE_FUNCTION
void
247 join (
volatile value_type& dst,
248 const volatile value_type& src)
const
250 const bool good = dst.first == 0 || src.first == 0;
251 dst.first = good ? 0 : dst.first;
257 counts_view_type counts_;
259 keys_view_type keys_;
274 template<
class KeyType>
276 KOKKOS_INLINE_FUNCTION
278 minKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
291 maxKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
292 ::Kokkos::Details::ArithTraits<KeyType>::min () :
293 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
296 static_assert (std::is_arithmetic<KeyType>::value,
"FillPairsResult: "
297 "KeyType must be some kind of number type.");
300 KOKKOS_INLINE_FUNCTION
301 FillPairsResult (
const KeyType& initMinKey,
302 const KeyType& initMaxKey) :
307 static_assert (std::is_arithmetic<KeyType>::value,
"FillPairsResult: "
308 "KeyType must be some kind of number type.");
345 template<
class PairsViewType,
347 class CountsViewType,
348 class SizeType =
typename KeysViewType::size_type>
351 typedef typename CountsViewType::non_const_type counts_view_type;
352 typedef typename counts_view_type::const_type offsets_view_type;
354 typedef PairsViewType pairs_view_type;
355 typedef typename KeysViewType::const_type keys_view_type;
356 typedef typename offsets_view_type::execution_space execution_space;
357 typedef typename offsets_view_type::memory_space memory_space;
358 typedef SizeType size_type;
360 typedef typename keys_view_type::non_const_value_type key_type;
361 typedef typename pairs_view_type::non_const_value_type pair_type;
385 const counts_view_type& counts,
386 const offsets_view_type& ptr,
387 const keys_view_type& keys,
388 const typename pair_type::second_type startingValue) :
393 size_ (counts.extent (0)),
394 startingValue_ (startingValue),
395 initMinKey_ (::Kokkos::Details::ArithTraits<key_type>::max ()),
396 initMaxKey_ (::Kokkos::Details::ArithTraits<key_type>::is_integer ?
397 ::Kokkos::Details::ArithTraits<key_type>::min () :
398 -::Kokkos::Details::ArithTraits<key_type>::max ())
420 const counts_view_type& counts,
421 const offsets_view_type& ptr,
422 const keys_view_type& keys,
423 const typename pair_type::second_type startingValue,
424 const key_type initMinKey,
425 const key_type initMaxKey) :
430 size_ (counts.extent (0)),
431 startingValue_ (startingValue),
432 initMinKey_ (initMinKey),
433 initMaxKey_ (initMaxKey)
444 KOKKOS_INLINE_FUNCTION
void
445 join (
volatile value_type& dst,
446 const volatile value_type& src)
const
448 if (src.maxKey_ > dst.maxKey_) {
449 dst.maxKey_ = src.maxKey_;
451 if (src.minKey_ < dst.minKey_) {
452 dst.minKey_ = src.minKey_;
454 dst.success_ = dst.success_ && src.success_;
461 KOKKOS_INLINE_FUNCTION
void
465 typedef typename offsets_view_type::non_const_value_type offset_type;
466 typedef typename pair_type::second_type val_type;
467 typedef typename std::remove_reference< decltype( counts_[0] ) >::type atomic_incr_type;
469 const key_type key = keys_[i];
476 const val_type theVal = startingValue_ +
static_cast<val_type
> (i);
480 const offset_type count = Kokkos::atomic_fetch_add (&counts_[hashVal], atomic_incr_type(-1));
485 const offset_type curPos = ptr_[hashVal+1] - count;
487 pairs_[curPos].first = key;
488 pairs_[curPos].second = theVal;
493 pairs_view_type pairs_;
494 counts_view_type counts_;
495 offsets_view_type ptr_;
496 keys_view_type keys_;
498 typename pair_type::second_type startingValue_;
500 key_type initMinKey_;
502 key_type initMaxKey_;
528 template<
class OffsetsViewType,
530 class SizeType =
typename OffsetsViewType::size_type>
533 typedef typename OffsetsViewType::const_type offsets_view_type;
534 typedef typename PairsViewType::const_type pairs_view_type;
535 typedef typename offsets_view_type::execution_space execution_space;
536 typedef typename offsets_view_type::memory_space memory_space;
537 typedef SizeType size_type;
540 typedef int value_type;
547 const offsets_view_type& ptr) :
550 size_ (ptr_.extent (0) == 0 ?
556 KOKKOS_INLINE_FUNCTION
void init (value_type& dst)
const
562 KOKKOS_INLINE_FUNCTION
void
563 join (
volatile value_type& dst,
564 const volatile value_type& src)
const
566 dst = dst + src > 0?1:0;
570 KOKKOS_INLINE_FUNCTION
void
573 typedef typename offsets_view_type::non_const_value_type offset_type;
574 typedef typename pairs_view_type::non_const_value_type pair_type;
575 typedef typename pair_type::first_type key_type;
581 const offset_type beg = ptr_[i];
582 const offset_type end = ptr_[i+1];
583 bool foundDuplicateKey =
false;
588 for (offset_type j = beg + 1; j < end; ++j) {
589 const key_type curKey = pairs_[j].first;
590 for (offset_type k = beg; k < j; ++k) {
591 if (pairs_[k].first == curKey) {
592 foundDuplicateKey =
true;
597 dst = (dst>0) || foundDuplicateKey?1:0;
602 pairs_view_type pairs_;
603 offsets_view_type ptr_;
613 template<
class KeyType,
class ValueType,
class DeviceType>
623 return keys_.extent (0) == val_.extent (0);
626 template<
class KeyType,
class ValueType,
class DeviceType>
635 template<
class KeyType,
class ValueType,
class DeviceType>
638 minKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
639 maxKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
640 ::Kokkos::Details::ArithTraits<KeyType>::min () :
641 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
642 minVal_ (::Kokkos::Details::ArithTraits<ValueType>::max ()),
643 maxVal_ (::Kokkos::Details::ArithTraits<ValueType>::is_integer ?
644 ::Kokkos::Details::ArithTraits<ValueType>::min () :
645 -::Kokkos::Details::ArithTraits<ValueType>::max ()),
646 firstContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
647 lastContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
648 ::Kokkos::Details::ArithTraits<KeyType>::min () :
649 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
650 contiguousValues_ (true),
651 checkedForDuplicateKeys_ (true),
652 hasDuplicateKeys_ (false)
654 #ifdef HAVE_TPETRA_DEBUG
656 #endif // HAVE_TPETRA_DEBUG
659 template<
class KeyType,
class ValueType,
class DeviceType>
663 minKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
664 maxKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
665 ::Kokkos::Details::ArithTraits<KeyType>::min () :
666 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
668 maxVal_ (keys.size () == 0 ?
669 static_cast<ValueType> (0) :
670 static_cast<ValueType> (keys.size () - 1)),
671 firstContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
672 lastContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
673 ::Kokkos::Details::ArithTraits<KeyType>::min () :
674 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
675 contiguousValues_ (true),
676 checkedForDuplicateKeys_ (false),
677 hasDuplicateKeys_ (false)
679 const ValueType startingValue =
static_cast<ValueType
> (0);
680 const KeyType initMinKey = this->minKey_;
681 const KeyType initMaxKey = this->maxKey_;
682 this->init (keys, startingValue, initMinKey, initMaxKey,
683 initMinKey, initMinKey,
false);
685 #ifdef HAVE_TPETRA_DEBUG
687 #endif // HAVE_TPETRA_DEBUG
690 template<
class KeyType,
class ValueType,
class DeviceType>
693 const bool keepKeys) :
694 minKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
695 maxKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
696 ::Kokkos::Details::ArithTraits<KeyType>::min () :
697 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
699 maxVal_ (keys.size () == 0 ?
700 static_cast<ValueType> (0) :
701 static_cast<ValueType> (keys.size () - 1)),
702 firstContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
703 lastContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
704 ::Kokkos::Details::ArithTraits<KeyType>::min () :
705 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
706 contiguousValues_ (true),
707 checkedForDuplicateKeys_ (false),
708 hasDuplicateKeys_ (false)
710 typedef typename keys_type::non_const_type nonconst_keys_type;
715 const ValueType startingValue =
static_cast<ValueType
> (0);
716 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
718 using Kokkos::ViewAllocateWithoutInitializing;
719 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
722 const KeyType initMinKey = this->minKey_;
723 const KeyType initMaxKey = this->maxKey_;
724 this->init (keys_d, startingValue, initMinKey, initMaxKey,
725 initMinKey, initMinKey,
false);
728 #ifdef HAVE_TPETRA_DEBUG
729 typedef typename keys_type::size_type size_type;
730 TEUCHOS_TEST_FOR_EXCEPTION
731 (keys_.extent (0) !=
static_cast<size_type
> (keys.size ()),
732 std::logic_error,
"Tpetra::Details::FixedHashTable constructor: "
733 "keepKeys is true, but on return, keys_.extent(0) = " <<
734 keys_.extent (0) <<
" != keys.size() = " << keys.size () <<
735 ". Please report this bug to the Tpetra developers.");
736 #endif // HAVE_TPETRA_DEBUG
739 #ifdef HAVE_TPETRA_DEBUG
741 #endif // HAVE_TPETRA_DEBUG
744 template<
class KeyType,
class ValueType,
class DeviceType>
747 const ValueType startingValue,
748 const bool keepKeys) :
749 minKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
750 maxKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
751 ::Kokkos::Details::ArithTraits<KeyType>::min () :
752 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
753 minVal_ (startingValue),
754 maxVal_ (keys.size () == 0 ?
756 static_cast<ValueType> (startingValue + keys.size () - 1)),
757 firstContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
758 lastContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
759 ::Kokkos::Details::ArithTraits<KeyType>::min () :
760 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
761 contiguousValues_ (true),
762 checkedForDuplicateKeys_ (false),
763 hasDuplicateKeys_ (false)
765 typedef typename keys_type::non_const_type nonconst_keys_type;
770 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
772 using Kokkos::ViewAllocateWithoutInitializing;
773 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
777 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
790 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
791 ::Kokkos::Details::ArithTraits<KeyType>::min () :
792 -::Kokkos::Details::ArithTraits<KeyType>::max ();
793 this->init (keys_d, startingValue, initMinKey, initMaxKey,
794 initMinKey, initMinKey,
false);
797 #ifdef HAVE_TPETRA_DEBUG
798 typedef typename keys_type::size_type size_type;
799 TEUCHOS_TEST_FOR_EXCEPTION
800 (keys_.extent (0) !=
static_cast<size_type
> (keys.size ()),
801 std::logic_error,
"Tpetra::Details::FixedHashTable constructor: "
802 "keepKeys is true, but on return, keys_.extent(0) = " <<
803 keys_.extent (0) <<
" != keys.size() = " << keys.size () <<
804 ". Please report this bug to the Tpetra developers.");
805 #endif // HAVE_TPETRA_DEBUG
808 #ifdef HAVE_TPETRA_DEBUG
810 #endif // HAVE_TPETRA_DEBUG
813 template<
class KeyType,
class ValueType,
class DeviceType>
816 const KeyType firstContigKey,
817 const KeyType lastContigKey,
818 const ValueType startingValue,
819 const bool keepKeys) :
820 minKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
821 maxKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
822 ::Kokkos::Details::ArithTraits<KeyType>::min () :
823 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
824 minVal_ (startingValue),
825 maxVal_ (keys.size () == 0 ?
827 static_cast<ValueType> (startingValue + keys.size () - 1)),
828 firstContigKey_ (firstContigKey),
829 lastContigKey_ (lastContigKey),
830 contiguousValues_ (true),
831 checkedForDuplicateKeys_ (false),
832 hasDuplicateKeys_ (false)
834 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
847 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
848 ::Kokkos::Details::ArithTraits<KeyType>::min () :
849 -::Kokkos::Details::ArithTraits<KeyType>::max ();
850 this->init (keys, startingValue, initMinKey, initMaxKey,
851 firstContigKey, lastContigKey,
true);
854 #ifdef HAVE_TPETRA_DEBUG
855 typedef typename keys_type::size_type size_type;
856 TEUCHOS_TEST_FOR_EXCEPTION
857 (keys_.extent (0) !=
static_cast<size_type
> (keys.size ()),
858 std::logic_error,
"Tpetra::Details::FixedHashTable constructor: "
859 "keepKeys is true, but on return, keys_.extent(0) = " <<
860 keys_.extent (0) <<
" != keys.size() = " << keys.size () <<
861 ". Please report this bug to the Tpetra developers.");
862 #endif // HAVE_TPETRA_DEBUG
865 #ifdef HAVE_TPETRA_DEBUG
867 #endif // HAVE_TPETRA_DEBUG
870 template<
class KeyType,
class ValueType,
class DeviceType>
873 const KeyType firstContigKey,
874 const KeyType lastContigKey,
875 const ValueType startingValue,
876 const bool keepKeys) :
877 minKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
878 maxKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
879 ::Kokkos::Details::ArithTraits<KeyType>::min () :
880 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
881 minVal_ (startingValue),
882 maxVal_ (keys.size () == 0 ?
884 static_cast<ValueType> (startingValue + keys.size () - 1)),
885 firstContigKey_ (firstContigKey),
886 lastContigKey_ (lastContigKey),
887 contiguousValues_ (true),
888 checkedForDuplicateKeys_ (false),
889 hasDuplicateKeys_ (false)
891 typedef typename keys_type::non_const_type nonconst_keys_type;
896 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
898 using Kokkos::ViewAllocateWithoutInitializing;
899 nonconst_keys_type keys_d (ViewAllocateWithoutInitializing (
"FixedHashTable::keys"),
903 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
916 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
917 ::Kokkos::Details::ArithTraits<KeyType>::min () :
918 -::Kokkos::Details::ArithTraits<KeyType>::max ();
919 this->init (keys_d, startingValue, initMinKey, initMaxKey,
920 firstContigKey, lastContigKey,
true);
923 #ifdef HAVE_TPETRA_DEBUG
924 typedef typename keys_type::size_type size_type;
925 TEUCHOS_TEST_FOR_EXCEPTION
926 (keys_.extent (0) !=
static_cast<size_type
> (keys.size ()),
927 std::logic_error,
"Tpetra::Details::FixedHashTable constructor: "
928 "keepKeys is true, but on return, keys_.extent(0) = " <<
929 keys_.extent (0) <<
" != keys.size() = " << keys.size () <<
930 ". Please report this bug to the Tpetra developers.");
931 #endif // HAVE_TPETRA_DEBUG
934 #ifdef HAVE_TPETRA_DEBUG
936 #endif // HAVE_TPETRA_DEBUG
939 template<
class KeyType,
class ValueType,
class DeviceType>
942 const ValueType startingValue) :
944 minKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
945 maxKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
946 ::Kokkos::Details::ArithTraits<KeyType>::min () :
947 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
948 minVal_ (startingValue),
949 maxVal_ (keys.size () == 0 ?
951 static_cast<ValueType> (startingValue + keys.size () - 1)),
952 firstContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
953 lastContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
954 ::Kokkos::Details::ArithTraits<KeyType>::min () :
955 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
956 contiguousValues_ (true),
957 checkedForDuplicateKeys_ (false),
958 hasDuplicateKeys_ (false)
960 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
973 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
974 ::Kokkos::Details::ArithTraits<KeyType>::min () :
975 -::Kokkos::Details::ArithTraits<KeyType>::max ();
976 this->init (keys, startingValue, initMinKey, initMaxKey,
977 initMinKey, initMinKey,
false);
979 #ifdef HAVE_TPETRA_DEBUG
981 #endif // HAVE_TPETRA_DEBUG
984 template<
class KeyType,
class ValueType,
class DeviceType>
987 const Teuchos::ArrayView<const ValueType>& vals) :
988 minKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
989 maxKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
990 ::Kokkos::Details::ArithTraits<KeyType>::min () :
991 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
992 minVal_ (::Kokkos::Details::ArithTraits<ValueType>::max ()),
993 maxVal_ (::Kokkos::Details::ArithTraits<ValueType>::is_integer ?
994 ::Kokkos::Details::ArithTraits<ValueType>::min () :
995 -::Kokkos::Details::ArithTraits<ValueType>::max ()),
996 firstContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::max ()),
997 lastContigKey_ (::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
998 ::Kokkos::Details::ArithTraits<KeyType>::min () :
999 -::Kokkos::Details::ArithTraits<KeyType>::max ()),
1000 contiguousValues_ (false),
1001 checkedForDuplicateKeys_ (false),
1002 hasDuplicateKeys_ (false)
1007 host_input_keys_type keys_k (keys.size () == 0 ? NULL : keys.getRawPtr (),
1009 host_input_vals_type vals_k (vals.size () == 0 ? NULL : vals.getRawPtr (),
1011 const KeyType initMinKey = ::Kokkos::Details::ArithTraits<KeyType>::max ();
1024 const KeyType initMaxKey = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
1025 ::Kokkos::Details::ArithTraits<KeyType>::min () :
1026 -::Kokkos::Details::ArithTraits<KeyType>::max ();
1027 this->init (keys_k, vals_k, initMinKey, initMaxKey);
1029 #ifdef HAVE_TPETRA_DEBUG
1031 #endif // HAVE_TPETRA_DEBUG
1034 template<
class KeyType,
class ValueType,
class DeviceType>
1037 init (
const keys_type& keys,
1038 ValueType startingValue,
1041 KeyType firstContigKey,
1042 KeyType lastContigKey,
1043 const bool computeInitContigKeys)
1045 using Kokkos::subview;
1046 using Kokkos::ViewAllocateWithoutInitializing;
1047 using Teuchos::TypeNameTraits;
1048 typedef typename std::decay<decltype (keys.extent (0)) >::type size_type;
1049 const char prefix[] =
"Tpetra::Details::FixedHashTable: ";
1051 const offset_type numKeys =
static_cast<offset_type
> (keys.extent (0));
1053 const offset_type theMaxVal = ::Kokkos::Details::ArithTraits<offset_type>::max ();
1054 const size_type maxValST =
static_cast<size_type
> (theMaxVal);
1055 TEUCHOS_TEST_FOR_EXCEPTION
1056 (keys.extent (0) > maxValST, std::invalid_argument, prefix <<
"The "
1057 "number of keys " << keys.extent (0) <<
" does not fit in "
1058 "offset_type = " << TypeNameTraits<offset_type>::name () <<
", whose "
1059 "max value is " << theMaxVal <<
". This means that it is not possible to "
1060 "use this constructor.");
1062 TEUCHOS_TEST_FOR_EXCEPTION
1063 (static_cast<unsigned long long> (numKeys) >
1064 static_cast<unsigned long long> (::Kokkos::Details::ArithTraits<ValueType>::max ()),
1065 std::invalid_argument,
"Tpetra::Details::FixedHashTable: The number of "
1066 "keys " << numKeys <<
" is greater than the maximum representable "
1067 "ValueType value " << ::Kokkos::Details::ArithTraits<ValueType>::max () <<
". "
1068 "This means that it is not possible to use this constructor.");
1069 TEUCHOS_TEST_FOR_EXCEPTION
1070 (numKeys > static_cast<offset_type> (INT_MAX), std::logic_error, prefix <<
1071 "This class currently only works when the number of keys is <= INT_MAX = "
1072 << INT_MAX <<
". If this is a problem for you, please talk to the Tpetra "
1075 const bool buildInParallel =
1076 FHT::worthBuildingFixedHashTableInParallel<execution_space> ();
1087 if (computeInitContigKeys) {
1106 firstContigKey_ = keys[0];
1110 lastContigKey_ = firstContigKey_ + 1;
1116 for (offset_type k = 1; k < numKeys; ++k) {
1117 if (lastContigKey_ != keys[k]) {
1126 firstContigKey_ = firstContigKey;
1127 lastContigKey_ = lastContigKey;
1130 offset_type startIndex;
1132 initMinKey = std::min (initMinKey, firstContigKey_);
1133 initMaxKey = std::max (initMaxKey, lastContigKey_);
1134 startIndex =
static_cast<offset_type
> (lastContigKey_ - firstContigKey_);
1139 const offset_type theNumKeys = numKeys - startIndex;
1140 const offset_type size = hash_type::getRecommendedSize (theNumKeys);
1141 #ifdef HAVE_TPETRA_DEBUG
1142 TEUCHOS_TEST_FOR_EXCEPTION(
1143 size == 0 && numKeys != 0, std::logic_error,
1144 "Tpetra::Details::FixedHashTable constructor: "
1145 "getRecommendedSize(" << numKeys <<
") returned zero, "
1146 "even though the number of keys " << numKeys <<
" is nonzero. "
1147 "Please report this bug to the Tpetra developers.");
1148 #endif // HAVE_TPETRA_DEBUG
1150 subview (keys, std::pair<offset_type, offset_type> (startIndex, numKeys));
1157 typedef typename ptr_type::non_const_type counts_type;
1158 counts_type counts (
"FixedHashTable::counts", size);
1169 if (buildInParallel) {
1170 FHT::CountBuckets<counts_type, keys_type> functor (counts, theKeys, size);
1171 using execution_space =
typename counts_type::execution_space;
1172 using range_type = Kokkos::RangePolicy<execution_space, offset_type>;
1173 const char kernelLabel[] =
"Tpetra::Details::FixedHashTable CountBuckets";
1175 using key_type =
typename keys_type::non_const_value_type;
1176 Kokkos::pair<int, key_type> err;
1177 Kokkos::parallel_reduce (kernelLabel, range_type (0, theNumKeys),
1179 TEUCHOS_TEST_FOR_EXCEPTION
1180 (err.first != 0, std::logic_error,
"Tpetra::Details::FixedHashTable "
1181 "constructor: CountBuckets found a key " << err.second <<
" that "
1182 "results in an out-of-bounds hash value.");
1185 Kokkos::parallel_for (kernelLabel, range_type (0, theNumKeys), functor);
1193 auto countsHost = Kokkos::create_mirror_view (counts);
1197 for (offset_type k = 0; k < theNumKeys; ++k) {
1198 using key_type =
typename keys_type::non_const_value_type;
1199 const key_type key = theKeys[k];
1201 using hash_value_type =
typename hash_type::result_type;
1202 const hash_value_type hashVal = hash_type::hashFunc (key, size);
1203 TEUCHOS_TEST_FOR_EXCEPTION
1204 (hashVal < hash_value_type (0) ||
1205 hashVal >= hash_value_type (countsHost.extent (0)),
1206 std::logic_error,
"Tpetra::Details::FixedHashTable "
1207 "constructor: Sequential CountBuckets found a key " << key
1208 <<
" that results in an out-of-bounds hash value.");
1210 ++countsHost[hashVal];
1217 execution_space().fence ();
1220 typename ptr_type::non_const_type ptr (
"FixedHashTable::ptr", size+1);
1236 if (buildInParallel) {
1240 if (! buildInParallel || debug) {
1241 Kokkos::HostSpace hostMemSpace;
1242 auto counts_h = Kokkos::create_mirror_view (hostMemSpace, counts);
1244 auto ptr_h = Kokkos::create_mirror_view (hostMemSpace, ptr);
1246 #ifdef KOKKOS_ENABLE_SERIAL
1247 Kokkos::Serial hostExecSpace;
1249 Kokkos::DefaultHostExecutionSpace hostExecSpace;
1250 #endif // KOKKOS_ENABLE_SERIAL
1257 for (offset_type i = 0; i < size; ++i) {
1258 if (ptr_h[i+1] != ptr_h[i] + counts_h[i]) {
1262 TEUCHOS_TEST_FOR_EXCEPTION
1263 (bad, std::logic_error,
"Tpetra::Details::FixedHashTable "
1264 "constructor: computeOffsetsFromCounts gave an incorrect "
1271 execution_space().fence ();
1275 using Kokkos::ViewAllocateWithoutInitializing;
1276 typedef typename val_type::non_const_type nonconst_val_type;
1277 nonconst_val_type val (ViewAllocateWithoutInitializing (
"FixedHashTable::pairs"),
1281 typedef FHT::FillPairs<
typename val_type::non_const_type, keys_type,
1282 typename ptr_type::non_const_type> functor_type;
1283 typename functor_type::value_type result (initMinKey, initMaxKey);
1285 const ValueType newStartingValue = startingValue +
static_cast<ValueType
> (startIndex);
1286 if (buildInParallel) {
1287 functor_type functor (val, counts, ptr, theKeys, newStartingValue,
1288 initMinKey, initMaxKey);
1289 typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
1290 Kokkos::parallel_reduce (range_type (0, theNumKeys), functor, result);
1293 for (offset_type k = 0; k < theNumKeys; ++k) {
1294 typedef typename hash_type::result_type hash_value_type;
1295 const KeyType key = theKeys[k];
1296 if (key > result.maxKey_) {
1297 result.maxKey_ = key;
1299 if (key < result.minKey_) {
1300 result.minKey_ = key;
1302 const ValueType theVal = newStartingValue +
static_cast<ValueType
> (k);
1303 const hash_value_type hashVal = hash_type::hashFunc (key, size);
1309 const offset_type count = counts[hashVal];
1312 result.success_ =
false;
1317 const offset_type curPos = ptr[hashVal+1] - count;
1320 val[curPos].first = key;
1321 val[curPos].second = theVal;
1338 minKey_ = result.minKey_;
1339 maxKey_ = result.maxKey_;
1344 template<
class KeyType,
class ValueType,
class DeviceType>
1346 FixedHashTable<KeyType, ValueType, DeviceType>::
1347 init (
const host_input_keys_type& keys,
1348 const host_input_vals_type& vals,
1352 const offset_type numKeys =
static_cast<offset_type
> (keys.extent (0));
1353 TEUCHOS_TEST_FOR_EXCEPTION
1354 (static_cast<unsigned long long> (numKeys) > static_cast<unsigned long long> (::Kokkos::Details::ArithTraits<ValueType>::max ()),
1355 std::invalid_argument,
"Tpetra::Details::FixedHashTable: The number of "
1356 "keys " << numKeys <<
" is greater than the maximum representable "
1357 "ValueType value " << ::Kokkos::Details::ArithTraits<ValueType>::max () <<
".");
1358 TEUCHOS_TEST_FOR_EXCEPTION
1359 (numKeys > static_cast<offset_type> (INT_MAX), std::logic_error,
"Tpetra::"
1360 "Details::FixedHashTable: This class currently only works when the number "
1361 "of keys is <= INT_MAX = " << INT_MAX <<
". If this is a problem for you"
1362 ", please talk to the Tpetra developers.");
1369 const offset_type size = hash_type::getRecommendedSize (numKeys);
1370 #ifdef HAVE_TPETRA_DEBUG
1371 TEUCHOS_TEST_FOR_EXCEPTION(
1372 size == 0 && numKeys != 0, std::logic_error,
1373 "Tpetra::Details::FixedHashTable constructor: "
1374 "getRecommendedSize(" << numKeys <<
") returned zero, "
1375 "even though the number of keys " << numKeys <<
" is nonzero. "
1376 "Please report this bug to the Tpetra developers.");
1377 #endif // HAVE_TPETRA_DEBUG
1387 typename ptr_type::non_const_type ptr (
"FixedHashTable::ptr", size + 1);
1391 using Kokkos::ViewAllocateWithoutInitializing;
1392 typedef typename val_type::non_const_type nonconst_val_type;
1393 nonconst_val_type val (ViewAllocateWithoutInitializing (
"FixedHashTable::pairs"),
1397 for (offset_type k = 0; k < numKeys; ++k) {
1398 const typename hash_type::result_type hashVal =
1399 hash_type::hashFunc (keys[k], size);
1411 for (offset_type i = 0; i < size; ++i) {
1417 typename ptr_type::non_const_type curRowStart (
"FixedHashTable::curRowStart", size);
1420 FHT::FillPairsResult<KeyType> result (initMinKey, initMaxKey);
1421 for (offset_type k = 0; k < numKeys; ++k) {
1422 typedef typename hash_type::result_type hash_value_type;
1423 const KeyType key = keys[k];
1424 if (key > result.maxKey_) {
1425 result.maxKey_ = key;
1427 if (key < result.minKey_) {
1428 result.minKey_ = key;
1430 const ValueType theVal = vals[k];
1431 if (theVal > maxVal_) {
1434 if (theVal < minVal_) {
1437 const hash_value_type hashVal = hash_type::hashFunc (key, size);
1439 const offset_type offset = curRowStart[hashVal];
1440 const offset_type curPos = ptr[hashVal] + offset;
1441 if (curPos >= ptr[hashVal+1]) {
1442 result.success_ =
false;
1445 val[curPos].first = key;
1446 val[curPos].second = theVal;
1447 ++curRowStart[hashVal];
1451 TEUCHOS_TEST_FOR_EXCEPTION
1452 (! result.success_, std::logic_error,
"Tpetra::Details::FixedHashTable::"
1453 "init: Filling the hash table failed! Please report this bug to the "
1454 "Tpetra developers.");
1459 minKey_ = result.minKey_;
1460 maxKey_ = result.maxKey_;
1464 template <
class KeyType,
class ValueType,
class DeviceType>
1469 if (! checkedForDuplicateKeys_) {
1470 hasDuplicateKeys_ = checkForDuplicateKeys ();
1471 checkedForDuplicateKeys_ =
true;
1473 return hasDuplicateKeys_;
1476 template <
class KeyType,
class ValueType,
class DeviceType>
1481 const offset_type size = this->getSize ();
1485 if (size == 0 || this->numPairs () == 0) {
1489 typedef FHT::CheckForDuplicateKeys<ptr_type, val_type> functor_type;
1490 functor_type functor (val_, ptr_);
1492 typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
1493 Kokkos::parallel_reduce (range_type (0, size), functor, hasDupKeys);
1494 return hasDupKeys > 0;
1498 template <
class KeyType,
class ValueType,
class DeviceType>
1503 std::ostringstream oss;
1504 oss <<
"FixedHashTable<"
1505 << Teuchos::TypeNameTraits<KeyType>::name () <<
","
1506 << Teuchos::TypeNameTraits<ValueType>::name () <<
">: "
1507 <<
"{ numKeys: " << val_.extent (0)
1508 <<
", tableSize: " << this->getSize () <<
" }";
1512 template <
class KeyType,
class ValueType,
class DeviceType>
1516 const Teuchos::EVerbosityLevel verbLevel)
const
1520 using Teuchos::OSTab;
1521 using Teuchos::rcpFromRef;
1522 using Teuchos::TypeNameTraits;
1523 using Teuchos::VERB_DEFAULT;
1524 using Teuchos::VERB_NONE;
1525 using Teuchos::VERB_LOW;
1526 using Teuchos::VERB_EXTREME;
1531 Teuchos::EVerbosityLevel vl = verbLevel;
1532 if (vl == VERB_DEFAULT) vl = VERB_LOW;
1534 if (vl == VERB_NONE) {
1537 else if (vl == VERB_LOW) {
1538 out << this->description() << endl;
1541 out <<
"FixedHashTable:" << endl;
1543 OSTab tab1 (rcpFromRef (out));
1549 out <<
"Template parameters:" << endl;
1551 OSTab tab2 (rcpFromRef (out));
1552 out <<
"KeyType: " << TypeNameTraits<KeyType>::name () << endl
1553 <<
"ValueType: " << TypeNameTraits<ValueType>::name () << endl;
1556 const offset_type tableSize = this->getSize ();
1557 const offset_type numKeys = val_.extent (0);
1559 out <<
"Table parameters:" << endl;
1561 OSTab tab2 (rcpFromRef (out));
1562 out <<
"numKeys: " << numKeys << endl
1563 <<
"tableSize: " << tableSize << endl;
1566 if (vl >= VERB_EXTREME) {
1567 out <<
"Contents: ";
1568 if (tableSize == 0 || numKeys == 0) {
1569 out <<
"[]" << endl;
1571 out <<
"[ " << endl;
1573 OSTab tab2 (rcpFromRef (out));
1574 for (offset_type i = 0; i < tableSize; ++i) {
1575 OSTab tab3 (rcpFromRef (out));
1577 for (offset_type k = ptr_[i]; k < ptr_[i+1]; ++k) {
1578 out <<
"(" << val_[k].first <<
"," << val_[k].second <<
")";
1579 if (k + 1 < ptr_[i+1]) {
1605 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT_DEFAULTNODE(LO,GO) \
1606 template class FixedHashTable< GO , LO >;
1617 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, DEVICE) \
1618 template class FixedHashTable< GO , LO , DEVICE >;
1620 #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_INLINE_FUNCTION void join(volatile value_type &dst, const volatile value_type &src) const
Combine two intermediate reduction results.
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 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.
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_.
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.
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
bool hasDuplicateKeys()
Whether the table has any duplicate keys.
static KOKKOS_INLINE_FUNCTION result_type hashFunc(const argument_type &key, const offset_type &size)
The hash function.
CountBuckets(const counts_view_type &counts, const keys_view_type &keys, const size_type size)
Constructor.
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
Functor for checking whether a FixedHashTable has one or more duplicate entries.
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.