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"
7 d1f529f4 2005-10-29 devnull * String hash tables.
10 d1f529f4 2005-10-29 devnull Stringtab *tfree;
12 d1f529f4 2005-10-29 devnull Stringtab*
13 d1f529f4 2005-10-29 devnull taballoc(void)
15 d1f529f4 2005-10-29 devnull static Stringtab *t;
16 d1f529f4 2005-10-29 devnull static uint nt;
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;
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;
31 d1f529f4 2005-10-29 devnull return t++;
35 d1f529f4 2005-10-29 devnull tabfree(Stringtab *tt)
37 d1f529f4 2005-10-29 devnull tt->link = tfree;
38 d1f529f4 2005-10-29 devnull tfree = tt;
42 d1f529f4 2005-10-29 devnull xstrdup(char *s, int len)
45 d1f529f4 2005-10-29 devnull static char *t;
46 d1f529f4 2005-10-29 devnull static int nt;
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;
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;
61 d1f529f4 2005-10-29 devnull static uint
62 d1f529f4 2005-10-29 devnull hash(char *s, int n)
65 d1f529f4 2005-10-29 devnull uchar *p, *ep;
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;
72 d1f529f4 2005-10-29 devnull static void
73 d1f529f4 2005-10-29 devnull rehash(Hash *hh)
76 d1f529f4 2005-10-29 devnull Stringtab *s;
78 d1f529f4 2005-10-29 devnull if(hh->nstab == 0)
79 d1f529f4 2005-10-29 devnull hh->nstab = 1024;
81 d1f529f4 2005-10-29 devnull hh->nstab = hh->ntab*2;
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");
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;
95 d1f529f4 2005-10-29 devnull Stringtab*
96 d1f529f4 2005-10-29 devnull findstab(Hash *hh, char *str, int n, int create)
99 d1f529f4 2005-10-29 devnull Stringtab *tab, **l;
101 d1f529f4 2005-10-29 devnull if(hh->nstab == 0)
102 d1f529f4 2005-10-29 devnull rehash(hh);
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;
113 d1f529f4 2005-10-29 devnull if(!create)
114 d1f529f4 2005-10-29 devnull return nil;
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;
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;
134 d1f529f4 2005-10-29 devnull scmp(Stringtab *a, Stringtab *b)
136 d1f529f4 2005-10-29 devnull int n, x;
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 */
155 d1f529f4 2005-10-29 devnull Stringtab*
156 d1f529f4 2005-10-29 devnull merge(Stringtab *a, Stringtab *b)
158 d1f529f4 2005-10-29 devnull Stringtab *s, **l;
161 d1f529f4 2005-10-29 devnull while(a || b){
162 d1f529f4 2005-10-29 devnull if(scmp(a, b) < 0){
164 d1f529f4 2005-10-29 devnull l = &a->link;
165 d1f529f4 2005-10-29 devnull a = a->link;
168 d1f529f4 2005-10-29 devnull l = &b->link;
169 d1f529f4 2005-10-29 devnull b = b->link;
173 d1f529f4 2005-10-29 devnull return s;
176 d1f529f4 2005-10-29 devnull Stringtab*
177 d1f529f4 2005-10-29 devnull mergesort(Stringtab *s)
179 d1f529f4 2005-10-29 devnull Stringtab *a, *b;
180 d1f529f4 2005-10-29 devnull int delay;
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;
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;
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;
198 d1f529f4 2005-10-29 devnull b = a->link;
199 d1f529f4 2005-10-29 devnull a->link = nil;
201 d1f529f4 2005-10-29 devnull a = mergesort(s);
202 d1f529f4 2005-10-29 devnull b = mergesort(b);
204 d1f529f4 2005-10-29 devnull return merge(a, b);
207 d1f529f4 2005-10-29 devnull Stringtab*
208 d1f529f4 2005-10-29 devnull sortstab(Hash *hh)
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;
214 d1f529f4 2005-10-29 devnull return hh->all;
218 d1f529f4 2005-10-29 devnull Bwritehash(Biobuf *b, Hash *hh)
220 d1f529f4 2005-10-29 devnull Stringtab *s;
221 d1f529f4 2005-10-29 devnull int now;
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;
230 d1f529f4 2005-10-29 devnull * Entries that haven't been updated in thirty days get tossed.
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);
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;
243 d1f529f4 2005-10-29 devnull Breadhash(Biobuf *b, Hash *hh, int scale)
245 d1f529f4 2005-10-29 devnull char *s;
246 d1f529f4 2005-10-29 devnull char *t;
248 d1f529f4 2005-10-29 devnull int date;
249 d1f529f4 2005-10-29 devnull Stringtab *st;
251 d1f529f4 2005-10-29 devnull s = Brdstr(b, '\n', 1);
252 d1f529f4 2005-10-29 devnull if(s == nil)
254 d1f529f4 2005-10-29 devnull if(strcmp(s, "# hash table") != 0)
255 d1f529f4 2005-10-29 devnull sysfatal("bad hash table format");
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 == ' '){
270 d1f529f4 2005-10-29 devnull date = strtol(t, &t, 10);
272 d1f529f4 2005-10-29 devnull if(*t != 0)
273 d1f529f4 2005-10-29 devnull sysfatal("bad hash table format");
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;
283 d1f529f4 2005-10-29 devnull freehash(Hash *h)
285 d1f529f4 2005-10-29 devnull Stringtab *s, *next;
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);
291 d1f529f4 2005-10-29 devnull free(h->stab);
292 d1f529f4 2005-10-29 devnull free(h);
296 d1f529f4 2005-10-29 devnull Bopenlock(char *file, int mode)
299 d1f529f4 2005-10-29 devnull Biobuf *b;
300 d1f529f4 2005-10-29 devnull char err[ERRMAX];
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)
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)
309 d1f529f4 2005-10-29 devnull sleep(1000);
311 d1f529f4 2005-10-29 devnull return b;