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