![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ndbm.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / lib / libc / gen|
Return to ndbm.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / lib / libc / gen |
1.1 root 1: /*
2: * Copyright (c) 1983 Regents of the University of California.
3: * All rights reserved. The Berkeley software License Agreement
4: * specifies the terms and conditions for redistribution.
5: */
6:
7: #if defined(LIBC_SCCS) && !defined(lint)
8: static char sccsid[] = "@(#)ndbm.c 5.4 (Berkeley) 9/4/87";
9: #endif LIBC_SCCS and not lint
10:
11: #include <sys/types.h>
12: #include <sys/stat.h>
13: #include <sys/file.h>
14: #include <stdio.h>
15: #include <errno.h>
16: #include <ndbm.h>
17:
18: #define BYTESIZ 8
19: #undef setbit
20:
21: static datum makdatum();
22: static long hashinc();
23: static long dcalchash();
24: extern int errno;
25:
26: DBM *
27: dbm_open(file, flags, mode)
28: char *file;
29: int flags, mode;
30: {
31: struct stat statb;
32: register DBM *db;
33:
34: if ((db = (DBM *)malloc(sizeof *db)) == 0) {
35: errno = ENOMEM;
36: return ((DBM *)0);
37: }
38: db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
39: if ((flags & 03) == O_WRONLY)
40: flags = (flags & ~03) | O_RDWR;
41: strcpy(db->dbm_pagbuf, file);
42: strcat(db->dbm_pagbuf, ".pag");
43: db->dbm_pagf = open(db->dbm_pagbuf, flags, mode);
44: if (db->dbm_pagf < 0)
45: goto bad;
46: strcpy(db->dbm_pagbuf, file);
47: strcat(db->dbm_pagbuf, ".dir");
48: db->dbm_dirf = open(db->dbm_pagbuf, flags, mode);
49: if (db->dbm_dirf < 0)
50: goto bad1;
51: fstat(db->dbm_dirf, &statb);
52: db->dbm_maxbno = statb.st_size*BYTESIZ-1;
53: db->dbm_pagbno = db->dbm_dirbno = -1;
54: return (db);
55: bad1:
56: (void) close(db->dbm_pagf);
57: bad:
58: free((char *)db);
59: return ((DBM *)0);
60: }
61:
62: void
63: dbm_close(db)
64: DBM *db;
65: {
66:
67: (void) close(db->dbm_dirf);
68: (void) close(db->dbm_pagf);
69: free((char *)db);
70: }
71:
72: long
73: dbm_forder(db, key)
74: register DBM *db;
75: datum key;
76: {
77: long hash;
78:
79: hash = dcalchash(key);
80: for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
81: db->dbm_blkno = hash & db->dbm_hmask;
82: db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
83: if (getbit(db) == 0)
84: break;
85: }
86: return (db->dbm_blkno);
87: }
88:
89: datum
90: dbm_fetch(db, key)
91: register DBM *db;
92: datum key;
93: {
94: register i;
95: datum item;
96:
97: if (dbm_error(db))
98: goto err;
99: dbm_access(db, dcalchash(key));
100: if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
101: item = makdatum(db->dbm_pagbuf, i+1);
102: if (item.dptr != NULL)
103: return (item);
104: }
105: err:
106: item.dptr = NULL;
107: item.dsize = 0;
108: return (item);
109: }
110:
111: dbm_delete(db, key)
112: register DBM *db;
113: datum key;
114: {
115: register i;
116: datum item;
117:
118: if (dbm_error(db))
119: return (-1);
120: if (dbm_rdonly(db)) {
121: errno = EPERM;
122: return (-1);
123: }
124: dbm_access(db, dcalchash(key));
125: if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
126: return (-1);
127: if (!delitem(db->dbm_pagbuf, i))
128: goto err;
129: db->dbm_pagbno = db->dbm_blkno;
130: (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
131: if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
132: err:
133: db->dbm_flags |= _DBM_IOERR;
134: return (-1);
135: }
136: return (0);
137: }
138:
139: dbm_store(db, key, dat, replace)
140: register DBM *db;
141: datum key, dat;
142: int replace;
143: {
144: register i;
145: datum item, item1;
146: char ovfbuf[PBLKSIZ];
147:
148: if (dbm_error(db))
149: return (-1);
150: if (dbm_rdonly(db)) {
151: errno = EPERM;
152: return (-1);
153: }
154: loop:
155: dbm_access(db, dcalchash(key));
156: if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
157: if (!replace)
158: return (1);
159: if (!delitem(db->dbm_pagbuf, i)) {
160: db->dbm_flags |= _DBM_IOERR;
161: return (-1);
162: }
163: }
164: if (!additem(db->dbm_pagbuf, key, dat))
165: goto split;
166: db->dbm_pagbno = db->dbm_blkno;
167: (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
168: if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
169: db->dbm_flags |= _DBM_IOERR;
170: return (-1);
171: }
172: return (0);
173:
174: split:
175: if (key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) {
176: db->dbm_flags |= _DBM_IOERR;
177: errno = ENOSPC;
178: return (-1);
179: }
180: bzero(ovfbuf, PBLKSIZ);
181: for (i=0;;) {
182: item = makdatum(db->dbm_pagbuf, i);
183: if (item.dptr == NULL)
184: break;
185: if (dcalchash(item) & (db->dbm_hmask+1)) {
186: item1 = makdatum(db->dbm_pagbuf, i+1);
187: if (item1.dptr == NULL) {
188: fprintf(stderr, "ndbm: split not paired\n");
189: db->dbm_flags |= _DBM_IOERR;
190: break;
191: }
192: if (!additem(ovfbuf, item, item1) ||
193: !delitem(db->dbm_pagbuf, i)) {
194: db->dbm_flags |= _DBM_IOERR;
195: return (-1);
196: }
197: continue;
198: }
199: i += 2;
200: }
201: db->dbm_pagbno = db->dbm_blkno;
202: (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
203: if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
204: db->dbm_flags |= _DBM_IOERR;
205: return (-1);
206: }
207: (void) lseek(db->dbm_pagf, (db->dbm_blkno+db->dbm_hmask+1)*PBLKSIZ, L_SET);
208: if (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ) {
209: db->dbm_flags |= _DBM_IOERR;
210: return (-1);
211: }
212: setbit(db);
213: goto loop;
214: }
215:
216: datum
217: dbm_firstkey(db)
218: DBM *db;
219: {
220:
221: db->dbm_blkptr = 0L;
222: db->dbm_keyptr = 0;
223: return (dbm_nextkey(db));
224: }
225:
226: datum
227: dbm_nextkey(db)
228: register DBM *db;
229: {
230: struct stat statb;
231: datum item;
232:
233: if (dbm_error(db) || fstat(db->dbm_pagf, &statb) < 0)
234: goto err;
235: statb.st_size /= PBLKSIZ;
236: for (;;) {
237: if (db->dbm_blkptr != db->dbm_pagbno) {
238: db->dbm_pagbno = db->dbm_blkptr;
239: (void) lseek(db->dbm_pagf, db->dbm_blkptr*PBLKSIZ, L_SET);
240: if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
241: bzero(db->dbm_pagbuf, PBLKSIZ);
242: #ifdef DEBUG
243: else if (chkblk(db->dbm_pagbuf) < 0)
244: db->dbm_flags |= _DBM_IOERR;
245: #endif
246: }
247: if (((short *)db->dbm_pagbuf)[0] != 0) {
248: item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
249: if (item.dptr != NULL) {
250: db->dbm_keyptr += 2;
251: return (item);
252: }
253: db->dbm_keyptr = 0;
254: }
255: if (++db->dbm_blkptr >= statb.st_size)
256: break;
257: }
258: err:
259: item.dptr = NULL;
260: item.dsize = 0;
261: return (item);
262: }
263:
264: static
265: dbm_access(db, hash)
266: register DBM *db;
267: long hash;
268: {
269:
270: for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
271: db->dbm_blkno = hash & db->dbm_hmask;
272: db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
273: if (getbit(db) == 0)
274: break;
275: }
276: if (db->dbm_blkno != db->dbm_pagbno) {
277: db->dbm_pagbno = db->dbm_blkno;
278: (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
279: if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
280: bzero(db->dbm_pagbuf, PBLKSIZ);
281: #ifdef DEBUG
282: else if (chkblk(db->dbm_pagbuf) < 0)
283: db->dbm_flags |= _DBM_IOERR;
284: #endif
285: }
286: }
287:
288: static
289: getbit(db)
290: register DBM *db;
291: {
292: long bn;
293: register b, i, n;
294:
295:
296: if (db->dbm_bitno > db->dbm_maxbno)
297: return (0);
298: n = db->dbm_bitno % BYTESIZ;
299: bn = db->dbm_bitno / BYTESIZ;
300: i = bn % DBLKSIZ;
301: b = bn / DBLKSIZ;
302: if (b != db->dbm_dirbno) {
303: db->dbm_dirbno = b;
304: (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
305: if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
306: bzero(db->dbm_dirbuf, DBLKSIZ);
307: }
308: return (db->dbm_dirbuf[i] & (1<<n));
309: }
310:
311: static
312: setbit(db)
313: register DBM *db;
314: {
315: long bn;
316: register i, n, b;
317:
318: if (db->dbm_bitno > db->dbm_maxbno)
319: db->dbm_maxbno = db->dbm_bitno;
320: n = db->dbm_bitno % BYTESIZ;
321: bn = db->dbm_bitno / BYTESIZ;
322: i = bn % DBLKSIZ;
323: b = bn / DBLKSIZ;
324: if (b != db->dbm_dirbno) {
325: db->dbm_dirbno = b;
326: (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
327: if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
328: bzero(db->dbm_dirbuf, DBLKSIZ);
329: }
330: db->dbm_dirbuf[i] |= 1<<n;
331: db->dbm_dirbno = b;
332: (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
333: if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
334: db->dbm_flags |= _DBM_IOERR;
335: }
336:
337: static datum
338: makdatum(buf, n)
339: char buf[PBLKSIZ];
340: {
341: register short *sp;
342: register t;
343: datum item;
344:
345: sp = (short *)buf;
346: if ((unsigned)n >= sp[0]) {
347: item.dptr = NULL;
348: item.dsize = 0;
349: return (item);
350: }
351: t = PBLKSIZ;
352: if (n > 0)
353: t = sp[n];
354: item.dptr = buf+sp[n+1];
355: item.dsize = t - sp[n+1];
356: return (item);
357: }
358:
359: static
360: finddatum(buf, item)
361: char buf[PBLKSIZ];
362: datum item;
363: {
364: register short *sp;
365: register int i, n, j;
366:
367: sp = (short *)buf;
368: n = PBLKSIZ;
369: for (i=0, j=sp[0]; i<j; i+=2, n = sp[i]) {
370: n -= sp[i+1];
371: if (n != item.dsize)
372: continue;
373: if (n == 0 || bcmp(&buf[sp[i+1]], item.dptr, n) == 0)
374: return (i);
375: }
376: return (-1);
377: }
378:
379: static int hitab[16]
380: /* ken's
381: {
382: 055,043,036,054,063,014,004,005,
383: 010,064,077,000,035,027,025,071,
384: };
385: */
386: = { 61, 57, 53, 49, 45, 41, 37, 33,
387: 29, 25, 21, 17, 13, 9, 5, 1,
388: };
389: static long hltab[64]
390: = {
391: 06100151277L,06106161736L,06452611562L,05001724107L,
392: 02614772546L,04120731531L,04665262210L,07347467531L,
393: 06735253126L,06042345173L,03072226605L,01464164730L,
394: 03247435524L,07652510057L,01546775256L,05714532133L,
395: 06173260402L,07517101630L,02431460343L,01743245566L,
396: 00261675137L,02433103631L,03421772437L,04447707466L,
397: 04435620103L,03757017115L,03641531772L,06767633246L,
398: 02673230344L,00260612216L,04133454451L,00615531516L,
399: 06137717526L,02574116560L,02304023373L,07061702261L,
400: 05153031405L,05322056705L,07401116734L,06552375715L,
401: 06165233473L,05311063631L,01212221723L,01052267235L,
402: 06000615237L,01075222665L,06330216006L,04402355630L,
403: 01451177262L,02000133436L,06025467062L,07121076461L,
404: 03123433522L,01010635225L,01716177066L,05161746527L,
405: 01736635071L,06243505026L,03637211610L,01756474365L,
406: 04723077174L,03642763134L,05750130273L,03655541561L,
407: };
408:
409: static long
410: hashinc(db, hash)
411: register DBM *db;
412: long hash;
413: {
414: long bit;
415:
416: hash &= db->dbm_hmask;
417: bit = db->dbm_hmask+1;
418: for (;;) {
419: bit >>= 1;
420: if (bit == 0)
421: return (0L);
422: if ((hash & bit) == 0)
423: return (hash | bit);
424: hash &= ~bit;
425: }
426: }
427:
428: static long
429: dcalchash(item)
430: datum item;
431: {
432: register int s, c, j;
433: register char *cp;
434: register long hashl;
435: register int hashi;
436:
437: hashl = 0;
438: hashi = 0;
439: for (cp = item.dptr, s=item.dsize; --s >= 0; ) {
440: c = *cp++;
441: for (j=0; j<BYTESIZ; j+=4) {
442: hashi += hitab[c&017];
443: hashl += hltab[hashi&63];
444: c >>= 4;
445: }
446: }
447: return (hashl);
448: }
449:
450: /*
451: * Delete pairs of items (n & n+1).
452: */
453: static
454: delitem(buf, n)
455: char buf[PBLKSIZ];
456: {
457: register short *sp, *sp1;
458: register i1, i2;
459:
460: sp = (short *)buf;
461: i2 = sp[0];
462: if ((unsigned)n >= i2 || (n & 1))
463: return (0);
464: if (n == i2-2) {
465: sp[0] -= 2;
466: return (1);
467: }
468: i1 = PBLKSIZ;
469: if (n > 0)
470: i1 = sp[n];
471: i1 -= sp[n+2];
472: if (i1 > 0) {
473: i2 = sp[i2];
474: bcopy(&buf[i2], &buf[i2 + i1], sp[n+2] - i2);
475: }
476: sp[0] -= 2;
477: for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
478: sp[0] = sp[2] + i1;
479: return (1);
480: }
481:
482: /*
483: * Add pairs of items (item & item1).
484: */
485: static
486: additem(buf, item, item1)
487: char buf[PBLKSIZ];
488: datum item, item1;
489: {
490: register short *sp;
491: register i1, i2;
492:
493: sp = (short *)buf;
494: i1 = PBLKSIZ;
495: i2 = sp[0];
496: if (i2 > 0)
497: i1 = sp[i2];
498: i1 -= item.dsize + item1.dsize;
499: if (i1 <= (i2+3) * (int)sizeof(short))
500: return (0);
501: sp[0] += 2;
502: sp[++i2] = i1 + item1.dsize;
503: bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize);
504: sp[++i2] = i1;
505: bcopy(item1.dptr, &buf[i1], item1.dsize);
506: return (1);
507: }
508:
509: #ifdef DEBUG
510: static
511: chkblk(buf)
512: char buf[PBLKSIZ];
513: {
514: register short *sp;
515: register t, i;
516:
517: sp = (short *)buf;
518: t = PBLKSIZ;
519: for (i=0; i<sp[0]; i++) {
520: if (sp[i+1] > t)
521: return (-1);
522: t = sp[i+1];
523: }
524: if (t < (sp[0]+1)*sizeof(short))
525: return (-1);
526: return (0);
527: }
528: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.