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