IFPACK  Development
 All Classes Namespaces Files Functions Variables Enumerations Friends Pages
Ifpack_HashTable.h
1 /*@HEADER
2 // ***********************************************************************
3 //
4 // Ifpack: Object-Oriented Algebraic Preconditioner Package
5 // Copyright (2002) Sandia Corporation
6 //
7 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8 // license for use of this work by or on behalf of the U.S. Government.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are
12 // met:
13 //
14 // 1. Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
16 //
17 // 2. Redistributions in binary form must reproduce the above copyright
18 // notice, this list of conditions and the following disclaimer in the
19 // documentation and/or other materials provided with the distribution.
20 //
21 // 3. Neither the name of the Corporation nor the names of the
22 // contributors may be used to endorse or promote products derived from
23 // this software without specific prior written permission.
24 //
25 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 //
37 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
38 //
39 // ***********************************************************************
40 //@HEADER
41 */
42 
43 /* \file Ifpack_HashTable.h
44  *
45  * \brief HashTable used in Ifpack_ICT and Ifpack_ILUT.
46  *
47  * \author Marzio Sala, ETHZ/D-INFK.
48  *
49  * \date Last modified on 30-Jun-06.
50  */
51 
52 #ifndef IFPACK_HASHTABLE_H
53 #define IFPACK_HASHTABLE_H
54 
55 #include "Ifpack_ConfigDefs.h"
56 
57 // ============================================================================
58 // Hash table with good performances and high level of memory reuse.
59 // Given a maximum number of keys n_keys, this class allocates chunks of memory
60 // to store n_keys keys and values.
61 //
62 // Usage:
63 //
64 // 1) Instantiate a object,
65 //
66 // Ifpack_HashTable Hash(n_keys);
67 //
68 // n_keys - maximum number of keys (This will be the n_keys with zero
69 // collisons.)
70 //
71 // 3) use it, then delete it:
72 //
73 // Hash.get(key, value) --> returns the value stored on key, or 0.0
74 // if not found.
75 // Hash.set(key, value) --> sets the value in the hash table, replace
76 // existing values.
77 // Hash.set(key, value, true) --> to sum into an already inserted value
78 // Hash.arrayify(...)
79 //
80 // 4) clean memory:
81 //
82 // Hash.reset();
83 //
84 // \author Marzio Sala, ETHZ/COLAB
85 //
86 // \date 30-Jun-06
87 // ============================================================================
88 template<typename key_type>
90 {
91  public:
93  TIfpack_HashTable(const int n_keys = 1031, const int n_sets = 1)
94  {
95  n_keys_ = getRecommendedHashSize(n_keys) ;
96  n_sets_ = n_sets;
97  seed_ = (2654435761U);
98 
99  keys_.reserve(50);
100  vals_.reserve(50);
101 
102  keys_.resize(n_sets_);
103  vals_.resize(n_sets_);
104 
105  for (int i = 0; i < n_sets_; ++i)
106  {
107  keys_[i].resize(n_keys_);
108  vals_[i].resize(n_keys_);
109  }
110 
111  counter_.resize(n_keys_);
112  for (int i = 0; i < n_keys_; ++i) counter_[i] = 0;
113  }
114 
116  inline double get(const key_type key)
117  {
118  int hashed_key = doHash(key);
119 
120  for (int set_ptr = 0; set_ptr < counter_[hashed_key]; ++set_ptr)
121  {
122  if (keys_[set_ptr][hashed_key] == key)
123  return(vals_[set_ptr][hashed_key]);
124  }
125 
126  return(0.0);
127  }
128 
130  inline void set(const key_type key, const double value,
131  const bool addToValue = false)
132  {
133  int hashed_key = doHash(key);
134  int& hashed_counter = counter_[hashed_key];
135 
136  for (int set_ptr = 0; set_ptr < hashed_counter; ++set_ptr)
137  {
138  if (keys_[set_ptr][hashed_key] == key)
139  {
140  if (addToValue)
141  vals_[set_ptr][hashed_key] += value;
142  else
143  vals_[set_ptr][hashed_key] = value;
144  return;
145  }
146  }
147 
148  if (hashed_counter < n_sets_)
149  {
150  keys_[hashed_counter][hashed_key] = key;
151  vals_[hashed_counter][hashed_key] = value;
152  ++hashed_counter;
153  return;
154  }
155 
156  std::vector<key_type> new_key;
157  std::vector<double> new_val;
158 
159  keys_.push_back(new_key);
160  vals_.push_back(new_val);
161  keys_[n_sets_].resize(n_keys_);
162  vals_[n_sets_].resize(n_keys_);
163 
164  keys_[n_sets_][hashed_key] = key;
165  vals_[n_sets_][hashed_key] = value;
166  ++hashed_counter;
167  ++n_sets_;
168  }
169 
174  inline void reset()
175  {
176  memset(&counter_[0], 0, sizeof(int) * n_keys_);
177  }
178 
180  inline int getNumEntries() const
181  {
182  int n_entries = 0;
183  for (int key = 0; key < n_keys_; ++key)
184  n_entries += counter_[key];
185  return(n_entries);
186  }
187 
189  void arrayify(key_type* key_array, double* val_array)
190  {
191  int count = 0;
192  for (int key = 0; key < n_keys_; ++key)
193  for (int set_ptr = 0; set_ptr < counter_[key]; ++set_ptr)
194  {
195  key_array[count] = keys_[set_ptr][key];
196  val_array[count] = vals_[set_ptr][key];
197  ++count;
198  }
199  }
200 
202  void print()
203  {
204  using std::cout;
205  using std::endl;
206 
207  cout << "n_keys = " << n_keys_ << endl;
208  cout << "n_sets = " << n_sets_ << endl;
209  }
210 
211  int getRecommendedHashSize (int n)
212  {
213  /* Prime number approximately in the middle of the range [2^x..2^(x+1)]
214  * is in primes[x-1]. Every prime number stored is approximately two
215  * times the previous one, so hash table size doubles every time.
216  */
217  int primes[] = {
218  3, 7, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
219  49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
220  12582917, 25165842, 50331653, 100663319, 201326611, 402653189,
221  805306457, 1610612741 } ;
222  int i, hsize ;
223 
224  /* SRSR : err on the side of performance and choose the next largest
225  * prime number. One can also choose primes[i-1] below to cut the
226  * memory by half.
227  */
228  hsize = primes[29] ;
229  for (i = 6 ; i < 30 ; i++)
230  {
231  if (n <= primes[i])
232  {
233  /*hsize = (i == 0 ? n : primes[i-1]) ;*/
234  hsize = primes[i] ;
235  break ;
236  }
237  }
238 
239  return hsize ;
240  }
241 
242  private:
244  inline int doHash(const key_type key)
245  {
246  return (key % n_keys_);
247  //return ((seed_ ^ key) % n_keys_);
248  }
249 
250  int n_keys_;
251  int n_sets_;
252  std::vector<std::vector<double> > vals_;
253  std::vector<std::vector<key_type> > keys_;
254  std::vector<int> counter_;
255  unsigned int seed_;
256 };
257 
259 {
260  public:
261  Ifpack_HashTable(const int n_keys = 1031, const int n_sets = 1)
262  : TIfpack_HashTable<int>(n_keys, n_sets)
263  {
264  }
265 };
266 
267 class Ifpack_HashTable64 : public TIfpack_HashTable<long long>
268 {
269  public:
270  Ifpack_HashTable64(const int n_keys = 1031, const int n_sets = 1)
271  : TIfpack_HashTable<long long>(n_keys, n_sets)
272  {
273  }
274 };
275 
276 #endif
void print()
Basic printing routine.
void set(const key_type key, const double value, const bool addToValue=false)
Sets an element in the hash table.
TIfpack_HashTable(const int n_keys=1031, const int n_sets=1)
constructor.
void arrayify(key_type *key_array, double *val_array)
Converts the contents in array format for both keys and values.
int getNumEntries() const
Returns the number of stored entries.
void reset()
Resets the entries of the already allocated memory. This method can be used to clean an array...