4.3BSD - /usr/ingres/source/iutil/insert_btree.c

   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: }

Defined functions