IFPACK  Development
 All Classes Namespaces Files Functions Variables Enumerations Friends Pages
Hash_dh.c
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 
47 static void Hash_dhInit_private (Hash_dh h, int s);
48 
49 #define CUR_MARK_INIT -1
50 
51 
53 {
54  int key;
55  int mark;
56  HashData data;
57 };
58 
59 
60 #undef __FUNC__
61 #define __FUNC__ "Hash_dhCreate"
62 void
63 Hash_dhCreate (Hash_dh * h, int size)
64 {
65  START_FUNC_DH
66  struct _hash_dh *tmp =
67  (struct _hash_dh *) MALLOC_DH (sizeof (struct _hash_dh));
68  CHECK_V_ERROR;
69  *h = tmp;
70  tmp->size = 0;
71  tmp->count = 0;
72  tmp->curMark = CUR_MARK_INIT + 1;
73  tmp->data = NULL;
74 
75  Hash_dhInit_private (*h, size);
76  CHECK_V_ERROR;
77 END_FUNC_DH}
78 
79 #undef __FUNC__
80 #define __FUNC__ "Hash_dhDestroy"
81 void
82 Hash_dhDestroy (Hash_dh h)
83 {
84  START_FUNC_DH if (h->data != NULL)
85  {
86  FREE_DH (h->data);
87  CHECK_V_ERROR;
88  }
89  FREE_DH (h);
90  CHECK_V_ERROR;
91 END_FUNC_DH}
92 
93 #undef __FUNC__
94 #define __FUNC__ "Hash_dhReset"
95 void
96 Hash_dhReset (Hash_dh h)
97 {
98  START_FUNC_DH h->count = 0;
99  h->curMark += 1;
100 END_FUNC_DH}
101 
102 #undef __FUNC__
103 #define __FUNC__ "Hash_dhInit_private"
104 void
105 Hash_dhInit_private (Hash_dh h, int s)
106 {
107  START_FUNC_DH int i;
108  int size = 16;
109  HashRecord *data;
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));
128  CHECK_V_ERROR;
129  for (i = 0; i < size; ++i)
130  {
131  data[i].key = -1;
132  data[i].mark = -1;
133  }
134 END_FUNC_DH}
135 
136 #undef __FUNC__
137 #define __FUNC__ "Hash_dhLookup"
138 HashData *
139 Hash_dhLookup (Hash_dh h, int key)
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  }
164 END_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"
173 void
174 Hash_dhInsert (Hash_dh h, int key, HashData * dataIN)
175 {
176  START_FUNC_DH int i, start, size = h->size;
177  int curMark = h->curMark;
178  HashRecord *data;
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  }
201 END_FUNC_DH}
202 
203 #undef __FUNC__
204 #define __FUNC__ "Hash_dhPrint"
205 void
206 Hash_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");
223 END_FUNC_DH}