Fixes stat() #include
[akaros.git] / user / ndblib / ndbhash.c
1 /* 
2  * This file is part of the UCB release of Plan 9. It is subject to the license
3  * terms in the LICENSE file found in the top-level directory of this
4  * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
5  * part of the UCB release of Plan 9, including this file, may be copied,
6  * modified, propagated, or distributed except according to the terms contained
7  * in the LICENSE file.
8  */
9 #include <stdlib.h>
10
11 #include <stdio.h>
12 #include <parlib.h>
13 #include <unistd.h>
14 #include <signal.h>
15 #include <fcntl.h>
16 #include <iplib.h>
17 #include <ndb.h>
18 #include <ndbhf.h>
19
20 enum {
21         Dptr,   /* pointer to database file */
22         Cptr,   /* pointer to first chain entry */
23         Cptr1,  /* pointer to second chain entry */
24 };
25
26 /*
27  *  generate a hash value for an ascii string (val) given
28  *  a hash table length (hlen)
29  */
30 uint32_t
31 ndbhash(char *vp, int hlen)
32 {
33         uint32_t hash;
34         uint8_t *val = (uint8_t*)vp;
35
36         for(hash = 0; *val; val++)
37                 hash = (hash*13) + *val-'a';
38         return hash % hlen;
39 }
40
41 /*
42  *  read a hash file with buffering
43  */
44 static uint8_t*
45 hfread(struct ndbhf *hf, long off, int len)
46 {
47         if(off < hf->off || off + len > hf->off + hf->len){
48                 if(lseek(hf->fd, off, 0) < 0
49                 || (hf->len = read(hf->fd, hf->buf, sizeof(hf->buf))) < len){
50                         hf->off = -1;
51                         return 0;
52                 }
53                 hf->off = off;
54         }
55         return &hf->buf[off-hf->off];
56 }
57
58 /*
59  *  return an opened hash file if one exists for the
60  *  attribute and if it is current vis-a-vis the data
61  *  base file
62  */
63 static struct ndbhf*
64 hfopen(struct ndb *db, char *attr)
65 {
66         static int beenhere = 0;
67         struct ndbhf *hf;
68         char buf[sizeof(hf->attr)+sizeof(db->file)+2];
69         uint8_t *p;
70         struct dir *d;
71
72         /* try opening the data base if it's closed */
73         if(db->mtime==0 && ndbreopen(db) < 0)
74                 return 0;
75
76         /* if the database has changed, throw out hash files and reopen db */
77 #if 0
78         if((d = dirfstat(Bfildes(&db->b))) == NULL || db->qid.path != d->qid.path
79         || db->qid.vers != d->qid.vers){
80 #else
81         if (! beenhere){
82 #endif
83                 if(ndbreopen(db) < 0){
84                         free(d);
85                         return 0;
86                 }
87                 beenhere = 1;
88                 db->mtime = 1;
89         }
90         free(d);
91
92         if(db->nohash)
93                 return 0;
94
95         /* see if a hash file exists for this attribute */
96         for(hf = db->hf; hf; hf= hf->next){
97                 if(strcmp(hf->attr, attr) == 0)
98                         return hf;
99         }
100
101         /* create a new one */
102         hf = (struct ndbhf*)calloc(sizeof(struct ndbhf), 1);
103         if(hf == 0)
104                 return 0;
105         memset(hf, 0, sizeof(struct ndbhf));
106
107         /* compare it to the database file */
108         strncpy(hf->attr, attr, sizeof(hf->attr)-1);
109         sprintf(buf, "%s.%s", db->file, hf->attr);
110         hf->fd = open(buf, O_RDONLY);
111         if(hf->fd >= 0){
112                 hf->len = 0;
113                 hf->off = 0;
114                 p = hfread(hf, 0, 2*NDBULLEN);
115                 if(p){
116                         hf->dbmtime = NDBGETUL(p);
117                         hf->hlen = NDBGETUL(p+NDBULLEN);
118                         if(hf->dbmtime == db->mtime){
119                                 hf->next = db->hf;
120                                 db->hf = hf;
121                                 return hf;
122                         }
123                 }
124                 close(hf->fd);
125         }
126
127         free(hf);
128         return 0;
129 }
130
131 /*
132  *  return the first matching entry
133  */
134 struct ndbtuple*
135 ndbsearch(struct ndb *db, struct ndbs *s, char *attr, char *val)
136 {
137         uint8_t *p;
138         struct ndbtuple *t;
139         struct ndbhf *hf;
140         hf = hfopen(db, attr);
141
142         memset(s, 0, sizeof(*s));
143         if(_ndbcachesearch(db, s, attr, val, &t) == 0){
144                 /* found in cache */
145                 if(t != NULL){
146                         ndbsetmalloctag(t, getcallerpc(&db));
147                         return t;       /* answer from this file */
148                 }
149                 if(db->next == NULL)
150                         return NULL;
151                 t = ndbsearch(db->next, s, attr, val);
152                 ndbsetmalloctag(t, getcallerpc(&db));
153                 return t;
154         }
155
156         s->db = db;
157         s->hf = hf;
158         if(s->hf){
159                 s->ptr = ndbhash(val, s->hf->hlen)*NDBPLEN;
160                 p = hfread(s->hf, s->ptr+NDBHLEN, NDBPLEN);
161                 if(p == 0){
162                         t = _ndbcacheadd(db, s, attr, val, NULL);
163                         ndbsetmalloctag(t, getcallerpc(&db));
164                         return t;
165                 }
166                 s->ptr = NDBGETP(p);
167                 s->type = Cptr1;
168         } else if(db->length > 128*1024){
169                 printf("Missing or out of date hash file %s.%s.\n", db->file, attr);
170                 //syslog(0, "ndb", "Missing or out of date hash file %s.%s.", db->file, attr);
171
172                 /* advance search to next db file */
173                 s->ptr = NDBNAP;
174                 _ndbcacheadd(db, s, attr, val, NULL);
175                 if(db->next == 0)
176                         return NULL;
177                 t = ndbsearch(db->next, s, attr, val);
178                 ndbsetmalloctag(t, getcallerpc(&db));
179                 return t;
180         } else {
181                 s->ptr = 0;
182                 s->type = Dptr;
183         }
184         t = ndbsnext(s, attr, val);
185         _ndbcacheadd(db, s, attr, val, (t != NULL && s->db == db)?t:NULL);
186         ndbsetmalloctag(t, getcallerpc(&db));
187         return t;
188 }
189
190 static struct ndbtuple*
191 match(struct ndbtuple *t, char *attr, char *val)
192 {
193         struct ndbtuple *nt;
194
195         for(nt = t; nt; nt = nt->entry)
196                 if(strcmp(attr, nt->attr) == 0
197                 && strcmp(val, nt->val) == 0)
198                         return nt;
199         return 0;
200 }
201
202 /*
203  *  return the next matching entry in the hash chain
204  */
205 struct ndbtuple*
206 ndbsnext(struct ndbs *s, char *attr, char *val)
207 {
208         struct ndbtuple *t;
209         struct ndb *db;
210         uint8_t *p;
211
212         db = s->db;
213         if(s->ptr == NDBNAP)
214                 goto nextfile;
215
216         for(;;){
217                 if(s->type == Dptr){
218                         if(fseek(db->b, s->ptr, 0) < 0)
219                                 break;
220                         t = ndbparse(db);
221                         s->ptr = ftell(db->b);
222                         if(t == 0)
223                                 break;
224                         if(s->t = match(t, attr, val)){
225                                 ndbsetmalloctag(t, getcallerpc(&s));
226                                 return t;
227                         }
228                         ndbfree(t);
229                 } else if(s->type == Cptr){
230                         if(fseek(db->b, s->ptr, 0) < 0)
231                                 break; 
232                         s->ptr = s->ptr1;
233                         s->type = Cptr1;
234                         t = ndbparse(db);
235                         if(t == 0)
236                                 break;
237                         if(s->t = match(t, attr, val)){
238                                 ndbsetmalloctag(t, getcallerpc(&s));
239                                 return t;
240                         }
241                         ndbfree(t);
242                 } else if(s->type == Cptr1){
243                         if(s->ptr & NDBCHAIN){  /* hash chain continuation */
244                                 s->ptr &= ~NDBCHAIN;
245                                 p = hfread(s->hf, s->ptr+NDBHLEN, 2*NDBPLEN);
246                                 if(p == 0)
247                                         break;
248                                 s->ptr = NDBGETP(p);
249                                 s->ptr1 = NDBGETP(p+NDBPLEN);
250                                 s->type = Cptr;
251                         } else {                /* end of hash chain */
252                                 if(fseek(db->b, s->ptr, 0) < 0)
253                                         break; 
254                                 s->ptr = NDBNAP;
255                                 t = ndbparse(db);
256                                 if(t == 0)
257                                         break;
258                                 if(s->t = match(t, attr, val)){
259                                         ndbsetmalloctag(t, getcallerpc(&s));
260                                         return t;
261                                 }
262                                 ndbfree(t);
263                                 break;
264                         }
265                 }
266         }
267
268 nextfile:
269
270         /* nothing left to search? */
271         s->ptr = NDBNAP;
272         if(db->next == 0)
273                 return 0;
274
275         /* advance search to next db file */
276         t = ndbsearch(db->next, s, attr, val);
277         ndbsetmalloctag(t, getcallerpc(&s));
278         return t;
279 }