![[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] / 3BSD / lib / libdbm|
Return to dbm.c CVS log | Up to [CSRG BSD Unix] / 3BSD / lib / libdbm |
1.1 root 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.