Return to btdiag.c CVS log

Up to [Research Unix] / researchv10no / cmd / btree

Annotation of researchv10no/cmd/btree/btdiag.c, revision 1.1

1.1     ! root        1: #include "stdio.h"
        !             2: #include "cbt.h"
        !             3: #include "sys/types.h"
        !             4: #include "sys/stat.h"
        !             5: 
        !             6: extern bfile *bopen();
        !             7: extern char *malloc();
        !             8: extern int errno;
        !             9: int errcnt;
        !            10: char nodes[MXHT + 1][NDSZ];
        !            11: int loc[MXHT + 1];
        !            12: char *seen;
        !            13: dkey *curd[MXHT + 1];
        !            14: char curkey[MXHT + 1][MAXKLEN];
        !            15: int keynum[MXHT + 1];
        !            16: mbuf tinykey = { "", 0};
        !            17: mbuf giantkey = {"\177\177\177\177", 4};
        !            18: 
        !            19: main(argc, argv)
        !            20: char **argv;
        !            21: {      bfile *bt;
        !            22:        int n;
        !            23:        if(argc < 2)
        !            24:                error("file name?");
        !            25:        bt = bopen(argv[1], 0);
        !            26:        if(bt == 0)
        !            27:                error("couldn't open tree");
        !            28:        n = diagnose(bt);
        !            29:        printf("return value is %d\n", n);
        !            30:        exit(n);
        !            31: }
        !            32: 
        !            33: diagnose(b)
        !            34: bfile *b;
        !            35: {      int i;
        !            36:        struct stat statb;
        !            37:        if(fstat(b->tfd, &statb) < 0)
        !            38:                error("can't stat tree");
        !            39:        if(statb.st_size % NDSZ || statb.st_size <= 0) {
        !            40:                printf("tree size %d mod ndsz %d != 0\n", statb.st_size, NDSZ);
        !            41:                errcnt++;
        !            42:        }
        !            43:        if(b->height > MXHT || b->height < 0) {
        !            44:                printf("tree height %d weird max %d\n", b->height, MXHT);
        !            45:                return(-1);
        !            46:        }
        !            47:        seen = malloc(statb.st_size / NDSZ);
        !            48:        for(i = 0; i < statb.st_size/NDSZ; i++)
        !            49:                seen[i] = -1;
        !            50:        lseek(b->tfd, 0, 0);
        !            51:        if((i = read(b->tfd, nodes[b->height], NDSZ)) != NDSZ) {
        !            52:                printf("read of root returned %d (%d)\n", i, errno);
        !            53:                error("can't proceed");
        !            54:        }
        !            55:        return(dolevel(b->tfd, b->height, tinykey, giantkey) || errcnt);
        !            56: }
        !            57: 
        !            58: mbuf
        !            59: firstkey(n)
        !            60: {      hdr *b;
        !            61:        mbuf z;
        !            62:        int i;
        !            63:        b = (hdr *)nodes[n];
        !            64:        keynum[n] = 0;
        !            65:        if(keynum[n] >= b->kcnt) {
        !            66:                z.mlen = -1;
        !            67:                return(z);
        !            68:        }
        !            69:        curd[n] = (dkey *)(b+1);
        !            70:        for(i = 0; i < curd[n]->dlen - DKEYSZ; i++)
        !            71:                curkey[n][i] = curd[n]->dkey[i];
        !            72:        z.mlen = i;
        !            73:        z.mdata = curkey[n];
        !            74:        return(z);
        !            75: }
        !            76: 
        !            77: mbuf
        !            78: nextkey(n)
        !            79: {      mbuf z;
        !            80:        char *p = (char *)curd[n];
        !            81:        dkey *d;
        !            82:        int i;
        !            83:        hdr *b = (hdr *)nodes[n];
        !            84:        if(++keynum[n] >= b->kcnt) {
        !            85:                z.mlen = -1;
        !            86:                return(z);
        !            87:        }
        !            88:        p += curd[n]->dlen;
        !            89:        d = curd[n] = (dkey *)p;
        !            90:        z.mdata = curkey[n];
        !            91:        for(i = 0; i < d->dlen - DKEYSZ; i++)
        !            92:                z.mdata[d->dcom + i] = d->dkey[i];
        !            93:        z.mlen = i + d->dcom;
        !            94:        return(z);
        !            95: }
        !            96: 
        !            97: dolevel(fd, lev, lokey, hikey)
        !            98: mbuf lokey, hikey;
        !            99: {      int i, j;
        !           100:        mbuf left, right;
        !           101:        char leftx[MAXKLEN];
        !           102:        hdr *b = (hdr *)nodes[lev];
        !           103:        if(lseek(fd, loc[lev] * NDSZ, 0) < 0 || read(fd, nodes[lev], NDSZ) != NDSZ) {
        !           104:                printf("couldn't read node %d, level %d\n", loc[lev], lev);
        !           105:                return(-1);
        !           106:        }
        !           107:        if(seen[loc[lev]] != -1) {
        !           108:                printf("node %d visited twice, at lev %d and %d\n", lev, seen[loc[lev]], lev);
        !           109:                if(lev != seen[loc[lev]])
        !           110:                        return(-1);
        !           111:        }
        !           112:        else
        !           113:                seen[loc[lev]] = lev;
        !           114:        if(check(loc[lev], nodes[lev], lokey, hikey))
        !           115:                return(-1);
        !           116:        if(lev == 0)
        !           117:                return(0);
        !           118:        right = firstkey(lev);
        !           119:        left.mlen = lokey.mlen;
        !           120:        left.mdata = leftx;
        !           121:        for(j = 0; j < left.mlen; j++)
        !           122:                left.mdata[j] = lokey.mdata[j];
        !           123:        for(i = 0; i < b->kcnt; i++) {
        !           124:                loc[lev - 1] = *ndadr(b, i);
        !           125:                if(dolevel(fd, lev - 1, left, right))
        !           126:                        return(-1);
        !           127:                left.mlen = right.mlen;
        !           128:                for(j = 0; j < left.mlen; j++)
        !           129:                        left.mdata[j] = right.mdata[j];
        !           130:                right = nextkey(lev);
        !           131:                if(right.mlen < 0)
        !           132:                        printf("unexpected end of keys, node %d\n", loc[lev]);
        !           133:        }
        !           134:        loc[lev - 1] = *ndadr(b, i);
        !           135:        return(dolevel(fd, lev - 1, left, hikey));
        !           136: }
        !           137: 
        !           138: check(noden, b, lokey, hikey)
        !           139: hdr *b;
        !           140: mbuf lokey, hikey;
        !           141: {      int i, plen, sz, j;
        !           142:        char *p, prefix[MAXKLEN];
        !           143:        dkey *d;
        !           144: 
        !           145:        /* check space allocation */
        !           146:        sz = sizeof(hdr) + sizeof(trailer) + nfree(b);
        !           147:        if(nfree(b) < 0) {
        !           148:                printf("nfree: %d < 0, node %d\n", nfree(b), noden);
        !           149:                errcnt++;
        !           150:        }
        !           151:        if(sz > NDSZ) {
        !           152:                printf("nfree: %d impossibly large, node %d\n", nfree(b), noden);
        !           153:                errcnt++;
        !           154:        }
        !           155:        if(b->kcnt < 0) {
        !           156:                printf("kcnt %d < 0, node %d\n", b->kcnt, noden);
        !           157:                return(-1);
        !           158:        }
        !           159:        p = (char *)(b+1);
        !           160:        for(i = 0; i < b->kcnt; i++) {
        !           161:                d = (dkey *)p;
        !           162:                if(d->dlen < DKEYSZ) {
        !           163:                        printf("node %d, key %d, dlen %d too small\n", noden, i, d->dlen);
        !           164:                        return(-1);
        !           165:                }
        !           166:                if(b->hlev)
        !           167:                        sz += sizeof(ndaddr);
        !           168:                else if(!(b->htype & INDEX))
        !           169:                        sz += sizeof(lfaddr);
        !           170:                if((sz += d->dlen) > NDSZ) {
        !           171:                        printf("node %d, contents too large\n", noden);
        !           172:                        return(-1);
        !           173:                }
        !           174:                p += d->dlen;
        !           175:        }
        !           176:        if(b->hlev)
        !           177:                sz += sizeof(ndaddr);
        !           178:        if(sz != NDSZ) {
        !           179:                printf("node %d, size %d ndsz %d\n", noden, sz, NDSZ);
        !           180:                return(-1);
        !           181:        }
        !           182:        /* check key ordering */
        !           183:        p = (char *)(b + 1);
        !           184:        d = (dkey *)p;
        !           185:        if(d->dcom != 0) {
        !           186:                printf("node %d first key has dcom %d > 0\n", noden, d->dcom);
        !           187:                return(-1);
        !           188:        }
        !           189:        plen = lokey.mlen;
        !           190:        for(i = 0; i < plen; i++)
        !           191:                prefix[i] = lokey.mdata[i];
        !           192:        for(i = 0; i < b->kcnt; i++) {
        !           193:                if(d->dcom > plen) {
        !           194:                        printf("node %d key %d, dcom %d bigger than len %d of prev key\n",
        !           195:                                noden, i, d->dcom, plen);
        !           196:                        return(-1);
        !           197:                }
        !           198:                for(j = 0; j < d->dlen - DKEYSZ; j++) {
        !           199:                        if(j + d->dcom > plen)
        !           200:                                break;
        !           201:                        if(d->dkey[j] < prefix[d->dcom + j]) {
        !           202:                                printf("node %d, key %d out of order\n",
        !           203:                                        noden, i);
        !           204:                                errcnt++;
        !           205:                                break;
        !           206:                        }
        !           207:                        else if(d->dkey[j] == prefix[d->dcom + j])
        !           208:                                continue;
        !           209:                        else
        !           210:                                break;
        !           211:                }
        !           212:                for(j = 0; j < d->dlen - DKEYSZ; j++)
        !           213:                        prefix[j + d->dcom] = d->dkey[j];
        !           214:                plen = j + d->dcom;
        !           215:        }
        !           216:        for(i = 0; i < plen && i < hikey.mlen; i++) {
        !           217:                if(prefix[i] < hikey.mdata[i])
        !           218:                        return(0);
        !           219:                else if(prefix[i] == hikey.mdata[i])
        !           220:                        continue;
        !           221:                printf("node %d last key too large pref %s, hi %s\n", noden, prefix, hikey.mdata);
        !           222:                return(-1);
        !           223:        }
        !           224:        if(plen > hikey.mlen) {
        !           225:                printf("node %d last key too large plen %d, hikey.len %d\n", noden, plen, hikey.mlen);
        !           226:                return(-1);
        !           227:        }
        !           228:        return(0);
        !           229: }
        !           230: 
        !           231: error(s)
        !           232: char *s;
        !           233: {
        !           234:        printf("%s\n", s);
        !           235:        exit(1);
        !           236: }
        !           237: static struct D { struct D *a; char *b;} VER = {&VER,"\n82/10/9:btdiag.c\n"};
        !           238: /*1100001011001101*/

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.