![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to btdiag.c 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 btdiag.c CVS log | Up to [Research Unix] / researchv10no / cmd / btree |
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.