Tpetra parallel linear algebra  Version of the Day
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 "Kokkos_Core.hpp"
52 
53 namespace Tpetra {
54 namespace Details {
55 
81 template<class KeyType,
82  class ValueType,
83  class DeviceType>
84 class FixedHashTable : public Teuchos::Describable {
85 private:
86  typedef typename DeviceType::execution_space execution_space;
87  typedef typename DeviceType::memory_space memory_space;
88  typedef Kokkos::Device<execution_space, memory_space> device_type;
89 
91  typedef typename hash_type::offset_type offset_type;
92 
100  typedef typename Kokkos::View<const offset_type*, Kokkos::LayoutLeft,
101  device_type> ptr_type;
108  typedef typename Kokkos::View<const Kokkos::pair<KeyType, ValueType>*,
109  Kokkos::LayoutLeft, device_type> val_type;
110 
117  KOKKOS_INLINE_FUNCTION bool hasContiguousValues () const {
118  return contiguousValues_;
119  }
120 
121 public:
125  typedef Kokkos::View<const KeyType*, Kokkos::LayoutLeft, device_type> keys_type;
126 
128  FixedHashTable ();
129 
139  FixedHashTable (const keys_type& keys);
140 
151  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
152  const bool keepKeys = false);
153 
167  FixedHashTable (const keys_type& keys,
168  const ValueType startingValue);
169 
184  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
185  const ValueType startingValue,
186  const bool keepKeys = false);
187 
209  FixedHashTable (const keys_type& keys,
210  const KeyType firstContigKey,
211  const KeyType lastContigKey,
212  const ValueType startingValue,
213  const bool keepKeys = false);
214 
233  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
234  const KeyType firstContigKey,
235  const KeyType lastContigKey,
236  const ValueType startingValue,
237  const bool keepKeys = false);
238 
250  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
251  const Teuchos::ArrayView<const ValueType>& vals);
252 
253  template<class K, class V, class D>
254  friend class FixedHashTable;
255 
261  template<class InDeviceType>
263  typename std::enable_if<! std::is_same<DeviceType, InDeviceType>::value, int>::type* = NULL)
264  {
265  using Kokkos::ViewAllocateWithoutInitializing;
266  typedef typename ptr_type::non_const_type nonconst_ptr_type;
267  typedef typename val_type::non_const_type nonconst_val_type;
268 
269  // FIXME (mfh 28 May 2015) The code below _always_ copies. This
270  // shouldn't be necessary if the input and output memory spaces
271  // are the same. However, it is always correct.
272 
273  // Different Devices may have different offset_type, because
274  // offset_type comes from the memory space's size_type typedef.
275  // That's why we use a specialized deep copy function here instead
276  // of Kokkos::deep_copy.
277  nonconst_ptr_type ptr (ViewAllocateWithoutInitializing ("ptr"),
278  src.ptr_.dimension_0 ());
279  ::Tpetra::Details::copyOffsets (ptr, src.ptr_);
280  nonconst_val_type val (ViewAllocateWithoutInitializing ("val"),
281  src.val_.dimension_0 ());
282  // val and src.val_ have the same entry types, unlike (possibly)
283  // ptr and src.ptr_. Thus, we can use Kokkos::deep_copy here.
284  Kokkos::deep_copy (val, src.val_);
285 
286  this->ptr_ = ptr;
287  this->val_ = val;
288  this->minKey_ = src.minKey_;
289  this->maxKey_ = src.maxKey_;
290  this->minVal_ = src.minVal_;
291  this->maxVal_ = src.maxVal_;
292  this->firstContigKey_ = src.firstContigKey_;
293  this->lastContigKey_ = src.lastContigKey_;
294  this->contiguousValues_ = src.contiguousValues_;
295  this->checkedForDuplicateKeys_ = src.checkedForDuplicateKeys_;
296  this->hasDuplicateKeys_ = src.hasDuplicateKeys_;
297 
298 #if defined(HAVE_TPETRA_DEBUG)
299  this->check ();
300 #endif // defined(HAVE_TPETRA_DEBUG)
301  }
302 
304  KOKKOS_INLINE_FUNCTION ValueType get (const KeyType& key) const {
305  const offset_type size = this->getSize ();
306  if (size == 0) {
307  // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
308  // because neither have the right device function markings.
310  }
311 
312  // If this object assumes contiguous values, then it doesn't store
313  // the initial sequence of >= 1 contiguous keys in the table.
314  if (this->hasContiguousValues () &&
315  key >= firstContigKey_ && key <= lastContigKey_) {
316  return static_cast<ValueType> (key - firstContigKey_) + this->minVal ();
317  }
318 
319  const typename hash_type::result_type hashVal =
320  hash_type::hashFunc (key, size);
321 
322  const offset_type start = ptr_[hashVal];
323  const offset_type end = ptr_[hashVal+1];
324  for (offset_type k = start; k < end; ++k) {
325  if (val_[k].first == key) {
326  return val_[k].second;
327  }
328  }
329 
330  // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
331  // because neither have the right device function markings.
333  }
334 
340  bool hasKeys () const;
341 
348  KOKKOS_INLINE_FUNCTION KeyType getKey (const ValueType& val) const {
349  // If there are no keys in the table, then we set minVal_ to the
350  // the max possible ValueType value and maxVal_ to the min
351  // possible ValueType value. Thus, this is always true.
352  if (val < this->minVal () || val > this->maxVal ()) {
354  }
355  else {
356  const ValueType index = val - this->minVal ();
357  return keys_[index];
358  }
359  }
360 
364  KOKKOS_INLINE_FUNCTION offset_type numPairs () const {
365  // NOTE (mfh 26 May 2015) Using val_.dimension_0() only works
366  // because the table stores pairs with duplicate keys separately.
367  // If the table didn't do that, we would have to keep a separate
368  // numPairs_ field (remembering the size of the input array of
369  // keys).
370  if (this->hasContiguousValues ()) {
371  return val_.dimension_0 () + static_cast<offset_type> (lastContigKey_ - firstContigKey_);
372  }
373  else {
374  return val_.dimension_0 ();
375  }
376  }
377 
386  KOKKOS_INLINE_FUNCTION KeyType minKey () const {
387  return minKey_;
388  }
389 
398  KOKKOS_INLINE_FUNCTION KeyType maxKey () const {
399  return maxKey_;
400  }
401 
409  KOKKOS_INLINE_FUNCTION ValueType minVal () const {
410  return minVal_;
411  }
412 
420  KOKKOS_INLINE_FUNCTION ValueType maxVal () const {
421  return maxVal_;
422  }
423 
436  bool hasDuplicateKeys ();
437 
439 
440  std::string description () const;
442 
444  void
445  describe (Teuchos::FancyOStream &out,
446  const Teuchos::EVerbosityLevel verbLevel=
447  Teuchos::Describable::verbLevel_default) const;
449 
450 private:
460  keys_type keys_;
462  ptr_type ptr_;
464  val_type val_;
465 
470  KeyType minKey_;
471 
476  KeyType maxKey_;
477 
482  ValueType minVal_;
483 
488  ValueType maxVal_;
489 
496  KeyType firstContigKey_;
497 
504  KeyType lastContigKey_;
505 
512  bool contiguousValues_;
513 
519  bool checkedForDuplicateKeys_;
520 
524  bool hasDuplicateKeys_;
525 
530  bool checkForDuplicateKeys () const;
531 
533  KOKKOS_INLINE_FUNCTION offset_type getSize () const {
534  return ptr_.dimension_0 () == 0 ?
535  static_cast<offset_type> (0) :
536  static_cast<offset_type> (ptr_.dimension_0 () - 1);
537  }
538 
540  void check () const;
541 
542  typedef Kokkos::View<const KeyType*,
543  typename ptr_type::HostMirror::array_layout,
544  typename ptr_type::HostMirror::execution_space,
545  Kokkos::MemoryUnmanaged> host_input_keys_type;
546 
547  typedef Kokkos::View<const ValueType*,
548  typename ptr_type::HostMirror::array_layout,
549  typename ptr_type::HostMirror::execution_space,
550  Kokkos::MemoryUnmanaged> host_input_vals_type;
551 
558  void
559  init (const keys_type& keys,
560  const ValueType startingValue,
561  KeyType initMinKey,
562  KeyType initMaxKey,
563  KeyType firstContigKey,
564  KeyType lastContigKey,
565  const bool computeInitContigKeys);
566 
573  void
574  init (const host_input_keys_type& keys,
575  const host_input_vals_type& vals,
576  KeyType initMinKey,
577  KeyType initMaxKey);
578 };
579 
580 } // Details namespace
581 } // Tpetra namespace
582 
583 #endif // TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP
KOKKOS_INLINE_FUNCTION KeyType getKey(const ValueType &val) const
Get the key corresponding to the given value.
KOKKOS_INLINE_FUNCTION offset_type numPairs() const
Number of (key, value) pairs in the table.
Namespace Tpetra contains the class and methods constituting the Tpetra library.
KOKKOS_INLINE_FUNCTION ValueType maxVal() const
The maximum value in the table.
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...
Traits class for "invalid" (flag) values of integer types that Tpetra uses as local ordinals or globa...
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...
void deep_copy(MultiVector< DS, DL, DG, DN, dstClassic > &dst, const MultiVector< SS, SL, SG, SN, srcClassic > &src)
Copy the contents of the MultiVector src into dst.
KOKKOS_INLINE_FUNCTION KeyType maxKey() const
The maximum key in the table.
Implementation details of Tpetra.
std::string description() const
Implementation of Teuchos::Describable.
Traits class for "invalid" (flag) values of integer types that Tpetra uses as local ordinals or globa...
The hash function for FixedHashTable.
FixedHashTable(const FixedHashTable< KeyType, ValueType, InDeviceType > &src, typename std::enable_if<! std::is_same< DeviceType, InDeviceType >::value, int >::type *=NULL)
"Copy" constructor that takes a FixedHashTable with the same KeyType and ValueType, but a different DeviceType.
FixedHashTable()
Default constructor; makes an empty table.
bool hasKeys() const
Whether it is safe to call getKey().
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 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.
KOKKOS_INLINE_FUNCTION KeyType minKey() const
The minimum key 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.