Tpetra_Details_FixedHashTable_decl.hpp

/*
// @HEADER
// ***********************************************************************
//
//          Tpetra: Templated Linear Algebra Services Package
//                 Copyright (2008) Sandia Corporation
//
// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
// the U.S. Government retains certain rights in this software.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the Corporation nor the names of the
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Questions? Contact Michael A. Heroux (maherou@sandia.gov)
//
// ************************************************************************
// @HEADER
*/

#ifndef TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP
#define TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP

#include "Tpetra_Details_Hash.hpp"
#include "Tpetra_Details_OrdinalTraits.hpp"
#include "Tpetra_Details_copyOffsets.hpp"
#include "Teuchos_Describable.hpp"
#include "Teuchos_FancyOStream.hpp"
#include "Teuchos_VerbosityLevel.hpp"
#include "Kokkos_Core.hpp"

namespace Tpetra {
namespace Details {

template<class KeyType,
         class ValueType,
         class DeviceType>
class FixedHashTable {
private:
  typedef typename DeviceType::execution_space execution_space;
  typedef typename DeviceType::memory_space memory_space;
  typedef Kokkos::Device<execution_space, memory_space> device_type;

  typedef Hash<KeyType, device_type> hash_type;
  typedef typename hash_type::offset_type offset_type;

  typedef typename Kokkos::View<const offset_type*, Kokkos::LayoutLeft,
                                device_type> ptr_type;
  typedef typename Kokkos::View<const Kokkos::pair<KeyType, ValueType>*,
                                Kokkos::LayoutLeft, device_type> val_type;

  KOKKOS_INLINE_FUNCTION bool hasContiguousValues () const {
    return contiguousValues_;
  }

public:
  typedef Kokkos::View<const KeyType*, Kokkos::LayoutLeft, device_type> keys_type;

  FixedHashTable ();

  FixedHashTable (const keys_type& keys);

  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
                  const bool keepKeys = false);

  FixedHashTable (const keys_type& keys,
                  const ValueType startingValue);

  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
                  const ValueType startingValue,
                  const bool keepKeys = false);

