1 #include <u.h>
2 #include <libc.h>
3 #include <bio.h>
4 #include "hash.h"
5
6 /***
7 * String hash tables.
8 */
9
10 Stringtab *tfree;
11
12 Stringtab*
taballoc(void)13 taballoc(void)
14 {
15 static Stringtab *t;
16 static uint nt;
17
18 if(tfree){
19 Stringtab *tt = tfree;
20 tfree = tt->link;
21 return tt;
22 }
23
24 if(nt == 0){
25 t = malloc(64000*sizeof(Stringtab));
26 if(t == 0)
27 sysfatal("out of memory");
28 nt = 64000;
29 }
30 nt--;
31 return t++;
32 }
33
34 void
tabfree(Stringtab * tt)35 tabfree(Stringtab *tt)
36 {
37 tt->link = tfree;
38 tfree = tt;
39 }
40
41 char*
xstrdup(char * s,int len)42 xstrdup(char *s, int len)
43 {
44 char *r;
45 static char *t;
46 static int nt;
47
48 if(nt < len){
49 t = malloc(512*1024+len);
50 if(t == 0)
51 sysfatal("out of memory");
52 nt = 512*1024;
53 }
54 r = t;
55 t += len;
56 nt -= len;
57 memmove(r, s, len);
58 return r;
59 }
60
61 static uint
hash(char * s,int n)62 hash(char *s, int n)
63 {
64 uint h;
65 uchar *p, *ep;
66 h = 0;
67 for(p=(uchar*)s, ep=p+n; p<ep; p++)
68 h = h*37 + *p;
69 return h;
70 }
71
72 static void
rehash(Hash * hh)73 rehash(Hash *hh)
74 {
75 int h;
76 Stringtab *s;
77
78 if(hh->nstab == 0)
79 hh->nstab = 1024;
80 else
81 hh->nstab = hh->ntab*2;
82
83 free(hh->stab);
84 hh->stab = mallocz(hh->nstab*sizeof(Stringtab*), 1);
85 if(hh->stab == nil)
86 sysfatal("out of memory");
87
88 for(s=hh->all; s; s=s->link){
89 h = hash(s->str, s->n) % hh->nstab;
90 s->hash = hh->stab[h];
91 hh->stab[h] = s;
92 }
93 }
94
95 Stringtab*
findstab(Hash * hh,char * str,int n,int create)96 findstab(Hash *hh, char *str, int n, int create)
97 {
98 uint h;
99 Stringtab *tab, **l;
100
101 if(hh->nstab == 0)
102 rehash(hh);
103
104 h = hash(str, n) % hh->nstab;
105 for(tab=hh->stab[h], l=&hh->stab[h]; tab; l=&tab->hash, tab=tab->hash)
106 if(n==tab->n && memcmp(str, tab->str, n) == 0){
107 *l = tab->hash;
108 tab->hash = hh->stab[h];
109 hh->stab[h] = tab;
110 return tab;
111 }
112
113 if(!create)
114 return nil;
115
116 hh->sorted = 0;
117 tab = taballoc();
118 tab->str = xstrdup(str, n);
119 tab->hash = hh->stab[h];
120 tab->link = hh->all;
121 hh->all = tab;
122 tab->n = n;
123 tab->count = 0;
124 tab->date = 0;
125 hh->stab[h] = tab;
126
127 hh->ntab++;
128 if(hh->ntab > 2*hh->nstab && !(hh->ntab&(hh->ntab-1)))
129 rehash(hh);
130 return tab;
131 }
132
133 int
scmp(Stringtab * a,Stringtab * b)134 scmp(Stringtab *a, Stringtab *b)
135 {
136 int n, x;
137
138 if(a == 0)
139 return 1;
140 if(b == 0)
141 return -1;
142 n = a->n;
143 if(n > b->n)
144 n = b->n;
145 x = memcmp(a->str, b->str, n);
146 if(x != 0)
147 return x;
148 if(a->n < b->n)
149 return -1;
150 if(a->n > b->n)
151 return 1;
152 return 0; /* shouldn't happen */
153 }
154
155 Stringtab*
merge(Stringtab * a,Stringtab * b)156 merge(Stringtab *a, Stringtab *b)
157 {
158 Stringtab *s, **l;
159
160 l = &s;
161 while(a || b){
162 if(scmp(a, b) < 0){
163 *l = a;
164 l = &a->link;
165 a = a->link;
166 }else{
167 *l = b;
168 l = &b->link;
169 b = b->link;
170 }
171 }
172 *l = 0;
173 return s;
174 }
175
176 Stringtab*
mergesort(Stringtab * s)177 mergesort(Stringtab *s)
178 {
179 Stringtab *a, *b;
180 int delay;
181
182 if(s == nil)
183 return nil;
184 if(s->link == nil)
185 return s;
186
187 a = b = s;
188 delay = 1;
189 while(a && b){
190 if(delay) /* easy way to handle 2-element list */
191 delay = 0;
192 else
193 a = a->link;
194 if(b = b->link)
195 b = b->link;
196 }
197
198 b = a->link;
199 a->link = nil;
200
201 a = mergesort(s);
202 b = mergesort(b);
203
204 return merge(a, b);
205 }
206
207 Stringtab*
sortstab(Hash * hh)208 sortstab(Hash *hh)
209 {
210 if(!hh->sorted){
211 hh->all = mergesort(hh->all);
212 hh->sorted = 1;
213 }
214 return hh->all;
215 }
216
217 int
Bwritehash(Biobuf * b,Hash * hh)218 Bwritehash(Biobuf *b, Hash *hh)
219 {
220 Stringtab *s;
221 int now;
222
223 now = time(0);
224 s = sortstab(hh);
225 Bprint(b, "# hash table\n");
226 for(; s; s=s->link){
227 if(s->count <= 0)
228 continue;
229 /*
230 * Entries that haven't been updated in thirty days get tossed.
231 */
232 if(s->date+30*86400 < now)
233 continue;
234 Bwrite(b, s->str, s->n);
235 Bprint(b, "\t%d %d\n", s->count, s->date);
236 }
237 if(Bflush(b) == Beof)
238 return -1;
239 return 0;
240 }
241
242 void
Breadhash(Biobuf * b,Hash * hh,int scale)243 Breadhash(Biobuf *b, Hash *hh, int scale)
244 {
245 char *s;
246 char *t;
247 int n;
248 int date;
249 Stringtab *st;
250
251 s = Brdstr(b, '\n', 1);
252 if(s == nil)
253 return;
254 if(strcmp(s, "# hash table") != 0)
255 sysfatal("bad hash table format");
256
257 while(s = Brdline(b, '\n')){
258 s[Blinelen(b)-1] = 0;
259 t = strrchr(s, '\t');
260 if(t == nil)
261 sysfatal("bad hash table format");
262 *t++ = '\0';
263 if(*t < '0' || *t > '9')
264 sysfatal("bad hash table format");
265 n = strtol(t, &t, 10);
266 date = time(0);
267 if(*t != 0){
268 if(*t == ' '){
269 t++;
270 date = strtol(t, &t, 10);
271 }
272 if(*t != 0)
273 sysfatal("bad hash table format");
274 }
275 st = findstab(hh, s, strlen(s), 1);
276 if(date > st->date)
277 st->date = date;
278 st->count += n*scale;
279 }
280 }
281
282 void
freehash(Hash * h)283 freehash(Hash *h)
284 {
285 Stringtab *s, *next;
286
287 for(s=h->all; s; s=next){
288 next = s->link;
289 tabfree(s);
290 }
291 free(h->stab);
292 free(h);
293 }
294
295 Biobuf*
Bopenlock(char * file,int mode)296 Bopenlock(char *file, int mode)
297 {
298 int i;
299 Biobuf *b;
300 char err[ERRMAX];
301
302 b = nil;
303 for(i=0; i<120; i++){
304 if((b = Bopen(file, mode)) != nil)
305 break;
306 rerrstr(err, sizeof err);
307 if(strstr(err, "file is locked")==nil && strstr(err, "exclusive lock")==nil)
308 break;
309 sleep(1000);
310 }
311 return b;
312 }
313