Ifpack Package Browser (Single Doxygen Collection)  Development
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
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;
57 };
58 
59 
60 #undef __FUNC__
61 #define __FUNC__ "Hash_dhCreate"
62 void
63 Hash_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 
75  Hash_dhInit_private (*h, size);
78 
79 #undef __FUNC__
80 #define __FUNC__ "Hash_dhDestroy"
81 void
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"
95 void
97 {
98  START_FUNC_DH h->count = 0;
99  h->curMark += 1;
101 
102 #undef __FUNC__
103 #define __FUNC__ "Hash_dhInit_private"
104 void
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));
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"
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  }
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");
HashData * Hash_dhLookup(Hash_dh h, int key)
Definition: Hash_dh.c:139
void Hash_dhDestroy(Hash_dh h)
Definition: Hash_dh.c:82
#define HASH_2(k, size, idxOut)
Definition: Hash_dh.h:103
#define CHECK_V_ERROR
Definition: macros_dh.h:144
static void Hash_dhInit_private(Hash_dh h, int s)
Definition: Hash_dh.c:105
double fData
Definition: Hash_dh.h:71
#define END_FUNC_DH
Definition: macros_dh.h:193
int count
Definition: Hash_dh.h:84
#define END_FUNC_VAL(retval)
Definition: macros_dh.h:214
#define MALLOC_DH(s)
void Hash_dhPrint(Hash_dh h, FILE *fp)
Definition: Hash_dh.c:206
int curMark
Definition: Hash_dh.h:85
#define CUR_MARK_INIT
Definition: Hash_dh.c:49
void Hash_dhReset(Hash_dh h)
Definition: Hash_dh.c:96
#define SET_V_ERROR(msg)
Definition: macros_dh.h:132
void Hash_dhInsert(Hash_dh h, int key, HashData *dataIN)
Definition: Hash_dh.c:174
#define START_FUNC_DH
Definition: macros_dh.h:187
#define HASH_1(k, size, idxOut)
Definition: Hash_dh.h:100
int size
Definition: Hash_dh.h:83
HashData data
Definition: Hash_dh.c:56
HashRecord * data
Definition: Hash_dh.h:86
void Hash_dhCreate(Hash_dh *h, int size)
Definition: Hash_dh.c:63
#define FREE_DH(p)