Ifpack Package Browser (Single Doxygen Collection) Development
Loading...
Searching...
No Matches
Hash_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_dh.h"
44#include "Parser_dh.h"
45#include "Mem_dh.h"
46
47static void Hash_dhInit_private (Hash_dh h, int s);
48
49#define CUR_MARK_INIT -1
50
51
58
59
60#undef __FUNC__
61#define __FUNC__ "Hash_dhCreate"
62void
63Hash_dhCreate (Hash_dh * h, int size)
64{
66 struct _hash_dh *tmp =
67 (struct _hash_dh *) MALLOC_DH (sizeof (struct _hash_dh));
69 *h = tmp;
70 tmp->size = 0;
71 tmp->count = 0;
72 tmp->curMark = CUR_MARK_INIT + 1;
73 tmp->data = NULL;
74
78
79#undef __FUNC__
80#define __FUNC__ "Hash_dhDestroy"
81void
83{
84 START_FUNC_DH if (h->data != NULL)
85 {
86 FREE_DH (h->data);
88 }
89 FREE_DH (h);
92
93#undef __FUNC__
94#define __FUNC__ "Hash_dhReset"
95void
97{
98 START_FUNC_DH h->count = 0;
99 h->curMark += 1;
101
102#undef __FUNC__
103#define __FUNC__ "Hash_dhInit_private"
104void
106{
107 START_FUNC_DH int i;
108 int size = 16;
110
111 /* want table size to be a power of 2: */
112 while (size < s)
113 size *= 2;
114 /* rule-of-thumb: ensure there's some padding */
115 if ((size - s) < (.1 * size))
116 {
117 size *= 2.0;
118 }
119 h->size = size;
120
121/*
122 sprintf(msgBuf_dh, "requested size = %i; allocated size = %i", s, size);
123 SET_INFO(msgBuf_dh);
124*/
125
126 /* allocate and zero the hash table */
127 data = h->data = (HashRecord *) MALLOC_DH (size * sizeof (HashRecord));
129 for (i = 0; i < size; ++i)
130 {
131 data[i].key = -1;
132 data[i].mark = -1;
133 }
135
136#undef __FUNC__
137#define __FUNC__ "Hash_dhLookup"
138HashData *
140{
141 START_FUNC_DH int i, start;
142 int curMark = h->curMark;
143 int size = h->size;
144 HashData *retval = NULL;
145 HashRecord *data = h->data;
146
147 HASH_1 (key, size, &start) for (i = 0; i < size; ++i)
148 {
149 int tmp, idx;
150 HASH_2 (key, size, &tmp) idx = (start + i * tmp) % size;
151 if (data[idx].mark != curMark)
152 {
153 break; /* key wasn't found */
154 }
155 else
156 {
157 if (data[idx].key == key)
158 {
159 retval = &(data[idx].data);
160 break;
161 }
162 }
163 }
164END_FUNC_VAL (retval)}
165
166
167/*
168 TODO: (1) check for already-inserted (done?)
169 (2) rehash, if table grows too large
170*/
171#undef __FUNC__
172#define __FUNC__ "Hash_dhInsert"
173void
174Hash_dhInsert (Hash_dh h, int key, HashData * dataIN)
175{
176 START_FUNC_DH int i, start, size = h->size;
177 int curMark = h->curMark;
179
180 data = h->data;
181
182 /* check for overflow */
183 h->count += 1;
184 if (h->count == h->size)
185 {
186 SET_V_ERROR ("hash table overflow; rehash need implementing!");
187 }
188
189 HASH_1 (key, size, &start) for (i = 0; i < size; ++i)
190 {
191 int tmp, idx;
192 HASH_2 (key, size, &tmp) idx = (start + i * tmp) % size;
193 if (data[idx].mark < curMark)
194 {
195 data[idx].key = key;
196 data[idx].mark = curMark;
197 memcpy (&(data[idx].data), dataIN, sizeof (HashData));
198 break;
199 }
200 }
202
203#undef __FUNC__
204#define __FUNC__ "Hash_dhPrint"
205void
206Hash_dhPrint (Hash_dh h, FILE * fp)
207{
208 START_FUNC_DH int i, size = h->size;
209 int curMark = h->curMark;
210 HashRecord *data = h->data;
211
212
213 fprintf (fp, "\n--------------------------- hash table \n");
214 for (i = 0; i < size; ++i)
215 {
216 if (data[i].mark == curMark)
217 {
218 fprintf (fp, "key = %2i; iData = %3i; fData = %g\n",
219 data[i].key, data[i].data.iData, data[i].data.fData);
220 }
221 }
222 fprintf (fp, "\n");
void Hash_dhDestroy(Hash_dh h)
Definition Hash_dh.c:82
HashData * Hash_dhLookup(Hash_dh h, int key)
Definition Hash_dh.c:139
static void Hash_dhInit_private(Hash_dh h, int s)
Definition Hash_dh.c:105
#define CUR_MARK_INIT
Definition Hash_dh.c:49
void Hash_dhPrint(Hash_dh h, FILE *fp)
Definition Hash_dh.c:206
void Hash_dhCreate(Hash_dh *h, int size)
Definition Hash_dh.c:63
void Hash_dhInsert(Hash_dh h, int key, HashData *dataIN)
Definition Hash_dh.c:174
void Hash_dhReset(Hash_dh h)
Definition Hash_dh.c:96
#define HASH_2(k, size, idxOut)
Definition Hash_dh.h:97
#define HASH_1(k, size, idxOut)
Definition Hash_dh.h:94
#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 END_FUNC_DH
Definition macros_dh.h:187
#define END_FUNC_VAL(retval)
Definition macros_dh.h:208
int curMark
Definition Hash_dh.h:79
int count
Definition Hash_dh.h:78
int size
Definition Hash_dh.h:77
HashRecord * data
Definition Hash_dh.h:80
HashData data
Definition Hash_dh.c:56
double fData
Definition Hash_dh.h:65