Commit | Line | Data |
---|---|---|
18e5fa7e BJ |
1 | #include "dbm.h" |
2 | #include <sys/types.h> | |
3 | #include <sys/stat.h> | |
4 | ||
5 | dbminit(file) | |
6 | char *file; | |
7 | { | |
8 | struct stat statb; | |
9 | ||
10 | strcpy(pagbuf, file); | |
11 | strcat(pagbuf, ".pag"); | |
12 | pagf = open(pagbuf, 2); | |
13 | ||
14 | strcpy(pagbuf, file); | |
15 | strcat(pagbuf, ".dir"); | |
16 | dirf = open(pagbuf, 2); | |
17 | if(pagf < 0 || dirf < 0) { | |
18 | printf("cannot open database %s\n", file); | |
19 | return(-1); | |
20 | } | |
21 | fstat(dirf, &statb); | |
22 | maxbno = statb.st_size*BYTESIZ-1; | |
23 | return(0); | |
24 | } | |
25 | ||
26 | long | |
27 | forder(key) | |
28 | datum key; | |
29 | { | |
30 | long hash; | |
31 | ||
32 | hash = calchash(key); | |
33 | for(hmask=0;; hmask=(hmask<<1)+1) { | |
34 | blkno = hash & hmask; | |
35 | bitno = blkno + hmask; | |
36 | if(getbit() == 0) | |
37 | break; | |
38 | } | |
39 | return(blkno); | |
40 | } | |
41 | ||
42 | datum | |
43 | fetch(key) | |
44 | datum key; | |
45 | { | |
46 | register i; | |
47 | datum item; | |
48 | ||
49 | dbm_access(calchash(key)); | |
50 | for(i=0;; i+=2) { | |
51 | item = makdatum(pagbuf, i); | |
52 | if(item.dptr == NULL) | |
53 | return(item); | |
54 | if(cmpdatum(key, item) == 0) { | |
55 | item = makdatum(pagbuf, i+1); | |
56 | if(item.dptr == NULL) | |
57 | printf("items not in pairs\n"); | |
58 | return(item); | |
59 | } | |
60 | } | |
61 | } | |
62 | ||
63 | delete(key) | |
64 | datum key; | |
65 | { | |
66 | register i; | |
67 | datum item; | |
68 | ||
69 | dbm_access(calchash(key)); | |
70 | for(i=0;; i+=2) { | |
71 | item = makdatum(pagbuf, i); | |
72 | if(item.dptr == NULL) | |
73 | return(-1); | |
74 | if(cmpdatum(key, item) == 0) { | |
75 | delitem(pagbuf, i); | |
76 | delitem(pagbuf, i); | |
77 | break; | |
78 | } | |
79 | } | |
80 | lseek(pagf, blkno*PBLKSIZ, 0); | |
81 | write(pagf, pagbuf, PBLKSIZ); | |
82 | return(0); | |
83 | } | |
84 | ||
85 | store(key, dat) | |
86 | datum key, dat; | |
87 | { | |
88 | register i; | |
89 | datum item; | |
90 | char ovfbuf[PBLKSIZ]; | |
91 | ||
92 | loop: | |
93 | dbm_access(calchash(key)); | |
94 | for(i=0;; i+=2) { | |
95 | item = makdatum(pagbuf, i); | |
96 | if(item.dptr == NULL) | |
97 | break; | |
98 | if(cmpdatum(key, item) == 0) { | |
99 | delitem(pagbuf, i); | |
100 | delitem(pagbuf, i); | |
101 | break; | |
102 | } | |
103 | } | |
104 | i = additem(pagbuf, key); | |
105 | if(i < 0) | |
106 | goto split; | |
107 | if(additem(pagbuf, dat) < 0) { | |
108 | delitem(pagbuf, i); | |
109 | goto split; | |
110 | } | |
111 | lseek(pagf, blkno*PBLKSIZ, 0); | |
112 | write(pagf, pagbuf, PBLKSIZ); | |
113 | return; | |
114 | ||
115 | split: | |
116 | if(key.dsize+dat.dsize+2*sizeof(short) >= PBLKSIZ) { | |
117 | printf("entry too big\n"); | |
118 | return; | |
119 | } | |
120 | clrbuf(ovfbuf, PBLKSIZ); | |
121 | for(i=0;;) { | |
122 | item = makdatum(pagbuf, i); | |
123 | if(item.dptr == NULL) | |
124 | break; | |
125 | if(calchash(item) & (hmask+1)) { | |
126 | additem(ovfbuf, item); | |
127 | delitem(pagbuf, i); | |
128 | item = makdatum(pagbuf, i); | |
129 | if(item.dptr == NULL) { | |
130 | printf("split not paired\n"); | |
131 | break; | |
132 | } | |
133 | additem(ovfbuf, item); | |
134 | delitem(pagbuf, i); | |
135 | continue; | |
136 | } | |
137 | i += 2; | |
138 | } | |
139 | lseek(pagf, blkno*PBLKSIZ, 0); | |
140 | write(pagf, pagbuf, PBLKSIZ); | |
141 | lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0); | |
142 | write(pagf, ovfbuf, PBLKSIZ); | |
143 | setbit(); | |
144 | goto loop; | |
145 | } | |
146 | ||
147 | datum | |
148 | firstkey() | |
149 | { | |
150 | return(firsthash(0L)); | |
151 | } | |
152 | ||
153 | datum | |
154 | nextkey(key) | |
155 | datum key; | |
156 | { | |
157 | register i; | |
158 | datum item, bitem; | |
159 | long hash; | |
160 | int f; | |
161 | ||
162 | hash = calchash(key); | |
163 | dbm_access(hash); | |
164 | f = 1; | |
165 | for(i=0;; i+=2) { | |
166 | item = makdatum(pagbuf, i); | |
167 | if(item.dptr == NULL) | |
168 | break; | |
169 | if(cmpdatum(key, item) <= 0) | |
170 | continue; | |
171 | if(f || cmpdatum(bitem, item) < 0) { | |
172 | bitem = item; | |
173 | f = 0; | |
174 | } | |
175 | } | |
176 | if(f == 0) | |
177 | return(bitem); | |
178 | hash = hashinc(hash); | |
179 | if(hash == 0) | |
180 | return(item); | |
181 | return(firsthash(hash)); | |
182 | } | |
183 | ||
184 | datum | |
185 | firsthash(hash) | |
186 | long hash; | |
187 | { | |
188 | register i; | |
189 | datum item, bitem; | |
190 | ||
191 | loop: | |
192 | dbm_access(hash); | |
193 | bitem = makdatum(pagbuf, 0); | |
194 | for(i=2;; i+=2) { | |
195 | item = makdatum(pagbuf, i); | |
196 | if(item.dptr == NULL) | |
197 | break; | |
198 | if(cmpdatum(bitem, item) < 0) | |
199 | bitem = item; | |
200 | } | |
201 | if(bitem.dptr != NULL) | |
202 | return(bitem); | |
203 | hash = hashinc(hash); | |
204 | if(hash == 0) | |
205 | return(item); | |
206 | goto loop; | |
207 | } | |
208 | ||
209 | dbm_access(hash) | |
210 | long hash; | |
211 | { | |
212 | static long oldb = -1; | |
213 | ||
214 | for(hmask=0;; hmask=(hmask<<1)+1) { | |
215 | blkno = hash & hmask; | |
216 | bitno = blkno + hmask; | |
217 | if(getbit() == 0) | |
218 | break; | |
219 | } | |
220 | if(blkno != oldb) { | |
221 | clrbuf(pagbuf, PBLKSIZ); | |
222 | lseek(pagf, blkno*PBLKSIZ, 0); | |
223 | read(pagf, pagbuf, PBLKSIZ); | |
224 | chkblk(pagbuf); | |
225 | oldb = blkno; | |
226 | } | |
227 | } | |
228 | ||
229 | getbit() | |
230 | { | |
231 | long bn; | |
232 | register b, i, n; | |
233 | static oldb = -1; | |
234 | ||
235 | if(bitno > maxbno) | |
236 | return(0); | |
237 | n = bitno % BYTESIZ; | |
238 | bn = bitno / BYTESIZ; | |
239 | i = bn % DBLKSIZ; | |
240 | b = bn / DBLKSIZ; | |
241 | if(b != oldb) { | |
242 | clrbuf(dirbuf, DBLKSIZ); | |
243 | lseek(dirf, (long)b*DBLKSIZ, 0); | |
244 | read(dirf, dirbuf, DBLKSIZ); | |
245 | oldb = b; | |
246 | } | |
247 | if(dirbuf[i] & (1<<n)) | |
248 | return(1); | |
249 | return(0); | |
250 | } | |
251 | ||
252 | setbit() | |
253 | { | |
254 | long bn; | |
255 | register i, n, b; | |
256 | ||
257 | if(bitno > maxbno) { | |
258 | maxbno = bitno; | |
259 | getbit(); | |
260 | } | |
261 | n = bitno % BYTESIZ; | |
262 | bn = bitno / BYTESIZ; | |
263 | i = bn % DBLKSIZ; | |
264 | b = bn / DBLKSIZ; | |
265 | dirbuf[i] |= 1<<n; | |
266 | lseek(dirf, (long)b*DBLKSIZ, 0); | |
267 | write(dirf, dirbuf, DBLKSIZ); | |
268 | } | |
269 | ||
270 | clrbuf(cp, n) | |
271 | register char *cp; | |
272 | register n; | |
273 | { | |
274 | ||
275 | do | |
276 | *cp++ = 0; | |
277 | while(--n); | |
278 | } | |
279 | ||
280 | datum | |
281 | makdatum(buf, n) | |
282 | char buf[PBLKSIZ]; | |
283 | { | |
284 | register short *sp; | |
285 | register t; | |
286 | datum item; | |
287 | ||
288 | sp = (short *)buf; | |
289 | if(n < 0 || n >= sp[0]) | |
290 | goto null; | |
291 | t = PBLKSIZ; | |
292 | if(n > 0) | |
293 | t = sp[n+1-1]; | |
294 | item.dptr = buf+sp[n+1]; | |
295 | item.dsize = t - sp[n+1]; | |
296 | return(item); | |
297 | ||
298 | null: | |
299 | item.dptr = NULL; | |
300 | item.dsize = 0; | |
301 | return(item); | |
302 | } | |
303 | ||
304 | cmpdatum(d1, d2) | |
305 | datum d1, d2; | |
306 | { | |
307 | register n; | |
308 | register char *p1, *p2; | |
309 | ||
310 | n = d1.dsize; | |
311 | if(n != d2.dsize) | |
312 | return(n - d2.dsize); | |
313 | if(n == 0) | |
314 | return(0); | |
315 | p1 = d1.dptr; | |
316 | p2 = d2.dptr; | |
317 | do | |
318 | if(*p1++ != *p2++) | |
319 | return(*--p1 - *--p2); | |
320 | while(--n); | |
321 | return(0); | |
322 | } | |
323 | ||
324 | int hitab[16] | |
325 | /* ken's | |
326 | { | |
327 | 055,043,036,054,063,014,004,005, | |
328 | 010,064,077,000,035,027,025,071, | |
329 | }; | |
330 | */ | |
331 | = { 61, 57, 53, 49, 45, 41, 37, 33, | |
332 | 29, 25, 21, 17, 13, 9, 5, 1, | |
333 | }; | |
334 | long hltab[64] | |
335 | = { | |
336 | 06100151277L,06106161736L,06452611562L,05001724107L, | |
337 | 02614772546L,04120731531L,04665262210L,07347467531L, | |
338 | 06735253126L,06042345173L,03072226605L,01464164730L, | |
339 | 03247435524L,07652510057L,01546775256L,05714532133L, | |
340 | 06173260402L,07517101630L,02431460343L,01743245566L, | |
341 | 00261675137L,02433103631L,03421772437L,04447707466L, | |
342 | 04435620103L,03757017115L,03641531772L,06767633246L, | |
343 | 02673230344L,00260612216L,04133454451L,00615531516L, | |
344 | 06137717526L,02574116560L,02304023373L,07061702261L, | |
345 | 05153031405L,05322056705L,07401116734L,06552375715L, | |
346 | 06165233473L,05311063631L,01212221723L,01052267235L, | |
347 | 06000615237L,01075222665L,06330216006L,04402355630L, | |
348 | 01451177262L,02000133436L,06025467062L,07121076461L, | |
349 | 03123433522L,01010635225L,01716177066L,05161746527L, | |
350 | 01736635071L,06243505026L,03637211610L,01756474365L, | |
351 | 04723077174L,03642763134L,05750130273L,03655541561L, | |
352 | }; | |
353 | ||
354 | long | |
355 | hashinc(hash) | |
356 | long hash; | |
357 | { | |
358 | long bit; | |
359 | ||
360 | hash &= hmask; | |
361 | bit = hmask+1; | |
362 | for(;;) { | |
363 | bit >>= 1; | |
364 | if(bit == 0) | |
365 | return(0L); | |
366 | if((hash&bit) == 0) | |
367 | return(hash|bit); | |
368 | hash &= ~bit; | |
369 | } | |
370 | } | |
371 | ||
372 | long | |
373 | calchash(item) | |
374 | datum item; | |
375 | { | |
376 | register i, j, f; | |
377 | long hashl; | |
378 | int hashi; | |
379 | ||
380 | hashl = 0; | |
381 | hashi = 0; | |
382 | for(i=0; i<item.dsize; i++) { | |
383 | f = item.dptr[i]; | |
384 | for(j=0; j<BYTESIZ; j+=4) { | |
385 | hashi += hitab[f&017]; | |
386 | hashl += hltab[hashi&63]; | |
387 | f >>= 4; | |
388 | } | |
389 | } | |
390 | return(hashl); | |
391 | } | |
392 | ||
393 | delitem(buf, n) | |
394 | char buf[PBLKSIZ]; | |
395 | { | |
396 | register short *sp; | |
397 | register i1, i2, i3; | |
398 | ||
399 | sp = (short *)buf; | |
400 | if(n < 0 || n >= sp[0]) | |
401 | goto bad; | |
402 | i1 = sp[n+1]; | |
403 | i2 = PBLKSIZ; | |
404 | if(n > 0) | |
405 | i2 = sp[n+1-1]; | |
406 | i3 = sp[sp[0]+1-1]; | |
407 | if(i2 > i1) | |
408 | while(i1 > i3) { | |
409 | i1--; | |
410 | i2--; | |
411 | buf[i2] = buf[i1]; | |
412 | buf[i1] = 0; | |
413 | } | |
414 | i2 -= i1; | |
415 | for(i1=n+1; i1<sp[0]; i1++) | |
416 | sp[i1+1-1] = sp[i1+1] + i2; | |
417 | sp[0]--; | |
418 | sp[sp[0]+1] = 0; | |
419 | return; | |
420 | ||
421 | bad: | |
422 | printf("bad delitem\n"); | |
423 | abort(); | |
424 | } | |
425 | ||
426 | additem(buf, item) | |
427 | char buf[PBLKSIZ]; | |
428 | datum item; | |
429 | { | |
430 | register short *sp; | |
431 | register i1, i2; | |
432 | ||
433 | sp = (short *)buf; | |
434 | i1 = PBLKSIZ; | |
435 | if(sp[0] > 0) | |
436 | i1 = sp[sp[0]+1-1]; | |
437 | i1 -= item.dsize; | |
438 | i2 = (sp[0]+2) * sizeof(short); | |
439 | if(i1 <= i2) | |
440 | return(-1); | |
441 | sp[sp[0]+1] = i1; | |
442 | for(i2=0; i2<item.dsize; i2++) { | |
443 | buf[i1] = item.dptr[i2]; | |
444 | i1++; | |
445 | } | |
446 | sp[0]++; | |
447 | return(sp[0]-1); | |
448 | } | |
449 | ||
450 | chkblk(buf) | |
451 | char buf[PBLKSIZ]; | |
452 | { | |
453 | register short *sp; | |
454 | register t, i; | |
455 | ||
456 | sp = (short *)buf; | |
457 | t = PBLKSIZ; | |
458 | for(i=0; i<sp[0]; i++) { | |
459 | if(sp[i+1] > t) | |
460 | goto bad; | |
461 | t = sp[i+1]; | |
462 | } | |
463 | if(t < (sp[0]+1)*sizeof(short)) | |
464 | goto bad; | |
465 | return; | |
466 | ||
467 | bad: | |
468 | printf("bad block\n"); | |
469 | abort(); | |
470 | clrbuf(buf, PBLKSIZ); | |
471 | } |