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