![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to btbuild.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / btree|
Return to btbuild.c CVS log | Up to [Research Unix] / researchv10no / cmd / btree |
1.1 ! root 1: #include "stdio.h" ! 2: #include "cbt.h" ! 3: #define SZ MXHT+1 ! 4: ! 5: typedef struct { ! 6: unsigned short mlen; ! 7: char mdata[NDSZ]; /* max size of values */ ! 8: } xbuf; ! 9: int address[SZ]; /* where the next address goes in the node */ ! 10: xbuf curkey[SZ]; /* last key put in the node */ ! 11: xbuf shortone; /* for compression */ ! 12: int freecnt[SZ]; /* number of bytes left in node */ ! 13: dkey *kp[SZ]; /* where to put next dkey in node */ ! 14: char node[SZ][NDSZ]; /* the nodes */ ! 15: char used[SZ+1]; /* which nodes have been used */ ! 16: xbuf nkey; /* as read by getrec */ ! 17: struct { ! 18: unsigned short mlen; ! 19: char mdata[32767]; ! 20: } val; ! 21: lfaddr currec; /* where getrec put val */ ! 22: FILE *tfd, *dfd; ! 23: char name[16]; ! 24: int type; ! 25: long reccnt; ! 26: extern char *malloc(); ! 27: ! 28: char * ! 29: prkey(a) ! 30: xbuf *a; ! 31: { int i; ! 32: unsigned char c; ! 33: static char buf[4*NDSZ], *p; ! 34: for(i = 0, p = buf; i < a->mlen; i++) { ! 35: c = a->mdata[i]; ! 36: if(c < ' ') { ! 37: *p++ = '^'; ! 38: c += ' '; ! 39: } ! 40: if(c < 127) ! 41: *p++ = (char)c; ! 42: else { ! 43: *p++ = '\\'; ! 44: *p++ = (c >> 6) + '0'; ! 45: *p++ = ((c&63)>>3) + '0'; ! 46: *p++ = c&7 + '0'; ! 47: } ! 48: } ! 49: *p++ = 0; ! 50: return(buf); ! 51: } ! 52: pref(a, b, lev) xbuf *a, *b; ! 53: { register int n; ! 54: register char *p, *q; ! 55: for(n = 0, p = a->mdata, q = b->mdata; n < a->mlen && n < b->mlen; n++) ! 56: if(*p++ != *q++) ! 57: break; ! 58: p--, q--; ! 59: if(lev == 0 && ((n == b->mlen && n >= a->mlen) || *p > *q)) { ! 60: fprintf(stderr, "key %ld out of order:\n", reccnt); ! 61: fprintf(stderr, "key %ld is %s\n", reccnt - 1, prkey(a)); ! 62: fprintf(stderr, "key %ld is %s\n", reccnt, prkey(b)); ! 63: } ! 64: return(n); ! 65: } ! 66: ! 67: getrec() ! 68: { ! 69: reccnt++; ! 70: if(mget(&nkey)) ! 71: return(-1); ! 72: if(mget((xbuf *)&val)) ! 73: fail("half a record read"); ! 74: if((currec.llen = val.mlen) != 0) { ! 75: currec.lloc = ftell(dfd); ! 76: (void) fwrite(val.mdata, 1, val.mlen, dfd); ! 77: if(ferror(dfd)) ! 78: fail("value write"); ! 79: } ! 80: else currec.lloc = 0; ! 81: return(1); ! 82: } ! 83: ! 84: mget(a) xbuf *a; ! 85: { ! 86: (void) fread((char *)&(a->mlen), 1, sizeof(a->mlen), stdin); ! 87: if(feof(stdin) || ferror(stdin)) ! 88: return(1); ! 89: if(fread(a->mdata, 1, a->mlen, stdin) != a->mlen) ! 90: return(1); ! 91: return(0); ! 92: } ! 93: ! 94: ndaddr ndwrt(level) ! 95: { ndaddr loc; ! 96: int i; ! 97: hdr *x; ! 98: trailer *t; ! 99: loc = ftell(tfd)/NDSZ; ! 100: x = (hdr *)(node[level]); ! 101: x->hlev = level; ! 102: t = (trailer *)(node[level] + NDSZ - sizeof(trailer)); ! 103: t->tfree = freecnt[level]; ! 104: x->kcnt = address[level] - (level == 0? 0: 1); ! 105: x->htype = type; ! 106: (void) fwrite(node[level], 1, NDSZ, tfd); ! 107: if(ferror(tfd)) ! 108: fail("node write"); ! 109: for(i = 0; i < NDSZ; i++) ! 110: node[level][i] = 0; ! 111: address[level] = 0; ! 112: curkey[level].mlen = 0; ! 113: freecnt[level] = NDSZ - sizeof(hdr) - sizeof(trailer); ! 114: if(level) ! 115: freecnt[level] -= sizeof(ndaddr); ! 116: kp[level] = (dkey *)(node[level] + sizeof(hdr)); ! 117: return(loc); ! 118: } ! 119: ! 120: finish(level, ptr) ndaddr ptr; ! 121: { ndaddr loc; ! 122: if(!used[level]) ! 123: return; ! 124: *ndadr(node[level], address[level]++) = ptr; ! 125: if(!used[level + 1]) ! 126: fseek(tfd, 0L, 0); ! 127: loc = ndwrt(level); ! 128: finish(level + 1, loc); ! 129: } ! 130: ! 131: insert(level, key, ptr) xbuf *key; ndaddr ptr; ! 132: { int n, len; ! 133: char *p; ! 134: ndaddr loc; ! 135: used[level] = 1; ! 136: n = pref(&curkey[level], key, level); ! 137: len = DKEYSZ + key->mlen - n + sizeof(ptr); ! 138: if(len < freecnt[level]) { ! 139: *ndadr(node[level], address[level]++) = ptr; ! 140: kp[level]->dlen = len - sizeof(ptr); ! 141: kp[level]->dcom = n; ! 142: mvgbt(kp[level]->dkey, key->mdata + n, key->mlen - n); ! 143: p = (char *)(kp[level]) + kp[level]->dlen; ! 144: kp[level] = (dkey *)p; ! 145: freecnt[level] -= len; ! 146: curkey[level] = *key; ! 147: } ! 148: else { ! 149: *ndadr(node[level],address[level]++) = ptr; ! 150: loc = ndwrt(level); ! 151: insert(level+1, key, loc); ! 152: curkey[level].mlen = 0; ! 153: } ! 154: } ! 155: ! 156: doit() ! 157: { int n, len; ! 158: ndaddr loc; ! 159: char *p; ! 160: for(;;) { ! 161: if(getrec() == -1) ! 162: break; ! 163: used[0] = 1; ! 164: n = pref(&curkey[0], &nkey, 0); ! 165: len = DKEYSZ + nkey.mlen - n + sizeof(currec); ! 166: if(type & INDEX) ! 167: len -= sizeof(currec); ! 168: if(len < freecnt[0]) { ! 169: freecnt[0] -= len; ! 170: if(!(type & INDEX)) ! 171: *lfadr(node[0], address[0]++) = currec; ! 172: else ! 173: address[0]++; ! 174: kp[0]->dlen = DKEYSZ + nkey.mlen - n; ! 175: kp[0]->dcom = n; ! 176: mvgbt(kp[0]->dkey, nkey.mdata + n, nkey.mlen - n); ! 177: p = (char *)(kp[0]) + kp[0]->dlen; ! 178: kp[0] = (dkey *)p; ! 179: curkey[0] = nkey; ! 180: } ! 181: else { ! 182: shortest(&curkey[0], &nkey); ! 183: loc = ndwrt(0); ! 184: freecnt[0] -= DKEYSZ + nkey.mlen + sizeof(currec); ! 185: if(type & INDEX) ! 186: freecnt[0] += sizeof(currec); ! 187: insert(1, &shortone, loc); ! 188: if(!(type & INDEX)) ! 189: *lfadr(node[0], address[0]++) = currec; ! 190: else ! 191: address[0]++; ! 192: kp[0]->dlen = DKEYSZ + nkey.mlen; ! 193: kp[0]->dcom = 0; ! 194: mvgbt(kp[0]->dkey, nkey.mdata, nkey.mlen); ! 195: p = (char *)(kp[0]) + kp[0]->dlen; ! 196: kp[0] = (dkey *)p; ! 197: curkey[0] = nkey; ! 198: } ! 199: } ! 200: if(!used[1]) ! 201: (void) fseek(tfd, 0L, 0); ! 202: loc = ndwrt(0); ! 203: finish(1, loc); ! 204: } ! 205: ! 206: init(s) ! 207: char *s; ! 208: { int i; ! 209: hdr *b; ! 210: char xx[NDSZ]; ! 211: (void) sprintf(name, "%s.T", s); ! 212: tfd = fopen(name, "r"); ! 213: if(tfd == NULL) { ! 214: perror(s); ! 215: exit(1); ! 216: } ! 217: fread(xx, 1, NDSZ, tfd); ! 218: fclose(tfd); ! 219: tfd = fopen(name, "w"); ! 220: (void) fseek(tfd, (long)NDSZ, 0); ! 221: b = (hdr *)xx; ! 222: type = b->htype; ! 223: (void) sprintf(name, "%s.F", s); ! 224: if((type & INDEX) != INDEX) ! 225: dfd = fopen(name, "w"); ! 226: for(i = 0; i < SZ; i++) { ! 227: freecnt[i] = NDSZ - sizeof(hdr) - sizeof(trailer); ! 228: if(i) ! 229: freecnt[i] -= sizeof(ndaddr); ! 230: kp[i] = (dkey *)(node[i] + sizeof(hdr)); ! 231: } ! 232: } ! 233: ! 234: main(argc, argv) ! 235: char **argv; ! 236: { ! 237: if(argc != 2) { ! 238: fprintf(stderr, "%s: too many arguments\n", argv[1]); ! 239: exit(1); ! 240: } ! 241: init(argv[1]); ! 242: doit(); ! 243: exit(0); ! 244: } ! 245: ! 246: shortest(a, b) xbuf *a, *b; ! 247: { int n; ! 248: char *p, *q, *s; ! 249: p = a->mdata; ! 250: q = b->mdata; ! 251: s = shortone.mdata; ! 252: for(n = 0; n < a->mlen && n < b->mlen; n++, p++, q++) ! 253: if(*p == *q) ! 254: *s++ = *p; ! 255: else break; ! 256: if(n < a->mlen) { ! 257: again: ! 258: if(n + 1 == a->mlen) ! 259: *s++ = *p; ! 260: else if(*p + 1 < *q) ! 261: *s++ = *p + 1; ! 262: else { ! 263: *s++ = *p++; ! 264: n++; ! 265: if(*p + 1 > *p) ! 266: *s++ = *p + 1; ! 267: else goto again; ! 268: } ! 269: } ! 270: shortone.mlen = s - shortone.mdata; ! 271: } ! 272: prbuf(x) xbuf *x; ! 273: { int i; ! 274: for(i = 0; i < x->mlen; i++) ! 275: printf("%3.3o ", x->mdata[i]); ! 276: putchar('\n'); ! 277: } ! 278: fail(s) ! 279: char *s; ! 280: { ! 281: perror(s); ! 282: exit(2); ! 283: } ! 284: static struct D { struct D *a; char *b;} VER = {&VER,"\n81/8/9:btbuild.c\n"}; ! 285: /*1101000110100100*/
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.