![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dbm.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / old / libdbm|
Return to dbm.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / old / libdbm |
1.1 root 1: #ifndef lint
2: static char sccsid[] = "@(#)dbm.c 4.5 (Berkeley) 6/19/85";
3: #endif
4:
5: #include "dbm.h"
6: #undef NULL
7: #include <sys/types.h>
8: #undef setbit
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) {
33: printf("dbm: %s: cannot open database\n", file);
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)
72: printf("dbm: items not in pairs\n");
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:
135: if(key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) {
136: printf("dbm: entry too big\n");
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) {
149: printf("dbm: split not paired\n");
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:
443: printf("dbm: bad delitem\n");
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:
489: printf("dbm: bad block\n");
490: abort();
491: clrbuf(buf, PBLKSIZ);
492: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.