  FixedHashTable (const keys_type& keys,
                  const KeyType firstContigKey,
                  const KeyType lastContigKey,
                  const ValueType startingValue,
                  const bool keepKeys = false);

  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
                  const KeyType firstContigKey,
                  const KeyType lastContigKey,
                  const ValueType startingValue,
                  const bool keepKeys = false);

  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
                  const Teuchos::ArrayView<const ValueType>& vals);

  template<class K, class V, class D>
  friend class FixedHashTable;

  template<class InDeviceType>
  FixedHashTable (const FixedHashTable<KeyType, ValueType, InDeviceType>& src,
                  typename std::enable_if<! std::is_same<DeviceType, InDeviceType>::value, int>::type* = NULL)
  {
    using Kokkos::ViewAllocateWithoutInitializing;
    typedef typename ptr_type::non_const_type nonconst_ptr_type;
    typedef typename val_type::non_const_type nonconst_val_type;

    // FIXME (mfh 28 May 2015) The code below _always_ copies.  This
    // shouldn't be necessary if the input and output memory spaces
    // are the same.  However, it is always correct.

    // Different Devices may have different offset_type, because
    // offset_type comes from the memory space's size_type typedef.
    // That's why we use a specialized deep copy function here instead
    // of Kokkos::deep_copy.
    nonconst_ptr_type ptr (ViewAllocateWithoutInitializing ("ptr"),
                           src.ptr_.extent (0));
    ::Tpetra::Details::copyOffsets (ptr, src.ptr_);
    nonconst_val_type val (ViewAllocateWithoutInitializing ("val"),
                           src.val_.extent (0));
    // val and src.val_ have the same entry types, unlike (possibly)
    // ptr and src.ptr_.  Thus, we can use Kokkos::deep_copy here.
    Kokkos::deep_copy (val, src.val_);

    this->ptr_ = ptr;
    this->val_ = val;
    this->minKey_ = src.minKey_;
    this->maxKey_ = src.maxKey_;
    this->minVal_ = src.minVal_;
    this->maxVal_ = src.maxVal_;
    this->firstContigKey_ = src.firstContigKey_;
    this->lastContigKey_ = src.lastContigKey_;
    this->contiguousValues_ = src.contiguousValues_;
    this->checkedForDuplicateKeys_ = src.checkedForDuplicateKeys_;
    this->hasDuplicateKeys_ = src.hasDuplicateKeys_;

#if defined(HAVE_TPETRA_DEBUG)
    this->check ();
#endif // defined(HAVE_TPETRA_DEBUG)
  }

  KOKKOS_INLINE_FUNCTION ValueType get (const KeyType& key) const {
    const offset_type size = this->getSize ();
    if (size == 0) {
      // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
      // because neither have the right device function markings.
      return Tpetra::Details::OrdinalTraits<ValueType>::invalid ();
    }

    // If this object assumes contiguous values, then it doesn't store
    // the initial sequence of >= 1 contiguous keys in the table.
    if (this->hasContiguousValues () &&
        key >= firstContigKey_ && key <= lastContigKey_) {
      return static_cast<ValueType> (key - firstContigKey_) + this->minVal ();
    }

    const typename hash_type::result_type hashVal =
      hash_type::hashFunc (key, size);

    const offset_type start = ptr_[hashVal];
    const offset_type end = ptr_[hashVal+1];
    for (offset_type k = start; k < end; ++k) {
      if (val_[k].first == key) {
        return val_[k].second;
      }
    }

    // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
    // because neither have the right device function markings.
    return Tpetra::Details::OrdinalTraits<ValueType>::invalid ();
  }

  bool hasKeys () const;

  KOKKOS_INLINE_FUNCTION KeyType getKey (const ValueType& val) const {
    // If there are no keys in the table, then we set minVal_ to the
    // the max possible ValueType value and maxVal_ to the min
    // possible ValueType value.  Thus, this is always true.
    if (val < this->minVal () || val > this->maxVal ()) {
      return Tpetra::Details::OrdinalTraits<KeyType>::invalid ();
    }
    else {
      const ValueType index = val - this->minVal ();
      return keys_[index];
    }
  }

  KOKKOS_INLINE_FUNCTION offset_type numPairs () const {
    // NOTE (mfh 26 May 2015) Using val_.extent(0) only works
    // because the table stores pairs with duplicate keys separately.
    // If the table didn't do that, we would have to keep a separate
    // numPairs_ field (remembering the size of the input array of
    // keys).
    if (this->hasContiguousValues ()) {
      return val_.extent (0) + static_cast<offset_type> (lastContigKey_ - firstContigKey_);
    }
    else {
      return val_.extent (0);
    }
  }

  KOKKOS_INLINE_FUNCTION KeyType minKey () const {
    return minKey_;
  }

  KOKKOS_INLINE_FUNCTION KeyType maxKey () const {
    return maxKey_;
  }

  KOKKOS_INLINE_FUNCTION ValueType minVal () const {
    return minVal_;
  }

  KOKKOS_INLINE_FUNCTION ValueType maxVal () const {
    return maxVal_;
  }

  bool hasDuplicateKeys ();


  std::string description () const;

  void
  describe (Teuchos::FancyOStream &out,
            const Teuchos::EVerbosityLevel verbLevel=
            Teuchos::Describable::verbLevel_default) const;

private:
  keys_type keys_;
  ptr_type ptr_;
  val_type val_;

  KeyType minKey_;

  KeyType maxKey_;

  ValueType minVal_;

  ValueType maxVal_;

  KeyType firstContigKey_;

  KeyType lastContigKey_;

  bool contiguousValues_;

  bool checkedForDuplicateKeys_;

  bool hasDuplicateKeys_;

  bool checkForDuplicateKeys () const;

  KOKKOS_INLINE_FUNCTION offset_type getSize () const {
    return ptr_.extent (0) == 0 ?
      static_cast<offset_type> (0) :
      static_cast<offset_type> (ptr_.extent (0) - 1);
  }

  void check () const;

  typedef Kokkos::View<const KeyType*,
                       typename ptr_type::HostMirror::array_layout,
                       typename ptr_type::HostMirror::execution_space,
                       Kokkos::MemoryUnmanaged> host_input_keys_type;

  typedef Kokkos::View<const ValueType*,
                       typename ptr_type::HostMirror::array_layout,
                       typename ptr_type::HostMirror::execution_space,
                       Kokkos::MemoryUnmanaged> host_input_vals_type;

  void
  init (const keys_type& keys,
        const ValueType startingValue,
        KeyType initMinKey,
        KeyType initMaxKey,
        KeyType firstContigKey,
        KeyType lastContigKey,
        const bool computeInitContigKeys);

  void
  init (const host_input_keys_type& keys,
        const host_input_vals_type& vals,
        KeyType initMinKey,
        KeyType initMaxKey);
};

} // Details namespace
} // Tpetra namespace

#endif // TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP