Ifpack Package Browser (Single Doxygen Collection) Development
Loading...
Searching...
No Matches
Hash_i_dh.c
Go to the documentation of this file.
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#include "Hash_i_dh.h"
44#include "Parser_dh.h"
45#include "Mem_dh.h"
46
47#define DEFAULT_TABLE_SIZE 16
48
49static void rehash_private (Hash_i_dh h);
50
51
52/*--------------------------------------------------------------
53 * hash functions (double hashing is used)
54 *--------------------------------------------------------------*/
55#define HASH_1(k,size,idxOut) \
56 { *idxOut = k % size; }
57
58#define HASH_2(k,size,idxOut) \
59 { \
60 int r = k % (size-13); \
61 r = (r % 2) ? r : r+1; \
62 *idxOut = r; \
63 }
64
65
66/*--------------------------------------------------------------
67 * class structure
68 *--------------------------------------------------------------*/
70
72{
73 int key;
74 int mark;
75 int data;
76};
77
78
80{
81 int size; /* total slots in table */
82 int count; /* number of items inserted in table */
83 int curMark; /* used by Reset */
85};
86
87
88/*--------------------------------------------------------------
89 * class methods follow
90 *--------------------------------------------------------------*/
91
92#undef __FUNC__
93#define __FUNC__ "Hash_i_dhCreate"
94void
95Hash_i_dhCreate (Hash_i_dh * h, int sizeIN)
96{
97 START_FUNC_DH int i, size;
98 Hash_i_Record *tmp2;
99 struct _hash_i_dh *tmp;
100
102 if (sizeIN == -1)
103 {
104 sizeIN = size = DEFAULT_TABLE_SIZE;
105 }
106 tmp = (struct _hash_i_dh *) MALLOC_DH (sizeof (struct _hash_i_dh));
108 *h = tmp;
109 tmp->size = 0;
110 tmp->count = 0;
111 tmp->curMark = 0;
112 tmp->data = NULL;
113
114 /*
115 determine initial hash table size. If this is too small,
116 it will be dynamically enlarged as needed by Hash_i_dhInsert()
117 See "double hashing," p. 255, "Algorithms," Cormen, et. al.
118 */
119 while (size < sizeIN)
120 size *= 2; /* want table size to be a power of 2: */
121 /* rule-of-thumb: ensure there's at least 10% padding */
122 if ((size - sizeIN) < (.1 * size))
123 {
124 size *= 2.0;
125 }
126 tmp->size = size;
127
128
129 /* allocate and zero the hash table */
130 tmp2 = tmp->data =
131 (Hash_i_Record *) MALLOC_DH (size * sizeof (Hash_i_Record));
133 for (i = 0; i < size; ++i)
134 {
135 tmp2[i].key = -1;
136 tmp2[i].mark = -1;
137 /* "tmp2[i].data" needn't be initialized */
138 }
139
141
142
143#undef __FUNC__
144#define __FUNC__ "Hash_i_dhDestroy"
145void
147{
148 START_FUNC_DH if (h->data != NULL)
149 {
150 FREE_DH (h->data);
152 }
153 FREE_DH (h);
156
157#undef __FUNC__
158#define __FUNC__ "Hash_i_dhReset"
159void
161{
162 START_FUNC_DH h->count = 0;
163 h->curMark += 1;
165
166
167#undef __FUNC__
168#define __FUNC__ "Hash_i_dhLookup"
169int
171{
172 START_FUNC_DH int idx, inc, i, start;
173 int curMark = h->curMark;
174 int size = h->size;
175 int retval = -1;
176 Hash_i_Record *data = h->data;
177
178 HASH_1 (key, size, &start) HASH_2 (key, size, &inc)
179/*printf("Hash_i_dhLookup:: key: %i tableSize: %i start: %i inc: %i\n", key, size, start, inc);
180*/
181 for (i = 0; i < size; ++i)
182 {
183 idx = (start + i * inc) % size;
184
185/* printf(" idx= %i\n", idx); */
186
187 if (data[idx].mark != curMark)
188 {
189 break; /* key wasn't found */
190 }
191 else
192 {
193 if (data[idx].key == key)
194 {
195 retval = data[idx].data;
196 break;
197 }
198 }
199 }
200END_FUNC_VAL (retval)}
201
202
203#undef __FUNC__
204#define __FUNC__ "Hash_i_dhInsert"
205void
206Hash_i_dhInsert (Hash_i_dh h, int key, int dataIN)
207{
208 START_FUNC_DH int i, idx, inc, start, size;
209 int curMark = h->curMark;
211 bool success = false;
212
213 if (dataIN < 0)
214 {
215 sprintf (msgBuf_dh, "data = %i must be >= 0", dataIN);
217 }
218
219 /* enlarge table if necessary */
220 if (h->count >= 0.9 * h->size)
221 {
222 rehash_private (h);
224 }
225
226 size = h->size;
227 data = h->data;
228 h->count += 1; /* for this insertion */
229
230 HASH_1 (key, size, &start) HASH_2 (key, size, &inc)
231/*printf("Hash_i_dhInsert:: tableSize= %i start= %i inc= %i\n", size, start, inc);
232*/
233 for (i = 0; i < size; ++i)
234 {
235 idx = (start + i * inc) % size;
236
237/* printf(" idx= %i\n", idx);
238*/
239
240 /* check for previous insertion */
241 if (data[idx].mark == curMark && data[idx].key == key)
242 {
243 sprintf (msgBuf_dh, "key,data= <%i, %i> already inserted", key,
244 dataIN);
246 }
247
248 if (data[idx].mark < curMark)
249 {
250 data[idx].key = key;
251 data[idx].mark = curMark;
252 data[idx].data = dataIN;
253 success = true;
254 break;
255 }
256 }
257
258 if (!success)
259 { /* should be impossible to be here, I think . . . */
260 sprintf (msgBuf_dh, "Failed to insert key= %i, data= %i", key, dataIN);
261 }
263
264
265#undef __FUNC__
266#define __FUNC__ "rehash_private"
267void
269{
271 int i,
272 old_size = h->size, new_size = old_size * 2, oldCurMark = h->curMark;
273 Hash_i_Record *oldData = h->data, *newData;
274
275 sprintf (msgBuf_dh, "rehashing; old_size= %i, new_size= %i", old_size,
276 new_size);
278
279 /* allocate new data table, and install it in the Hash_i_dh object;
280 essentially, we reinitialize the hash object.
281 */
282 newData = (Hash_i_Record *) MALLOC_DH (new_size * sizeof (Hash_i_Record));
284 for (i = 0; i < new_size; ++i)
285 {
286 newData[i].key = -1;
287 newData[i].mark = -1;
288 }
289 h->size = new_size;
290 h->data = newData;
291 h->count = 0;
292 h->curMark = 0;
293
294 for (i = h->count; i < new_size; ++i)
295 {
296 newData[i].key = -1;
297 newData[i].mark = -1;
298 }
299
300 /* insert <key, data> pairs from old table to new table;
301 wouldn't have been called) it's simplest to sweep through
302 the old table.
303 */
304 for (i = 0; i < old_size; ++i)
305 {
306 if (oldData[i].mark == oldCurMark)
307 {
308 Hash_i_dhInsert (h, oldData[i].key, oldData[i].data);
310 }
311 }
312
313 FREE_DH (oldData);
void Hash_i_dhCreate(Hash_i_dh *h, int sizeIN)
Definition: Hash_i_dh.c:95
static void rehash_private(Hash_i_dh h)
Definition: Hash_i_dh.c:268
void Hash_i_dhReset(Hash_i_dh h)
Definition: Hash_i_dh.c:160
#define HASH_2(k, size, idxOut)
Definition: Hash_i_dh.c:58
void Hash_i_dhInsert(Hash_i_dh h, int key, int dataIN)
Definition: Hash_i_dh.c:206
void Hash_i_dhDestroy(Hash_i_dh h)
Definition: Hash_i_dh.c:146
#define HASH_1(k, size, idxOut)
Definition: Hash_i_dh.c:55
int Hash_i_dhLookup(Hash_i_dh h, int key)
Definition: Hash_i_dh.c:170
#define DEFAULT_TABLE_SIZE
Definition: Hash_i_dh.c:47
char msgBuf_dh[MSG_BUF_SIZE_DH]
Definition: globalObjects.c:61
#define MALLOC_DH(s)
#define FREE_DH(p)
#define SET_V_ERROR(msg)
Definition: macros_dh.h:126
#define START_FUNC_DH
Definition: macros_dh.h:181
#define CHECK_V_ERROR
Definition: macros_dh.h:138
#define SET_INFO(msg)
Definition: macros_dh.h:156
#define END_FUNC_DH
Definition: macros_dh.h:187
#define END_FUNC_VAL(retval)
Definition: macros_dh.h:208
int curMark
Definition: Hash_i_dh.c:83
int count
Definition: Hash_i_dh.c:82
int size
Definition: Hash_i_dh.c:81
Hash_i_Record * data
Definition: Hash_i_dh.c:84