IFPACK Development
Loading...
Searching...
No Matches
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// ============================================================================
88template<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
267class 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
double get(const key_type key)
Returns an element from the hash table, or 0.0 if not found.
void arrayify(key_type *key_array, double *val_array)
Converts the contents in array format for both keys and values.
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.
void reset()
Resets the entries of the already allocated memory. This method can be used to clean an array,...
int getNumEntries() const
Returns the number of stored entries.
TIfpack_HashTable(const int n_keys=1031, const int n_sets=1)
constructor.