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