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