![[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.