44#ifndef TPETRA_HASHTABLE_DEF_HPP_
45#define TPETRA_HASHTABLE_DEF_HPP_
47#include "Tpetra_HashTable_decl.hpp"
48#include "MurmurHash3.hpp"
57template<
typename KeyType,
typename ValueType>
59HashTable<KeyType, ValueType>::hashFunc(
const KeyType key ) {
60#ifdef TPETRA_USE_MURMUR_HASH
62 MurmurHash3_x86_32((
void *)&key,
sizeof(KeyType),
64 return (
int) (k%Size_);
70 int intkey = (int) ((key & 0x000000007fffffffLL) +
71 ((key & 0x7fffffff80000000LL) >> 31));
72 return (
int) ((Seed_ ^ intkey)%Size_);
76template<
typename KeyType,
typename ValueType>
78HashTable<KeyType, ValueType>::getRecommendedSize(
const int size ) {
92 3, 7, 13, 23, 53, 97, 193, 389, 769, 1543,
93 2237, 2423, 2617, 2797, 2999, 3167, 3359, 3539,
94 3727, 3911, 4441 , 4787 , 5119 , 5471 , 5801 , 6143 , 6521 , 6827
95 , 7177 , 7517 , 7853 , 8887 , 9587 , 10243 , 10937 , 11617 , 12289
96 , 12967 , 13649 , 14341 , 15013 , 15727
97 , 17749 , 19121 , 20479 , 21859 , 23209 , 24593 , 25939 , 27329
98 , 28669 , 30047 , 31469 , 35507 , 38231 , 40961 , 43711 , 46439
99 , 49157 , 51893 , 54617 , 57347 , 60077 , 62801 , 70583 , 75619
100 , 80669 , 85703 , 90749 , 95783 , 100823 , 105871 , 110909 , 115963
101 , 120997 , 126031 , 141157 , 151237 , 161323 , 171401 , 181499 , 191579
102 , 201653 , 211741 , 221813 , 231893 , 241979 , 252079
103 , 282311 , 302483 , 322649 , 342803 , 362969 , 383143 , 403301 , 423457
104 , 443629 , 463787 , 483953 , 504121 , 564617 , 604949 , 645313 , 685609
105 , 725939 , 766273 , 806609 , 846931 , 887261 , 927587 , 967919 , 1008239
106 , 1123477 , 1198397 , 1273289 , 1348177 , 1423067 , 1497983 , 1572869
107 , 1647761 , 1722667 , 1797581 , 1872461 , 1947359 , 2022253
108 , 2246953 , 2396759 , 2546543 , 2696363 , 2846161 , 2995973 , 3145739
109 , 3295541 , 3445357 , 3595117 , 3744941 , 3894707 , 4044503
110 , 4493921 , 4793501 , 5093089 , 5392679 , 5692279 , 5991883 , 6291469
111 , 6591059 , 6890641 , 7190243 , 7489829 , 7789447 , 8089033
112 , 8987807 , 9586981 , 10186177 , 10785371 , 11384539 , 11983729
113 , 12582917 , 13182109 , 13781291 , 14380469 , 14979667 , 15578861
114 , 16178053 , 17895707 , 19014187 , 20132683 , 21251141 , 22369661
115 , 23488103 , 24606583 , 25725083 , 26843549 , 27962027 , 29080529
116 , 30198989 , 31317469 , 32435981 , 35791397 , 38028379 , 40265327
117 , 42502283 , 44739259 , 46976221 , 49213237 , 51450131 , 53687099
118 , 55924061 , 58161041 , 60397993 , 62634959 , 64871921
119 , 71582857 , 76056727 , 80530643 , 85004567 , 89478503 , 93952427
120 , 98426347 , 102900263 , 107374217 , 111848111 , 116322053 , 120795971
121 , 125269877 , 129743807 , 143165587 , 152113427 , 161061283 , 170009141
122 , 178956983 , 187904819 , 196852693 , 205800547 , 214748383 , 223696237
123 , 232644089 , 241591943 , 250539763 , 259487603 , 268435399 };
125 int hsize = primes[220] ;
126 for (
int i = 0 ; i < 221 ; i++)
128 if (size <= primes[i])
138template<
typename KeyType,
typename ValueType>
145 "HashTable : ERROR, size cannot be less than zero");
147 Size_ = getRecommendedSize(
size);
148 Container_ =
new Node * [Size_];
150#ifdef HAVE_TPETRA_DEBUG
156template<
typename KeyType,
typename ValueType>
163#ifdef HAVE_TPETRA_DEBUG
167 Container_ =
new Node * [Size_];
170 Node *
ptr =
obj.Container_[
i];
175template<
typename KeyType,
typename ValueType>
176HashTable<KeyType, ValueType>::~HashTable() {
179 for( KeyType i = 0; i < Size_; ++i ) {
180 ptr1 = Container_[i];
181 while( ptr1 ) { ptr2 = ptr1; ptr1 = ptr1->Ptr;
delete ptr2; }
184 delete [] Container_;
187template<
typename KeyType,
typename ValueType>
191 int v = hashFunc(
key);
192 Node *
n1 = Container_[
v];
193 Container_[
v] =
new Node(
key,value,
n1);
196template<
typename KeyType,
typename ValueType>
200 Node *
n = Container_[ hashFunc(
key) ];
202#ifdef HAVE_TPETRA_DEBUG
206 while(
n && (
n->Key !=
key) ){
208#ifdef HAVE_TPETRA_DEBUG
214#ifdef HAVE_TPETRA_DEBUG
217 if(
n )
return n->Value;
221template <
typename KeyType,
typename ValueType>
223 std::ostringstream
oss;
225 << Teuchos::TypeNameTraits<KeyType>::name() <<
","
226 << Teuchos::TypeNameTraits<ValueType>::name() <<
"> "
227 <<
"{ Size_: " << Size_ <<
" }";
231template <
typename KeyType,
typename ValueType>
233 Teuchos::FancyOStream &
out,
234 const Teuchos::EVerbosityLevel
verbLevel)
const {
237 using Teuchos::OSTab;
238 using Teuchos::rcpFromRef;
239 using Teuchos::TypeNameTraits;
240 using Teuchos::VERB_DEFAULT;
241 using Teuchos::VERB_NONE;
242 using Teuchos::VERB_LOW;
243 using Teuchos::VERB_EXTREME;
252 out << this->description() <<
endl;
261 out <<
"label: " << label <<
endl;
263 out <<
"Template parameters: {" <<
endl;
269 out <<
"}" <<
endl <<
"Table parameters: {" <<
endl;
272 out <<
"Size_: " << Size_ <<
endl;
275#ifdef HAVE_TPETRA_DEBUG
276 out <<
"Debug info: {" <<
endl;
279 out <<
"Maximum number of collisions for any key: " <<
maxc_ <<
endl
280 <<
"Total number of collisions: " <<
nc_ <<
endl;
287 if (Container_ ==
NULL || Size_ == 0) {
334#define TPETRA_HASHTABLE_INSTANT_DEFAULTNODE(LO,GO) \
335 template class HashTable< GO , LO >; \
Struct that holds views of the contents of a CrsMatrix.
HashTable(const int size, const unsigned int seed=(2654435761U))
ValueType get(const KeyType key)
Get the value corresponding to the given key.
std::string description() const
Implementation of Teuchos::Describable.
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.
void add(const KeyType key, const ValueType value)
Add a key and its value to the hash table.
Implementation details of Tpetra.
Namespace Tpetra contains the class and methods constituting the Tpetra library.