Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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 
}