![[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] / researchv8dc / lib / libcbt|
Return to bwrite.c CVS log | Up to [Research Unix] / researchv8dc / lib / libcbt |
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: addaddr(b, n, u);
102: newkeys(b, &x, dx, dy);
103: b->kcnt++;
104: nfree(b) -= dellen;
105: mustwrite(curbf, lev) = 1;
106: return(NOTFOUND);
107: }
108:
109: newx(x, key, c, d) private *x; mbuf key; dkey *c, *d;
110: { int i, j;
111: if(x->match != EOF)
112: c->dcom = x->ocom;
113: else c->dcom = x->ncom;
114: i = key.mlen - c->dcom;
115: c->dlen = DKEYSZ + i;
116: mvgbt(c->dkey, key.mdata + c->dcom, i);
117: if(x->match == EOF)
118: return(c->dlen);
119: j = x->ncom - x->d->dcom;
120: d->dcom = x->ncom;
121: d->dlen = x->d->dlen - j;
122: mvgbt(d->dkey, x->d->dkey + j, d->dlen - DKEYSZ);
123: return(c->dlen - j);
124: }
125:
126: addaddr(b, n, u)
127: hdr *b;
128: addr u;
129: {
130: if(b->hlev) {
131: mvgbt((char *)ndadr(b, b->kcnt + 1),
132: (char *)ndadr(b, b->kcnt),
133: sizeof(ndaddr) * (b->kcnt + 1 - n) );
134: *ndadr(b, n) = u.na;
135: return;
136: }
137: if(treeonly(curbf))
138: return;
139: mvgbt((char *)lfadr(b, b->kcnt), (char *)lfadr(b, b->kcnt - 1),
140: sizeof(lfaddr) * (b->kcnt - n));
141: *lfadr(b, n) = u.la;
142: }
143:
144: newkeys(b, x, c, d)
145: hdr *b;
146: private *x;
147: dkey *c, *d;
148: { int n;
149: char *ffree;
150: if(b->hlev)
151: ffree = (char *)ndadr(b, b->kcnt) - nfree(b);
152: else if(treeonly(curbf))
153: ffree = (char *)&nfree(b) - nfree(b);
154: else
155: ffree = (char *)lfadr(b, b->kcnt - 1) - nfree(b);
156: if(x->match != EOF) {
157: n = c->dlen + d->dlen;
158: n -= x->d->dlen;
159: mvgbt((char *)x->d + n, (char *)x->d, ffree - (char *)x->d);
160: mvgbt((char *)x->d, (char *)c, c->dlen);
161: mvgbt((char *)x->d + c->dlen, (char *)d, d->dlen);
162: }
163: else if(b->kcnt > 0)
164: mvgbt((char *)x->d + x->d->dlen, (char *)c, c->dlen);
165: else
166: mvgbt((char *)x->d, (char *)c, c->dlen);
167: }
168:
169: nsplit(lev)
170: { dkey *tod, *fromd;
171: char prefix[MAXKLEN + 10];
172: hdr *b = curbf->path[lev];
173: mbuf key;
174: addr u;
175: union {
176: lfaddr *la;
177: ndaddr *na;
178: } from, to;
179: int mvd, x, i, count, n;
180: hdr *ha;
181: char a[NDSZ];
182:
183: x = (NDSZ - sizeof(hdr) - sizeof(trailer)) / 2;
184: ha = (hdr *) a;
185: mvd = count = 0;
186: tod = (dkey *)(ha + 1);
187: fromd = (dkey *)(b + 1);
188: if(lev == 0) {
189: to.la = lfadr(ha, 0);
190: from.la = lfadr(b, 0);
191: }
192: else {
193: to.na = ndadr(ha, 0);
194: from.na = ndadr(b, 0);
195: }
196: *ha = *b;
197: n = (b->kcnt + 1)/2;
198: if(lev && b->kcnt - n <= 1)
199: n--;
200: for(; count < n && mvd <= x; count++) {
201: mvgbt((char *)tod, (char *)fromd, fromd->dlen);
202: mvd += fromd->dlen;
203: tod = (dkey *)((char *)tod + fromd->dlen);
204: fromd = (dkey *)((char *)fromd + fromd->dlen);
205: if(lev) {
206: *to.na-- = *from.na--;
207: mvd += sizeof(ndaddr);
208: }
209: else if(!treeonly(curbf)) {
210: *to.la-- = *from.la--;
211: mvd += sizeof(lfaddr);
212: }
213: }
214: if(lev) { /* another pointer for non-leaves */
215: *to.na-- = *from.na--;
216: mvd += sizeof(ndaddr);
217: }
218: ha->kcnt = count;
219: nfree(ha) = NDSZ - sizeof(hdr) - sizeof(trailer) - mvd;
220: /* if lev == 0, we promote the last key, else the next key */
221: key.mlen = lastkey(ha, prefix);
222: if(lev) {
223: mvgbt(prefix + fromd->dcom, fromd->dkey, fromd->dlen - DKEYSZ);
224: key.mlen = fromd->dcom + fromd->dlen - DKEYSZ;
225: count++;
226: fromd = (dkey *)((char *)fromd + fromd->dlen);
227: }
228: u.na = newnode(ha);
229: if(u.na == EOF) { /* error while splitting */
230: curbf->fatal++;
231: return(EOF);
232: }
233: key.mdata = prefix;
234: /* other half */
235: if(lev == 0)
236: to.la = lfadr(ha, 0);
237: else
238: to.na = ndadr(ha, 0);
239: tod = (dkey *)(ha + 1);
240: tod->dcom = 0;
241: tod->dlen = fromd->dlen + fromd->dcom;
242: mvgbt(tod->dkey, prefix, fromd->dcom);
243: mvgbt(tod->dkey + fromd->dcom, fromd->dkey, fromd->dlen - DKEYSZ);
244: mvd = tod->dlen;
245: fromd = (dkey *)((char *)fromd + fromd->dlen);
246: tod = (dkey *)((char *)tod + tod->dlen);
247: if(lev) {
248: *to.na-- = *from.na--;
249: mvd += sizeof(ndaddr);
250: }
251: else if(!treeonly(curbf)) {
252: *to.la-- = *from.la--;
253: mvd += sizeof(lfaddr);
254: }
255: count++;
256: for(i = 1; count < b->kcnt; i++, count++) {
257: mvgbt((char *)tod, (char *)fromd, fromd->dlen);
258: mvd += fromd->dlen;
259: tod = (dkey *)((char *)tod + tod->dlen);
260: fromd = (dkey *)((char *)fromd + fromd->dlen);
261: if(lev) {
262: *to.na-- = *from.na--;
263: mvd += sizeof(ndaddr);
264: }
265: else if(!treeonly(curbf)) {
266: *to.la-- = *from.la--;
267: mvd += sizeof(lfaddr);
268: }
269:
270: }
271: if(lev) {
272: *to.na-- = *from.na--;
273: mvd += sizeof(ndaddr);
274: }
275: ha->kcnt = i;
276: nfree(ha) = NDSZ - sizeof(hdr) - sizeof(trailer) - mvd;
277: mvgbt((char *)b, (char *)ha, NDSZ);
278: mustwrite(curbf, lev) = 1;
279: if(lev < curbf->height) {
280: if(xinsert(lev + 1, key, u) == EOF) {
281: curbf->fatal++;
282: return(EOF);
283: }
284: }
285: else
286: return(newroot(u, key, b));
287: return(0);
288: }
289:
290: newroot(u, key, b)
291: addr u;
292: mbuf key;
293: hdr *b;
294: { hdr *x;
295: dkey *d;
296: if(curbf->height >= MXHT) {
297: errno = BTALL;
298: curbf->fatal++;
299: return(EOF);
300: }
301: if((x = curbf->path[b->hlev + 1] = (hdr *)malloc(NDSZ)) == NULL) {
302: errno = BNOMEM;
303: curbf->fatal++;
304: return(EOF);
305: }
306: *x = *b;
307: x->hlev++;
308: d = (dkey *)(x + 1);
309: d->dlen = DKEYSZ + key.mlen;
310: d->dcom = 0;
311: mvgbt(d->dkey, key.mdata, key.mlen);
312: *ndadr(x, 0) = u.na;
313: *ndadr(x, 1) = curbf->loc[b->hlev] = newnode(b);
314: x->kcnt = 1;
315: nfree(x) = NDSZ - sizeof(hdr) - sizeof(trailer) - DKEYSZ
316: - key.mlen - 2 * sizeof(ndaddr);
317: mustwrite(curbf, ++curbf->height) = 1;
318: return(0);
319: }
320:
321: lastkey(b, s)
322: hdr *b;
323: char *s;
324: { int i, n;
325: dkey *p;
326: p = (dkey *)(b + 1);
327: for(n = i = 0; i < b->kcnt; i++) {
328: mvgbt(s + p->dcom, p->dkey, p->dlen - DKEYSZ);
329: n = p->dlen + p->dcom - DKEYSZ;
330: p = (dkey *)((char *) p + p->dlen);
331: }
332: return(n);
333: }
334:
335: static struct D { struct D *a; char *b;} VER = {&VER,"\n82/10/9:bwrite.c\n"};
336: /*0010010000010101*/
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.