Tpetra parallel linear algebra  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator 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 
55 namespace Tpetra {
56 namespace Details {
57 
83 template<class KeyType,
84  class ValueType,
85  class DeviceType>
87 private:
88  typedef typename DeviceType::execution_space execution_space;
89  typedef typename DeviceType::memory_space memory_space;
90  typedef Kokkos::Device<execution_space, memory_space> device_type;
91 
93  typedef typename hash_type::offset_type offset_type;
94 
102  typedef typename Kokkos::View<const offset_type*, Kokkos::LayoutLeft,
103  device_type> ptr_type;
110  typedef typename Kokkos::View<const Kokkos::pair<KeyType, ValueType>*,
111  Kokkos::LayoutLeft, device_type> val_type;
112 
119  KOKKOS_INLINE_FUNCTION bool hasContiguousValues () const {
120  return contiguousValues_;
121  }
122 
123 public:
127  typedef Kokkos::View<const KeyType*, Kokkos::LayoutLeft, device_type> keys_type;
128 
130  FixedHashTable ();
131 
141  FixedHashTable (const keys_type& keys);
142 
153  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
154  const bool keepKeys = false);
155 
169  FixedHashTable (const keys_type& keys,
170  const ValueType startingValue);
171 
186  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
187  const ValueType startingValue,
188  const bool keepKeys = false);
189 
211  FixedHashTable (const keys_type& keys,
212  const KeyType firstContigKey,
213  const KeyType lastContigKey,
214  const ValueType startingValue,
215  const bool keepKeys = false);
216 
235  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
236  const KeyType firstContigKey,
237  const KeyType lastContigKey,
238  const ValueType startingValue,
239  const bool keepKeys = false);
240 
252  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
253  const Teuchos::ArrayView<const ValueType>& vals);
254 
255  template<class K, class V, class D>
256  friend class FixedHashTable;
257 
263  template<class InDeviceType>
265  typename std::enable_if<! std::is_same<DeviceType, InDeviceType>::value, int>::type* = NULL)
266  {
267  using Kokkos::ViewAllocateWithoutInitializing;
268  typedef typename ptr_type::non_const_type nonconst_ptr_type;
269  typedef typename val_type::non_const_type nonconst_val_type;
270 
271  // FIXME (mfh 28 May 2015) The code below _always_ copies. This
272  // shouldn't be necessary if the input and output memory spaces
273  // are the same. However, it is always correct.
274 
275  // Different Devices may have different offset_type, because
276  // offset_type comes from the memory space's size_type typedef.
277  // That's why we use a specialized deep copy function here instead
278  // of Kokkos::deep_copy.
279  nonconst_ptr_type ptr (ViewAllocateWithoutInitializing ("ptr"),
280  src.ptr_.extent (0));
281  ::Tpetra::Details::copyOffsets (ptr, src.ptr_);
282  nonconst_val_type val (ViewAllocateWithoutInitializing ("val"),
283  src.val_.extent (0));
284  // val and src.val_ have the same entry types, unlike (possibly)
285  // ptr and src.ptr_. Thus, we can use Kokkos::deep_copy here.
286  Kokkos::deep_copy (val, src.val_);
287 
288  this->ptr_ = ptr;
289  this->val_ = val;
290  this->minKey_ = src.minKey_;
291  this->maxKey_ = src.maxKey_;
292  this->minVal_ = src.minVal_;
293  this->maxVal_ = src.maxVal_;
294  this->firstContigKey_ = src.firstContigKey_;
295  this->lastContigKey_ = src.lastContigKey_;
296  this->contiguousValues_ = src.contiguousValues_;
297  this->checkedForDuplicateKeys_ = src.checkedForDuplicateKeys_;
298  this->hasDuplicateKeys_ = src.hasDuplicateKeys_;
299 
300 #if defined(HAVE_TPETRA_DEBUG)
301  this->check ();
302 #endif // defined(HAVE_TPETRA_DEBUG)
303  }
304 
306  KOKKOS_INLINE_FUNCTION ValueType get (const KeyType& key) const {
307  const offset_type size = this->getSize ();
308  if (size == 0) {
309  // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
310  // because neither have the right device function markings.
311  return Tpetra::Details::OrdinalTraits<ValueType>::invalid ();
312  }
313 
314  // If this object assumes contiguous values, then it doesn't store
315  // the initial sequence of >= 1 contiguous keys in the table.
316  if (this->hasContiguousValues () &&
317  key >= firstContigKey_ && key <= lastContigKey_) {
318  return static_cast<ValueType> (key - firstContigKey_) + this->minVal ();
319  }
320 
321  const typename hash_type::result_type hashVal =
322  hash_type::hashFunc (key, size);
323 
324  const offset_type start = ptr_[hashVal];
325  const offset_type end = ptr_[hashVal+1];
326  for (offset_type k = start; k < end; ++k) {
327  if (val_[k].first == key) {
328  return val_[k].second;
329  }
330  }
331 
332  // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
333  // because neither have the right device function markings.
334  return Tpetra::Details::OrdinalTraits<ValueType>::invalid ();
335  }
336 
342  bool hasKeys () const;
343 
350  KOKKOS_INLINE_FUNCTION KeyType getKey (const ValueType& val) const {
351  // If there are no keys in the table, then we set minVal_ to the
352  // the max possible ValueType value and maxVal_ to the min
353  // possible ValueType value. Thus, this is always true.
354  if (val < this->minVal () || val > this->maxVal ()) {
355  return Tpetra::Details::OrdinalTraits<KeyType>::invalid ();
356  }
357  else {
358  const ValueType index = val - this->minVal ();
359  return keys_[index];
360  }
361  }
362 
366  KOKKOS_INLINE_FUNCTION offset_type numPairs () const {
367  // NOTE (mfh 26 May 2015) Using val_.extent(0) only works
368  // because the table stores pairs with duplicate keys separately.
369  // If the table didn't do that, we would have to keep a separate
370  // numPairs_ field (remembering the size of the input array of
371  // keys).
372  if (this->hasContiguousValues ()) {
373  return val_.extent (0) + static_cast<offset_type> (lastContigKey_ - firstContigKey_);
374  }
375  else {
376  return val_.extent (0);
377  }
378  }
379 
388  KOKKOS_INLINE_FUNCTION KeyType minKey () const {
389  return minKey_;
390  }
391 
400  KOKKOS_INLINE_FUNCTION KeyType maxKey () const {
401  return maxKey_;
402  }
403 
411  KOKKOS_INLINE_FUNCTION ValueType minVal () const {
412  return minVal_;
413  }
414 
422  KOKKOS_INLINE_FUNCTION ValueType maxVal () const {
423  return maxVal_;
424  }
425 
438  bool hasDuplicateKeys ();
439 
445 
446  std::string description () const;
448 
450  void
451  describe (Teuchos::FancyOStream &out,
452  const Teuchos::EVerbosityLevel verbLevel=
453  Teuchos::Describable::verbLevel_default) const;
455 
456 private:
458  std::string objectLabel_;
459 
469  keys_type keys_;
471  ptr_type ptr_;
473  val_type val_;
474 
479  KeyType minKey_;
480 
485  KeyType maxKey_;
486 
491  ValueType minVal_;
492 
497  ValueType maxVal_;
498 
505  KeyType firstContigKey_;
506 
513  KeyType lastContigKey_;
514 
521  bool contiguousValues_;
522 
528  bool checkedForDuplicateKeys_;
529 
533  bool hasDuplicateKeys_;
534 
539  bool checkForDuplicateKeys () const;
540 
542  KOKKOS_INLINE_FUNCTION offset_type getSize () const {
543  return ptr_.extent (0) == 0 ?
544  static_cast<offset_type> (0) :
545  static_cast<offset_type> (ptr_.extent (0) - 1);
546  }
547 
549  void check () const;
550 
551  typedef Kokkos::View<const KeyType*,
552  typename ptr_type::HostMirror::array_layout,
553  typename ptr_type::HostMirror::execution_space,
554  Kokkos::MemoryUnmanaged> host_input_keys_type;
555 
556  typedef Kokkos::View<const ValueType*,
557  typename ptr_type::HostMirror::array_layout,
558  typename ptr_type::HostMirror::execution_space,
559  Kokkos::MemoryUnmanaged> host_input_vals_type;
560 
567  void
568  init (const keys_type& keys,
569  const ValueType startingValue,
570  KeyType initMinKey,
571  KeyType initMaxKey,
572  KeyType firstContigKey,
573  KeyType lastContigKey,
574  const bool computeInitContigKeys);
575 
582  void
583  init (const host_input_keys_type& keys,
584  const host_input_vals_type& vals,
585  KeyType initMinKey,
586  KeyType initMaxKey);
587 };
588 
589 } // Details namespace
590 } // Tpetra namespace
591 
592 #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_INLINE_FUNCTION KeyType getKey(const ValueType &val) const
Get the key corresponding to the given value.
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...
bool hasKeys() const
Whether it is safe to call getKey().
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.
FixedHashTable()
Default constructor; makes an empty table.
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.