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
|
Last modified: 1986-04-17
Generated: 2016-12-26 |
Generated by src2html V0.67
page hit count: 1609 |
|