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 }