![[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] / 42BSD / usr.lib / libdbm|
Return to dbm.c CVS log | Up to [CSRG BSD Unix] / 42BSD / usr.lib / libdbm |
1.1 root 1: #ifndef lint
2: static char sccsid[] = "@(#)dbm.c 4.1 (Berkeley) 6/27/83";
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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.