# 2.11BSD#431 - /usr/src/lib/libc/gen/ndbm.c

##### Functions

    dbm_close         X
    dbm_delete        X
    dbm_fetch         X
    dbm_firstkey      X
    dbm_forder        X
    dbm_nextkey       X
    dbm_open          X
    dbm_store         X

##### Macros

    BYTESIZ           X

       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.3 (Berkeley) 3/9/86";
       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, b;
     293:     register 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, 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, b;
     316:     register i, n;
     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, 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 <= (int)((i2+3) * 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

#### Defined functions

additem defined in line 485; used 2 times

- in line 164, 192

chkblk defined in line 510; used 2 times

- in line 243, 282

dbm_access defined in line 264; used 3 times

- in line 99, 124, 155

dbm_close defined in line 62; used 10 times

- in /usr/include/ndbm.h line 60
- in /usr/src/include/ndbm.h line 60
- in /usr/src/lib/libc/gen/getpwent.c line 158
- in /usr/src/lib/libc/net/hosttable/gethnamadr.c line 115, 150
- in /usr/src/lib/libc/net/hosttable/gethostent.c line 59
- in /usr/src/sbin/mkpasswd/mkpasswd.c line 158
- in /usr/src/usr.lib/libdbm/dbm.c line 23
- in /usr/src/usr.sbin/dev_mkdb/dev_mkdb.c line 133
- in /usr/src/usr.sbin/mkhosts/mkhosts.c line 134

dbm_delete defined in line 111; used 3 times

- in /usr/include/ndbm.h line 65
- in /usr/src/include/ndbm.h line 65
- in /usr/src/usr.lib/libdbm/dbm.c line 68

dbm_fetch defined in line 89; used 8 times

- in /usr/include/ndbm.h line 61
- in /usr/src/include/ndbm.h line 61
- in /usr/src/lib/libc/gen/devname.c line 76
- in /usr/src/lib/libc/gen/getpwent.c line 234
- in /usr/src/lib/libc/net/hosttable/gethnamadr.c line 44
- in /usr/src/new/nntp/server/misc.c line 172
- in /usr/src/usr.lib/libdbm/dbm.c line 56
- in /usr/src/usr.sbin/mkhosts/mkhosts.c line 177

dbm_firstkey defined in line 216; used 4 times

- in /usr/include/ndbm.h line 62
- in /usr/src/include/ndbm.h line 62
- in /usr/src/lib/libc/gen/getpwent.c line 230
- in /usr/src/usr.lib/libdbm/dbm.c line 94

dbm_forder defined in line 72; used 3 times

- in /usr/include/ndbm.h line 64
- in /usr/src/include/ndbm.h line 64
- in /usr/src/usr.lib/libdbm/dbm.c line 42

dbm_nextkey defined in line 226; used 5 times

- in line 223
- in /usr/include/ndbm.h line 63
- in /usr/src/include/ndbm.h line 63
- in /usr/src/lib/libc/gen/getpwent.c line 232
- in /usr/src/usr.lib/libdbm/dbm.c line 108

dbm_open defined in line 26; used 12 times

- in /usr/include/ndbm.h line 59
- in /usr/src/include/ndbm.h line 59
- in /usr/src/lib/libc/gen/devname.c line 59
- in /usr/src/lib/libc/gen/getpwent.c line 126
- in /usr/src/lib/libc/net/hosttable/gethnamadr.c line 97, 133
- in /usr/src/new/nntp/server/misc.c line 155
- in /usr/src/sbin/mkpasswd/mkpasswd.c line 108
- in /usr/src/usr.lib/libdbm/dbm.c line 25-27(2)
- in /usr/src/usr.sbin/dev_mkdb/dev_mkdb.c line 94
- in /usr/src/usr.sbin/mkhosts/mkhosts.c line 55

dbm_store defined in line 139; used 9 times

- in /usr/include/ndbm.h line 66
- in /usr/src/include/ndbm.h line 66
- in /usr/src/sbin/mkpasswd/mkpasswd.c line 143-148(2)
- in /usr/src/usr.lib/libdbm/dbm.c line 81
- in /usr/src/usr.sbin/dev_mkdb/dev_mkdb.c line 130
- in /usr/src/usr.sbin/mkhosts/mkhosts.c line 104, 116, 124

dcalchash defined in line 428; used 6 times

- in line 23, 79, 99, 124, 155, 185

delitem defined in line 453; used 3 times

- in line 127, 159, 193

finddatum defined in line 359; used 3 times

- in line 100, 125, 156

getbit defined in line 288; used 2 times

- in line 83, 273

hashinc defined in line 409; used 1 times

- in line 22

makdatum defined in line 337; used 5 times

- in line 21, 101, 182-186(2), 248

setbit defined in line 311; used 2 times

- in line 19, 212

#### Defined variables

hitab defined in line 379; used 1 times

- in line 442

hltab defined in line 389; used 1 times

- in line 443

sccsid defined in line 8; never used

#### Defined macros

BYTESIZ defined in line 18; used 6 times

- in line 52, 298-299(2), 320-321(2), 441

Last modified: 1987-03-10 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1449 |