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;
 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) * 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
chkblk defined in line 510; used 2 times
dbm_access defined in line 264; used 3 times
dbm_close defined in line 62; used 15 times
dbm_delete defined in line 111; used 3 times
dbm_fetch defined in line 89; used 6 times
dbm_firstkey defined in line 216; used 3 times
dbm_forder defined in line 72; used 3 times
dbm_nextkey defined in line 226; used 4 times
dbm_open defined in line 26; used 12 times
dbm_store defined in line 139; used 10 times
dcalchash defined in line 428; used 6 times
delitem defined in line 453; used 3 times
finddatum defined in line 359; used 3 times
getbit defined in line 288; used 2 times
hashinc defined in line 409; used 1 times
  • in line 22
makdatum defined in line 337; used 5 times
setbit defined in line 311; used 2 times

Defined variables

hitab defined in line 379; used 1 times
hltab defined in line 389; used 1 times
sccsid defined in line 8; never used

Defined macros

BYTESIZ defined in line 18; used 6 times
Last modified: 1986-03-10
Generated: 2016-12-26 		Generated by src2html V0.67
page hit count: 2179 		Valid CSS Valid XHTML 1.0 Strict