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
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
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() :
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
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,...
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.
The hash function for FixedHashTable.
ResultType result_type
Type of the return value of the hash function.
static KOKKOS_INLINE_FUNCTION result_type hashFunc(const argument_type &key, const offset_type &size)
The hash function.
OffsetType offset_type
Type of offsets into the hash table's array of (key,value) pairs.