43 #include "Hash_i_dh.h"
44 #include "Parser_dh.h"
47 #define DEFAULT_TABLE_SIZE 16
55 #define HASH_1(k,size,idxOut) \
56 { *idxOut = k % size; }
58 #define HASH_2(k,size,idxOut) \
60 int r = k % (size-13); \
61 r = (r % 2) ? r : r+1; \
93 #define __FUNC__ "Hash_i_dhCreate"
95 Hash_i_dhCreate (
Hash_i_dh * h,
int sizeIN)
97 START_FUNC_DH
int i, size;
101 size = DEFAULT_TABLE_SIZE;
104 sizeIN = size = DEFAULT_TABLE_SIZE;
119 while (size < sizeIN)
122 if ((size - sizeIN) < (.1 * size))
133 for (i = 0; i < size; ++i)
144 #define __FUNC__ "Hash_i_dhDestroy"
148 START_FUNC_DH
if (h->data != NULL)
158 #define __FUNC__ "Hash_i_dhReset"
162 START_FUNC_DH h->count = 0;
168 #define __FUNC__ "Hash_i_dhLookup"
172 START_FUNC_DH
int idx, inc, i, start;
173 int curMark = h->curMark;
178 HASH_1 (key, size, &start) HASH_2 (key, size, &inc)
181 for (i = 0; i < size; ++i)
183 idx = (start + i * inc) % size;
187 if (data[idx].mark != curMark)
193 if (data[idx].key == key)
195 retval = data[idx].data;
200 END_FUNC_VAL (retval)}
204 #define __FUNC__ "Hash_i_dhInsert"
206 Hash_i_dhInsert (
Hash_i_dh h,
int key,
int dataIN)
208 START_FUNC_DH
int i, idx, inc, start, size;
209 int curMark = h->curMark;
211 bool success =
false;
215 sprintf (msgBuf_dh,
"data = %i must be >= 0", dataIN);
216 SET_V_ERROR (msgBuf_dh);
220 if (h->count >= 0.9 * h->size)
230 HASH_1 (key, size, &start) HASH_2 (key, size, &inc)
233 for (i = 0; i < size; ++i)
235 idx = (start + i * inc) % size;
241 if (data[idx].mark == curMark && data[idx].key == key)
243 sprintf (msgBuf_dh,
"key,data= <%i, %i> already inserted", key,
245 SET_V_ERROR (msgBuf_dh);
248 if (data[idx].mark < curMark)
251 data[idx].mark = curMark;
252 data[idx].data = dataIN;
260 sprintf (msgBuf_dh,
"Failed to insert key= %i, data= %i", key, dataIN);
266 #define __FUNC__ "rehash_private"
272 old_size = h->size, new_size = old_size * 2, oldCurMark = h->curMark;
275 sprintf (msgBuf_dh,
"rehashing; old_size= %i, new_size= %i", old_size,
277 SET_INFO (msgBuf_dh);
284 for (i = 0; i < new_size; ++i)
287 newData[i].mark = -1;
294 for (i = h->count; i < new_size; ++i)
297 newData[i].mark = -1;
304 for (i = 0; i < old_size; ++i)
306 if (oldData[i].mark == oldCurMark)
308 Hash_i_dhInsert (h, oldData[i].key, oldData[i].data);