Commit | Line | Data |
79072805 |
1 | /* $RCSfile: hash.c,v $$Revision: 4.1 $$Date: 92/08/07 18:29:20 $ |
a687059c |
2 | * |
352d5a3a |
3 | * Copyright (c) 1991, Larry Wall |
a687059c |
4 | * |
352d5a3a |
5 | * You may distribute under the terms of either the GNU General Public |
6 | * License or the Artistic License, as specified in the README file. |
8d063cd8 |
7 | * |
8 | * $Log: hash.c,v $ |
79072805 |
9 | * Revision 4.1 92/08/07 18:29:20 lwall |
10 | * |
352d5a3a |
11 | * Revision 4.0.1.1 91/06/07 12:15:55 lwall |
12 | * patch4: new copyright notice |
13 | * |
fe14fcc3 |
14 | * Revision 4.0 91/03/20 01:57:49 lwall |
15 | * 4.0 baseline. |
8d063cd8 |
16 | * |
17 | */ |
18 | |
19 | #include <stdio.h> |
20 | #include "EXTERN.h" |
21 | #include "handy.h" |
22 | #include "util.h" |
23 | #include "a2p.h" |
24 | |
25 | STR * |
26 | hfetch(tb,key) |
27 | register HASH *tb; |
28 | char *key; |
29 | { |
30 | register char *s; |
31 | register int i; |
32 | register int hash; |
33 | register HENT *entry; |
34 | |
35 | if (!tb) |
36 | return Nullstr; |
37 | for (s=key, i=0, hash = 0; |
38 | /* while */ *s; |
39 | s++, i++, hash *= 5) { |
40 | hash += *s * coeff[i]; |
41 | } |
42 | entry = tb->tbl_array[hash & tb->tbl_max]; |
43 | for (; entry; entry = entry->hent_next) { |
44 | if (entry->hent_hash != hash) /* strings can't be equal */ |
45 | continue; |
46 | if (strNE(entry->hent_key,key)) /* is this it? */ |
47 | continue; |
48 | return entry->hent_val; |
49 | } |
50 | return Nullstr; |
51 | } |
52 | |
53 | bool |
54 | hstore(tb,key,val) |
55 | register HASH *tb; |
56 | char *key; |
57 | STR *val; |
58 | { |
59 | register char *s; |
60 | register int i; |
61 | register int hash; |
62 | register HENT *entry; |
63 | register HENT **oentry; |
64 | |
65 | if (!tb) |
66 | return FALSE; |
67 | for (s=key, i=0, hash = 0; |
68 | /* while */ *s; |
69 | s++, i++, hash *= 5) { |
70 | hash += *s * coeff[i]; |
71 | } |
72 | |
73 | oentry = &(tb->tbl_array[hash & tb->tbl_max]); |
74 | i = 1; |
75 | |
76 | for (entry = *oentry; entry; i=0, entry = entry->hent_next) { |
77 | if (entry->hent_hash != hash) /* strings can't be equal */ |
78 | continue; |
79 | if (strNE(entry->hent_key,key)) /* is this it? */ |
80 | continue; |
fe14fcc3 |
81 | /*NOSTRICT*/ |
8d063cd8 |
82 | safefree((char*)entry->hent_val); |
83 | entry->hent_val = val; |
84 | return TRUE; |
85 | } |
fe14fcc3 |
86 | /*NOSTRICT*/ |
8d063cd8 |
87 | entry = (HENT*) safemalloc(sizeof(HENT)); |
88 | |
89 | entry->hent_key = savestr(key); |
90 | entry->hent_val = val; |
91 | entry->hent_hash = hash; |
92 | entry->hent_next = *oentry; |
93 | *oentry = entry; |
94 | |
95 | if (i) { /* initial entry? */ |
96 | tb->tbl_fill++; |
97 | if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT) |
98 | hsplit(tb); |
99 | } |
100 | |
101 | return FALSE; |
102 | } |
103 | |
104 | #ifdef NOTUSED |
105 | bool |
106 | hdelete(tb,key) |
107 | register HASH *tb; |
108 | char *key; |
109 | { |
110 | register char *s; |
111 | register int i; |
112 | register int hash; |
113 | register HENT *entry; |
114 | register HENT **oentry; |
115 | |
116 | if (!tb) |
117 | return FALSE; |
118 | for (s=key, i=0, hash = 0; |
119 | /* while */ *s; |
120 | s++, i++, hash *= 5) { |
121 | hash += *s * coeff[i]; |
122 | } |
123 | |
124 | oentry = &(tb->tbl_array[hash & tb->tbl_max]); |
125 | entry = *oentry; |
126 | i = 1; |
127 | for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) { |
128 | if (entry->hent_hash != hash) /* strings can't be equal */ |
129 | continue; |
130 | if (strNE(entry->hent_key,key)) /* is this it? */ |
131 | continue; |
132 | safefree((char*)entry->hent_val); |
133 | safefree(entry->hent_key); |
134 | *oentry = entry->hent_next; |
135 | safefree((char*)entry); |
136 | if (i) |
137 | tb->tbl_fill--; |
138 | return TRUE; |
139 | } |
140 | return FALSE; |
141 | } |
142 | #endif |
143 | |
144 | hsplit(tb) |
145 | HASH *tb; |
146 | { |
147 | int oldsize = tb->tbl_max + 1; |
148 | register int newsize = oldsize * 2; |
149 | register int i; |
150 | register HENT **a; |
151 | register HENT **b; |
152 | register HENT *entry; |
153 | register HENT **oentry; |
154 | |
155 | a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*)); |
156 | bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */ |
157 | tb->tbl_max = --newsize; |
158 | tb->tbl_array = a; |
159 | |
160 | for (i=0; i<oldsize; i++,a++) { |
161 | if (!*a) /* non-existent */ |
162 | continue; |
163 | b = a+oldsize; |
164 | for (oentry = a, entry = *a; entry; entry = *oentry) { |
165 | if ((entry->hent_hash & newsize) != i) { |
166 | *oentry = entry->hent_next; |
167 | entry->hent_next = *b; |
168 | if (!*b) |
169 | tb->tbl_fill++; |
170 | *b = entry; |
171 | continue; |
172 | } |
173 | else |
174 | oentry = &entry->hent_next; |
175 | } |
176 | if (!*a) /* everything moved */ |
177 | tb->tbl_fill--; |
178 | } |
179 | } |
180 | |
181 | HASH * |
182 | hnew() |
183 | { |
184 | register HASH *tb = (HASH*)safemalloc(sizeof(HASH)); |
185 | |
186 | tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*)); |
187 | tb->tbl_fill = 0; |
188 | tb->tbl_max = 7; |
189 | hiterinit(tb); /* so each() will start off right */ |
190 | bzero((char*)tb->tbl_array, 8 * sizeof(HENT*)); |
191 | return tb; |
192 | } |
193 | |
194 | #ifdef NOTUSED |
195 | hshow(tb) |
196 | register HASH *tb; |
197 | { |
198 | fprintf(stderr,"%5d %4d (%2d%%)\n", |
199 | tb->tbl_max+1, |
200 | tb->tbl_fill, |
201 | tb->tbl_fill * 100 / (tb->tbl_max+1)); |
202 | } |
203 | #endif |
204 | |
205 | hiterinit(tb) |
206 | register HASH *tb; |
207 | { |
208 | tb->tbl_riter = -1; |
209 | tb->tbl_eiter = Null(HENT*); |
210 | return tb->tbl_fill; |
211 | } |
212 | |
213 | HENT * |
214 | hiternext(tb) |
215 | register HASH *tb; |
216 | { |
217 | register HENT *entry; |
218 | |
219 | entry = tb->tbl_eiter; |
220 | do { |
221 | if (entry) |
222 | entry = entry->hent_next; |
223 | if (!entry) { |
224 | tb->tbl_riter++; |
225 | if (tb->tbl_riter > tb->tbl_max) { |
226 | tb->tbl_riter = -1; |
227 | break; |
228 | } |
229 | entry = tb->tbl_array[tb->tbl_riter]; |
230 | } |
231 | } while (!entry); |
232 | |
233 | tb->tbl_eiter = entry; |
234 | return entry; |
235 | } |
236 | |
237 | char * |
238 | hiterkey(entry) |
239 | register HENT *entry; |
240 | { |
241 | return entry->hent_key; |
242 | } |
243 | |
244 | STR * |
245 | hiterval(entry) |
246 | register HENT *entry; |
247 | { |
248 | return entry->hent_val; |
249 | } |