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