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*
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
35 tabfree(Stringtab *tt)
36 {
37 	tt->link = tfree;
38 	tfree = tt;
39 }
40 
41 char*
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
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
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*
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
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*
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*
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*
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
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
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
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*
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 }