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