![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to bwrite.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 bwrite.c CVS log | Up to [Research Unix] / researchv10no / cmd / btree |
1.1 root 1: #include "cbt.h"
2: #include "pr.h"
3:
4: typedef union {
5: ndaddr na;
6: lfaddr la;
7: } addr;
8: static char splitting[MXHT+1];
9: extern bfile *curbf;
10: extern ndaddr oldnode(), newnode();
11: extern char *malloc();
12:
13: extern long brecwrite();
14:
15: bwrite(bf, key, rec) mbuf key, rec; bfile *bf;
16: { addr u;
17: int n;
18: if(bf == NULL)
19: return(EOF);
20: if(!bf->rdwrt) {
21: errno = BNOWRITE;
22: return(EOF);
23: }
24: if(notran(bf))
25: return(EOF);
26: if(key.mlen > MAXKLEN)
27: return(EOF);
28: if(!treeonly(bf)) {
29: u.la.llen = rec.mlen;
30: u.la.lloc = brecwrite(rec);
31: if(u.la.lloc == EOF)
32: return(EOF);
33: }
34: if(desce(bf, key, (private *)NULL) == EOF)
35: return(EOF);
36: n = xinsert(0, key, u);
37: (void) bseek(bf, key);
38: return(n);
39: }
40:
41: fixpath(bf)
42: bfile *bf;
43: { addr u;
44: hdr *b;
45: int i, n, j;
46: for(i = 0; i < bf->height; i++) {
47: if(!mustwrite(bf, i))
48: continue;
49: n = bf->loc[i];
50: if((u.na = oldnode(i)) == EOF)
51: return(EOF);
52: b = bf->path[i+1];
53: for(j = 0; j <= b->kcnt; j++)
54: if(*ndadr(b, j) == n)
55: break;
56: if(j > b->kcnt){ /* curtains, the parent doesn't point to us */
57: errno = BFATAL;
58: return(EOF);
59: }
60: *ndadr(b, j) = u.na;
61: mustwrite(bf, i + 1) = 1;
62: }
63: return(0);
64: }
65:
66: xinsert(lev, key, u) mbuf key; addr u;
67: { private x;
68: int n, dellen;
69: hdr *b = curbf->path[lev];
70: char ba[NDSZ], bb[NDSZ];
71: dkey *dx, *dy;
72: if(splitting[lev])
73: if(desce(curbf, key, (private *)NULL) == EOF)
74: return(EOF);
75: n = xscan(b, key, &x);
76: if(x.match == FOUND) {
77: if(treeonly(curbf))
78: return(FOUND);
79: else if(lev)
80: *ndadr(b, n) = u.na;
81: else
82: *lfadr(b, n) = u.la;
83: mustwrite(curbf, lev) = 1;
84: return(FOUND);
85: }
86: dx = (dkey *)ba;
87: dy = (dkey *)bb;
88: dellen = newx(&x, key, dx, dy);
89: if(lev)
90: dellen += sizeof(ndaddr);
91: else if(!treeonly(curbf))
92: dellen += sizeof(lfaddr);
93: if(dellen > nfree(b)) {
94: if(nsplit(lev) == EOF)
95: return(EOF);
96: splitting[lev] = 1;
97: n = xinsert(lev, key, u);
98: splitting[lev] = 0;
99: return(n);
100: }
101: b = curbf->path[lev]; /* with thanks to brian meekings */
102: addaddr(b, n, u);
103: newkeys(b, &x, dx, dy);
104: b->kcnt++;
105: nfree(b) -= dellen;
106: mustwrite(curbf, lev) = 1;
107: return(NOTFOUND);
108: }
109:
110: newx(x, key, c, d) private *x; mbuf key; dkey *c, *d;
111: { int i, j;
112: if(x->match != EOF)
113: c->dcom = x->ocom;
114: else c->dcom = x->ncom;
115: i = key.mlen - c->dcom;
116: c->dlen = DKEYSZ + i;
117: mvgbt(c->dkey, key.mdata + c->dcom, i);
118: if(x->match == EOF)
119: return(c->dlen);
120: j = x->ncom - x->d->dcom;
121: d->dcom = x->ncom;
122: d->dlen = x->d->dlen - j;
123: mvgbt(d->dkey, x->d->dkey + j, d->dlen - DKEYSZ);
124: return(c->dlen - j);
125: }
126:
127: addaddr(b, n, u)
128: hdr *b;
129: addr u;
130: {
131: if(b->hlev) {
132: mvgbt((char *)ndadr(b, b->kcnt + 1),
133: (char *)ndadr(b, b->kcnt),
134: sizeof(ndaddr) * (b->kcnt + 1 - n) );
135: *ndadr(b, n) = u.na;
136: return;
137: }
138: if(treeonly(curbf))
139: return;
140: mvgbt((char *)lfadr(b, b->kcnt), (char *)lfadr(b, b->kcnt - 1),
141: sizeof(lfaddr) * (b->kcnt - n));
142: *lfadr(b, n) = u.la;
143: }
144:
145: newkeys(b, x, c, d)
146: hdr *b;
147: private *x;
148: dkey *c, *d;
149: { int n;
150: char *ffree;
151: if(b->hlev)
152: ffree = (char *)ndadr(b, b->kcnt) - nfree(b);
153: else if(treeonly(curbf))
154: ffree = (char *)&nfree(b) - nfree(b);
155: else
156: ffree = (char *)lfadr(b, b->kcnt - 1) - nfree(b);
157: if(x->match != EOF) {
158: n = c->dlen + d->dlen;
159: n -= x->d->dlen;
160: mvgbt((char *)x->d + n, (char *)x->d, ffree - (char *)x->d);
161: mvgbt((char *)x->d, (char *)c, c->dlen);
162: mvgbt((char *)x->d + c->dlen, (char *)d, d->dlen);
163: }
164: else if(b->kcnt > 0)
165: mvgbt((char *)x->d + x->d->dlen, (char *)c, c->dlen);
166: else
167: mvgbt((char *)x->d, (char *)c, c->dlen);
168: }
169:
170: nsplit(lev)
171: { dkey *tod, *fromd;
172: char prefix[MAXKLEN + 10];
173: hdr *b = curbf->path[lev];
174: mbuf key;
175: addr u;
176: union {
177: lfaddr *la;
178: ndaddr *na;
179: } from, to;
180: int mvd, x, i, count, n;
181: hdr *ha;
182: char a[NDSZ];
183:
184: x = (NDSZ - sizeof(hdr) - sizeof(trailer)) / 2;
185: ha = (hdr *) a;
186: mvd = count = 0;
187: tod = (dkey *)(ha + 1);
188: fromd = (dkey *)(b + 1);
189: if(lev == 0) {
190: to.la = lfadr(ha, 0);
191: from.la = lfadr(b, 0);
192: }
193: else {
194: to.na = ndadr(ha, 0);
195: from.na = ndadr(b, 0);
196: }
197: *ha = *b;
198: n = (b->kcnt + 1)/2;
199: if(lev && b->kcnt - n <= 1)
200: n--;
201: for(; count < n && mvd <= x; count++) {
202: mvgbt((char *)tod, (char *)fromd, fromd->dlen);
203: mvd += fromd->dlen;
204: tod = (dkey *)((char *)tod + fromd->dlen);
205: fromd = (dkey *)((char *)fromd + fromd->dlen);
206: if(lev) {
207: *to.na-- = *from.na--;
208: mvd += sizeof(ndaddr);
209: }
210: else if(!treeonly(curbf)) {
211: *to.la-- = *from.la--;
212: mvd += sizeof(lfaddr);
213: }
214: }
215: if(lev) { /* another pointer for non-leaves */
216: *to.na-- = *from.na--;
217: mvd += sizeof(ndaddr);
218: }
219: ha->kcnt = count;
220: nfree(ha) = NDSZ - sizeof(hdr) - sizeof(trailer) - mvd;
221: /* if lev == 0, we promote the last key, else the next key */
222: key.mlen = lastkey(ha, prefix);
223: if(lev) {
224: mvgbt(prefix + fromd->dcom, fromd->dkey, fromd->dlen - DKEYSZ);
225: key.mlen = fromd->dcom + fromd->dlen - DKEYSZ;
226: count++;
227: fromd = (dkey *)((char *)fromd + fromd->dlen);
228: }
229: u.na = newnode(ha);
230: if(u.na == EOF) { /* error while splitting */
231: curbf->fatal++;
232: return(EOF);
233: }
234: key.mdata = prefix;
235: /* other half */
236: if(lev == 0)
237: to.la = lfadr(ha, 0);
238: else
239: to.na = ndadr(ha, 0);
240: tod = (dkey *)(ha + 1);
241: tod->dcom = 0;
242: tod->dlen = fromd->dlen + fromd->dcom;
243: mvgbt(tod->dkey, prefix, fromd->dcom);
244: mvgbt(tod->dkey + fromd->dcom, fromd->dkey, fromd->dlen - DKEYSZ);
245: mvd = tod->dlen;
246: fromd = (dkey *)((char *)fromd + fromd->dlen);
247: tod = (dkey *)((char *)tod + tod->dlen);
248: if(lev) {
249: *to.na-- = *from.na--;
250: mvd += sizeof(ndaddr);
251: }
252: else if(!treeonly(curbf)) {
253: *to.la-- = *from.la--;
254: mvd += sizeof(lfaddr);
255: }
256: count++;
257: for(i = 1; count < b->kcnt; i++, count++) {
258: mvgbt((char *)tod, (char *)fromd, fromd->dlen);
259: mvd += fromd->dlen;
260: tod = (dkey *)((char *)tod + tod->dlen);
261: fromd = (dkey *)((char *)fromd + fromd->dlen);
262: if(lev) {
263: *to.na-- = *from.na--;
264: mvd += sizeof(ndaddr);
265: }
266: else if(!treeonly(curbf)) {
267: *to.la-- = *from.la--;
268: mvd += sizeof(lfaddr);
269: }
270:
271: }
272: if(lev) {
273: *to.na-- = *from.na--;
274: mvd += sizeof(ndaddr);
275: }
276: ha->kcnt = i;
277: nfree(ha) = NDSZ - sizeof(hdr) - sizeof(trailer) - mvd;
278: mvgbt((char *)b, (char *)ha, NDSZ);
279: mustwrite(curbf, lev) = 1;
280: if(lev < curbf->height) {
281: if(xinsert(lev + 1, key, u) == EOF) {
282: curbf->fatal++;
283: return(EOF);
284: }
285: }
286: else
287: return(newroot(u, key, b));
288: return(0);
289: }
290:
291: newroot(u, key, b)
292: addr u;
293: mbuf key;
294: hdr *b;
295: { hdr *x;
296: dkey *d;
297: if(curbf->height >= MXHT) {
298: errno = BTALL;
299: curbf->fatal++;
300: return(EOF);
301: }
302: if((x = curbf->path[b->hlev + 1] = (hdr *)malloc(NDSZ)) == NULL) {
303: errno = BNOMEM;
304: curbf->fatal++;
305: return(EOF);
306: }
307: *x = *b;
308: x->hlev++;
309: d = (dkey *)(x + 1);
310: d->dlen = DKEYSZ + key.mlen;
311: d->dcom = 0;
312: mvgbt(d->dkey, key.mdata, key.mlen);
313: *ndadr(x, 0) = u.na;
314: *ndadr(x, 1) = curbf->loc[b->hlev] = newnode(b);
315: x->kcnt = 1;
316: nfree(x) = NDSZ - sizeof(hdr) - sizeof(trailer) - DKEYSZ
317: - key.mlen - 2 * sizeof(ndaddr);
318: mustwrite(curbf, ++curbf->height) = 1;
319: return(0);
320: }
321:
322: lastkey(b, s)
323: hdr *b;
324: char *s;
325: { int i, n;
326: dkey *p;
327: p = (dkey *)(b + 1);
328: for(n = i = 0; i < b->kcnt; i++) {
329: mvgbt(s + p->dcom, p->dkey, p->dlen - DKEYSZ);
330: n = p->dlen + p->dcom - DKEYSZ;
331: p = (dkey *)((char *) p + p->dlen);
332: }
333: return(n);
334: }
335:
336: static struct D { struct D *a; char *b;} VER = {&VER,"\n82/10/9:bwrite.c\n"};
337: /*0010010000010101*/
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.