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