1 /* $Header: hash.c,v 1.0 87/12/18 13:05:17 root Exp $
4 * Revision 1.0 87/12/18 13:05:17 root
28 for (s=key, i=0, hash = 0;
30 s++, i++, hash *= 5) {
31 hash += *s * coeff[i];
33 entry = tb->tbl_array[hash & tb->tbl_max];
34 for (; entry; entry = entry->hent_next) {
35 if (entry->hent_hash != hash) /* strings can't be equal */
37 if (strNE(entry->hent_key,key)) /* is this it? */
39 return entry->hent_val;
54 register HENT **oentry;
58 for (s=key, i=0, hash = 0;
60 s++, i++, hash *= 5) {
61 hash += *s * coeff[i];
64 oentry = &(tb->tbl_array[hash & tb->tbl_max]);
67 for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
68 if (entry->hent_hash != hash) /* strings can't be equal */
70 if (strNE(entry->hent_key,key)) /* is this it? */
72 safefree((char*)entry->hent_val);
73 entry->hent_val = val;
76 entry = (HENT*) safemalloc(sizeof(HENT));
78 entry->hent_key = savestr(key);
79 entry->hent_val = val;
80 entry->hent_hash = hash;
81 entry->hent_next = *oentry;
84 if (i) { /* initial entry? */
86 if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
102 register HENT *entry;
103 register HENT **oentry;
107 for (s=key, i=0, hash = 0;
109 s++, i++, hash *= 5) {
110 hash += *s * coeff[i];
113 oentry = &(tb->tbl_array[hash & tb->tbl_max]);
116 for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) {
117 if (entry->hent_hash != hash) /* strings can't be equal */
119 if (strNE(entry->hent_key,key)) /* is this it? */
121 safefree((char*)entry->hent_val);
122 safefree(entry->hent_key);
123 *oentry = entry->hent_next;
124 safefree((char*)entry);
136 int oldsize = tb->tbl_max + 1;
137 register int newsize = oldsize * 2;
141 register HENT *entry;
142 register HENT **oentry;
144 a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
145 bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
146 tb->tbl_max = --newsize;
149 for (i=0; i<oldsize; i++,a++) {
150 if (!*a) /* non-existent */
153 for (oentry = a, entry = *a; entry; entry = *oentry) {
154 if ((entry->hent_hash & newsize) != i) {
155 *oentry = entry->hent_next;
156 entry->hent_next = *b;
163 oentry = &entry->hent_next;
165 if (!*a) /* everything moved */
173 register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
175 tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
178 hiterinit(tb); /* so each() will start off right */
179 bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
187 fprintf(stderr,"%5d %4d (%2d%%)\n",
190 tb->tbl_fill * 100 / (tb->tbl_max+1));
198 tb->tbl_eiter = Null(HENT*);
206 register HENT *entry;
208 entry = tb->tbl_eiter;
211 entry = entry->hent_next;
214 if (tb->tbl_riter > tb->tbl_max) {
218 entry = tb->tbl_array[tb->tbl_riter];
222 tb->tbl_eiter = entry;
228 register HENT *entry;
230 return entry->hent_key;
235 register HENT *entry;
237 return entry->hent_val;