1: # include   <stdio.h>
   2: # include   <btree.h>
   3: # include   <ingres.h>
   4: # include   <batch.h>
   5: # include   <sccs.h>
   6: 
   7: SCCSID(@(#)delete_btree.c	8.1	12/31/84)
   8: 
   9: /*	DELETE_BTREE -- BTree deletion routine
  10: **
  11: **	Deletes a tid from a leaf node and adjusts all values up the tree
  12: **
  13: **	Parameters :
  14: **		tree - BTree filename (I)
  15: **		lid - lid to be deleted (I)
  16: **
  17: **	Returns :
  18: **		> 0 	success
  19: **		< 0 	bad lid
  20: */
  21: 
  22: delete_btree(lid, level)
  23: long lid[];
  24: register int level;
  25: 
  26: {
  27:     register int        i, j;
  28:     struct locator      tid[MAXLID];
  29:     register int        save;
  30:     int         num[MAXLID];
  31:     int         del[MAXLID];
  32:     long            page[MAXLID + 1], t;
  33:     struct BTreeNode    temp;
  34: 
  35: #	ifdef xATR1
  36:     if(tTf(24,0))
  37:         printf("deleting lid %ld from tree ", lid);
  38: #	endif
  39: 
  40:     page[0] = RT;
  41:     for (i = 0; i < level; ++i)
  42:     {
  43:         if ((t = get_tid(page[i], lid[i], &tid[i])) < 0)
  44:             return(-1);
  45:         del[i] = 0;
  46:         num[i] = tid[i].page.nelmts;
  47:         page[i+1] = t;
  48:     }
  49: 
  50:     del[level-1] = 1;
  51:     for (i = level - 2; i >= 0; --i)
  52:     {
  53:         if (num[i + 1] == 1 && del[i + 1] == 1)
  54:             del[i] = 1;
  55:     }
  56: 
  57:     for (i = 0; i < level; ++i)
  58:     {
  59:         if (del[i])
  60:         {
  61:             ++Repl_cnt[i];
  62:             for (j = i - 1; j >= 0; --j)
  63:                 Prev_lid[j] = lid[j];
  64:             /* remove tid from leaf */
  65:             if (tid[i].offset != tid[i].page.nelmts - 1)
  66:             {
  67:                 save = tid[i].page.node.leafnode.tid_loc[tid[i].offset];
  68:                 for (j = tid[i].offset; j < tid[i].page.nelmts; ++j)
  69:                 {
  70:                     tid[i].page.node.leafnode.tid_loc[j] =
  71:                         tid[i].page.node.leafnode.tid_loc[j + 1];
  72:                     tid[i].page.node.leafnode.back_ptr[tid[i].page.node.leafnode.tid_loc[j]] = j;
  73:                 }
  74:                 tid[i].page.node.leafnode.tid_loc[tid[i].page.nelmts - 1] = save;
  75:                 tid[i].page.node.leafnode.back_ptr[save] = tid[i].page.nelmts - 1;
  76:             }
  77:             --tid[i].page.nelmts;
  78: 
  79:             if (tid[i].page.nelmts != 0)
  80:             {
  81:                 write_node(tid[i].pageno, &tid[i].page);
  82:                 /* leaf is now empty as a result of deletion, decrement keys
  83: 				** up tree */
  84:                 tracepath(page[i], &tid[i], -1);
  85:             }
  86: 
  87:             else if (tid[i].pageno != page[i])
  88:             {
  89:                 /* key/ptr pair corresponding to empty leaf must be removed */
  90:                 delete_key(page[i], &tid[i]);
  91:             }
  92:             else if (lid[i] == 1 && page[i] != RT)
  93:             {
  94:                 if (tid[i].page.prevtree)
  95:                 {
  96:                     get_node(tid[i].page.prevtree, &temp);
  97:                     temp.nexttree = tid[i].page.nexttree;
  98:                     write_node(tid[i].page.prevtree, &temp);
  99:                 }
 100:                 if (tid[i].page.nexttree)
 101:                 {
 102:                     get_node(tid[i].page.nexttree, &temp);
 103:                     temp.prevtree = tid[i].page.prevtree;
 104:                     write_node(tid[i].page.nexttree, &temp);
 105:                 }
 106:                 return_page(page[i]);
 107:             }
 108:             else
 109:                 write_node(page[i], &tid[i].page);
 110:         }
 111:     }
 112:     return(0);
 113: }
 114: 
 115: /*	Returns an empty page to the empty file space list.  Removes key/ptr
 116: ** 	pair corresponding to empty node from tree.  Combines and distributes
 117: **	pairs if a node has less than the minimum number of values.  Adjusts
 118: **	all values up the tree.
 119: **
 120: **	Parameters :
 121: **		tree - BTree filename (I)
 122: **		empty - empty node (I)
 123: */
 124: 
 125: delete_key(rootpage, empty)
 126: 
 127: long rootpage;
 128: register struct locator *empty;
 129: {
 130:     struct locator      prt, gprt, sibling;
 131:     register int        i;
 132:     struct BTreeNode    new, temp;
 133:     long            pkey, skey;
 134:     extern char     *Fileset;
 135:     char            replbatch[MAXNAME + 4];
 136:     FILE            *fp;
 137:     long            count, page;
 138:     TID         oldtid, newtid;
 139: 
 140:     /* find parent corresponding to empty node, and remove ptr/key pair
 141: 	** from parent */
 142:     prt.pageno = empty->page.parent;
 143:     parentkey(empty->pageno, &prt);
 144:     if (prt.offset != prt.page.nelmts - 1)
 145:     {
 146:         for (i = prt.offset; i < prt.page.nelmts; ++i)
 147:         {
 148:             prt.page.node.intnode.ptr[i] =
 149:                 prt.page.node.intnode.ptr[i + 1];
 150:             prt.page.node.intnode.key[i] =
 151:                 prt.page.node.intnode.key[i + 1];
 152:         }
 153:     }
 154:     --prt.page.nelmts;
 155: 
 156:     if (empty->page.nodetype == 'L')
 157:     /* adjust previous and next fields of leaves */
 158:     {
 159:         if (empty->page.node.leafnode.nextleaf != 0)
 160:         {
 161:             get_node(empty->page.node.leafnode.nextleaf, &temp);
 162:             temp.node.leafnode.prevleaf = empty->page.node.leafnode.prevleaf;
 163:             write_node(empty->page.node.leafnode.nextleaf, &temp);
 164:         }
 165:         if (empty->page.node.leafnode.prevleaf != 0)
 166:         {
 167:             get_node(empty->page.node.leafnode.prevleaf, &temp);
 168:             temp.node.leafnode.nextleaf = empty->page.node.leafnode.nextleaf;
 169:             write_node(empty->page.node.leafnode.prevleaf, &temp);
 170:         }
 171:     }
 172: 
 173:     /* return empty node to empty file space */
 174:     return_page(empty->pageno);
 175: 
 176:     if (prt.page.nelmts >= (int) ((float) MAXPTRS / 2 + 0.5))
 177:     {
 178:         write_node(prt.pageno, &prt.page);
 179:         /* node still has proper number of elements, decrement key
 180: 		** values up the tree */
 181:         tracepath(rootpage, &prt, -1);
 182:     }
 183: 
 184:     else if (prt.pageno == rootpage && prt.page.nelmts < 2)
 185:     /* root has only one child, a leaf; root becomes leaf node */
 186:     {
 187:         /* move leaf values into root; root's position always remains
 188: 		** the same */
 189:         get_node(prt.page.node.intnode.ptr[0], &new);
 190:         new.parent = prt.page.parent;
 191:         write_node(rootpage, &new);
 192:         return_page(prt.page.node.intnode.ptr[0]);
 193:         if (new.nodetype  == 'I')
 194:         {
 195:             for (i = 0; i < new.nelmts; ++i)
 196:             {
 197:                 get_node(new.node.intnode.ptr[i], &temp);
 198:                 temp.parent = rootpage;
 199:                 write_node(new.node.intnode.ptr[i], &temp);
 200:             }
 201:         }
 202:         else
 203:         {
 204:             /* btree tid is being changed, must be reflected in
 205: 			** secondary btree relation
 206: 			*/
 207:             concat(REPL_IN, Fileset, replbatch);
 208:             if ((fp = fopen(replbatch, "w")) == NULL)
 209:                 syserr("can't open replbatch in delete_btree");
 210:             count = 0;
 211:             page = 0l;
 212:             stuff_page(&newtid, &page);
 213:             stuff_page(&oldtid, &prt.page.node.intnode.ptr[0]);
 214:             for (i = 0; i < new.nelmts; ++i)
 215:             {
 216:                 oldtid.line_id = newtid.line_id = new.node.leafnode.tid_loc[i];
 217:                 if (fwrite(&oldtid, 1, LIDSIZE, fp) != LIDSIZE)
 218:                     syserr("write error in delete_btree");
 219:                 if (fwrite(&newtid, 1, LIDSIZE, fp) != LIDSIZE)
 220:                     syserr("write error in delete_btree");
 221:                 ++count;
 222:             }
 223:             fclose(fp);
 224:             repl_btree(replbatch, count);
 225:             unlink(replbatch);
 226:             unlink(ztack(REPL_OUT, Fileset));
 227:         }
 228:     }
 229: 
 230:     else if (prt.pageno != rootpage)
 231:     {
 232:         /* find the grandparent of the empty node */
 233:         gprt.pageno = prt.page.parent;
 234:         parentkey(prt.pageno, &gprt);
 235:         if (gprt.page.nelmts - 1 != gprt.offset)
 236:         {
 237:             /* determine the right sibling of the parent node */
 238:             sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset + 1];
 239:             get_node(sibling.pageno, &sibling.page);
 240: 
 241:             if (sibling.page.nelmts > MAXPTRS / 2 + 1)
 242:             /* distribute key/ptr pairs of parent and right sibling
 243: 			** between the two nodes (since there are sufficient
 244: 			** pairs to guarantee that both will have at the least
 245: 			** the minimum number of required children) */
 246:             {
 247:                 distribute(&prt, &sibling, &pkey, &skey);
 248:                 /* adjust key values in grandparent */
 249:                 gprt.page.node.intnode.key[gprt.offset] = pkey;
 250:                 gprt.page.node.intnode.key[gprt.offset + 1] = skey;
 251:                 write_node(gprt.pageno, &gprt.page);
 252:                 tracepath(rootpage, &gprt, -1);
 253:                 return;
 254:             }
 255:         }
 256:         if (gprt.offset != 0)
 257:         {
 258:             /* determine the left sibling of the parent node */
 259:             sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset - 1];
 260:             get_node(sibling.pageno, &sibling.page);
 261: 
 262:             if (sibling.page.nelmts > MAXPTRS / 2 + 1)
 263:             /* distribute key/ptr pairs of parent and left sibling
 264: 			** between the two nodes */
 265:             {
 266:                 distribute(&sibling, &prt, &skey, &pkey);
 267:                 gprt.page.node.intnode.key[gprt.offset - 1] = skey;
 268:                 gprt.page.node.intnode.key[gprt.offset] = pkey;
 269:                 write_node(gprt.pageno, &gprt.page);
 270:                 tracepath(rootpage, &gprt, -1);
 271:                 return;
 272:             }
 273:         }
 274: 
 275:         if (gprt.page.nelmts - 1 != gprt.offset)
 276:         /* combine parent node with its right sibling */
 277:         {
 278:             sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset + 1];
 279:             get_node(sibling.pageno, &sibling.page);
 280:             combine(&prt, &sibling);
 281:         }
 282:         else
 283:         /* combine parent node with its left sibling */
 284:         {
 285:             sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset - 1];
 286:             get_node(sibling.pageno, &sibling.page);
 287:             combine(&sibling, &prt);
 288:             /* grandparent should point to newly combined block,
 289: 			** the left sibling */
 290:             --gprt.offset;
 291:         }
 292: 
 293:         get_node(gprt.page.node.intnode.ptr[gprt.offset], &new);
 294:         if (gprt.pageno == rootpage && gprt.page.nelmts == 2)
 295:         /* root has only one child, reduce B-Tree level */
 296:         {
 297:             /* only child becomes root */
 298:             new.parent = gprt.page.parent;
 299:             write_node(rootpage, &new);
 300: 
 301:             /* make sure "new's" children's parent is the root */
 302:             for (i = 0; i < new.nelmts; ++i)
 303:             {
 304:                 get_node(new.node.intnode.ptr[i], &temp);
 305:                 temp.parent = rootpage;
 306:                 write_node(new.node.intnode.ptr[i], &temp);
 307:             }
 308:             /* both of root's children empty */
 309:             return_page(gprt.page.node.intnode.ptr[gprt.offset + 1]);
 310:             return_page(gprt.page.node.intnode.ptr[gprt.offset]);
 311:         }
 312: 
 313:         else
 314:         {
 315:             /* adjust key value in grandparent node */
 316:             pkey = 0;
 317:             for (i = 0; i < new.nelmts; ++i)
 318:                 pkey += new.node.intnode.key[i];
 319:             gprt.page.node.intnode.key[gprt.offset] = pkey;
 320:             write_node(gprt.pageno, &gprt.page);
 321: 
 322:             /* remove ptr/key pair corresponding to empty node */
 323:             gprt.pageno = gprt.page.node.intnode.ptr[gprt.offset + 1];
 324:             get_node(gprt.pageno, &gprt.page);
 325:             delete_key(rootpage, &gprt);
 326:         }
 327: 
 328:     }
 329: }
 330: 
 331: /*	Divides key/ptr pairs between the left and right nodes, so both will
 332: **	have the proper number of elements.
 333: **
 334: **	Parameters :
 335: **		tree - BTree filename (I)
 336: **		left - left node (I, O)
 337: **		right - "left's" right sibling (I, O)
 338: **		lkey - key value of the parent of left node (O)
 339: **		rkey - key value of the parent of right node (O)
 340: */
 341: 
 342: distribute(left, right, lkey, rkey)
 343: 
 344: register struct locator *left, *right;
 345: int *lkey, *rkey;
 346: {
 347:     register int        i, move;
 348:     struct BTreeNode    temp;
 349: 
 350:     if (right->page.nelmts > left->page.nelmts)
 351:     /* move elements from the right node to the left node */
 352:     {
 353:         move = MAXPTRS / 2 - left->page.nelmts;
 354: 
 355:         for (i = 1; i <= move; ++i)
 356:         /* move first part of right node into the end of the left node */
 357:         {
 358:             left->page.node.intnode.ptr[i + left->page.nelmts] =
 359:                 right->page.node.intnode.ptr[i - 1];
 360:             left->page.node.intnode.key[i + left->page.nelmts] =
 361:                 right->page.node.intnode.key[i - 1];
 362:             /* adjust parents of children whose parents have been
 363: 			** moved */
 364:             get_node(left->page.node.intnode.ptr[i + left->page.nelmts], &temp);
 365:             temp.parent = left->pageno;
 366:             write_node(left->page.node.intnode.ptr[i + left->page.nelmts], &temp);
 367:         }
 368:         left->page.nelmts += move;
 369: 
 370:         for (i = move; i < right->page.nelmts; ++i)
 371:         /* flush right node values to the left */
 372:         {
 373:             right->page.node.intnode.ptr[i - move] =
 374:                 right->page.node.intnode.ptr[i];
 375:             right->page.node.intnode.key[i - move] =
 376:                 right->page.node.intnode.key[i];
 377:         }
 378:         right->page.nelmts -= move;
 379:     }
 380: 
 381:     else
 382:     /*  move left node values to the right node */
 383:     {
 384:         move = MAXPTRS / 2 - right->page.nelmts + 1;
 385: 
 386:         /* move right node values to the right to make room for left
 387: 		** node values */
 388:         for (i = right->page.nelmts - 1; i >= 0; --i)
 389:         {
 390:             right->page.node.intnode.ptr[i + move] =
 391:                 right->page.node.intnode.ptr[i];
 392:             right->page.node.intnode.key[i + move] =
 393:                 right->page.node.intnode.key[i];
 394:         }
 395: 
 396:         /* move latter part of left node into the now free space at the
 397: 		** beginning of the right node */
 398:         for (i = 0; i < move; ++i)
 399:         {
 400:             right->page.node.intnode.ptr[i] =
 401:                 left->page.node.intnode.ptr[left->page.nelmts - move + i];
 402:             right->page.node.intnode.key[i] =
 403:                 left->page.node.intnode.key[left->page.nelmts - move + i];
 404:             /* adjust parents of children whose parents have been
 405: 			** moved */
 406:             get_node(right->page.node.intnode.ptr[i], &temp);
 407:             temp.parent = right->pageno;
 408:             write_node(right->page.node.intnode.ptr[i], &temp);
 409:         }
 410:         left->page.nelmts -= move;
 411:         right->page.nelmts += move;
 412:     }
 413: 
 414:     /* calculate key values for parents of the left and right nodes */
 415:     *lkey = 0;
 416:     for (i = 0; i < left->page.nelmts; ++i)
 417:         *lkey += left->page.node.intnode.key[i];
 418:     *rkey = 0;
 419:     for (i = 0; i < right->page.nelmts; ++i)
 420:         *rkey += right->page.node.intnode.key[i];
 421:     write_node(left->pageno, &left->page);
 422:     write_node(right->pageno, &right->page);
 423: }
 424: 
 425: /*	Combines left and right nodes together to form one node.
 426: **
 427: **	Parameters :
 428: **		tree - BTree filename (I)
 429: **		left - left node (I, O)
 430: **		right - "left's" right sibling (I)
 431: */
 432: 
 433: combine(left, right)
 434: 
 435: register struct locator *left, *right;
 436: {
 437:     register int        i;
 438:     struct BTreeNode    temp;
 439: 
 440:     /* move all ptr/key values in the right node to the end of the left node */
 441:     for (i = 0; i < right->page.nelmts; ++i)
 442:     {
 443:         left->page.node.intnode.ptr[left->page.nelmts + i] =
 444:             right->page.node.intnode.ptr[i];
 445:         left->page.node.intnode.key[left->page.nelmts + i] =
 446:             right->page.node.intnode.key[i];
 447:         /* adjust parents of children whose parents have been moved */
 448:         get_node(left->page.node.intnode.ptr[left->page.nelmts + i], &temp);
 449:         temp.parent = left->pageno;
 450:         write_node(left->page.node.intnode.ptr[left->page.nelmts + i], &temp);
 451:     }
 452:     left->page.nelmts += right->page.nelmts;
 453:     write_node(left->pageno, &left->page);
 454: }

Defined functions

combine defined in line 433; used 2 times
delete_btree defined in line 7; used 1 times
delete_key defined in line 125; used 2 times
distribute defined in line 342; used 2 times
Last modified: 1986-04-17
Generated: 2016-12-26
Generated by src2html V0.67
page hit count: 1140
Valid CSS Valid XHTML 1.0 Strict