Add ndblib and iplib
[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 <libip.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         struct ndbhf *hf;
67         char buf[sizeof(hf->attr)+sizeof(db->file)+2];
68         uint8_t *p;
69         struct dir *d;
70
71         /* try opening the data base if it's closed */
72         if(db->mtime==0 && ndbreopen(db) < 0)
73                 return 0;
74
75         /* if the database has changed, throw out hash files and reopen db */
76 #if 0
77         if((d = dirfstat(Bfildes(&db->b))) == NULL || db->qid.path != d->qid.path
78         || db->qid.vers != d->qid.vers){
79 #else
80         if (1){
81 #endif
82                 if(ndbreopen(db) < 0){
83                         free(d);
84                         return 0;
85                 }
86         }
87         free(d);
88
89         if(db->nohash)
90                 return 0;
91
92         /* see if a hash file exists for this attribute */
93         for(hf = db->hf; hf; hf= hf->next){
94                 if(strcmp(hf->attr, attr) == 0)
95                         return hf;
96         }
97
98         /* create a new one */
99         hf = (struct ndbhf*)calloc(sizeof(struct ndbhf), 1);
100         if(hf == 0)
101                 return 0;
102         memset(hf, 0, sizeof(struct ndbhf));
103
104         /* compare it to the database file */
105         strncpy(hf->attr, attr, sizeof(hf->attr)-1);
106         sprintf(buf, "%s.%s", db->file, hf->attr);
107         hf->fd = open(buf, O_RDONLY);
108         if(hf->fd >= 0){
109                 hf->len = 0;
110                 hf->off = 0;
111                 p = hfread(hf, 0, 2*NDBULLEN);
112                 if(p){
113                         hf->dbmtime = NDBGETUL(p);
114                         hf->hlen = NDBGETUL(p+NDBULLEN);
115                         if(hf->dbmtime == db->mtime){
116                                 hf->next = db->hf;
117                                 db->hf = hf;
118                                 return hf;
119                         }
120                 }
121                 close(hf->fd);
122         }
123
124         free(hf);
125         return 0;
126 }
127
128 /*
129  *  return the first matching entry
130  */
131 struct ndbtuple*
132 ndbsearch(struct ndb *db, struct ndbs *s, char *attr, char *val)
133 {
134         uint8_t *p;
135         struct ndbtuple *t;
136         struct ndbhf *hf;
137
138         hf = hfopen(db, attr);
139
140         memset(s, 0, sizeof(*s));
141         if(_ndbcachesearch(db, s, attr, val, &t) == 0){
142                 /* found in cache */
143                 if(t != NULL){
144                         ndbsetmalloctag(t, getcallerpc(&db));
145                         return t;       /* answer from this file */
146                 }
147                 if(db->next == NULL)
148                         return NULL;
149                 t = ndbsearch(db->next, s, attr, val);
150                 ndbsetmalloctag(t, getcallerpc(&db));
151                 return t;
152         }
153
154         s->db = db;
155         s->hf = hf;
156         if(s->hf){
157                 s->ptr = ndbhash(val, s->hf->hlen)*NDBPLEN;
158                 p = hfread(s->hf, s->ptr+NDBHLEN, NDBPLEN);
159                 if(p == 0){
160                         t = _ndbcacheadd(db, s, attr, val, NULL);
161                         ndbsetmalloctag(t, getcallerpc(&db));
162                         return t;
163                 }
164                 s->ptr = NDBGETP(p);
165                 s->type = Cptr1;
166         } else if(db->length > 128*1024){
167                 printf("Missing or out of date hash file %s.%s.\n", db->file, attr);
168                 //syslog(0, "ndb", "Missing or out of date hash file %s.%s.", db->file, attr);
169
170                 /* advance search to next db file */
171                 s->ptr = NDBNAP;
172                 _ndbcacheadd(db, s, attr, val, NULL);
173                 if(db->next == 0)
174                         return NULL;
175                 t = ndbsearch(db->next, s, attr, val);
176                 ndbsetmalloctag(t, getcallerpc(&db));
177                 return t;
178         } else {
179                 s->ptr = 0;
180                 s->type = Dptr;
181         }
182         t = ndbsnext(s, attr, val);
183         _ndbcacheadd(db, s, attr, val, (t != NULL && s->db == db)?t:NULL);
184         ndbsetmalloctag(t, getcallerpc(&db));
185         return t;
186 }
187
188 static struct ndbtuple*
189 match(struct ndbtuple *t, char *attr, char *val)
190 {
191         struct ndbtuple *nt;
192
193         for(nt = t; nt; nt = nt->entry)
194                 if(strcmp(attr, nt->attr) == 0
195                 && strcmp(val, nt->val) == 0)
196                         return nt;
197         return 0;
198 }
199
200 /*
201  *  return the next matching entry in the hash chain
202  */
203 struct ndbtuple*
204 ndbsnext(struct ndbs *s, char *attr, char *val)
205 {
206         struct ndbtuple *t;
207         struct ndb *db;
208         uint8_t *p;
209
210         db = s->db;
211         if(s->ptr == NDBNAP)
212                 goto nextfile;
213
214         for(;;){
215                 if(s->type == Dptr){
216                         if(fseek(db->b, s->ptr, 0) < 0)
217                                 break;
218                         t = ndbparse(db);
219                         s->ptr = ftell(db->b);
220                         if(t == 0)
221                                 break;
222                         if(s->t = match(t, attr, val)){
223                                 ndbsetmalloctag(t, getcallerpc(&s));
224                                 return t;
225                         }
226                         ndbfree(t);
227                 } else if(s->type == Cptr){
228                         if(fseek(db->b, s->ptr, 0) < 0)
229                                 break; 
230                         s->ptr = s->ptr1;
231                         s->type = Cptr1;
232                         t = ndbparse(db);
233                         if(t == 0)
234                                 break;
235                         if(s->t = match(t, attr, val)){
236                                 ndbsetmalloctag(t, getcallerpc(&s));
237                                 return t;
238                         }
239                         ndbfree(t);
240                 } else if(s->type == Cptr1){
241                         if(s->ptr & NDBCHAIN){  /* hash chain continuation */
242                                 s->ptr &= ~NDBCHAIN;
243                                 p = hfread(s->hf, s->ptr+NDBHLEN, 2*NDBPLEN);
244                                 if(p == 0)
245                                         break;
246                                 s->ptr = NDBGETP(p);
247                                 s->ptr1 = NDBGETP(p+NDBPLEN);
248                                 s->type = Cptr;
249                         } else {                /* end of hash chain */
250                                 if(fseek(db->b, s->ptr, 0) < 0)
251                                         break; 
252                                 s->ptr = NDBNAP;
253                                 t = ndbparse(db);
254                                 if(t == 0)
255                                         break;
256                                 if(s->t = match(t, attr, val)){
257                                         ndbsetmalloctag(t, getcallerpc(&s));
258                                         return t;
259                                 }
260                                 ndbfree(t);
261                                 break;
262                         }
263                 }
264         }
265
266 nextfile:
267
268         /* nothing left to search? */
269         s->ptr = NDBNAP;
270         if(db->next == 0)
271                 return 0;
272
273         /* advance search to next db file */
274         t = ndbsearch(db->next, s, attr, val);
275         ndbsetmalloctag(t, getcallerpc(&s));
276         return t;
277 }