![[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] / 43BSDReno / lib / libc / gen|
Return to ndbm.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / 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.