![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to bundled CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / btree|
Return to bundled CVS log | Up to [Research Unix] / researchv10no / cmd / btree |
1.1 ! root 1: # To unbundle, sh this file ! 2: echo be.h 1>&2 ! 3: sed 's/.//' >be.h <<'//GO.SYSIN DD be.h' ! 4: -#define BERROR 100 /* first btree value of errno */ ! 5: -#define BUTRAN BERROR + 0 /* user caused tran abort */ ! 6: -#define BNOWRITE BERROR + 1 /* not opened for writing */ ! 7: -#define BIOWRT BERROR + 2 /* wrote short record */ ! 8: -#define BNOMEM BERROR + 3 /* no mem from malloc */ ! 9: -#define BFATAL BERROR + 4 /* last chance for user */ ! 10: -#define BTALL BERROR + 5 /* tree becoming taller than MXHT */ ! 11: -#define BLASTE BERROR + 6 /* one past last btree value of errno */ ! 12: -extern int errno; ! 13: -/*0101010011100100*/ ! 14: //GO.SYSIN DD be.h ! 15: echo cbt.h 1>&2 ! 16: sed 's/.//' >cbt.h <<'//GO.SYSIN DD cbt.h' ! 17: -#ifdef TEST ! 18: -#define NDSZ 64 ! 19: -#else ! 20: -#define NDSZ 1024/* for real systems (larger may be slower) */ ! 21: -#endif ! 22: -#define MAXKLEN (NDSZ/4)-8 ! 23: -#if MAXKLEN > 255 ! 24: -#undef MAXKLEN ! 25: -#define MAXKLEN 255 ! 26: -#endif ! 27: -#define MXHT 5 ! 28: -typedef long ndaddr; ! 29: -/* for communication with users */ ! 30: -typedef struct { ! 31: - char *mdata; ! 32: - unsigned short mlen; ! 33: -} mbuf; ! 34: -typedef struct bfile { ! 35: - struct bfile *next; ! 36: - struct hdr *path[MXHT + 1]; ! 37: - char height, advnc, rdwrt, flag[MXHT + 1]; ! 38: - ndaddr loc[MXHT + 1]; ! 39: - int tfd, dfd; ! 40: - char *fname, *altname; ! 41: - struct rdptr { ! 42: - struct dkey *rptr; /* current dkey */ ! 43: - short rnum; /* its ordinal */ ! 44: - char rpref[MAXKLEN]; /* first dcom bytes of its key */ ! 45: - } rdptr; ! 46: - char fatal; /* this bfile can't be used */ ! 47: -} bfile; ! 48: -extern bfile *bopen(); ! 49: -extern mbuf bkey(); ! 50: - ! 51: -#define BERROR 100 /* first btree value of errno */ ! 52: -#define BUTRAN BERROR + 0 /* user caused tran abort */ ! 53: -#define BNOWRITE BERROR + 1 /* not opened for writing */ ! 54: -#define BIOWRT BERROR + 2 /* wrote short record */ ! 55: -#define BNOMEM BERROR + 3 /* no mem from malloc */ ! 56: -#define BFATAL BERROR + 4 /* last chance for user */ ! 57: -#define BTALL BERROR + 5 /* tree becoming taller than MXHT */ ! 58: -#define BRDERR BERROR + 6 /* read short record or read error */ ! 59: -#define BLASTE BERROR + 7 /* one past last btree value of errno */ ! 60: -extern int errno; ! 61: - ! 62: -/* users can ignore the rest of this stuff */ ! 63: -/* keys in nodes */ ! 64: -typedef struct dkey { ! 65: - unsigned char dlen; /* total size of structure */ ! 66: - char dcom; /* bytes in common with preceding */ ! 67: - char dkey[MAXKLEN]; /* rest of key */ ! 68: -} dkey; ! 69: -#define DKEYSZ 2 /* overhead in dkey */ ! 70: -/* node header */ ! 71: -typedef struct hdr { ! 72: - long hstamp; /* for owning process */ ! 73: - short kcnt; /* keys in node */ ! 74: - char htype; ! 75: - char hlev; ! 76: -} hdr; ! 77: -typedef struct { ! 78: - short tfree; /* free bytes in node, at end for triv checking */ ! 79: -} trailer; ! 80: -#define nfree(p) ((trailer *)((char *)(p) + NDSZ - sizeof(trailer)))->tfree ! 81: -#define SHARED 1 ! 82: -#define INDEX 2 ! 83: -#define READONLY 4 ! 84: -#define bf_type(b, t) ((b)->path[0]->htype & (t)) ! 85: -#define treeonly(b) bf_type(b, INDEX) ! 86: -#define shared(b) bf_type(b, SHARED) ! 87: -#define readonly(b) bf_type(b, READONLY) ! 88: -/* disk addresses */ ! 89: -typedef struct { ! 90: - long lloc; ! 91: - unsigned short llen; ! 92: -} lfaddr; ! 93: -#define ndadr(b, j) ((ndaddr *)((char *)(b) + NDSZ - sizeof(trailer)) - (j) - 1) ! 94: -#define lfadr(b, j) ((lfaddr *)((char *)(b) + NDSZ - sizeof(trailer)) - (j) - 1) ! 95: -#define mustwrite(bf, n) bf->flag[n] /* for getincore */ ! 96: -/* node format: ! 97: - * hdr, dkey, dkey, dkey, ..., space, adr, adrn, ..., adr0, trailer ! 98: - */ ! 99: -extern int bdump; /* dump on first fatal error */ ! 100: -extern long tranid, getlpid(); /* unique transaction id */ ! 101: -#ifndef EOF ! 102: -#ifndef NULL ! 103: -#define NULL 0 ! 104: -#endif ! 105: -#define EOF -1 ! 106: -#endif ! 107: -#define NOTFOUND 0 ! 108: -#define FOUND 1 ! 109: - ! 110: -#define alloc(x) (x *)malloc(sizeof(x)) ! 111: -#define stamped(b) b->hstamp == tranid ! 112: -/*1000001111101111*/ ! 113: //GO.SYSIN DD cbt.h ! 114: echo pr.h 1>&2 ! 115: sed 's/.//' >pr.h <<'//GO.SYSIN DD pr.h' ! 116: -typedef struct { ! 117: - short match; /* FOUND, NOTFOUND, or EOF */ ! 118: - unsigned char ncom, /* len of prefix in common with d */ ! 119: - ocom; /* len for predecessor of d */ ! 120: - dkey *d; /* first key >= requested */ ! 121: - /* or, if match==EOF, last in node */ ! 122: -} private; ! 123: -/*0111110111010100*/ ! 124: //GO.SYSIN DD pr.h ! 125: echo bdelete.c 1>&2 ! 126: sed 's/.//' >bdelete.c <<'//GO.SYSIN DD bdelete.c' ! 127: -#include "cbt.h" ! 128: -#include "pr.h" ! 129: - ! 130: -extern bfile *curbf; ! 131: -bdelete(bf, key) bfile *bf; mbuf key; ! 132: -{ dkey *dold, *dnew; ! 133: - hdr *b; ! 134: - int svlen, dellen; ! 135: - char *ffree; ! 136: - ! 137: - if(bf == NULL) ! 138: - return(EOF); ! 139: - if(notran(bf)) ! 140: - return(EOF); ! 141: - if(!bf->rdwrt) { ! 142: - errno = BNOWRITE; ! 143: - return(EOF); ! 144: - } ! 145: - if(bseek(bf, key) != FOUND) ! 146: - return(NOTFOUND); ! 147: - b = bf->path[0]; ! 148: - dold = bf->rdptr.rptr; ! 149: - if(bf->rdptr.rnum + 1 >= b->kcnt) { ! 150: - nfree(b) += dold->dlen + (treeonly(bf)? 0: sizeof(lfaddr)); ! 151: - --b->kcnt; ! 152: - mustwrite(bf, 0) = 1; ! 153: - if(b->hlev == 0 && b->kcnt <= 0 || b->hlev > 0 && b->kcnt < 0) { ! 154: - mustwrite(bf, 0) = 0; ! 155: - ndelete(1, key); ! 156: - } ! 157: - if(b->kcnt < 0) ! 158: - b->kcnt = 0; ! 159: - (void) bseek(bf, key); ! 160: - return(FOUND); ! 161: - } ! 162: - ! 163: - if(treeonly(bf)) ! 164: - ffree = (char *)&nfree(b) - nfree(b); ! 165: - else ! 166: - ffree = (char *)lfadr(b, b->kcnt - 1) - nfree(b); ! 167: - svlen = dold->dlen; ! 168: - dnew = (dkey *)((char *)dold + dold->dlen); ! 169: - if(dnew->dcom <= dold->dcom) { ! 170: - mvgbt((char *)dold, (char *)dnew, ffree - (char *)dnew); ! 171: - if(!treeonly(bf)) ! 172: - rmlfadr(b, bf->rdptr.rnum); ! 173: - b->kcnt--; ! 174: - mustwrite(bf, 0) = 1; ! 175: - nfree(b) += svlen + (treeonly(bf)? 0: sizeof(lfaddr)); ! 176: - (void) bseek(bf, key); ! 177: - return(FOUND); ! 178: - } ! 179: - dellen = dnew->dcom - dold->dcom; ! 180: - /* writing over dold */ ! 181: - dold->dlen = dnew->dlen + dellen; ! 182: - mvgbt(dold->dkey + dellen, dnew->dkey, ffree - dnew->dkey); ! 183: - if(!treeonly(bf)) ! 184: - rmlfadr(b, bf->rdptr.rnum); ! 185: - b->kcnt--; ! 186: - mustwrite(bf, 0) = 1; ! 187: - nfree(b) += svlen - dellen + (treeonly(bf)? 0: sizeof(lfaddr)); ! 188: - (void) bseek(bf, key); ! 189: - return(FOUND); ! 190: -} ! 191: -rmlfadr(b, n) hdr *b; unsigned int n; ! 192: -{ ! 193: - mvgbt((char *)lfadr(b, b->kcnt - 2), (char *)lfadr(b, b->kcnt - 1), ! 194: - (int)sizeof(lfaddr) * (b->kcnt - 1 - n)); ! 195: -} ! 196: -rmndadr(b, n) hdr *b; unsigned short n; ! 197: -{ ! 198: - mvgbt((char *)ndadr(b, b->kcnt - 1), (char *)ndadr(b, b->kcnt), ! 199: - (int)sizeof(ndaddr) * (b->kcnt - n)); ! 200: -} ! 201: -ndelete(lev, key) mbuf key; ! 202: -{ hdr *b; ! 203: - int svlen, dellen; ! 204: - unsigned short n; ! 205: - private x; ! 206: - char *ffree; ! 207: - dkey *dold, *dnew; ! 208: - if(lev > curbf->height) { ! 209: - b = curbf->path[curbf->height]; ! 210: - b->hlev = 0; ! 211: - curbf->height = 0; ! 212: - mustwrite(curbf, 0) = 1; ! 213: - curbf->loc[0] = 0; ! 214: - nfree(b) = NDSZ - sizeof(hdr) - sizeof(trailer); ! 215: - b->kcnt = 0; ! 216: - mvgbt((char *)curbf->path[0], (char *)b, NDSZ); ! 217: - return; ! 218: - } ! 219: - b = curbf->path[lev]; ! 220: - n = xscan(b, key, &x); ! 221: - if(x.match == EOF) { ! 222: - if(b->kcnt <= 0) { ! 223: - mustwrite(curbf, lev) = 0; ! 224: - ndelete(lev+1, key); ! 225: - return; ! 226: - } ! 227: - b->kcnt--; ! 228: - nfree(b) += sizeof(ndaddr) + x.d->dlen; ! 229: - mustwrite(curbf, lev) = 1; ! 230: - return; ! 231: - } ! 232: - dold = x.d; ! 233: - dnew = (dkey *)((char *)dold + dold->dlen); ! 234: - ffree = (char *)ndadr(b, b->kcnt) - nfree(b); ! 235: - svlen = dold->dlen; ! 236: - if(n + 1 >= b->kcnt || dnew->dcom <= dold->dcom) { ! 237: - mvgbt((char *)dold, (char *)dnew, ffree - (char *)dnew); ! 238: - rmndadr(b, n); ! 239: - b->kcnt--; ! 240: - mustwrite(curbf, lev) = 1; ! 241: - nfree(b) += sizeof(ndaddr) + svlen; ! 242: - return; ! 243: - } ! 244: - dellen = dnew->dcom - dold->dcom; ! 245: - /* writing over dold */ ! 246: - dold->dlen = dnew->dlen + dellen; ! 247: - mvgbt(dold->dkey + dellen, dnew->dkey, ffree - dnew->dkey); ! 248: - rmndadr(b, n); ! 249: - b->kcnt--; ! 250: - mustwrite(curbf, lev) = 1; ! 251: - nfree(b) += sizeof(ndaddr) + svlen - dellen; ! 252: -} ! 253: -static struct D { struct D *a; char *b;} VER = {&VER,"\n82/10/9:bdelete.c\n"}; ! 254: -/*1101110100011001*/ ! 255: //GO.SYSIN DD bdelete.c ! 256: echo bt.c 1>&2 ! 257: sed 's/.//' >bt.c <<'//GO.SYSIN DD bt.c' ! 258: -#include "cbt.h" ! 259: -#include "pr.h" ! 260: - ! 261: -bfile *curbf; ! 262: -extern bfile *newtran(); ! 263: -extern char *malloc(), *strcpy(); ! 264: -extern long lseek(); ! 265: - ! 266: -bfile *bopen(s, typ) char *s; /* typ is 0 or 2 */ ! 267: -{ bfile *p; ! 268: - int n, i; ! 269: - ! 270: - p = alloc(bfile); ! 271: - if(p == NULL) ! 272: - goto nomem; ! 273: - n = strlen(s); ! 274: - p->fname = malloc((unsigned)n + 3); ! 275: - if(p->fname == NULL) ! 276: - goto nomem; ! 277: - (void) strcpy(p->fname, s); ! 278: - strcpy(p->fname + n, ".T"); ! 279: - if((p->tfd = open(p->fname, typ)) == -1) { ! 280: - free(p->fname); ! 281: - free((char *)p); ! 282: - return(NULL); ! 283: - } ! 284: - p->rdwrt = typ; ! 285: - p->fatal = p->advnc = 0; ! 286: - p->altname = NULL; ! 287: - for(i = 0; i <= MXHT; i++) { ! 288: - p->path[i] = NULL; ! 289: - p->flag[i] = 0; ! 290: - p->loc[i] = 0; ! 291: - } ! 292: - p->path[0] = (hdr *)malloc(NDSZ); ! 293: - if(p->path[0] == NULL) ! 294: - goto nomem; ! 295: - curbf = p; ! 296: - if(ndrd(0, (ndaddr)0) == EOF) ! 297: - return(NULL); ! 298: - strcpy(p->fname + n, ".F"); ! 299: - if(!treeonly(p) && (p->dfd = open(p->fname, typ)) == -1) { ! 300: - (void) close(p->tfd); ! 301: - free(p->fname); ! 302: - free((char *) p->path[0]); ! 303: - free((char *)p); ! 304: - return(NULL); ! 305: - } ! 306: - else if(treeonly(p)) ! 307: - p->dfd = -1; ! 308: - p->fname[n] = 0; ! 309: - if(shared(p)) ! 310: - return(newtran(p)); ! 311: - else if(tranid == 0) ! 312: - tranid = getlpid(); ! 313: - p->height = p->path[0]->hlev; ! 314: - for(n = 1; n <= p->height; n++) ! 315: - if((p->path[n] = (hdr *)malloc(NDSZ)) == NULL) ! 316: - goto nomem; ! 317: - if(p->height > 0) ! 318: - mvgbt((char *)p->path[p->height], (char *)p->path[0], NDSZ); ! 319: - (void) bfirst(p); ! 320: - return(p); ! 321: -nomem: ! 322: - errno = BNOMEM; ! 323: - return(NULL); ! 324: -} ! 325: - ! 326: -bseek(bf, key) bfile *bf; mbuf key; ! 327: -{ private m; ! 328: - int i; ! 329: - if(bf == NULL) ! 330: - return(EOF); ! 331: - if(notran(bf)) ! 332: - return(EOF); ! 333: - if(!readonly(bf)) ! 334: - for(i = 0; i < bf->height; i++) ! 335: - if(mustwrite(bf, i)) ! 336: - if(fixpath(bf) == EOF) ! 337: - return(EOF); ! 338: - bf->rdptr.rnum = desce(bf, key, &m); ! 339: - if(bf->rdptr.rnum == EOF) ! 340: - return(EOF); ! 341: - bf->advnc = 0; ! 342: - bf->rdptr.rptr = m.d; ! 343: - if(m.match == EOF) { ! 344: - if(advance() == EOF) ! 345: - return(EOF); ! 346: - if(bf->rdptr.rptr != NULL) ! 347: - m.match = NOTFOUND; ! 348: - } ! 349: - if(m.match != EOF) ! 350: - mvgbt(bf->rdptr.rpref, key.mdata, bf->rdptr.rptr->dcom); ! 351: - /* maybe use rptr instead of m.d */ ! 352: - return(m.match); ! 353: -} ! 354: - ! 355: -bfirst(bf) bfile *bf; ! 356: -{ mbuf key; ! 357: - key.mlen = 0; ! 358: - return(bseek(bf, key)); ! 359: -} ! 360: - ! 361: -bclose(bf) bfile *bf; ! 362: -{ int i; ! 363: - if(bf == NULL) ! 364: - return; ! 365: - if(shared(bf)) { ! 366: - if(intran()) ! 367: - trabort(); ! 368: - rmtran(bf); ! 369: - } ! 370: - else ! 371: - bflush(bf); ! 372: - free(bf->fname); ! 373: - for(i = 0; i <= MXHT; i++) ! 374: - if(bf->path[i] != NULL) ! 375: - free((char *)bf->path[i]); ! 376: - if(bf->tfd != -1) ! 377: - (void) close(bf->tfd); ! 378: - if(bf->dfd != -1) ! 379: - (void) close(bf->dfd); ! 380: - free((char *)bf); ! 381: -} ! 382: - ! 383: -bflush(bf) bfile *bf; ! 384: -{ int i; ! 385: - if(bf == NULL) ! 386: - return(0); ! 387: - if(!bf->rdwrt) { ! 388: - errno = BNOWRITE; ! 389: - return(EOF); ! 390: - } ! 391: - curbf = bf; ! 392: - if(shared(bf)) ! 393: - if(intran()) { ! 394: - trabort(); ! 395: - return(EOF); ! 396: - } ! 397: - else return(0); ! 398: - for(i = 0; i <= bf->height; i++) { ! 399: - if(!mustwrite(bf, i)) ! 400: - continue; ! 401: - if(readonly(bf) || i == bf->height) ! 402: - if(ndwrt(bf->path[i], bf->loc[i]) == EOF) ! 403: - return(EOF); ! 404: - else ! 405: - if(fixpath(bf) == EOF) ! 406: - return(EOF); ! 407: - bf->flag[i] = 0; ! 408: - } ! 409: - return(0); ! 410: -} ! 411: - ! 412: -breclen(bf) bfile *bf; ! 413: -{ ! 414: - if(bf == NULL) ! 415: - return(EOF); ! 416: - if(notran(bf)) ! 417: - return(EOF); ! 418: - if(bf->advnc) ! 419: - if(advance() == EOF) ! 420: - return(EOF); ! 421: - if(bf->rdptr.rnum >= bf->path[0]->kcnt) ! 422: - return(EOF); ! 423: - if(treeonly(bf)) ! 424: - return(0); ! 425: - return(lfadr(bf->path[0], bf->rdptr.rnum)->llen); ! 426: -} ! 427: - ! 428: -mbuf bkey(bf) bfile *bf; ! 429: -{ mbuf x; ! 430: - dkey *d; ! 431: - if(bf == NULL) ! 432: - goto eof; ! 433: - if(notran(bf)) ! 434: - goto eof; ! 435: - if(bf->advnc) ! 436: - if(advance() == EOF) ! 437: - goto eof; ! 438: - if(bf->rdptr.rnum >= bf->path[0]->kcnt) ! 439: - goto eof; ! 440: - d = bf->rdptr.rptr; ! 441: - x.mlen = d->dlen - DKEYSZ + d->dcom; ! 442: - mvgbt(bf->rdptr.rpref + d->dcom, d->dkey, d->dlen-DKEYSZ); ! 443: - x.mdata = bf->rdptr.rpref; ! 444: - return(x); ! 445: -eof: ! 446: - x.mlen = 0; ! 447: - x.mdata = NULL; ! 448: - return(x); ! 449: -} ! 450: - ! 451: -bread(bf, key, rec) bfile *bf; mbuf *key, *rec; ! 452: -{ ! 453: - dkey *d; ! 454: - lfaddr *x; ! 455: - int n; ! 456: - if(bf == NULL) ! 457: - return(NULL); ! 458: - if(notran(bf)) ! 459: - return(EOF); ! 460: - if(bf->advnc) ! 461: - if(advance() == EOF) ! 462: - return(EOF); ! 463: - if(bf->rdptr.rnum >= bf->path[0]->kcnt) ! 464: - return(EOF); ! 465: - if(key != NULL) { ! 466: - d = bf->rdptr.rptr; ! 467: - key->mlen = d->dlen - DKEYSZ + d->dcom; ! 468: - mvgbt(key->mdata, bf->rdptr.rpref, d->dcom); ! 469: - mvgbt(key->mdata + d->dcom, d->dkey, d->dlen - DKEYSZ); ! 470: - } ! 471: - if(rec != NULL && !treeonly(bf)) { ! 472: - x = lfadr(bf->path[0], bf->rdptr.rnum); ! 473: - rec->mlen = x->llen; ! 474: - if(rec->mlen != 0) { ! 475: - (void) lseek(bf->dfd, x->lloc, 0); ! 476: - if((n = read(bf->dfd, rec->mdata, (int)rec->mlen)) ! 477: - != rec->mlen) { ! 478: - if(n >= 0) ! 479: - errno = BRDERR; ! 480: - return(EOF); ! 481: - } ! 482: - } ! 483: - } ! 484: - bf->advnc = 1; ! 485: - return(0); ! 486: -} ! 487: -static struct D { struct D *a; char *b;} VER = {&VER,"\n82/10/9:bt.c\n"}; ! 488: -/*0001011110110101*/ ! 489: //GO.SYSIN DD bt.c ! 490: echo btadd.c 1>&2 ! 491: sed 's/.//' >btadd.c <<'//GO.SYSIN DD btadd.c' ! 492: -#include "stdio.h" ! 493: -#include "cbt.h" ! 494: - ! 495: -/* like btbuild, but random access */ ! 496: -char keybuf[NDSZ]; ! 497: -char recbuf[32767]; ! 498: -mbuf key = { keybuf, 0}; ! 499: -mbuf rec = { recbuf, 0}; ! 500: -bfile *bf; ! 501: -int cflag; ! 502: - ! 503: -main(argc, argv) ! 504: -char **argv; ! 505: -{ int n; ! 506: - if(argv[1][0] == '-') { ! 507: - cflag++; ! 508: - argc--; ! 509: - argv++; ! 510: - } ! 511: - if(argc != 2) { ! 512: - fprintf(stderr, "usage: btadd bfile < recs\n"); ! 513: - exit(1); ! 514: - } ! 515: - if((bf = bopen(argv[1], 2)) == NULL) { ! 516: - perror(argv[1]); ! 517: - exit(1); ! 518: - } ! 519: - for(;;) { ! 520: - get(2, (char *)&key.mlen); ! 521: - if(key.mlen > MAXKLEN) { ! 522: - fprintf(stderr, "key too long\n"); ! 523: - exit(1); ! 524: - } ! 525: - get(key.mlen, key.mdata); ! 526: - get(2, (char *)&rec.mlen); ! 527: - if(rec.mlen > sizeof(recbuf)) { ! 528: - fprintf(stderr, "rec len %ud: recompile btadd\n", ! 529: - rec.mlen); ! 530: - abort(); ! 531: - } ! 532: - get(rec.mlen, rec.mdata); ! 533: - (void)bwrite(bf, key, rec); ! 534: - bfirst(bf); ! 535: - if(bseek(bf, key) != FOUND) { ! 536: - key.mdata[key.mlen] = 0; ! 537: - fprintf(stderr, "vanished:%s:\n", key.mdata); ! 538: - abort(); ! 539: - } ! 540: - if(cflag) ! 541: - bcheck(bf); ! 542: - } ! 543: -} ! 544: -get(n, s) ! 545: -char *s; ! 546: -{ int m; ! 547: - for(m = 0; n > 0; n -= m) { ! 548: - m = read(0, s, n); ! 549: - if(m == 0) { ! 550: - bclose(bf); ! 551: - exit(0); ! 552: - } ! 553: - if(m < 0) { ! 554: - fprintf(stderr, "io error in btadd\n"); ! 555: - abort(); ! 556: - } ! 557: - s += m; ! 558: - } ! 559: -} ! 560: - ! 561: -mbuf new, old; ! 562: -char newbuf[NDSZ], oldbuf[NDSZ]; ! 563: -bcheck(bf) ! 564: -bfile *bf; ! 565: -{ long i; ! 566: - int j, k; ! 567: - char *p; ! 568: - bfirst(bf); ! 569: - new.mdata = newbuf; ! 570: - old.mdata = oldbuf; ! 571: - for(i = 0;; i++) { ! 572: - if(bread(bf, &new, (mbuf *)NULL) == EOF) ! 573: - break; ! 574: - if(i > 0) { ! 575: - k = new.mlen; ! 576: - if(old.mlen < new.mlen) ! 577: - k = old.mlen; ! 578: - for(j = 0; j < k; j++) ! 579: - if(new.mdata[j] != old.mdata[j]) ! 580: - break; ! 581: - if(j != k) { ! 582: - if(new.mdata[j] > old.mdata[j]) ! 583: - continue; ! 584: -bad: ! 585: - fprintf(stderr, "disorder at key %ld\n", i); ! 586: - key.mdata[key.mlen] = 0; ! 587: - fprintf(stderr, "key is:%s:\n", key.mdata); ! 588: - abort(); ! 589: - } ! 590: - if(old.mlen >= new.mlen) ! 591: - goto bad; ! 592: - } ! 593: - p = old.mdata; ! 594: - old = new; ! 595: - new.mdata = p; ! 596: - } ! 597: -} ! 598: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/8/25:btadd.c\n"}; ! 599: -/*1100001100101101*/ ! 600: //GO.SYSIN DD btadd.c ! 601: echo btbuild.c 1>&2 ! 602: sed 's/.//' >btbuild.c <<'//GO.SYSIN DD btbuild.c' ! 603: -#include "stdio.h" ! 604: -#include "cbt.h" ! 605: -#define SZ MXHT+1 ! 606: - ! 607: -typedef struct { ! 608: - unsigned short mlen; ! 609: - char mdata[NDSZ]; /* max size of values */ ! 610: -} xbuf; ! 611: -int address[SZ]; /* where the next address goes in the node */ ! 612: -xbuf curkey[SZ]; /* last key put in the node */ ! 613: -xbuf shortone; /* for compression */ ! 614: -int freecnt[SZ]; /* number of bytes left in node */ ! 615: -dkey *kp[SZ]; /* where to put next dkey in node */ ! 616: -char node[SZ][NDSZ]; /* the nodes */ ! 617: -char used[SZ+1]; /* which nodes have been used */ ! 618: -xbuf nkey; /* as read by getrec */ ! 619: -struct { ! 620: - unsigned short mlen; ! 621: - char mdata[32767]; ! 622: -} val; ! 623: -lfaddr currec; /* where getrec put val */ ! 624: -FILE *tfd, *dfd; ! 625: -char name[16]; ! 626: -int type; ! 627: -long reccnt; ! 628: -extern char *malloc(); ! 629: - ! 630: -char * ! 631: -prkey(a) ! 632: -xbuf *a; ! 633: -{ int i; ! 634: - unsigned char c; ! 635: - static char buf[4*NDSZ], *p; ! 636: - for(i = 0, p = buf; i < a->mlen; i++) { ! 637: - c = a->mdata[i]; ! 638: - if(c < ' ') { ! 639: - *p++ = '^'; ! 640: - c += ' '; ! 641: - } ! 642: - if(c < 127) ! 643: - *p++ = (char)c; ! 644: - else { ! 645: - *p++ = '\\'; ! 646: - *p++ = (c >> 6) + '0'; ! 647: - *p++ = ((c&63)>>3) + '0'; ! 648: - *p++ = c&7 + '0'; ! 649: - } ! 650: - } ! 651: - *p++ = 0; ! 652: - return(buf); ! 653: -} ! 654: -pref(a, b, lev) xbuf *a, *b; ! 655: -{ register int n; ! 656: - register char *p, *q; ! 657: - for(n = 0, p = a->mdata, q = b->mdata; n < a->mlen && n < b->mlen; n++) ! 658: - if(*p++ != *q++) ! 659: - break; ! 660: - p--, q--; ! 661: - if(lev == 0 && ((n == b->mlen && n >= a->mlen) || *p > *q)) { ! 662: - fprintf(stderr, "key %ld out of order:\n", reccnt); ! 663: - fprintf(stderr, "key %ld is %s\n", reccnt - 1, prkey(a)); ! 664: - fprintf(stderr, "key %ld is %s\n", reccnt, prkey(b)); ! 665: - } ! 666: - return(n); ! 667: -} ! 668: - ! 669: -getrec() ! 670: -{ ! 671: - reccnt++; ! 672: - if(mget(&nkey)) ! 673: - return(-1); ! 674: - if(mget((xbuf *)&val)) ! 675: - fail("half a record read"); ! 676: - if((currec.llen = val.mlen) != 0) { ! 677: - currec.lloc = ftell(dfd); ! 678: - (void) fwrite(val.mdata, 1, val.mlen, dfd); ! 679: - if(ferror(dfd)) ! 680: - fail("value write"); ! 681: - } ! 682: - else currec.lloc = 0; ! 683: - return(1); ! 684: -} ! 685: - ! 686: -mget(a) xbuf *a; ! 687: -{ ! 688: - (void) fread((char *)&(a->mlen), 1, sizeof(a->mlen), stdin); ! 689: - if(feof(stdin) || ferror(stdin)) ! 690: - return(1); ! 691: - if(fread(a->mdata, 1, a->mlen, stdin) != a->mlen) ! 692: - return(1); ! 693: - return(0); ! 694: -} ! 695: - ! 696: -ndaddr ndwrt(level) ! 697: -{ ndaddr loc; ! 698: - int i; ! 699: - hdr *x; ! 700: - trailer *t; ! 701: - loc = ftell(tfd)/NDSZ; ! 702: - x = (hdr *)(node[level]); ! 703: - x->hlev = level; ! 704: - t = (trailer *)(node[level] + NDSZ - sizeof(trailer)); ! 705: - t->tfree = freecnt[level]; ! 706: - x->kcnt = address[level] - (level == 0? 0: 1); ! 707: - x->htype = type; ! 708: - (void) fwrite(node[level], 1, NDSZ, tfd); ! 709: - if(ferror(tfd)) ! 710: - fail("node write"); ! 711: - for(i = 0; i < NDSZ; i++) ! 712: - node[level][i] = 0; ! 713: - address[level] = 0; ! 714: - curkey[level].mlen = 0; ! 715: - freecnt[level] = NDSZ - sizeof(hdr) - sizeof(trailer); ! 716: - if(level) ! 717: - freecnt[level] -= sizeof(ndaddr); ! 718: - kp[level] = (dkey *)(node[level] + sizeof(hdr)); ! 719: - return(loc); ! 720: -} ! 721: - ! 722: -finish(level, ptr) ndaddr ptr; ! 723: -{ ndaddr loc; ! 724: - if(!used[level]) ! 725: - return; ! 726: - *ndadr(node[level], address[level]++) = ptr; ! 727: - if(!used[level + 1]) ! 728: - fseek(tfd, 0L, 0); ! 729: - loc = ndwrt(level); ! 730: - finish(level + 1, loc); ! 731: -} ! 732: - ! 733: -insert(level, key, ptr) xbuf *key; ndaddr ptr; ! 734: -{ int n, len; ! 735: - char *p; ! 736: - ndaddr loc; ! 737: - used[level] = 1; ! 738: - n = pref(&curkey[level], key, level); ! 739: - len = DKEYSZ + key->mlen - n + sizeof(ptr); ! 740: - if(len < freecnt[level]) { ! 741: - *ndadr(node[level], address[level]++) = ptr; ! 742: - kp[level]->dlen = len - sizeof(ptr); ! 743: - kp[level]->dcom = n; ! 744: - mvgbt(kp[level]->dkey, key->mdata + n, key->mlen - n); ! 745: - p = (char *)(kp[level]) + kp[level]->dlen; ! 746: - kp[level] = (dkey *)p; ! 747: - freecnt[level] -= len; ! 748: - curkey[level] = *key; ! 749: - } ! 750: - else { ! 751: - *ndadr(node[level],address[level]++) = ptr; ! 752: - loc = ndwrt(level); ! 753: - insert(level+1, key, loc); ! 754: - curkey[level].mlen = 0; ! 755: - } ! 756: -} ! 757: - ! 758: -doit() ! 759: -{ int n, len; ! 760: - ndaddr loc; ! 761: - char *p; ! 762: - for(;;) { ! 763: - if(getrec() == -1) ! 764: - break; ! 765: - used[0] = 1; ! 766: - n = pref(&curkey[0], &nkey, 0); ! 767: - len = DKEYSZ + nkey.mlen - n + sizeof(currec); ! 768: - if(type & INDEX) ! 769: - len -= sizeof(currec); ! 770: - if(len < freecnt[0]) { ! 771: - freecnt[0] -= len; ! 772: - if(!(type & INDEX)) ! 773: - *lfadr(node[0], address[0]++) = currec; ! 774: - else ! 775: - address[0]++; ! 776: - kp[0]->dlen = DKEYSZ + nkey.mlen - n; ! 777: - kp[0]->dcom = n; ! 778: - mvgbt(kp[0]->dkey, nkey.mdata + n, nkey.mlen - n); ! 779: - p = (char *)(kp[0]) + kp[0]->dlen; ! 780: - kp[0] = (dkey *)p; ! 781: - curkey[0] = nkey; ! 782: - } ! 783: - else { ! 784: - shortest(&curkey[0], &nkey); ! 785: - loc = ndwrt(0); ! 786: - freecnt[0] -= DKEYSZ + nkey.mlen + sizeof(currec); ! 787: - if(type & INDEX) ! 788: - freecnt[0] += sizeof(currec); ! 789: - insert(1, &shortone, loc); ! 790: - if(!(type & INDEX)) ! 791: - *lfadr(node[0], address[0]++) = currec; ! 792: - else ! 793: - address[0]++; ! 794: - kp[0]->dlen = DKEYSZ + nkey.mlen; ! 795: - kp[0]->dcom = 0; ! 796: - mvgbt(kp[0]->dkey, nkey.mdata, nkey.mlen); ! 797: - p = (char *)(kp[0]) + kp[0]->dlen; ! 798: - kp[0] = (dkey *)p; ! 799: - curkey[0] = nkey; ! 800: - } ! 801: - } ! 802: - if(!used[1]) ! 803: - (void) fseek(tfd, 0L, 0); ! 804: - loc = ndwrt(0); ! 805: - finish(1, loc); ! 806: -} ! 807: - ! 808: -init(s) ! 809: -char *s; ! 810: -{ int i; ! 811: - hdr *b; ! 812: - char xx[NDSZ]; ! 813: - (void) sprintf(name, "%s.T", s); ! 814: - tfd = fopen(name, "r"); ! 815: - if(tfd == NULL) { ! 816: - perror(s); ! 817: - exit(1); ! 818: - } ! 819: - fread(xx, 1, NDSZ, tfd); ! 820: - fclose(tfd); ! 821: - tfd = fopen(name, "w"); ! 822: - (void) fseek(tfd, (long)NDSZ, 0); ! 823: - b = (hdr *)xx; ! 824: - type = b->htype; ! 825: - (void) sprintf(name, "%s.F", s); ! 826: - if((type & INDEX) != INDEX) ! 827: - dfd = fopen(name, "w"); ! 828: - for(i = 0; i < SZ; i++) { ! 829: - freecnt[i] = NDSZ - sizeof(hdr) - sizeof(trailer); ! 830: - if(i) ! 831: - freecnt[i] -= sizeof(ndaddr); ! 832: - kp[i] = (dkey *)(node[i] + sizeof(hdr)); ! 833: - } ! 834: -} ! 835: - ! 836: -main(argc, argv) ! 837: -char **argv; ! 838: -{ ! 839: - if(argc != 2) { ! 840: - fprintf(stderr, "%s: too many arguments\n", argv[1]); ! 841: - exit(1); ! 842: - } ! 843: - init(argv[1]); ! 844: - doit(); ! 845: - exit(0); ! 846: -} ! 847: - ! 848: -shortest(a, b) xbuf *a, *b; ! 849: -{ int n; ! 850: - char *p, *q, *s; ! 851: - p = a->mdata; ! 852: - q = b->mdata; ! 853: - s = shortone.mdata; ! 854: - for(n = 0; n < a->mlen && n < b->mlen; n++, p++, q++) ! 855: - if(*p == *q) ! 856: - *s++ = *p; ! 857: - else break; ! 858: - if(n < a->mlen) { ! 859: - again: ! 860: - if(n + 1 == a->mlen) ! 861: - *s++ = *p; ! 862: - else if(*p + 1 < *q) ! 863: - *s++ = *p + 1; ! 864: - else { ! 865: - *s++ = *p++; ! 866: - n++; ! 867: - if(*p + 1 > *p) ! 868: - *s++ = *p + 1; ! 869: - else goto again; ! 870: - } ! 871: - } ! 872: - shortone.mlen = s - shortone.mdata; ! 873: -} ! 874: -prbuf(x) xbuf *x; ! 875: -{ int i; ! 876: - for(i = 0; i < x->mlen; i++) ! 877: - printf("%3.3o ", x->mdata[i]); ! 878: - putchar('\n'); ! 879: -} ! 880: -fail(s) ! 881: -char *s; ! 882: -{ ! 883: - perror(s); ! 884: - exit(2); ! 885: -} ! 886: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/8/9:btbuild.c\n"}; ! 887: -/*1101000110100100*/ ! 888: //GO.SYSIN DD btbuild.c ! 889: echo btcat.c 1>&2 ! 890: sed 's/.//' >btcat.c <<'//GO.SYSIN DD btcat.c' ! 891: -#include "stdio.h" ! 892: -#include "cbt.h" ! 893: -extern char *malloc(), *realloc(); ! 894: -extern mbuf bkey(); ! 895: -extern bfile *bopen(); ! 896: -int rflag; ! 897: -int rsize = 64; ! 898: -mbuf key, rec; ! 899: -char tabchar = '\t'; ! 900: -main(argc, argv) char **argv; ! 901: -{ ! 902: - rec.mdata = malloc(rsize); ! 903: - key.mdata = malloc(NDSZ); ! 904: - for(argc--, argv++; argc > 0; argc--, argv++) { ! 905: - switch(*argv[0]) { ! 906: - case '-': ! 907: - if(argv[0][1] == 'R') ! 908: - rflag = 1; ! 909: - else fprintf(stderr, "unknown option %s\n", argv[0]); ! 910: - break; ! 911: - default: ! 912: - copy(argv[0]); ! 913: - break; ! 914: - } ! 915: - } ! 916: - exit(0); ! 917: -} ! 918: -copy(s) char *s; ! 919: -{ bfile *bt; ! 920: - int n; ! 921: - bt = bopen(s, 0); ! 922: - if(bt == NULL) { ! 923: - perror(s); ! 924: - exit(1); ! 925: - } ! 926: - if(bfirst(bt) == EOF) { ! 927: - fprintf(stderr, "%s empty\n", s); ! 928: - return; ! 929: - } ! 930: - while((n = breclen(bt)) != EOF) { ! 931: - if(n > rsize) { ! 932: - rsize = n; ! 933: - rec.mdata = realloc(rec.mdata, rsize); ! 934: - } ! 935: - (void) bread(bt, &key, &rec); ! 936: - if(!rflag) { ! 937: - out(key); ! 938: - putchar(tabchar); ! 939: - out(rec); ! 940: - putchar('\n'); ! 941: - } ! 942: - else { ! 943: - fwrite((char *)&key.mlen, 1, sizeof(short), stdout); ! 944: - fwrite(key.mdata, key.mlen, 1, stdout); ! 945: - fwrite((char *)&rec.mlen, 1, sizeof(short), stdout); ! 946: - fwrite(rec.mdata, rec.mlen, 1, stdout); ! 947: - } ! 948: - ! 949: - } ! 950: - bclose(bt); ! 951: -} ! 952: -out(a) mbuf a; ! 953: -{ int i; ! 954: - for(i = 0; i < a.mlen; i++) putchar(*(a.mdata + i)); ! 955: -} ! 956: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/4/8:btcat.c\n"}; ! 957: -/*1110000011011001*/ ! 958: //GO.SYSIN DD btcat.c ! 959: echo btcreat.c 1>&2 ! 960: sed 's/.//' >btcreat.c <<'//GO.SYSIN DD btcreat.c' ! 961: -#include "stdio.h" ! 962: -#include "cbt.h" ! 963: -#define error(x, y) {fprintf(stderr, x, y); exit(1); } ! 964: - ! 965: -int iflag, rflag; ! 966: -char node[NDSZ]; ! 967: -char buf[512]; ! 968: -extern char *malloc(); ! 969: - ! 970: -main(argc, argv) ! 971: -char **argv; ! 972: -{ int i, fd; ! 973: - hdr *b; ! 974: - char *p; ! 975: - for(i = 1; i < argc; i++) { ! 976: - if(argv[i][0] == '-') { ! 977: - for(p = argv[i] + 1; *p; p++) ! 978: - if(*p == 'i') ! 979: - iflag = 1; ! 980: - else if(*p == 'r') ! 981: - rflag = 1; ! 982: - else ! 983: - error("unknown flag %c\n", *p); ! 984: - if(i >= argc - 1) ! 985: - error("file name?", 0); ! 986: - continue; ! 987: - } ! 988: - if(!iflag) { ! 989: - sprintf(buf, "%s.F", argv[i]); ! 990: - if((fd = creat(buf, 0666)) < 0) { ! 991: - perror(buf); ! 992: - exit(1); ! 993: - } ! 994: - close(fd); ! 995: - } ! 996: - sprintf(buf, "%s.T", argv[i]); ! 997: - if((fd = creat(buf, 0666)) < 0) { ! 998: - perror(buf); ! 999: - if(!iflag) { ! 1000: - sprintf(buf, "%s.F", argv[i]); ! 1001: - unlink(buf); ! 1002: - } ! 1003: - exit(1); ! 1004: - } ! 1005: - b = (hdr *)node; ! 1006: - b->kcnt = 0; ! 1007: - if(iflag) ! 1008: - b->htype |= INDEX; ! 1009: - if(rflag) ! 1010: - b->htype |= READONLY; ! 1011: - nfree(b) = NDSZ - sizeof(hdr) - sizeof(trailer); ! 1012: - if(write(fd, node, NDSZ) != NDSZ) ! 1013: - perror("failed"); ! 1014: - close(fd); ! 1015: - } ! 1016: - exit(0); ! 1017: -} ! 1018: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/8/9:btcreat.c\n"}; ! 1019: -/*0011011101111110*/ ! 1020: //GO.SYSIN DD btcreat.c ! 1021: echo btdelete.c 1>&2 ! 1022: sed 's/.//' >btdelete.c <<'//GO.SYSIN DD btdelete.c' ! 1023: -/* read keys from stdin, and delete the records from argv[1] */ ! 1024: -#include "stdio.h" ! 1025: -#include "cbt.h" ! 1026: - ! 1027: -char buf[NDSZ]; ! 1028: -bfile *bf; ! 1029: -mbuf key; ! 1030: - ! 1031: -main(argc, argv) ! 1032: -char **argv; ! 1033: -{ char *p; ! 1034: - int c = 0; ! 1035: - if(argc != 2) { ! 1036: - fprintf(stderr, "usage: delete b-tree < keys\n"); ! 1037: - exit(1); ! 1038: - } ! 1039: - if((bf = bopen(argv[1], 2)) == NULL) { ! 1040: - perror(argv[1]); ! 1041: - exit(1); ! 1042: - } ! 1043: - key.mdata = buf; ! 1044: -loop: ! 1045: - if(c == EOF) { ! 1046: - bclose(bf); ! 1047: - exit(0); ! 1048: - } ! 1049: - for(p = buf; (c = getchar()) != '\n' && c != EOF; *p++ = c) ! 1050: - ; ! 1051: - *p = 0; ! 1052: - key.mlen = p - buf; ! 1053: - if(key.mlen == 0) ! 1054: - goto loop; ! 1055: - if(!bdelete(bf, key)) ! 1056: - fprintf(stderr, "not in file:%s\n", buf); ! 1057: - goto loop; ! 1058: -} ! 1059: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/8/9:btdelete.c\n"}; ! 1060: -/*0010110100010101*/ ! 1061: //GO.SYSIN DD btdelete.c ! 1062: echo btdiag.c 1>&2 ! 1063: sed 's/.//' >btdiag.c <<'//GO.SYSIN DD btdiag.c' ! 1064: -#include "stdio.h" ! 1065: -#include "cbt.h" ! 1066: -#include "sys/types.h" ! 1067: -#include "sys/stat.h" ! 1068: - ! 1069: -extern bfile *bopen(); ! 1070: -extern char *malloc(); ! 1071: -extern int errno; ! 1072: -int errcnt; ! 1073: -char nodes[MXHT + 1][NDSZ]; ! 1074: -int loc[MXHT + 1]; ! 1075: -char *seen; ! 1076: -dkey *curd[MXHT + 1]; ! 1077: -char curkey[MXHT + 1][MAXKLEN]; ! 1078: -int keynum[MXHT + 1]; ! 1079: -mbuf tinykey = { "", 0}; ! 1080: -mbuf giantkey = {"\177\177\177\177", 4}; ! 1081: - ! 1082: -main(argc, argv) ! 1083: -char **argv; ! 1084: -{ bfile *bt; ! 1085: - int n; ! 1086: - if(argc < 2) ! 1087: - error("file name?"); ! 1088: - bt = bopen(argv[1], 0); ! 1089: - if(bt == 0) ! 1090: - error("couldn't open tree"); ! 1091: - n = diagnose(bt); ! 1092: - printf("return value is %d\n", n); ! 1093: - exit(n); ! 1094: -} ! 1095: - ! 1096: -diagnose(b) ! 1097: -bfile *b; ! 1098: -{ int i; ! 1099: - struct stat statb; ! 1100: - if(fstat(b->tfd, &statb) < 0) ! 1101: - error("can't stat tree"); ! 1102: - if(statb.st_size % NDSZ || statb.st_size <= 0) { ! 1103: - printf("tree size %d mod ndsz %d != 0\n", statb.st_size, NDSZ); ! 1104: - errcnt++; ! 1105: - } ! 1106: - if(b->height > MXHT || b->height < 0) { ! 1107: - printf("tree height %d weird max %d\n", b->height, MXHT); ! 1108: - return(-1); ! 1109: - } ! 1110: - seen = malloc(statb.st_size / NDSZ); ! 1111: - for(i = 0; i < statb.st_size/NDSZ; i++) ! 1112: - seen[i] = -1; ! 1113: - lseek(b->tfd, 0, 0); ! 1114: - if((i = read(b->tfd, nodes[b->height], NDSZ)) != NDSZ) { ! 1115: - printf("read of root returned %d (%d)\n", i, errno); ! 1116: - error("can't proceed"); ! 1117: - } ! 1118: - return(dolevel(b->tfd, b->height, tinykey, giantkey) || errcnt); ! 1119: -} ! 1120: - ! 1121: -mbuf ! 1122: -firstkey(n) ! 1123: -{ hdr *b; ! 1124: - mbuf z; ! 1125: - int i; ! 1126: - b = (hdr *)nodes[n]; ! 1127: - keynum[n] = 0; ! 1128: - if(keynum[n] >= b->kcnt) { ! 1129: - z.mlen = -1; ! 1130: - return(z); ! 1131: - } ! 1132: - curd[n] = (dkey *)(b+1); ! 1133: - for(i = 0; i < curd[n]->dlen - DKEYSZ; i++) ! 1134: - curkey[n][i] = curd[n]->dkey[i]; ! 1135: - z.mlen = i; ! 1136: - z.mdata = curkey[n]; ! 1137: - return(z); ! 1138: -} ! 1139: - ! 1140: -mbuf ! 1141: -nextkey(n) ! 1142: -{ mbuf z; ! 1143: - char *p = (char *)curd[n]; ! 1144: - dkey *d; ! 1145: - int i; ! 1146: - hdr *b = (hdr *)nodes[n]; ! 1147: - if(++keynum[n] >= b->kcnt) { ! 1148: - z.mlen = -1; ! 1149: - return(z); ! 1150: - } ! 1151: - p += curd[n]->dlen; ! 1152: - d = curd[n] = (dkey *)p; ! 1153: - z.mdata = curkey[n]; ! 1154: - for(i = 0; i < d->dlen - DKEYSZ; i++) ! 1155: - z.mdata[d->dcom + i] = d->dkey[i]; ! 1156: - z.mlen = i + d->dcom; ! 1157: - return(z); ! 1158: -} ! 1159: - ! 1160: -dolevel(fd, lev, lokey, hikey) ! 1161: -mbuf lokey, hikey; ! 1162: -{ int i, j; ! 1163: - mbuf left, right; ! 1164: - char leftx[MAXKLEN]; ! 1165: - hdr *b = (hdr *)nodes[lev]; ! 1166: - if(lseek(fd, loc[lev] * NDSZ, 0) < 0 || read(fd, nodes[lev], NDSZ) != NDSZ) { ! 1167: - printf("couldn't read node %d, level %d\n", loc[lev], lev); ! 1168: - return(-1); ! 1169: - } ! 1170: - if(seen[loc[lev]] != -1) { ! 1171: - printf("node %d visited twice, at lev %d and %d\n", lev, seen[loc[lev]], lev); ! 1172: - if(lev != seen[loc[lev]]) ! 1173: - return(-1); ! 1174: - } ! 1175: - else ! 1176: - seen[loc[lev]] = lev; ! 1177: - if(check(loc[lev], nodes[lev], lokey, hikey)) ! 1178: - return(-1); ! 1179: - if(lev == 0) ! 1180: - return(0); ! 1181: - right = firstkey(lev); ! 1182: - left.mlen = lokey.mlen; ! 1183: - left.mdata = leftx; ! 1184: - for(j = 0; j < left.mlen; j++) ! 1185: - left.mdata[j] = lokey.mdata[j]; ! 1186: - for(i = 0; i < b->kcnt; i++) { ! 1187: - loc[lev - 1] = *ndadr(b, i); ! 1188: - if(dolevel(fd, lev - 1, left, right)) ! 1189: - return(-1); ! 1190: - left.mlen = right.mlen; ! 1191: - for(j = 0; j < left.mlen; j++) ! 1192: - left.mdata[j] = right.mdata[j]; ! 1193: - right = nextkey(lev); ! 1194: - if(right.mlen < 0) ! 1195: - printf("unexpected end of keys, node %d\n", loc[lev]); ! 1196: - } ! 1197: - loc[lev - 1] = *ndadr(b, i); ! 1198: - return(dolevel(fd, lev - 1, left, hikey)); ! 1199: -} ! 1200: - ! 1201: -check(noden, b, lokey, hikey) ! 1202: -hdr *b; ! 1203: -mbuf lokey, hikey; ! 1204: -{ int i, plen, sz, j; ! 1205: - char *p, prefix[MAXKLEN]; ! 1206: - dkey *d; ! 1207: - ! 1208: - /* check space allocation */ ! 1209: - sz = sizeof(hdr) + sizeof(trailer) + nfree(b); ! 1210: - if(nfree(b) < 0) { ! 1211: - printf("nfree: %d < 0, node %d\n", nfree(b), noden); ! 1212: - errcnt++; ! 1213: - } ! 1214: - if(sz > NDSZ) { ! 1215: - printf("nfree: %d impossibly large, node %d\n", nfree(b), noden); ! 1216: - errcnt++; ! 1217: - } ! 1218: - if(b->kcnt < 0) { ! 1219: - printf("kcnt %d < 0, node %d\n", b->kcnt, noden); ! 1220: - return(-1); ! 1221: - } ! 1222: - p = (char *)(b+1); ! 1223: - for(i = 0; i < b->kcnt; i++) { ! 1224: - d = (dkey *)p; ! 1225: - if(d->dlen < DKEYSZ) { ! 1226: - printf("node %d, key %d, dlen %d too small\n", noden, i, d->dlen); ! 1227: - return(-1); ! 1228: - } ! 1229: - if(b->hlev) ! 1230: - sz += sizeof(ndaddr); ! 1231: - else if(!(b->htype & INDEX)) ! 1232: - sz += sizeof(lfaddr); ! 1233: - if((sz += d->dlen) > NDSZ) { ! 1234: - printf("node %d, contents too large\n", noden); ! 1235: - return(-1); ! 1236: - } ! 1237: - p += d->dlen; ! 1238: - } ! 1239: - if(b->hlev) ! 1240: - sz += sizeof(ndaddr); ! 1241: - if(sz != NDSZ) { ! 1242: - printf("node %d, size %d ndsz %d\n", noden, sz, NDSZ); ! 1243: - return(-1); ! 1244: - } ! 1245: - /* check key ordering */ ! 1246: - p = (char *)(b + 1); ! 1247: - d = (dkey *)p; ! 1248: - if(d->dcom != 0) { ! 1249: - printf("node %d first key has dcom %d > 0\n", noden, d->dcom); ! 1250: - return(-1); ! 1251: - } ! 1252: - plen = lokey.mlen; ! 1253: - for(i = 0; i < plen; i++) ! 1254: - prefix[i] = lokey.mdata[i]; ! 1255: - for(i = 0; i < b->kcnt; i++) { ! 1256: - if(d->dcom > plen) { ! 1257: - printf("node %d key %d, dcom %d bigger than len %d of prev key\n", ! 1258: - noden, i, d->dcom, plen); ! 1259: - return(-1); ! 1260: - } ! 1261: - for(j = 0; j < d->dlen - DKEYSZ; j++) { ! 1262: - if(j + d->dcom > plen) ! 1263: - break; ! 1264: - if(d->dkey[j] < prefix[d->dcom + j]) { ! 1265: - printf("node %d, key %d out of order\n", ! 1266: - noden, i); ! 1267: - errcnt++; ! 1268: - break; ! 1269: - } ! 1270: - else if(d->dkey[j] == prefix[d->dcom + j]) ! 1271: - continue; ! 1272: - else ! 1273: - break; ! 1274: - } ! 1275: - for(j = 0; j < d->dlen - DKEYSZ; j++) ! 1276: - prefix[j + d->dcom] = d->dkey[j]; ! 1277: - plen = j + d->dcom; ! 1278: - } ! 1279: - for(i = 0; i < plen && i < hikey.mlen; i++) { ! 1280: - if(prefix[i] < hikey.mdata[i]) ! 1281: - return(0); ! 1282: - else if(prefix[i] == hikey.mdata[i]) ! 1283: - continue; ! 1284: - printf("node %d last key too large pref %s, hi %s\n", noden, prefix, hikey.mdata); ! 1285: - return(-1); ! 1286: - } ! 1287: - if(plen > hikey.mlen) { ! 1288: - printf("node %d last key too large plen %d, hikey.len %d\n", noden, plen, hikey.mlen); ! 1289: - return(-1); ! 1290: - } ! 1291: - return(0); ! 1292: -} ! 1293: - ! 1294: -error(s) ! 1295: -char *s; ! 1296: -{ ! 1297: - printf("%s\n", s); ! 1298: - exit(1); ! 1299: -} ! 1300: -static struct D { struct D *a; char *b;} VER = {&VER,"\n82/10/9:btdiag.c\n"}; ! 1301: -/*1100001011001101*/ ! 1302: //GO.SYSIN DD btdiag.c ! 1303: echo btexer.c 1>&2 ! 1304: sed 's/.//' >btexer.c <<'//GO.SYSIN DD btexer.c' ! 1305: -#include "cbt.h" ! 1306: -extern char *malloc(); ! 1307: - ! 1308: -bfile *bt; ! 1309: -mbuf *key; ! 1310: -char *state; ! 1311: -#define IN 1 ! 1312: -#define OUT 2 ! 1313: -int cnt, keysz; ! 1314: -char *buf; ! 1315: -char cmdbuf[128]; ! 1316: -mbuf rec = {"", 0}; ! 1317: -extern char *outkey(); ! 1318: -char *filename; ! 1319: - ! 1320: -main(argc, argv) ! 1321: -char **argv; ! 1322: -{ int i; ! 1323: - if(argc != 3) ! 1324: - error("usage: file key-cnt"); ! 1325: - bt = bopen(filename = argv[1], 2); ! 1326: - if(bt == 0) ! 1327: - error("bopen"); ! 1328: - sprintf(cmdbuf, "btdiag %s", argv[1]); ! 1329: - cnt = atoi(argv[2]); ! 1330: - printf("cnt = %d\n", cnt); ! 1331: - key = (mbuf *)malloc(cnt * sizeof(mbuf)); ! 1332: - keysz = NDSZ/5; ! 1333: - if(keysz > MAXKLEN) ! 1334: - keysz = MAXKLEN; ! 1335: - printf("keysz %d\n", keysz); ! 1336: - buf = malloc((keysz + 1) * cnt); ! 1337: - state = malloc(cnt); ! 1338: - if(buf == 0 || state == 0) ! 1339: - error("key malloc"); ! 1340: - for(i = 0; i < cnt; i++) ! 1341: - state[i] = OUT; ! 1342: - for(i = 0; i < cnt; i++) ! 1343: - key[i].mlen = keysz; ! 1344: - for(i = 0; i < cnt; i++) ! 1345: - key[i].mdata = buf + i * (keysz + 1); ! 1346: - srand(0); ! 1347: - for(i = 0; i < cnt * (keysz + 1); i++) ! 1348: - buf[i] = rand() % 94 + ' ' + 1; ! 1349: - for(i = 0; i < cnt; i++) ! 1350: - buf[i * (keysz + 1) + keysz] = 0; ! 1351: - doit(); ! 1352: - printf("sbrk %d\n", sbrk(0)); ! 1353: - exit(0); ! 1354: -} ! 1355: - ! 1356: -doit() ! 1357: -{ ! 1358: - allin(); ! 1359: - test("allin ok\n"); ! 1360: - checkseek(); ! 1361: - out(500); ! 1362: - test("out 500 ok\n"); ! 1363: - checkseek(); ! 1364: - in(500); ! 1365: - test("in 500 ok\n"); ! 1366: - checkseek(); ! 1367: - out(700); ! 1368: - test("out 700 ok\n"); ! 1369: - checkseek(); ! 1370: - in(700); ! 1371: - test("in 700 ok\n"); ! 1372: - checkseek(); ! 1373: - out(1000); ! 1374: - test("out 1000 ok\n"); ! 1375: - checkseek(); ! 1376: - in(100); ! 1377: - test("in 100 ok\n"); ! 1378: - checkseek(); ! 1379: - in(200); ! 1380: - test("in 200 ok\n"); ! 1381: - checkseek(); ! 1382: - in(300); ! 1383: - test("in 300 ok\n"); ! 1384: - checkseek(); ! 1385: -} ! 1386: - ! 1387: -test(s) ! 1388: -char *s; ! 1389: -{ int n; ! 1390: - bclose(bt); ! 1391: - n = system(cmdbuf); ! 1392: - if(n) { ! 1393: - printf("%s returned %d\n", cmdbuf, n); ! 1394: - exit(1); ! 1395: - } ! 1396: - else ! 1397: - printf(s); ! 1398: - bt = bopen(filename, 2); ! 1399: - if(bt == NULL) ! 1400: - error(filename); ! 1401: -} ! 1402: - ! 1403: -error(s) ! 1404: -char *s; ! 1405: -{ ! 1406: - perror(s); ! 1407: - exit(1); ! 1408: -} ! 1409: - ! 1410: -allin() ! 1411: -{ int i; ! 1412: - for(i = 0; i < cnt; i++) { ! 1413: - if(state[i] == IN) ! 1414: - continue; ! 1415: - if(bwrite(bt, key[i], rec) == EOF) ! 1416: - printf("write error %d on key %d\n", errno, i); ! 1417: - else ! 1418: - state[i] = IN; ! 1419: - } ! 1420: -} ! 1421: - ! 1422: -in(n) ! 1423: -{ int i; ! 1424: - for(i = 0; i < cnt; i++) { ! 1425: - if(state[i] == IN || (rand() % 1007) >= n) ! 1426: - continue; ! 1427: - else if(bwrite(bt, key[i], rec) == EOF) ! 1428: - printf("write error %d on key %d\n", errno, i); ! 1429: - else ! 1430: - state[i] = IN; ! 1431: - } ! 1432: -} ! 1433: - ! 1434: -out(n) ! 1435: -{ int i, count = 0; ! 1436: - for(i = 0; i < cnt; i++) { ! 1437: - if(state[i] == OUT || (rand() % 1007) >= n) ! 1438: - continue; ! 1439: - if(bdelete(bt, key[i], rec) != 1) { ! 1440: - printf("bdelete error %d on key %s\n", errno, outkey(i)); ! 1441: - printf("out(%d) deleted %d\n", n, count); ! 1442: - bflush(bt); ! 1443: - exit(1); ! 1444: - } ! 1445: - else if(bt->fatal) ! 1446: - printf("set fatal flag, bdelete key %d %s err %d\n", i, outkey(i), errno); ! 1447: - else { ! 1448: - count++; ! 1449: - state[i] = OUT; ! 1450: - } ! 1451: - } ! 1452: -} ! 1453: - ! 1454: -checkseek() ! 1455: -{ int i, j, count = 0; ! 1456: - mbuf x; ! 1457: - printf("\tcheckseek"); ! 1458: - for(i = 0; i < cnt; i++) { ! 1459: - if(state[i] == OUT) ! 1460: - continue; ! 1461: - if(bseek(bt, key[i]) != FOUND) { ! 1462: - printf("sought key %s, not found\n", key[i].mdata); ! 1463: - continue; ! 1464: - } ! 1465: - x = bkey(bt); ! 1466: - for(j = 0; j < keysz; j++) ! 1467: - if(key[i].mdata[j] != x.mdata[j]) { ! 1468: - printf("bkey mismatch at key %d\n", i); ! 1469: - break; ! 1470: - } ! 1471: - count++; ! 1472: - } ! 1473: - printf(" saw %d\n", count); ! 1474: -} ! 1475: - ! 1476: -char * ! 1477: -outkey(n) ! 1478: -{ static char kb[MAXKLEN + 1]; ! 1479: - int i; ! 1480: - strncpy(kb, key[n].mdata, keysz); ! 1481: - return(kb); ! 1482: -} ! 1483: -static struct D { struct D *a; char *b;} VER = {&VER,"\n82/10/9:btexer.c\n"}; ! 1484: -/*1101101100011000*/ ! 1485: //GO.SYSIN DD btexer.c ! 1486: echo btran.c 1>&2 ! 1487: sed 's/.//' >btran.c <<'//GO.SYSIN DD btran.c' ! 1488: -#include "stdio.h" ! 1489: -#define MAX 8192 ! 1490: -char tab = '\t'; ! 1491: -char *line, *oline; ! 1492: -char abuf[MAX], bbuf[MAX]; ! 1493: -int cnt, ocnt; ! 1494: -main() ! 1495: -{ long lcnt = 0; ! 1496: - line = abuf; ! 1497: - oline = bbuf; ! 1498: - for(; !feof(stdin); ) { ! 1499: - lcnt++; ! 1500: - (void) fgets(line, MAX, stdin); ! 1501: - if(feof(stdin)) cnt = 0; ! 1502: - else cnt = strlen(line); ! 1503: - if(cnt >= MAX-1) { ! 1504: - fprintf(stderr, "line %ld too long\n", lcnt); ! 1505: - cnt = 0; ! 1506: - } ! 1507: - output(); ! 1508: - } ! 1509: - exit(0); ! 1510: -} ! 1511: -output() ! 1512: -{ unsigned short u; ! 1513: - char *p; ! 1514: - if(ocnt <= 1) { /* oline was used to give ooline a newline */ ! 1515: - swtch(); ! 1516: - return; ! 1517: - } ! 1518: - if(cnt != 1) /* line isnt a newline to be added to oline */ ! 1519: - oline[--ocnt] = 0; ! 1520: - else oline[ocnt] = 0; ! 1521: - for(p = oline; *p && *p != tab; p++); ! 1522: - u = p - oline; ! 1523: - (void) fwrite((char *)&u, 1, sizeof(u), stdout); ! 1524: - (void) fwrite(oline, (int)u, 1, stdout); ! 1525: - if(*p == tab) ! 1526: - p++; ! 1527: - if(oline + ocnt - p < 0) ! 1528: - u = 0; ! 1529: - else u = oline + ocnt - p; ! 1530: - (void) fwrite((char *)&u, 1, sizeof(u), stdout); ! 1531: - (void) fwrite(p, (int)u, 1, stdout); ! 1532: - swtch(); ! 1533: -} ! 1534: -swtch() ! 1535: -{ char *x; ! 1536: - x = line; ! 1537: - line = oline; ! 1538: - oline = x; ! 1539: - ocnt = cnt; ! 1540: -} ! 1541: -static char VER[] = "\n80/2/13:btran.c\n"; ! 1542: -/*1111100011110011*/ ! 1543: //GO.SYSIN DD btran.c ! 1544: echo btreport.c 1>&2 ! 1545: sed 's/.//' >btreport.c <<'//GO.SYSIN DD btreport.c' ! 1546: -#include "stdio.h" ! 1547: -#include "cbt.h" ! 1548: -#include "sys/types.h" ! 1549: -#include "sys/stat.h" ! 1550: -extern bfile *bopen(); ! 1551: - ! 1552: -long ndcnt[MXHT + 1]; ! 1553: -long frcnt, reccnt, reclen; ! 1554: -bfile *bt; ! 1555: - ! 1556: -main(argc, argv) ! 1557: -char **argv; ! 1558: -{ int i, j; ! 1559: - for(i = 1; i < argc; i++) { ! 1560: - doarg(argv[i]); ! 1561: - for(j = 0; j <= MXHT; j++) ! 1562: - ndcnt[j] = 0; ! 1563: - frcnt = reccnt = reclen = 0; ! 1564: - if(i+1 < argc) ! 1565: - putchar('\n'); ! 1566: - } ! 1567: - exit(0); ! 1568: -} ! 1569: - ! 1570: -doarg(s) ! 1571: -char *s; ! 1572: -{ struct stat statbuf; ! 1573: - long x; ! 1574: - int i; ! 1575: - bt = bopen(s, 0); ! 1576: - if(bt == NULL) { ! 1577: - i = strlen(s); ! 1578: - if(s[i-2] == '.') { ! 1579: - s[i-2] = 0; ! 1580: - if(s[i-1] == 'F') ! 1581: - return; ! 1582: - if(s[i-1] == 'T') ! 1583: - bt = bopen(s, 0); ! 1584: - } ! 1585: - if(bt == NULL) { ! 1586: - perror(s); ! 1587: - return; ! 1588: - } ! 1589: - } ! 1590: - fstat(bt->tfd, &statbuf); ! 1591: - printf("%s.T %ld bytes", s, statbuf.st_size); ! 1592: - if(bt->dfd > 0 && fstat(bt->dfd, &statbuf) == 0) ! 1593: - printf(", %s.F %ld bytes", s, statbuf.st_size); ! 1594: - putchar('\n'); ! 1595: - donode((ndaddr)0); ! 1596: - for(x = i = 0; i <= MXHT; i++) ! 1597: - x += ndcnt[i] * NDSZ; ! 1598: - printf("%ld bytes used in tree\n", x); ! 1599: - for(i = 0; i <= bt->height; i++) ! 1600: - printf(" %ld nodes at level %d", ndcnt[i], i); ! 1601: - printf("\n%ld bytes free\n", frcnt); ! 1602: - printf("%ld records totalling %ld bytes\n", reccnt, reclen); ! 1603: - bclose(bt); ! 1604: -} ! 1605: - ! 1606: -/* this routine believes the tree is well-formed */ ! 1607: -donode(n) ! 1608: -ndaddr n; ! 1609: -{ char buf[NDSZ]; ! 1610: - hdr *b = (hdr *)buf; ! 1611: - int i; ! 1612: - (void) lseek(bt->tfd, (long)NDSZ * n, 0); ! 1613: - i = read(bt->tfd, buf, NDSZ); ! 1614: - if(i != NDSZ) { ! 1615: - printf("btreport: attempt to read node %d failed\n", n); ! 1616: - perror("breport"); ! 1617: - exit(1); ! 1618: - } ! 1619: - ndcnt[b->hlev]++; ! 1620: - frcnt += nfree(b); ! 1621: - if(b->hlev) ! 1622: - for(i = 0; i <= b->kcnt; i++) ! 1623: - donode(*ndadr(b, i)); ! 1624: - else ! 1625: - for(i = 0; i < b->kcnt; i++) { ! 1626: - reccnt++; ! 1627: - if(!(b->htype & INDEX)) ! 1628: - reclen += lfadr(b, i)->llen; ! 1629: - } ! 1630: -} ! 1631: -static struct D { struct D *a; char *b;} VER = {&VER,"\n86/8/12:btreport.c\n"}; ! 1632: //GO.SYSIN DD btreport.c ! 1633: echo btsquash.c 1>&2 ! 1634: sed 's/.//' >btsquash.c <<'//GO.SYSIN DD btsquash.c' ! 1635: -#include "stdio.h" ! 1636: -#include "cbt.h" ! 1637: - ! 1638: -extern int errno; ! 1639: -mbuf key, value; ! 1640: -char kbuf[NDSZ], vbuf[32767]; ! 1641: -bfile *bfd; ! 1642: -FILE *pfd; ! 1643: -extern FILE *popen(); ! 1644: -char iflag, rflag; ! 1645: - ! 1646: -main(argc, argv) ! 1647: -char **argv; ! 1648: -{ ! 1649: - if(argc != 2) { ! 1650: - fprintf(stderr, "usage; %s file-name\n", argv[0]); ! 1651: - exit(1); ! 1652: - } ! 1653: - bfd = bopen(argv[1], 0); ! 1654: - if(bfd == NULL) ! 1655: - fail(argv[1]); ! 1656: - strcpy(vbuf, "cbt creat "); ! 1657: - if(bfd->path[0]->htype & INDEX) { ! 1658: - iflag = 1; ! 1659: - strcat(vbuf, "-i "); ! 1660: - } ! 1661: - if(bfd->path[0]->htype & READONLY) { ! 1662: - rflag = 1; ! 1663: - strcat(vbuf, "-r"); ! 1664: - } ! 1665: - sprintf(kbuf, "%s TS%d", vbuf, getpid()); ! 1666: - if(system(kbuf) != 0) { ! 1667: - fprintf(stderr, "%s failed\n", kbuf); ! 1668: - exit(1); ! 1669: - } ! 1670: - /* this refers to the installed version? */ ! 1671: - sprintf(kbuf, "cbt build -r TS%d", getpid()); ! 1672: - pfd = popen(kbuf, "w"); ! 1673: - if(pfd == NULL) ! 1674: - fail(kbuf); ! 1675: - key.mdata = kbuf; ! 1676: - value.mdata = vbuf; ! 1677: - errno = 0; ! 1678: - while(bread(bfd, &key, &value) != EOF) { ! 1679: - (void) fwrite((char *)&key.mlen, 1, sizeof(key.mlen), pfd); ! 1680: - (void) fwrite(key.mdata, 1, key.mlen, pfd); ! 1681: - (void) fwrite((char *)&value.mlen, 1, sizeof(value.mlen), pfd); ! 1682: - (void) fwrite(value.mdata, 1, value.mlen, pfd); ! 1683: - if(ferror(pfd)) ! 1684: - fail("write to build"); ! 1685: - } ! 1686: - if(errno) ! 1687: - fail("extracting"); ! 1688: - if(pclose(pfd) != 0) ! 1689: - fail("pipe close"); ! 1690: - sprintf(kbuf, "%s.T", argv[1]); ! 1691: - sprintf(vbuf, "TS%d.T", getpid()); ! 1692: - unlink(kbuf); ! 1693: - link(vbuf, kbuf); ! 1694: - if(iflag) ! 1695: - exit(0); ! 1696: - sprintf(kbuf, "%s.F", argv[1]); ! 1697: - sprintf(vbuf, "TS%d.F", getpid()); ! 1698: - unlink(kbuf); ! 1699: - link(vbuf, kbuf); ! 1700: - if(errno) ! 1701: - perror("linking"); ! 1702: - exit(0); ! 1703: -} ! 1704: - ! 1705: -fail(s) ! 1706: -char *s; ! 1707: -{ ! 1708: - perror(s); ! 1709: - exit(2); ! 1710: -} ! 1711: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/4/26:btsquash.c\n"}; ! 1712: -/*0100011001101001*/ ! 1713: //GO.SYSIN DD btsquash.c ! 1714: echo bttest.c 1>&2 ! 1715: sed 's/.//' >bttest.c <<'//GO.SYSIN DD bttest.c' ! 1716: -#include "stdio.h" ! 1717: -#include "cbt.h" ! 1718: -extern char *malloc(); ! 1719: -extern bfile *bopen(); ! 1720: -extern mbuf bkey(); ! 1721: -extern long lseek(); ! 1722: - ! 1723: -char *onearg(); ! 1724: -mbuf key, value; ! 1725: -bfile *it; ! 1726: -#define OPEN 1 ! 1727: -#define CLOSE 2 ! 1728: -#define SEEK 3 ! 1729: -#define FIRST 4 ! 1730: -#define NEXT 5 ! 1731: -#define WRITE 6 ! 1732: -#define BT 7 ! 1733: -#define LEV 8 ! 1734: -#define NODE 9 ! 1735: -#define KEY 10 ! 1736: -#define FLUSH 11 ! 1737: -#define COMMIT 12 ! 1738: -#define SHELL 13 ! 1739: -#define DELETE 14 ! 1740: -#define START 15 ! 1741: -#define CHECK 16 ! 1742: -struct cmd ! 1743: -{ int cmt, cln; ! 1744: - char *ccm; ! 1745: -} cmnd[] = ! 1746: -{ {OPEN, 4, "open"}, ! 1747: - {CLOSE, 5, "close"}, ! 1748: - {SHELL, 1, "!"}, ! 1749: - {DELETE, 6, "delete"}, ! 1750: - {SEEK, 4, "seek"}, ! 1751: - {FIRST, 5, "first"}, ! 1752: - {NEXT, 4, "next"}, ! 1753: - {NEXT, 4, "read"}, ! 1754: - {WRITE, 5, "write"}, ! 1755: - {CHECK, 5, "check"}, ! 1756: - {BT, 2, "bt"}, ! 1757: - {LEV, 3, "lev"}, ! 1758: - {NODE, 4, "node"}, ! 1759: - {KEY, 3, "key"}, ! 1760: - {FLUSH, 5, "flush"}, ! 1761: - {COMMIT, 6, "commit"}, ! 1762: - {START, 5, "start"}, ! 1763: - {START, 7, "trstart"}, ! 1764: - {0, 0, 0} ! 1765: -}; ! 1766: -char line[128]; ! 1767: -char ndbuf[512]; ! 1768: -main() ! 1769: -{ ! 1770: - int n; ! 1771: - char *s, *p; ! 1772: - key.mdata = malloc(200); ! 1773: - value.mdata = malloc(200); ! 1774: - for(;;) { ! 1775: - for(n = 0; n < sizeof(line); n++) ! 1776: - line[n] = 0; ! 1777: - (void) fgets(line, sizeof(line), stdin); ! 1778: - if(feof(stdin)) break; ! 1779: - switch(cmtp(line)) { ! 1780: - default: ! 1781: - printf("?\n"); ! 1782: - break; ! 1783: - case CLOSE: ! 1784: - bclose(it); ! 1785: - break; ! 1786: - case SHELL: ! 1787: - (void) system(line); ! 1788: - printf("!\n"); ! 1789: - break; ! 1790: - case START: ! 1791: - /* printf("%d\n", trstart()); */ ! 1792: - break; ! 1793: - case COMMIT: ! 1794: - /* btcommit(); */ ! 1795: - break; ! 1796: - case FLUSH: ! 1797: - bflush(it); ! 1798: - break; ! 1799: - case OPEN: ! 1800: - s = onearg(line); ! 1801: - it = bopen(s, 2); ! 1802: - if(it == NULL || errno) ! 1803: - { perror(s); ! 1804: - } ! 1805: - break; ! 1806: - case DELETE: ! 1807: - s = onearg(line); ! 1808: - if(s[strlen(s)-1] == '\n') ! 1809: - s[strlen(s)-1] = 0; ! 1810: - todatum(s, &key); ! 1811: - printf("%d\n", bdelete(it, key)); ! 1812: - break; ! 1813: - case SEEK: ! 1814: - s = onearg(line); ! 1815: - if(s[strlen(s)-1] == '\n') ! 1816: - s[strlen(s)-1] = 0; ! 1817: - todatum(s, &key); ! 1818: - printf("%d\n", bseek(it, key)); ! 1819: - break; ! 1820: - case FIRST: ! 1821: - printf("%d\n", bfirst(it)); ! 1822: - break; ! 1823: - case NEXT: ! 1824: - printf("%d - ", bread(it, &key, &value)); ! 1825: - prbuf(value); ! 1826: - printf(" | "); ! 1827: - prbuf(key); ! 1828: - putchar('\n'); ! 1829: - break; ! 1830: - case WRITE: ! 1831: - twoarg(line, &s, &p); ! 1832: - todatum(s, &key); ! 1833: - todatum(p, &value); ! 1834: - printf("%d\n", bwrite(it, key, value)); ! 1835: - break; ! 1836: - case BT: ! 1837: - prbt(it); ! 1838: - break; ! 1839: - case LEV: ! 1840: - (void) sscanf(line, "%d", &n); ! 1841: - if(n < 0 || n > it->height) ! 1842: - { printf("out of range\n"); ! 1843: - break; ! 1844: - } ! 1845: - tprnode(it->path[n]); ! 1846: - break; ! 1847: - case NODE: ! 1848: - (void) sscanf(line, "%d", &n); ! 1849: - (void) lseek(it->tfd, (long)n*NDSZ, 0); ! 1850: - (void) read(it->tfd, ndbuf, NDSZ); ! 1851: - tprnode((hdr *)ndbuf); ! 1852: - break; ! 1853: - case CHECK: ! 1854: - (void) sscanf(line, "%d", &n); ! 1855: - (void) lseek(it->tfd, (long)n * NDSZ, 0); ! 1856: - (void) read(it->tfd, ndbuf, NDSZ); ! 1857: - checknode((hdr *)ndbuf); ! 1858: - break; ! 1859: - case KEY: ! 1860: - printf("%d ", breclen(it)); ! 1861: - prbuf(bkey(it)); ! 1862: - putchar('\n'); ! 1863: - break; ! 1864: - } ! 1865: - } ! 1866: - exit(0); ! 1867: -} ! 1868: -cmtp(s) char *s; ! 1869: -{ struct cmd *p; ! 1870: - int i; ! 1871: - for(p=cmnd; p->cln != 0; p++) ! 1872: - if(strncmp(s, p->ccm, p->cln) == 0) ! 1873: - { for(i=0; i<p->cln; i++) ! 1874: - line[i] =' '; ! 1875: - return(p->cmt); ! 1876: - } ! 1877: - return(-1); ! 1878: -} ! 1879: -char *onearg(s) char *s; ! 1880: -{ char *p, *q; ! 1881: - for(p=s; *p == ' '; p++); ! 1882: - for(q=p; *q && *q!='\n'; q++); ! 1883: - *q = 0; ! 1884: - return(p); ! 1885: -} ! 1886: -todatum(s, k) char *s; mbuf *k; ! 1887: -{ int i; ! 1888: - k->mlen = strlen(s); ! 1889: - if(s[k->mlen - 1] == '\n') ! 1890: - k->mlen--; ! 1891: - for(i=0; i<k->mlen; i++) ! 1892: - k->mdata[i] = s[i]; ! 1893: -} ! 1894: -twoarg(a, b, c) char *a, **b, **c; ! 1895: -{ char *p, *q; ! 1896: - for(; *a==' '; a++); ! 1897: - for(p=a; *p && *p!='\t'; p++); ! 1898: - *p++ = 0; ! 1899: - for(q=p; *q && *q!='\n'; q++); ! 1900: - *q = 0; ! 1901: - *b = a; ! 1902: - *c = p; ! 1903: -} ! 1904: -prbuf(a) mbuf a; ! 1905: -{ int i; ! 1906: - printf("%d:", a.mlen); ! 1907: - for(i=0; i<a.mlen; i++) ! 1908: - putchar(a.mdata[i]); ! 1909: -} ! 1910: -prbt(a) bfile *a; ! 1911: -{ int i; ! 1912: - printf("ht %d adv %d rdw %d flags ", a->height, a->advnc, ! 1913: - a->rdwrt); ! 1914: - for(i = 0; i <= MXHT; i++) ! 1915: - printf(" %d", a->flag[i]); ! 1916: - putchar('\n'); ! 1917: - printf("nodes "); ! 1918: - for(i = 0; i <= MXHT; i++) ! 1919: - printf(" %d", a->loc[i]); ! 1920: - putchar('\n'); ! 1921: - printf("rdkey #%d:", a->rdptr.rnum); ! 1922: - printf(":\n"); ! 1923: -} ! 1924: -tprnode(a) hdr *a; ! 1925: -{ int i; ! 1926: - dkey *q; ! 1927: - prhdr(a); ! 1928: - q = (dkey *)(a+1); ! 1929: - for(i = 0; i < a->kcnt; i++) { ! 1930: - if(a->hlev == 0) ! 1931: - prlfa(lfadr(a, i)); ! 1932: - else prnda(ndadr(a, i)); ! 1933: - prkey(q); ! 1934: - q = (dkey *)((char *)q + q->dlen); ! 1935: - } ! 1936: - if(a->hlev) ! 1937: - prnda(ndadr(a, i)); ! 1938: - putchar('\n'); ! 1939: -} ! 1940: -checknode(a) ! 1941: -hdr *a; ! 1942: -{ int i; ! 1943: - char *p; ! 1944: - for(i = 0, p = (char *)(a + 1); i < a->kcnt; i++) ! 1945: - p += *p; ! 1946: - i = p - (char *)a + nfree(a) + sizeof(trailer); ! 1947: - if(a->hlev) ! 1948: - i += (a->kcnt + 1) * sizeof(ndaddr); ! 1949: - else if(!treeonly(it)) ! 1950: - i += a->kcnt * sizeof(lfaddr); ! 1951: - if(i == NDSZ) { ! 1952: - printf("ok\n"); ! 1953: - return; ! 1954: - } ! 1955: - printf("nfree should be %d not %d\n", NDSZ - i + nfree(a), ! 1956: - nfree(a)); ! 1957: -} ! 1958: -prhdr(a) hdr *a; ! 1959: -{ ! 1960: - printf("stamp %ld kcnt %d type %d lev %d free %d\n", ! 1961: - a->hstamp, a->kcnt, a->htype, a->hlev, nfree(a)); ! 1962: -} ! 1963: -prlfa(a) lfaddr *a; ! 1964: -{ ! 1965: - if(treeonly(it)) ! 1966: - printf("\t"); ! 1967: - else ! 1968: - printf("%ld %u\t", a->lloc, a->llen); ! 1969: -} ! 1970: -prnda(a) ndaddr *a; ! 1971: -{ ! 1972: - printf("%u\t", *a); ! 1973: -} ! 1974: -prkey(b) dkey *b; ! 1975: -{ int i; ! 1976: - for(i = 0; i < b->dcom; i++) ! 1977: - putchar(' '); ! 1978: - for(i = 0; i < b->dlen - DKEYSZ; i++) ! 1979: - putchar(b->dkey[i]); ! 1980: - putchar('\n'); ! 1981: -} ! 1982: -static struct D { struct D *a; char *b;} VER = {&VER,"\n82/10/9:bttest.c\n"}; ! 1983: -/*0111000111010001*/ ! 1984: //GO.SYSIN DD bttest.c ! 1985: echo bwrite.c 1>&2 ! 1986: sed 's/.//' >bwrite.c <<'//GO.SYSIN DD bwrite.c' ! 1987: -#include "cbt.h" ! 1988: -#include "pr.h" ! 1989: - ! 1990: -typedef union { ! 1991: - ndaddr na; ! 1992: - lfaddr la; ! 1993: -} addr; ! 1994: -static char splitting[MXHT+1]; ! 1995: -extern bfile *curbf; ! 1996: -extern ndaddr oldnode(), newnode(); ! 1997: -extern char *malloc(); ! 1998: - ! 1999: -extern long brecwrite(); ! 2000: - ! 2001: -bwrite(bf, key, rec) mbuf key, rec; bfile *bf; ! 2002: -{ addr u; ! 2003: - int n; ! 2004: - if(bf == NULL) ! 2005: - return(EOF); ! 2006: - if(!bf->rdwrt) { ! 2007: - errno = BNOWRITE; ! 2008: - return(EOF); ! 2009: - } ! 2010: - if(notran(bf)) ! 2011: - return(EOF); ! 2012: - if(key.mlen > MAXKLEN) ! 2013: - return(EOF); ! 2014: - if(!treeonly(bf)) { ! 2015: - u.la.llen = rec.mlen; ! 2016: - u.la.lloc = brecwrite(rec); ! 2017: - if(u.la.lloc == EOF) ! 2018: - return(EOF); ! 2019: - } ! 2020: - if(desce(bf, key, (private *)NULL) == EOF) ! 2021: - return(EOF); ! 2022: - n = xinsert(0, key, u); ! 2023: - (void) bseek(bf, key); ! 2024: - return(n); ! 2025: -} ! 2026: - ! 2027: -fixpath(bf) ! 2028: -bfile *bf; ! 2029: -{ addr u; ! 2030: - hdr *b; ! 2031: - int i, n, j; ! 2032: - for(i = 0; i < bf->height; i++) { ! 2033: - if(!mustwrite(bf, i)) ! 2034: - continue; ! 2035: - n = bf->loc[i]; ! 2036: - if((u.na = oldnode(i)) == EOF) ! 2037: - return(EOF); ! 2038: - b = bf->path[i+1]; ! 2039: - for(j = 0; j <= b->kcnt; j++) ! 2040: - if(*ndadr(b, j) == n) ! 2041: - break; ! 2042: - if(j > b->kcnt){ /* curtains, the parent doesn't point to us */ ! 2043: - errno = BFATAL; ! 2044: - return(EOF); ! 2045: - } ! 2046: - *ndadr(b, j) = u.na; ! 2047: - mustwrite(bf, i + 1) = 1; ! 2048: - } ! 2049: - return(0); ! 2050: -} ! 2051: - ! 2052: -xinsert(lev, key, u) mbuf key; addr u; ! 2053: -{ private x; ! 2054: - int n, dellen; ! 2055: - hdr *b = curbf->path[lev]; ! 2056: - char ba[NDSZ], bb[NDSZ]; ! 2057: - dkey *dx, *dy; ! 2058: - if(splitting[lev]) ! 2059: - if(desce(curbf, key, (private *)NULL) == EOF) ! 2060: - return(EOF); ! 2061: - n = xscan(b, key, &x); ! 2062: - if(x.match == FOUND) { ! 2063: - if(treeonly(curbf)) ! 2064: - return(FOUND); ! 2065: - else if(lev) ! 2066: - *ndadr(b, n) = u.na; ! 2067: - else ! 2068: - *lfadr(b, n) = u.la; ! 2069: - mustwrite(curbf, lev) = 1; ! 2070: - return(FOUND); ! 2071: - } ! 2072: - dx = (dkey *)ba; ! 2073: - dy = (dkey *)bb; ! 2074: - dellen = newx(&x, key, dx, dy); ! 2075: - if(lev) ! 2076: - dellen += sizeof(ndaddr); ! 2077: - else if(!treeonly(curbf)) ! 2078: - dellen += sizeof(lfaddr); ! 2079: - if(dellen > nfree(b)) { ! 2080: - if(nsplit(lev) == EOF) ! 2081: - return(EOF); ! 2082: - splitting[lev] = 1; ! 2083: - n = xinsert(lev, key, u); ! 2084: - splitting[lev] = 0; ! 2085: - return(n); ! 2086: - } ! 2087: - b = curbf->path[lev]; /* with thanks to brian meekings */ ! 2088: - addaddr(b, n, u); ! 2089: - newkeys(b, &x, dx, dy); ! 2090: - b->kcnt++; ! 2091: - nfree(b) -= dellen; ! 2092: - mustwrite(curbf, lev) = 1; ! 2093: - return(NOTFOUND); ! 2094: -} ! 2095: - ! 2096: -newx(x, key, c, d) private *x; mbuf key; dkey *c, *d; ! 2097: -{ int i, j; ! 2098: - if(x->match != EOF) ! 2099: - c->dcom = x->ocom; ! 2100: - else c->dcom = x->ncom; ! 2101: - i = key.mlen - c->dcom; ! 2102: - c->dlen = DKEYSZ + i; ! 2103: - mvgbt(c->dkey, key.mdata + c->dcom, i); ! 2104: - if(x->match == EOF) ! 2105: - return(c->dlen); ! 2106: - j = x->ncom - x->d->dcom; ! 2107: - d->dcom = x->ncom; ! 2108: - d->dlen = x->d->dlen - j; ! 2109: - mvgbt(d->dkey, x->d->dkey + j, d->dlen - DKEYSZ); ! 2110: - return(c->dlen - j); ! 2111: -} ! 2112: - ! 2113: -addaddr(b, n, u) ! 2114: -hdr *b; ! 2115: -addr u; ! 2116: -{ ! 2117: - if(b->hlev) { ! 2118: - mvgbt((char *)ndadr(b, b->kcnt + 1), ! 2119: - (char *)ndadr(b, b->kcnt), ! 2120: - sizeof(ndaddr) * (b->kcnt + 1 - n) ); ! 2121: - *ndadr(b, n) = u.na; ! 2122: - return; ! 2123: - } ! 2124: - if(treeonly(curbf)) ! 2125: - return; ! 2126: - mvgbt((char *)lfadr(b, b->kcnt), (char *)lfadr(b, b->kcnt - 1), ! 2127: - sizeof(lfaddr) * (b->kcnt - n)); ! 2128: - *lfadr(b, n) = u.la; ! 2129: -} ! 2130: - ! 2131: -newkeys(b, x, c, d) ! 2132: -hdr *b; ! 2133: -private *x; ! 2134: -dkey *c, *d; ! 2135: -{ int n; ! 2136: - char *ffree; ! 2137: - if(b->hlev) ! 2138: - ffree = (char *)ndadr(b, b->kcnt) - nfree(b); ! 2139: - else if(treeonly(curbf)) ! 2140: - ffree = (char *)&nfree(b) - nfree(b); ! 2141: - else ! 2142: - ffree = (char *)lfadr(b, b->kcnt - 1) - nfree(b); ! 2143: - if(x->match != EOF) { ! 2144: - n = c->dlen + d->dlen; ! 2145: - n -= x->d->dlen; ! 2146: - mvgbt((char *)x->d + n, (char *)x->d, ffree - (char *)x->d); ! 2147: - mvgbt((char *)x->d, (char *)c, c->dlen); ! 2148: - mvgbt((char *)x->d + c->dlen, (char *)d, d->dlen); ! 2149: - } ! 2150: - else if(b->kcnt > 0) ! 2151: - mvgbt((char *)x->d + x->d->dlen, (char *)c, c->dlen); ! 2152: - else ! 2153: - mvgbt((char *)x->d, (char *)c, c->dlen); ! 2154: -} ! 2155: - ! 2156: -nsplit(lev) ! 2157: -{ dkey *tod, *fromd; ! 2158: - char prefix[MAXKLEN + 10]; ! 2159: - hdr *b = curbf->path[lev]; ! 2160: - mbuf key; ! 2161: - addr u; ! 2162: - union { ! 2163: - lfaddr *la; ! 2164: - ndaddr *na; ! 2165: - } from, to; ! 2166: - int mvd, x, i, count, n; ! 2167: - hdr *ha; ! 2168: - char a[NDSZ]; ! 2169: - ! 2170: - x = (NDSZ - sizeof(hdr) - sizeof(trailer)) / 2; ! 2171: - ha = (hdr *) a; ! 2172: - mvd = count = 0; ! 2173: - tod = (dkey *)(ha + 1); ! 2174: - fromd = (dkey *)(b + 1); ! 2175: - if(lev == 0) { ! 2176: - to.la = lfadr(ha, 0); ! 2177: - from.la = lfadr(b, 0); ! 2178: - } ! 2179: - else { ! 2180: - to.na = ndadr(ha, 0); ! 2181: - from.na = ndadr(b, 0); ! 2182: - } ! 2183: - *ha = *b; ! 2184: - n = (b->kcnt + 1)/2; ! 2185: - if(lev && b->kcnt - n <= 1) ! 2186: - n--; ! 2187: - for(; count < n && mvd <= x; count++) { ! 2188: - mvgbt((char *)tod, (char *)fromd, fromd->dlen); ! 2189: - mvd += fromd->dlen; ! 2190: - tod = (dkey *)((char *)tod + fromd->dlen); ! 2191: - fromd = (dkey *)((char *)fromd + fromd->dlen); ! 2192: - if(lev) { ! 2193: - *to.na-- = *from.na--; ! 2194: - mvd += sizeof(ndaddr); ! 2195: - } ! 2196: - else if(!treeonly(curbf)) { ! 2197: - *to.la-- = *from.la--; ! 2198: - mvd += sizeof(lfaddr); ! 2199: - } ! 2200: - } ! 2201: - if(lev) { /* another pointer for non-leaves */ ! 2202: - *to.na-- = *from.na--; ! 2203: - mvd += sizeof(ndaddr); ! 2204: - } ! 2205: - ha->kcnt = count; ! 2206: - nfree(ha) = NDSZ - sizeof(hdr) - sizeof(trailer) - mvd; ! 2207: - /* if lev == 0, we promote the last key, else the next key */ ! 2208: - key.mlen = lastkey(ha, prefix); ! 2209: - if(lev) { ! 2210: - mvgbt(prefix + fromd->dcom, fromd->dkey, fromd->dlen - DKEYSZ); ! 2211: - key.mlen = fromd->dcom + fromd->dlen - DKEYSZ; ! 2212: - count++; ! 2213: - fromd = (dkey *)((char *)fromd + fromd->dlen); ! 2214: - } ! 2215: - u.na = newnode(ha); ! 2216: - if(u.na == EOF) { /* error while splitting */ ! 2217: - curbf->fatal++; ! 2218: - return(EOF); ! 2219: - } ! 2220: - key.mdata = prefix; ! 2221: - /* other half */ ! 2222: - if(lev == 0) ! 2223: - to.la = lfadr(ha, 0); ! 2224: - else ! 2225: - to.na = ndadr(ha, 0); ! 2226: - tod = (dkey *)(ha + 1); ! 2227: - tod->dcom = 0; ! 2228: - tod->dlen = fromd->dlen + fromd->dcom; ! 2229: - mvgbt(tod->dkey, prefix, fromd->dcom); ! 2230: - mvgbt(tod->dkey + fromd->dcom, fromd->dkey, fromd->dlen - DKEYSZ); ! 2231: - mvd = tod->dlen; ! 2232: - fromd = (dkey *)((char *)fromd + fromd->dlen); ! 2233: - tod = (dkey *)((char *)tod + tod->dlen); ! 2234: - if(lev) { ! 2235: - *to.na-- = *from.na--; ! 2236: - mvd += sizeof(ndaddr); ! 2237: - } ! 2238: - else if(!treeonly(curbf)) { ! 2239: - *to.la-- = *from.la--; ! 2240: - mvd += sizeof(lfaddr); ! 2241: - } ! 2242: - count++; ! 2243: - for(i = 1; count < b->kcnt; i++, count++) { ! 2244: - mvgbt((char *)tod, (char *)fromd, fromd->dlen); ! 2245: - mvd += fromd->dlen; ! 2246: - tod = (dkey *)((char *)tod + tod->dlen); ! 2247: - fromd = (dkey *)((char *)fromd + fromd->dlen); ! 2248: - if(lev) { ! 2249: - *to.na-- = *from.na--; ! 2250: - mvd += sizeof(ndaddr); ! 2251: - } ! 2252: - else if(!treeonly(curbf)) { ! 2253: - *to.la-- = *from.la--; ! 2254: - mvd += sizeof(lfaddr); ! 2255: - } ! 2256: - ! 2257: - } ! 2258: - if(lev) { ! 2259: - *to.na-- = *from.na--; ! 2260: - mvd += sizeof(ndaddr); ! 2261: - } ! 2262: - ha->kcnt = i; ! 2263: - nfree(ha) = NDSZ - sizeof(hdr) - sizeof(trailer) - mvd; ! 2264: - mvgbt((char *)b, (char *)ha, NDSZ); ! 2265: - mustwrite(curbf, lev) = 1; ! 2266: - if(lev < curbf->height) { ! 2267: - if(xinsert(lev + 1, key, u) == EOF) { ! 2268: - curbf->fatal++; ! 2269: - return(EOF); ! 2270: - } ! 2271: - } ! 2272: - else ! 2273: - return(newroot(u, key, b)); ! 2274: - return(0); ! 2275: -} ! 2276: - ! 2277: -newroot(u, key, b) ! 2278: -addr u; ! 2279: -mbuf key; ! 2280: -hdr *b; ! 2281: -{ hdr *x; ! 2282: - dkey *d; ! 2283: - if(curbf->height >= MXHT) { ! 2284: - errno = BTALL; ! 2285: - curbf->fatal++; ! 2286: - return(EOF); ! 2287: - } ! 2288: - if((x = curbf->path[b->hlev + 1] = (hdr *)malloc(NDSZ)) == NULL) { ! 2289: - errno = BNOMEM; ! 2290: - curbf->fatal++; ! 2291: - return(EOF); ! 2292: - } ! 2293: - *x = *b; ! 2294: - x->hlev++; ! 2295: - d = (dkey *)(x + 1); ! 2296: - d->dlen = DKEYSZ + key.mlen; ! 2297: - d->dcom = 0; ! 2298: - mvgbt(d->dkey, key.mdata, key.mlen); ! 2299: - *ndadr(x, 0) = u.na; ! 2300: - *ndadr(x, 1) = curbf->loc[b->hlev] = newnode(b); ! 2301: - x->kcnt = 1; ! 2302: - nfree(x) = NDSZ - sizeof(hdr) - sizeof(trailer) - DKEYSZ ! 2303: - - key.mlen - 2 * sizeof(ndaddr); ! 2304: - mustwrite(curbf, ++curbf->height) = 1; ! 2305: - return(0); ! 2306: -} ! 2307: - ! 2308: -lastkey(b, s) ! 2309: -hdr *b; ! 2310: -char *s; ! 2311: -{ int i, n; ! 2312: - dkey *p; ! 2313: - p = (dkey *)(b + 1); ! 2314: - for(n = i = 0; i < b->kcnt; i++) { ! 2315: - mvgbt(s + p->dcom, p->dkey, p->dlen - DKEYSZ); ! 2316: - n = p->dlen + p->dcom - DKEYSZ; ! 2317: - p = (dkey *)((char *) p + p->dlen); ! 2318: - } ! 2319: - return(n); ! 2320: -} ! 2321: - ! 2322: -static struct D { struct D *a; char *b;} VER = {&VER,"\n82/10/9:bwrite.c\n"}; ! 2323: -/*0010010000010101*/ ! 2324: //GO.SYSIN DD bwrite.c ! 2325: echo diskrd.c 1>&2 ! 2326: sed 's/.//' >diskrd.c <<'//GO.SYSIN DD diskrd.c' ! 2327: -#include "cbt.h" ! 2328: - ! 2329: -extern bfile *curbf; ! 2330: -extern long lseek(); ! 2331: - ! 2332: -ndrd(lev, where) ndaddr where; ! 2333: -{ ! 2334: - register n; ! 2335: - if(mustwrite(curbf, lev)) { ! 2336: - /* do we ever get here? (yes, while splitting) */ ! 2337: - if(ndwrt(curbf->path[lev], curbf->loc[lev]) == EOF) ! 2338: - return(EOF); ! 2339: - mustwrite(curbf, lev) = 0; ! 2340: - } ! 2341: - if(lseek(curbf->tfd, where * (long)NDSZ, 0) == -1) ! 2342: - return(EOF); ! 2343: - if((n = read(curbf->tfd, (char *)curbf->path[lev], NDSZ)) != NDSZ) { ! 2344: - if(n >= 0) ! 2345: - errno = BRDERR; ! 2346: - return(EOF); ! 2347: - } ! 2348: - curbf->loc[lev] = where; ! 2349: - return(0); ! 2350: -} ! 2351: - ! 2352: -getincore(lev, where) ndaddr where; ! 2353: -{ ! 2354: - if(ndrd(lev, where) == EOF) ! 2355: - return(EOF); ! 2356: - if(curbf->path[lev]->hlev != lev) { ! 2357: - errno = BRDERR; ! 2358: - curbf->fatal++; ! 2359: - return(EOF); ! 2360: - } ! 2361: - return(0); ! 2362: -} ! 2363: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/8/9:diskrd.c\n"}; ! 2364: -/*1010100001000111*/ ! 2365: //GO.SYSIN DD diskrd.c ! 2366: echo diskwrt.c 1>&2 ! 2367: sed 's/.//' >diskwrt.c <<'//GO.SYSIN DD diskwrt.c' ! 2368: -#include "cbt.h" ! 2369: - ! 2370: -extern bfile *curbf; ! 2371: -extern long lseek(); ! 2372: - ! 2373: -ndwrt(b, where) hdr *b; ndaddr where; ! 2374: -{ ! 2375: - register n; ! 2376: - if(lseek(curbf->tfd, where * (long)NDSZ, 0) == -1) ! 2377: - return(EOF); ! 2378: - if((n = write(curbf->tfd, (char *)b, NDSZ)) != NDSZ) { /*unacceptable*/ ! 2379: - if(n >= 0) ! 2380: - errno = BIOWRT; ! 2381: - curbf->fatal++; ! 2382: - return(EOF); ! 2383: - } ! 2384: - return(0); ! 2385: -} ! 2386: - ! 2387: -long brecwrite(rec) mbuf rec; ! 2388: -{ long loc; ! 2389: - int n; ! 2390: - errno = 0; ! 2391: - loc = lseek(curbf->dfd, 0L, 2); ! 2392: - if((n = write(curbf->dfd, rec.mdata, rec.mlen)) == rec.mlen) ! 2393: - return(loc); ! 2394: - else if(n == -1 || errno) ! 2395: - return(EOF); ! 2396: - errno = BIOWRT; ! 2397: - return(EOF); ! 2398: -} ! 2399: - ! 2400: -ndaddr newnode(b) hdr *b; ! 2401: -{ long loc; ! 2402: - int n; ! 2403: - b->hstamp = tranid; ! 2404: - loc = lseek(curbf->tfd, 0L, 2); ! 2405: - if(loc == -1) ! 2406: - return(EOF); ! 2407: - if((n = write(curbf->tfd, (char *)b, NDSZ)) != NDSZ) ! 2408: - if(n < 0) ! 2409: - return(EOF); ! 2410: - else { ! 2411: - errno = BIOWRT; ! 2412: - return(EOF); ! 2413: - } ! 2414: - return(loc/NDSZ); ! 2415: -} ! 2416: - ! 2417: -ndaddr oldnode(lev) ! 2418: -{ int n; ! 2419: - ndaddr a; ! 2420: - if(curbf->path[lev]->hstamp != tranid) { ! 2421: - a = newnode(curbf->path[lev]); ! 2422: - if(a == EOF) ! 2423: - curbf->fatal++; ! 2424: - curbf->loc[lev] = a; ! 2425: - return(a); ! 2426: - } ! 2427: - if(lseek(curbf->tfd, (long)curbf->loc[lev]*NDSZ, 0) == EOF) ! 2428: - return(EOF); ! 2429: - if((n = write(curbf->tfd, (char *)curbf->path[lev], NDSZ)) != NDSZ) { ! 2430: - if(n >= 0) ! 2431: - errno = BIOWRT; ! 2432: - return(EOF); ! 2433: - } ! 2434: - mustwrite(curbf, lev) = 0; ! 2435: - return(curbf->loc[lev]); ! 2436: -} ! 2437: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/8/9:diskwrt.c\n"}; ! 2438: -/*0100101010000110*/ ! 2439: //GO.SYSIN DD diskwrt.c ! 2440: echo get.c 1>&2 ! 2441: sed 's/.//' >get.c <<'//GO.SYSIN DD get.c' ! 2442: -#include "stdio.h" ! 2443: -#include "cbt.h" ! 2444: -extern bfile *bopen(); ! 2445: -extern mbuf bkey(); ! 2446: - ! 2447: -char *index; ! 2448: -char *dfile; ! 2449: -char sep = '!'; ! 2450: -char preflg; ! 2451: -char nl; ! 2452: - ! 2453: -/* get key from index, print all records from dfile. ! 2454: - * default file names and separator in the index are as given ! 2455: - * preflg => prefix searching ! 2456: - */ ! 2457: -char line[256]; ! 2458: -char buf1[256], buf2[2048]; ! 2459: -bfile *bi, *bd; ! 2460: - ! 2461: -main(argc, argv) ! 2462: -char **argv; ! 2463: -{ int i; ! 2464: - char *p; ! 2465: - for(i = 1; i < argc && *argv[i] == '-'; i++) ! 2466: - for(p = argv[i] + 1; *(p-1) && *p; p++) ! 2467: - switch(*p) { ! 2468: - default: ! 2469: - fprintf(stderr, "unk flag %c\n", *p); ! 2470: - exit(1); ! 2471: - case 'p': ! 2472: - preflg = 1; ! 2473: - break; ! 2474: - case 'n': ! 2475: - nl = *++p; ! 2476: - break; ! 2477: - case 's': ! 2478: - sep = *++p; ! 2479: - break; ! 2480: - } ! 2481: - if(i < argc) { ! 2482: - dfile = argv[i++]; ! 2483: - bd = bopen(dfile, 0); ! 2484: - if(bd == NULL) { ! 2485: - perror(dfile); ! 2486: - exit(1); ! 2487: - } ! 2488: - } ! 2489: - if(i < argc) { ! 2490: - index = argv[i++]; ! 2491: - bi = bopen(index, 0); ! 2492: - if(bi == NULL) { ! 2493: - perror(index); ! 2494: - exit(1); ! 2495: - } ! 2496: - } ! 2497: - for(;;) { ! 2498: - (void) fgets(line, sizeof(line), stdin); ! 2499: - if(feof(stdin)) ! 2500: - exit(1); ! 2501: - for(p = line; *p && *p != '\n'; p++) ! 2502: - ; ! 2503: - if(*p == '\n') ! 2504: - *p = 0; ! 2505: - if(index) ! 2506: - doindex(); ! 2507: - dodata(); ! 2508: - } ! 2509: -} ! 2510: - ! 2511: -doindex() ! 2512: -{ mbuf key, found, newkey, rec; ! 2513: - int cnt; ! 2514: - char *q; ! 2515: - key.mlen = strlen(line); ! 2516: - key.mdata = line; ! 2517: - if(bseek(bi, key) == EOF) { ! 2518: - printf("not found\n"); ! 2519: - return; ! 2520: - } ! 2521: - for(cnt = 0; ; cnt++) { ! 2522: - if(bread(bi, &found, (mbuf *)NULL) == EOF) ! 2523: - break; ! 2524: - if(found.mlen < key.mlen || strncmp(found.mdata, line, key.mlen) ! 2525: - break; ! 2526: - if(!preflg && found.mdata[key.mlen] != sep) ! 2527: - break; ! 2528: - for(q = found.mdata; q < found.mdata + found.mlen; q++) ! 2529: - if(*q == sep) ! 2530: - break; ! 2531: - if(*q != sep) { ! 2532: - fprintf(stderr, "retrieved bad index:%s\n", ! 2533: - found.mdata); ! 2534: - continue; ! 2535: - } ! 2536: - newkey.mdata = ++q; ! 2537: - newkey.mlen = found.mlen - (q - found.mdata); ! 2538: - if(bseek(bd, newkey) != FOUND) { ! 2539: - fprintf(stderr, "erro, didn't find %s\n", ! 2540: - newkey.mdata); ! 2541: - continue; ! 2542: - } ! 2543: - bread(bd, (mbuf *)NULL &rec); ! 2544: - for(i = 0; i < rec.mlen; i++) ! 2545: - if(rec.mdata[i] != nl) ! 2546: - putchar(rec.mdata[i]); ! 2547: - else ! 2548: - putchar('\n'); ! 2549: - putchar('\n'); ! 2550: - } ! 2551: - if(cnt == 0) ! 2552: - printf("not found\n"); ! 2553: -} ! 2554: -/*1010001100101110*/ ! 2555: //GO.SYSIN DD get.c ! 2556: echo lib.c 1>&2 ! 2557: sed 's/.//' >lib.c <<'//GO.SYSIN DD lib.c' ! 2558: -#include "cbt.h" ! 2559: -mvgbt(to, from, ln) register char *from, *to; ! 2560: -{ ! 2561: - if(from > to) ! 2562: - while(ln-- > 0) *to++ = *from++; ! 2563: - else if(from < to) ! 2564: - { from += ln-1; ! 2565: - to += ln-1; ! 2566: - while(ln-- > 0) *to-- = *from--; ! 2567: - } ! 2568: -} ! 2569: - ! 2570: -prnode(b) ! 2571: -hdr *b; ! 2572: -{ int i; ! 2573: - char *p; ! 2574: - dkey *d; ! 2575: - ! 2576: - printf("kcnt %d htype %d hlev %d nfree %d ndsz %d\n", b->kcnt, b->htype, ! 2577: - b->hlev, nfree(b), NDSZ); ! 2578: - for(i = 0, p = (char *)(b+1); i < b->kcnt; i++) { ! 2579: - d = (dkey *)p; ! 2580: - prdkey(d); ! 2581: - p += d->dlen; ! 2582: - } ! 2583: - putchar('\n'); ! 2584: -} ! 2585: - ! 2586: -prdkey(d) ! 2587: -dkey *d; ! 2588: -{ int i; ! 2589: - printf("(%d,%d,", d->dlen, d->dcom); ! 2590: - for(i = 0; i < MAXKLEN &&i < d->dlen - DKEYSZ; i++) /* dlen unsigned */ ! 2591: - putchar(d->dkey[i]); ! 2592: - printf("),"); ! 2593: -} ! 2594: -static struct D { struct D *a; char *b;} VER = {&VER,"\n82/10/9:lib.c\n"}; ! 2595: -/*1001101011001110*/ ! 2596: //GO.SYSIN DD lib.c ! 2597: echo nodesz.c 1>&2 ! 2598: sed 's/.//' >nodesz.c <<'//GO.SYSIN DD nodesz.c' ! 2599: -#include "cbt.h" ! 2600: -your nodesize is NDSZ bytes. Except for checking, ! 2601: -nodesize should be the file system block size (cbt.h). ! 2602: -/*0100111000000100*/ ! 2603: //GO.SYSIN DD nodesz.c ! 2604: echo prelim.c 1>&2 ! 2605: sed 's/.//' >prelim.c <<'//GO.SYSIN DD prelim.c' ! 2606: -#include "stdio.h" ! 2607: -char line[129]; ! 2608: -main() ! 2609: -{ unsigned short n; ! 2610: - for(;;) { ! 2611: - fgets(line, sizeof(line), stdin); ! 2612: - if(feof(stdin)) ! 2613: - break; ! 2614: - n = strlen(line); ! 2615: - n--; ! 2616: - fwrite(&n, 1, sizeof(n), stdout); ! 2617: - fwrite(line, 1, n, stdout); ! 2618: - n = 0; ! 2619: - fwrite(&n, 1, sizeof(n), stdout); ! 2620: - } ! 2621: -} ! 2622: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/4/8:prelim.c\n"}; ! 2623: -/*1011011100100111*/ ! 2624: //GO.SYSIN DD prelim.c ! 2625: echo salvage.c 1>&2 ! 2626: sed 's/.//' >salvage.c <<'//GO.SYSIN DD salvage.c' ! 2627: -/* write out all records pointed to by level 0 blocks, ! 2628: - * whether or not the level 0 blocks are accessible. ! 2629: - * the output is like that of bcat -R, except that many keys ! 2630: - * will be duplicated ! 2631: - * In general, the later keys are more up to date ! 2632: - * btsalvage xxx | slvg | sort | slvg2 | cbt build -R newxxx ! 2633: - * is the optimistic way of slavaging a b-tree in which the non-leaves ! 2634: - * have been clobbered ! 2635: - */ ! 2636: -#include "cbt.h" ! 2637: -#include "pr.h" ! 2638: -#include "stdio.h" ! 2639: - ! 2640: -bfile *curbf; ! 2641: -extern bfile *newtran(), *xopen(); ! 2642: -extern char *malloc(), *strcpy(), *realloc(); ! 2643: -extern long lseek(); ! 2644: -char keybuf[NDSZ]; ! 2645: -char *recbuf; ! 2646: -int buflen; ! 2647: - ! 2648: -main(argc, argv) ! 2649: -char **argv; ! 2650: -{ bfile *bf; ! 2651: - mbuf key, rec; ! 2652: - int n; ! 2653: - if(argc != 2) { ! 2654: - fprintf(stderr, "usage: salvage file\n"); ! 2655: - exit(1); ! 2656: - } ! 2657: - bf = xopen(argv[1], 0); ! 2658: - key.mdata = keybuf; ! 2659: - if(bf == NULL) { ! 2660: - fprintf(stderr, "couldn't open %s\n", argv[1]); ! 2661: - exit(1); ! 2662: - } ! 2663: - while((n = breclen(bf)) > buflen) { ! 2664: - if(buflen == 0) ! 2665: - recbuf = malloc(buflen = 1024); ! 2666: - else ! 2667: - recbuf = realloc(recbuf, buflen += 1024); ! 2668: - if(recbuf == NULL) { ! 2669: - fprintf(stderr, "recbuf[%d] failed\n", buflen); ! 2670: - exit(1); ! 2671: - } ! 2672: - rec.mdata = recbuf; ! 2673: - } ! 2674: - for(;;) { ! 2675: - xread(bf, &key, &rec); ! 2676: - write(1, (char *)&key.mlen, 2); ! 2677: - write(1, key.mdata, key.mlen); ! 2678: - write(1, (char *)&rec.mlen, 2); ! 2679: - write(1, rec.mdata, rec.mlen); ! 2680: - } ! 2681: -} ! 2682: -bfile *xopen(s, typ) char *s; /* typ is 0 or 2 */ ! 2683: -{ bfile *p; ! 2684: - int n, i; ! 2685: - ! 2686: - p = alloc(bfile); ! 2687: - if(p == NULL) ! 2688: - goto nomem; ! 2689: - n = strlen(s); ! 2690: - p->fname = malloc((unsigned)n + 3); ! 2691: - if(p->fname == NULL) ! 2692: - goto nomem; ! 2693: - (void) strcpy(p->fname, s); ! 2694: - strcpy(p->fname + n, ".T"); ! 2695: - if((p->tfd = open(p->fname, typ)) == -1) { ! 2696: - free(p->fname); ! 2697: - free((char *)p); ! 2698: - return(NULL); ! 2699: - } ! 2700: - p->rdwrt = typ; ! 2701: - p->fatal = p->advnc = 0; ! 2702: - p->altname = NULL; ! 2703: - for(i = 0; i <= MXHT; i++) { ! 2704: - p->path[i] = NULL; ! 2705: - p->flag[i] = 0; ! 2706: - p->loc[i] = 0; ! 2707: - } ! 2708: - p->path[0] = (hdr *)malloc(NDSZ); ! 2709: - if(p->path[0] == NULL) ! 2710: - goto nomem; ! 2711: - curbf = p; ! 2712: - if(read(p->tfd, (char *)p->path[0], NDSZ) != NDSZ) { ! 2713: - perror(" first read"); ! 2714: - exit(1); ! 2715: - } ! 2716: - strcpy(p->fname + n, ".F"); ! 2717: - if(!treeonly(p) && (p->dfd = open(p->fname, typ)) == -1) { ! 2718: - (void) close(p->tfd); ! 2719: - free(p->fname); ! 2720: - free(p->path[0]); ! 2721: - free((char *)p); ! 2722: - return(NULL); ! 2723: - } ! 2724: - else if(treeonly(p)) ! 2725: - p->dfd = -1; ! 2726: - p->fname[n] = 0; ! 2727: - p->height = p->path[0]->hlev; ! 2728: - xfirst(p); ! 2729: - return(p); ! 2730: -nomem: ! 2731: - errno = BNOMEM; ! 2732: - return(NULL); ! 2733: -} ! 2734: - ! 2735: -breclen(bf) bfile *bf; ! 2736: -{ ! 2737: - if(bf == NULL) ! 2738: - return(EOF); ! 2739: - if(notran(bf)) ! 2740: - return(EOF); ! 2741: - if(bf->advnc) ! 2742: - xadvance(); ! 2743: - if(bf->rdptr.rnum >= bf->path[0]->kcnt) ! 2744: - return(EOF); ! 2745: - if(treeonly(bf)) ! 2746: - return(0); ! 2747: - return(lfadr(bf->path[0], bf->rdptr.rnum)->llen); ! 2748: -} ! 2749: - ! 2750: -xread(bf, key, rec) bfile *bf; mbuf *key, *rec; ! 2751: -{ ! 2752: - dkey *d; ! 2753: - lfaddr *x; ! 2754: - if(bf == NULL) ! 2755: - return(NULL); ! 2756: - if(notran(bf)) ! 2757: - return(EOF); ! 2758: - if(bf->advnc) ! 2759: - xadvance(); ! 2760: - if(bf->rdptr.rnum >= bf->path[0]->kcnt) ! 2761: - return(EOF); ! 2762: - if(key != NULL) { ! 2763: - d = bf->rdptr.rptr; ! 2764: - key->mlen = d->dlen - DKEYSZ + d->dcom; ! 2765: - mvgbt(key->mdata, bf->rdptr.rpref, d->dcom); ! 2766: - mvgbt(key->mdata + d->dcom, d->dkey, d->dlen - DKEYSZ); ! 2767: - } ! 2768: - if(rec != NULL && !treeonly(bf)) { ! 2769: - x = lfadr(bf->path[0], bf->rdptr.rnum); ! 2770: - rec->mlen = x->llen; ! 2771: - if(rec->mlen != 0) { ! 2772: - (void) lseek(bf->dfd, x->lloc, 0); ! 2773: - (void) read(bf->dfd, rec->mdata, (int)rec->mlen); ! 2774: - } ! 2775: - /* errors on read ? */ ! 2776: - } ! 2777: - bf->advnc = 1; ! 2778: - return(0); ! 2779: -} ! 2780: - ! 2781: -xstep(level) ! 2782: -/* ran off the end of node at lev-1 */ ! 2783: -{ hdr *b; ! 2784: - int n, i; ! 2785: - ndaddr u; ! 2786: - do { ! 2787: - n = read(curbf->tfd, (char *)curbf->path[0], NDSZ); ! 2788: - if(n == 0) ! 2789: - exit(0); ! 2790: - if(n != NDSZ) { ! 2791: - perror("xstep"); ! 2792: - exit(1); ! 2793: - } ! 2794: - } while(curbf->path[0]->hlev != 0); ! 2795: -} ! 2796: - ! 2797: -xadvance() ! 2798: -{ mbuf x; ! 2799: - dkey *dold, *dnew; ! 2800: - struct rdptr *y = &curbf->rdptr; ! 2801: - curbf->advnc = 0; ! 2802: - dold = y->rptr; ! 2803: - if(++y->rnum < curbf->path[0]->kcnt) { ! 2804: - dnew = (dkey *)((char *)dold + dold->dlen); ! 2805: - if(dold->dcom < dnew->dcom) ! 2806: - mvgbt(y->rpref + dold->dcom, dold->dkey, dnew->dcom - dold->dcom); ! 2807: - y->rptr = dnew; ! 2808: - return; ! 2809: - } ! 2810: - if(xstep(1) == EOF) { ! 2811: - y->rnum = curbf->path[0]->kcnt + 1; ! 2812: - y->rptr = NULL; ! 2813: - } ! 2814: - else { ! 2815: - y->rnum = 0; ! 2816: - y->rptr = (dkey *)(curbf->path[0] + 1); ! 2817: - } ! 2818: -} ! 2819: - ! 2820: -xfirst(p) ! 2821: -bfile *p; ! 2822: -{ int n; ! 2823: - while(p->path[0]->hlev != 0) { ! 2824: - n = read(p->tfd, (char *)p->path[0], NDSZ); ! 2825: - if(n == 0) { ! 2826: - fprintf(stderr, "empty?\n"); ! 2827: - exit(0); ! 2828: - } ! 2829: - if(n != NDSZ) { ! 2830: - perror("xfirst"); ! 2831: - exit(1); ! 2832: - } ! 2833: - } ! 2834: - curbf->rdptr.rnum = 0; ! 2835: - curbf->rdptr.rptr = (dkey *)(curbf->path[0] + 1); ! 2836: -} ! 2837: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/8/9:salvage.c\n"}; ! 2838: -/*0000110110110000*/ ! 2839: //GO.SYSIN DD salvage.c ! 2840: echo seek.c 1>&2 ! 2841: sed 's/.//' >seek.c <<'//GO.SYSIN DD seek.c' ! 2842: -#include "cbt.h" ! 2843: -#include "pr.h" ! 2844: - ! 2845: -extern bfile *curbf; ! 2846: - ! 2847: -xscan(b, key, x) hdr *b; mbuf key; private *x; ! 2848: -{ int ncom, i, n, val; ! 2849: - char a, *p; ! 2850: - dkey *d; ! 2851: - ! 2852: - n = i = ncom = 0; ! 2853: - val = NOTFOUND; ! 2854: - p = (char *)(b+1); ! 2855: - d = (dkey *)p; ! 2856: - for(; i < b->kcnt; i++, p += d->dlen) { ! 2857: - d = (dkey *)p; ! 2858: - if(ncom < d->dcom) ! 2859: - goto onward; ! 2860: - if(ncom > d->dcom) { ! 2861: - if(x != NULL) { ! 2862: - x->match = val; ! 2863: - x->ncom = d->dcom; ! 2864: - x->ocom = ncom; ! 2865: - x->d = d; ! 2866: - } ! 2867: - return(i); ! 2868: - } ! 2869: - for(n = ncom; ncom < key.mlen && ncom - n < d->dlen - DKEYSZ; ncom++) { ! 2870: - if((a = d->dkey[ncom - n]) == key.mdata[ncom]) ! 2871: - continue; ! 2872: - if(a < key.mdata[ncom]) ! 2873: - goto onward; ! 2874: - goto done; ! 2875: - } ! 2876: - if(ncom == key.mlen) { ! 2877: - if(ncom == d->dlen - DKEYSZ + d->dcom) ! 2878: - val = FOUND; ! 2879: - goto done; ! 2880: - } ! 2881: - onward: ; ! 2882: - } ! 2883: -/* infinity: */ ! 2884: - if(x != NULL) { ! 2885: - x->match = EOF; ! 2886: - x->ncom = ncom; ! 2887: - x->ocom = n; ! 2888: - x->d = d; ! 2889: - } ! 2890: - return(i); ! 2891: -done: ! 2892: - if(x != NULL) { ! 2893: - x->match = val; ! 2894: - x->ncom = ncom; ! 2895: - x->ocom = n; ! 2896: - x->d = d; ! 2897: - } ! 2898: - return(i); ! 2899: -} ! 2900: - ! 2901: -desce(bf, key, x) bfile *bf; mbuf key; private *x; ! 2902: -{ int i, j; ! 2903: - ndaddr u; ! 2904: - for(i = bf->height; i > 0; i--) { ! 2905: - j = xscan(bf->path[i], key, (private *)NULL); ! 2906: - u = *ndadr(bf->path[i], j); ! 2907: - if(bf->loc[i-1] != u) ! 2908: - if(getincore(i - 1, u) == EOF) ! 2909: - return(EOF); ! 2910: - } ! 2911: - i = xscan(bf->path[0], key, x); ! 2912: - return(i); ! 2913: -} ! 2914: - ! 2915: -step(level) ! 2916: -/* ran off the end of node at lev-1 */ ! 2917: -{ hdr *b; ! 2918: - int n, i; ! 2919: - ndaddr u; ! 2920: - if(level > curbf->height) ! 2921: - return(EOF); ! 2922: - n = curbf->loc[level - 1]; ! 2923: - b = curbf->path[level]; ! 2924: - for(i = 0; i <= b->kcnt; i++) ! 2925: - if(*ndadr(b, i) == n) ! 2926: - break; ! 2927: - if(i >= b->kcnt) ! 2928: - return(step(level + 1)); ! 2929: - n = level; ! 2930: - i++; ! 2931: - do { ! 2932: - u = *ndadr(curbf->path[n], i); ! 2933: - if(curbf->loc[n-1] != u) ! 2934: - if(getincore(n - 1, u) == EOF) ! 2935: - return(EOF); ! 2936: - i = 0; ! 2937: - } while(--n > 0); ! 2938: - return(0); ! 2939: -} ! 2940: - ! 2941: -advance() ! 2942: -{ dkey *dold, *dnew; ! 2943: - struct rdptr *y = &curbf->rdptr; ! 2944: - curbf->advnc = 0; ! 2945: - dold = y->rptr; ! 2946: - if(++y->rnum < curbf->path[0]->kcnt) { ! 2947: - dnew = (dkey *)((char *)dold + dold->dlen); ! 2948: - if(dold->dcom < dnew->dcom) ! 2949: - mvgbt(y->rpref + dold->dcom, dold->dkey, dnew->dcom - dold->dcom); ! 2950: - y->rptr = dnew; ! 2951: - return(0); ! 2952: - } ! 2953: - errno = 0; ! 2954: - if(step(1) == EOF) { ! 2955: - if(errno) ! 2956: - return(EOF); ! 2957: - y->rnum = curbf->path[0]->kcnt + 1; ! 2958: - y->rptr = NULL; ! 2959: - } ! 2960: - else { ! 2961: - y->rnum = 0; ! 2962: - y->rptr = (dkey *)(curbf->path[0] + 1); ! 2963: - } ! 2964: - return(0); ! 2965: -} ! 2966: -static struct D { struct D *a; char *b;} VER = {&VER,"\n82/10/9:seek.c\n"}; ! 2967: -/*1100011110101111*/ ! 2968: -/*1101111110111111*/ ! 2969: //GO.SYSIN DD seek.c ! 2970: echo slvg.c 1>&2 ! 2971: sed 's/.//' >slvg.c <<'//GO.SYSIN DD slvg.c' ! 2972: -#include "stdio.h" ! 2973: -/* change the output of btsalvage or btcat -R to sortable */ ! 2974: -/* an 8 byte sortable sequence number is appended to each key ! 2975: - * that slvg2 can keep only the last record with a given key */ ! 2976: - ! 2977: -char *buf; ! 2978: -int buflen; ! 2979: -long reccnt; ! 2980: -extern char *malloc(), *realloc(); ! 2981: - ! 2982: -main() ! 2983: -{ int n, i, j; ! 2984: - for(;;) { ! 2985: - if(read(0, &n, 2) == 0) ! 2986: - exit(0); ! 2987: - if(n > buflen) ! 2988: - space(n); ! 2989: - read(0, buf, n); ! 2990: - reccnt++; ! 2991: - out(buf, n, '\t'); ! 2992: - countout(); ! 2993: - read(0, &n, 2); ! 2994: - if(n > buflen) ! 2995: - space(n); ! 2996: - read(0, buf, n); ! 2997: - j = n; ! 2998: - for(i = 0; i < 4; i++) { ! 2999: - putchar('a' + (j & 0xf)); ! 3000: - j >>= 4; ! 3001: - } ! 3002: - out(buf, n, '\n'); ! 3003: - } ! 3004: -} ! 3005: - ! 3006: -space(n) ! 3007: -{ ! 3008: - while(n > buflen) { ! 3009: - if(buflen == 0) ! 3010: - buf = malloc(buflen = 1024); ! 3011: - else ! 3012: - buf = realloc(buf, buflen += 1024); ! 3013: - if(buf == 0) { ! 3014: - fprintf(stderr, "buf[%d]failed\n", buflen); ! 3015: - exit(1); ! 3016: - } ! 3017: - ! 3018: - } ! 3019: -} ! 3020: - ! 3021: -out(s, n, c) ! 3022: -char *s; ! 3023: -{ ! 3024: - while(n-- > 0) { ! 3025: - putchar('3' + ((*s >> 6) & 3)); ! 3026: - putchar((*s & 077) + ' '); ! 3027: - s++; ! 3028: - } ! 3029: - putchar(c); ! 3030: -} ! 3031: - ! 3032: -countout() ! 3033: -{ int i, n; ! 3034: - n = reccnt; ! 3035: - for(i = 7; i >= 0; i--) ! 3036: - putchar('0' + ((n >> (4*i)) & 077)); ! 3037: -} ! 3038: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/8/7:slvg.c\n"}; ! 3039: -/*1100100010001010*/ ! 3040: //GO.SYSIN DD slvg.c ! 3041: echo slvg2.c 1>&2 ! 3042: sed 's/.//' >slvg2.c <<'//GO.SYSIN DD slvg2.c' ! 3043: -/* takes the output fromt slvg | sort and puts it back into ! 3044: - * form suitable for btbuild -R ! 3045: - * it reduces the two byte codes, and it only keeps the ! 3046: - * last version of each record. ! 3047: - * the input format is ! 3048: - * key tab 8-bytes-of-sequence 4-byete-of-value-len value newline ! 3049: - */ ! 3050: -#include "stdio.h" ! 3051: -#define BUF 20000 ! 3052: -char bufa[BUF], bufb[BUF]; ! 3053: -char *old = bufa; ! 3054: -char *new = bufb; ! 3055: -int len; ! 3056: - ! 3057: -main() ! 3058: -{ char *p, *q; ! 3059: - int c, i; ! 3060: -loop: ! 3061: - for(p = new; (c = getchar()) != '\t' && c != EOF; *p++ = c) ! 3062: - if(p - new >= BUF) { ! 3063: - fprintf(stderr, "recompile slvg2 with more BUF\n"); ! 3064: - exit(1); ! 3065: - } ! 3066: - if(c == EOF) ! 3067: - exit(0); ! 3068: - *p++ = 0; ! 3069: - for(i = 0; i < 8; i++) ! 3070: - getchar(); ! 3071: - if((p - new != len || strcmp(old, new) != 0) && len > 0) { ! 3072: - out(old); ! 3073: - dorest(); ! 3074: - } ! 3075: - len = p - new; ! 3076: - q = old; ! 3077: - old = new; ! 3078: - new = q; ! 3079: - ignore(); ! 3080: - goto loop; ! 3081: -} ! 3082: - ! 3083: -out(s) ! 3084: -char *s; ! 3085: -{ short n; ! 3086: - char c; ! 3087: - n = (len - 1)/2; ! 3088: - fwrite((char *)&n, 1, 2, stdout); ! 3089: - for(; *s; s++) { ! 3090: - c = (*s - '3') << 6; ! 3091: - c |= *++s- ' '; ! 3092: - putchar(c); ! 3093: - } ! 3094: -} ! 3095: - ! 3096: -ignore() ! 3097: -{ int c; ! 3098: - while((c = getchar()) != '\n' && c != EOF) ! 3099: - ; ! 3100: - if(c == EOF) ! 3101: - exit(0); ! 3102: -} ! 3103: - ! 3104: -dorest() ! 3105: -{ unsigned short n; ! 3106: - int i; ! 3107: - /* 4 bytes of length */ ! 3108: - for(i = n = 0; i < 4; i++) ! 3109: - n |= (getchar() - 'a') << (4*i); ! 3110: - fwrite((char *)&n, 1, 2, stdout); ! 3111: - while((i = getchar()) != '\n' && i != EOF) { ! 3112: - n = (i - '3') << 6; ! 3113: - n |= getchar() - ' '; ! 3114: - putchar(n); ! 3115: - } ! 3116: -} ! 3117: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/8/9:slvg2.c\n"}; ! 3118: -/*0010100001111110*/ ! 3119: -/*1110001101011101*/ ! 3120: //GO.SYSIN DD slvg2.c ! 3121: echo tran.c 1>&2 ! 3122: sed 's/.//' >tran.c <<'//GO.SYSIN DD tran.c' ! 3123: -/* place holders */ ! 3124: -#include "cbt.h" ! 3125: -extern long time(); ! 3126: -long tranid; ! 3127: - ! 3128: -long getlpid() ! 3129: -{ ! 3130: - return(time((long *)0) ^ 077777 + getpid()); ! 3131: -} ! 3132: -extern bfile *curbf; ! 3133: -bfile *newtran(bf) bfile *bf; ! 3134: -{ ! 3135: - tranid = getlpid(); ! 3136: - return(bf); ! 3137: -} ! 3138: - ! 3139: -notran(bf) bfile *bf; ! 3140: -{ ! 3141: - curbf = bf; ! 3142: - if(bf->fatal) { ! 3143: - if(bf->fatal++ < 2) { ! 3144: - errno = BFATAL; ! 3145: - return(EOF); ! 3146: - } ! 3147: - perror("btree repeatedly accessed after fatal error"); ! 3148: - abort(); ! 3149: - } ! 3150: - return(0); ! 3151: -} ! 3152: - ! 3153: -trabort() ! 3154: -{ ! 3155: - errno = BUTRAN; ! 3156: - tranid = 0; ! 3157: -} ! 3158: - ! 3159: -intran() ! 3160: -{ ! 3161: - return(0); ! 3162: -} ! 3163: - ! 3164: -rmtran(bf) bfile *bf; ! 3165: -{ ! 3166: -} ! 3167: -static struct D { struct D *a; char *b;} VER = {&VER,"\n81/8/9:tran.c\n"}; ! 3168: -/*0001010110001011*/ ! 3169: //GO.SYSIN DD tran.c ! 3170: echo makefile 1>&2 ! 3171: sed 's/.//' >makefile <<'//GO.SYSIN DD makefile' ! 3172: -.SUFFIXES: .x .o .c ! 3173: -.c.o: ! 3174: - $(CC) $(CFLAGS) -c $< ! 3175: - -ld -r -X $@ ! 3176: - mv a.out $@ ! 3177: -.c.x: ! 3178: - $(CC) $(CFLAGS) -c $< ! 3179: - -ld -r -X $*.o ! 3180: - mv a.out $*.o ! 3181: - ar u btlib $*.o ! 3182: - rm $*.o ! 3183: - touch $*.x ! 3184: -CFLAGS=-g ! 3185: -debug: bttest ! 3186: -all: nodesize ! 3187: -all: btlib btcat btbuild bttest btcreat btreport btsquash btran btdelete ! 3188: -all: btadd btdiag btexer ! 3189: -bwrite.x bdelete.x diskrd.x diskwrt.x bt.x seek.x tran.x: cbt.h ! 3190: -btsquash.o btcreat.o btreport.o bttest.o btcat.o btbuild.o: cbt.h ! 3191: -btlib: bt.x seek.x tran.x diskrd.x diskwrt.x bwrite.x bdelete.x lib.x ! 3192: - ranlib btlib ! 3193: -cyntax: ! 3194: - cyntax bttest.c bt.c seek.c tran.c diskrd.c diskwrt.c bwrite.c bdelete.c lib.c ! 3195: -bttest: bttest.o btlib ! 3196: - $(CC) $(CFLAGS) -o bttest bttest.o btlib ! 3197: -btran: btran.o ! 3198: - $(CC) $(CFLAGS) -o btran btran.o ! 3199: -btsquash: btsquash.o btlib ! 3200: - $(CC) $(CFLAGS) -o btsquash btsquash.o btlib ! 3201: -btadd: btadd.o btlib ! 3202: - $(CC) $(CFLAGS) -o btadd btadd.o btlib ! 3203: -btreport: btreport.o btlib ! 3204: - $(CC) $(CFLAGS) -o btreport btreport.o btlib ! 3205: -btdelete: btdelete.o btlib ! 3206: - $(CC) $(CFLAGS) -o btdelete btdelete.o btlib ! 3207: -btcreat: btcreat.o cbt.h ! 3208: - $(CC) $(CFLAGS) -o btcreat btcreat.o btlib ! 3209: -btdiag: btdiag.o btlib ! 3210: - $(CC) $(CFLAGS) -o btdiag btdiag.o btlib ! 3211: -btexer: btexer.o btlib ! 3212: - $(CC) $(CFLAGS) -o btexer btexer.o btlib ! 3213: -btcat: btcat.o btlib ! 3214: - cc -o btcat btcat.o btlib ! 3215: -btbuild: btbuild.o lib.x ! 3216: - $(CC) $(CFLAGS) -o btbuild btbuild.o btlib ! 3217: -nodesize: ! 3218: - @cc -E $(CFLAGS) nodesz.c | grep nodesize ! 3219: -install: ! 3220: - -cp cbt /usr/bin ! 3221: - -cp cbt.h /usr/include ! 3222: - -cp btlib /usr/lib/libcbt.a ! 3223: - -ranlib /usr/lib/libcbt.a ! 3224: -clean: ! 3225: - rm *.o *.x btlib ! 3226: //GO.SYSIN DD makefile ! 3227: echo cbt 1>&2 ! 3228: sed 's/.//' >cbt <<'//GO.SYSIN DD cbt' ! 3229: -LIB=/usr/lib/btree ! 3230: -if test $# = 0 ! 3231: -then ! 3232: - echo 'cbt add|build|cat|creat|delete|report|squash ...' ! 3233: - exit 1 ! 3234: -fi ! 3235: -x=$1 ! 3236: -shift ! 3237: -case $x in ! 3238: -add) case $1 in ! 3239: - -*) shift ! 3240: - $LIB/btadd $* ;; ! 3241: - *) $LIB/btran | $LIB/btadd $* ;; ! 3242: - esac ;; ! 3243: -build) case $1 in ! 3244: - -*) shift ! 3245: - $LIB/btbuild $* ;; ! 3246: - *) $LIB/btran | $LIB/btbuild $* ;; ! 3247: - esac ;; ! 3248: -cat) $LIB/btcat $* ;; ! 3249: -creat) $LIB/btcreat $* ;; ! 3250: -delete) case $1 in ! 3251: - -*) shift ! 3252: - $LIB/btdelete $* ;; ! 3253: - *) $LIB/btran | $LIB/btdelete $* ;; ! 3254: - esac ;; ! 3255: -grep) $LIB/btgrep $* ;; ! 3256: -report) $LIB/btreport $* ;; ! 3257: -squash) if test $# != 1 ! 3258: - then ! 3259: - echo usage cbt squash file-name ! 3260: - exit 1 ! 3261: - fi ! 3262: - $LIB/btsquash $1 ;; ! 3263: -*) echo 1>&2 unknown command $x ! 3264: -esac ! 3265: //GO.SYSIN DD cbt ! 3266: echo verify 1>&2 ! 3267: sed 's/.//' >verify <<'//GO.SYSIN DD verify' ! 3268: -PATH=:$PATH ! 3269: -export PATH ! 3270: -x=$1 ! 3271: -if test $# = 0 ! 3272: -then ! 3273: - echo verify rec-cnt ! 3274: - exit 1 ! 3275: -fi ! 3276: -echo 1. loading a btree with $x records ! 3277: -btcreat junk ! 3278: -awk '{for(i = 0; i < $1; i++) printf "%8.8d\n", i}' <<! | btran | btbuild junk ! 3279: -$x ! 3280: -! ! 3281: -echo 1. does btreport think there are $x records ! 3282: -btreport junk ! 3283: -echo 2. if btcat doesn\'t agree, it will say so ! 3284: -btcat junk | awk 'length != 9 || $0+0 != NR-1 {print length, $0+0, NR, "bad"}' ! 3285: -echo 2. end of load test ! 3286: -echo ! 3287: -echo 3. delete all the records ! 3288: -awk '{for(i = 0; i < $1; i++) printf "%8.8d\n", i}' <<! | btdelete junk ! 3289: -$x ! 3290: -! ! 3291: -echo 3. btreport should think they are all gone ! 3292: -btreport junk ! 3293: -echo 4. btcat should too ! 3294: -btcat junk | awk '{next}; END {print NR " records"}' ! 3295: -echo 4. there should be no records left ! 3296: -echo ! 3297: -echo 5. now load them back one at a time ! 3298: -echo $x | awk '{for(i = 0; i < $1; i++) printf "%8.8d\n", i}' | ! 3299: - btran | tee foo | btadd junk ! 3300: -echo 5. btreport should think there are $x records ! 3301: -btreport junk ! 3302: -echo 6. btcat should think so too ! 3303: -btcat junk | awk 'length != 9 || $0+0 != NR-1 {print length, $0+0, NR, "bad"} ! 3304: - END {print NR " records"}' ! 3305: -echo 6. there should have been no bad records ! 3306: -echo ! 3307: -echo 7. now throw every other one away ! 3308: -awk '{for(i = 0; i < $1; i+=2) printf "%8.8d\n", i}' <<! | btdelete junk ! 3309: -$x ! 3310: -! ! 3311: -echo 7. btreport should think they are gone ! 3312: -btreport junk ! 3313: -echo 8. btcat should too ! 3314: -btcat junk | awk '{next}; END {print NR " records"}' ! 3315: -echo 8. there should be half the records left ! 3316: -echo ! 3317: -echo 9. now squash the file ! 3318: -btsquash junk ! 3319: -echo 9. btreport says ! 3320: -btreport junk ! 3321: -echo 10. and can btcat find them all: ! 3322: -btcat junk | awk 'length != 9 || $0+0 != 2*NR-1 {print length, $0+0, NR, "bad"} ! 3323: - END {print NR " records"}' ! 3324: -echo 10. there should be half the records left ! 3325: -echo ! 3326: -echo 11. now put the other half back ! 3327: -echo $x | awk '{for(i = 0; i < $1; i+=2) printf "%8.8d\n", i}' | ! 3328: - btran | btadd junk ! 3329: -echo 11. btreport should see $x records ! 3330: -btreport junk ! 3331: -echo 12. so should btcat ! 3332: -btcat junk | awk 'length != 9 || $0+0 != NR-1 {print length, $0+0, NR, "bad"} ! 3333: - END {print NR " records"}' ! 3334: -echo 13. and they should all be there after squashing ! 3335: -btsquash junk ! 3336: -echo 13. btreport should see $x records ! 3337: -btreport junk ! 3338: -echo 14. so should btcat ! 3339: -btcat junk | awk 'length != 9 || $0+0 != NR-1 {print length, $0+0, NR, "bad"} ! 3340: - END {print NR " records"}' ! 3341: -echo and that is all I could think of doing ! 3342: //GO.SYSIN DD verify ! 3343: echo README 1>&2 ! 3344: sed 's/.//' >README <<'//GO.SYSIN DD README' ! 3345: -INSTALLING THE BTREE STUFF ! 3346: -Acceptance testing - ! 3347: -1. Put the distributed software in a testing directory. ! 3348: - Put the name of the directory in the LIB= line in cbt. ! 3349: - make all. (If you are not on a vax, remove the -g CFLAG in makefile.) ! 3350: - (If your machine does not have ranlib, remove all references ! 3351: - to it from the makefile.) ! 3352: -2. Run the verify shell script with various arguments. I use ! 3353: - verify 10, verify 100, and verify 1000. The last needs 3 minutes ! 3354: - of cpu time. ! 3355: -3. Copy everything to its final directory. Fix the CFLAGS line in ! 3356: - the makefile by removing -DTEST. Change the LIB= line in cbt ! 3357: - to point to this directory. Change the NDSZ definition after ! 3358: - #else in cbt.h to the size of a file system block on your system ! 3359: - (512 or 1024 or whatever). ! 3360: -4. make clean ! 3361: - make all ! 3362: - Run the verify shell script to check that everything is still ok. ! 3363: -5. make install ! 3364: //GO.SYSIN DD README
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.