Tpetra parallel linear algebra  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Tpetra_Details_FixedHashTable_decl.hpp
1 /*
2 // @HEADER
3 // ***********************************************************************
4 //
5 // Tpetra: Templated Linear Algebra Services Package
6 // Copyright (2008) Sandia Corporation
7 //
8 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9 // the U.S. Government retains certain rights in this software.
10 //
11 // Redistribution and use in source and binary forms, with or without
12 // modification, are permitted provided that the following conditions are
13 // met:
14 //
15 // 1. Redistributions of source code must retain the above copyright
16 // notice, this list of conditions and the following disclaimer.
17 //
18 // 2. Redistributions in binary form must reproduce the above copyright
19 // notice, this list of conditions and the following disclaimer in the
20 // documentation and/or other materials provided with the distribution.
21 //
22 // 3. Neither the name of the Corporation nor the names of the
23 // contributors may be used to endorse or promote products derived from
24 // this software without specific prior written permission.
25 //
26 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 //
38 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
39 //
40 // ************************************************************************
41 // @HEADER
42 */
43 
44 #ifndef TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP
45 #define TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP
46 
47 #include "Tpetra_Details_Hash.hpp"
50 #include "Teuchos_Describable.hpp"
51 #include "Teuchos_FancyOStream.hpp"
52 #include "Teuchos_VerbosityLevel.hpp"
53 #include "Kokkos_Core.hpp"
54 #include "Kokkos_ArithTraits.hpp"
55 
56 namespace Tpetra {
57 namespace Details {
58 
84 template<class KeyType,
85  class ValueType,
86  class DeviceType>
88 private:
89  typedef typename DeviceType::execution_space execution_space;
90  typedef typename DeviceType::memory_space memory_space;
91  typedef Kokkos::Device<execution_space, memory_space> device_type;
92 
94  typedef typename hash_type::offset_type offset_type;
95 
103  typedef typename Kokkos::View<const offset_type*, Kokkos::LayoutLeft,
104  device_type> ptr_type;
111  typedef typename Kokkos::View<const Kokkos::pair<KeyType, ValueType>*,
112  Kokkos::LayoutLeft, device_type> val_type;
113 
120  KOKKOS_INLINE_FUNCTION bool hasContiguousValues () const {
121  return contiguousValues_;
122  }
123 
124 public:
128  typedef Kokkos::View<const KeyType*, Kokkos::LayoutLeft, device_type> keys_type;
129 
131  KOKKOS_DEFAULTED_FUNCTION FixedHashTable() = default;
132 
142  FixedHashTable (const keys_type& keys);
143 
151  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys);
152 
166  FixedHashTable (const keys_type& keys,
167  const ValueType startingValue);
168 
180  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
181  const ValueType startingValue);
182 
201  FixedHashTable (const keys_type& keys,
202  const KeyType firstContigKey,
203  const KeyType lastContigKey,
204  const ValueType startingValue);
205 
221  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
222  const KeyType firstContigKey,
223  const KeyType lastContigKey,
224  const ValueType startingValue);
225 
234  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
235  const Teuchos::ArrayView<const ValueType>& vals);
236 
237  template<class K, class V, class D>
238  friend class FixedHashTable;
239 
245  template<class InDeviceType>
247  typename std::enable_if<! std::is_same<DeviceType, InDeviceType>::value, int>::type* = NULL)
248  {
249  using Kokkos::ViewAllocateWithoutInitializing;
250  typedef typename ptr_type::non_const_type nonconst_ptr_type;
251  typedef typename val_type::non_const_type nonconst_val_type;
252 
253  // FIXME (mfh 28 May 2015) The code below _always_ copies. This
254  // shouldn't be necessary if the input and output memory spaces
255  // are the same. However, it is always correct.
256 
257  // Different Devices may have different offset_type, because
258  // offset_type comes from the memory space's size_type typedef.
259  // That's why we use a specialized deep copy function here instead
260  // of Kokkos::deep_copy.
261  nonconst_ptr_type ptr (ViewAllocateWithoutInitializing ("Tpetra::FixedHashTable::ptr"),
262  src.ptr_.extent (0));
263  ::Tpetra::Details::copyOffsets (ptr, src.ptr_);
264  nonconst_val_type val (ViewAllocateWithoutInitializing ("Tpetra::FixedHashTable::val"),
265  src.val_.extent (0));
266  // val and src.val_ have the same entry types, unlike (possibly)
267  // ptr and src.ptr_. Thus, we can use Kokkos::deep_copy here.
268  // DEEP_COPY REVIEW - DEVICE-TO-DEVICE
269  Kokkos::deep_copy (execution_space(), val, src.val_);
270 
271  this->ptr_ = ptr;
272  this->val_ = val;
273  this->minKey_ = src.minKey_;
274  this->maxKey_ = src.maxKey_;
275  this->minVal_ = src.minVal_;
276  this->maxVal_ = src.maxVal_;
277  this->firstContigKey_ = src.firstContigKey_;
278  this->lastContigKey_ = src.lastContigKey_;
279  this->contiguousValues_ = src.contiguousValues_;
280  this->checkedForDuplicateKeys_ = src.checkedForDuplicateKeys_;
281  this->hasDuplicateKeys_ = src.hasDuplicateKeys_;
282  }
283 
285  KOKKOS_INLINE_FUNCTION ValueType get (const KeyType& key) const {
286  const offset_type size = this->getSize ();
287  if (size == 0) {
288  // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
289  // because neither have the right device function markings.
290  return Tpetra::Details::OrdinalTraits<ValueType>::invalid ();
291  }
292 
293  // If this object assumes contiguous values, then it doesn't store
294  // the initial sequence of >= 1 contiguous keys in the table.
295  if (this->hasContiguousValues () &&
296  key >= firstContigKey_ && key <= lastContigKey_) {
297  return static_cast<ValueType> (key - firstContigKey_) + this->minVal ();
298  }
299 
300  const typename hash_type::result_type hashVal =
301  hash_type::hashFunc (key, size);
302 
303  const offset_type start = ptr_[hashVal];
304  const offset_type end = ptr_[hashVal+1];
305  for (offset_type k = start; k < end; ++k) {
306  if (val_[k].first == key) {
307  return val_[k].second;
308  }
309  }
310 
311  // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
312  // because neither have the right device function markings.
313  return Tpetra::Details::OrdinalTraits<ValueType>::invalid ();
314  }
315 
319  KOKKOS_INLINE_FUNCTION offset_type numPairs () const {
320  // NOTE (mfh 26 May 2015) Using val_.extent(0) only works
321  // because the table stores pairs with duplicate keys separately.
322  // If the table didn't do that, we would have to keep a separate
323  // numPairs_ field (remembering the size of the input array of
324  // keys).
325  if (this->hasContiguousValues ()) {
326  return val_.extent (0) + static_cast<offset_type> (lastContigKey_ - firstContigKey_);
327  }
328  else {
329  return val_.extent (0);
330  }
331  }
332 
341  KOKKOS_INLINE_FUNCTION KeyType minKey () const {
342  return minKey_;
343  }
344 
353  KOKKOS_INLINE_FUNCTION KeyType maxKey () const {
354  return maxKey_;
355  }
356 
364  KOKKOS_INLINE_FUNCTION ValueType minVal () const {
365  return minVal_;
366  }
367 
375  KOKKOS_INLINE_FUNCTION ValueType maxVal () const {
376  return maxVal_;
377  }
378 
391  bool hasDuplicateKeys ();
392 
398 
399  std::string description () const;
401 
403  void
404  describe (Teuchos::FancyOStream &out,
405  const Teuchos::EVerbosityLevel verbLevel=
406  Teuchos::Describable::verbLevel_default) const;
408 
409 private:
411  ptr_type ptr_;
413  val_type val_;
414 
420  KeyType minKey_ = ::Kokkos::Details::ArithTraits<KeyType>::max();
421 
427  KeyType maxKey_ = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
428  ::Kokkos::Details::ArithTraits<KeyType>::min() :
429  -::Kokkos::Details::ArithTraits<KeyType>::max();
430 
435  ValueType minVal_ = ::Kokkos::Details::ArithTraits<ValueType>::max();
436 
441  ValueType maxVal_ = ::Kokkos::Details::ArithTraits<ValueType>::is_integer ?
442  ::Kokkos::Details::ArithTraits<ValueType>::min() :
443  -::Kokkos::Details::ArithTraits<ValueType>::max();
444 
451  KeyType firstContigKey_ = ::Kokkos::Details::ArithTraits<KeyType>::max();
452 
459  KeyType lastContigKey_ = ::Kokkos::Details::ArithTraits<KeyType>::is_integer ?
460  ::Kokkos::Details::ArithTraits<KeyType>::min() :
461  -::Kokkos::Details::ArithTraits<KeyType>::max();
462 
469  bool contiguousValues_ = true;
470 
477  bool checkedForDuplicateKeys_ = true;
478 
482  bool hasDuplicateKeys_ = false;
483 
488  bool checkForDuplicateKeys () const;
489 
491  KOKKOS_INLINE_FUNCTION offset_type getSize () const {
492  return ptr_.extent (0) == 0 ?
493  static_cast<offset_type> (0) :
494  static_cast<offset_type> (ptr_.extent (0) - 1);
495  }
496 
497  typedef Kokkos::View<const KeyType*,
498  typename ptr_type::HostMirror::array_layout,
499  typename ptr_type::HostMirror::execution_space,
500  Kokkos::MemoryUnmanaged> host_input_keys_type;
501 
502  typedef Kokkos::View<const ValueType*,
503  typename ptr_type::HostMirror::array_layout,
504  typename ptr_type::HostMirror::execution_space,
505  Kokkos::MemoryUnmanaged> host_input_vals_type;
506 
513  void
514  init (const keys_type& keys,
515  const ValueType startingValue,
516  KeyType initMinKey,
517  KeyType initMaxKey,
518  KeyType firstContigKey,
519  KeyType lastContigKey,
520  const bool computeInitContigKeys);
521 
528  void
529  init (const host_input_keys_type& keys,
530  const host_input_vals_type& vals,
531  KeyType initMinKey,
532  KeyType initMaxKey);
533 };
534 
535 } // Details namespace
536 } // Tpetra namespace
537 
538 #endif // TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP
void copyOffsets(const OutputViewType &dst, const InputViewType &src)
Copy row offsets (in a sparse graph or matrix) from src to dst. The offsets may have different types...
Import KokkosSparse::OrdinalTraits, a traits class for &quot;invalid&quot; (flag) values of integer types...
KOKKOS_DEFAULTED_FUNCTION FixedHashTable()=default
Default constructor; makes an empty table.
KOKKOS_INLINE_FUNCTION ValueType minVal() const
The minimum value in the table.
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.
Declare and define Tpetra::Details::copyOffsets, an implementation detail of Tpetra (in particular...
KOKKOS_INLINE_FUNCTION KeyType minKey() const
The minimum key in the table.
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.
std::string description() const
Implementation of Teuchos::Describable interface.
KOKKOS_INLINE_FUNCTION offset_type numPairs() const
Number of (key, value) pairs in the table.
FixedHashTable(const FixedHashTable< KeyType, ValueType, InDeviceType > &src, typename std::enable_if<!std::is_same< DeviceType, InDeviceType >::value, int >::type *=NULL)
&quot;Copy&quot; constructor that takes a FixedHashTable with the same KeyType and ValueType, but a different DeviceType.
KOKKOS_INLINE_FUNCTION KeyType maxKey() const
The maximum key in the table.
OffsetType offset_type
Type of offsets into the hash table&#39;s array of (key,value) pairs.
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.
KOKKOS_INLINE_FUNCTION ValueType maxVal() const
The maximum value in the table.
Kokkos::View< const KeyType *, Kokkos::LayoutLeft, device_type > keys_type
Type of a 1-D Kokkos::View (array) used to store keys.