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