Tpetra parallel linear algebra  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Tpetra_HashTable_def.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_HASHTABLE_DEF_HPP_
45 #define TPETRA_HASHTABLE_DEF_HPP_
46 
47 #include "Tpetra_HashTable_decl.hpp"
48 #include "MurmurHash3.hpp"
49 
50 
51 namespace Tpetra
52 {
53 
54 namespace Details
55 {
56 
57 template<typename KeyType, typename ValueType>
58 int
59 HashTable<KeyType, ValueType>::hashFunc( const KeyType key ) {
60 #ifdef TPETRA_USE_MURMUR_HASH
61  uint32_t k;
62  MurmurHash3_x86_32((void *)&key, sizeof(KeyType),
63  1, (void *)&k);
64  return (int) (k%Size_);
65 #else
66  // Epetra's version of hash, using it as default as we have observed
67  // this is much faster than murmur hash. However, this is not a good
68  // hash function for all data sets. For our typical use case, this is good.
69  // Use murmur if the maps are sparse.
70  int intkey = (int) ((key & 0x000000007fffffffLL) +
71  ((key & 0x7fffffff80000000LL) >> 31));
72  return (int) ((Seed_ ^ intkey)%Size_);
73 #endif
74 }
75 
76 template<typename KeyType, typename ValueType>
77 int
78 HashTable<KeyType, ValueType>::getRecommendedSize( const int size ) {
79  // A large list of prime numbers.
80  // Based on a recommendation by Andres Valloud in hash forums.
81  // There are only enough primes here so that between any number N and 2*N,
82  // there will be at least about 8 to choose from (except the first 10).
83  // This is a balance between a small list of primes, and getting a
84  // collection size that doesn't waste too much space. In addition,
85  // the primes in this table were chosen so that they do not divide
86  // 256^k +- a, for 1<=k<=8, and -32<=a<=32. This is so that
87  // using them as a modulo will not have a tendency to just throw away
88  // the most significant bits of the object's hash. The primes (except the
89  // first ten) or not close to any power of two to avoid aliasing
90  // between hash functions based on bit manipulation and the moduli.
91  int primes [ ] = {
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 };
124 
125  int hsize = primes[220] ;
126  for (int i = 0 ; i < 221 ; i++)
127  {
128  if (size <= primes[i])
129  {
130  hsize = primes[i] ;
131  break ;
132  }
133  }
134 
135  return hsize ;
136 }
137 
138 template<typename KeyType, typename ValueType>
140 HashTable( const int size, const unsigned int seed )
141  : Container_(NULL),
142  Seed_(seed)
143 {
144  TEUCHOS_TEST_FOR_EXCEPTION(size < 0, std::runtime_error,
145  "HashTable : ERROR, size cannot be less than zero");
146 
147  Size_ = getRecommendedSize(size);
148  Container_ = new Node * [Size_];
149  for( KeyType i = 0; i < Size_; ++i ) Container_[i] = NULL;
150 #ifdef HAVE_TEUCHOS_DEBUG
151  maxc_ = 0;
152  nc_ = 0;
153 #endif
154 }
155 
156 template<typename KeyType, typename ValueType>
158 HashTable( const HashTable & obj )
159  : Container_(NULL),
160  Size_(obj.Size_),
161  Seed_(obj.Seed_)
162 {
163 #ifdef HAVE_TEUCHOS_DEBUG
164  maxc_ = 0;
165  nc_ = 0;
166 #endif
167  Container_ = new Node * [Size_];
168  for( KeyType i = 0; i < Size_; ++i ) Container_[i] = NULL;
169  for( KeyType i = 0; i < Size_; ++i ) {
170  Node * ptr = obj.Container_[i];
171  while( ptr ) { add( ptr->Key, ptr->Value ); ptr = ptr->Ptr; }
172  }
173 }
174 
175 template<typename KeyType, typename ValueType>
176 HashTable<KeyType, ValueType>::~HashTable() {
177  Node * ptr1;
178  Node * ptr2;
179  for( KeyType i = 0; i < Size_; ++i ) {
180  ptr1 = Container_[i];
181  while( ptr1 ) { ptr2 = ptr1; ptr1 = ptr1->Ptr; delete ptr2; }
182  }
183 
184  delete [] Container_;
185 }
186 
187 template<typename KeyType, typename ValueType>
188 void
190 add( const KeyType key, const ValueType value ) {
191  int v = hashFunc(key);
192  Node * n1 = Container_[v];
193  Container_[v] = new Node(key,value,n1);
194 }
195 
196 template<typename KeyType, typename ValueType>
197 ValueType
199 get( const KeyType key ) {
200  Node * n = Container_[ hashFunc(key) ];
201 
202 #ifdef HAVE_TEUCHOS_DEBUG
203  int k = 0;
204 #endif
205 
206  while( n && (n->Key != key) ){
207  n = n->Ptr;
208 #ifdef HAVE_TEUCHOS_DEBUG
209  ((k+1 > maxc_) ? maxc_ = k+1 : 0) ;
210  k++;
211 #endif
212  }
213 
214 #ifdef HAVE_TEUCHOS_DEBUG
215  if (k != 0) nc_++;
216 #endif
217  if( n ) return n->Value;
218  else return -1;
219 }
220 
221 template <typename KeyType, typename ValueType>
223  std::ostringstream oss;
224  oss << "HashTable<"
225  << Teuchos::TypeNameTraits<KeyType>::name() << ","
226  << Teuchos::TypeNameTraits<ValueType>::name() << "> "
227  << "{ Size_: " << Size_ << " }";
228  return oss.str();
229 }
230 
231 template <typename KeyType, typename ValueType>
233  Teuchos::FancyOStream &out,
234  const Teuchos::EVerbosityLevel verbLevel) const {
235  using std::endl;
236  using std::setw;
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;
244 
245  Teuchos::EVerbosityLevel vl = verbLevel;
246  if (vl == VERB_DEFAULT) vl = VERB_LOW;
247 
248  if (vl == VERB_NONE) {
249  // do nothing
250  }
251  else if (vl == VERB_LOW) {
252  out << this->description() << endl;
253  }
254  else { // MEDIUM, HIGH or EXTREME
255  out << "HashTable: {" << endl;
256  {
257  OSTab tab1 (rcpFromRef (out));
258 
259  const std::string label = this->getObjectLabel ();
260  if (label != "") {
261  out << "label: " << label << endl;
262  }
263  out << "Template parameters: {" << endl;
264  {
265  OSTab tab2 (rcpFromRef (out));
266  out << "KeyType: " << TypeNameTraits<KeyType>::name () << endl
267  << "ValueType" << TypeNameTraits<ValueType>::name () << endl;
268  }
269  out << "}" << endl << "Table parameters: {" << endl;
270  {
271  OSTab tab2 (rcpFromRef (out));
272  out << "Size_: " << Size_ << endl;
273  }
274  out << "}" << endl;
275 #ifdef HAVE_TEUCHOS_DEBUG
276  out << "Debug info: {" << endl;
277  {
278  OSTab tab2 (rcpFromRef (out));
279  out << "Maximum number of collisions for any key: " << maxc_ << endl
280  << "Total number of collisions: " << nc_ << endl;
281  }
282  out << "}" << endl;
283 #endif // HAVE_TEUCHOS_DEBUG
284 
285  if (vl >= VERB_EXTREME) {
286  out << "Contents: ";
287  if (Container_ == NULL || Size_ == 0) {
288  out << "[]" << endl;
289  } else {
290  out << "[" << endl;
291  {
292  OSTab tab2 (rcpFromRef (out));
293  for (KeyType i = 0; i < Size_; ++i) {
294  Node* curNode = Container_[i];
295  if (curNode == NULL) {
296  out << "NULL";
297  } else { // curNode != NULL
298  // Print all the buckets at the current table position i.
299  out << "[";
300  // Print the first bucket.
301  out << "[" << curNode->Key << "," << curNode->Value << "]";
302  curNode = curNode->Ptr;
303  // Print the remaining buckets, if there are any.
304  while (curNode != NULL) {
305  out << ", [" << curNode->Key << "," << curNode->Value << "]";
306  curNode = curNode->Ptr;
307  }
308  out << "]" << endl;
309  } // if curNode == or != NULL
310  if (i + 1 < Size_) {
311  out << ", ";
312  }
313  } // for each table position i
314  }
315  out << "]" << endl;
316  } // The table contains entries
317  } // vl >= VERB_EXTREME
318  }
319  out << "}" << endl;
320  } // if vl > VERB_LOW
321 }
322 
323 } // namespace Details
324 } // namespace Tpetra
325 
326 // Macro that explicitly instantiates HashTable for the given local
327 // ordinal (LO) and global ordinal (GO) types. Note that HashTable's
328 // template parameters occur in the opposite order of most Tpetra
329 // classes. This is because HashTable performs global-to-local
330 // lookup, and the convention in templated C++ lookup tables (such as
331 // std::map) is <KeyType, ValueType>.
332 //
333 // This macro must be explanded within the Tpetra::Details namespace.
334 #define TPETRA_HASHTABLE_INSTANT_DEFAULTNODE(LO,GO) \
335  template class HashTable< GO , LO >; \
336 
337 #endif
HashTable(const int size, const unsigned int seed=(2654435761U))
ValueType get(const KeyType key)
Get the value corresponding to the given key.
void add(const KeyType key, const ValueType value)
Add a key and its value to the hash table.
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.