Commit | Line | Data |
378cc40b |
1 | /* $Header: hash.c,v 2.0 88/06/05 00:09:06 root Exp $ |
8d063cd8 |
2 | * |
3 | * $Log: hash.c,v $ |
378cc40b |
4 | * Revision 2.0 88/06/05 00:09:06 root |
5 | * Baseline version 2.0. |
8d063cd8 |
6 | * |
7 | */ |
8 | |
8d063cd8 |
9 | #include "EXTERN.h" |
8d063cd8 |
10 | #include "perl.h" |
11 | |
12 | STR * |
13 | hfetch(tb,key) |
14 | register HASH *tb; |
15 | char *key; |
16 | { |
17 | register char *s; |
18 | register int i; |
19 | register int hash; |
20 | register HENT *entry; |
21 | |
22 | if (!tb) |
23 | return Nullstr; |
24 | for (s=key, i=0, hash = 0; |
378cc40b |
25 | /* while */ *s && i < COEFFSIZE; |
8d063cd8 |
26 | s++, i++, hash *= 5) { |
27 | hash += *s * coeff[i]; |
28 | } |
29 | entry = tb->tbl_array[hash & tb->tbl_max]; |
30 | for (; entry; entry = entry->hent_next) { |
31 | if (entry->hent_hash != hash) /* strings can't be equal */ |
32 | continue; |
33 | if (strNE(entry->hent_key,key)) /* is this it? */ |
34 | continue; |
35 | return entry->hent_val; |
36 | } |
37 | return Nullstr; |
38 | } |
39 | |
40 | bool |
41 | hstore(tb,key,val) |
42 | register HASH *tb; |
43 | char *key; |
44 | STR *val; |
45 | { |
46 | register char *s; |
47 | register int i; |
48 | register int hash; |
49 | register HENT *entry; |
50 | register HENT **oentry; |
51 | |
52 | if (!tb) |
53 | return FALSE; |
54 | for (s=key, i=0, hash = 0; |
378cc40b |
55 | /* while */ *s && i < COEFFSIZE; |
8d063cd8 |
56 | s++, i++, hash *= 5) { |
57 | hash += *s * coeff[i]; |
58 | } |
59 | |
60 | oentry = &(tb->tbl_array[hash & tb->tbl_max]); |
61 | i = 1; |
62 | |
63 | for (entry = *oentry; entry; i=0, entry = entry->hent_next) { |
64 | if (entry->hent_hash != hash) /* strings can't be equal */ |
65 | continue; |
66 | if (strNE(entry->hent_key,key)) /* is this it? */ |
67 | continue; |
68 | safefree((char*)entry->hent_val); |
69 | entry->hent_val = val; |
70 | return TRUE; |
71 | } |
72 | entry = (HENT*) safemalloc(sizeof(HENT)); |
73 | |
74 | entry->hent_key = savestr(key); |
75 | entry->hent_val = val; |
76 | entry->hent_hash = hash; |
77 | entry->hent_next = *oentry; |
78 | *oentry = entry; |
79 | |
80 | if (i) { /* initial entry? */ |
81 | tb->tbl_fill++; |
82 | if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT) |
83 | hsplit(tb); |
84 | } |
85 | |
86 | return FALSE; |
87 | } |
88 | |
378cc40b |
89 | STR * |
8d063cd8 |
90 | hdelete(tb,key) |
91 | register HASH *tb; |
92 | char *key; |
93 | { |
94 | register char *s; |
95 | register int i; |
96 | register int hash; |
97 | register HENT *entry; |
98 | register HENT **oentry; |
378cc40b |
99 | STR *str; |
8d063cd8 |
100 | |
101 | if (!tb) |
378cc40b |
102 | return Nullstr; |
8d063cd8 |
103 | for (s=key, i=0, hash = 0; |
378cc40b |
104 | /* while */ *s && i < COEFFSIZE; |
8d063cd8 |
105 | s++, i++, hash *= 5) { |
106 | hash += *s * coeff[i]; |
107 | } |
108 | |
109 | oentry = &(tb->tbl_array[hash & tb->tbl_max]); |
110 | entry = *oentry; |
111 | i = 1; |
378cc40b |
112 | for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) { |
8d063cd8 |
113 | if (entry->hent_hash != hash) /* strings can't be equal */ |
114 | continue; |
115 | if (strNE(entry->hent_key,key)) /* is this it? */ |
116 | continue; |
8d063cd8 |
117 | *oentry = entry->hent_next; |
378cc40b |
118 | str = str_static(entry->hent_val); |
119 | hentfree(entry); |
8d063cd8 |
120 | if (i) |
121 | tb->tbl_fill--; |
378cc40b |
122 | return str; |
8d063cd8 |
123 | } |
378cc40b |
124 | return Nullstr; |
8d063cd8 |
125 | } |
8d063cd8 |
126 | |
127 | hsplit(tb) |
128 | HASH *tb; |
129 | { |
130 | int oldsize = tb->tbl_max + 1; |
131 | register int newsize = oldsize * 2; |
132 | register int i; |
133 | register HENT **a; |
134 | register HENT **b; |
135 | register HENT *entry; |
136 | register HENT **oentry; |
137 | |
138 | a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*)); |
139 | bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */ |
140 | tb->tbl_max = --newsize; |
141 | tb->tbl_array = a; |
142 | |
143 | for (i=0; i<oldsize; i++,a++) { |
144 | if (!*a) /* non-existent */ |
145 | continue; |
146 | b = a+oldsize; |
147 | for (oentry = a, entry = *a; entry; entry = *oentry) { |
148 | if ((entry->hent_hash & newsize) != i) { |
149 | *oentry = entry->hent_next; |
150 | entry->hent_next = *b; |
151 | if (!*b) |
152 | tb->tbl_fill++; |
153 | *b = entry; |
154 | continue; |
155 | } |
156 | else |
157 | oentry = &entry->hent_next; |
158 | } |
159 | if (!*a) /* everything moved */ |
160 | tb->tbl_fill--; |
161 | } |
162 | } |
163 | |
164 | HASH * |
165 | hnew() |
166 | { |
167 | register HASH *tb = (HASH*)safemalloc(sizeof(HASH)); |
168 | |
169 | tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*)); |
170 | tb->tbl_fill = 0; |
171 | tb->tbl_max = 7; |
172 | hiterinit(tb); /* so each() will start off right */ |
173 | bzero((char*)tb->tbl_array, 8 * sizeof(HENT*)); |
174 | return tb; |
175 | } |
176 | |
378cc40b |
177 | void |
178 | hentfree(hent) |
179 | register HENT *hent; |
180 | { |
181 | if (!hent) |
182 | return; |
183 | str_free(hent->hent_val); |
184 | safefree(hent->hent_key); |
185 | safefree((char*)hent); |
186 | } |
187 | |
188 | void |
189 | hclear(tb) |
190 | register HASH *tb; |
191 | { |
192 | register HENT *hent; |
193 | register HENT *ohent = Null(HENT*); |
194 | |
195 | if (!tb) |
196 | return; |
197 | hiterinit(tb); |
198 | while (hent = hiternext(tb)) { /* concise but not very efficient */ |
199 | hentfree(ohent); |
200 | ohent = hent; |
201 | } |
202 | hentfree(ohent); |
203 | tb->tbl_fill = 0; |
204 | bzero((char*)tb->tbl_array, (tb->tbl_max + 1) * sizeof(HENT*)); |
205 | } |
206 | |
207 | #ifdef NOTUSED |
208 | void |
209 | hfree(tb) |
210 | HASH *tb; |
211 | { |
212 | if (!tb) |
213 | return |
214 | hiterinit(tb); |
215 | while (hent = hiternext(tb)) { |
216 | hentfree(ohent); |
217 | ohent = hent; |
218 | } |
219 | hentfree(ohent); |
220 | safefree((char*)tb->tbl_array); |
221 | safefree((char*)tb); |
222 | } |
223 | #endif |
224 | |
8d063cd8 |
225 | #ifdef NOTUSED |
226 | hshow(tb) |
227 | register HASH *tb; |
228 | { |
229 | fprintf(stderr,"%5d %4d (%2d%%)\n", |
230 | tb->tbl_max+1, |
231 | tb->tbl_fill, |
232 | tb->tbl_fill * 100 / (tb->tbl_max+1)); |
233 | } |
234 | #endif |
235 | |
236 | hiterinit(tb) |
237 | register HASH *tb; |
238 | { |
239 | tb->tbl_riter = -1; |
240 | tb->tbl_eiter = Null(HENT*); |
241 | return tb->tbl_fill; |
242 | } |
243 | |
244 | HENT * |
245 | hiternext(tb) |
246 | register HASH *tb; |
247 | { |
248 | register HENT *entry; |
249 | |
250 | entry = tb->tbl_eiter; |
251 | do { |
252 | if (entry) |
253 | entry = entry->hent_next; |
254 | if (!entry) { |
255 | tb->tbl_riter++; |
256 | if (tb->tbl_riter > tb->tbl_max) { |
257 | tb->tbl_riter = -1; |
258 | break; |
259 | } |
260 | entry = tb->tbl_array[tb->tbl_riter]; |
261 | } |
262 | } while (!entry); |
263 | |
264 | tb->tbl_eiter = entry; |
265 | return entry; |
266 | } |
267 | |
268 | char * |
269 | hiterkey(entry) |
270 | register HENT *entry; |
271 | { |
272 | return entry->hent_key; |
273 | } |
274 | |
275 | STR * |
276 | hiterval(entry) |
277 | register HENT *entry; |
278 | { |
279 | return entry->hent_val; |
280 | } |