tndbhash.c - plan9port - [fork] Plan 9 from user space
HTML git clone git://src.adamsgaard.dk/plan9port
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
tndbhash.c (4975B)
---
1 #include <u.h>
2 #include <libc.h>
3 #include <bio.h>
4 #include "ndb.h"
5 #include "ndbhf.h"
6
7 enum {
8 Dptr, /* pointer to database file */
9 Cptr, /* pointer to first chain entry */
10 Cptr1 /* pointer to second chain entry */
11 };
12
13 /*
14 * generate a hash value for an ascii string (val) given
15 * a hash table length (hlen)
16 */
17 ulong
18 ndbhash(char *vp, int hlen)
19 {
20 ulong hash;
21 uchar *val = (uchar*)vp;
22
23 for(hash = 0; *val; val++)
24 hash = (hash*13) + *val-'a';
25 return hash % hlen;
26 }
27
28 /*
29 * read a hash file with buffering
30 */
31 static uchar*
32 hfread(Ndbhf *hf, long off, int len)
33 {
34 if(off < hf->off || off + len > hf->off + hf->len){
35 if(seek(hf->fd, off, 0) < 0
36 || (hf->len = read(hf->fd, hf->buf, sizeof(hf->buf))) < len){
37 hf->off = -1;
38 return 0;
39 }
40 hf->off = off;
41 }
42 return &hf->buf[off-hf->off];
43 }
44
45 /*
46 * return an opened hash file if one exists for the
47 * attribute and if it is current vis-a-vis the data
48 * base file
49 */
50 static Ndbhf*
51 hfopen(Ndb *db, char *attr)
52 {
53 Ndbhf *hf;
54 char buf[sizeof(hf->attr)+sizeof(db->file)+2];
55 uchar *p;
56 Dir *d;
57
58 /* try opening the data base if it's closed */
59 if(db->mtime==0 && ndbreopen(db) < 0)
60 return 0;
61
62 /* if the database has changed, throw out hash files and reopen db */
63 if((d = dirfstat(Bfildes(&db->b))) == nil || db->qid.path != d->qid.path
64 || db->qid.vers != d->qid.vers){
65 if(ndbreopen(db) < 0){
66 free(d);
67 return 0;
68 }
69 }
70 free(d);
71
72 if(db->nohash)
73 return 0;
74
75 /* see if a hash file exists for this attribute */
76 for(hf = db->hf; hf; hf= hf->next){
77 if(strcmp(hf->attr, attr) == 0)
78 return hf;
79 }
80
81 /* create a new one */
82 hf = (Ndbhf*)malloc(sizeof(Ndbhf));
83 if(hf == 0)
84 return 0;
85 memset(hf, 0, sizeof(Ndbhf));
86
87 /* compare it to the database file */
88 strncpy(hf->attr, attr, sizeof(hf->attr)-1);
89 sprint(buf, "%s.%s", db->file, hf->attr);
90 hf->fd = open(buf, OREAD);
91 if(hf->fd >= 0){
92 hf->len = 0;
93 hf->off = 0;
94 p = hfread(hf, 0, 2*NDBULLEN);
95 if(p){
96 hf->dbmtime = NDBGETUL(p);
97 hf->hlen = NDBGETUL(p+NDBULLEN);
98 if(hf->dbmtime == db->mtime){
99 hf->next = db->hf;
100 db->hf = hf;
101 return hf;
102 }
103 }
104 close(hf->fd);
105 }
106
107 free(hf);
108 return 0;
109 }
110
111 /*
112 * return the first matching entry
113 */
114 Ndbtuple*
115 ndbsearch(Ndb *db, Ndbs *s, char *attr, char *val)
116 {
117 uchar *p;
118 Ndbtuple *t;
119 Ndbhf *hf;
120
121 hf = hfopen(db, attr);
122
123 memset(s, 0, sizeof(*s));
124 if(_ndbcachesearch(db, s, attr, val, &t) == 0){
125 /* found in cache */
126 if(t != nil)
127 return t; /* answer from this file */
128 if(db->next == nil)
129 return nil;
130 return ndbsearch(db->next, s, attr, val);
131 }
132
133 s->db = db;
134 s->hf = hf;
135 if(s->hf){
136 s->ptr = ndbhash(val, s->hf->hlen)*NDBPLEN;
137 p = hfread(s->hf, s->ptr+NDBHLEN, NDBPLEN);
138 if(p == 0)
139 return _ndbcacheadd(db, s, attr, val, nil);
140 s->ptr = NDBGETP(p);
141 s->type = Cptr1;
142 } else if(db->length > 128*1024){
143 print("Missing or out of date hash file %s.%s.\n", db->file, attr);
144 /* syslog(0, "ndb", "Missing or out of date hash file %s.%s.", db->file, attr); */
145
146 /* advance search to next db file */
147 s->ptr = NDBNAP;
148 _ndbcacheadd(db, s, attr, val, nil);
149 if(db->next == 0)
150 return nil;
151 return ndbsearch(db->next, s, attr, val);
152 } else {
153 s->ptr = 0;
154 s->type = Dptr;
155 }
156 t = ndbsnext(s, attr, val);
157 _ndbcacheadd(db, s, attr, val, (t != nil && s->db == db)?t:nil);
158 setmalloctag(t, getcallerpc(&db));
159 return t;
160 }
161
162 static Ndbtuple*
163 match(Ndbtuple *t, char *attr, char *val)
164 {
165 Ndbtuple *nt;
166
167 for(nt = t; nt; nt = nt->entry)
168 if(strcmp(attr, nt->attr) == 0
169 && strcmp(val, nt->val) == 0)
170 return nt;
171 return 0;
172 }
173
174 /*
175 * return the next matching entry in the hash chain
176 */
177 Ndbtuple*
178 ndbsnext(Ndbs *s, char *attr, char *val)
179 {
180 Ndbtuple *t;
181 Ndb *db;
182 uchar *p;
183
184 db = s->db;
185 if(s->ptr == NDBNAP)
186 goto nextfile;
187
188 for(;;){
189 if(s->type == Dptr){
190 if(Bseek(&db->b, s->ptr, 0) < 0)
191 break;
192 t = ndbparse(db);
193 s->ptr = Boffset(&db->b);
194 if(t == 0)
195 break;
196 if(s->t = match(t, attr, val))
197 return t;
198 ndbfree(t);
199 } else if(s->type == Cptr){
200 if(Bseek(&db->b, s->ptr, 0) < 0)
201 break;
202 s->ptr = s->ptr1;
203 s->type = Cptr1;
204 t = ndbparse(db);
205 if(t == 0)
206 break;
207 if(s->t = match(t, attr, val))
208 return t;
209 ndbfree(t);
210 } else if(s->type == Cptr1){
211 if(s->ptr & NDBCHAIN){ /* hash chain continuation */
212 s->ptr &= ~NDBCHAIN;
213 p = hfread(s->hf, s->ptr+NDBHLEN, 2*NDBPLEN);
214 if(p == 0)
215 break;
216 s->ptr = NDBGETP(p);
217 s->ptr1 = NDBGETP(p+NDBPLEN);
218 s->type = Cptr;
219 } else { /* end of hash chain */
220 if(Bseek(&db->b, s->ptr, 0) < 0)
221 break;
222 s->ptr = NDBNAP;
223 t = ndbparse(db);
224 if(t == 0)
225 break;
226 if(s->t = match(t, attr, val)){
227 setmalloctag(t, getcallerpc(&s));
228 return t;
229 }
230 ndbfree(t);
231 break;
232 }
233 }
234 }
235
236 nextfile:
237
238 /* nothing left to search? */
239 s->ptr = NDBNAP;
240 if(db->next == 0)
241 return 0;
242
243 /* advance search to next db file */
244 t = ndbsearch(db->next, s, attr, val);
245 setmalloctag(t, getcallerpc(&s));
246 return t;
247 }