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