Tpetra parallel linear algebra Version of the Day
Loading...
Searching...
No Matches
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
56namespace Tpetra {
57namespace Details {
58
84template<class KeyType,
85 class ValueType,
86 class DeviceType>
88private:
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
124public:
128 typedef Kokkos::View<const KeyType*, Kokkos::LayoutLeft, device_type> keys_type;
129
132
143
151 FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys);
152
168
180 FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
182
205
221 FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
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));
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
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
342 return minKey_;
343 }
344
354 return maxKey_;
355 }
356
365 return minVal_;
366 }
367
376 return maxVal_;
377 }
378
391 bool hasDuplicateKeys ();
392
398
399
400 std::string description () const;
401
403 void
404 describe (Teuchos::FancyOStream &out,
405 const Teuchos::EVerbosityLevel verbLevel=
406 Teuchos::Describable::verbLevel_default) const;
408
409private:
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() :
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() :
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() :
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,
520 const bool computeInitContigKeys);
521
528 void
529 init (const host_input_keys_type& keys,
530 const host_input_vals_type& vals,
533};
534
535} // Details namespace
536} // Tpetra namespace
537
538#endif // TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP
Import KokkosSparse::OrdinalTraits, a traits class for "invalid" (flag) values of integer types,...
Declare and define Tpetra::Details::copyOffsets, an implementation detail of Tpetra (in particular,...
Struct that holds views of the contents of a CrsMatrix.
KOKKOS_INLINE_FUNCTION ValueType minVal() const
The minimum value in the table.
std::string description() const
Implementation of Teuchos::Describable interface.
bool hasDuplicateKeys()
Whether the table has any duplicate keys.
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,...
KOKKOS_INLINE_FUNCTION offset_type numPairs() const
Number of (key, value) pairs 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.
KOKKOS_INLINE_FUNCTION KeyType maxKey() const
The maximum key in the table.
KOKKOS_INLINE_FUNCTION ValueType maxVal() const
The maximum value in the table.
KOKKOS_INLINE_FUNCTION KeyType minKey() const
The minimum key in the table.
KOKKOS_DEFAULTED_FUNCTION FixedHashTable()=default
Default constructor; makes an empty table.
KOKKOS_INLINE_FUNCTION ValueType get(const KeyType &key) const
Get the value corresponding to the given key.
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.
Implementation details of Tpetra.
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.
Namespace Tpetra contains the class and methods constituting the Tpetra library.