![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to insert_btree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / ingres / source / iutil|
Return to insert_btree.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ingres / source / iutil |
1.1 ! root 1: # include <btree.h> ! 2: # include <ingres.h> ! 3: # include <batch.h> ! 4: # include <symbol.h> ! 5: # include <sccs.h> ! 6: ! 7: SCCSID(@(#)insert_btree.c 8.1 12/31/84) ! 8: ! 9: /* INSERT_BTREE -- BTree insertion routine ! 10: ** ! 11: ** Insert a tid into the BTree at the position corresponding to its lid. ! 12: ** Split the leaf if necessary and adjust all values up the tree. ! 13: ** ! 14: ** Parameters : ! 15: ** tree - BTree filename (I) ! 16: ** lid - given lid (I) ! 17: ** tid - tid to be inserted into BTree leaf (I) ! 18: ** tidpos - location where tid was inserted (O) ! 19: ** ! 20: ** Returns : ! 21: ** -1 lid position does not exist ! 22: ** 0 successful insertion ! 23: */ ! 24: ! 25: insert_btree(tree, rootpage, lid, tid, tidpos, create) ! 26: ! 27: char *tree; ! 28: long rootpage; ! 29: long lid; ! 30: long *tid; ! 31: register TID *tidpos; ! 32: char create; ! 33: { ! 34: register int i, j, start; ! 35: struct locator block, p; ! 36: struct BTreeNode newblock, temp, newroot; ! 37: short rblock, tline; ! 38: long newpage, tpage; ! 39: long get_tid(), new_page(); ! 40: int save; ! 41: char replbatch[MAXNAME + 4]; ! 42: FILE *fp; ! 43: TID oldtid, newtid; ! 44: long count, page, childpage; ! 45: extern char *Fileset; ! 46: extern DESC Btreesec; ! 47: ! 48: # ifdef xATR1 ! 49: if (tTf(24,0)) ! 50: printf("inserting lid %ld into btree at rootpage %d", lid, rootpage); ! 51: # endif ! 52: ! 53: /* find location of desired lid in B-Tree */ ! 54: if (get_tid(rootpage, lid, &block) < -1) ! 55: return(-1); ! 56: ! 57: if (newroot.depth = create) ! 58: { ! 59: if (save = block.offset) ! 60: newroot.prevtree = block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[save -1]]; ! 61: else ! 62: { ! 63: if (!block.page.prevtree) ! 64: newroot.prevtree = 0; ! 65: else ! 66: { ! 67: get_node(block.page.prevtree, &temp); ! 68: newroot.prevtree = temp.node.leafnode.tid_pos[temp.node.leafnode.tid_loc[temp.nelmts - 1]]; ! 69: } ! 70: } ! 71: if (save <= block.page.nelmts - 1 && block.page.nelmts) ! 72: newroot.nexttree = block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[save]]; ! 73: else ! 74: { ! 75: if (!block.page.nexttree) ! 76: newroot.nexttree = 0; ! 77: else ! 78: { ! 79: get_node(block.page.nexttree, &temp); ! 80: newroot.nexttree = temp.node.leafnode.tid_pos[temp.node.leafnode.tid_loc[0]]; ! 81: } ! 82: } ! 83: *tid = new_page(tree); ! 84: if (block.pageno == RT) ! 85: get_node(RT, &block.page); ! 86: if (newroot.prevtree) ! 87: { ! 88: get_node(newroot.prevtree, &temp); ! 89: temp.nexttree = *tid; ! 90: write_node(newroot.prevtree, &temp); ! 91: } ! 92: if (newroot.nexttree) ! 93: { ! 94: get_node(newroot.nexttree, &temp); ! 95: temp.prevtree = *tid; ! 96: write_node(newroot.nexttree, &temp); ! 97: } ! 98: stuff_page(&newroot.prttree, &block.pageno); ! 99: newroot.nodetype = 'L'; ! 100: newroot.nelmts = 0; ! 101: newroot.parent = 0; ! 102: newroot.node.leafnode.prevleaf = 0; ! 103: newroot.node.leafnode.nextleaf = 0; ! 104: for (i = 0; i < MAXLEAVES; ++i) ! 105: newroot.node.leafnode.tid_loc[i] = newroot.node.leafnode.back_ptr[i] = i; ! 106: } ! 107: ! 108: if (block.page.nelmts != MAXLEAVES) ! 109: /* insert tid into its proper position in leaf */ ! 110: { ! 111: save = block.page.node.leafnode.tid_loc[block.page.nelmts]; ! 112: /* move other tids down to make room for new tid */ ! 113: for (i = block.page.nelmts - 1; i >= block.offset; --i) ! 114: { ! 115: block.page.node.leafnode.tid_loc[i + 1] = ! 116: block.page.node.leafnode.tid_loc[i]; ! 117: block.page.node.leafnode.back_ptr[block.page.node.leafnode.tid_loc[i]] = i + 1; ! 118: } ! 119: block.page.node.leafnode.tid_loc[block.offset] = save; ! 120: block.page.node.leafnode.tid_pos[save] = *tid; ! 121: block.page.node.leafnode.back_ptr[save] = block.offset; ! 122: ++block.page.nelmts; ! 123: write_node(block.pageno, &block.page); ! 124: if (create) ! 125: newroot.prttree.line_id = save; ! 126: ! 127: /* trace up B-Tree, incrementing key values */ ! 128: tracepath(rootpage, &block, 1); ! 129: ! 130: tpage = block.pageno; ! 131: tline = save; ! 132: } ! 133: ! 134: else ! 135: /* leaf is full, must be split */ ! 136: { ! 137: /* determine where to split leaf */ ! 138: start = MAXLEAVES / 2; ! 139: rblock = 0; ! 140: ! 141: if (block.offset > start) ! 142: /* new tid will be inserted in the new leaf */ ! 143: { ! 144: ++start; ! 145: rblock = 1; ! 146: } ! 147: ! 148: /* readjust all values in the old leaf and assign them for ! 149: ** the new leaf */ ! 150: ! 151: block.page.nelmts = start; /* assume new tid will be ! 152: ** inserted into new leaf */ ! 153: newpage = new_page(tree); ! 154: newblock.nodetype = 'L'; ! 155: for (i = 0; i < MAXLEAVES; ++i) ! 156: newblock.node.leafnode.tid_loc[i] = newblock.node.leafnode.back_ptr[i] = i; ! 157: newblock.nelmts = MAXLEAVES + 1 - start; ! 158: newblock.parent = block.page.parent; ! 159: newblock.depth = 0; ! 160: ! 161: if (newblock.node.leafnode.nextleaf = block.page.node.leafnode.nextleaf) ! 162: { ! 163: get_node(newblock.node.leafnode.nextleaf, &temp); ! 164: temp.node.leafnode.prevleaf = newpage; ! 165: write_node(newblock.node.leafnode.nextleaf, &temp); ! 166: } ! 167: block.page.node.leafnode.nextleaf = newpage; ! 168: newblock.node.leafnode.prevleaf = block.pageno; ! 169: ! 170: /* create file for storing tids that must be replaced in btree ! 171: ** secondary relation ! 172: */ ! 173: if (!bequal("_SYS", tree, 4) && !create) ! 174: { ! 175: concat(REPL_IN, Fileset, replbatch); ! 176: if ((fp = fopen(replbatch, "w")) == NULL) ! 177: syserr("can't open batch file in insert_btree"); ! 178: count = 0; ! 179: stuff_page(&oldtid, &block.pageno); ! 180: stuff_page(&newtid, &newpage); ! 181: } ! 182: ! 183: /* copy the right half of the old leaf onto the new leaf */ ! 184: for (i = 0, j = start; j < MAXLEAVES || rblock == 1; ++i) ! 185: { ! 186: if (j == block.offset && rblock == 1) ! 187: /* current position in new leaf corresponds to position ! 188: ** of new tid */ ! 189: { ! 190: newblock.node.leafnode.tid_pos[newblock.node.leafnode.tid_loc[i]] = *tid; ! 191: tline = newblock.node.leafnode.tid_loc[i]; ! 192: /* indicate that tid has been inserted */ ! 193: rblock = -1; ! 194: } ! 195: else ! 196: { ! 197: childpage = newblock.node.leafnode.tid_pos[newblock.node.leafnode.tid_loc[i]] = ! 198: block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[j]]; ! 199: if (create) ! 200: { ! 201: get_node(childpage, &temp); ! 202: stuff_page(&temp.prttree, &newpage); ! 203: temp.prttree.line_id = newblock.node.leafnode.tid_loc[i]; ! 204: write_node(childpage, &temp); ! 205: } ! 206: if (!bequal("_SYS", tree, 4) && !create) ! 207: { ! 208: oldtid.line_id = block.page.node.leafnode.tid_loc[j]; ! 209: newtid.line_id = newblock.node.leafnode.tid_loc[i]; ! 210: if (fwrite(&oldtid, 1, LIDSIZE, fp) != LIDSIZE) ! 211: syserr("write error in insert_btree"); ! 212: if (fwrite(&newtid, 1, LIDSIZE, fp) != LIDSIZE) ! 213: syserr("write error in insert_btree"); ! 214: ++count; ! 215: } ! 216: ++j; ! 217: } ! 218: } ! 219: if (!bequal("_SYS", tree, 4) && !create) ! 220: { ! 221: fclose(fp); ! 222: repl_btree(replbatch, count); ! 223: } ! 224: ! 225: if (!rblock) ! 226: /* new tid belongs in old leaf, insert it into its proper ! 227: ** position */ ! 228: { ! 229: save = block.page.node.leafnode.tid_loc[block.page.nelmts]; ! 230: for (i = block.page.nelmts - 1; i >= block.offset; --i) ! 231: { ! 232: block.page.node.leafnode.tid_loc[i + 1] = ! 233: block.page.node.leafnode.tid_loc[i]; ! 234: block.page.node.leafnode.back_ptr[block.page.node.leafnode.tid_loc[i]] = i + 1; ! 235: } ! 236: block.page.node.leafnode.tid_loc[block.offset] = save; ! 237: block.page.node.leafnode.tid_pos[save] = *tid; ! 238: block.page.node.leafnode.back_ptr[save] = block.offset; ! 239: tline = save; ! 240: /* readjust element counts to reflect that tid has been ! 241: ** placed in the old leaf */ ! 242: ++block.page.nelmts; ! 243: --newblock.nelmts; ! 244: } ! 245: ! 246: if (block.pageno == rootpage) ! 247: { ! 248: /* split leaf was the root, a new level to the B-Tree ! 249: ** must be added */ ! 250: rootsplit(tree, rootpage, &block, newpage, block.page.nelmts, newblock.nelmts); ! 251: newblock.parent = rootpage; ! 252: write_node(block.pageno, &block.page); ! 253: newblock.node.leafnode.prevleaf = block.pageno; ! 254: write_node(newpage, &newblock); ! 255: ! 256: if (create) ! 257: { ! 258: for (i = 0; i < block.page.nelmts; ++ i) ! 259: { ! 260: get_node(block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]], &temp); ! 261: stuff_page(&temp.prttree, &block.pageno); ! 262: write_node(block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]], &temp); ! 263: } ! 264: } ! 265: /* btree page has changed */ ! 266: if (!bequal("_SYS", tree, 4) && !create) ! 267: { ! 268: concat(REPL_IN, Fileset, replbatch); ! 269: if ((fp = fopen(replbatch, "w")) == NULL) ! 270: syserr("can't open batch file in insert_btree"); ! 271: count = 0; ! 272: page = 0l; ! 273: stuff_page(&oldtid, &page); ! 274: stuff_page(&newtid, &block.pageno); ! 275: for (i = 0; i < block.page.nelmts; ++i) ! 276: { ! 277: if (rblock || block.page.node.leafnode.tid_loc[i] != tline) ! 278: { ! 279: oldtid.line_id = newtid.line_id = block.page.node.leafnode.tid_loc[i]; ! 280: if (fwrite(&oldtid, 1, LIDSIZE, fp) != LIDSIZE) ! 281: syserr("write error in insert_btree"); ! 282: if (fwrite(&newtid, 1, LIDSIZE, fp) != LIDSIZE) ! 283: syserr("write error in insert_btree"); ! 284: ++count; ! 285: } ! 286: } ! 287: fclose(fp); ! 288: repl_btree(replbatch, count); ! 289: } ! 290: } ! 291: else ! 292: /* insert the pointer and key associated with new leaf into the ! 293: ** parent of the old leaf */ ! 294: { ! 295: write_node(block.pageno, &block.page); ! 296: write_node(newpage, &newblock); ! 297: p.pageno = block.page.parent; ! 298: parentkey(block.pageno, &p); ! 299: p.page.node.intnode.key[p.offset] = block.page.nelmts; ! 300: insert_key(tree, rootpage, newpage, newblock.nelmts, &p); ! 301: } ! 302: tpage = (rblock) ? newpage : block.pageno; ! 303: } ! 304: stuff_page(tidpos, &tpage); ! 305: tidpos->line_id = tline; ! 306: ! 307: if (create) ! 308: write_node(*tid, &newroot); ! 309: ! 310: } ! 311: ! 312: /* ! 313: ** Takes a pair of tids from a file and sequentially replaces the ! 314: ** old tid with the new tid in the secondary btree relation ! 315: */ ! 316: ! 317: repl_btree(replbatch, count) ! 318: register char *replbatch; ! 319: long count; ! 320: { ! 321: register int i, j; ! 322: TID uptid; ! 323: DESC d; ! 324: char tids[2 * LIDSIZE], key[2 * LIDSIZE], newkey[2 * LIDSIZE]; ! 325: extern DESC Btreesec; ! 326: ! 327: if (count > 0) ! 328: { ! 329: /* set up descriptor for sort */ ! 330: d.reloff[1] = 0; ! 331: d.reloff[2] = LIDSIZE; ! 332: d.relfrmt[1] = d.relfrmt[2] = INT; ! 333: d.relfrml[1] = d.relfrml[2] = LIDSIZE; ! 334: d.relgiven[1] = 1; ! 335: d.relgiven[2] = 2; ! 336: d.reldum.relspec = M_ORDER; ! 337: d.reldum.relatts = 2; ! 338: d.reldum.relwid = 2 * LIDSIZE; ! 339: sortfile(replbatch, &d, FALSE); ! 340: if ((Repl_outfp = fopen(ztack(REPL_OUT, Fileset), "r")) == NULL) ! 341: syserr("can't open replace file after sort in insertbtreee\n"); ! 342: clearkeys(&Btreesec); ! 343: for (i = 0; i < count; ++i) ! 344: { ! 345: if (fread(tids, 1, 2 * LIDSIZE, Repl_outfp) != 2 * LIDSIZE) ! 346: syserr("read error in insert_btree"); ! 347: setkey(&Btreesec, key, tids, 2); ! 348: if (getequal(&Btreesec, key, newkey, &uptid)) ! 349: { ! 350: printup(&Btreesec, key); ! 351: syserr("getequal error in insert_btree"); ! 352: } ! 353: /* place new tid in place */ ! 354: setkey(&Btreesec, newkey, tids + LIDSIZE, 2); ! 355: if (j = replace(&Btreesec, &uptid, newkey, TRUE)) ! 356: if (j == 1) ! 357: continue; ! 358: else ! 359: syserr("bad replace in insert_btree"); ! 360: } ! 361: fclose(Repl_outfp); ! 362: unlink(replbatch); ! 363: unlink(ztack(REPL_OUT, Fileset)); ! 364: } ! 365: } ! 366: ! 367: /* Insert a key/ptr pair into a node, splitting nodes if necessary and ! 368: ** adjusting values up the tree. ! 369: ** ! 370: ** Parameters : ! 371: ** tree - BTree filename (I) ! 372: ** p - page number of newly formed node (I) ! 373: ** k - key value of newly formed node (I) ! 374: ** pkey - information about the node whose ptr/key pair is to ! 375: ** be inserted (I, O) ! 376: */ ! 377: ! 378: insert_key(tree, rootpage, p, k, pkey) ! 379: ! 380: char *tree; ! 381: long rootpage; ! 382: long p, k; ! 383: register struct locator *pkey; ! 384: { ! 385: register int i, j, start; ! 386: struct BTreeNode newblock, temp; ! 387: long newpage, oldkey, newkey; ! 388: struct locator prt; ! 389: short rblock; ! 390: long new_page(); ! 391: ! 392: if (pkey->page.nelmts != MAXPTRS) ! 393: /* insert pointer/key pair into proper position in node by moving ! 394: ** other pairs down node */ ! 395: { ! 396: for (i = pkey->page.nelmts - 1; i >= pkey->offset + 1; --i) ! 397: { ! 398: pkey->page.node.intnode.ptr[i + 1] = ! 399: pkey->page.node.intnode.ptr[i]; ! 400: pkey->page.node.intnode.key[i + 1] = ! 401: pkey->page.node.intnode.key[i]; ! 402: } ! 403: ++pkey->page.nelmts; ! 404: pkey->page.node.intnode.ptr[pkey->offset + 1] = p; ! 405: pkey->page.node.intnode.key[pkey->offset + 1] = k; ! 406: ! 407: write_node(pkey->pageno, &pkey->page); ! 408: ! 409: /* trace up B-Tree incrementing keys */ ! 410: tracepath(rootpage, pkey, 1); ! 411: } ! 412: ! 413: else ! 414: /* node is full, must be split */ ! 415: { ! 416: /* determine where split will be made */ ! 417: start = MAXPTRS / 2; ! 418: rblock = 0; ! 419: ! 420: if (pkey->offset + 1 > start) ! 421: /* ptr/key pair will be inserted in new node */ ! 422: { ! 423: ++start; ! 424: rblock = 1; ! 425: } ! 426: ! 427: /* readjust old node values and create new node values */ ! 428: pkey->page.nelmts = start; ! 429: newpage = new_page(tree); ! 430: newblock.nodetype = 'I'; ! 431: newblock.nelmts = MAXPTRS + 1 - start; ! 432: newblock.parent = pkey->page.parent; ! 433: newblock.depth = 0; ! 434: ! 435: /* copy right side of old node into new node */ ! 436: ! 437: for (i = 0, j = start; j < MAXPTRS || rblock == 1; ++i) ! 438: { ! 439: if (j == pkey->offset + 1 && rblock == 1) ! 440: /* node position corresponds to that of new ptr/key pair */ ! 441: { ! 442: newblock.node.intnode.ptr[i] = p; ! 443: newblock.node.intnode.key[i] = k; ! 444: /* make sure children of newblock have proper ! 445: ** parent */ ! 446: get_node(p, &temp); ! 447: temp.parent = newpage; ! 448: write_node(p, &temp); ! 449: ! 450: rblock = -1; ! 451: } ! 452: else ! 453: { ! 454: newblock.node.intnode.ptr[i] = ! 455: pkey->page.node.intnode.ptr[j]; ! 456: newblock.node.intnode.key[i] = ! 457: pkey->page.node.intnode.key[j]; ! 458: /* make sure children of newblock have proper ! 459: ** parent */ ! 460: get_node(newblock.node.intnode.ptr[i], &temp); ! 461: temp.parent = newpage; ! 462: write_node(newblock.node.intnode.ptr[i], &temp); ! 463: ++j; ! 464: } ! 465: } ! 466: ! 467: if (!rblock) ! 468: /* insert new ptr/key pair into proper position in old node */ ! 469: { ! 470: for (i = pkey->page.nelmts - 1; i >= pkey->offset + 1; --i) ! 471: { ! 472: pkey->page.node.intnode.ptr[i + 1] = ! 473: pkey->page.node.intnode.ptr[i]; ! 474: pkey->page.node.intnode.key[i + 1] = ! 475: pkey->page.node.intnode.key[i]; ! 476: } ! 477: pkey->page.node.intnode.ptr[pkey->offset + 1] = p; ! 478: pkey->page.node.intnode.key[pkey->offset + 1] = k; ! 479: ++pkey->page.nelmts; ! 480: --newblock.nelmts; ! 481: } ! 482: ! 483: /* calculate the key values of the old and new nodes */ ! 484: oldkey = 0; ! 485: for (i = 0; i < pkey->page.nelmts; ++i) ! 486: oldkey += pkey->page.node.intnode.key[i]; ! 487: newkey = 0; ! 488: for (i = 0; i < newblock.nelmts; ++i) ! 489: newkey += newblock.node.intnode.key[i]; ! 490: ! 491: if (pkey->pageno == rootpage) ! 492: { ! 493: /* split node was root, add a new level to B-Tree */ ! 494: rootsplit(tree, rootpage, pkey, newpage, oldkey, newkey); ! 495: newblock.parent = rootpage; ! 496: write_node(pkey->pageno, &pkey->page); ! 497: write_node(newpage, &newblock); ! 498: } ! 499: ! 500: else ! 501: /* recursively add ptr/key pair corresponding to new node into ! 502: ** the parent of the old node */ ! 503: { ! 504: write_node(pkey->pageno, &pkey->page); ! 505: write_node(newpage, &newblock); ! 506: prt.pageno = pkey->page.parent; ! 507: parentkey(pkey->pageno, &prt); ! 508: prt.page.node.intnode.key[prt.offset] = oldkey; ! 509: insert_key(tree, rootpage, newpage, newkey, &prt); ! 510: } ! 511: } ! 512: } ! 513: ! 514: /* Form a new root with two children since the old root was split. ! 515: ** ! 516: ** Parameters : ! 517: ** tree - BTree filename (I) ! 518: ** oldroot - split root (I, O) ! 519: ** rpageno - page number of new root's right child (I) ! 520: ** rkey - key of new root's right child (I) ! 521: */ ! 522: ! 523: rootsplit(tree, rootpage, oldroot, rpageno, lkey, rkey) ! 524: ! 525: char *tree; ! 526: long rootpage; ! 527: register struct locator *oldroot; ! 528: long rpageno, lkey, rkey; ! 529: { ! 530: struct BTreeNode newroot, temp; ! 531: long i; ! 532: ! 533: /* get a new page for the former root */ ! 534: oldroot->pageno = new_page(tree); ! 535: ! 536: newroot.depth = oldroot->page.depth; ! 537: newroot.prevtree = oldroot->page.prevtree; ! 538: newroot.nexttree = oldroot->page.nexttree; ! 539: bmove(&oldroot->page.prttree, &newroot.prttree, LIDSIZE); ! 540: newroot.nodetype = 'I'; ! 541: newroot.nelmts = 2; ! 542: newroot.parent = oldroot->page.parent; ! 543: oldroot->page.parent = rootpage; ! 544: oldroot->page.depth = 0; ! 545: newroot.node.intnode.key[0] = lkey; ! 546: newroot.node.intnode.ptr[0] = oldroot->pageno; ! 547: newroot.node.intnode.key[1] = rkey; ! 548: newroot.node.intnode.ptr[1] = rpageno; ! 549: ! 550: write_node(rootpage, &newroot); ! 551: ! 552: if (oldroot->page.nodetype == 'I') ! 553: /* make sure the children of the oldroot have the correct parent */ ! 554: for (i = 0; i < oldroot->page.nelmts; ++i) ! 555: { ! 556: get_node(oldroot->page.node.intnode.ptr[i], &temp); ! 557: temp.parent = oldroot->pageno; ! 558: write_node(oldroot->page.node.intnode.ptr[i], &temp); ! 559: } ! 560: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.